Кластеризация методом K-средних

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

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

начинается с выбора k случайно расположенных центроидов (точек, представляющих центр кластера).

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

Рис. 3.5. с двумя кластерами

На первом шаге случайно размещены два центроида (изображены темными кружками). На втором шаге каждый элемент приписан к ближайшему центроиду. В данном случае A и B приписаны к верхнему центроиду, а C, D и E – к нижнему. На третьем шаге каждый центроид перемещен в точку, рассчитанную как среднее по всем приписанным к нему элементам. После пересчета назначений оказалось, что C теперь ближе к верхнему центроиду, а D и E – по-прежнему ближе к нижнему. Окончательный результат достигается, когда A, B и C помещены в один кластер, а D и E – в другой.

Функция для выполнения кластеризации методом K-средних принимает на входе те же строки данных, что и алгоритм иерархической кластеризации, а кроме того, количество кластеров (k), которое хотела бы получить вызывающая программа. Добавьте в файл clusters.py такой код:

import random

def kcluster(rows,distance=pearson,k=4): # Определить минимальное и максимальное значения для каждой точки

ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) for i in range(len(rows[0]))]

# Создать k случайно расположенных центроидов

clusters=[[random.random( )*(ranges[i][1]-ranges[i][0])+ranges[i][0] for i in range(len(rows[0]))] for j in range(k)]

lastmatches=None for t in range(100): print ‘Итерация %d’ % t bestmatches=[[] for i in range(k)]

#       Найти для каждой строки ближайший центроид for j in range(len(rows)):

row=rows[j] bestmatch=0 for i in range(k): d=distance(clusters[i],row)

if d<distance(clusters[bestmatch],row): bestmatch=i bestmatches[bestmatch].append(j)

#       Если получился такой же результат, как в прошлый раз, заканчиваем if bestmatches==lastmatches: break lastmatches=bestmatches

#       Перемещаем каждый центроид в центр приписанных к нему элементов for i in range(k):

avgs=[0.0]*len(rows[0]) if len(bestmatches[i])>0: for rowid in bestmatches[i]: for m in range(len(rows[rowid])): avgs[m]+=rows[rowid][m] for j in range(len(avgs)):

avgs[j]/=len(bestmatches[i]) clusters[i]=avgs

return bestmatches

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

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

Можете протестировать эту функцию на наборе данных о блогах. Она должна работать заметно быстрее, чем в случае иерархической кластеризации:

>> reload(clusters)

>> kclust=clusters.kcluster(data,k=10)

Итерация 0

>> [rownames[r] for r in k[0]]

[‘The Viral Garden’, ‘Copyblogger’, ‘Creating Passionate Users’, ‘Oilman’,

‘ProBlogger Blog Tips’, "Seth’s Blog"] >> [rownames[r] for r in k[1]] и т. д…

Теперь kclust содержит список идентификаторов, вошедших в каждый кластер. Попробуйте выполнить кластеризацию с другим значением k и посмотрите, как это отразится на результатах.

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