Grupa K-średnich: Centroidy, Komór Voronoi i Inertia

Rozdziel najpierw, nigdy nie pytaj

Algorytm K-średnich jest najprostszym i powszechnym algorytmem uczenia się bez nadzoru: przy danym zbiorze punktów i wybranej liczbie klastrów k, dzieli punkty na k grup, tak że każdy punkt jest bliżej własnego centrum klastra (środka) niż do jakiegokolwiek innego centrum klastra. Nie ma etykiet do nauki – algorytm odkrywa strukturę wyłącznie na podstawie sposobu rozmieszczenia punktów w przestrzeni.

Algorytm przechodzi przez dwie proste kroki, które się zmieniają aż do momentu, gdy nic się nie zmienia, co jest specyficzną wersją szerszej techniki zwanej algorytmem Lloyda: przypisanie – przydziel każdy punkt do najbliższego centroidy – i aktualizacja – przesuwaj każdą centroidę w średnie położenie punktów teraz przypisanych do niej. Ponieważ ponowne przypisywanie punktów nigdy nie zwiększa całkowitej sumy kwadratów odległości punktów od ich przypisanej centroidy, a ponowne obliczanie centroidów jako środków może tylko je zmniejszyć, cel jest gwarantowany monotoniczną nierosnący na każdym kroku, dlatego pętla zawsze kończy się, zamiast oscylować w nieskończoność.

1. pick k initial centroids
2. repeat until assignments stop changing:
     assign each point to its nearest centroid   (Voronoi partition)
     move each centroid to the mean of its assigned points
3. done — clusters are the final Voronoi regions

Co w rzeczywistości minimalizuje algorytm K-średnich

Formalny cel to suma kwadratów wewnątrzklasterowych (WCSS), zwana również inerencją: suma kwadratów odległości Euklidesowej z każdego punktu do centroidu jego własnej klastra, obliczona dla wszystkich klastrów. Każda iteracja przypisywania-następnie aktualizacji jest udowodniona jako nieująca się w tej wartości, dlatego obserwowanie spadku inerencji, jej ustabilizowania się i ostatecznego wypadkowanie do stanu płaskiego jest standardowym sposobem na śledzenie przebiegu konwergencji – płaska krzywa inerencji oznacza, że przypisanie przestało się zmieniać i algorytm osiągnął lokalny minimum WCSS.

Geometrycznie, ustalając centroidy i pytając 'który centroid jest najbliższy dla każdego punktu', definiujemy to dokładnie diagramy Voronoi: k centroidów dzieli płaszczyznę na k wypukłych obszarów, każdy z których stanowi zbiór punktów bliższych danego centroidu niż jakiegokolwiek innego. Algorytm K-średnich w tym sensie iteracyjnie dopasowuje diagram Voronoi do danych – przesuwa każdy punkt generujący do środka masy swojego własnego komórki, a następnie ponownie oblicza komórki dla nowych punktów i powtarza proces.

Lokalne minimumy i znaczenie inicjalizacji

Algorytm K-means gwarantuje jedynie znalezienie lokalnego minimum WCSS, a nie globalnego. Rozpoczynając od różnych początkowych centroidów, algorytm może konwergować do różnych, czasem wyraźnie gorszych, ostatecznych grupowania, szczególnie w przypadku bardzo różniących się pod względem wielkości lub gęstości klastrów. Losowa inicjalizacja jest notoriously podatna na wybór dwóch początkowych centroidów blisko siebie wewnątrz tego, co powinno być jednym klastrem, pozostawiając inny klastr bez pobliskiego centroidu. K-means++ rozwiązuje ten problem, wybierając początkowe centroidy sekwencyjnie z prawdopodobieństwem proporcjonalnym do kwadratowego odległości od już wybranych centroidów, co silnie wpływa na rozłożenie początkowych pozycji – w praktyce konwerguje szybciej i do zauważenie lepszych lokalnych minimum niż losowe starty, a jest to domyślna inicjalizacja w zasadzie każdej nowoczesnej implementacji.

Wybór k: metoda łopatek i metoda sylwetki

K-means wymaga określenia liczby k z góry, a algorytm nie ma możliwości poinformowania Cię o "prawidłowej" wartości. Inercja (WCSS) maleje w miarę wzrostu k (więcej grup może dopasować dane przynajmniej tak dobrze, a k równy liczbie punktów prowadzi WCSS do zera trivially), więc nie możesz po prostu wybrać k minimalizującego WCSS. Metoda łopatek rysuje inercję w funkcji k i szuka punktu, w którym tempo spadku ostro wyhamowuje – heurystyka wizualna, nieco subiektywna oparta na zmniejszających się zwrotach. Wynik sylwetki jest bardziej ugruntowany: dla każdego punktu porównuje średnią odległość do punktów w jego własnej grupie z średnią odległością do punktów w najbliższej innej grupie, generując wynik od -1 do 1, który nagradza ciasne, dobrze oddzielone grupy. Wybór k maksymalizujący średni wynik sylwetki dla wszystkich punktów jest powszechnym, bardziej ilościowym wyborem.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz K-Means Clustering i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.