Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Пусть расстояние между ? i и ? j будет минимальным: d( j2 = min {di j2, i ( j}. Образуем с помощью ? i и ? j новый кластер

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

| | | | | | | |
| | | | | | | |
|?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) = [pic], если dik ( djk

A(w) = [pic], если dik ( djk

B(w) =[pic], если d(k ( djk

B(w) = [pic], если dik ( djk где ni и nj - число элементов в кластерах i и j, а w – свободный параметр, выбор которого определяет конкретный алгоритм. Например, при w =
1 мы получаем, так называемый, алгоритм «средней связи», для которого формула перерасчета расстояний принимает вид: di+j,k = [pic]

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

Наглядный смысл параметра w становится понятным, если положить w ( (.
Формула пересчета расстояний принимает вид: di+j,k = min (d(,k djk)

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

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

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

Естественной мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними
[pic] где mi ,mj ,(i ,(j - соответственно средние и среднеквадратичные отклонения для характеристик i и j. Мерой различия между характеристиками может служить величина 1 - r. В некоторых задачах знак коэффициента корреляции несуществен и зависит лишь от выбора единицы измерения. В этом случае в качестве меры различия между характеристиками используется (1 - ri j (

1.5 Число кластеров.

Очень важным вопросом является проблема выбора необходимого числа кластеров. Иногда можно m число кластеров выбирать априорно. Однако в общем случае это число определяется в процессе разбиения множества на кластеры.

Проводились исследования Фортьером и Соломоном, и было установлено, что число кластеров должно быть принято для достижения вероятности ( того, что найдено наилучшее разбиение. Таким образом, оптимальное число разбиений является функцией заданной доли ( наилучших или в некотором смысле допустимых разбиений во множестве всех возможных. Общее рассеяние будет тем больше, чем выше доля ( допустимых разбиений. Фортьер и Соломон разработали таблицу, по которой можно найти число необходимых разбиений.
S(((((( в зависимости от ( и ( (где ( - вероятность того, что найдено наилучшее разбиение, (( - доля наилучших разбиений в общем числе разбиений)
Причем в качестве меры разнородности используется не мера рассеяния, а мера принадлежности, введенная Хользенгером и Харманом. Таблица значений S((( () приводится ниже.

Таблица значений S((( ()

|( ( |0.20 |0.10 |0.05 |0.01 |0.001 |0.0001 |
|0.20 |8 |11 |14 |21 |31 |42 |
|0.10 |16 |22 |29 |44 |66 |88 |
|0.05 |32 |45 |59 |90 |135 |180 |
|0.01 |161 |230 |299 |459 |689 |918 |
|0.001 |1626 |2326 |3026 |4652 |6977 |9303 |
|0.0001 |17475 |25000 |32526 |55000 |75000 |100000 |

Довольно часто критерием объединения (числа кластеров) становится изменение соответствующей функции. Например, суммы квадратов отклонений:
[pic]

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

Рекомендуем скачать другие рефераты по теме: определение реферат, красные дипломы.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата