Klasteryzacja Danych: K-means, GMM i DBSCAN

Klasteryzacja to fundamentalna technika uczenia nienadzorowanego, wykorzystywana w eksploracyjnej analizie danych oraz systemach uczenia maszynowego. Jej głównym celem jest automatyczny podział nieoznakowanych zbiorów danych na spójne podgrupy, tak aby elementy wewnątrz pojedynczego klastra wykazywały maksymalne podobieństwo, a obiekty z różnych grup znacząco się od siebie różniły. Wybór odpowiedniej metody grupowania zależy ściśle od topologii przestrzeni wejściowej, rozkładu statystycznego cech oraz wymagań analitycznych, co wymusza stosowanie odmiennych paradygmatów badawczych. W tym artykule przeanalizujemy od strony technicznej i matematycznej trzy wiodące architektury rozwiązujące ten problem: K-means oparty na optymalizacji metryki, probabilistyczne modele mieszanek Gaussowskich (GMM) oraz topologiczny algorytm analizy gęstości DBSCAN.

K-means: Optymalizacja funkcji sumy kwadratów odległości

Algorytm K-means jest oparty na geometrycznym podejściu do partycjonowania przestrzeni. Wykorzystuje on strategię twardego przypisywania (ang. hard clustering), co oznacza, że każdy punkt wejściowy zostaje jednoznacznie powiązany z dokładnie jednym klastrem. Działanie algorytmu można traktować jako problem optymalizacyjny, w którym minimalizowana jest wariancja wewnątrzklastrowa. W ujęciu matematycznym sprowadza się to do minimalizacji funkcji kosztu nazywanej sumą kwadratów błędów (SSE – Sum of Squared Errors).

Funkcja kosztu (często oznaczana jako J) jest definiowana następująco:

J = \sum_{i=1}^{k} \sum_{x \in C_i} ||x – \mu_i||^2

W powyższym równaniu wartość „k” to z góry określona liczba klastrów, „C_i” oznacza zbiór obserwacji przypisanych do i-tego klastra, a „μ_i” to centroid (wektor średnich wartości cech) tego klastra. Optymalizacja globalna tej funkcji należy do klasy problemów NP-trudnych. Z tego powodu w praktyce inżynierskiej standardem jest wykorzystywanie heurystycznego algorytmu Lloyda, który skutecznie i szybko znajduje minimum lokalne funkcji.

Wyprowadzenie i struktura algorytmu Lloyda bazują na naprzemiennej aktualizacji parametrów w iteracyjnej pętli:

• Krok inicjalizacji: Algorytm rozpoczyna działanie od wybrania początkowych pozycji centroidów. W klasycznym podejściu „k” punktów jest losowanych równomiernie z dostępnej przestrzeni lub wybieranych z istniejących obserwacji.
• Krok przypisania (odpowiednik fazy Expectation): Przy zamrożonych położeniach centroidów, funkcja jest optymalizowana względem przypisań punktów. Każda obserwacja jest alokowana do klastra, którego centroid znajduje się najbliżej niej, najczęściej z wykorzystaniem metryki euklidesowej. Przestrzeń ulega podziałowi tworząc tzw. diagramy Woronoja.
• Krok aktualizacji (odpowiednik fazy Maximization): Przy zablokowanych przypisaniach punktów, algorytm rekalibruje pozycje centroidów, minimalizując funkcję J. Różniczkując sumę kwadratów odległości względem położenia centroidu i przyrównując wynik do zera, dowodzi się matematycznie, że optymalnym nowym położeniem centroidu jest dokładna średnia arytmetyczna wszystkich punktów wchodzących w skład danej grupy.

Proces ten rekurencyjnie powtarza kroki przypisania i aktualizacji aż do osiągnięcia momentu zbieżności – gdy żadna obserwacja nie zmienia już swojego klastra. Głównym założeniem algorytmu K-means jest to, że klastry w danych mają kształt wypukły i sferyczny oraz zbliżoną wariancję. Kiedy te warunki nie są spełnione, K-means może błędnie modelować granice decyzyjne.

Modele Mieszanek Gaussowskich (GMM) i Algorytm EM

W przeciwieństwie do geometrycznego algorytmu K-means, Modele Mieszanek Gaussowskich wprowadzają całkowicie probabilistyczną architekturę i łagodzą założenie o sztywnym przypisaniu. GMM zakłada, że cały zbiór danych jest generowany przez ukrytą mieszaninę skończonej liczby „k” wielowymiarowych rozkładów normalnych (Gaussa). Zamiast zero-jedynkowego wyboru klastra, GMM stosuje tzw. miękkie grupowanie (ang. soft clustering), zwracając rozkład prawdopodobieństwa przynależności dla każdej z badanych próbek.

Pojedynczy komponent GMM w przestrzeni jest definiowany przez trzy niezależne zestawy parametrów: wektor średnich (\mu), który wskazuje geometryczny środek klastra; macierz kowariancji (\Sigma), która modeluje jego kształt, orientację oraz szerokość (pozwalając na obsługę klastrów eliptycznych rozciągniętych wzdłuż dowolnych osi); oraz współczynnik mieszania (\pi), oznaczający a priori wagę i wielkość populacji danego klastra w całym zbiorze.

Dopasowanie parametrów GMM wymaga maksymalizacji funkcji wiarygodności (MLE). Bezpośrednie obliczenia są w tym przypadku niemożliwe analitycznie przez wzgląd na istnienie zmiennych ukrytych (nie wiemy z góry, z jakiego komponentu pochodzi dana obserwacja). Aby rozwiązać ten problem, stosuje się algorytm EM (Expectation-Maximization), który iteracyjnie aproksymuje optymalne parametry:

• Krok E (Expectation): Korzystając z bieżących estymatorów parametrów układu, algorytm ewaluuje tzw. odpowiedzialności (ang. responsibilities). Za pomocą twierdzenia Bayesa oblicza się dla każdego punktu w przestrzeni prawdopodobieństwo a posteriori mówiące o tym, że punkt x_i został wygenerowany przez j-ty rozkład Gaussa.
• Krok M (Maximization): Wykorzystując wyliczone odpowiedzialności w charakterze wag statystycznych, algorytm przelicza na nowo parametry każdego komponentu mieszanki. Średnia staje się średnią ważoną wszystkich punktów. Macierz kowariancji jest aktualizowana na podstawie wariancji ważonej ułamkowym udziałem obserwacji w danym klastrze. Współczynniki mieszania zostają uśrednione z wartości odpowiedzialności.

Algorytm powtarza na przemian krok E oraz M, do momentu w którym przyrost logarytmu funkcji wiarygodności jest mniejszy od zadanej tolerancji. Główną zaletą metody GMM jest elastyczność i możliwość uchwycenia skomplikowanych kowariancji pomiędzy cechami, z którymi standardowy K-means nie jest w stanie sobie poradzić.

DBSCAN: Gęstościowa metoda wykrywania nieregularnych klastrów

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) fundamentalnie różni się od podejść opartych na odległości do centroidu czy modelowaniu statystycznym. Jego działanie opiera się na założeniu, że w dobrze pogrupowanych danych klastry to spójne topologicznie obszary o wysokiej gęstości przestrzennej, które są rozdzielone rejonami o relatywnie niskim zagęszczeniu punktów. To unikalne podejście pozwala algorytmowi skutecznie identyfikować klastry o skomplikowanych, wysoce nieregularnych i wklęsłych kształtach.

Architektura algorytmu wymaga dostarczenia dwóch kluczowych parametrów wejściowych:

• Epsilon (\varepsilon): Promień sąsiedztwa. Określa on fizyczną odległość (liczoną w wybranej metryce np. euklidesowej), definiującą lokalne środowisko badanego punktu.
• minPts (Minimum Points): Minimalna liczebność obserwacji potrzebna do uznania lokalnego obszaru za zwarty zbiór i zakwalifikowania badanego punktu jako punkt centralny.

Na podstawie tych parametrów algorytm DBSCAN klasyfikuje punkty w zbiorze danych na trzy niezależne kategorie. Jeżeli w promieniu „epsilon” wybranego punktu znajduje się co najmniej „minPts” innych punktów (włączając badany), staje się on punktem centralnym (core point). Inicjuje on nowy lub poszerza aktualny klaster. Jeśli punkt znajduje się w odległości epsilon od punktu centralnego, ale w jego własnym promieniu brakuje wymaganej liczby minPts, staje się punktem brzegowym (border point). Z kolei wszystkie te obserwacje, które nie leżą w zasięgu ani jednego punktu centralnego i są odizolowane, klasyfikuje się jako punkty szumu lub anomalie (outliers).

Wdrażanie DBSCAN w środowiskach produkcyjnych wymaga świadomego wyboru parametrów. Wartość epsilon najczęściej dobiera się przy pomocy heurystycznej metody k-distance, w której oblicza się odległości każdego punktu do jego k-tego sąsiada, a na wykresie posortowanych dystansów wyszukuje się punkt przegięcia („łokieć”). Mechanika polegająca na budowie klastrów w oparciu o łączność gęstościową czyni algorytm wysoce odpornym na zaburzenia oraz niewymagającym a priori informacji o docelowej liczbie poszukiwanych grup.

Porównanie właściwości algorytmów

W poniższej tabeli podsumowano najważniejsze różnice w architekturze omawianych modeli, co ułatwia inżynierski dobór odpowiedniego algorytmu do przetwarzanego zbioru danych.

Praktyczne zastosowania w analizie danych

Zrozumienie mechaniki powyższych algorytmów otwiera drogę do projektowania wysokowydajnych rozwiązań analitycznych i optymalizacyjnych w systemach Data Science. Zastosowanie odpowiedniego narzędzia determinuje efektywność operacyjną całego rurociągu danych.

Algorytm K-means sprawdza się doskonale w zadaniach wielowymiarowej optymalizacji o ustalonej z góry liczbie stanów wyjściowych. Klasycznym i najczęściej wdrażanym przemysłowo przykładem jest kwantyzacja wektorowa wykorzystywana podczas kompresji obrazów i filmów. Redukcja palety kolorów do „k” najbardziej optymalnych barw następuje właśnie poprzez wyznaczenie centroidów kolorystycznych minimalizujących błędy wizualne. K-means jest również chętnie wdrażany na pierwszej linii segmentacji klientów, kiedy model biznesowy zakłada sztywny podział klientów na kategoryczne przedziały zachowań.

Dzięki swojej wielowymiarowej gęstościowej reprezentacji, algorytm GMM stanowi standard branżowy w przetwarzaniu skomplikowanych danych sensorycznych oraz cyfrowym przetwarzaniu sygnałów. Systemy rozpoznawania mowy (takie jak izolacja poszczególnych fonemów z ciągłej mowy) wykorzystują modele mieszanin do opisywania akustycznej wariancji wymowy. Ponadto zaawansowana analityka bezpieczeństwa sieci z sukcesem integruje mechanizmy miękkiego przypisywania GMM jako niezawodny system detekcji anomalii serwerowych, poszukując ruchów o mikroskopijnym prawdopodobieństwie wystąpienia.

DBSCAN odgrywa kluczową rolę w środowiskach topologicznych i systemach informacji geograficznej (GIS), gdzie dane cechują się dużą zaszumioną przestrzenią. Analityka logistyczna, analizująca strumienie danych z odbiorników GPS floty pojazdów używa DBSCAN do izolowania ważnych zagęszczeń punktów (np. stałe przystanki, węzły dystrybucyjne), odrzucając naturalny szum błędu satelitarnego. Algorytm jest także filarem nowoczesnych modułów antyfraudowych we flagowych produktach ubezpieczeniowych, gdzie gęste układy parametrów reprezentują typowe, bezpieczne zachowania ubezpieczonych, natomiast odseparowane geograficznie i parametrycznie instancje identyfikowane są jako potencjalne wymuszenia, niezależnie od ogólnej wariancji systemu.

Źródła

• EM algorithm and GMM model – Wikipedia
• Modele mieszanin Gaussowskich – Wikipedia
• DBSCAN – Baza wiedzy Data Science
• Grupowanie gęstościowe. Algorytm DBSCAN – teoria – Mateusz Grzyb
• Grupowanie — Data Science – Przegląd Zagadnień (K-Means)
• Алгоритмы кластеризации: k-средних (Suma kwadratów wewnątrzklastrowych)
• Klasteryzacja: K-Means, Expectation Maximization – Politechnika Wrocławska
• Choosing eps and minpts for DBSCAN – Stack Overflow