Реферат: Кластерный анализ

В качестве меры расстояния возьмем квадрат евклидовой метрики di j2. и вычислим матрицу D = {di j2}, где di j2 - квадрат расстояния между

Ι i и Ι j:

Ι1	Ι2	Ι3	….	Ιn
Ι1	0	d122	d132	….	d1n2
Ι2	0	d232	….	d2n2
Ι3	0	….	d3n2
….	….	….
Ιn	0

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

di j2 = min {di j2, i ¹ j}. Образуем с помощью Ι i и Ι j новый кластер

{Ι i , Ι j}. Построим новую ((n-1), (n-1)) матрицу расстояния

{Ι i , Ι j}	Ι1	Ι2	Ι3	….	Ιn
{Ι i ; Ι j}	0	di j21	di j22	di j23	….	di j2n
Ι1	0	d122	d13	….	d12n
Ι2	0	di j21	….	d2n
Ι3	0	….	d3n
Ιn	0

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

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

di+j,k = ½ (di k + dj k).

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

di+j,k = min (di k + dj k).

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

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

di+j,k = A(w) min(dik djk) + B(w) max(dik djk), где

A(w) = , если dik £ djk

A(w) = , если dik > djk

B(w) =, если dik £ djk

B(w) = , если dik > djk

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

di+j,k =

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

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

di+j,k = min (di,k djk)

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

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

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

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

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