K-Średnich: Centroidy, Zbieżność i k-średnich++

Dwie kroki, powtarzane do ustalonego punktu

K-means dzieli n punktów na k skupień, każde reprezentowane przez pojedynczy centroid. Mając k początkowych centroidów, algorytm Lloyda (Stuart Lloyd, 1957, opublikowany 1982) w alternując sposób wykonuje dwie kroki, aż do momentu, gdy nic się nie zmienia: przypisuje każdy punkt do najbliższego centroidu, tworząc diagram Voronoi i następnie przesuwa każdy centroid na średnią pozycję punktów przypisanych do niego. Obie operacje tylko zmniejszają lub utrzymują stałą wartość celu optymalizacji, co gwarantuje ustabilizowanie procesu.

Co w zasadzie jest minimalizowane

Celem jest zachowanie bezruchu, zwane również sumą kwadratów wewnątrzklasterowego rozrzutu: dla każdego punktu, suma odległości euklidesowych ze sześcianem do jego przypisanego centroidu, obliczona na wszystkich punktach. Krok przypisania, przy ustalonych centroidach, jest udowodniony jako przypisanie minimalizujące inerencję. Krok aktualizacji, przy ustalonych przypisaniach, ustawia każdy centroid na średnią arytmetyczną jego punktów, co jest udowodnione jako punkt minimalizujący sumę kwadratów odległości do tego grupy. Alternowanie dwóch dokładnych minimalizacji tego samego celu jest przyczyną, dla której pętla nie może zwiększać inerencji i w końcu musi przestać się zmieniać.

while (assignments changed) {
  for (const p of points)                          // assignment step
    p.cluster = argmin_k( dist2(p, centroid[k]) );
  for (let k = 0; k < K; k++)                       // update step
    centroid[k] = mean(points where p.cluster === k);
}

Minimalna wartość lokalna, i dlaczego inicjalizacja ma znaczenie

Minimalizowanie inercji dokładnie we wszystkich możliwych podziałach jest problemem NP-trudnym, więc algorytm Lloyda gwarantuje jedynie minimalną wartość lokalną – wynik, do którego się zbiega, zależy w dużym stopniu od tego, gdzie zaczęły się centroidy. Dwa złe początkowe centroidy mogą trwale rozdzielić to, co powinno być jednym klastrem, lub połączyć dwa klastry, które powinny pozostać oddzielne, ponieważ nie ma w pętli mechanizmu, który przesuwałby centroid przez pustą przestrzeń, gdy przypisania się ustabilizowały. Standardowe rozwiązanie polega na uruchomieniu całego algorytmu kilkakrotnie z różnych losowych startów i zachowaniu tego, który daje najniższą ostateczną inercję.

k-means++: strategia zapewniająca lepsze początkowe wyniki

Arthur i Vassilvitskii w swoim k-means++ (2007) poprawiają szanse na dobry start bez zmiany głównego pętli. Wybierz pierwszy centroid losowo z całej próby. Dla każdego kolejnego centroidu, wybierz punkt z prawdopodobieństwem proporcjonalnym do kwadratu jego odległości od najbliżej wybranego dotychczas centroidu – punkty oddalone od istniejących centroidów są znacznie bardziej prawdopodobne, rozpraszając początkowe centroidy po całym zbiorze danych zamiast skupiać je w gęstych grupach. Ta strategia podsedziania sama w sobie gwarantuje oczekiwane przybliżenie współczynnika O(log k) względem prawdziwego optimum, a w praktyce znacząco redukuje zarówno liczbę iteracji potrzebnych do konwergencji, jak i prawdopodobieństwo złego lokalnego minimum.

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.