K-Means++: Dlaczego Nasiona Mają Znaczenie, a Nie Losowość

Algorytm Lloyda, w czterech liniach

K-średnich dzieli n punktów na k skupień poprzez alternowanie dwóch kroków aż do momentu, gdy nic się nie zmienia: przypisuje każdy punkt do jego najbliższego centroidy, a następnie przesuwa każdy centroid w kierunku średniej punktów przypisanych do niego. Ten cykl to algorytm Lloyda, a każda pełna iteracja jest dowodem na to, że nie zwiększa ona obiektywu, który minimalizuje - suma kwadratów wewnątrz klastrów (inertia):

J = sum over clusters c, sum over points x in c of ||x - mean(c)||^2 przypisanie : każdego x -> argmin_c ||x - centroid_c||^2 (wygrywa najbliższy centroid) aktualizacja : centroid_c Geometrycznie, ustalenie centroidów i przypisanie każdego punktu do jego najbliższego z nich wyrywa płaszczyznę w diagram Voronoi – granica między dwoma obszarami klastrów jest dokładnie prostopadłym środkiem bicia ich centroidów, ponieważ to zbiór punktów oddalonych od obu centroidów tej samej odległości. K-średnich, w każdej iteracji, oblicza diagram Voronoi i następnie go rozluźnia w kierunku własnych centrów masy.

J = sum over clusters c, sum over points x in c  of  ||x - mean(c)||^2

assign  : each x -> argmin_c ||x - centroid_c||^2   (nearest centroid wins)
update  : centroid_c <- mean of all x currently assigned to c
repeat until assignments stop changing

Dlaczego inicjalizacja to cała rozgrywka

Algorytm Lloyds jest gwarantowany jedynie dobiegania do lokalnego minimum J, a które konkretnie lokalne minimum osiągnie zależy w zasadzie tylko od tego, gdzie zaczynają się centroidy. Dwa początkowe centroidy umieszczone w tym samym prawdziwym skupieniu często będą tam utknęły na wieki, dzieląc jedno rzeczywiste skupienie na dwie części i jednocześnie łącząc dwa inne – krok aktualizacyjny może jedynie przemieszczać granice, nie może teleportować centroida z pustego miejsca do skupienia, które nie ma swojego centroidu w pobliżu. Prosta losowa inicjalizacja (wybranie k przypadkowych punktów jako centroidy) jest tania, ale często wystarczająco często powoduje ten typ awarii.

K-Means++: ziarna rozstawione celowo

Algorytm K-Means++ (Arthur & Vassilvassili, 2007) rozwiązuje to poprzez etap losowego wybierania z wagami, który uruchamiany jest raz przed rozpoczęciem algorytmu Lloyda:

1. wybierz pierwszy centroid losowo spośród danych 2. dla każdego pozostałego punktu x oblicz D(x) = odległość do najbliższego wybranego centrydów 3. wybierz następny centroid losowo, z prawdopodobieństwem proporcjonalnym do D(x)^2 4. powtórz kroki 2 i 3 aż do wyboru k centrydów 5. uruchom zwykły algorytm Lloyda z tych ziarn Z kwadratowaniem odległości przed ważeniem dokonuje się tego celowo: punkty oddalone od każdego istniejącego centrydów stają się znacznie bardziej prawdopodobnymi wyborami, aktywnie rozrzucając ziarna na różnych klastrach zamiast zgrupowywać je, a jednocześnie pozostawiając niewielką szansę na wybranie punktu blisko niego, aby uniknąć trwałego zakłócenia ziarn przez pojedynczy odstępnik. Gwarancja, jaką zapewnia to podejście: ziarno K-Means++ daje oczekiwany współczynnik przybliżenia O(log k) w stosunku do optymalnego klastrowania, matematyczny wynik, którego nie osiągnie losowe wybieranie. W praktyce również konwerguje w zauważalnie mniejszej liczbie iteracji Lloyda, ponieważ ziarna już znajdują się blisko dobrych końcowych pozycji.

1. pick the first centroid uniformly at random from the data
2. for each remaining point x, compute D(x) = distance to the nearest chosen centroid
3. pick the next centroid at random, with probability proportional to D(x)^2
4. repeat step 2-3 until k centroids are chosen
5. run ordinary Lloyd's algorithm from these seeds

Wybór k: metoda łokcia i sylwetka

Nic w algorytmie nie mówi, jaki jest najlepszy numer grup (k – to hiperparametr, który podajesz). Dwie popularne metody diagnostyczne to: metoda łokcia, która rysuje innertię J w zależności od k i szuka miejsca, gdzie dodanie kolejnej grupy nie przynosi już dużego cięcia (innertia zawsze maleje wraz ze wzrostem k, osiągając zero, gdy k = n, więc istotny sygnał to punkt spadku zwrotu, a nie minimum). Sylwetka natomiast ocenia każdy punkt pod kątem tego, jak blisko jest do swojej własnej grupy w porównaniu z najbliższą drugą grupą, średnio na wszystkich punktach, i nagradza wartość k, która generuje ciasne, dobrze rozróżnione grupy, zamiast tylko niskiej całkowitej wariancji.

Gdzie K-Medias nie sprawdza się

K-Medias implikuje, że klastry są w przybliżeniu kuliste i o podobnych rozmiarach, ponieważ minimalizuje odległość euklidesową do pojedynczego centroidu na dany klaster – to samo założenie wbudowane w mieszaninę równych, izotropowych rozkładów Gaussa. Jeśli podasz mu klasyczne zestawy danych z kształtem dwóch półksiżyków lub nakładających się okręgów, i ono zawiedzie widocznie: prosta granica przecinająca dwie skrzyżowane łuki lub dwa wklęsłe koła nie da się utworzyć niezależnie od tego, jak przemieszczasz centroidy, ponieważ żaden układ centroidów nie tworzy tych kształtów wypukłych komórek Voronoi. Metody oparte na gęstości (DBSCAN) lub klastrowanie spektralne radzą sobie z tymi kształtami; K-Medias wciąż jest popularny, ponieważ ma złożoność O(n*k*i) na każde uruchomienie (i = iteracje), co jest łatwo równoległe i wystarczająco dobre, gdy klastry rzeczywiście mają kształt kropli.

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.