Co to jest grupowanie K-średnich?

Grupowanie K-średnich jest uczenie się bez nadzoru spośród wszystkich algorytmów uczenia się bez nadzoru, grupowanie K-średnich może być najczęściej stosowane ze względu na jego moc i prostotę. Jak dokładnie działa grupowanie K-średnich?

Krótka odpowiedź jest taka, że ​​grupowanie K-średnich działa według utworzenie punktu odniesienia (centrroidy) dla żądanej liczby zajęć, a następnie przypisywanie punktów danych do klastrów klas na podstawie tego, który punkt odniesienia jest najbliższy. Chociaż jest to krótka definicja grupowania K-średnich, poświęćmy trochę czasu, aby zagłębić się w grupowanie K-średnich i uzyskać lepszą intuicję dotyczącą jego działania.

Definicja klastrowania

Zanim przyjrzymy się dokładnym algorytmom używanym do przeprowadzania grupowania K-średnich, poświęćmy trochę czasu na ogólne zdefiniowanie grupowania.

Klastry to po prostu grupy elementów, a grupowanie polega po prostu na umieszczaniu elementów w tych grupach. W sensie analityki danych algorytmy klastrowania staraj się zrobić dwie rzeczy:

• Upewnij się, że wszystkie punkty danych w klastrze są do siebie jak najbardziej podobne.
• Upewnij się, że wszystkie punkty danych w różnych klastrach są do siebie jak najbardziej odmienne.

Algorytmy grupowania grupują elementy w oparciu o pewną metrykę podobieństwa. Często dokonuje się tego poprzez znalezienie „środka ciężkości” różnych możliwych grup w zbiorze danych, choć nie wyłącznie. Istnieje wiele różnych algorytmów grupowania, ale cel wszystkich algorytmów grupowania jest taki sam: określenie grup nieodłącznie związanych ze zbiorem danych.

Klastrowanie K-średnich

Klastrowanie K-Means jest jednym z najstarszych i najczęściej stosowanych typów algorytmów grupowania, a jego działanie opiera się na kwantyzacja wektorowa. Jako początek wybierany jest punkt w przestrzeni, a następnie od początku rysowane są wektory do wszystkich punktów danych w zbiorze danych.

Ogólnie rzecz biorąc, grupowanie K-średnich można podzielić na pięć różnych etapów:

• Umieść wszystkie instancje w podzbiorach, gdzie liczba podzbiorów jest równa K.
• Znajdź średni punkt/centrroid nowo utworzonych partycji klastra.
• Na podstawie tych centroidów przypisz każdy punkt do określonego skupienia.
• Oblicz odległości od każdego punktu do centroid i przypisz punkty do klastrów, w których odległość od centroidy jest minimalna.
• Po przypisaniu punktów do skupień znajdź nowy środek ciężkości skupień.

Powyższe kroki powtarza się aż do zakończenia procesu uczenia.

W początkowej fazie centroidy są umieszczane gdzieś pomiędzy punktami danych.
Zdjęcie: Weston.pace za pośrednictwem Wikimedia Commons, Licencja Wolnej Dokumentacji GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternatywnie, po umieszczeniu centroid, możemy wyobrazić sobie grupowanie K-średnich jako zamianę między dwiema różnymi fazami: oznaczanie punktów danych i aktualizowanie centroid.

W drugim kroku metryka odległości, taka jak odległość euklidesowa, jest wykorzystywana do obliczenia, do której centroidy dany punkt jest najbliżej, a następnie punkty są przypisywane do klasy tej centroidy. Zdjęcie: Weston.pace za pośrednictwem Wikimedia Commons, licencja GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

W fazie etykietowania punktów danych każdemu punktowi danych przypisuje się etykietę umieszczającą go w klastrze należącym do najbliższej centroidy. Najbliższą centroidę określa się zwykle za pomocą kwadratu odległości euklidesowej, chociaż można zastosować inne metryki odległości, takie jak odległość Manhattanu, cosinus i odległość Jaccarda, w zależności od rodzaju danych wprowadzanych do algorytmu grupowania.

W trzecim kroku centroidy przesuwane są do średniej wszystkich punktów danych. Następnie zajęcia zostaną przeniesione. Zdjęcie: Weston.pace za pośrednictwem Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Na etapie aktualizacji środka ciężkości oblicza się, znajdując średnią odległość pomiędzy wszystkimi punktami danych aktualnie zawartymi w klastrze.

Jak wybrać odpowiednią wartość dla „K”

Biorąc pod uwagę, że grupowanie K-średnich jest algorytmem nienadzorowanym i liczba klas nie jest z góry znana, jak wybrać odpowiednią liczbę klas/właściwą wartość K?

Jedna z technik wyboru właściwej wartości K nazywa się „technika łokcia”. Technika łokcia polega na uruchomieniu algorytmu grupowania K-średnich dla zakresu różnych wartości K i zastosowaniu metryki dokładności, zwykle sumy błędów kwadratowych, w celu określenia, które wartości K dają najlepsze wyniki. Sumę kwadratu błędu określa się poprzez obliczenie średniej odległości między środkiem ciężkości klastra a punktami danych w tym klastrze.

Termin „technika łokcia” wynika z faktu, że gdy wykreślisz SSE w odniesieniu do różnych wartości K, powstały wykres liniowy będzie często miał kształt „kolanka”, gdzie SSE szybko maleje dla kilku pierwszych wartości K, ale potem się wyrównuje. W takich warunkach wartość K zlokalizowana na kolanku jest najlepszą wartością dla K, gdyż po tej wartości następuje gwałtowny spadek zysków.

Klastrowanie K-średnich mini-wsadowych

W miarę powiększania się zbiorów danych wydłuża się także czas obliczeń. Podstawowe grupowanie K-średnich może zająć dużo czasu, jeśli jest uruchamiane na ogromnych zbiorach danych, w rezultacie wprowadzono poprawki do grupowania K-średnich, aby umożliwić zmniejszenie kosztów przestrzennych i czasowych algorytmu.

Mini-Batch K-oznacza grupowanie jest wariantem grupowania K-średnich gdzie rozmiar rozważanego zbioru danych jest ograniczony. Normalne grupowanie K-średnich działa na całym zestawie danych/partii jednocześnie, podczas gdy grupowanie K-średnich w trybie mini-batch dzieli zbiór danych na podzbiory. Minipartie są losowo pobierane z całego zbioru danych i dla każdej nowej iteracji wybierana jest nowa próbka losowa, która jest wykorzystywana do aktualizacji położenia centroid.

W przypadku grupowania K-średnich w trybie Mini-Batch klastry są aktualizowane przy użyciu kombinacji wartości mini-partii i szybkości uczenia się. Szybkość uczenia się maleje w miarę iteracji i jest odwrotnością liczby punktów danych umieszczonych w określonym klastrze. Efektem zmniejszenia szybkości uczenia się jest zmniejszenie wpływu nowych danych i osiągnięcie zbieżności, gdy po kilku iteracjach nie ma zmian w klastrach.

Wyniki badań nad efektywnością grupowania K-średnich w trybie mini-partii sugerują, że może ono skutecznie skrócić czas obliczeń przy niewielkim kompromisie w zakresie jakości klastrów.

Zastosowania grupowania K-średnich

Grupowanie K-średnich można bezpiecznie stosować w każdej sytuacji, w której punkty danych można podzielić na odrębne grupy/klasy. Oto kilka przykładów typowych przypadków użycia grupowania K-średnich.

Grupowanie K-średnich można zastosować do klasyfikacji dokumentów, grupowania dokumentów na podstawie takich cech, jak tematy, znaczniki, użycie słów, metadane i inne cechy dokumentu. Można go również wykorzystać do klasyfikowania użytkowników jako botów lub nie botów na podstawie wzorców aktywności, takich jak posty i komentarze. Grupowanie K-średnich można również wykorzystać do podziału osób na grupy w oparciu o poziom obaw podczas monitorowania ich zdrowia, w oparciu o takie cechy, jak choroby współistniejące, wiek, historia pacjenta itp.

Klastrowanie K-średnich można również wykorzystać do bardziej otwartych zadań, takich jak tworzenie systemów rekomendacji. Użytkownicy systemu takiego jak Netflix można grupować na podstawie wzorców oglądania i polecanych podobnych treści. Grupowanie K-średnich można wykorzystać do zadań wykrywania anomalii, podkreślając potencjalne przypadki oszustwa lub wadliwych elementów.