В интеллектуальном анализе данных и статистика, иерархическая кластеризация (также называемая иерархический кластерный анализ или HCA ) - это метод кластерного анализа который стремится построить иерархию кластеров. Стратегии иерархической кластеризации обычно делятся на два типа:
Как правило, слияния и разделения определяются жадным способом. Результаты иерархической кластеризации обычно представляются в виде дендрограммы.
. Стандартный алгоритм для иерархической агломеративной кластеризации (HAC) имеет временную сложность и требует , что делает его слишком медленным даже для средних наборов данных. Однако для некоторых особых случаев известны оптимальные эффективные агломерационные методы (сложности ): SLINK для однократной связи и CLINK для кластеризации полной связи. С помощью кучи время выполнения общего случая можно уменьшить до , улучшение вышеупомянутой границы , при стоимость дальнейшего увеличения требований к памяти. Во многих случаях накладные расходы на память при таком подходе слишком велики, чтобы сделать его практически применимым.
За исключением особого случая одиночной связи, ни один из алгоритмов (кроме исчерпывающего поиска в ) можно гарантированно найти оптимальное решение.
Делительная кластеризация с исчерпывающим поиском - это , но это обычное дело использовать более быструю эвристику для выбора разбиений, например k-средних.
Чтобы решить, какие кластеры следует объединить (для агломерации), или где кластер должен быть разделен (для разделения), требуется мера несходства между наборами наблюдений. В большинстве методов иерархической кластеризации это достигается за счет использования соответствующей метрики (мера расстояния между парами наблюдений) и критерия связи, который определяет несходство множеств как функция парных расстояний наблюдений в наборах.
Выбор подходящей метрики будет влиять на форму кластеров, поскольку некоторые элементы могут быть относительно ближе друг к другу по одной метрике, чем по другой. Например, в двух измерениях под метрикой расстояния Манхэттен расстояние между исходной точкой (0,0) и (.5,.5) совпадает с расстоянием между исходной точкой и (0, 1), а под метрикой Метрика евклидова расстояния у последнего строго больше.
Некоторые часто используемые метрики для иерархической кластеризации:
Имена | Формула |
---|---|
Евклидово расстояние | |
Евклидово расстояние в квадрате | |
Манхэттенское расстояние | |
Максимальное расстояние | |
расстояние Махаланобиса | где S - матрица ковариации |
для текстовые или другие нечисловые данные, часто используются такие показатели, как расстояние Хэмминга или расстояние Левенштейна.
Обзор кластерного анализа в исследованиях психологии здоровья показал, что наиболее распространенной мерой расстояния в опубликованных исследованиях в этой области исследований является Евклидово расстояние или Евклидово расстояние в квадрате.
Критерий связи определяет расстояние между наборами наблюдений как функцию попарных расстояний между наблюдениями.
Некоторые часто используемые критерии связи между двумя наборами наблюдений A и B:
Имена | Формула |
---|---|
Максимум или кластеризация с полной связью | |
Минимальная или одинарная кластеризация | |
Кластеризация связей невзвешенного среднего (или UPGMA ) | |
Средневзвешенная кластеризация связей (или WPGMA ) | |
Центроидная кластеризация связи, или UPGMC | , где и - центроиды кластеров s и t, соответственно. |
Минимальная энергия кластеризации |
где d - th Выбранная метрика. Другие критерии связи включают в себя:
Иерархическая кластеризация имеет явное преимущество, заключающееся в том, что можно использовать любую допустимую меру расстояния. Фактически, наблюдения сами по себе не требуются: все, что используется, это матрица расстояний.
Например, предположим, что эти данные должны быть кластеризованы, а евклидово расстояние - это показатель расстояния.
Иерархическая кластеризация дендрограмма будет выглядеть так:
Традиционное представление 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} и, следовательно, определить расстояние между двумя кластерами. Обычно расстояние между двумя кластерами и равно одно из следующих:
В случае связанных минимальных расстояний, пара выбирается случайным образом, что позволяет несколько структурно различных дендрограмм. В качестве альтернативы все связанные пары могут быть объединены одновременно, генерируя уникальную дендрограмму.
Всегда можно решить остановить кластеризацию, когда имеется достаточно небольшое количество кластеров (числовой критерий). Некоторые связи могут также гарантировать, что агломерация происходит на большем расстоянии между кластерами, чем предыдущая агломерация, а затем можно прекратить кластеризацию, когда кластеры слишком далеко друг от друга для объединения (критерий расстояния). Однако это не относится, например, к центроидному соединению, где могут происходить так называемые инверсии (инверсии, отклонения от ультраметричности).
Основной принцип разделительной кластеризации был опубликован как алгоритм DIANA (DIvisive ANAlysis Clustering). Первоначально все данные находятся в одном кластере, а самый большой кластер разделяется до тех пор, пока каждый объект не станет отдельным. Поскольку существуют способы разбиения каждого кластера, необходима эвристика. ДИАНА выбирает объект с максимальной средней несхожестью, а затем перемещает в этот кластер все объекты, которые больше похожи на новый кластер, чем на остальные.