Jak zrozumieć wady hierarchicznego grupowania?

19

Czy ktoś może wyjaśnić zalety i wady hierarchicznego grupowania?

  1. Czy klastrowanie hierarchiczne ma te same wady, co oznacza K?
  2. Jakie są zalety Hierarchical Clustering nad K?
  3. Kiedy powinniśmy używać środków K zamiast hierarchicznego grupowania i odwrotnie?

Odpowiedzi na ten post wyjaśnia wady k oznacza bardzo dobrze. Jak zrozumieć wady K-średnich

GeorgeOfTheRF
źródło
2
W tej odpowiedzi dotknąłem niektórych potencjalnie problematycznych aspektów hierarchicznej analizy skupień aglomeracyjnych. Główną „wadą” jest to, że jest to niepiśmienny, chciwy algorytm jednoprzebiegowy. Za pomocą chciwego algorytmu optymalizujesz zadanie bieżącego kroku, co - w przypadku większości metod HC - niekoniecznie gwarantuje najlepszą partycję w odległym kroku w przyszłości. Główną zaletą HC jest to, że jest elastyczny pod względem wyboru zastosowanego miernika zbliżeniowego. @Mic już udzielił dobrej odpowiedzi poniżej, więc po prostu powtarzam.
ttnphns

Odpowiedzi:

13

Podczas gdy k oznacza próbuje zoptymalizować globalny cel (wariancja klastrów) i osiąga lokalny optymalny, aglomeracyjny hierarchiczny klaster ma na celu znalezienie najlepszego kroku przy każdym zespoleniu klastra (algorytm zachłanny), który jest wykonywany dokładnie, ale skutkuje potencjalnie nieoptymalnym rozwiązaniem .

Należy użyć hierarchicznego grupowania, gdy dane bazowe mają strukturę hierarchiczną (np. Korelacje na rynkach finansowych) i chcesz odzyskać hierarchię. Nadal możesz zastosować do tego k średnich, ale możesz skończyć z partycjami (od najgrubszego (wszystkie punkty danych w klastrze) do najlepszego (każdy punkt danych to klaster)), które nie są zagnieżdżone, a zatem niewłaściwa hierarchia.

Jeśli chcesz zagłębić się w lepsze właściwości klastrowania, możesz nie chcieć przeciwstawiać się klastrowaniu płaskiemu, na przykład k średnim, klastrom hierarchicznym, takim jak Pojedyncze, Średnie, Kompletne Połączenia. Na przykład wszystkie te klastry zajmują mało miejsca, tzn. Gdy budujesz klastry, nie zniekształcasz przestrzeni, podczas gdy hierarchiczne klastry, takie jak Totem, nie zajmują miejsca, tj. Na każdym etapie łączenia zniekształca przestrzeń metryczną.

Podsumowując, wady hierarchicznych algorytmów klastrowania mogą się bardzo różnić między sobą. Niektóre mogą mieć podobne właściwości do k średnich: Totem ma na celu optymalizację wariancji, ale Pojedyncze Połączenie nie. Mogą jednak mieć także inne właściwości: Totem rozszerza przestrzeń, podczas gdy Pojedynczy Łącznik zachowuje przestrzeń jak k średnie.

- edycja w celu precyzyjnego określenia właściwości zajmujących przestrzeń i rozszerzających przestrzeń

Oszczędność miejsca:

Dij[minxCi,yCjd(x,y),maxxCi,yCjd(x,y)]
gdzie Dij jest odległością między klastrami Ci i Cj chcesz scalić, a d to odległość między punktami danych.

Przestrzeń-rozszerzeniu: czyli poprzez połączenie C I i C j algorytm popchnie dalej klastrze C k .

D(CiCj,Ck)max(Dik,Djk),
CiCjCk
mikrofon
źródło
Czy możesz podać jeszcze kilka przykładów danych o strukturze hierarchicznej? Nie poszedł za przykładem rynku finansowego.
GeorgeOfTheRF
Pewnie. por. arxiv.org/pdf/cond-mat/9802256.pdf lub po prostu rysunek 7 w arxiv.org/pdf/1506.00976.pdf, który przedstawia macierz korelacji o (hałaśliwej) hierarchicznej strukturze bloków korelacji: można zauważyć bloki na głównej przekątna, które są podzielone na więcej bloków, każdy podzielony na jeszcze więcej bloków. Odpowiada to mniej więcej podziałowi na regiony (Europa, USA, Azja bez Japonii, Japonia), a następnie każdy region podzielony przez jakość aktywów (powiedzmy wysoką jakość kontra śmieci), a następnie podzielony przez duże sektory przemysłowe (handel detaliczny, przemysł, media), dalej dzielą się na (lotnictwo, auto ...)
mic
3
+1. Jednak should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchyniekoniecznie. W większości przypadków wręcz przeciwnie. Hierarchia HC jest raczej historią algo niż strukturą danych . Jednak pytanie to jest ostatecznie filozoficzne / logiczne, a nie tak statystyczne.
ttnphns
Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Czy możesz napisać o tym więcej? To nie jest bardzo jasne.
ttnphns
Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Czy chciałbyś powiedzieć, że kontrakty kosmiczne dotyczą pojedynczego połączenia?
ttnphns
13

Skalowalność

oznacza tutaj wyraźnego zwycięzcę. O ( n K d I ) jest znacznie lepszy niż w O ( N 3 d ) (w niektórych przypadkach O ( n 2 d ) ) skalowalność grupowanie hierarchiczne ponieważ zwykle zarówno k i i i d są małe (niestety i wykazuje tendencję do wzrostu w n , tak o ( n ) maniekO(nkdi)O(n3d)O(n2d)kidinO(n)zwykle trzymaj). Ponadto zużycie pamięci jest liniowe, w przeciwieństwie do kwadratowego (zwykle istnieją specjalne przypadki liniowe).

Elastyczność

Wartość k -ma bardzo ograniczone zastosowanie. Jest to zasadniczo ograniczone do odległości euklidesowych (w tym euklidesowych w przestrzeniach jądra i rozbieżności Bregmana, ale są one dość egzotyczne i nikt tak naprawdę nie używa ich z k- średnimi). Co gorsza, k- średnie oznacza tylko dane liczbowe (które powinny być ciągłe i gęste, aby dobrze pasowały do k- średnich).kkkk

Hierarchiczne grupowanie jest tutaj wyraźnym zwycięzcą. Nie wymaga nawet odległości - można zastosować dowolny pomiar, w tym funkcje podobieństwa, po prostu preferując wysokie wartości od niskich. Dane kategorialne? na pewno po prostu użyj np. Jaccard. Smyczki? Wypróbuj odległość Levenshtein. Szereg czasowy? pewnie. Mieszane typy danych? Odległość Gower. Istnieją miliony zestawów danych, w których można użyć klastrowania hierarchicznego, ale w których nie można użyć średnich.k

Model

Nie ma tutaj zwycięzcy. oznacza wysokie wyniki, ponieważ zapewnia doskonałą redukcję danych. Centroidy są łatwe do zrozumienia i użycia. Z drugiej strony klastrowanie hierarchiczne tworzy dendrogram. Dendrogram może być również bardzo przydatny w zrozumieniu twojego zestawu danych.k

Anony-Mus-Przywróć Monikę
źródło
Czy błąd hierarchiczny jak k oznacza, że ​​klastry są 1) niesferyczne 2) mają inny promień 3) mają inną gęstość?
GeorgeOfTheRF
2
Oba mogą działać i oba mogą zawieść. Dlatego takie rzeczy jak dendrogramy są przydatne. Nigdy nie ufaj, że wynik grupowania będzie „poprawny”, zawsze.
Anony-Mus-Przywróć Monikę
Hierarchiczne grupowanie może dać lokalnie zoptymalizowane klastry, ponieważ opiera się na chciwym podejściu, ale K oznacza daje globalnie zoptymalizowane klastry. Doświadczyłem również, że wyjaśnienie hierarchicznego grupowania jest stosunkowo łatwe dla ludzi biznesu w porównaniu do średnich K.
Arpit Sisodia,
7

Chciałem tylko dodać nieco do pozostałych odpowiedzi, że w pewnym sensie istnieje silny teoretyczny powód, aby preferować pewne hierarchiczne metody grupowania.

Powszechnym założeniem w analizie skupień jest to, że dane są próbkowane z pewnej podstawowej gęstości prawdopodobieństwa , do której nie mamy dostępu. Załóżmy jednak, że mieliśmy do tego dostęp. W jaki sposób możemy zdefiniować klastry o f ?ff

Bardzo naturalnym i intuicyjnym podejściem jest stwierdzenie, że skupiska są regionami o dużej gęstości. Rozważmy na przykład gęstość dwóch pików poniżej:f

enter image description here

Rysując linię na wykresie, indukujemy zestaw klastrów. Na przykład, jeśli narysujemy linię w , otrzymamy dwa pokazane klastry. Ale jeśli narysujemy linię w λ 3 , otrzymamy pojedynczy klaster.λ1λ3

Dla uściślenia, załóżmy, że mamy dowolne . Jakie są klastry f na poziomie λ ? Są one połączonym składnikiem zestawu superpoziomowego { x : f ( x ) λ } .λ>0fλ{x:f(x)λ}

Teraz zamiast wybierania arbitralnego możemy rozważyć wszystkie λ , tak że zbiór „prawdziwych” klastrów f jest połączonymi składnikami dowolnego zestawu superpoziomowego f . Kluczem jest to, że ta kolekcja klastrów ma strukturę hierarchiczną .λ λff

Let me make that more precise. Suppose f is supported on X. Now let C1 be a connected component of {x:f(x)λ1}, and C2 be a connected component of {x:f(x)λ2}. In other words, C1 is a cluster at level λ1, and C2 is a cluster at level λ2. Then if λ2<λ1C1C2C1C2=.

Teraz mam próbki danych z gęstości. Czy mogę grupować te dane w sposób, który odzyskuje drzewo klastrów? W szczególności chcielibyśmy, aby metoda była spójna in the sense that as we gather more and more data, our empirical estimate of the cluster tree grows closer and closer to the true cluster tree.

Hartigan jako pierwszy zadał takie pytania, robiąc to, dokładnie zdefiniował, co oznaczałoby dla hierarchicznej metody klastrowania konsekwentna ocena drzewa klastrów. Jego definicja była następująca: LetZA and B be true disjoint clusters of f as defined above -- that is, they are connected components of some superlevel sets. Now draw a set of n samples iid from f, and call this set Xn. We apply a hierarchical clustering method to the data Xn, and we get back a collection of empirical clusters. Let An be the smallest empirical cluster containing all of AXn, and let Bn be the smallest containing all of BXn. Then our clustering method is said to be Hartigan consistent if Pr(AnBn)=1 as n for any pair of disjoint clusters A and B.

Essentially, Hartigan consistency says that our clustering method should adequately separate regions of high density. Hartigan investigated whether single linkage clustering might be consistent, and found that it is not consistent in dimensions > 1. The problem of finding a general, consistent method for estimating the cluster tree was open until just a few years ago, when Chaudhuri and Dasgupta introduced robust single linkage, which is provably consistent. I'd suggest reading about their method, as it is quite elegant, in my opinion.

So, to address your questions, there is a sense in which hierarchical cluster is the "right" thing to do when attempting to recover the structure of a density. However, note the scare-quotes around "right"... Ultimately density-based clustering methods tend to perform poorly in high dimensions due to the curse of dimensionality, and so even though a definition of clustering based on clusters being regions of high probability is quite clean and intuitive, it often is ignored in favor of methods which perform better in practice. That isn't to say robust single linkage isn't practical -- it actually works quite well on problems in lower dimensions.

Lastly, I'll say that Hartigan consistency is in some sense not in accordance with our intuition of convergence. The problem is that Hartigan consistency allows a clustering method to greatly over-segment clusters such that an algorithm may be Hartigan consistent, yet produce clusterings which are very different than the true cluster tree. We have produced work this year on an alternative notion of convergence which addresses these issues. The work appeared in "Beyond Hartigan Consistency: Merge distortion metric for hierarchical clustering" in COLT 2015.

jme
źródło
This is an interesting way of thinking about hierarchical clustering. I find it strongly reminiscent of clustering by nonparametric density estimation (pdf), which is implemented in R in the pdfCluster package. (I discuss it here.)
gung - Reinstate Monica
HDBSCAN* uses a similar approach.
Anony-Mousse -Reinstate Monica
3

An additional practical advantage in hierarchical clustering is the possibility of visualising results using dendrogram. If you don't know in advance what number of clusters you're looking for (as is often the case...), you can the dendrogram plot can help you choose k with no need to create separate clusterings. Dedrogram can also give a great insight into data structure, help identify outliers etc. Hierarchical clustering is also deterministic, whereas k-means with random initialization can give you different results when run several times on the same data. In k-means, you also can choose different methods for updating cluster means (although the Hartigan-Wong approach is by far the most common), which is no issue with hierarchical method.

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
źródło
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 Actually, " k-means " can be used with any Bregman divergences jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf ; I mean this is the case when considering that k-means is what results when considering the limiting case of Gaussian mixture models (from soft to hard), then by replacing Gaussian by another member of the exponential family, you replace the Euclidean distance by another Bregman divergence associated with the member of the family you picked. You end up with a similar algorithm scheme that aims to find a maximum likelihood with an expectation-maximization.
mic
I believe the original question was made with regard to "classical' K-means and not a slightest intention to delve into Bregman divergences. Nice remark though, I'll check out this paper more thoroughly for sure.
Jacek Podlewski
@mic nobody uses Bregman divergences beyond variations of Euclidean distance... it is a tiny tiny class only. But people would like to use e.g. Manhattan distance, Gower etc. which are not Bregman divergences for all I know.
Anony-Mousse -Reinstate Monica