Иерархическая кластеризация

Алгоритм иерархической кластеризации строит иерархию групп, объединяя на каждом шаге две самые похожие группы. В начале каждая группа состоит из одного элемента, в данном случае – одного блога. На каждой итерации вычисляются попарные расстояния между группами, и группы, оказавшиеся самыми близкими, объединяются в новую группу. Так повторяется до тех пор, пока не останется всего одна группа. Эта процедура изображена на рис. 3.1.

Здесь схожесть элементов представлена их относительным расположением – чем элементы ближе друг к другу, тем более они схожи. В начале каждый элемент – это отдельная группа. На втором шаге два самых

Рис. 3.1. в действии

близких элемента A и B объединены в новую группу, расположенную посередине между исходными. На третьем шаге эта новая группа объединяется с элементом C. Поскольку теперь два ближайших элемента – это D и E, то из них образуется новая группа. И на последнем шаге две оставшиеся группы объединяются в одну.

Результаты иерархической кластеризации обычно представляются в виде графа, который называется дендрограммой. На нем изображено, как из узлов формировалась иерархия. Дендрограмма для рассмотренного выше примера показана на рис. 3.2.

Рис. 3.2. Дендрограмма как способ визуализации иерархической кластеризации

На дендрограмме представлены не только ребра графа, показывающие, из каких элементов составлен каждый кластер, но и расстояния, говорящие о том, как далеко эти элементы отстояли друг от друга. Кластер AB гораздо ближе к составляющим его элементам A и B, чем кластер DE к элементам D и E. Изображение графа таким образом помогает понять, насколько схожи элементы, вошедшие в кластер. Эта характеристика называется теснотой (tightness) кластера.

В этом разделе мы покажем, как с помощью кластеризации построить иерархию блогов, которая в случае успеха сгруппирует их по тематике. Прежде всего нам понадобится метод для загрузки файла данных. Создайте файл clusters.py и включите в него такую функцию:

def readfile(filename):

lines=[line for line in file(filename)]

#       Первая строка содержит названия столбцов colnames=lines[0].strip( ).split(‘\t’)[1:] rownames=[]

data=[]

for line in lines[1:]:

p=line.strip( ).split(‘\t’)

#       Первый столбец в каждой строке содержит название строки rownames.append(p[0])

#       Остальные ячейки содержат данные этой строки data.append([float(x) for x in p[1:]])

return rownames,colnames,data

Эта функция считывает первую строку и формирует из нее список названий столбцов, затем считывает самый левый столбец, формируя названия строк, а после этого помещает данные из остальных ячеек в один большой список, где каждый элемент соответствует одной ячейке текущей строки. Счетчик, находившийся в ячейке, можно найти по индексу строки и столбца в массиве data, а индексы получить по именам из списков rownames и colnames.

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

from math import sqrt def pearson(v1,v2):

#       Простые суммы

sum1=sum(v1) sum2=sum(v2)

#       Суммы квадратов

sum1Sq=sum([pow(v,2) for v in v1]) sum2Sq=sum([pow(v,2) for v in v2])

#       Суммы произведений

pSum=sum([v1[i]*v2[i] for i in range(len(v1))])

#       Вычисляем r (коэффициент Пирсона) num=pSum-(sum1*sum2/len(v1))

den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1))) if den==0: return 0

return 1.0-num/den

Напомним, что коэффициент Пирсона равен 1,0, если два набора данных в точности совпадают, и близок к 0,0, если никакой связи между ними не наблюдается. В последней строке мы возвращаем 1,0 минус коэффициент корреляции, чтобы расстояние между наборами было тем меньше, чем они более схожи.

Каждый кластер в алгоритме иерархической кластеризации – это либо узел в дереве с двумя ветвями, либо конечный (листовый) узел, ассоциированный с конкретной строкой из набора данных (в данном случае с блогом). Каждый кластер содержит также данные о своем положении; это либо строка данных для листовых узлов, либо объединенные данные двух ветвей для остальных узлов. Можно создать класс bicluster для представления иерархического дерева, наделив его всеми этими свойствами. Включите класс, описывающий тип кластера, в файл clusters.py:

class bicluster:

def ___ init    (self,vec,left=None,right=None,distance=0.0,id=None):

self.left=left self.right=right self.vec=vec self.id=id

self.distance=distance Алгоритм иерархической кластеризации начинает работу с создания группы кластеров, каждый из которых содержит ровно один исходный элемент. В главном цикле функция ищет два самых похожих элемента, вычисляя коэффициент корреляции между каждой парой кластеров. Наилучшая пара объединяется в новый кластер. Данными для нового кластера служит среднее арифметическое данных двух старых кластеров. Этот процесс повторяется, пока не останется только один кластер. На выполнение всех вычислений может уйти очень много времени, поэтому было бы разумно сохранять коэффициенты корреляции для каждой пары, поскольку они вычисляются снова и снова, пока один из элементов пары не попадет в новый кластер.

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

def hcluster(rows,distance=pearson): distances={} currentclustid=-1

# В начале кластеры совпадают со строками clust=[bicluster(rows[i],id=i) for i in range(len(rows))]

while len(clust)>1: lowestpair=(0,1)

closest=distance(clust[0].vec,clust[1].vec)

#       в цикле рассматриваются все пары и ищется пара с минимальным

#       расстоянием

for i in range(len(clust)): for j in range(i+1,len(clust)):

# вычисленные расстояния запоминаются в кэше if (clust[i].id,clust[]].id) not in distances: distances[(clust[i].id,clust[]].id)]= distance(clust[i].vec,clust[]].vec)

d=distances[(clust[i].id,clust[]].id)]

if d<closest: closest=d lowestpair=(i,j)

#       вычислить среднее для двух кластеров mergevec=[

(clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0 for i in range(len(clust[0].vec))]

#       создать новый кластер

newcluster=bicluster(mergevec,left=clust[lowestpair[0]], right=clust[lowestpair[1]], distance=closest,id=currentclustid)

#       идентификаторы кластеров, которых не было в исходном наборе,

#       отрицательны currentclustid-=1

del clust[lowestpair[1]] del clust[lowestpair[0]] clust.append(newcluster)

return clust[0]

Поскольку в каждом кластере хранятся ссылки на оба кластера, объединением которых он получился, то финальный кластер, возвращенный этой функцией, можно рекурсивно обойти, показав все промежуточные кластеры и листовые узлы.

Чтобы выполнить иерархическую кластеризацию, запустите Python в интерактивном режиме, загрузите файл и вызовите функцию hcluster: $ python

>> import clusters

>> blognames,words,data=clusters.readfile(‘blogdata.txt’) >> clust=clusters.hcluster(data)

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

def printclust(clust,labels=None,n=0): # отступ для визуализации иерархии for i in range(n): print ‘ ‘, if clust.id<0:

# отрицательный id означает, что это внутренний узел print ‘-‘

else:

# положительный id означает, что это листовый узел if labels==None: print clust.id

else: print labels[clust.id]

# теперь печатаем правую и левую ветви

if clust.left!=None: printclust(clust.left,labels=labels,n=n+1) if clust.right!=None: printclust(clust.right,labels=labels,n=n+1)

Получившийся результат выглядит не слишком красиво, и при таком большом наборе данных, как список блогов, неудобен для восприятия. Тем не менее общее представление о том, как работает алгоритм кластеризации, он дает. В следующем разделе мы поговорим о создании графической версии, которая воспринимается гораздо легче и рисуется так, чтобы была видна протяженность каждого кластера. В сеансе работы с интерпретатором вызовите эту функцию для только что построенных кластеров: >> reload(clusters)

>> clusters.printclust(clust,labels=blognames) Распечатка содержит все 100 блогов и потому довольно длинная. Вот пример кластера, обнаруженного при обработке этого набора данных:

John Battelle’s Searchblog

Search Engine Watch Blog Read/WriteWeb

Official Google Blog

Search Engine Roundtable

Google Operating System Google Blogoscoped

Показаны элементы исходного набора. Знак минус обозначает кластер, получившийся объединением двух или более элементов. Здесь вы видите прекрасный пример обнаружения группы; интересно также, что в самых популярных каналах так много блогов, имеющих отношение к поиску. Изучая распечатку, вы найдете также кластеры блогов о политике, о технологии и о самих блогах.

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

Вы можете следить за любыми ответами на эту запись через 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