Русская Википедия:Иерархическая кластеризация

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Hierarchical clustering simple diagram.svg
Дендрограмма

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

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

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

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

Файл:Iris dendrogram.png
Дендрограмма кластеризации ирисов Фишера

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

Для построения матрицы сходства (различия) необходимо задать меру расстояния между двумя кластерами. Наиболее часто используются следующие методы определения расстояния (Шаблон:Lang-en)[2]:

  1. Метод одиночной связи (Шаблон:Lang-en), также известен, как «метод ближайшего соседа». Расстояние между двумя кластерами полагается равным минимальному расстоянию между двумя элементами из разных кластеров: <math>\min \, \{\, d(a,b) : a \in A,\, b \in B \,\}</math>, где <math>d(a,b)</math>— расстояние между элементами <math>a</math> и <math>b</math>, принадлежащими кластерам <math>A</math> и <math>B</math>
  2. Метод полной связи (Шаблон:Lang-en), также известен, как «метод дальнего соседа». Расстояние между двумя кластерами полагается равным максимальному расстоянию между двумя элементами из разных кластеров: <math>\max \, \{\, d(a,b) : a \in A,\, b \in B \,\}</math>;
  3. Метод средней связи (Шаблон:Lang-en):
    • Невзвешенный (Шаблон:Lang-en). Расстояние между двумя кластерами полагается равным среднему расстоянию между элементами этих кластеров: <math>{1 \over {|A|\cdot|B|}}\sum_{a \in A}\sum_{b \in B} d(a,b)</math> , где <math>d(a,b)</math>— расстояние между элементами <math>a</math> и <math>b</math>, принадлежащими кластерам <math>A</math> и <math>B</math>, а <math>|A|</math> и <math>|B|</math>— мощности кластеров.
    • Взвешенный (Шаблон:Lang-en).
  4. Центроидный метод (Шаблон:Lang-en):
    • Невзвешенный (Шаблон:Lang-en). Расстояние между кластерами полагается равным расстоянию между их центроидами (центрами массы)[3]: <math>\|c_A - c_B \|</math>, где <math>c_A</math> и <math>c_B</math>— центройды <math>A</math> и <math>B</math>.
    • Взвешенный (Шаблон:Lang-en).
  5. Метод Уорда (Шаблон:Lang-en). В отличие от других методов кластерного анализа, для оценки расстояний между кластерами здесь используются методы дисперсионного анализа. В качестве расстояния между кластерами берётся прирост суммы квадратов расстояний объектов до центра кластера, получаемого в результате их объединения[4]: <math>\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</math>. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению дисперсии. Этот метод применяется для задач с близко расположенными кластерами.

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

<math> 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} </math>

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

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

Файл:Дендрит.png
Дендрит

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

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

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

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

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

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

Файл:Diagrcz.png
Пример расчёта диаграммы Чекановского

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

<math> K^{(2)}(i,j) = max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q,j)))</math>,

где <math>K(i, j)</math> — элемент, стоящий на пересечении <math>i</math>-ой строки и <math>j</math>-го столбца в новой (второй) матрице, полученной после первой итерации; <math>q</math> — общее количество строк (столбцов) матрицы сходства. Данную процедуру необходимо продолжать, пока матрица не станет идемпотентной (то есть самоподобной): <math> K^{(n)}(i,j) = K^{(n-1)}(i,j) </math>, где 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) Шаблон:Wayback // 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 Шаблон:Wayback // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Иерархическая_кластеризация&oldid=9977034