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

Еще один метод кластеризации – это метод ^-средних. Если при иерархической кластеризации создается дерево образцов, то метод .^-средних разбивает данные на отдельные группы. Но перед началом работы алгоритма вы должны задать количество желаемых групп. На рис. 12.14 иллюстрируется кластеризация методом . -средних в действии. Здесь мы пытаемся найти два кластера в несколько ином наборе данных.

Рис. 12.14. Процесс кластеризации методом K-средних

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

Использование ранее написанного кода

Для выполнения кластеризации необходим набор данных и метрика. Набор данных представляет собой список чисел, в котором каждое число соответствует некоторой переменной. Ранее в качестве метрики мы применяли коэффициент корреляции Пирсона и коэффициент Та- нимото, но годятся и другие метрики, например евклидово расстояние: >>> data=[[1.0,8.0],[3.0,8.0],[2.0,7.0],[1.5,1.0],[4.0,2.0]] >>> labels=[‘A’,’B’,’C’,’D’,’E’]

>>> def euclidean(v1,v2): return sum([(v1[i]-v2[i])**2 for i in range(len(v1))]) >>> import clusters

>>> hcl=clusters.hcluster(data,distance=euclidean) >>> kcl=clusters.kcluster(data,distance=euclidean,k=2)

Итерация 0 Итерация 1

В случае кластеризации методом ^-средних можно напечатать, какие образцы в какой кластер попали: >>> kcl

[[0, 1, 2], [3, 4]]

>>> for c in kcl: print [labels[l] for l in c]

[‘A’, ‘B’, ‘C’] [‘D’, ‘E’]

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

>>> clusters.drawdendrogram(hcl,labels,jpeg=’hcl.jpg’) Выбор алгоритма зависит от того, что вы хотите сделать. Часто бывает полезно разбить данные на отдельные группы, поскольку так их проще увидеть и охарактеризовать. В этом случае подойдет кластеризация методом ^-средних. С другой стороны, имея совершенно новый набор данных, вы зачастую не знаете, сколько в нем групп, и хотите посмотреть, какие получаются группы похожих образцов. В таком случае лучше остановиться на алгоритме иерархической кластеризации. Можно взять и лучшее из обоих методов: сначала методом ^-средних создать набор групп, а затем выполнить для них иерархическую кластеризацию, взяв в качестве метрики расстояние между центроидами. Тогда вы получите на одном уровне отдельные группы, которые организованы в дерево, чтобы было видно, как группы связаны между собой.

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