Введение
Статистический метод анализа, который стремится построить иерархию кластеров.
В анализе данных и статистике иерархическое кластерирование (также называемое иерархическим анализом кластеров или HCA) – это метод кластерного анализа, который стремится построить иерархию кластеров. Стратегии иерархического кластерирования обычно делятся на две категории:
Агломеративный: Это подход "снизу вверх": каждое наблюдение изначально находится в собственном кластере, и пары кластеров объединяются по мере продвижения вверх по иерархии. Разделительный: Это подход "сверху вниз": все наблюдения изначально находятся в одном кластере, и разделения выполняются рекурсивно по мере продвижения вниз по иерархии. В общем случае, объединения и разделения определяются жадным алгоритмом. Результаты иерархического кластерирования обычно представляются в виде дендрограммы. Иерархическое кластерирование обладает явным преимуществом: может использоваться любая допустимая мера расстояния. Фактически, сами наблюдения не требуются: используется только матрица расстояний. С другой стороны, за исключением частного случая метода одиночной связи, ни один из алгоритмов (за исключением полного перебора) не гарантирует нахождение оптимального решения.
Agglomerative: This is a "bottom up" approach: Each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. Divisive: This is a "top down" approach: All observations start in one cluster, and splits are performed recursively as one moves down the hierarchy. In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram. Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. On the other hand, except for the special case of single linkage distance, none of the algorithms (except exhaustive search in ) can be guaranteed to find the optimum solution.
Сложность
Стандартный алгоритм для иерархической агломеративной кластеризации (HAC) имеет временную сложность и требует памяти, что делает его слишком медленным даже для наборов данных среднего размера. Однако для некоторых частных случаев известны оптимальные эффективные агломеративные методы (со сложностью ): SLINK для одиночной связи и CLINK для полной связи. Использование кучи позволяет сократить время выполнения общего случая до , что является улучшением по сравнению с вышеупомянутой границей , но за счет дальнейшего увеличения требований к памяти. Во многих случаях накладные расходы по памяти при таком подходе слишком велики для практического применения. Существуют методы, использующие квадродеревья, которые демонстрируют общее время работы при использовании памяти . Разделяющая кластеризация с полным перебором имеет сложность , но обычно для выбора разделов используются более быстрые эвристики, такие как k-средних.
Коммерческие реализации
MATLAB включает в себя иерархический кластерный анализ. SAS включает в себя иерархический кластерный анализ в PROC CLUSTER. Mathematica включает в себя пакет иерархической кластеризации. NCSS включает в себя иерархический кластерный анализ. SPSS включает в себя иерархический кластерный анализ. Qlucore Omics Explorer включает в себя иерархический кластерный анализ. Stata включает в себя иерархический кластерный анализ. CrimeStat включает в себя алгоритм иерархической кластеризации ближайших соседей с графическим выводом для географической информационной системы.