Grupowanie K-średnich (K-means Clustering)
- Autor metody
- MacQueen, J. B.; Lloyd, S. P.
- Rok
- 1967 (formalized 1982)
- Typ
- Partitional clustering
- Rodzina
- Machine learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
K-means to klasyczny algorytm grupowania partycyjnego bez nadzoru, który dzieli zbiór danych na K niepokrywających się grup poprzez iteracyjne przypisywanie każdej obserwacji do najbliższego centroidu i aktualizowanie centroidów jako średniej przypisanych do nich punktów.
Jest to jedno z najczęściej używanych narzędzi eksploracyjnych w uczeniu maszynowym i analizie danych.
Intuicja stojąca za metodą
Wyobraźmy sobie upuszczenie K magnesów na mapę punktów danych. Każdy punkt jest przyciągany do najbliższego magnesu, a następnie każdy magnes przesuwa się do środka ciężkości punktów, które przyciągnął. Powtarzamy ten cykl przyciągania i przesuwania, aż nic się nie rusza: magnesy znalazły K naturalnych grup. K-means formalizuje dokładnie tę ideę, minimalizując całkowitą sumę kwadratów odległości od każdego punktu do centrum jego klastra, zwaną sumą kwadratów wewnątrz klastra (WCSS lub inercja).
Historia
Idea k-means została niezależnie wprowadzona przez MacQueena w 1967 roku, który ukuł ten termin, i sformalizowana jako efektywny algorytm iteracyjny przez Stuarta Lloyda w Bell Labs w latach 50. XX wieku (opublikowana w 1982). Udoskonalenie inicjalizacji k-means++ przez Arthura i Vassilvitskiego w 2007 roku rozwiązało problem wrażliwości na minima lokalne. Dziś k-means pozostaje podstawową metodą uczenia nienadzorowanego nauczaną w praktycznie każdym programie nauczania data science.
Kiedy stosować
K-means nadaje się do eksploracyjnego grupowania dużych, czysto numerycznych zbiorów danych, gdy potrzebne jest szybkie, skalowalne partycjonowanie i akceptowalne jest wcześniejsze określenie K lub jego poszukiwanie za pomocą metody łokcia lub sylwetki. Dobrze sprawdza się w segmentacji klientów, kompresji obrazów, grupowaniu tematów dokumentów i wstępnym przetwarzaniu przed uczeniem nadzorowanym. Należy go unikać, gdy klastry są niesferyczne, mają znacznie różniące się rozmiary lub gęstości, gdy cechy są kategoryczne lub porządkowe (zamiast tego użyj k-modes lub k-prototypes), gdy liczba klastrów jest całkowicie nieznana, a eksperymenty ze zmiennym K są niewykonalne, lub gdy dane zawierają wiele wartości odstających (zamiast tego użyj DBSCAN lub wariantów odpornych).
Ograniczenia i uwagi
- Wymaga wcześniejszego określenia K; niewłaściwy wybór K prowadzi do bezsensownych klastrów.
- Zakłada sferyczne klastry o podobnych rozmiarach; wydłużone, nieregularne lub różnie skalowane klastry są dzielone lub łączone nieprawidłowo.
- Wrażliwy na wartości odstające: pojedynczy ekstremalny punkt może odciągnąć centroid daleko od większości klastra.
- Działa tylko z numerycznymi cechami ciągłymi; dane kategoryczne wymagają innego algorytmu (k-modes).
- Zbiega się do minimum lokalnego; wyniki mogą się różnić w zależności od przebiegu z różnymi ziarnami losowymi, chyba że użyto k-means++ lub wielokrotnych restartów.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Szybki i skalowalny: O(nKdi) na iterację, praktyczny dla milionów obserwacji przy umiarkowanym K i wymiarach.
- Prosty w implementacji, szeroko dostępny w każdej głównej platformie uczenia maszynowego i łatwy do wyjaśnienia odbiorcom nietechnicznym.
- Dobrze sprawdza się w przypadku dużych, dobrze oddzielonych, w przybliżeniu sferycznych klastrów o podobnym rozmiarze.
- Inicjalizacja k-means++ znacznie zmniejsza wrażliwość na warunki początkowe w porównaniu z inicjalizacją losową.
- Deterministyczny w ramach ustalonego ziarna losowego, co zapewnia powtarzalność wyników.
Zastosowania
- Segmentacja klientów dla marketingu i personalizacji na podstawie cech behawioralnych lub demograficznych.
- Kompresja obrazu poprzez kwantyzację kolorów pikseli do K reprezentatywnych wartości (kwantyzacja kolorów).
- Grupowanie dokumentów i tekstu jako krok w potokach modelowania tematów po wektoryzacji.
- Wstępne przetwarzanie do wykrywania anomalii: punkty daleko od dowolnego centroidu są kandydatami na wartości odstające.
- Krok inicjalizacji dla bardziej złożonych algorytmów, takich jak modele mieszanin gaussowskich lub grupowanie hierarchiczne.
- Analiza ekspresji genów w celu grupowania genów lub próbek o podobnych profilach ekspresji.
Jak to działa
Jak to działa
K centroidów klastrów jest umieszczanych w przestrzeni cech, albo poprzez losowe wybranie K punktów danych (Forgy), albo za pomocą inteligentniejszej strategii k-means++, która rozkłada początkowe centroidy, aby zmniejszyć szansę na słabe minima lokalne. Wybór inicjalizacji ma znaczenie: k-means++ zazwyczaj prowadzi do szybszej konwergencji i lepszych rozwiązań końcowych.
Każda obserwacja jest przypisywana do klastra, którego centroid jest najbliżej zgodnie z odległością euklidesową. To twarde przypisanie tworzy K niepokrywających się partycji danych. Formalnie, każdy punkt x_i jest przypisywany do klastra c_i = argmin_k ||x_i - mu_k||^2.
Wzór
c_i = \arg\min_k \|x_i - \mu_k\|^2
Każdy centroid jest ponownie obliczany jako średnia arytmetyczna wszystkich punktów aktualnie przypisanych do tego klastra: mu_k = (1/|C_k|) razy suma wszystkich x_i w C_k. Ten krok gwarantuje, że nowy centroid minimalizuje WCSS w każdym klastrze, biorąc pod uwagę bieżące przypisanie.
Wzór
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_iKroki przypisywania i aktualizacji naprzemiennie powtarzają się, aż pozycje centroidów przestaną się zmieniać (lub zmienią się o mniej niż próg tolerancji) lub zostanie osiągnięta maksymalna liczba iteracji. Algorytm gwarantuje konwergencję do minimum lokalnego WCSS, choć niekoniecznie do minimum globalnego.
Jakość rozwiązania ocenia się za pomocą całkowitego WCSS (inercji) J = suma po klastrach sumy po przypisanych punktach ||x_i - mu_k||^2. Wybór K jest osobną kwestią, rozwiązywaną metodą łokcia, wskaźnikami sylwetki lub statystykami luki, ponieważ sam algorytm wymaga wcześniejszego określenia K.
Wzór
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2Częste pułapki
- Zapominanie o standaryzacji cech przed grupowaniem — zmienne o dużych skalach będą dominować w obliczeniach odległości.
- Wybór K poprzez samo sprawdzenie WCSS w próbce bez wykresu łokcia lub walidacji sylwetki, co prowadzi do trywialnie małych lub dużych K.
- Uruchamianie tylko jednej inicjalizacji i akceptowanie pierwszego wyniku bez wielokrotnych restartów w celu zabezpieczenia przed słabymi minimami lokalnymi.
- Włączanie zmiennych kategorycznych lub porządkowych do macierzy cech bez odpowiedniego kodowania lub przełączania na k-modes.
- Traktowanie etykiet klastrów jako znaczących tożsamości grup bez zewnętrznej walidacji, zwłaszcza gdy klastry nie są dobrze oddzielone.
Najczęściej zadawane pytania
Jak wybrać odpowiednią liczbę klastrów K?
Uruchom k-means dla zakresu wartości K, wykreśl sumę kwadratów wewnątrz klastra w funkcji K i poszukaj „łokcia”, gdzie tempo spadku gwałtownie zwalnia. Uzupełnij to wskaźnikami sylwetki, które mierzą, jak podobny jest każdy punkt do własnego klastra w porównaniu z klastrami sąsiednimi; wyższa średnia sylwetka wskazuje na lepiej zdefiniowane klastry.
Dlaczego otrzymuję różne wyniki przy każdym uruchomieniu?
K-means jest wrażliwy na inicjalizację i zbiega się do minimum lokalnego, a nie globalnego WCSS. Użyj inicjalizacji k-means++ i ustaw stałe ziarno losowe dla powtarzalności. Dobrą praktyką jest wielokrotne uruchamianie algorytmu z różnymi ziarnami i zachowanie rozwiązania z najniższą inercją.
Czy k-means działa z danymi kategorycznymi?
Nie. K-means opiera się na odległości euklidesowej i średnich centroidów, które są niezdefiniowane dla zmiennych kategorycznych. Dla danych czysto kategorycznych użyj k-modes; dla danych mieszanych numerycznych i kategorycznych użyj k-prototypes.
Kiedy powinienem preferować DBSCAN lub GMM zamiast k-means?
Użyj DBSCAN, gdy klastry mają nieregularne kształty lub potrzebujesz automatycznego wykrywania wartości odstających bez określania K. Użyj modeli mieszanin gaussowskich (GMM), gdy chcesz miękkich (probabilistycznych) przypisań do klastrów lub klastrów o różnych rozmiarach i orientacjach, kosztem wyższej złożoności obliczeniowej.
Czy muszę skalować moje cechy?
Tak, prawie zawsze. K-means używa odległości euklidesowej, więc cechy o dużych zakresach numerycznych będą dominować w grupowaniu. Zastosuj standaryzację z-score lub skalowanie min-max przed dopasowaniem k-means, chyba że wszystkie cechy są już w tej samej skali.
Pokrewne metody
Źródła
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
Otwórz odnośnik DOISkopiowano.MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
Otwórz odnośnik do publikacjiSkopiowano.