Библиотека NumPy

В стандартном дистрибутиве Python нет функций для операций над матрицами. Хотя их несложно написать самостоятельно, но лучше установить пакет NumPy, который не только предоставляет объект matrix и поддерживает все необходимые операции, но и сравним по производительности с коммерческими программами. Загрузить этот пакет можно с сайта http://numpy.scipy.org.

Дополнительную информацию об установке пакета NumPy см. в приложении А.

NumPy предоставляет объект matrix, конструктору которого передается список списков. Он очень похож на ту матрицу, которую мы создали для представления новостей. Чтобы увидеть пакет NumPy в действии, импортируйте его в интерактивном сеансе и создайте матрицу:

>>> from numpy import * >>> l1=[[1,2,3],[4,5,6]]

>>> l1

[[1, 2, 3], [4, 5, 6]] >>> m1=matrix(l1)

>>> m1

matrix([[1, 2, 3], [4, 5, 6]])

Объекты-матрицы поддерживают такие математические операции, как сложение и умножение с помощью стандартных операторов. Для транспонирования матрицы применяется функция transpose: >>> m2=matrix([[1,2],[3,4],[5,6]])

>>> m2

matrix([[1, 2], [3, 4], [5, 6]]) >>> m1*m2

matrix([[22, 28], [49, 64]])

Функция shape возвращает количество строк и столбцов матрицы, что полезно для обхода всех ее элементов в цикле:

>>> shape(m1)

(2, 3)

>>> shape(m2)

(3, 2)

Наконец, пакет NumPy предоставляет также высокопроизводительный объект-массив array, который, как и матрица, может быть многомерным. Матрицу можно легко преобразовать в массив и наоборот. При выполнении умножения массив ведет себя иначе, чем матрица; массивы можно перемножать, только если они имеют в точности одинаковую форму, причем каждый элемент произведения вычисляется перемножением соответственных элементов сомножителей. Например:

>>> a1=m1.A

>>> a1

array([[1, 2, 3],

[4, 5, 6]]) >>> a2=array([[1,2,3],[1,2,3]]) >>> a1*a2

array([[ 1, 4, 9],

[ 4, 10, 18]])

Высокая производительность NumPy критически важна для работы алгоритма, который, как вы скоро увидите, выполняет много операций над матрицами.

Алгоритм

Описываемый алгоритм факторизации матриц впервые был опубликован в конце 1990-х годов и является одним из самых современных алгоритмов, рассматриваемых в настоящей книге. Было показано, что он очень хорошо работает для определенного класса задач, в частности для автоматического распознавания черт лица по фотографиям.

Алгоритм пытается максимально близко реконструировать матрицу новостей путем вычисления оптимальных матриц признаков и весов. В данном случае было бы полезно иметь способ измерения степени близости результата. Функция difcost перебирает все значения в двух матрицах одинакового размера и вычисляет квадраты разностей между ними.

Создайте файл nmf.py и включите в него функцию difcost:

from numpy import *

def difcost(a,b): dif=0

# Цикл по строкам и столбцам матрицы for i in range(shape(a)[0]): for j in range(shape(a)[1]): # Суммируем квадраты разностей dif+=pow(a[i,]]-b[i,]],2) return dif

Теперь нужно придумать, как постепенно изменять матрицы, чтобы эта целевая функция уменьшалась. Ранее мы заметили, что это действительно целевая функция, поэтому для поиска хорошего решения можно применить алгоритм имитации отжига или генетический алгоритм. Однако в данном случае более эффективно использование мультипликативных правил обновления. Вывод этих правил выходит за рамки книги, но, если вам интересно, ознакомьтесь с оригинальной статьей по адресу http://hebb.mit.edu/ people/seung/papers/nmfconverge.pdf.

Согласно этим правилам генерируются четыре новых матрицы. В описании исходная матрица новостей называется матрицей данных:

hn

Произведение транспонированной матрицы весов и матрицы данных.

hd

Произведение транспонированной матрицы весов, самой матрицы весов и матрицы признаков.

wn

Произведение матрицы данных и транспонированной матрицы признаков.

wd

Произведение матрицы весов, матрицы признаков и транспонированной матрицы признаков.

Для обновления матриц признаков и весов все эти матрицы преобразуются в массивы. Каждый элемент матрицы признаков умножается на соответственный элемент hn и делится на соответственный элемент hd. Аналогично, каждый элемент матрицы весов умножается на соответственный элемент wn и делится на элемент wd.

Функция factorize выполняет все эти вычисления. Добавьте ее в файл nmf.py:

def factorize(v,pc=10,iter=50): ic=shape(v)[0] fc=shape(v)[1]

#       Матрицы весов и признаков инициализируются случайными значениями w=matrix([[random.random( ) for j in range(pc)] for i in range(ic)]) h=matrix([[random.random( ) for i in range(fc)] for i in range(pc)])

#       Выполняем операцию не более iter раз for i in range(iter):

wh=w*h

#       Вычисляем текущую разность cost=difcost(v,wh)

if i%%10==0: print cost

#       Выходим из цикла, если матрица уже факторизована if cost==0: break

#       Обновляем матрицу признаков hn=(transpose(w)*v) hd=(transpose(w)*w*h)

h=matrix(array(h)*array(hn)/array(hd))

#       Обновляем матрицу весов wn=(v*transpose(h)) wd=(w*h*transpose(h))

w=matrix(array(w)*array(wn)/array(wd))

return w,h

Функции, которая факторизует матрицу, необходимо указать, сколько признаков вы хотите обнаружить. Иногда количество признаков заранее известно (два голоса в записи или пять главных новостей за день). В других случаях о количестве признаков ничего нельзя сказать. Не существует общего способа автоматически определить правильное число признаков, но путем экспериментов можно подобрать подходящий диапазон.

Попробуйте выполнить этот алгоритм для матрицы размерностью m1*m2 в текущем сеансе и посмотрите, найдет ли алгоритм решение, похожее на исходную матрицу: >>> import nmf

>>> w,h= nmf.factorize(m1*m2,pc=3,iter=100)

7632.94395925 0.0364091326734

1.12810164789e-017 6.8747907867e-020 >>> w*h

matrix([[ 22., 28.], [ 49., 64.]]) >>> m1*m2

matrix([[22, 28], [49, 64]])

Алгоритм сумел подобрать матрицы весов и признаков так, что при их перемножении получается в точности исходная матрица. Применим его к матрице новостей и посмотрим, как он справится с задачей выделения существенных признаков (на это может уйти заметное время): >>> v=matrix(wordmatrix)

>>> weights,feat=nmf.factorize(v,pc=20,iter=50)

1712024.47944 2478.13274637 2265.75996871 2229.07352131 2211.42204622

Теперь в переменной feat хранятся признаки, а в переменной weights – значения, характеризующие релевантность признаков новостям. Простой взгляд на матрицу ничего не дает, а хотелось бы как-то визуализировать и интерпретировать результаты.

Вывод результатов

Довольно сложно решить, как именно визуализировать результаты. Каждому свойству в матрице признаков соответствует набор весов, показывающих, как сильно связано с этим признаком каждое слово. Поэтому можно попытаться вывести пять-десять слов для каждого признака, чтобы узнать, какие слова для него наиболее характерны. Аналогично, столбец в матрице весов говорит о том, в какой мере этот признак соотносится с каждой новостью, поэтому было бы также интересно показать верхние три новости для данного признака вместе с индексом релевантности.

Добавьте в файл newsfeatures.py функцию showfeatures:

from numpy import *

def showfeatures(w,h,titles,wordvec,out=’features.txt’): outfile=file(out,’w’) pc,wc=shape(h)

toppatterns=[[] for i in range(len(titles))] patternnames=[]

# Цикл по всем признакам for i in range(pc): slist=[]

# Создаем список слов и их весов for j in range(wc):

slist.append((h[i,]],wordvec[]]))

#       Сортируем список слов в порядке убывания slist.sort( )

slist.reverse( )

#       Печатаем первые шесть элементов n=[s[1] for s in slist[0:6]] outfile.write(str(n)+’\n’) patternnames.append(n)

#       Создаем список слов для этого признака flist=[]

for j in range(len(titles)): # Добавляем новость вместе с ее весом flist.append((w[],i],titles[]])) toppatterns[]].append((w[],i],i,titles[]]))

#       Сортируем список в порядке убывания flist.sort( )

flist.reverse( )

#       Выводим первые три новости for f in flist[0:3]:

outfile.write(str(f)+’\n’) outfile.write(‘\n’)

outfile.close( )

# Возвращаем списки слов и новостей для дальнейшего использования return toppatterns,patternnames

Эта функция в цикле перебирает все признаки и создает список всех слов и их весов из вектора слов. Затем этот список сортируется так, чтобы слова с наибольшим весом оказались в начале, и первые шесть слов печатаются. Это должно дать представление о том, какая тема соответствует данному признаку. Функция возвращает список наиболее четких паттернов и их названий, чтобы не вычислять их каждый раз заново при использовании в функции showarticles, показанной ниже. После вывода признака функция перебирает заголовки всех новостей и сортирует их в соответствии со значениями в матрице весов для данной новости и признака. Далее печатаются три новости, наиболее релевантные текущему признаку, вместе со значениями из матрицы весов. Вы увидите, что иногда признак релевантен нескольким новостям, а иногда – только одной.

Вызовите эту функцию, чтобы посмотреть, какие признаки найдены: >>> reload(newsfeatures)

<module ‘newsfeatures’ from ‘newsfeatures.py’>

>>> topp,pn= newsfeatures.showfeatures(weights,feat,artt,wordvec)

Поскольку список результатов длинный, программа сохраняет его в текстовом файле. При вызове функции мы попросили выделить

20 признаков. Очевидно, что в сотнях новостей тем будет гораздо больше, но хочется надеяться, что самые важные мы все-таки выявим. Вот пример:

[u’palestinian’, u’elections’, u’abbas’, u’fatah’, u’monday’, u’new’] (14.189453058041485, u’US Backs Early Palestinian Elections – ABC News’) (12.748863898714507, u’Abbas Presses for New Palestinian Elections Despite Violence’)

(11.286669969240645, u’Abbas Determined to Go Ahead With Vote’) Видно, что этому признаку релевантны слова, относящиеся к выборам в Палестине, и имеется целая подборка статей на эту тему. Поскольку результат определяется как заголовком, так и текстом новости, то вторая и третья новости оказались ассоциированы с этим свойством, хотя в их заголовках нет ни одного слова из списка. Кроме того, поскольку наиболее важны слова, встречающихся во многих новостях, то слова palestinian (палестинский) и elections (выборы) оказались на первых местах.

Для некоторых признаков такой четкой подборки новостей нет, но результаты все равно интересны. Взгляните:

[u’cancer’, u’fat’, u’low’, u’breast’, u’news’, u’diet’] (29.808285029040864, u’Low-Fat Diet May Help Breast Cancer’) (2.3737882572527238, u’Big Apple no longer Fat City’) (2.3430261571622881, u’The Nose Knows Better’)

Очевидно, этот признак наиболее тесно связан с новостью о раке груди (breast cancer). Однако и новости с более слабой ассоциацией тоже касаются здоровья. По-видимому, в них встречаются какие-то слова, общие с первой новостью.

Вывод новости

Другой способ визуализировать данные – показать каждую новость и три наиболее релевантных ей признака. Это даст возможность понять, обсуждаются ли в новости несколько тем одинаковой важности или она посвящена главным образом одной теме. Добавьте в файл newsfeatures.py функцию showarticles:

def showarticles(titles,toppatterns,patternnames,out=’articles.txt’): outfile=file(out,’w’)

# Цикл по всем новостям for j in range(len(titles)): outfile.write(titles[]].encode(‘utf8′)+’\n’)

#      Получить наиболее релевантные этой новости признаки

#      и отсортировать их в порядке убывания toppatterns[]].sort( ) toppatterns[]].reverse( )

# Напечатать три верхних признака for i in range(3):

outfile.write(str(toppatterns[]][i][0])+’ ‘+

str(patternnames[toppatterns[]][i][1]])+’\n’) outfile.write(‘\n’)

outfile.close( )

Так как релевантные каждой статье признаки были вычислены функцией showfeatures, то здесь нам остается только обойти все новости, напечатать их названия и для каждой вывести три основных признака. Для тестирования перезагрузите модуль newsfeatures.py и вызовите функцию showfeatures: >>> reload(newsfeatures)

<module ‘newsfeatures’ from ‘newsfeatures.py’> >>> newsfeatures.showarticles(artt,topp,pn)

В результате будет создан файл articles.txt, который содержит заголовки новостей и наиболее характерные для них паттерны. Вот пример новости, в которой обсуждаются две одинаково важные темы:

Attacks in Iraq at record high: Pentagon

5.4890098003 [u’monday’, u’said’, u’oil’, u’iraq’, u’attacks’, u’two’] 5.33447632219 [u’gates’, u’iraq’, u’pentagon’, u’washington’, u’over’, u’report’]

0.618495842404 [u’its’, u’iraqi’, u’baghdad’, u’red’, u’crescent’, u’monday’] Очевидно, что оба признака связаны с Ираком, но относятся они не только к этой новости, поскольку в ее тексте не встречаются слова oil (нефть) и gates (Гейтс). Поскольку алгоритм выделяет признаки, которые могут сочетаться друг с другом, но необязательно относятся к единственной новости, то общее число признаков оказывается меньше числа новостей.

А вот пример новости с высокорелевантным признаком, который вряд ли ассоциируется еще с чем-нибудь:

Yogi Bear Creator Joe Barbera Dies at 95

11.8474089735 [u’barbera’, u’team’, u’creator’, u’hanna’, u’dies’, u’bear’] 2.21373704749 [u’monday’, u’said’, u’oil’, u’iraq’, u’attacks’, u’two’] 0.421760994361 [u’man’, u’was’, u’year’, u’his’, u’old’, u’kidnapping’]

Так как количество признаков невелико, вероятно появление новостей-сирот, которые больше ни на что не похожи и потому не удостоились собственного признака. Вот пример:

U.S. Files Charges in Fannie Mae Accounting Case

0.856087848533 [u’man’, u’was’, u’year’, u’his’, u’old’, u’kidnapping’] 0.784659717694 [u’climbers’, u’hood’, u’have’, u’their’, u’may’, u’deaths’] 0.562439763693 [u’will’, u’smith’, u’news’, u’office’, u’box’, u’all’]

Как видите, наиболее релевантные этой новости признаки не очень-то связаны с ней и кажутся случайными. Но их веса очень малы, поэтому вы сразу понимаете, что к данной новости они имеют слабое отношение.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100