Klasterowanie k-srednich: Znalezienie Grup w Danych Bez Etykiety

Grupowanie danych bez klucza odpowiedzi

Większość technik uczenia maszynowego, z którymi ludzie spotykają się na początku — filtr spamu, prognozy cen, klasyfikatory obrazów — to uczenie nadzorowane: uczą się na podstawie przykładów, które już zawierają poprawną odpowiedź. Klustering należy do innej rodziny, nazywanej uczeniem bez nadzoru, gdzie w ogóle nie istnieją etykiety. Algorytm otrzymuje tylko zbiorcę punktów danych i prosi go, aby znaleziono w nich strukturę: które punkty wydają się należeć do grupy, a które są oddzielne? Algorytm K-means jest najpopularniejszym algorytmem klusteringu dlatego, że jego odpowiedź na to pytanie jest prosta, szybka i zwykle logiczna.

Zwykłe zastosowania obejmują grupowanie klientów według zachowania zakupowego dla celów marketingowych, skompresowanie palety kolorów obrazu do małej liczby reprezentatywnych tonów, grupowanie dokumentów według tematów oraz przetwarzanie danych przed wprowadzeniem ich w model nadzorowany.

Algorytm, krok po kroku

K-means wymaga od użytkownika wyboru jednej liczby na początku: k, liczbę klastrów do znalezienia. Od tamta chwili algorytm alternuje między dwiema prostymi fazami aż do momentu, gdy nic się nie zmienia:

Z matematycznego punktu widzenia, k-means próbuje minimalizować sumę kwadratów odległości wewnątrz klastra (także nazywaną inertią): sumę, po każdym punkcie, kwadratu odległości między tym punktem a jego przypisanym centroidem. Mniejsza inertja oznacza bardziej skupione i kompaktowe klastry.

Dlaczego ważne są inicjalizacja i kształt klastrów

Ponieważ k-means zawsze konverguje tylko do lokalnego ekstremum, losowe położenia centroidów mogą znacząco wpłynąć na końcowy wynik. Dwa uruchomienia algorytmu na tym samym zestawie danych z różnymi kluczami losowymi mogą osiągnąć widocznie różne podziały na klastry, szczególnie gdy klastry się nadlatują lub mają różne gęstości. To jest przyczyną tego, dlaczego większość praktycznych implementacji uruchamia algorytm wielokrotnie z różnych losowych punktów startowych i zachowuje rezultat o najniższej inertii, lub używa strategii inicjalizacji k-means++, która zamiernie rozpraszona jest początkowe centroidy, aby zmniejszyć tę wrażliwość.

Druga, bardziej podstawowa ograniczona jest wbudowana w algorytm geometria: ponieważ każdy punkt przypisany jest do najbliższego centroidu na podstawie odległości prostej, k-means nieco zakłada, że klastry są prawie sferyczne (technicznie, konwexne) i porównywalnej wielkości. Algorytm wykazuje słabe wyniki przy elongowanych, krzyżowato-miesięcznych lub wewnętrznie zagnieżdżonych klastrach, a także dla klastrów o bardzo różnym rozmiarze lub gęstości — mniejszy, bardziej skupiony klaster leżący blisko większego może stracić swoje punkty tylko dlatego, że centroid większego klastra się okazuje być blisko. W tych sytuacjach metody oparte na gęstości, takie jak DBSCAN lub hierarchiczne klasyfikacja, które nie zakładały określonego kształtu klastrów, tendują do lepszych wyników.

Wybór k: metoda łokciowa i indeks siluety

Największym praktycznym problemem dla k-means jest konieczność podania wartości k w zaawansowanej fazie, ponieważ rzeczywiste dane rzadko pozwalają na wyraźne stwierdzenie, ile naturalnych grup jest właściwe. Dwa techniki są często używane do zrobienia wyboru opartego na informacjach:

Metoda łokciowa polega na powtarzalnym wykonaniu k-means dla zakresu wartości k (np., od 1 do 10) i narysowaniu wynikowej inertii w zależności od k. Inertja zawsze maleje, gdy k rośnie — więcej grup może zawsze lepiej dopasować dane, aż do momentu, gdy k jest równe liczbie punktów danych (wtedy inertja osiąga wartość 0) — ale stopniowo spadek efektywności często przestaje być wyraźny po osiągnięciu prawdziwej liczby grup. Narysowana w ten sposób krzywa ma kształt łokcia, a k na jego łuku jest dobrym wyborem.

Indeks siluety podchodzi do sprawy inaczej, oceniając każdy punkt zgodnie z tym, jak dobrze pasuje on do przypisanego mu klastra w porównaniu z najbliższym klasterem sąsiadującym. Wynik to wartość z zakresu -1 do 1 dla każdego punktu (i średnia dla całego zestawu danych). Wartości bliskie 1 sugerują skupione, dobrze oddzielone klastry; wartości bliskie 0 oznaczają punkty na granicach klastrów; negatywne wartości wskazują, że punkt może zostać przypisany do nieprawidłowego klastra. Próba kilku wartości k i wybór tej z najwyższym średnim indeksem siluety często jest bardziej wiarygodny niż metoda łokciowa, szczególnie gdy łokieć sam nie jest wyraźnie definiowany.

K-means w praktyce: skalowanie i przetwarzanie przed grupowaniem

Dokonane na całym podstawie obliczeń odległości, k-węgielkowy (k-means) jest bardzo wrażliwy na skalę każdego cechy. Jeśli jedna cecha ma jednostki funtów (zasięg do tysięcy), a druga procenty (zasięg od 0 do 1), cecha w funtach dominuje w każdym obliczeniu odległości i prawie sama decyduje o grupowaniu, niezależnie od tego, jak znacząca jest really cecha procentowa. Zatem standaryzacja lub normalizacja każdej cechy na podobną skalę przed grupowaniem nie jest opcjonalna – to wymagane przetwarzanie przed grupowaniem, a pominięcie go stanowi jedno z najczęstszych praktycznych błędów.

K-means staje się również trudniejszy wraz ze wzrostem liczby wymiarów, co jest manifestacją tak zwanej mocy przekleństwa wymiarowości: w przestrzeniach o wysokim wymiarze odległość między najbliższymi a najbardziej oddalonymi punktami staje się podobna, co sprawia, że pojęcie „bliższego” centroidu jest mniej znaczące. Dla danych o wysokiej liczbie wymiarów standardową praktyką jest zastosowanie techniki zmniejszania wymiarowości, takiej jak analiza głównych komponent (PCA), aby skompresować dane do mniejszej liczby informacyjnych wymiarów przed grupowaniem.

Często zadawane pytania