Porównanie hierarchicznych dendrogramów grupowania uzyskanych różnymi odległościami i metodami


28

[Początkowy tytuł „Pomiar podobieństwa dla hierarchicznych drzew klastrowych” został później zmieniony przez @ttnphns, aby lepiej odzwierciedlić temat]

Przeprowadzam szereg hierarchicznych analiz skupień na ramce danych rekordów pacjentów (np. Podobnie do http://www.biomedcentral.com/1471-2105/5/126/figure/F1?highres=y )

Eksperymentuję z różnymi miarami odległości , różnymi wagami parametrów i różnymi metodami hierarchicznymi , aby zrozumieć ich wpływ na końcowe klastry / strukturę / widok drzewa (dendrogram). Moje pytanie, czy istnieje standardowe obliczenie / miara do obliczenia różnicy między różnymi drzewami hierarchicznymi i jak zaimplementować to w R (np. Aby obliczyć, że niektóre drzewa są prawie identyczne, a niektóre są drastycznie różne).

Odpowiedzi:


44

Aby porównać podobieństwo dwóch struktur hierarchicznych (drzewiastych), zastosowano miary oparte na idei korelacji kopenetycznej. Ale czy prawidłowe jest porównanie dendrogramów w celu wybrania „właściwej” metody lub miary odległości w hierarchicznym grupowaniu?

Istnieją pewne punkty - ukryte zaczepy - dotyczące hierarchicznej analizy skupień, które uważam za bardzo ważne :

  • Nigdy nie porównuj (w celu wybrania metody zapewniającej silniejszy podział) dendrogramów otrzymanych wizualnie różnymi metodami aglomeracji. Nie powie, która metoda jest w tym „lepsza”. Każda metoda ma swój „prototypowy” wygląd drzewa: drzewa będą się różniły konsekwentnie, nawet jeśli dane nie mają struktury klastrowej lub mają losową strukturę klastrową. (I nie sądzę, aby istniała normalizacja lub środek, który usunąłby te wewnętrzne różnice). Możesz jednak porównać wygląd dendrogramu wyników uzyskanych tą samą metodą, ale z różnymi danymi. Maksyma: bezpośrednie, porównywanie wyglądu dendrogramów po różnych metodach jest niedopuszczalne .
  • 1 Maksyma: wybranie poziomu cięcia przez rozważenie wyglądu dendrogramu, chociaż jest możliwe, nie jest najlepszą metodą wyboru partycji, a dla niektórych metod może być mylące . Zamiast tego zaleca się oparcie się na formalnym wewnętrznym kryterium klastrowania .
  • Chociaż nikt nie może zabronić ci „eksperymentowania” z pomiarami odległości lub metodami aglomeracyjnymi, lepiej jest świadomie wybrać odległość i metodę , nie zaślepiać. Odległość powinna odzwierciedlać aspekty różnicy, którymi jesteś zainteresowany, a metoda - trzeba być świadomym - implikuje określony archetyp gromady (np. Metafora gromady Totemów jest, powiedziałbym, typem ; gromada po całkowitym połączeniu być kołem [przez hobby lub fabułę]; klaster po pojedynczym łączeniu byłby widmem [łańcuchem]; klaster po centroidie byłby bliskością platform [polityka]; przeciętny klaster łączący jest koncepcyjnie najbardziej niezróżnicowany i ogólnie byłby zjednoczoną klasą ).
  • Niektóre metody wymagają odpowiednich pomiarów odległości i / lub odpowiedniego rodzaju danych. Na przykład totem i centroid wymagają logicznie (kwadrat) odległości euklidesowej - ponieważ metody te angażują się w obliczanie centroidów w przestrzeni euklidesowej. A obliczenia geometrycznych centroidów są niezgodne np. Z danymi binarnymi; dane powinny być skalowane / ciągłe. Maxim: założenia dotyczące danych / odległości / metody i korespondencja są bardzo ważne i nie tak łatwe.
  • Wstępne przetwarzanie (takie jak centrowanie, skalowanie i inne formy transformacji zmiennych / cech), wcześniejsze obliczenie macierzy odległości i przeprowadzanie grupowania, jest również niezwykle ważnym pytaniem. Może to dramatycznie wpłynąć na wyniki. Zastanów się, jakie przetwarzanie wstępne może ci pomóc i będzie miało sens z punktu widzenia interpretacji. Nigdy też nie wstydź się dokładnie sprawdzać danych graficznie przed przystąpieniem do analizy skupień.
  • Nie wszystkie metody grupowania aglomeracyjnego mogą być jednakowo postrzegane jako zapewniające hierarchiczną klasyfikację ... z powodów filozoficznych. Na przykład metoda centroid rzeczywiście daje hierarchię w pewnym sensie, ponieważ centrum klastrów jest wyłaniającą się i definiującą cechą klastra jako całości , a scalanie klastrów jest sterowane przez tę funkcję. Z drugiej strony całkowite powiązanie „odrzuca” obie podgrupy, gdy je łączy - na zasadzie dystansu między poszczególnymi obiektami obu. Zatem pełny dendrogram powiązania jest jedynie historią kolekcji, a nie taksonomią typu rodzic-dziecko .Maxim: hierarchiczna analiza skupień aglomeracyjnych ogólnie oczekuje, że utworzysz partycję na podstawie jej wyniku, a nie zobaczysz wynik jako taksonomię hierarchiczną.
  • Hierarchiczne grupowanie jest typowym chciwym algorytmem, który dokonuje najlepszego wyboru spośród alternatyw pojawiających się na każdym etapie w nadziei, że w końcu zbliży się do optymalnego rozwiązania. Jednak „najlepszy” wybór pojawiający się na wysokim poziomie prawdopodobnie będzie gorszy niż globalny optymalny teoretycznie możliwy na tym etapie. Im większy jest krok, tym większa jest z reguły suboptymalność. Biorąc pod uwagę, że zwykle chcemy niewielkiej liczby klastrów, ważne są ostatnie kroki; i, jak już powiedziano, oczekuje się, że będą stosunkowo słabe, jeśli liczba kroków jest wysoka (powiedzmy, krok tysięczny). Dlatego hierarchiczne grupowanie generalnie nie zaleca się dla dużych próbek obiektów (numeracja tysiące obiektów), nawet jeśli program może obsłużyć tak dużą macierz odległości.

XjajotYjajot


1 Późniejsza aktualizacja problemu dendrogramu metody totemów . Różne programy klastrowania mogą generować różnie przekształcone współczynniki aglomeracji dla metody Warda. Dlatego ich dendrogramy będą wyglądać nieco inaczej, mimo że historia i wyniki grupowania są takie same . Na przykład SPSS nie bierze pierwiastka ze współczynników ultrametrycznych i kumuluje je w danych wyjściowych. Inną tradycją (na przykład w niektórych pakietach R) jest rootowanie (tzw. „Ward-2”)implementacje) i nie kumulować. Powtarzając, różnice te wpływają tylko na ogólny kształt / wygląd dendrogramu, a nie na wyniki grupowania. Ale wygląd dendrogramu może wpłynąć na twoją decyzję dotyczącą liczby klastrów. Morał polega na tym, że bezpiecznie byłoby nie polegać w ogóle na dendrogramie w metodzie Warda, chyba że dokładnie wiesz, jakie są te współczynniki z twojego programu i jak poprawnie je interpretować.


5
Mogę popierać to wszystko. Dwie kwestie, które chcę dodać: A) wydaje się, że robisz coś w rodzaju nadmiernego dopasowania . Systematycznie oceniając miary, wagi i metody, istnieje wysokie ryzyko, że parametry, które uzyskasz, będą wysoce specyficzne dla twoich bieżących danych i mogą być bezużyteczne dla innych danych lub nawet późniejszych danych. B) Na czym polega znajomość podobieństwa dendrogramów. Zastanów się, co chcesz z nimi zrobić później, a następnie spróbuj ocenić wynik końcowy. Ocena wyników pośrednich może być myląca.
Anony-Mousse,

1
Jeśli nadal interesujesz się tym tematem, pomyślałem, że moja ostatnia odpowiedź na temat DS SE może okazać się pomocna, szczególnie, że oferuje on zasięg, choć ograniczony, zarówno częstych, jak i bayesowskich podejść do hierarchicznych modeli tematycznych (z osadzonymi informacjami o klasach) i wybierając miary podobieństwa .
Aleksandr Blekh

@ttnphns, czy możesz wyjaśnić bardziej szczegółowo, jak używać „współczynnika kolizji” do porównywania dwóch hierarchicznych klasyfikacji?
bassir
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.