05 · Bez nadzoru · 4 min czytania · Interaktywne · aktualizacja
Dlaczego k-średnich daje złe klastry i jak tego uniknąć?
W skrócie
K-średnich zawsze zwróci k grup, nawet bez sensu. Psują go skale cech, złe ziarno startowe, wydłużone i nierówne skupiska oraz źle dobrane k.
Co to jest
Pułapki k-średnich to typowe sytuacje, w których algorytm działa poprawnie technicznie, a mimo to zwraca podział bez sensu. K-średnich zawsze odda dokładnie k grup — także wtedy, gdy w danych nie ma żadnych skupisk albo gdy mają one kształt, którego metoda nie potrafi opisać. Brak komunikatu o błędzie nie oznacza, że wynik jest dobry.
Większość pułapek wynika z jednego zdania: k-średnich minimalizuje sumę kwadratów odległości euklidesowych punktów od najbliższego środka. Z tego kryterium wynikają jego ukryte założenia — i miejsca, w których się wykłada.
Mechanizm — dlaczego tak działa
Skala cech. Odległość euklidesowa sumuje kwadraty różnic po kolumnach. Kolumna o wariancji tysiąc razy większej dominuje całą sumę, a pozostałe stają się szumem. Algorytm nie wie, że gramy i milimetry to różne jednostki — dla niego to po prostu liczby.
Kształt i wielkość skupisk. Przypisanie do najbliższego środka dzieli przestrzeń na komórki Woronoja, czyli wielokąty o prostych granicach w połowie drogi między środkami. To działa, gdy grupy są mniej więcej kuliste i podobnej wielkości. Grupy wydłużone, zagięte (półksiężyce, pierścienie) albo bardzo różnej liczności zostaną pocięte prostymi liniami. Dodatkowo kryterium premiuje przesuwanie granicy w stronę dużej grupy, bo „podkradanie” jej brzegowych punktów obniża sumę kwadratów.
Minima lokalne. Algorytm Lloyda na przemian przypisuje punkty do środków i przelicza środki. Każdy krok nie pogarsza kryterium, więc proces zawsze się zatrzymuje — ale w najbliższym minimum lokalnym, niekoniecznie globalnym. Dwa środki mogą utknąć w jednym skupisku, zostawiając inne bez reprezentanta. Dlatego stosuje się mądre losowanie startu (k-means++) i wiele restartów.
Wybór k. Inercja (suma kwadratów) maleje monotonicznie z k — przy k równym liczbie punktów spada do zera. „Łokieć” na wykresie bywa niewidoczny, a współczynnik sylwetki potrafi wskazać mniej grup, niż jest ich merytorycznie. Nie istnieje liczba k wynikająca z samych danych bez decyzji, co ma znaczyć „grupa”.
Kryterium to nie prawda. Nawet globalne minimum inercji jest tylko najlepszym podziałem według sumy kwadratów. Jeśli grupy różnią się kształtem kowariancji, lepszy podział może mieć wyższą inercję.
Na przykładzie
Pingwiny z Palmer Archipelago: 342 osobniki, cztery pomiary, trzy gatunki (151 Adeli, 123 Gentoo, 68 maskowych). Na surowych danych k-średnich z k = 3 osiąga zgodność z gatunkami ARI = 0,33, bo masa ciała (odchylenie ok. 801 g) przygniata pozostałe cechy. Po standaryzacji: 0,79. Jedna linijka StandardScaler więcej niż podwaja jakość.
Teraz start. Uruchomiliśmy k-średnich 50 razy z losowym startem i jednym przebiegiem (n_init=1). W 14 przebiegach (28%) algorytm utknął w minimum lokalnym z inercją 486,3 zamiast 379,4, a ARI spadło do 0,51. Co ciekawe, przebiegi z nieco gorszą inercją 381,1 dawały ARI 0,91 — wyższe niż przy najlepszym minimum. Kryterium i „prawdziwe” gatunki nie są tym samym: grupa maskowa jest mała, więc k-średnich dokłada do niej 24 pingwiny Adeli. Mieszanina gaussowska z pełną kowariancją na tych samych danych osiąga ARI 0,96. Wreszcie k: sylwetka jest najwyższa dla k = 2 (0,53), a nie dla k = 3 (0,45). Na sztucznych półksiężycach (400 punktów) k-średnich osiąga ARI 0,27, a DBSCAN 1,00.
Dane: Palmer Penguins (pingwiny z Antarktydy)
W praktyce
- Zawsze skaluj:
make_pipeline(StandardScaler(), KMeans(...)). Przy cechach skośnych rozważ wcześniej logarytm. - Zostaw
init="k-means++"i kilka restartów (n_init=10); porównajinertia_między ziarnami. - Liczbę grup wybieraj kilkoma narzędziami: inercja,
silhouette_score, BIC zGaussianMixture, i sprawdź wynik merytorycznie. - Gdy grupy są wydłużone lub różnej wielkości, użyj
GaussianMixture; gdy mają dowolny kształt i jest szum —DBSCAN. - Wartości odstające ciągną środki; usuń je wcześniej lub użyj odpornej alternatywy (k-medoidów).
- Nie interpretuj grup bez sprawdzenia stabilności: inne ziarno, podpróbka, inny zestaw cech.
Najczęstsze pytania
- Dlaczego za każdym uruchomieniem dostaję inne klastry?
- Bo start jest losowy, a algorytm zbiega do najbliższego minimum lokalnego. Ustaw `random_state` dla powtarzalności i `n_init` większe niż 1, żeby wybrać najlepszy z kilku przebiegów. Jeśli wyniki nadal mocno się różnią, struktura w danych jest słaba.
- Jak wybrać k w k-średnich?
- Nie ma jednej metody. Łokieć inercji, współczynnik sylwetki i BIC mieszaniny gaussowskiej często wskazują różne wartości. Ostateczny wybór zależy od celu: ile grup da się sensownie opisać i wykorzystać.
- Czy k-średnich działa na danych kategorycznych?
- Nie bezpośrednio — średnia kategorii nie ma sensu, a kodowanie one-hot zniekształca odległości. Dla danych kategorycznych stosuje się k-mody albo metody oparte na innej mierze niepodobieństwa, np. klasteryzację hierarchiczną z odległością Gowera.
Źródła
- Lloyd S. P., „Least squares quantization in PCM”, IEEE Transactions on Information Theory 28(2), 1982.
- Arthur D., Vassilvitskii S., „k-means++: The Advantages of Careful Seeding”, Proceedings of SODA 2007.
- James G., Witten D., Hastie T., Tibshirani R., „An Introduction to Statistical Learning”, 2nd ed., Springer 2021, rozdz. 12.4.
- Rousseeuw P. J., „Silhouettes: a graphical aid to the interpretation and validation of cluster analysis”, Journal of Computational and Applied Mathematics 20, 1987.
- Dokumentacja scikit-learn, „Clustering — K-means”: https://scikit-learn.org/stable/modules/clustering.html#k-means