Алгоритмы кластеризации

Рассмотрим Ι = (Ι₁, Ι₂, … Ι_n) как множество кластеров {Ι₁}, {Ι₂},…{Ι_n}. Выберем два из них, например, Ι _i и Ι _j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

{Ι₁}, {Ι₂}…, {Ι _i , Ι _j}, …, {Ι_n}.

Повторяя процесс, получим последовательные множества кластеров, состоящие из (n-2), (n-3), (n–4) и т.д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством Ι = (Ι₁, Ι₂, … Ι_n).

В качестве меры расстояния возьмем квадрат евклидовой метрикиd_{i j}². и вычислим матрицу D = {d_{i j}²}, где d_{i j}² - квадрат расстояния между Ι _i и Ι _j:

Пусть расстояние между Ι _i и Ι _j будет минимальным:

d_{i j}² = min {d_{i j}², i ¹ j}.

Образуем с помощью Ι _i и Ι _j новый кластер {Ι _i , Ι _j}. Построим новую ((n-1), (n-1)) матрицу расстояния:

В ней (n-2) строки для последней матрицы взяты из предыдущей, а первая строка вычислена заново. Вычисления могут быть сведены к минимуму, если удастся выразить d_{i j}²_k,k = 1, 2,…, n; (k ¹ i ¹ j) через элементы первоначальной матрицы.

Исходно определено расстояние лишь между одноэлементными кластерами, но надо определять расстояния и между кластерами, содержащими более чем один элемент. Это можно сделать различными способами, и в зависимости от выбранного способа мы получают алгоритмы кластер анализа с различными свойствами. Можно, например, положить расстояние между кластером i + j и некоторым другим кластером k, равным среднему арифметическому из расстояний между кластерами i и k и кластерами j и k:

d_i+j,k = ½ (d_{i k} + d_{j k}).

Но можно также определить d_i+j,k как минимальное из этих двух расстояний:

d_i+j,k = min (d_{i k} + d_{j k}).

Таким образом, описан первый шаг работы агломеративного иерархического алгоритма. Последующие шаги аналогичны.

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

d_i+j,k = A(w) min(d_ik d_jk) + B(w) max(d_ik d_jk), где

A(w) = , если d_ik £ d_jk

A(w) = , если d_ik > d_jk

B(w) = , если d_ik £ d_jk

B(w) = , если d_ik > d_jk

где n_i и n_j - число элементов в кластерах i и j, а w – свободный параметр, выбор которого определяет конкретный алгоритм. Например, при w = 1 мы получаем, так называемый, алгоритм «средней связи», для которого формула перерасчета расстояний принимает вид:

d_i+j,k =

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

Наглядный смысл параметра w становится понятным, если положить w ® ¥. Формула пересчета расстояний принимает вид:

d_i+j,k = min (d_i,k d_jk)

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

Довольно часто предполагают, что первоначальные расстояния (различия) между группируемыми элементами заданы. В некоторых задачах это действительно так. Однако, задаются только объекты и их характеристики и матрицу расстояний строят исходя из этих данных. В зависимости от того, вычисляются ли расстояния между объектами или между характеристиками объектов, используются разные способы.

В случае кластер анализа объектов наиболее часто мерой различия служит либо квадрат евклидова расстояния

(где x_ih, x_jh - значения h-го признака для i-го и j-го объектов, а m - число характеристик), либо само евклидово расстояние. Если признакам приписывается разный вес, то эти веса можно учесть при вычислении расстояния

Иногда в качестве меры различия используется расстояние, вычисляемое по формуле:

которые называют: "хэмминговым", "манхэттенским" или "сити-блок" расстоянием.

Естественной мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними

где m_i ,m_j ,d_i ,d_j - соответственно средние и среднеквадратичные отклонения для характеристик i и j. Мерой различия между характеристиками может служить величина 1 - r. В некоторых задачах знак коэффициента корреляции несуществен и зависит лишь от выбора единицы измерения. В этом случае в качестве меры различия между характеристиками используется ô1 - r_{i j} ô