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
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<λ1C1⊂C2C1∩C2=∅.
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 A∩Xn, and let Bn be the smallest containing all of B∩Xn. Then our clustering method is said to be Hartigan consistent if Pr(An∩Bn)=∅→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.