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

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

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

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

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

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

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