Grupowanie k-średnich — algorytm i jak działa

Grupowanie k-średnich to sposób dzielenia danych liczbowych na $k$ klastrów. Jeśli wybierzesz $k$ i użyjesz standardowej wersji euklidesowej, algorytm powtarza jedną pętlę: przypisuje każdy punkt do najbliższego środka, a potem przesuwa każdy środek do średniej punktów do niego przypisanych.

Mówiąc prosto, próbuje sprawić, by punkty w tej samej grupie były blisko siebie, a punkty w różnych grupach były bardziej oddalone. Jest szybki i użyteczny, ale działa dobrze tylko wtedy, gdy te „grupy” są w miarę zwarte, a odległość ma sens.

Co optymalizuje grupowanie k-średnich

W standardowej postaci euklidesowej k-średnich stara się, aby punkty wewnątrz każdego klastra były jak najbliżej centroidu tego klastra. Często używaną funkcją celu jest

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Tutaj $C_j$ to $j$-ty klaster, a $\mu_j$ to jego centroid.

To jest suma kwadratów wewnątrz klastrów. Mniejsze wartości oznaczają, że przypisane punkty są ciaśniej skupione wokół swoich centroidów.

Ta funkcja celu wyjaśnia dwie części algorytmu:

• Jeśli centroidy są ustalone, najlepszym ruchem jest przypisanie każdego punktu do najbliższego centroidu.
• Jeśli przypisania są ustalone, najlepszym centroidem jest średnia przypisanych punktów.

Dlatego reguła aktualizacji nie jest arbitralna. „Średnie” w k-średnich to dosłownie średnie arytmetyczne.

Jak działa algorytm k-średnich

Typowa pętla jest krótka:

1. Wybierz $k$ początkowych centroidów.
2. Przypisz każdy punkt do najbliższego centroidu.
3. Przelicz każdy centroid jako średnią przypisanych do niego punktów.
4. Powtarzaj, aż przypisania przestaną się zmieniać albo poprawa będzie bardzo mała.

Ten proces zwykle zbiega szybko, ale niekoniecznie do najlepszego możliwego podziału na klastry. Różne centroidy początkowe mogą prowadzić do różnych końcowych wyników, więc inicjalizacja ma znaczenie.

Przykład grupowania k-średnich krok po kroku

Weźmy takie jednowymiarowe punkty danych:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Załóżmy, że chcemy uzyskać $k = 2$ klastry i zaczynamy z centroidami w punktach $1$ i $10$. To dobry przykład, bo centroidy rzeczywiście przesuwają się po pierwszej aktualizacji.

Krok 1: przypisz punkty do najbliższego centroidu

Punkty $1, 2, 3$ są bliżej $1$.

Punkty $10, 11, 12$ są bliżej $10$.

Zatem klastry to

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Krok 2: zaktualizuj centroidy

Nowy centroid pierwszego klastra to

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Nowy centroid drugiego klastra to

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Oba centroidy się przesunęły: z $1$ do $2$ oraz z $10$ do $11$.

Krok 3: przypisz ponownie

Teraz ponownie sprawdź najbliższy centroid, używając $2$ i $11$.

Punkty $1, 2, 3$ nadal należą do pierwszego klastra, a punkty $10, 11, 12$ nadal należą do drugiego klastra. Ponieważ przypisania już się nie zmieniają, algorytm osiągnął zbieżność.

To czysty przykład, bo dane naturalnie dzielą się na dwie zwarte grupy. Rzeczywiste zbiory danych są bardziej chaotyczne i właśnie wtedy k-średnich może zacząć wprowadzać w błąd.

Kiedy k-średnich działa dobrze

K-średnich działa najlepiej, gdy w przybliżeniu spełnione są następujące warunki:

• Cechy są liczbowe.
• Odległość euklidesowa jest sensownym sposobem mierzenia podobieństwa.
• Klastry są dość zwarte, a nie długie lub zakrzywione.
• Cechy zostały przeskalowane, tak aby jedna zmienna nie dominowała nad pozostałymi.

Jeśli te warunki nie są spełnione, wynik może nadal wyglądać schludnie, a mimo to nie oddawać rzeczywistej struktury danych.

Typowe błędy przy k-średnich

Traktowanie k-średnich jako uniwersalnej metody grupowania

K-średnich działa najlepiej wtedy, gdy klastry są w miarę zwarte, a średnia jest sensownym podsumowaniem. Nie jest to dobry domyślny wybór dla każdego zbioru danych.

Ignorowanie skalowania cech

Jeśli jedna cecha jest mierzona w znacznie większej skali niż inna, może zdominować obliczanie odległości. Standaryzacja lub normalizacja cech jest często ważna przed uruchomieniem k-średnich.

Zakładanie, że odpowiedź jest jednoznaczna

K-średnich może zbiegać do różnych minimów lokalnych przy różnych punktach startowych. Dlatego często stosuje się wielokrotne uruchomienia albo metody takie jak inicjalizacja k-means++.

Używanie cech nieliczbowych lub źle zakodowanych

Ponieważ centroidy są średnimi, standardowe k-średnich jest zbudowane dla zmiennych liczbowych. Jeśli cecha jest kategoryczna, obliczanie średniej arytmetycznej może nie mieć sensu.

Stosowanie do klastrów o wyraźnie niesferycznym kształcie

Jeśli prawdziwe grupy są długie, zakrzywione albo bardzo nierówne pod względem gęstości, k-średnich może podzielić jedną naturalną grupę albo połączyć dwie różne. Ta metoda preferuje zwarte klastry oparte na centroidach.

Zapominanie, że wartości odstające mogą przesuwać centroidy

Ponieważ centroidy są średnimi, wartości skrajne mogą wyraźnie je przesuwać. Jeśli wartości odstające są ważne w twoich danych, sprawdź to, zanim zaufasz wynikowi.

Gdzie stosuje się grupowanie k-średnich

K-średnich jest często używane do eksploracyjnego grupowania, segmentacji klientów lub zachowań, kwantyzacji kolorów obrazu oraz jako szybki punkt odniesienia w uczeniu nienadzorowanym.

Jest najbardziej użyteczne wtedy, gdy masz cechy liczbowe, chcesz szybkiego prostego modelu i oczekujesz klastrów, które są w przybliżeniu zwarte w przestrzeni euklidesowej.

Prosty model myślowy

Wyobraź sobie, że umieszczasz $k$ ruchomych pinezek na wykresie rozrzutu. Każdy punkt przyczepia się do najbliższej pinezki. Następnie każda pinezka przesuwa się do średniego położenia punktów do niej przypiętych. Powtarzaj to, aż pinezki prawie przestaną się ruszać.

Ten obrazek to nie tylko intuicja. To prawie cały algorytm.

Spróbuj podobnego zadania z grupowania

Weź mały zbiór punktów na prostej, wybierz $k = 2$ i ręcznie wykonaj jeden pełny cykl przypisania i aktualizacji. Następnie zmień centroidy początkowe albo dodaj jedną wartość odstającą i zobacz, jak zmienia się wynik. Jeśli chcesz pójść o krok dalej, wypróbuj własną wersję na małym zbiorze danych i porównaj, co dzieje się przed i po skalowaniu cech.