Grupowanie hierarchiczne – wprowadzenie teoretyczne

Po krótkim wstępie do problemu grupowania dziś biorę na tapetę pierwszą grupę algorytmów grupujących – algorytmy hierarchiczne.

Z tego artykułu dowiesz się:
1. Jak działają algorytmy grupowania hierarchicznego?
2. Jakie są ich wady i zalety?
3. Kiedy stosować grupowanie hierarchiczne?

Opis metod hierarchicznych

Nazwa metod hierarchicznych wzięła się od swego rodzaju hierarchii, którą budują algorytmy implementujące to podejście. Ma ona strukturę drzewa (wizualizowanego na wykresie zwanym dendrogramem), które przedstawia proces działania algorytmu i budowy grup (poprzez podział bądź scalanie). Na osi x uporządkowane są grupy, a z osi y w łatwy sposób można odczytać odległość pomiędzy łączonymi grupami.

W celu opisania działania metod hierarchicznych podzielę je na dwie grupy:

• aglomeracyjne (wstępujące lub łączące) – w tym podejściu algorytm zaczyna swe działanie w momencie, gdy liczba grup równa się liczbie obserwacji – każda obserwacja stanowi odrębną grupę. Następnie w sposób iteracyjny grupy są scalane w taki sposób, by wariancja wewnątrz nich była możliwie najmniejsza, a pomiędzy grupami możliwie duża. Algorytmy te reprezentują podejście „od szczegółu do ogółu”. Podejście zaimplementowane w algorytmach aglomeracyjnych sprawdza się, gdy decydujemy się na poszukiwanie małych grup (po kilku iteracjach proces może zostać przerwany).
• deglomeracyjne (zstępujące lub dzielące) – rozpoczynają działanie, gdy wszystkie obserwacje znajdują się w jednej grupie. W kolejnych iteracjach działania algorytmu grupy są dzielone mając na uwadze te same kryteria, co w przypadku algorytmów aglomeracyjnych: wariancję i miary odległości pomiędzy grupami. Tego typu algorytmy sprawdzają się, gdy zależy nam na znalezieniu dużych grup (podejście „od ogółu do szczegółu”).

Podstawowe definicje

W trakcie działania algorytmu, w przestrzeni grupa składająca się z wielu obserwacji jest reprezentowana przez centroid (środek grupy w przestrzeni euklidesowej) lub klastroid (środek grupy w pozostałych przypadkach). Dodatkowo by zrozumieć działanie algorytmów hierarchicznych, konieczne jest poznanie dwóch podstawowych definicji:

• metryki pomiaru odległości – są to przyjęte miary odległości, z których korzysta algorytm do pomiaru dystansu dzielącego centroidy bądź obserwacje reprezentujące grupy (w zależności od wybranego podejścia). Jednym z pośrednich celów jest minimalizowanie odległości pomiędzy obserwacjami w ramach jednej grupy. Do najpopularniejszych miar odległości zaliczamy odległości: miejską (Manhattan), euklidesową (w wariancie z pierwiastkiem, lub bez – tzw. odległość kwadratowa), minkowskiego, canberra, maksimum i inne odległości oparte o współczynnik korelacji,
• metody łączenia grup – używane są przez algorytm do podejmowania decyzji o łączeniu grup. Służą do zdefiniowania odległości między grupami. Kolejnym celem algorytmów hierarchicznych jest bowiem maksymalizowanie odległości pomiędzy powstałymi grupami. Do najpopularniejszych metod łączenia należą metody:
  • pojedynczego połączenia (najbliższy sąsiad) – mierzona jest minimalna odległość pomiędzy grupami, co sprawia, że metoda ta jest wrażliwa na obserwacje odstające,
  • maksymalnego połączenia (najdalszy sąsiad) – mierzona jest maksymalna odległość pomiędzy grupami, co sprawia, że podobnie jak w przypadku metody pojedynczego połączenia, ta również jest wrażliwa na obserwacje odstające,
  • centroidalnego połączenia – mierzona jest odległość dzieląca centroidy obu grup,
  • średniego połączenia (przeciętny sąsiad) – mierzona jest średnia odległość między obserwacjami z dwóch różnych grup,
  • medianowego połączenia – mierzona jest mediana odległość między obserwacjami z dwóch różnych grup – metoda niweluje znaczenie obserwacji nietypowych,
  • kryterium Warda – odległość pomiędzy grupami jest równa sumie kwadratów odchyleń wszystkich obserwacji od centroidu domniemanej (nowo powstałej) grupy. „Tworzona jest grupa o najmniejszej wariancji. Podejście użyte w kryterium Warda może nieco przypominać to użyte w algorytmie k-średnich, z tą różnicą, że tu jest ono zaimplementowane w algorytmie hierarchicznym.
• dendrogram – hierarchiczne drzewo będące schematem działania algorytmu. Na osi x widnieją poszczególne grupy, na osi y odległość pomiędzy grupami.

Być może po przeczytaniu powyższych definicji ciągle nie masz intuicji na temat różnicy pomiędzy metryką pomiaru a metodą łączenia. Jeśli tak jest, to spróbuj utożsamiać metrykę z jednostką a metodę łączenia grup z podejściem do mierzenia odległości. Nie jest to w 100% trafna analogia, lecz w mojej ocenie pomaga nieco zrozumieć tę relację. 🙂

Schemat budowy modelu grupującego

Algorytmy hierarchiczne w sposób rekursywny łączą grupy, które dzieli najmniejsza odległość określona zgodnie z przyjętą metodą łączenia grup. Jest to dosyć intuicyjne, dlatego proces budowy modelu grupującego możemy sprowadzić do czterech prostych kroków:

1. Wybór podejścia (aglomeracyjne/deglomeracyjne).
2. Wybór miary odległości.
3. Wybór metody łączenia obserwacji.
4. Uruchomienie modelu – policzenie drzewa.

Przykład budowy modelu z użyciem dostępnych w Pythonie bibliotek przedstawię już w kolejnym wpisie. Algorytmy hierarchiczne są zaimplementowane w dwóch popularnych bibliotekach: SciPy i SkLearn. Z tego powodu zademonstruję dwa przykłady budowy modelu. 🙂

Wady i zalety

Algorytmy hierarchiczne nie należą do najpopularniejszych ani do dających najlepsze rezultaty metod grupowania. Mimo to mają kilka zalet, które warto mieć na uwadze, gdy mierzymy się z problemem grupowania.

Z racji dosyć wysokiej złożoności obliczeniowej i pamięciowej algorytmy wykorzystujące grupowanie hierarchiczne należy stosować raczej przy małych zbiorach. Z drugiej strony z racji ich charakterystyki, nie wymagają one wczesniejszej specyfikacji liczby grup (w zależności od biblioteki – sklearn wymaga określenia liczby grup), co szczególnie w przypadku wstępnej analizy zbioru z użyciem grupowanie powinno być odbierane za zaletę. Liczbę grup możemy określić dopiero po np. wnikliwej analizie dendrogramu.

Wady:

• Mało wydajne obliczeniowo (sprawdzają się raczej na małych bazach) – duża złożoność obliczeniowa i pamięciowa.
• Wrażliwe na dobór metody liczenia odległości.
• Wrażliwe na wartości odstające.

Zalety:

• Intuicyjne – dosyć prosta idea działania.
• Proste w interpretacji – rozwiązanie przybiera kształt drzewa i może być prezentowane na dendrogramie.

Podsumowanie

Mam nadzieję, że ten wpis pozwolił Ci lepiej zrozumieć działanie algorytmów hierarchicznego grupowania. Już w kolejnym wpisie przejdę do części praktycznej i pokażę praktyczną implementację tych metod w Pythonie.

Jeśli masz jakieś pytania, to proszę podziel się nimi w komentarzu pod wpisem – zapraszam do dyskusji. Jeśli artykuł przypadł Ci do gustu, to proszę, podziel się nim w mediach społecznościowych ze swoimi znajomymi. Będę bardzo wdzięczny. 🙂

–
Linki:

• Opis grupowania hierarchicznego w sklearn.
• Grupowanie hierarchiczne, aglomeracyjne w sklearn.
• Grupowanie hierarchiczne na Wikipedii.
• Metoda Worda.
• Świetnie opisana idea grupowania hierarchicznego – Stanford University.
• Świetnie opisane metody łączenia grup w grupowaniu hierarchicznym – Victor Lavrenko.

photo: unsplash.com (Edvard Alexander Rølvaag)