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

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

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

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

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

Сложность

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

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

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

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

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

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

Имена	Формула
Кластеризация с максимальной или полной связью	$\max _{a\in A,\,b\in B}d(a,b)$
Минимальная кластеризация или кластеризация с одной связью	$\min _{a\in A,\,b\in B}d(a,b)$
Кластеризация невзвешенных средних связей (или UPGMA )	${\frac {1}{\|A\|\cdot \|B\|}}\sum _{a\in A}\sum _{b\in B}d(a,b).$
Кластеризация средневзвешенных связей (или WPGMA )	$d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.$
Кластеризация центроидных связей, или UPGMC	$\lVert \mu _{A}-\mu _{B}\rVert ^{2}$ где $\mu _{A}$ и $\mu _{B}$ являются центроидами A соотв. Б.
Медианная кластеризация связей, или WPGMC	$d(i\cup j,k)=d(m_{i\cup j},m_{k})$ где $m_{i\cup j}={\tfrac {1}{2}}\left(m_{i}+m_{j}\right)$
Универсальная кластеризация связей ^{[ 7 ]}	${\sqrt[{p}]{{\frac {1}{\|A\|\cdot \|B\|}}\sum _{a\in A}\sum _{b\in B}d(a,b)^{p}}},p\neq 0$
Связь с палатой , ^{[ 8 ]} Минимальное увеличение суммы квадратов (MISSQ) ^{[ 9 ]}	${\frac {\|A\|\cdot \|B\|}{\|A\cup B\|}}\lVert \mu _{A}-\mu _{B}\rVert ^{2}=\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}-\sum _{x\in A}\lVert x-\mu _{A}\rVert ^{2}-\sum _{x\in B}\lVert x-\mu _{B}\rVert ^{2}$
Минимальная сумма квадратов ошибок (MNSSQ) ^{[ 9 ]}	$\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}$
Минимальное увеличение дисперсии (МИВАР) ^{[ 9 ]}	${\frac {1}{\|A\cup B\|}}\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}-{\frac {1}{\|A\|}}\sum _{x\in A}\lVert x-\mu _{A}\rVert ^{2}-{\frac {1}{\|B\|}}\sum _{x\in B}\lVert x-\mu _{B}\rVert ^{2}$ $={\text{Var}}(A\cup B)-{\text{Var}}(A)-{\text{Var}}(B)$
Минимальная дисперсия (MNVAR) ^{[ 9 ]}	${\frac {1}{\|A\cup B\|}}\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}={\text{Var}}(A\cup B)$
Хаусдорфова связь ^{[ 10 ]}	$\max _{x\in A\cup B}\min _{y\in A\cup B}d(x,y)$
Минимальная сумма Медоидная связь ^{[ 11 ]}	$\min _{m\in A\cup B}\sum _{y\in A\cup B}d(m,y)$ такой, что m — медоид полученного кластера
Увеличение минимальной суммы Связь Medoid ^{[ 11 ]}	$\min _{m\in A\cup B}\sum _{y\in A\cup B}d(m,y)-\min _{m\in A}\sum _{y\in A}d(m,y)-\min _{m\in B}\sum _{y\in B}d(m,y)$
Медоидная связь ^{[ 12 ]}^{[ 13 ]}	$d(m_{A},m_{B})$ где $m_{A}$ , $m_{B}$ являются медоидами предыдущих кластеров
Минимальная энергетическая кластеризация	${\frac {2}{nm}}\sum _{i,j=1}^{n,m}\\|a_{i}-b_{j}\\|_{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\\|a_{i}-a_{j}\\|_{2}-{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\\|b_{i}-b_{j}\\|_{2}$

Некоторые из них можно пересчитать только рекурсивно (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} и, следовательно, определить расстояние между двумя кластерами. Обычно расстояние между двумя кластерами ${\mathcal {A}}$ и ${\mathcal {B}}$ является одним из следующих:

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

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

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

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

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

{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 ANAанализ). ^{[ 20 ]} Первоначально все данные находятся в одном кластере, а самый большой кластер разделяется до тех пор, пока каждый объект не станет отдельным. Потому что существуют $O(2^{n})$ способы разделения каждого кластера, необходимы эвристики. ДИАНА выбирает объект с максимальным средним отличием, а затем перемещает в этот кластер все объекты, которые больше похожи на новый кластер, чем на остальные.

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

Формально ДИАНА действует следующим образом:

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

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

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

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

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

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

ALGLIB реализует несколько алгоритмов иерархической кластеризации (однозвенная, полная ссылка, Ward) на C++ и C# с памятью O(n²) и временем выполнения O(n³).
ELKI включает в себя несколько алгоритмов иерархической кластеризации, различные стратегии связывания, а также эффективный SLINK, ^{[ 2 ]} КЛИНК ^{[ 3 ]} и алгоритмы Андерберга, гибкое извлечение кластеров из дендрограмм и различные другие кластерного анализа . алгоритмы
У Джулии есть реализация внутри пакета Clustering.jl. ^{[ 21 ]}
Octave , GNU аналог MATLAB, реализует иерархическую кластеризацию в функции «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 включает в себя алгоритм иерархического кластера ближайшего соседа с графическим выводом для географической информационной системы.

См. также

Ссылки

^ Нильсен, Франк (2016). «8. Иерархическая кластеризация» . Введение в HPC с MPI для науки о данных . Спрингер. стр. 195–211. ISBN 978-3-319-21903-5 .
^ Jump up to: ^а ^б Р. Сибсон (1973). «SLINK: оптимально эффективный алгоритм для метода однозвенной кластеризации» (PDF) . Компьютерный журнал . 16 (1). Британское компьютерное общество: 30–34. дои : 10.1093/comjnl/16.1.30 .
^ Jump up to: ^а ^б Д. Дефайс (1977). «Эффективный алгоритм для метода полной ссылки». Компьютерный журнал . 20 (4). Британское компьютерное общество: 364–6. дои : 10.1093/comjnl/20.4.364 .
^ Эппштейн, Дэвид (31 декабря 2001 г.). «Быстрая иерархическая кластеризация и другие применения динамических ближайших пар» . Журнал экспериментальной алгоритмики ACM . 5 : 1–с. arXiv : cs/9912014 . дои : 10.1145/351827.351829 . ISSN 1084-6654 .
^ «Процедура CLUSTER: методы кластеризации» . Руководство пользователя SAS/STAT 9.2 . Институт САС . Проверено 26 апреля 2009 г.
^ Секели, Г.Дж.; Риццо, МЛ (2005). «Иерархическая кластеризация с помощью соединения между-внутри расстояний: расширение метода минимальной дисперсии Уорда». Журнал классификации . 22 (2): 151–183. дои : 10.1007/s00357-005-0012-9 . S2CID 206960007 .
^ Фернандес, Альберто; Гомес, Серхио (2020). «Универсальная связь: семейство экономящих пространство стратегий агломеративной иерархической кластеризации». Журнал классификации . 37 (3): 584–597. arXiv : 1906.09222 . дои : 10.1007/s00357-019-09339-z . S2CID 195317052 .
^ Jump up to: ^а ^б Уорд, Джо Х. (1963). «Иерархическая группировка для оптимизации целевой функции». Журнал Американской статистической ассоциации . 58 (301): 236–244. дои : 10.2307/2282967 . JSTOR 2282967 . МР 0148188 .
^ Jump up to: ^а ^б ^с ^д Подани, Янош (1989), Мучина, Л.; Дейл, МБ (ред.), «Новые методы комбинаторной кластеризации» , Численная синтаксономия , Дордрехт: Springer Нидерланды, стр. 61–77, doi : 10.1007/978-94-009-2432-1_5 , ISBN 978-94-009-2432-1 , получено 4 ноября 2022 г.
^ Базальт, Николас; Беллотти, Роберто; Де Карло, Франческо; Факки, Паоло; Панталео, Эстер; Паскацио, Саверио (15 июня 2007 г.). «Хаусдорфская кластеризация финансовых временных рядов» . Физика А: Статистическая механика и ее приложения . 379 (2): 635–644. arXiv : физика/0504014 . Бибкод : 2007PhyA..379..635B . дои : 10.1016/j.physa.2007.01.011 . ISSN 0378-4371 . S2CID 27093582 .
^ Jump up to: ^а ^б Шуберт, Эрих (2021). HACAM: Иерархическая агломеративная кластеризация вокруг медоидов – и ее ограничения (PDF) . LWDA'21: Обучение, знания, данные, анализ, 1–03 сентября 2021 г., Мюнхен, Германия. стр. 191–204 – через CEUR-WS.
^ Миямото, Садааки; Кайдзу, Юске; Эндо, Ясунори (2016). Иерархическая и неиерархическая кластеризация медоидов с использованием асимметричных мер сходства . 2016 Совместная 8-я Международная конференция по мягким вычислениям и интеллектуальным системам (SCIS) и 17-й Международный симпозиум по передовым интеллектуальным системам (ISIS). стр. 400–403. дои : 10.1109/SCIS-ISIS.2016.0091 .
^ Герр, Доминик; Хан, Ци; Ломанн, Штеффен; Эртл, Томас (2016). Уменьшение визуального беспорядка посредством иерархического проецирования многомерных размеченных данных (PDF) . Графический интерфейс. Графический интерфейс . дои : 10.20380/gi2016.14 . Проверено 4 ноября 2022 г.
^ Чжан, Вэй; Ван, Сяоган; Чжао, Дели; Тан, Сяоу (2012). «Связь степеней графа: агломеративная кластеризация на ориентированном графе». В Фитцгиббоне, Эндрю; Лазебник Светлана ; Перона, Пьетро; Сато, Йоичи; Шмид, Корделия (ред.). Компьютерное зрение – ECCV 2012 . Конспекты лекций по информатике. Том. 7572. Шпрингер Берлин Гейдельберг. стр. 428–441. arXiv : 1208.5092 . Бибкод : 2012arXiv1208.5092Z . дои : 10.1007/978-3-642-33718-5_31 . ISBN 9783642337185 . S2CID 14751 . См. также: https://github.com/waynezhanghk/gacluster.
^ Чжан, В.; Чжао, Д.; Ван, X. (2013). «Агломеративная кластеризация с помощью максимального инкрементального интеграла по пути». Распознавание образов . 46 (11): 3056–65. Бибкод : 2013PatRe..46.3056Z . CiteSeerX 10.1.1.719.5355 . дои : 10.1016/j.patcog.2013.04.013 .
^ Чжао, Д.; Тан, X. (2008). «Циклизация кластеров с помощью дзета-функции графа». NIPS'08: Материалы 21-й Международной конференции по нейронным системам обработки информации . Курран. стр. 1953–60. CiteSeerX 10.1.1.945.1649 . ISBN 9781605609492 .
^ Может.; Дерксен, Х.; Хонг, В.; Райт, Дж. (2007). «Сегментация многомерных смешанных данных посредством кодирования и сжатия данных с потерями». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (9): 1546–62. дои : 10.1109/TPAMI.2007.1085 . hdl : 2142/99597 . ПМИД 17627043 . S2CID 4591894 .
^ Фернандес, Альберто; Гомес, Серхио (2008). «Решение неоднозначности в агломеративной иерархической кластеризации с использованием мультидендрограмм». Журнал классификации . 25 (1): 43–65. arXiv : cs/0608049 . дои : 10.1007/s00357-008-9004-x . S2CID 434036 .
^ Лежандр, П.; Лежандр, LFJ (2012). «Кластерный анализ §8.6 Развороты» . Численная экология . Развитие экологического моделирования. Том. 24 (3-е изд.). Эльзевир. стр. 376–7. ISBN 978-0-444-53868-0 .
^ Кауфман, Л.; Руссиу, П.Дж. (2009) [1990]. «6. Дивизионный анализ (Программа ДИАНА)» . Поиск групп в данных: введение в кластерный анализ . Уайли. стр. 253–279. ISBN 978-0-470-31748-8 .
^ «Иерархическая кластеризация · Clustering.jl» . Сайт juliastats.org . Проверено 28 февраля 2022 г.
^ «функция hclust — RDocumentation» . www.rdocumentation.org . Проверено 7 июня 2022 г.
^ Галили, Таль; Бенджамини, Йоав; Симпсон, Гэвин; Джефферис, Грегори (28 октября 2021 г.), dendextend: Расширение функциональности «дендрограммы» в R , получено 7 июня 2022 г.
^ Паради, Эммануэль; и др. «Обезьяна: анализ филогенетики и эволюции» . Проверено 28 декабря 2022 г.
^ Фернандес, Альберто; Гомес, Серхио (12 сентября 2021 г.). «mdendro: расширенная агломеративная иерархическая кластеризация» . Проверено 28 декабря 2022 г.

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

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

[1] Нильсен, Франк (2016). «8. Иерархическая кластеризация» . Введение в HPC с MPI для науки о данных . Спрингер. стр. 195–211. ISBN 978-3-319-21903-5 .

[SLINK-2] Jump up to: ^а ^б Р. Сибсон (1973). «SLINK: оптимально эффективный алгоритм для метода однозвенной кластеризации» (PDF) . Компьютерный журнал . 16 (1). Британское компьютерное общество: 30–34. дои : 10.1093/comjnl/16.1.30 .

[CLINK-3] Jump up to: ^а ^б Д. Дефайс (1977). «Эффективный алгоритм для метода полной ссылки». Компьютерный журнал . 20 (4). Британское компьютерное общество: 364–6. дои : 10.1093/comjnl/20.4.364 .

[4] Эппштейн, Дэвид (31 декабря 2001 г.). «Быстрая иерархическая кластеризация и другие применения динамических ближайших пар» . Журнал экспериментальной алгоритмики ACM . 5 : 1–с. arXiv : cs/9912014 . дои : 10.1145/351827.351829 . ISSN 1084-6654 .

[5] «Процедура CLUSTER: методы кластеризации» . Руководство пользователя SAS/STAT 9.2 . Институт САС . Проверено 26 апреля 2009 г.

[6] Секели, Г.Дж.; Риццо, МЛ (2005). «Иерархическая кластеризация с помощью соединения между-внутри расстояний: расширение метода минимальной дисперсии Уорда». Журнал классификации . 22 (2): 151–183. дои : 10.1007/s00357-005-0012-9 . S2CID 206960007 .

[7] Фернандес, Альберто; Гомес, Серхио (2020). «Универсальная связь: семейство экономящих пространство стратегий агломеративной иерархической кластеризации». Журнал классификации . 37 (3): 584–597. arXiv : 1906.09222 . дои : 10.1007/s00357-019-09339-z . S2CID 195317052 .

[wards_method-8] Jump up to: ^а ^б Уорд, Джо Х. (1963). «Иерархическая группировка для оптимизации целевой функции». Журнал Американской статистической ассоциации . 58 (301): 236–244. дои : 10.2307/2282967 . JSTOR 2282967 . МР 0148188 .

[:0-9] Jump up to: ^а ^б ^с ^д Подани, Янош (1989), Мучина, Л.; Дейл, МБ (ред.), «Новые методы комбинаторной кластеризации» , Численная синтаксономия , Дордрехт: Springer Нидерланды, стр. 61–77, doi : 10.1007/978-94-009-2432-1_5 , ISBN 978-94-009-2432-1 , получено 4 ноября 2022 г.

[10] Базальт, Николас; Беллотти, Роберто; Де Карло, Франческо; Факки, Паоло; Панталео, Эстер; Паскацио, Саверио (15 июня 2007 г.). «Хаусдорфская кластеризация финансовых временных рядов» . Физика А: Статистическая механика и ее приложения . 379 (2): 635–644. arXiv : физика/0504014 . Бибкод : 2007PhyA..379..635B . дои : 10.1016/j.physa.2007.01.011 . ISSN 0378-4371 . S2CID 27093582 .

[:1-11] Jump up to: ^а ^б Шуберт, Эрих (2021). HACAM: Иерархическая агломеративная кластеризация вокруг медоидов – и ее ограничения (PDF) . LWDA'21: Обучение, знания, данные, анализ, 1–03 сентября 2021 г., Мюнхен, Германия. стр. 191–204 – через CEUR-WS.

[12] Миямото, Садааки; Кайдзу, Юске; Эндо, Ясунори (2016). Иерархическая и неиерархическая кластеризация медоидов с использованием асимметричных мер сходства . 2016 Совместная 8-я Международная конференция по мягким вычислениям и интеллектуальным системам (SCIS) и 17-й Международный симпозиум по передовым интеллектуальным системам (ISIS). стр. 400–403. дои : 10.1109/SCIS-ISIS.2016.0091 .

[13] Герр, Доминик; Хан, Ци; Ломанн, Штеффен; Эртл, Томас (2016). Уменьшение визуального беспорядка посредством иерархического проецирования многомерных размеченных данных (PDF) . Графический интерфейс. Графический интерфейс . дои : 10.20380/gi2016.14 . Проверено 4 ноября 2022 г.

[14] Чжан, Вэй; Ван, Сяоган; Чжао, Дели; Тан, Сяоу (2012). «Связь степеней графа: агломеративная кластеризация на ориентированном графе». В Фитцгиббоне, Эндрю; Лазебник Светлана ; Перона, Пьетро; Сато, Йоичи; Шмид, Корделия (ред.). Компьютерное зрение – ECCV 2012 . Конспекты лекций по информатике. Том. 7572. Шпрингер Берлин Гейдельберг. стр. 428–441. arXiv : 1208.5092 . Бибкод : 2012arXiv1208.5092Z . дои : 10.1007/978-3-642-33718-5_31 . ISBN 9783642337185 . S2CID 14751 . См. также: https://github.com/waynezhanghk/gacluster.

[15] Чжан, В.; Чжао, Д.; Ван, X. (2013). «Агломеративная кластеризация с помощью максимального инкрементального интеграла по пути». Распознавание образов . 46 (11): 3056–65. Бибкод : 2013PatRe..46.3056Z . CiteSeerX 10.1.1.719.5355 . дои : 10.1016/j.patcog.2013.04.013 .

[16] Чжао, Д.; Тан, X. (2008). «Циклизация кластеров с помощью дзета-функции графа». NIPS'08: Материалы 21-й Международной конференции по нейронным системам обработки информации . Курран. стр. 1953–60. CiteSeerX 10.1.1.945.1649 . ISBN 9781605609492 .

[17] Может.; Дерксен, Х.; Хонг, В.; Райт, Дж. (2007). «Сегментация многомерных смешанных данных посредством кодирования и сжатия данных с потерями». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (9): 1546–62. дои : 10.1109/TPAMI.2007.1085 . hdl : 2142/99597 . ПМИД 17627043 . S2CID 4591894 .

[18] Фернандес, Альберто; Гомес, Серхио (2008). «Решение неоднозначности в агломеративной иерархической кластеризации с использованием мультидендрограмм». Журнал классификации . 25 (1): 43–65. arXiv : cs/0608049 . дои : 10.1007/s00357-008-9004-x . S2CID 434036 .

[19] Лежандр, П.; Лежандр, LFJ (2012). «Кластерный анализ §8.6 Развороты» . Численная экология . Развитие экологического моделирования. Том. 24 (3-е изд.). Эльзевир. стр. 376–7. ISBN 978-0-444-53868-0 .

[20] Кауфман, Л.; Руссиу, П.Дж. (2009) [1990]. «6. Дивизионный анализ (Программа ДИАНА)» . Поиск групп в данных: введение в кластерный анализ . Уайли. стр. 253–279. ISBN 978-0-470-31748-8 .

[21] «Иерархическая кластеризация · Clustering.jl» . Сайт juliastats.org . Проверено 28 февраля 2022 г.

[22] «функция hclust — RDocumentation» . www.rdocumentation.org . Проверено 7 июня 2022 г.

[23] Галили, Таль; Бенджамини, Йоав; Симпсон, Гэвин; Джефферис, Грегори (28 октября 2021 г.), dendextend: Расширение функциональности «дендрограммы» в R , получено 7 июня 2022 г.

[24] Паради, Эммануэль; и др. «Обезьяна: анализ филогенетики и эволюции» . Проверено 28 декабря 2022 г.

[25] Фернандес, Альберто; Гомес, Серхио (12 сентября 2021 г.). «mdendro: расширенная агломеративная иерархическая кластеризация» . Проверено 28 декабря 2022 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]