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

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Разработка функций Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k- означает Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор локального выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Схема машинного обучения
v т е

В интеллектуальном анализе данных и статистических данных , иерархическая кластеризация (также называемый иерархическим кластерного анализом или ГЛКОМ ) представляет собой метод кластерного анализа , который стремится построить иерархию кластеров. Стратегии иерархической кластеризации обычно делятся на два типа: ^[1]

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

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

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

За исключением особого случая одинарного связывания, ни один из алгоритмов (кроме полного перебора в ) не может гарантировать нахождение оптимального решения.${\ Displaystyle {\ mathcal {O}} (2 ^ {п})}$

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

Кластерное несходство [ править ]

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

Метрика [ править ]

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

Некоторые часто используемые метрики для иерархической кластеризации: ^[5]

Имена	Формула
Евклидово расстояние	${\ displaystyle \ | ab \ | _ {2} = {\ sqrt {\ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}}}$
Квадратное евклидово расстояние	${\ displaystyle \ | ab \ | _ {2} ^ {2} = \ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}$
Манхэттенское расстояние	${\ displaystyle \ | ab \ | _ {1} = \ sum _ {i} | a_ {i} -b_ {i} |}$
Максимальное расстояние	${\ displaystyle \ | ab \ | _ {\ infty} = \ max _ {i} | a_ {i} -b_ {i} |}$
Расстояние Махаланобиса	${\ displaystyle {\ sqrt {(ab) ^ {\ top} S ^ {- 1} (ab)}}}$где S - матрица ковариации

Для текстовых или других нечисловых данных часто используются такие показатели, как расстояние Хэмминга или расстояние Левенштейна .

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

Критерии связи [ править ]

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

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

Имена	Формула
Кластеризация с максимальной или полной связью	${\ displaystyle \ max \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$
Минимальная или одинарная кластеризация	${\ displaystyle \ min \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$
Кластеризация невзвешенных средних связей (или UPGMA )	${\ displaystyle {\ frac {1} {| A | \ cdot | B |}} \ sum _ {a \ in A} \ sum _ {b \ in B} d (a, b).}$
Кластеризация средневзвешенных связей (или WPGMA )	${\displaystyle d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.}$
Кластеризация центроидов, или UPGMC	${\displaystyle \|c_{s}-c_{t}\|}$где и - центроиды кластеров s и t соответственно.${\displaystyle c_{s}}$${\displaystyle c_{t}}$
Кластеризация с минимальной энергией	${\displaystyle {\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}}$

где d - выбранная метрика. Другие критерии привязки включают:

• Сумма всей внутрикластерной дисперсии.
• Увеличение дисперсии для объединяемого кластера ( критерий Уорда ). ^[8]
• Вероятность появления кластеров-кандидатов из одной и той же функции распределения (V-связь).
• Произведение внутренней и исходящей степени на графе k ближайших соседей (связь степени графа). ^[9]
• Приращение некоторого дескриптора кластера (т. Е. Количества, определенного для измерения качества кластера) после слияния двух кластеров. ^{[10] [11] [12]}

Обсуждение [ править ]

Иерархическая кластеризация имеет явное преимущество в том, что можно использовать любую допустимую меру расстояния. Фактически, сами наблюдения не требуются: все, что используется, - это матрица расстояний.

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

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

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

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

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

По желанию, на этом этапе можно также построить матрицу расстояний , где число в j -м столбце i-й строки - это расстояние между 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-связь).

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

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

Разделительная кластеризация [ править ]

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

Программное обеспечение [ править ]

Реализации с открытым исходным кодом [ править ]

• ALGLIB реализует несколько алгоритмов иерархической кластеризации (single-link, full-link, Ward) на C ++ и C # с памятью O (n²) и временем выполнения O (n³).
• ELKI включает несколько алгоритмов иерархической кластеризации, различные стратегии связывания, а также эффективные алгоритмы SLINK, ^[3] CLINK ^[4] и Андерберга, гибкое извлечение кластеров из дендрограмм и различные другие алгоритмы кластерного анализа .
• Octave , аналог MATLAB в GNU, реализует иерархическую кластеризацию в функции «связывание».
• Orange , программный пакет для интеллектуального анализа данных, включает иерархическую кластеризацию с интерактивной визуализацией дендрограмм.
• R имеет множество пакетов, которые предоставляют функции для иерархической кластеризации.
• SciPy реализует иерархическую кластеризацию в Python, включая эффективный алгоритм SLINK.
• scikit-learn также реализует иерархическую кластеризацию в Python.
• Weka включает иерархический кластерный анализ.

Коммерческие реализации [ править ]

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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