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

Статистический метод анализа, направленный на построение иерархии кластеров.

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

• Агломеративный : это подход « снизу вверх »: каждое наблюдение начинается в своем собственном кластере, а пары кластеров объединяются по мере продвижения вверх по иерархии.
• Разделительный : это подход « сверху вниз »: все наблюдения начинаются в одном кластере, а разделения выполняются рекурсивно по мере продвижения вниз по иерархии.

В общем случае слияния и разделения определяются жадным образом. Результаты иерархической кластеризации ^[1] обычно представляются в виде дендрограммы .

Иерархическая кластеризация имеет явное преимущество в том, что можно использовать любую допустимую меру расстояния. Фактически, сами наблюдения не требуются: используется только матрица расстояний . С другой стороны, за исключением особого случая расстояния с одной связью, ни один из алгоритмов (кроме исчерпывающего поиска в ) не может гарантировать нахождение оптимального решения. ^{[ необходима цитата ]} ${\displaystyle {\mathcal {O}}(2^{n})}$

Сложность

Стандартный алгоритм иерархической агломеративной кластеризации (HAC) имеет временную сложность и требует памяти, что делает его слишком медленным даже для средних наборов данных. Однако для некоторых особых случаев известны оптимальные эффективные агломеративные методы (сложности ): SLINK ^[2] для одиночной связи и CLINK ^[3] для полной связи кластеризации . С кучей время выполнения общего случая может быть сокращено до , улучшение вышеупомянутой границы , за счет дальнейшего увеличения требований к памяти. Во многих случаях накладные расходы памяти этого подхода слишком велики, чтобы сделать его практически применимым. Существуют методы, которые используют квадродеревья , которые демонстрируют общее время выполнения с пространством. ^[4] ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle \Omega (n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{2}\log n)}$ ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n)}$

Разделительная кластеризация с исчерпывающим поиском — это , но для выбора разделений обычно используют более быстрые эвристики, такие как k -средние . ${\displaystyle {\mathcal {O}}(2^{n})}$

Кластерная связь

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

Критерий связи определяет расстояние между наборами наблюдений как функцию попарных расстояний между наблюдениями.

Некоторые часто используемые критерии связи между двумя наборами наблюдений A и B и расстоянием d : ^{[5] [6]}

Некоторые из них можно пересчитать только рекурсивно (WPGMA, WPGMC), для многих рекурсивное вычисление с уравнениями Лэнса-Вильямса более эффективно, в то время как для других (Хаусдорф, Медоид) расстояния должны вычисляться с помощью более медленной полной формулы. Другие критерии связи включают:

• Вероятность того, что кластеры-кандидаты возникают из одной и той же функции распределения (V-связь).
• Произведение степени захода и степени исхода на графе k-ближайших соседей (сцепление степеней графа). ^[14]
• Приращение некоторого дескриптора кластера (т. е. величины, определенной для измерения качества кластера) после слияния двух кластеров. ^{[15] [16] [17]}

Пример агломеративной кластеризации

Исходные данные

Например, предположим, что эти данные необходимо кластеризовать, а евклидово расстояние является метрикой расстояния .

Иерархическая кластерная дендрограмма будет выглядеть следующим образом:

Традиционное представление

Обрезка дерева на заданной высоте даст кластеризацию разбиения с выбранной точностью. В этом примере обрезка после второй строки (сверху) дендрограммы даст кластеры {a} {bc} {de} {f}. Обрезка после третьей строки даст кластеры {a} {bc} {def}, что является более грубой кластеризацией с меньшим числом, но большими кластерами.

Этот метод строит иерархию из отдельных элементов путем постепенного слияния кластеров. В нашем примере у нас есть шесть элементов {a} {b} {c} {d} {e} и {f}. Первый шаг — определить, какие элементы объединить в кластер. Обычно мы хотим взять два ближайших элемента в соответствии с выбранным расстоянием.

При желании на этом этапе можно также построить матрицу расстояний , где число в i -й строке j -го столбца является расстоянием между i -м и j -м элементами. Затем, по мере кластеризации, строки и столбцы объединяются по мере объединения кластеров и обновления расстояний. Это распространенный способ реализации этого типа кластеризации, и он имеет преимущество кэширования расстояний между кластерами. Простой алгоритм агломеративной кластеризации описан на странице кластеризации с одной связью ; его можно легко адаптировать к различным типам связей (см. ниже).

Предположим, что мы объединили два ближайших элемента b и c , теперь у нас есть следующие кластеры { a }, { b , c }, { d }, { e } и { f }, и мы хотим объединить их дальше. Чтобы сделать это, нам нужно взять расстояние между {a} и {bc}, и, следовательно, определить расстояние между двумя кластерами. Обычно расстояние между двумя кластерами и является одним из следующих: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

• Максимальное расстояние между элементами каждого кластера (также называемое кластеризацией с полной связью ):

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Минимальное расстояние между элементами каждого кластера (также называемое односвязной кластеризацией ):

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Среднее расстояние между элементами каждого кластера (также называемое средним значением кластеризации связей, используется, например, в UPGMA ):

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$

• Сумма всех внутрикластерных дисперсий.
• Увеличение дисперсии для объединяемого кластера ( метод Уорда ^[8] )
• Вероятность того, что кластеры-кандидаты возникают из одной и той же функции распределения (V-связь).

В случае связанных минимальных расстояний пара выбирается случайным образом, что позволяет генерировать несколько структурно различных дендрограмм. В качестве альтернативы все связанные пары могут быть объединены одновременно, генерируя уникальную дендрограмму. ^[18]

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

Разделительная кластеризация

Основной принцип разделительной кластеризации был опубликован как алгоритм DIANA (DIvisive ANAlysis clustering). ^[20] Изначально все данные находятся в одном кластере, и самый большой кластер разделяется до тех пор, пока каждый объект не будет отделен. Поскольку существуют способы разделения каждого кластера, необходимы эвристики. DIANA выбирает объект с максимальным средним различием, а затем перемещает в этот кластер все объекты, которые больше похожи на новый кластер, чем на оставшийся. ${\displaystyle O(2^{n})}$

Неформально, DIANA — это не столько процесс «разделения», сколько «выемки»: на каждой итерации существующий кластер (например, начальный кластер всего набора данных) выбирается для формирования нового кластера внутри него. Объекты постепенно перемещаются в этот вложенный кластер и выемляют существующий кластер. В конце концов, все, что остается внутри кластера, — это вложенные кластеры, которые там выросли, без того, чтобы он сам владел какими-либо свободными объектами.

Формально DIANA работает по следующим этапам:

1. Пусть — множество всех индексов объектов и множество всех сформированных на данный момент кластеров. ${\displaystyle C_{0}=\{1\dots n\}}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {C}}=\{C_{0}\}}$
2. Повторяйте следующее до тех пор, пока : ${\displaystyle |{\mathcal {C}}|=n}$
   1. Найдите текущий кластер с 2 или более объектами, имеющими наибольший диаметр: ${\displaystyle C_{*}=\arg \max _{C\in {\mathcal {C}}}\max _{i_{1},i_{2}\in C}\delta (i_{1},i_{2})}$
   2. Найдите в этом кластере объект, который больше всего отличается от остальной части кластера: ${\displaystyle i^{*}=\arg \max _{i\in C_{*}}{\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)}$
   3. Выделите его из старого кластера и поместите в новую отколовшуюся группу . ${\displaystyle i^{*}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{\textrm {new}}=\{i^{*}\}}$
   4. Пока не пусто, продолжайте переносить объекты из , чтобы добавить их в . Чтобы выбрать, какие объекты переносить, не просто учитывайте несходство с , но и делайте поправку на несходство с отколовшейся группой: пусть , где мы определяем , затем либо прекратите итерацию, когда , либо выполните перенос . ${\displaystyle C_{*}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle C_{*}}$ ${\displaystyle i^{*}=\arg \max _{i\in C}D(i)}$ ${\displaystyle D(i)={\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)-{\frac {1}{|C_{\textrm {new}}|}}\sum _{j\in C_{\textrm {new}}}\delta (i,j)}$ ${\displaystyle D(i^{*})<0}$ ${\displaystyle i^{*}}$
   5. Добавить в . ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle {\mathcal {C}}}$

Интуитивно, выше измеряет, насколько сильно объект хочет покинуть свой текущий кластер, но это ослабляется, когда объект также не вписывается в отколовшуюся группу. Такие объекты, вероятно, в конечном итоге начнут свою собственную отколовшуюся группу. ${\displaystyle D(i)}$

Дендрограмма DIANA может быть построена, если каждый раз позволять группе отколовшихся элементов быть потомком выдолбленного кластера . Это создает дерево с корнем и уникальными кластерами с одним объектом в качестве листьев. ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{0}}$ ${\displaystyle n}$

Программное обеспечение

Реализации с открытым исходным кодом

Иерархическая кластерная дендрограмма набора данных Iris (с использованием R ). Источник

Иерархическая кластеризация и интерактивная визуализация дендрограммы в пакете инструментов для интеллектуального анализа данных Orange .

• ALGLIB реализует несколько иерархических алгоритмов кластеризации (однозвенный, полнозвенный, Уорда) на C++ и C# с памятью O(n²) и временем выполнения O(n³).
• ELKI включает в себя несколько иерархических алгоритмов кластеризации, различные стратегии связывания, а также эффективные алгоритмы SLINK, ^[2] CLINK ^[3] и Андерберга, гибкое извлечение кластеров из дендрограмм и различные другие алгоритмы кластерного анализа .
• У Julia есть реализация внутри пакета Clustering.jl. ^[21]
• Octave , аналог MATLAB в GNU , реализует иерархическую кластеризацию в функции «linkage».
• Orange — программный пакет для интеллектуального анализа данных, включающий иерархическую кластеризацию с интерактивной визуализацией дендрограммы.
• R имеет встроенные функции ^[22] и пакеты, которые предоставляют функции для иерархической кластеризации. ^{[23] [24] [25]}
• SciPy реализует иерархическую кластеризацию на Python, включая эффективный алгоритм SLINK.
• scikit-learn также реализует иерархическую кластеризацию в Python.
• Weka включает иерархический кластерный анализ.

Коммерческие реализации

• MATLAB включает иерархический кластерный анализ.
• SAS включает иерархический кластерный анализ в PROC CLUSTER.
• Mathematica включает пакет иерархической кластеризации.
• NCSS включает иерархический кластерный анализ.
• SPSS включает иерархический кластерный анализ.
• Qlucore Omics Explorer включает иерархический кластерный анализ.
• Stata включает иерархический кластерный анализ.
• CrimeStat включает в себя алгоритм иерархического кластера ближайшего соседа с графическим выводом для географической информационной системы.

Смотрите также

• Двоичное разбиение пространства
• Иерархия ограничивающего объема
• Коричневая кластеризация
• Кладистика
• Кластерный анализ
• Вычислительная филогенетика
• Алгоритм кластеризации данных CURE
• Цель Дасгупты
• Дендрограмма
• Определение количества кластеров в наборе данных
• Иерархическая кластеризация сетей
• Хеширование, чувствительное к местоположению
• Поиск ближайшего соседа
• Алгоритм цепочки ближайших соседей
• Числовая таксономия
• Алгоритм ОПТИКА
• Статистическое расстояние
• Постоянная гомология

Ссылки

1. Нильсен, Франк (2016). "8. Иерархическая кластеризация". Введение в HPC с MPI для науки о данных. Springer. С. 195–211. ISBN 978-3-319-21903-5.
2. R. Sibson (1973). "SLINK: оптимально эффективный алгоритм для метода кластера с одной связью" (PDF) . The Computer Journal . 16 (1). British Computer Society: 30–34. doi : 10.1093/comjnl/16.1.30 .
3. D. Defays (1977). "Эффективный алгоритм для метода полной связи". The Computer Journal . 20 (4). British Computer Society: 364–6. doi :10.1093/comjnl/20.4.364.
4. Эппштейн, Дэвид (2001-12-31). «Быстрая иерархическая кластеризация и другие приложения динамических ближайших пар». ACM Journal of Experimental Algorithmics . 5 : 1–es. arXiv : cs/9912014 . doi :10.1145/351827.351829. ISSN  1084-6654.
5. "Процедура CLUSTER: методы кластеризации". Руководство пользователя SAS/STAT 9.2 . Институт SAS . Получено 26.04.2009 .
6. Székely, GJ; Rizzo, ML (2005). «Иерархическая кластеризация с помощью совместных расстояний между внутренними: расширение метода минимальной дисперсии Уорда». Журнал классификации . 22 (2): 151–183. doi :10.1007/s00357-005-0012-9. S2CID  206960007.
7. Фернандес, Альберто; Гомес, Серхио (2020). «Универсальная связь: семейство стратегий сохранения пространства для агломеративной иерархической кластеризации». Журнал классификации . 37 (3): 584–597. arXiv : 1906.09222 . doi : 10.1007/s00357-019-09339-z. S2CID  195317052.
8. Ward, Joe H. (1963). «Иерархическая группировка для оптимизации целевой функции». Журнал Американской статистической ассоциации . 58 (301): 236–244. doi :10.2307/2282967. JSTOR  2282967. MR  0148188.
9. Podani, János (1989), Mucina, L.; Dale, MB (ред.), "Новые методы комбинаторной кластеризации", Numerical syntaxonomy , Dordrecht: Springer Netherlands, стр. 61–77, doi :10.1007/978-94-009-2432-1_5, ISBN 978-94-009-2432-1, получено 2022-11-04
10. Базальто, Николас; Беллотти, Роберто; Де Карло, Франческо; Факки, Паоло; Панталео, Эстер; Паскацио, Саверио (15 июня 2007 г.). «Хаусдорфская кластеризация финансовых временных рядов». Физика А: Статистическая механика и ее приложения . 379 (2): 635–644. arXiv : физика/0504014 . Бибкод : 2007PhyA..379..635B. doi :10.1016/j.physa.2007.01.011. ISSN  0378-4371. S2CID  27093582.
11. Шуберт, Эрих (2021). HACAM: Иерархическая агломеративная кластеризация вокруг медоидов – и ее ограничения (PDF) . LWDA'21: Лернен, Виссен, Датен, Аналисен 01–03 сентября 2021 г., Мюнхен, Германия. стр. 191–204 – через CEUR-WS.
12. Миямото, Садааки; Кайдзу, Юсукэ; Эндо, Ясунори (2016). Иерархическая и неиерархическая кластеризация медоидов с использованием асимметричных мер сходства. 2016 Совместная 8-я Международная конференция по мягким вычислениям и интеллектуальным системам (SCIS) и 17-й Международный симпозиум по передовым интеллектуальным системам (ISIS). стр. 400–403. doi :10.1109/SCIS-ISIS.2016.0091.
13. Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data (PDF) . Графический интерфейс. Графический интерфейс . doi :10.20380/gi2016.14 . Получено 2022-11-04 .
14. Чжан, Вэй; Ван, Сяоган; Чжао, Дели; Тан, Сяоу (2012). «Связь степеней графа: агломеративная кластеризация на направленном графе». В Fitzgibbon, Andrew; Lazebnik, Svetlana ; Perona, Pietro; Sato, Yoichi; Schmid, Cordelia (ред.). Computer Vision – ECCV 2012. Lecture Notes in Computer Science. Vol. 7572. Springer Berlin Heidelberg. pp. 428–441. arXiv : 1208.5092 . Bibcode :2012arXiv1208.5092Z. doi :10.1007/978-3-642-33718-5_31. ISBN 9783642337185. S2CID  14751.Смотрите также: https://github.com/waynezhanghk/gacluster
15. Чжан, В.; Чжао, Д.; Ван, С. (2013). «Агломеративная кластеризация с помощью максимального инкрементного интеграла пути». Pattern Recognition . 46 (11): 3056–65. Bibcode :2013PatRe..46.3056Z. CiteSeerX 10.1.1.719.5355 . doi :10.1016/j.patcog.2013.04.013. 
16. Чжао, Д.; Тан, С. (2008). «Циклизация кластеров с помощью дзета-функции графа». NIPS'08: Труды 21-й Международной конференции по нейронным системам обработки информации . Curran. стр. 1953–60. CiteSeerX 10.1.1.945.1649 . ISBN  9781605609492.
17. Ma, Y.; Derksen, H.; Hong, W.; Wright, J. (2007). «Сегментация многомерных смешанных данных с помощью кодирования и сжатия данных с потерями». Труды IEEE по анализу шаблонов и машинному интеллекту . 29 (9): 1546–62. doi : 10.1109/TPAMI.2007.1085. hdl : 2142/99597 . PMID  17627043. S2CID  4591894.
18. Фернандес, Альберто; Гомес, Серхио (2008). «Решение проблемы неуникальности в агломеративной иерархической кластеризации с использованием мультидендрограмм». Журнал классификации . 25 (1): 43–65. arXiv : cs/0608049 . doi :10.1007/s00357-008-9004-x. S2CID  434036.
19. Лежандр, П.; Лежандр, LFJ (2012). "Кластерный анализ §8.6 Инверсии". Численная экология . Развитие в моделировании окружающей среды. Том 24 (3-е изд.). Elsevier. С. 376–7. ISBN 978-0-444-53868-0.
20. Кауфман, Л.; Руссью, П.Дж. (2009) [1990]. "6. Разделительный анализ (программа DIANA)". Поиск групп в данных: введение в кластерный анализ . Wiley. стр. 253–279. ISBN 978-0-470-31748-8.
21. "Иерархическая кластеризация · Кластеризация.jl". juliastats.org . Получено 2022-02-28 .
22. "hclust function - RDocumentation". www.rdocumentation.org . Получено 2022-06-07 .
23. Галили, Таль; Бенджамини, Йоав; Симпсон, Гэвин; Джефферис, Грегори (28.10.2021), dendextend: Расширение функциональности «дендрограммы» в R , получено 07.06.2022
24. Парадис, Эммануэль и др. "ape: Analyses of Philogenetics and Evolution" . Получено 28.12.2022 .
25. Фернандес, Альберто; Гомес, Серхио (2021-09-12). "mdendro: Extended Agglomerative Hierarchical Clustering" . Получено 2022-12-28 .

Дальнейшее чтение

• Кауфман, Л.; Руссью, П.Дж. (1990). Поиск групп в данных: Введение в кластерный анализ (1-е изд.). Нью-Йорк: John Wiley. ISBN 0-471-87876-6.
• Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2009). "14.3.12 Иерархическая кластеризация". Элементы статистического обучения (2-е изд.). Нью-Йорк: Springer. С. 520–8. ISBN 978-0-387-84857-0. Архивировано из оригинала (PDF) 2009-11-10 . Получено 2009-10-20 .