Przejdź do treści
Wróć do wyników wyszukiwania

Klasteryzacja hierarchiczna

Autor metody
Ward, J. H.
Rok
1963
Typ
Unsupervised clustering (agglomerative)

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Klasteryzacja hierarchiczna jest metodą nienadzorowaną, która grupuje obserwacje w zagnieżdżone klastry i przedstawia wynik w postaci dendrogramu, dzięki czemu liczba klastrów nie musi być ustalona z góry.

Jej forma aglomeracyjna opiera się na kryterium grupowania funkcji celu wprowadzonej przez Joe Warda w 1963 roku.

Intuicja stojąca za metodą

Wyobraźmy sobie, że każda obserwacja zaczyna jako własna, maleńka grupa. Na każdym etapie łączone są dwie najbardziej podobne grupy, potem kolejne dwie i tak dalej, aż wszystko połączy się w jedno drzewo. Cięcie tego drzewa na różnych wysokościach daje różną liczbę klastrów, więc można zdecydować, jak drobno podzielić dane po zobaczeniu struktury, zamiast ustalać stałą liczbę z góry.

Historia

Forma aglomeracyjna klasteryzacji hierarchicznej została formalnie ugruntowana przez Joe H. Warda w 1963 roku, który przedstawił łączenie klastrów jako optymalizację funkcji celu — minimalizację wzrostu wariancji wewnątrzgrupy przy każdym połączeniu. Wiązanie Warda pozostaje jednym z najczęściej stosowanych kryteriów, a generowany przez nie dendrogram jest standardowym narzędziem eksploracyjnym w naukach społecznych, medycznych i biznesowych.

Kiedy stosować

Używaj jej do eksploracyjnego grupowania, gdy chcesz odkryć strukturę bez wstępnego określania liczby klastrów, na cechach ciągłych, porządkowych lub kategorycznych przy co najmniej około 10 obserwacjach. Jest ona mało wymagająca pod względem założeń, ale opiera się na dwóch wyborach: odpowiedniej metryce odległości i odpowiedniej metodzie wiązania. Poniżej około 10 obserwacji macierz odległości jest niewiarygodna, a dendrogram nie może pokazać znaczącej struktury, więc K-średnich jest bezpieczniejszą alternatywą; przy bardzo małych próbach wyniki stają się nadmiernie wrażliwe na metodę wiązania, a przynależność do klastrów jest niestabilna.

Ograniczenia i uwagi

  • Wyniki zależą w dużej mierze od wybranej metryki odległości i metody wiązania, które są decyzjami użytkownika.
  • Na małych próbach przynależność do klastrów jest niestabilna i nadmiernie wrażliwa na metodę wiązania.
  • Przy mniej niż około 10 obserwacjach macierz odległości jest niewiarygodna, a dendrogram nie pokazuje znaczącej struktury.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Nie wymaga wstępnego ustalenia liczby klastrów — odczytuje się ją z dendrogramu.
  • Dendrogram daje interpretowalną wizualną mapę tego, jak klastry zagnieżdżają się na różnych poziomach podobieństwa.
  • Mało wymagająca pod względem założeń: brak wymogu normalności i uwzględnia cechy ciągłe, porządkowe i kategoryczne poprzez wybór odległości.
  • Działa jako narzędzie eksploracyjne do ujawniania struktury przed ustaleniem podziału.

Zastosowania

  • Eksploracyjna segmentacja obserwacji, gdy liczba grup jest nieznana.
  • Budowanie dendrogramu do wizualizacji, jak przypadki zagnieżdżają się na różnych poziomach podobieństwa.
  • Grupowanie respondentów, próbek lub jednostek na mieszanych cechach ciągłych, porządkowych i kategorycznych.
  • Generowanie kandydackich liczb klastrów w celu poinformowania późniejszej metody podziału.

Jak to działa

Jak to działa

1

Najpierw oblicza się odległość między każdą parą obserwacji przy użyciu wybranej metryki odległości, tworząc macierz odległości. Wybór metryki ma znaczenie: definiuje ona, co liczy się jako „podobne”, a cechy ciągłe, porządkowe i kategoryczne mogą wymagać różnych definicji odległości.

2

Zaczynając od każdej obserwacji jako własnego klastra, algorytm wielokrotnie łączy dwa najbliższe klastry zgodnie z wybraną metodą wiązania. Kryterium Warda, na przykład, łączy parę, która daje najmniejszy wzrost sumy kwadratów wewnątrz klastra, utrzymując powstałe klastry tak zwarty, jak to możliwe. Wybór wiązania silnie kształtuje ostateczne grupowanie.

Wzór
\Delta(A,B) = \sum_{i \in A \cup B} \lVert x_i - m_{A \cup B}\rVert^2 - \sum_{i \in A}\lVert x_i - m_A\rVert^2 - \sum_{i \in B}\lVert x_i - m_B\rVert^2
3

Sekwencja połączeń jest zapisywana jako dendrogram, drzewo, którego wysokości gałęzi pokazują odległość, przy której klastry się połączyły. Cięcie dendrogramu na wybranej wysokości daje przypisania do klastrów, więc liczba klastrów jest odczytywana z drzewa, a nie określana z góry.

Częste pułapki

  • Uruchamianie jej na mniej niż około 10 obserwacjach, gdzie macierz odległości i dendrogram nie są wiarygodne.
  • Wybieranie metryki odległości i metody wiązania bez uzasadnienia i traktowanie wyniku jako ostatecznego.
  • Ufanie niestabilnej przynależności do klastrów na małej próbie zamiast przełączania się na K-średnich lub mieszaninę Gaussa.
  • Wymuszanie stałej liczby klastrów przed zbadaniem naturalnych punktów cięcia dendrogramu.

Najczęściej zadawane pytania

Czy muszę najpierw wybrać liczbę klastrów?

Nie. Klasteryzacja hierarchiczna buduje pełne drzewo połączeń niezależnie, a liczbę klastrów decydujesz później, tnąc dendrogram na wybranej wysokości — jest to jedna z jej głównych zalet w porównaniu do metod takich jak K-średnich.

Jakiej metryki odległości i wiązania powinienem użyć?

Oba są świadomymi wyborami, które silnie kształtują wynik. Metryka odległości powinna pasować do typów cech, a wiązanie Warda jest powszechnym domyślnym wyborem, ponieważ utrzymuje klastry zwarte, minimalizując wzrost wariancji wewnątrz klastra przy każdym połączeniu.

Ile obserwacji potrzebuję?

Co najmniej około 10. Poniżej tej liczby macierz odległości jest niewiarygodna, a dendrogram nie może ujawnić znaczącej struktury, więc K-średnich jest bezpieczniejszą alternatywą.

Dlaczego moje klastry są niestabilne?

Na małych próbach wynik jest nadmiernie wrażliwy na metodę wiązania, więc przynależność do klastrów zmienia się przy niewielkich zmianach. W takiej sytuacji rozważ K-średnich lub model mieszaniny Gaussa.

Pokrewne metody

Źródła

  1. Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244.

    Otwórz odnośnik DOI
    Skopiowano.