Czym jest Grupowanie metodą k-średnich (K-means clustering)?
Grupowanie metodą k-średnich należy do najpopularniejszych technik nienadzorowanego uczenia maszynowego. Algorytm dzieli zbiór obserwacji na k nieprzecinających się klastrów, minimalizując sumę kwadratów odległości punktów od centrów tych klastrów. W praktyce oznacza to, że obiekty znajdujące się blisko siebie w przestrzeni cech trafiają do tej samej grupy, zaś obiekty odległe stają się reprezentantami odrębnych klastrów.
Krótki rys historyczny
Podstawy metody opracował Sewall Wright w latach czterdziestych XX w. w kontekście genetyki populacyjnej, jednak formalną, komputerowo wykonalną postać nadał jej w 1957 r. Stuart Lloyd, inżynier w Bell Labs, projektując algorytm kwantyzacji sygnału. Powszechne uznanie naukowe przyszło wraz z publikacją Jamesa MacQueena z 1967 r., która wprowadziła nazwę „k-means”. Od tamtej pory metoda stała się filarem eksploracji danych i statystyki.
Jak dokładnie działa Grupowanie metodą k-średnich (K-means clustering)
Proces rozpoczyna się od losowego lub heurystycznego wybrania k początkowych centrów. Następnie każdy punkt danych zostaje przypisany do najbliższego centrum obliczanego najczęściej w metryce euklidesowej. Po zakończeniu fazy przypisywania algorytm wyznacza nowe położenia centrów jako średnie arytmetyczne punktów znajdujących się w danym klastrze. Dwie opisane fazy – przypisywanie i aktualizacja – są powtarzane aż do osiągnięcia stabilizacji, czyli braku zmian przynależności punktów lub minimalnej redukcji zmienności wewnątrz klastrów. Optymalizacja odnosi sukces, gdy suma kwadratów odległości punktów od odpowiadających im centrów przestaje maleć.
Przykładowe zastosowanie krok po kroku
Wyobraźmy sobie hurtownię internetową analizującą dobowe zachowania zakupowe klientów. Po standaryzacji zmiennych, takich jak wartość koszyka, liczba odwiedzin i częstotliwość zakupów, algorytm k-średnich może podzielić użytkowników na segmenty. Jedna grupa może obejmować okazjonalnych nabywców o małej wartości koszyka, inna lojalnych klientów realizujących częste zakupy, co pozwoli działowi marketingu tworzyć precyzyjne kampanie.
Zastosowania w praktyce
K-means sprawdza się w segmentacji rynku, kompresji obrazów, detekcji anomalii sieciowych oraz biologii obliczeniowej, gdzie pomaga wyróżniać typy komórek na podstawie ekspresji genów. W przetwarzaniu obrazu algorytm umożliwia redukcję liczby kolorów bez wyraźnej utraty jakości poprzez przypisanie pikseli do klastrów barw, co ułatwia kompresję.
Zalety i ograniczenia
Najważniejszą zaletą k-średnich jest skalowalność. Metoda charakteryzuje się liniową złożonością obliczeniową względem liczby punktów, co sprawia, że nadaje się do bardzo dużych zbiorów danych. Algorytm jest intuicyjny, łatwy do implementacji i – w przeciwieństwie do rozwiązań hierarchicznych – ma niewielkie zapotrzebowanie na pamięć. Z drugiej strony k-średnich zakłada kulisty kształt klastrów i zbliżone rozmiary grup. Wymaga również z góry określonej liczby klastrów, a wynik bywa wrażliwy na wybór punktów startowych oraz obecność odstających obserwacji.
Na co uważać?
Przed zastosowaniem warto znormalizować dane, aby uniknąć dominacji cech o dużej skali. Dobór liczby klastrów można wspomóc metodą łokcia, współczynnikiem sylwetki lub informacjami dziedzinowymi. W przypadku danych zawierających wartości odstające rozsądnym krokiem jest ich wcześniejsze odfiltrowanie lub zastosowanie wariantu k-medoids odpornego na ekstremalne obserwacje. Jeżeli zależy nam na wykrywaniu nieregularnych, nieliniowych struktur, lepiej sprawdzić algorytmy gęstościowe, takie jak DBSCAN, które nie opierają się na minimalizacji odległości od centrum.
Dodatkowe źródła
Pełniejszy opis historycznego artykułu MacQueena można znaleźć w repozytorium Project Euclid. Zwięzłe wprowadzenie oferuje także hasło Wikipedia. Osobom poszukującym szczegółów matematycznych polecamy przystępny przewodnik w publikacji „Data Clustering: Algorithms and Applications” dostępnej na arXiv. Dla praktyków przydatny może być rozdział o k-średnich w darmowym podręczniku „Introduction to Statistical Learning”, którego pełny tekst znajduje się na stronie statlearning.com.
