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

редактировать

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

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

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

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

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

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

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

Содержание

1 Несходство кластера
- 1.1 Метрика
- 1.2 Критерии связи
2 Обсуждение
3 Пример агломеративной кластеризации
4 Делительная кластеризация
5 Программное обеспечение
- 5.1 Открытый исходный код реализации
- 5.2 Коммерческие реализации
6 См. также
7 Ссылки
8 Дополнительная литература

Несходство кластеров

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

Метрика

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

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

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

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

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

Критерии связи

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

Некоторые часто используемые критерии связи между двумя наборами наблюдений A и B:

Имена	Формула
Максимум или кластеризация с полной связью	$max {d (a, b): a ∈ A, b ∈ B}. {\ displaystyle \ max \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$ $\ max \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.$
Минимальная или одинарная кластеризация	$min {d (a, b): a ∈ A, b ∈ B}. {\ displaystyle \ min \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$ $\ min \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.$
Кластеризация связей невзвешенного среднего (или UPGMA )	$1 \| A \| ⋅ \| B \| ∑ a ∈ A ∑ b ∈ B d (a, b). {\ Displaystyle {\ frac {1} {\| A \| \ cdot \| B \|}} \ sum _ {a \ in A} \ sum _ {b \ in B} d (a, b).}$ ${\ displaystyle {\ frac {1} {\| A \| \ cdot \| B \|}} \ sum _ {a \ in A} \ sum _ {b \ in B} d (a, b).}$
Средневзвешенная кластеризация связей (или WPGMA )	$d (i ∪ j, k) = d (i, k) + d (j, k) 2, {\ displaystyle d (i \ cup j, k) = {\ frac {d (i, k) + d (j, k)} {2}}.}$ ${\ displaystyle d (i \ cup j, k) = {\ frac {d (i, k) + d (j, k)} {2}}.}$
Центроидная кластеризация связи, или UPGMC	$‖ cs - ct ‖ {\ displaystyle \ \| c_ {s} -c_ {t} \ \|}$ ${\ displaystyle \ \| c_ {s} -c_ {t} \ \|}$ , где $cs {\ displaystyle c_ {s}}$ $c_ {s}$ и $ct {\ displaystyle c_ {t}}$ $c_ {t}$ - центроиды кластеров s и t, соответственно.
Минимальная энергия кластеризации	$2 нм ∑ i, j знак равно 1 N, м ‖ ai - bj ‖ 2 - 1 n 2 ∑ i, j = 1 n ‖ ai - aj ‖ 2 - 1 м 2 ∑ я, j = 1 m ‖ bi - bj ‖ 2 {\ 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}}$ ${\ 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 - th Выбранная метрика. Другие критерии связи включают в себя:

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

Обсуждение

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

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

Необработанные данные

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

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

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

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

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

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

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

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

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

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

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

min {d (x, y): x ∈ A, y ∈ B}. {\ displaystyle \ min \ {\, 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 | A | ⋅ | B | ∑ x ∈ A ∑ y ∈ B d (x, y). {\ Displaystyle {1 \ over {| {\ mathcal {A}} | \ cdot | {\ mathcal {B}} |}} \ sum _ {x \ in {\ mathcal {A}}} \ sum _ {y \ in {\ mathcal {B}}} d (x, y).}

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

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

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

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

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

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

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

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

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

Иерархическая кластеризация и интерактивная визуализация дендрограмм в Orange Data Mining Suite.

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

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

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

См. Также

Ссылки

Дополнительная литература

Кауфман, Л.; Rousseeuw, P.J. (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 г.