Иерархическая кластеризация - NiNa.Az

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

• Агломеративные методы (англ. agglomerative): новые кластеры создаются путем объединения более мелких кластеров и, таким образом, дерево создается от листьев к стволу;
• Дивизивные или дивизионные методы (англ. divisive): новые кластеры создаются путем деления более крупных кластеров на более мелкие и, таким образом, дерево создается от ствола к листьям.

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

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

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

Дендрограмма кластеризации ирисов Фишера

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

Для построения матрицы сходства (различия) необходимо задать меру расстояния между двумя кластерами. Наиболее часто используются следующие методы определения расстояния (англ. sorting strategies):

1. Метод одиночной связи (англ. single linkage), также известен, как «метод ближайшего соседа». Расстояние между двумя кластерами полагается равным минимальному расстоянию между двумя элементами из разных кластеров: ${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\}}$, где ${\displaystyle d(a,b)}$— расстояние между элементами ${\displaystyle a}$ и ${\displaystyle b}$, принадлежащими кластерам ${\displaystyle A}$ и ${\displaystyle B}$
2. Метод полной связи (англ. complete linkage), также известен, как «метод дальнего соседа». Расстояние между двумя кластерами полагается равным максимальному расстоянию между двумя элементами из разных кластеров: ${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\}}$;
3. Метод средней связи (англ. pair-group method using arithmetic mean):
   • Невзвешенный (англ. UPGMA). Расстояние между двумя кластерами полагается равным среднему расстоянию между элементами этих кластеров: ${\displaystyle {1 \over {|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)}$ , где ${\displaystyle d(a,b)}$— расстояние между элементами ${\displaystyle a}$ и ${\displaystyle b}$, принадлежащими кластерам ${\displaystyle A}$ и ${\displaystyle B}$, а ${\displaystyle |A|}$ и ${\displaystyle |B|}$— мощности кластеров.
   • Взвешенный (англ. WPGMA).
4. Центроидный метод (англ. pair-group method using the centroid average):
   • Невзвешенный (англ. UPGMC). Расстояние между кластерами полагается равным расстоянию между их центроидами (центрами массы): ${\displaystyle \|c_{A}-c_{B}\|}$, где ${\displaystyle c_{A}}$ и ${\displaystyle c_{B}}$— центройды ${\displaystyle A}$ и ${\displaystyle B}$.
   • Взвешенный (англ. WPGMC).
5. Метод Уорда (англ. Ward’s method). В отличие от других методов кластерного анализа, для оценки расстояний между кластерами здесь используются методы дисперсионного анализа. В качестве расстояния между кластерами берётся прирост суммы квадратов расстояний объектов до центра кластера, получаемого в результате их объединения: ${\displaystyle \Delta =\sum _{i}{(x_{i}-{\bar {x}})^{2}}-\sum _{x_{i}\in A}(x_{i}-{\bar {a}})^{2}-\sum _{x_{i}\in B}(x_{i}-{\bar {b}})^{2}}$. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению дисперсии. Этот метод применяется для задач с близко расположенными кластерами.

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

${\displaystyle K_{\eta }([i,j],k)=\left[{\frac {(n_{i}K(i,k)^{\eta }+(n_{j}K(j,k)^{\eta })}{n_{i}+n_{j}}}\right]^{\frac {1}{\eta }},-{\mathcal {1}}\leqslant \eta \leqslant +{\mathcal {1}}}$

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

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

Дендрит

Широко применяются в геоботанике и флористике. Их часто называют корреляционными плеядами.

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

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

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

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

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

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

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

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

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

См. также

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

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

1. Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
2. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
3. Sneath P.H.A., Sokal R.R. Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
4. Ward J.H. Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
5. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
6. Lance G.N., Willams W.T. A general theory of classification sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373—380.
7. von Terentjev P.V. Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) Архивная копия от 5 марта 2016 на Wayback Machine // 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 Архивная копия от 17 мая 2017 на Wayback Machine // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.