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

Наглядное введение в агломерационную иерархическую кластеризацию

Здравствуйте и вновь добро пожаловать на занятия по теме «Кластерный анализ и машинное обучение без учителя на языке Python».

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

Итак, рассмотрим алгоритм!

Предположим, у нас ряд точек данных a, b, c, d, e и f. Сгруппируем их согласно «жадной стратегии». Мы видим, что b и c, а также d и e находятся ближе всего друг к другу, а потому объединяем их в первую очередь. Далее мы видим, что f ближе всего к кластеру de, поэтому объединяем их всех в кластер def. Далее, ближайшим к кластеру def является кластер bc, поэтому объединяем их в bcdef. И, наконец, объединяем этот крупный кластер с оставшимся в одиночестве a в один большой кластер abcdef.

Тут вы можете спросить: так какие же из кластеров являются правильными? Которые из них выбирать?

Для ответа на этот вопрос мы должны создать график кластеризации – то, что называется дендрограммой. На рисунке вы можете увидеть пример большой дендрограммы. В действительности настоящие кластеры легко распознать, имея обширную дендрограмму вроде приведённой на рисунке. Но, как правило, высота каждого узла в древе пропорциональна расстоянию между двумя объединяемыми кластерами, то есть высота кластера A/B равно расстоянию между кластером A и кластером B. Таким образом, если вы наткнётесь на большой пропуск в дендрограмме, то будете знать, что два данных кластера находятся далеко друг от друга, а потому можно считать их отдельными. Разумеется, в какой-то момент вам нужно будет сделать оценку кластеризации, основываясь на визуальных данных или с использованием численного критерия, такого как порог.

Варианты агломерационной кластеризации

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

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

Итак, вот некоторые популярные показатели расстояния:

– евклидово расстояние, которое, я уверен, вам всем хорошо знакомо:

||a-b||_2 = \sqrt{\sum_i (a_i-b_i)^2};

– квадрат евклидова расстояния, являющийся всего лишь возведением в квадрат предыдущей формулы:

||a-b||_2^2 = \sum_i (a_i-b_i)^2;

– манхэттенская метрика, известная также как расстояние городских кварталов, в которой расстояние между точками является просто суммой модулей разностей их координат:

||a-b||_1 = \sum_i |a_i-b_i|;

– максимальное расстояние, являющееся просто нахождением максимума модуля между двумя любыми точками:

||a-b||_\infty = max_i |a_i-b_i|;

– и расстояние Махаланобиса – более сложное расстояние, использующее ковариацию S:

\sqrt {(a-b)^T S^{-1} (a-b)}.

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

Первый из них заключается в том, что расстояние всегда должно быть больше или равно нулю:

d(x,y)\geq 0.

На самом деле это требование не так уж и очевидно, но подумайте, что получится, если мы позволим возникать отрицательным расстояниям?

Следующим является требование, чтобы расстояние между x и y было равно нулю тогда и только тогда, когда x = y:

d(x,y) = 0 \Leftrightarrow x=y.

Эти два критерия определяют так называемую положительно определённую функцию.

Третий критерий состоит в том, что расстояние между x и y должно быть равно расстоянию между y и x:

d(x,y) = d(y,x).

И последний критерий – так называемое неравенство треугольника:

d(x,z) \leq d(x,y)+d(y,z).

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

Поговорим теперь о различных способах объединения кластеров.

Поскольку на предыдущей лекции мы не слишком углублялись в эту тему, то на самом деле мы до сих толком не знаем, что брать в качестве расстояния между двумя кластерами. Среднее значение расстояний между точками кластеров? Или медианное? Расстояние между двумя ближайшими точками? Или между двумя наиболее отдалёнными? Между прочим, многие из этих вариантов имеют собственные названия, которые мы сейчас и обсудим.

Первый вариант называется методом одиночной связи (другое название – метод ближайшего соседа). В этом случае мы рассматриваем каждую точку кластера 1 и ищем ближайшую к ней точку из кластера 2. Минимумы всех этих точек и являются расстоянием между кластерами. В виде кода это может выглядеть примерно так:

min_dist = Infinity

for p1 in cluster1:

  for p2 in cluster2:

    min_dist = min( d(p1, p2), min_dist )

Одним из недостатков этого метода является то обстоятельство, что мы можем получить так называемый «цепной эффект», когда мы выбираем следующий объект, находящийся рядом с текущим кластером, а в конечном итоге получаем «цепочки» из больших продолговатых кластеров, когда все точки находятся далеко друг от друга. Вы увидите этот эффект, когда мы начнём рассматривать код.

Противоположностью этого метода является метод полной связи, также известный под названием метода дальнего соседа. В нём мы находим максимальные расстояния между всеми возможными точками в двух кластерах и определяем их как расстояние между кластерами. Код для него может выглядеть так:

max_dist = 0

for p1 in cluster1:

  for p2 in cluster2:

    max_dist = max( d(p1, p2), max_dist )

Третий способ измерения расстояния между кластерами – метод средней связи – является, вероятно, наиболее интуитивно близким и понятным. В нём мы просто берём среднее расстояние. Его часто ещё называют методом UPGMA. В коде он может выглядеть так:

dist = 0

for p1 in cluster1:

  for p2 in cluster2:

    dist+=d(p1, p2)

dist = dist / ( len(cluster1)*len(cluster2) )

И последнее, что мы рассмотрим – метод (или критерий) Уорда. В нём мы берём каждую пару кластеров и смотрим, насколько увеличится дисперсия, если мы их объединим:

SS=\sum_j \sum_{i\in R_j} (x_i-m_j)^2.

Увеличение ошибки тогда составит

\Delta =\sum_i (x_i-\bar{x})^2 - \sum_{i\in A} (x_i-\bar{a})^2 - \sum_{i\in B} (x_i-\bar{b})^2 = \frac{n_a n_b}{n_a+n_b} (\bar{a}-\bar{b})^2.

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

Иерархическая кластеризация на языке Python и интерпретация дендрограмм

Здравствуйте и вновь добро пожаловать на занятия по теме «Кластерный анализ и машинное обучение без учителя на языке Python».

В этой лекции мы рассмотрим иерархическую кластеризацию в коде. Мы не будем самостоятельно писать код, а используем соответствующую библиотеку и посмотрим, что с её помощью можно сделать. Если вам не хочется изучать код, а просто посмотреть уже написанный, вы можете сделать это, открыв файл hcluster.py, который можно найти, перейдя по адресу https://github.com/lazyprogrammer/machine_learning_examples. Нужная папка называется unsupervised_class.

Итак мы начинаем с функции main и импорта пары основных библиотек. Кроме того, для выполнения данного кода нам также понадобится библиотека SciPy с функциями dendrogram и linkage. Чуть позже мы увидим, как их использовать.

import numpy as np

import matplotlib.pyplot as plt

from scipy.cluster.hierarchy import dendrogram, linkage

def main():

if __name__ == ‘__main__’:

main()

Прежде всего установим значения переменных для размерностей. Я выбрал такие же значения, как и в первом примере с методом k-средних, поэтому часть кода просто перенесём оттуда:

def main():

    D = 2

    s = 4

    mu1 = np.array([0, 0])

    mu2 = np.array([s, s])

    mu3 = np.array([0, s])

    N = 900 # number of samples

    X = np.zeros((N, D))

    X[:300, :] = np.random.randn(300, D) + mu1

    X[300:600, :] = np.random.randn(300, D) + mu2

    X[600:, :] = np.random.randn(300, D) + mu3

Далее начинаются отличия. Мы вызовем функцию linkage, использующую в качестве аргументов X и особый параметр, который указывает, какой именно метод определения межкластерного расстояния будет использоваться. В данном случае это будет метод Уорда. Функция возвращает значение переменной Z. Z является матрицей, так что выведем сразу на экран и форму этой матрицы. В общем случае Z имеет формат индекс1, индекс2 (эти два индекса X представляют объединяемые на данный момент точки), третий столбец показывает расстояние – насколько далеко были два кластера до их объединения, а четвёртый столбец представляет счётчик примеров – то есть показывает количество точек в данном кластере. Таким образом, размерность Z будет равна N-1×4. И сразу выведем результат на экран.

Z = linkage(X, ‘ward’)

print “Z.shape:”, Z.shape

plt.title(“Ward”)

dendrogram(Z)

plt.show()

Далее делаем то же самое, но с применением других методов определения расстояния – метода одиночной связи и метода полной связи, чтобы посмотреть, что это нам даст.

Z = linkage(X, ‘single’)

plt.title(“Single”)

dendrogram(Z)

plt.show()

Z = linkage(X, ‘complete’)

plt.title(“Complete”)

dendrogram(Z)

plt.show()

Запустим программу.

Итак, с самого начала мы можем убедиться, что размерность Z равна N-1×4. На первой дендрограмме ясно видно, что в данных присутствуют три истинных кластера. Это метод Уорда.

Следующим мы применили метод одиночной связи, и на графике видно, как проявился «цепной эффект».

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

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Share via
Copy link