05 · Bez nadzoru · 4 min czytania · Interaktywne · aktualizacja
Jak działa k-means i skąd wiedzieć, czy znalezione klastry są prawdziwe?
W skrócie
K-means dzieli punkty na k grup: każdy punkt trafia do najbliższego środka, a środki przesuwają się do średniej swojej grupy. Zwraca k grup, nawet gdy ich brak.
Co to jest
K-means to algorytm klastrowania (uczenia bez nadzoru), który dzieli zbiór punktów na k grup tak, by suma kwadratów odległości punktów od środków ich grup była jak najmniejsza. Działa naprzemiennie: przypisz każdy punkt do najbliższego środka, potem przesuń każdy środek do średniej przypisanych punktów (algorytm Lloyda).
Używa się go do segmentacji, kompresji (kwantyzacji wektorowej), inżynierii cech i jako składnika większych systemów. Liczbę grup k trzeba podać z góry.
Mechanizm — dlaczego tak działa
Cel to minimalizacja inercji J = Σ ‖xᵢ − μ_c(i)‖², czyli sumy kwadratów odległości punktów od środków ich klastrów. Żaden z dwóch kroków nie może jej zwiększyć: przy ustalonych środkach przypisanie do najbliższego daje najmniejszy składnik, a przy ustalonych przypisaniach średnia minimalizuje sumę kwadratów odległości — to własność średniej arytmetycznej, od której algorytm wziął nazwę. Ponieważ J nie rośnie, a możliwych przypisań jest skończenie wiele, algorytm zbiega w skończonej liczbie kroków.
Zbiega jednak do minimum lokalnego, więc wynik zależy od startu. Dlatego uruchamia się go wielokrotnie i bierze najmniejsze J, a inicjalizacja k-means++ (Arthur i Vassilvitskii 2007) losuje środki daleko od siebie, co daje gwarancję wyniku nie gorszego niż O(log k) razy optimum w oczekiwaniu.
Własność, która myli: k-means zawsze zwróci k grup. Jednorodną chmurę punktów bez żadnej struktury pokroi na k mniej więcej równych kafelków (komórek Voronoia). Algorytm nie testuje hipotezy „czy klastry istnieją” — trzeba to sprawdzić osobno, np. miarą silhouette, porównaniem z danymi losowymi (gap statistic) albo stabilnością podziału na podpróbkach.
Odległość euklidesowa sumuje kwadraty różnic po cechach, więc cecha o dużym zakresie liczbowym decyduje o wszystkim. Bez standaryzacji k-means klastruje w praktyce tylko po niej.
Zastrzeżenie: k-means zakłada klastry kuliste, o podobnej wielkości i rozrzucie. Wydłużone, zagnieżdżone lub różnej gęstości grupy wymagają innych metod: mieszanin gaussowskich, DBSCAN, klastrowania hierarchicznego.
Na przykładzie
Palmer Penguins: 342 pingwiny z kompletem czterech pomiarów (długość i głębokość dzioba w mm, długość płetwy w mm, masa w gramach), trzy gatunki — 151 Adelie, 123 Gentoo, 68 Chinstrap. Gatunku nie podajemy algorytmowi, używamy go tylko do oceny. KMeans(n_clusters=3, n_init=10, random_state=0) na surowych danych dał zgodność z gatunkami ARI (skorygowany indeks Randa) 0,33: masa ciała ma odchylenie około 800 g, a głębokość dzioba około 2 mm, więc podział szedł prawie tylko po masie.
Po standaryzacji (StandardScaler) ARI wzrosło do 0,79. Wszystkie 123 pingwiny Gentoo trafiły do jednego klastra; 127 z 151 Adelie do drugiego, a 63 z 68 Chinstrap do trzeciego, razem z 24 Adelie. Silhouette tego podziału wynosi 0,45, podczas gdy dla 333 punktów z jednorodnej chmury losowej w czterech wymiarach — około 0,2 przy każdym k od 2 do 4.
Dane: Palmer Penguins (pingwiny z Antarktydy)
W praktyce
- scikit-learn:
KMeans(n_clusters=..., init="k-means++", n_init="auto", random_state=0)— domyślne k = 8 jest arbitralne, zawsze ustaw własne.inertia_to J,silhouette_scoredo oceny. - Standaryzuj cechy (
StandardScaler) przed klastrowaniem; zmienne kategoryczne zakoduj albo użyj metod dla danych mieszanych (k-prototypes). - Wybór k: szczyt silhouette, „łokieć” inercji, gap statistic — żadna metoda nie rozstrzyga, wszystkie są wskazówką.
- Dla dużych zbiorów
MiniBatchKMeansliczy środki na próbkach i jest wielokrotnie szybszy. - Numer klastra lub odległości do środków bywają przydatną cechą dla innych modeli, jeśli klastry pokrywają się ze strukturą etykiet.
- Typowy błąd: interpretowanie k klastrów jako „odkrytych segmentów” bez sprawdzenia, czy struktura różni się od losowego podziału.
Najczęstsze pytania
- Jak wybrać liczbę klastrów k?
- Policz silhouette dla k od 2 do kilkunastu, porównaj z łokciem inercji i wiedzą o danych. Jeśli silhouette jest niskie dla każdego k (poniżej ok. 0,25), dane prawdopodobnie nie mają wyraźnych grup i k-means tnie jednolitą chmurę.
- Dlaczego k-means daje różne wyniki za każdym razem?
- Bo zbiega do minimum lokalnego zależnego od losowych środków startowych. scikit-learn uruchamia algorytm kilka razy (`n_init`) i zwraca najlepszy wynik, a k-means++ zmniejsza rozrzut. Ustaw `random_state` dla powtarzalności i sprawdź stabilność przypisań.
- Czy k-means potrzebuje standaryzacji danych?
- Tak, jeśli cechy mają różne jednostki. Na pingwinach standaryzacja podniosła zgodność z gatunkami z 0,33 do 0,79 ARI. Jeśli niektóre cechy mają być ważniejsze, przeskaluj je świadomie, a nie przez przypadek jednostek.
Źródła
- Lloyd, S. P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28(2), 129–137.
- Arthur, D., Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". SODA, 1027–1035.
- Hastie, T., Tibshirani, R., Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed., Springer, rozdz. 14.3.6 "K-means".
- Bishop, C. M. (2006). Pattern Recognition and Machine Learning, Springer, rozdz. 9.1 "K-means clustering".
- Horst, A. M., Hill, A. P., Gorman, K. B. (2020). palmerpenguins: Palmer Archipelago (Antarctica) penguin data. R package. https://allisonhorst.github.io/palmerpenguins/