Иерархический кластерный анализ

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

Definition

Иерархический кластерный анализ — это подход к кластеризации, который создает дерево вложенных разбиений путем итеративного объединения наиболее похожих кластеров или разделения наименее когезивных в соответствии с выбранным расстоянием между кластерами.

Scope

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

Core questions

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

Key theories

Объединение, определяемое связью

Агломеративная кластеризация многократно объединяет два кластера, которые являются наиболее близкими согласно определению связи; одиночная, полная, средняя связи и связь Уорда кодируют различные понятия расстояния между кластерами и производят характерно разные формы кластеров.

Представление дендрограммы

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

Clinical relevance

Иерархическая кластеризация широко используется там, где вложенная группировка является естественной или информативной, например, при построении таксономий, организации тепловых карт экспрессии генов и исследовании сходства документов или организмов.

History

Методы иерархической группировки были формализованы в начале 1960-х годов, включая критерий минимальной дисперсии Уорда, и стали основными элементами численной таксономии и разведочного анализа данных, поскольку вычисления сделали построение дендрограмм рутинным.

Debates

Выбор связи

Одиночная связь может объединять кластеры в цепочки, тогда как полная связь имеет тенденцию создавать компактные группы, а метод Уорда предпочитает сферические кластеры одинакового размера, поэтому выбор связи сильно влияет на результаты и редко бывает однозначно правильным.

Key figures

• Joe Ward
• Peter Rousseeuw

Seminal works

• everitt2011
• kaufman1990
• wardjr1963

Frequently asked questions

В чем разница между агломеративной и дивизимной кластеризацией?

Агломеративная кластеризация начинается с каждого объекта как отдельного кластера и объединяется вверх, тогда как дивизимная кластеризация начинается с одного кластера и разделяется вниз; агломеративные методы гораздо более распространены на практике.

Как выбрать количество кластеров из дендрограммы?

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