Grupowanie w uczeniu maszynowym: 5 kluczowych algorytmów klasteryzacji

Samo grupowanie nie jest jednym konkretnym algorytmem, lecz ogólnym zadaniem do rozwiązania. Możesz osiągnąć cel, korzystając z różnych algorytmów, które znacząco różnią się rozumieniem, czym jest klaster, i tym, jak efektywnie go znaleźć. 

Budowanie intuicji za grupowaniem

Zanim wejdziemy w szczegóły algorytmiczne, zbudujmy intuicję na przykładzie zabawkowego zbioru owoców. Załóżmy, że mamy ogromną kolekcję obrazów z trzema owocami: (i) truskawkami, (ii) gruszkami i (iii) jabłkami. 

W zbiorze wszystkie obrazy są wymieszane, a twoim zadaniem jest pogrupować podobne owoce, tzn. utworzyć trzy grupy, z których każda zawiera jeden rodzaj owocu. Dokładnie to zrobi algorytm klasteryzacji. 

Kluczowe kryteria sukcesu analizy klasteryzacji

Grupowanie, w przeciwieństwie do przypadków użycia uczenia nadzorowanego, takich jak klasyfikacja czy regresja, nie może być w pełni zautomatyzowane end-to-end. To iteracyjny proces odkrywania informacji, który wymaga wiedzy dziedzinowej i osądu człowieka, często wykorzystywanych do wprowadzania korekt w danych i parametrach modelu, by osiągnąć pożądany rezultat. 

Co najważniejsze, ponieważ grupowanie to uczenie bez nadzoru i nie używa danych z etykietami, nie możemy liczyć metryk takich jak accuracy, AUC, RMSE itd., by porównywać różne algorytmy czy techniki przetwarzania danych. W rezultacie ocena wydajności modeli klasteryzacji jest naprawdę trudna i subiektywna. 

Kluczowe kryteria sukcesu modeli klasteryzacji koncentrują się wokół:

• Czy wynik jest interpretowalny?
• Czy wynik grupowania jest użyteczny biznesowo?
• Czy dowiedziałeś się czegoś nowego lub odkryłeś nowe wzorce w danych, o których nie wiedziałeś przed grupowaniem?

Pomiar jakości klastrów

Bez danych z etykietami nie policzysz accuracy ani AUC. Dwie metryki pomagają ilościowo ocenić, jak dobrze twoje klastry są odseparowane. Dwa popularne miary:

• Silhouette Score mierzy, jak bardzo punkt jest podobny do własnego klastra w porównaniu z najbliższym sąsiednim klastrem. Przyjmuje wartości od -1 do 1; wyniki powyżej 0,5 sugerują dobrze odseparowane klastry.
• Indeks Daviesa–Bouldina mierzy średnie podobieństwo każdego klastra do najbardziej podobnego klastra — im niższy, tym lepiej.

Obie metryki są dostępne w scikit-learn: sklearn.metrics.silhouette_score(X, labels) oraz sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means to najczęściej stosowany algorytm do zadań klasteryzacji, głównie dlatego, że kroki są proste, a implementacja w scikit-learn jest nieskomplikowana. To algorytm oparty na centroidach, w którym użytkownik musi zdefiniować wymaganą liczbę klastrów, które chce utworzyć. 

Najczęściej wynika to z przypadku biznesowego lub z testowania różnych wartości liczby klastrów i oceny wyników. 

K-Means to iteracyjny algorytm tworzący nieprzecinające się klastry, co oznacza, że każda instancja w zbiorze może przynależeć wyłącznie do jednego klastra. Najłatwiej zrozumieć K-Means, śledząc kroki wraz z poniższym schematem. Szczegółowy opis znajdziesz też w naszych tutorialach K-Means Clustering w Pythonie oraz K-Means Clustering w R. 

1. Użytkownik określa liczbę klastrów.
2. Inicjalizuje się losowo centroids zgodnie z liczbą klastrów. Na schemacie poniżej, w Iteracji 1, widać trzy centroidy zainicjalizowane losowo w kolorach niebieskim, czerwonym i zielonym.
3. Liczy się odległość między punktami danych a każdym centroidem i przypisuje każdy punkt do najbliższego centroidu.
4. Przelicza się średnią centroidu na podstawie przypisanych punktów, co zmienia położenie centroidu — jak w Iteracjach 2–9 — aż do zbieżności.
5. Iteracje trwają, dopóki średnia centroidu się nie zmienia lub do osiągnięcia parametru max_iter — maksymalnej liczby iteracji zdefiniowanej przez użytkownika podczas treningu. W scikit-learn domyślnie max_iter = 300.

Źródło obrazu: Learnbymarketing.com

2. MeanShift

W odróżnieniu od K-Means, algorytm MeanShift nie wymaga określenia liczby klastrów. Samodzielnie ją wyznacza, co jest wyraźną przewagą nad K-Means, gdy nie wiesz, ile klastrów zawierają twoje dane. 

MeanShift również opiera się na centroidach i iteracyjnie przypisuje punkty do klastrów. Najczęstszym zastosowaniem MeanShift jest segmentacja obrazów.

Algorytm MeanShift bazuje na estymacji gęstości jądrowej. Podobnie jak K-Means, iteracyjnie przesuwa każdy punkt w stronę najbliższego centroidu klastra, które są początkowo inicjalizowane losowo, a każdy punkt jest przesuwany w przestrzeni w kierunku obszaru o największej liczbie punktów, czyli modu (moda to w tym kontekście najwyższa gęstość punktów w regionie). 

Dlatego MeanShift bywa nazywany algorytmem poszukiwania modu. Kroki algorytmu MeanShift są następujące:

• Wybierz losowy punkt i utwórz wokół niego okno.
• Policz średnią wszystkich punktów w tym oknie.
• Przesuń okno, podążając w kierunku modu. 
• Powtarzaj kroki do zbieżności.

Źródło obrazu: ResearchGate

Aby przejść przez MeanShift krok po kroku w praktyce, zobacz nasz tutorial Mean Shift Clustering.

3. DBSCAN

DBSCAN, czyli Density-Based Spatial Clustering of Applications with Noise, to nienadzorowany algorytm klasteryzacji oparty na założeniu, że klastry są gęstymi obszarami rozdzielonymi regionami o niższej gęstości. 

Największą zaletą tego algorytmu względem K-Means i MeanShift jest odporność na wartości odstające — nie przypisuje punktów odstających do żadnego klastra. 

DBSCAN wymaga od użytkownika tylko dwóch parametrów: 

• Promienia okręgu tworzonego wokół każdego punktu danych, znanego jako epsilon

• minPoints, czyli minimalnej liczby punktów wymaganej w tym okręgu, aby punkt uznać za punkt rdzeniowy (Core).

Każdy punkt danych jest otoczony okręgiem o promieniu epsilon, a DBSCAN klasyfikuje je jako punkt rdzeniowy (Core), brzegowy (Border) lub szum (Noise). Punkt uznaje się za rdzeniowy, jeśli okrąg wokół niego zawiera co najmniej liczbę punktów określoną parametrem minPoints. 

Uznaje się go za punkt brzegowy, jeśli liczba punktów jest mniejsza niż wymagana, a za szum — jeśli w promieniu epsilon od dowolnego punktu nie ma dodatkowych punktów. Punkty szumu nie są przypisane do żadnego klastra (to po prostu obserwacje odstające).

Typowe zastosowania DBSCAN to:

• Świetnie rozdziela klastry o wysokiej i niskiej gęstości;
• Dobrze działa na nieliniowych zbiorach danych oraz
• Może służyć do wykrywania anomalii, ponieważ wyodrębnia punkty szumu i nie przypisuje ich do klastrów.

DBSCAN vs K-Means

Porównując DBSCAN z K-Means, najczęstsze różnice to: 

• K-Means grupuje wszystkie instancje w zbiorze, natomiast DBSCAN nie przypisuje punktów szumu (odstających) do żadnego prawidłowego klastra
• K-Means ma trudności z klastrami nieglobalnymi, podczas gdy DBSCAN radzi sobie z tym gładko
• K-Means zakłada, że punkty danych pochodzą z rozkładu Gaussa, podczas gdy DBSCAN nie czyni założeń o danych.

Więcej znajdziesz w naszym przewodniku po algorytmie DBSCAN, który obejmuje strojenie parametrów i przykłady. 

Źródło obrazu: Medium

4. Hierarchical Clustering

Klasteryzacja hierarchiczna to metoda budująca hierarchię klastrów. Wyróżnia się dwa typy. 

• Agregacyjna: podejście oddolne, w którym na początku każdą obserwację traktuje się jako własny klaster, a następnie, idąc z dołu do góry, łączy się obserwacje w pary, a pary w klastry. 
• Dziedzinowa: podejście „z góry na dół”: wszystkie obserwacje startują w jednym klastrze, a podziały są wykonywane rekurencyjnie w miarę przechodzenia z góry na dół.

W analizie danych z sieci społecznościowych klasteryzacja hierarchiczna jest zdecydowanie najczęstszą i najpopularniejszą metodą. Węzły (gałęzie) w grafie porównuje się ze sobą w zależności od stopnia podobieństwa. Łącząc mniejsze, powiązane grupy węzłów, można tworzyć większe zbiory.

Największą zaletą klasteryzacji hierarchicznej jest łatwość zrozumienia i implementacji. Zwykle wynik tej metody analizuje się na obrazie takim jak poniżej — to dendrogram.

Więcej dowiesz się z naszego tutorialu o klasteryzacji hierarchicznej, który pokazuje, jak tworzyć i czytać dendrogramy w Pythonie. 

Źródło obrazu: ResearchGate

5. BIRCH

BIRCH to skrót od Balanced Iterative Hierarchical Based Clustering. Stosuje się go przy bardzo dużych zbiorach danych, gdzie K-Means nie skaluje się praktycznie. Algorytm BIRCH dzieli duże dane na małe klastry i stara się zachować maksymalnie dużo informacji. Zamiast klastrować bezpośrednio duże zbiory, mniejsze grupy są następnie klastrowane do końcowego wyniku. 

BIRCH często uzupełnia inne algorytmy grupowania, tworząc podsumowanie informacji, które te algorytmy mogą wykorzystać. Użytkownicy muszą zdefiniować liczbę klastrów do trenowania BIRCH, podobnie jak w K-Means.

Jedną z korzyści stosowania BIRCH jest możliwość progresywnego i dynamicznego grupowania wielowymiarowych punktów danych. Robi to, by tworzyć klastry najwyższej jakości przy danych ograniczeniach pamięci i czasu. W większości przypadków BIRCH wystarczy jedno przejście po bazie, co czyni go skalowalnym. 

Najczęstszym zastosowaniem BIRCH jest pamięciooszczędna alternatywa dla K-Means, pozwalająca grupować duże zbiory danych, których K-Means nie jest w stanie obsłużyć z powodu ograniczeń pamięci lub mocy obliczeniowej.

Zastosowania biznesowe grupowania

Grupowanie ma szerokie zastosowania w branżach: media, opieka zdrowotna, produkcja, handel detaliczny — wszędzie tam, gdzie masz duże ilości nieopisanych danych. Oto kilka praktycznych przykładów.

Segmentacja klientów

Klientów kategoryzuje się za pomocą algorytmów grupowania według zachowań zakupowych lub zainteresowań, aby tworzyć ukierunkowane kampanie marketingowe. 

Wyobraź sobie, że masz 10 mln klientów i chcesz opracować spersonalizowane kampanie. Mało prawdopodobne, że stworzysz 10 mln różnych kampanii, więc co robimy? Możemy użyć grupowania, by podzielić 10 mln klientów na 25 klastrów, a następnie zaprojektować 25 kampanii zamiast 10 mln.

Źródło obrazu: Medium

Grupowanie w handlu detalicznym

W handlu detalicznym jest wiele możliwości wykorzystania grupowania. Na przykład możesz zebrać dane o każdym sklepie i grupować na poziomie sklepu, by uzyskać wgląd w to, które lokalizacje są do siebie podobne pod względem takich atrybutów jak ruch, średnia sprzedaż sklepu, liczba SKU itd. 

Inny przykład to grupowanie na poziomie kategorii. Na diagramie poniżej mamy osiem sklepów. Różne kolory reprezentują różne klastry. W tym przykładzie są cztery klastry. 

Zauważ, że kategoria dezodorantów w Sklepie 1 należy do czerwonego klastra, a w Sklepie 2 do niebieskiego. Oznacza to, że Sklep 1 i Sklep 2 mają zupełnie inne rynki docelowe dla kategorii dezodorantów.

Źródło obrazu: dotactiv.com

Grupowanie w opiece klinicznej / zarządzaniu chorobą

Opieka zdrowotna i nauki kliniczne oferują szczególnie mocne zastosowania grupowania. Przykładem są badania Komaru & Yoshida i in. 2020, gdzie zebrano dane demograficzne i laboratoryjne dla 101 pacjentów, a następnie podzielono ich na 3 klastry. 

Każdy klaster reprezentował inne warunki. Na przykład klaster 1 obejmuje pacjentów z niskim WBC i CRP. Klaster 2 — pacjentów z wysokim BMP i surowicą, a Klaster 3 — pacjentów z niską surowicą. Każdy klaster reprezentuje inną trajektorię przeżycia, biorąc pod uwagę śmiertelność roczną po hemodializie.

Źródło obrazu: elsevierhealth.com

Segmentacja obrazu

Segmentacja obrazu to klasyfikacja obrazu na różne grupy. Przeprowadzono wiele badań nad segmentacją obrazu z użyciem grupowania. Ten rodzaj klasteryzacji jest przydatny, gdy chcesz wyodrębnić obiekty na obrazie, by analizować każdy obiekt osobno i sprawdzić, czym jest. 

W przykładzie poniżej po lewej jest oryginalny obraz, a po prawej wynik algorytmu grupowania. Wyraźnie widać 4 klastry, czyli 4 różne obiekty na obrazie określone na podstawie pikseli (tygrys, trawa, woda i piasek).

Porównanie algorytmów klasteryzacji

W scikit-learn, popularnej bibliotece uczenia maszynowego w Pythonie, zaimplementowano 10 algorytmów klasteryzacji bez nadzoru. Każdy z nich fundamentalnie inaczej wyznacza i przypisuje klastry w zbiorze danych. 

Różnice w ich podstawach matematycznych sprowadzają się do czterech aspektów, pod kątem których można je porównać:

• Parametry wymagane przez model 
• Skalowalność 
• Przypadki użycia 
• Geometria, tzn. metryka używana do obliczania odległości. 

Na diagramie poniżej każda kolumna przedstawia wynik innego algorytmu klasteryzacji, np. K-Means, Affinity Propagation, MeanShift itd. Łącznie jest 10 algorytmów wytrenowanych na tym samym zbiorze.

Niektóre algorytmy dały taki sam wynik. Zauważ, że Agglomerative Clustering, DBSCAN, OPTICS i Spectral Clustering uzyskały te same klastry. 

Jeśli jednak porównasz wynik K-Means z wynikiem MeanShift, zobaczysz, że oba algorytmy dały różne rezultaty. W K-Means są tylko dwie grupy (niebieska i pomarańczowa), podczas gdy w MeanShift są trzy — niebieska, zielona i pomarańczowa. 

Źródło obrazu: scikit-learn

Niestety (albo i na szczęście) w grupowaniu nie ma odpowiedzi „dobrze/źle”. Byłoby prosto stwierdzić: „Algorytm X działa tu najlepiej”. 

To nie jest możliwe — i właśnie dlatego grupowanie jest tak wymagającym zadaniem. 

Ostatecznie to, który algorytm sprawdzi się lepiej, nie zależy od łatwo mierzalnej metryki, ale od interpretacji i użyteczności wyniku dla danego przypadku.

Jak wybrać właściwy algorytm klasteryzacji

Każdy algorytm pasuje do innych warunków danych. Potraktuj tę tabelę jako punkt wyjścia, a potem przetestuj co najmniej dwa na swoich danych, zanim podejmiesz decyzję.

Praktyczny start: zacznij od K-Means dla szybkości, przełącz się na DBSCAN, jeśli twoje dane mają nieregularne kształty lub wartości odstające, a klasteryzację hierarchiczną wykorzystaj, gdy chcesz wizualnie eksplorować strukturę klastrów przez dendrogram, zanim wybierzesz k.

Final thoughts

Grupowanie trudniej zastosować niż techniki nadzorowane, takie jak klasyfikacja i regresja, z dwóch powodów: nie da się mierzyć wydajności względem etykiet docelowych, a parametry, takie jak liczba klastrów, wymagają osądu dziedzinowego zamiast algorytmicznego doboru. 

Grupowanie to cenna umiejętność w wielu rolach: data scientists, inżynierowie ML i analitycy często napotykają problemy, które grupowanie potrafi rozwiązać. 

Jeśli chcesz dowiedzieć się więcej o grupowaniu i uczeniu bez nadzoru oraz o implementacji w językach Python i R, poniższe kursy pomogą ci zrobić postępy: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R