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

Иерархическая кластеризация (также графовые алгоритмы кластеризации) — совокупность алгоритмов упорядочивания данных, визуализация которых обеспечивается с помощью графов.

Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов характеризуется определённой степенью связности. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации. Как и большинство визуальных способов представления зависимостей графы быстро теряют наглядность при увеличении числа объектов. Существует ряд специализированных программ для построения графов.

Дендрограмма

Дендрограмма

Под дендрограмой обычно понимается дерево, то есть граф без циклов построенный по матрице мер близости. Дендрограмма позволяет изобразить взаимные связи между объектами из заданного множества^[1]. Для создания дендрограммы требуется матрица сходства (или различия), которая определяет уровень сходства между парами объектов. Чаще используются агломеративные методы.

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

В работах по кластерному анализу описан довольно внушительный ряд способов построения (англ. sorting strategies) дендрограмм^[2]:

1. Метод одиночной связи (англ. single linkage). Также известен, как «метод ближайшего соседа».
2. Метод полной связи (англ. complete linkage). Также известен, как «метод дальнего соседа».
3. Метод средней связи (англ. pair-group method using arithmetic averages).

• Невзвешенный (англ. unweighted).
• Взвешенный (англ. weighted).

1. Центроидный метод (англ. pair-group method using the centroid average).

• Невзвешенный.
• Взвешенный (медианый).

1. Метод Уорда (англ. Ward’s method).

Для первых трёх методов существует общая формула, предложенная А. Н. Колмогоровым для мер сходства^[3]:

$K_\eta([i,j],k) = \left [ \frac{(n_iK(i,k)^\eta + (n_jK(j,k)^\eta)}{n_i + n_j} \right ]^\frac{1}{\eta}, - \mathcal {1} \leqslant \eta \leqslant + \mathcal {1}$

где $[i, j]$ — группа из двух объектов (кластеров) $i$ и $j$; $k$ — объект (кластер), с которым ищется сходство указанной группы; $n_i$ — число элементов в кластере $i$; $n_j$ — число элементов в кластере $j$. Для расстояний имеется аналогичная формула Ланса — Вильямса^[4].

Центроидный метод использует для пересчёта матрицы расстояний^[5]. В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.

В методе Уорда в качестве расстояния между кластерами берётся прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения^[6]. В отличие от других методов кластерного анализа для оценки расстояний между кластерами, здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, то есть внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров.

Корреляционные плеяды

Дендрит

Широко применяются в геоботанике и флористике. Их часто называют корреляционными плеядами^{[7][8][9][10]}.

Частным случаем является метод, известный как метод построения оптимальных деревьев (дендритов), который был предложен математиком львовской школы Гуго Штейнгаузом^[11], впоследствии метод был развит математиками вроцлавской таксономической школы^[12]. Дендриты также не должны образовывать циклов. Можно частично использовать направленные дуги графов при использовании дополнительно мер включения (несимметричных мер сходства).

Диаграмма Чекановского

Метод «диагонализации» матрицы различия и графическое изображение кластеров вдоль главной диагонали матрицы различия (диаграмма Чекановского) впервые предложен Яном Чекановским в 1909 году^[13]. Приведём описание методики:

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

Приведём гипотетический пример получения вышеуказанной диаграммы. Основой метода является построение матрицы транзитивного замыкания^[15].

Пример расчёта диаграммы Чекановского

Для построения матрицы транзитивного замыкания возьмём простую матрицу сходства и умножим её саму на себя:

$K^{(2)}(i,j) = max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q,j)))$,

где $K(i, j)$ — элемент, стоящий на пересечении $i$-ой строки и $j$-го столбца в новой (второй) матрице, полученной после первой итерации; $q$ — общее количество строк (столбцов) матрицы сходства. Данную процедуру необходимо продолжать пока матрица не станет идемпотентной (то есть самоподобной): $K^{(n)}(i,j) = K^{(n-1)}(i,j)$, где n — число итераций.

Далее преобразовываем матрицу таким образом, чтобы близкие числовые значения находились рядом. Если каждому числовому значению присвоить какой-либо цвет или оттенок цвета (как в нашем случае), то получим классическую диаграмму Чекановского. Традиционно более тёмный цвет соответствует большему сходству, а более светлый — меньшему. В этом она схожа с теплокартой для матрицы расстояний.

См. также

• Граф (математика)
• Кластерный анализ
• Метрическое пространство
• Задача классификации
• Метод Чекановского (польск.)

Источники и примечания

1. ↑ Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
2. ↑ Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
3. ↑ Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
4. ↑ Lance G.N., Willams W.T. A general theory of classification sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373—380.
5. ↑ Sneath P.H.A., Sokal R.R. Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
6. ↑ Ward J.H. Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
7. ↑ von Terentjev P.V. Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. № 23(1-2). P. 23-51.
8. ↑ Терентьев П. В. Метод корреляционных плеяд // Вестн. ЛГУ. № 9. 1959. С. 35-43.
9. ↑ Терентьев П. В. Дальнейшее развитие метода корреляционных плеяд // Применение математических методов в биологии. Т. 1. Л.: 1960. С. 42-58.
10. ↑ Выханду Л. К. Об исследовании многопризнаковых биологических систем // Применение математических методов в биологии. Л.: вып. 3. 1964. С. 19-22.
11. ↑ Штейнгауз Г. Математический калейдоскоп. — М.: Наука, 1981. — 160 с.
12. ↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropol. 1951. T. 17. S. 193—211.
13. ↑ Czekanowski J. Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
14. ↑ Василевич В. И. Статистические методы в геоботанике. — Л.: Наука, 1969. — 232 с.
15. ↑ Tamura S., Hiquchi S., Tanaka K. Pattern classification based on fuzzy relation // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.