Как понять недостатки иерархической кластеризации?

19

Может кто-нибудь объяснить плюсы и минусы иерархической кластеризации?

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

Ответы на этот пост очень хорошо объясняют недостатки k средств. Как понять недостатки К-средних

clustering k-means unsupervised-learning hierarchical-clustering GeorgeOfTheRF
источник

2

В этом ответе я коснулся некоторых потенциально проблемных аспектов иерархического агломерационного кластерного анализа. Основным «недостатком» является то, что это не итеративный, однопроходный жадный алгоритм. С помощью жадного алгоритма вы оптимизируете задачу текущего шага, которая - для большинства методов HC - не обязательно гарантирует лучший раздел на шаге в будущем. Основным преимуществом HC является то, что он гибок в отношении выбора меры приближения для использования. @Mic уже дал хороший ответ ниже, так что я просто повторяю.

ttnphns

13

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

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

Если вы хотите углубиться в более тонкие свойства кластеризации, вы, возможно, не захотите противопоставлять плоскую кластеризацию, такую как иерархической кластеризации, такой как одиночные, средние, полные связи. Например, все эти кластеры сохраняют пространство, то есть, когда вы строите кластеры, вы не искажаете пространство, в то время как иерархическая кластеризация, такая как Ward, не сохраняет пространство, то есть на каждом этапе объединения это будет искажать метрическое пространство. $k$

В заключение следует отметить, что недостатки алгоритмов иерархической кластеризации могут сильно отличаться друг от друга. Некоторые могут иметь свойства, аналогичные -means: Ward стремится оптимизировать дисперсию, но Single Linkage нет. Но они также могут иметь разные свойства: Ward расширяет пространство, тогда как Single Linkage сохраняет пространство, как образные. $k$ $k$

- редактировать для уточнения свойств сохранения пространства и расширения пространства

Сохранение пространства: где - расстояние между кластерами и вы хотите объединить, и

D_{i j} \in [min_{x \in C_{i}, y \in C_{j}} d (x, y), max_{x \in C_{i}, y \in C_{j}} d (x, y)]

$D_{ij} \in \left[ \min_{x \in C_i, y \in C_j} d(x,y), \max_{x \in C_i, y \in C_j} d(x,y) \right]$

D_{i j}

$D_{ij}$

C_{i}

$C_i$

C_{j}

$C_j$

d

$d$ это расстояние между точками данных.

Расширение пространства: т. Е. объединения и алгоритм будет отталкивать кластер дальше.

D (C_{i} \cup C_{j}, C_{k}) \geq max (D_{i k}, D_{j k}),

$D(C_i \cup C_j, C_k) \geq \max(D_{ik}, D_{jk}),$

C_{i}

$C_i$

C_{j}

$C_j$

C_{k}

$C_k$

микрофон
источник

Можете ли вы привести еще несколько примеров данных, имеющих иерархическую структуру? Не последовал примеру финансового рынка.

GeorgeOfTheRF

Конечно. ср arxiv.org/pdf/cond-mat/9802256.pdf или просто рисунок 7 в arxiv.org/pdf/1506.00976.pdf, который изображает матрицу корреляции, которая имеет (шумную) иерархическую структуру блоков корреляции: вы можете заметить блоки на главной диагонали, которые делятся на несколько блоков, каждый из которых делится на еще больше блоков. Это примерно соответствует подразделению в регионах (Европа, США, Азия, за исключением Японии, Японии), затем каждый регион делится на качество активов (скажем, высокое качество против мусора), затем делится на крупные промышленные сектора (розничная торговля, промышленность, СМИ), далее подразделить на (аэрокосмическая, авто ...)

микрофон

3

+1. Однако,

should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchy

не обязательно. В большинстве случаев скорее наоборот. Иерархия HC - это скорее история алгоритма, чем структура данных . Тем не менее, этот вопрос в конечном итоге философский / логический, а не статистический.

ttnphns

Ward is not space-conserving, i.e. at each merging step it will distort the metric space, Вы можете написать больше об этом? Это не очень понятно.

ttnphns

Ward is space-dilating, whereas Single Linkage is space-conserving like k-means, Вы хотели сказать, что космический контракт для единственной связи?

ttnphns

13

Масштабируемость

значит, явный победитель здесь. намного лучше, чеммасштабируемость (в некоторых случаях ) иерархической кластеризации, потому что обычно и и малы (к сожалению, стремлюсь расти вместе с $k$ $O(n\cdot k\cdot d\cdot i)$ $O(n^3 d)$ $O(n^2 d)$ $k$ $i$ $d$ $i$ , поэтому делаетне $n$ $O(n)$ обычно держат). Кроме того, потребление памяти является линейным, а не квадратичным (обычно существуют линейные особые случаи).

гибкость

-средство крайне ограничено в применении. Он по существу ограничен евклидовыми расстояниями (включая евклидовы в пространствах ядра и расхождения Брегмана, но они довольно экзотичны, и никто не использует их с средними). Хуже того, -means работает только с числовыми данными (которые должны быть непрерывными и плотными, чтобы подходить для средних). $k$ $k$ $k$ $k$

Иерархическая кластеризация - явный победитель здесь. Он даже не требует расстояния - можно использовать любую меру, включая функции подобия, просто предпочитая высокие значения низким значениям. Категориальные данные? обязательно просто используйте, например, Jaccard. Строки? Попробуйте расстояние Левенштейна. Временная последовательность? конечно. Данные смешанного типа? Gower расстояние. Существуют миллионы наборов данных, в которых вы можете использовать иерархическую кластеризацию, но где вы не можете использовать -means. $k$

модель

Здесь нет победителя. -means получает высокие баллы, потому что это приводит к значительному сокращению данных. Центроиды легко понять и использовать. Иерархическая кластеризация, с другой стороны, производит дендрограмму. Дендрограмма также может быть очень полезна для понимания вашего набора данных. $k$

Аноним-Мусс-Восстановить Монику
источник

Иерархическая ошибка, как k означает, когда кластеры 1) несферические 2) имеют разный радиус 3) имеют разную плотность?

GeorgeOfTheRF

2

Оба могут работать, и оба могут потерпеть неудачу. Вот почему такие вещи, как дендрограммы, полезны. Никогда не доверяйте результатам кластеризации, чтобы они были «правильными».

Anony-Mousse

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

Арпит Сисодия

7

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

Распространенным предположением в кластерном анализе является то, что данные отбираются из некоторой базовой плотности вероятности которой у нас нет доступа. Но предположим, что у нас был доступ к нему. Как мы определяем кластеры из ? $f$ $f$

Очень естественный и интуитивный подход состоит в том, чтобы сказать, что кластеры являются областями высокой плотности. Например, рассмотрим двухпиковую плотность ниже: $f$

Рисуя линию на графике, мы создаем набор кластеров. Например, если мы рисуем линию на , мы получаем два показанных кластера. Но если мы проведем линию на , мы получим один кластер. $\lambda_1$ $\lambda_3$

Чтобы сделать это более точным, предположим, что мы имеем произвольное . Каковы кластеры на уровне ? Они являются связной компонентой множества суперуровня . $\lambda > 0$ $f$ $\lambda$ $\{x : f(x) \geq \lambda \}$

Теперь вместо выбора произвольного мы могли бы рассмотреть все , так что множество «истинных» кластеров - это все связные компоненты любого суперуровневого множества . Ключ в том, что эта коллекция кластеров имеет иерархическую структуру. $\lambda$ $\lambda$ $f$ $f$

$f$ $\mathcal X$ $C_1$ $\{ x : f(x) \geq \lambda_1 \}$ $C_2$ $\{ x : f(x) \geq \lambda_2 \}$ $C_1$ $\lambda_1$ $C_2$ $\lambda_2$ $\lambda_2 < \lambda_1$ $C_1 \subset C_2$ $C_1 \cap C_2 = \emptyset$

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

$A$ $B$ $f$ $n$ $f$ $X_n$ $X_n$ $A_n$ $A \cap X_n$ $B_n$ $B \cap X_n$ $\Pr(A_n \cap B_n) = \emptyset \to 1$ $n \to \infty$ $A$ $B$ .

По сути, согласованность Хартигана говорит о том, что наш метод кластеризации должен адекватно разделять области высокой плотности. Хартиган исследовал, может ли единообразная кластеризация быть последовательной, и обнаружил, что это не так соответствует по размерам> 1. Задача нахождения общего, последовательный метод оценки дерева кластера был открыт до всего лишь несколько лет назад, когда Чоудхури и Дасгупта введены надежная единственная связь , которая доказуемо последовательна. Я бы посоветовал почитать об их методе, поскольку, на мой взгляд, он довольно элегантный.

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

Наконец, я скажу, что последовательность Хартигана в некотором смысле не соответствует нашей интуиции конвергенции. Проблема состоит в том, что согласованность Хартигана позволяет методу кластеризации сильно разбивать кластеры на сегменты , так что алгоритм может быть согласованным по Хартигану, но создавать кластеризации, которые сильно отличаются от истинного дерева кластеров. В этом году мы подготовили работу по альтернативному понятию конвергенции, которое решает эти проблемы. Работа появилась в статье «За пределами согласованности Хартигана: метрика искажения слияния для иерархической кластеризации» в COLT 2015.

ЮМЭ
источник

Это интересный способ мышления об иерархической кластеризации. Мне это сильно напоминает кластеризацию путем непараметрической оценки плотности ( pdf ), которая реализована Rв пакете pdfCluster . (Я обсуждаю это здесь .)

gung - Восстановить Монику

HDBSCAN * использует аналогичный подход.

Аноним-Мусс

3

Дополнительным практическим преимуществом иерархической кластеризации является возможность визуализации результатов с использованием дендрограммы. Если вы не знаете заранее, какое количество кластеров вы ищете (как это часто бывает ...), вы можете использовать график дендрограммы, который поможет вам выбрать $k$ без необходимости создавать отдельные кластеры. Дедрограмма также может дать хорошее представление о структуре данных, помочь идентифицировать выбросы и т. Д. Иерархическая кластеризация также является детерминированной, тогда как k-среднее со случайной инициализацией может дать вам разные результаты при запуске несколько раз на одних и тех же данных. В k-средних вы также можете выбрать разные методы для обновления кластерных средств (хотя подход Хартиган-Вонга является наиболее распространенным), что не является проблемой для иерархического метода.

EDIT thanks to ttnphns: One feature that hierarchical clustering shares with many other algorithms is the need to choose a distance measure. This is often highly dependent on the particular application and goals. This might be seen as an additional complication (another parameter to select...), but also as an asset - more possibilities. On the contrary, classical K-means algorithm specifically uses Euclidean distance.

Jacek Podlewski
источник

3

I suppose "problem" in your last paragraph would be seen positively as an asset. K-means, however, is based implicitly on euclidean distance only.

ttnphns

Many possible choices can be a problem as well as an asset, indeed :) Thanks for the comment on k-means, I'll improve that paragraph.

Jacek Podlewski

@ttnphns На самом деле, "

k

$k$ -средства "можно использовать с любыми расхождениями Брегмана jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf ; я имею в виду, что это тот случай, когда рассматривается

k

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

mic

Я полагаю, что первоначальный вопрос был задан в отношении «классических» K-средних и ни малейшего намерения вникать в расхождения Брегмана. Однако, приятное замечание, я обязательно проверю эту статью более тщательно.

Jacek Podlewski

@mic, никто не использует расхождения Брегмана за пределами евклидова расстояния ... это только крошечный крошечный класс. Но люди хотели бы использовать, например, расстояние Манхэттен, Гауэр и т. Д., Которые не являются расхождениями Брегмана, насколько я знаю.

Anony-Mousse

Как понять недостатки иерархической кластеризации?

Ответы:

Масштабируемость

гибкость

модель