Algorytmy grupowania - przegląd

Wprowadzenie do klastrowania

Metody klastrowania są jednymi z najbardziej użytecznych nienadzorowanych metod ML. Metody te służą do znajdowania podobieństw, a także wzorców relacji między próbkami danych, a następnie grupowania tych próbek w grupy o podobieństwie na podstawie cech.

Klastrowanie jest ważne, ponieważ określa wewnętrzne grupowanie wśród obecnie nieoznakowanych danych. Zasadniczo przyjmują pewne założenia dotyczące punktów danych, aby określić ich podobieństwo. Każde założenie skonstruuje różne, ale równie ważne klastry.

Na przykład poniżej znajduje się diagram, który pokazuje system klastrowania pogrupowany razem podobny rodzaj danych w różnych klastrach -

Metody tworzenia klastrów

Nie jest konieczne, aby klastry tworzyły się w formie kulistej. Poniżej znajduje się kilka innych metod tworzenia klastrów -

Oparte na gęstości

W tych metodach klastry są tworzone jako gęsty obszar. Zaletą tych metod jest to, że mają dobrą dokładność, a także dobrą zdolność łączenia dwóch klastrów. Dawny. Przestrzenne grupowanie aplikacji z hałasem w oparciu o gęstość (DBSCAN), punkty zamawiania w celu identyfikacji struktury klastrów (OPTYKA) itp.

Oparty na hierarchii

W tych metodach klastry są tworzone jako struktura drzewiasta oparta na hierarchii. Mają dwie kategorie, a mianowicie aglomeracyjne (podejście oddolne) i dzielące (podejście odgórne). Dawny. Klastrowanie przy użyciu Reprezentantów (CURE), Zrównoważona iteracyjna redukcja klastrowania przy użyciu hierarchii (BIRCH) itp.

Partycjonowanie

W tych metodach klastry są tworzone przez podzielenie obiektów na k skupień. Liczba klastrów będzie równa liczbie partycji. Dawny. K-średnich, grupowanie dużych aplikacji w oparciu o wyszukiwanie losowe (CLARANS).

Krata

W tych metodach klastry są tworzone jako struktura podobna do siatki. Zaletą tych metod jest to, że wszystkie operacje klastrowania wykonywane na tych siatkach są szybkie i niezależne od liczby obiektów danych. Dawny. Siatka informacji statystycznych (STING), Clustering in Quest (CLIQUE).

Pomiar wydajności klastrowania

Jedną z najważniejszych kwestii dotyczących modelu ML jest ocena jego wydajności lub, można powiedzieć, jakość modelu. W przypadku algorytmów uczenia nadzorowanego ocena jakości naszego modelu jest łatwa, ponieważ mamy już etykiety dla każdego przykładu.

Z drugiej strony, w przypadku nienadzorowanych algorytmów uczenia się nie jesteśmy aż tak szczęśliwi, ponieważ mamy do czynienia z nieoznaczonymi danymi. Ale nadal mamy pewne metryki, które dają praktykowi wgląd w zachodzenie zmian w klastrach w zależności od algorytmu.

Zanim zagłębimy się w takie metryki, musimy zrozumieć, że te metryki tylko oceniają porównawczą wydajność modeli względem siebie, a nie mierzą trafność przewidywań modelu. Oto niektóre metryki, które możemy wdrożyć w algorytmach klastrowania w celu pomiaru jakości modelu -

Analiza sylwetki

Analiza sylwetki służy do sprawdzenia jakości modelu skupień poprzez pomiar odległości między skupieniami. Zasadniczo zapewnia nam sposób oceny parametrów, takich jak liczba klastrów za pomocąSilhouette score. Wynik ten mierzy, jak blisko każdego punktu w jednym klastrze znajduje się punkt w sąsiednich klastrach.

Analiza wyniku sylwetki

Zakres punktacji Silhouette to [-1, 1]. Jego analiza jest następująca -

  • +1 Score - Blisko +1 Silhouette score wskazuje, że próbka jest daleko od sąsiedniego skupienia.

  • 0 Score - 0 Silhouette score wskazuje, że próbka znajduje się na granicy decyzyjnej oddzielającej dwa sąsiednie klastry lub bardzo blisko niej.

  • -1 Score & minusl -1 Silhouette score wskazuje, że próbki zostały przypisane do niewłaściwych klastrów.

Obliczenie wyniku Silhouette można wykonać za pomocą następującego wzoru -

= (-) / (,)

Tutaj = średnia odległość do punktów w najbliższym klastrze

I = średnia odległość wewnątrz klastra do wszystkich punktów.

Indeks Davisa-Bouldina

Indeks bazy danych to kolejna dobra miara do przeprowadzania analizy algorytmów klastrowania. Za pomocą indeksu DB możemy zrozumieć następujące punkty dotyczące modelu klastrowania -

  • Czy gromady są odpowiednio oddalone od siebie, czy nie?

  • Jak bardzo gęste są klastry?

Możemy obliczyć indeks DB za pomocą następującego wzoru -

$$ DB = \ Frac {1} {n} \ Displaystyle \ suma \ limit_ {i = 1} ^ n max_ {j \ neq {i}} \ lewo (\ Frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ right) $$

Tutaj = liczba klastrów

σ i = średnia odległość wszystkich punktów w klastrze od środka ciężkości gromady.

Im mniej indeksu DB, tym lepszy jest model klastrowy.

Dunn Index

Działa tak samo jak indeks DB, ale są następujące punkty, w których oba się różnią -

  • Indeks Dunn bierze pod uwagę tylko najgorszy przypadek, tj. Klastry, które są blisko siebie, podczas gdy indeks DB uwzględnia rozproszenie i separację wszystkich klastrów w modelu skupień.

  • Indeks Dunn rośnie wraz ze wzrostem wydajności, podczas gdy indeks DB staje się lepszy, gdy klastry są dobrze rozmieszczone i gęste.

Możemy obliczyć indeks Dunna za pomocą następującego wzoru -

$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$

Tutaj ,, = każdy indeks dla klastrów

= odległość między klastrami

q = odległość wewnątrz klastra

Typy algorytmów klastrowania ML

Poniżej przedstawiono najważniejsze i przydatne algorytmy klastrowania ML -

Grupowanie środków K

Ten algorytm grupowania oblicza centroidy i wykonuje iteracje, aż znajdziemy optymalną centroidę. Zakłada, że ​​liczba klastrów jest już znana. Jest również nazywany algorytmem płaskiego klastrowania. Liczba klastrów zidentyfikowanych na podstawie danych przez algorytm jest reprezentowana przez „K” w K-średnich.

Algorytm zmiany średniej

Jest to kolejny potężny algorytm klastrowania używany w uczeniu się bez nadzoru. W przeciwieństwie do grupowania K-średnich, nie przyjmuje żadnych założeń, dlatego jest algorytmem nieparametrycznym.

Klastrowanie hierarchiczne

Jest to kolejny nienadzorowany algorytm uczenia się, który służy do grupowania nieoznaczonych punktów danych o podobnych cechach.

W następnych rozdziałach szczegółowo omówimy wszystkie te algorytmy.

Zastosowania klastrowania

Klastrowanie może być przydatne w następujących obszarach -

Data summarization and compression- Klastrowanie jest szeroko stosowane w obszarach, w których potrzebujemy podsumowania, kompresji i redukcji danych. Przykładami są przetwarzanie obrazu i kwantyzacja wektorowa.

Collaborative systems and customer segmentation - Ponieważ tworzenie klastrów może być wykorzystywane do wyszukiwania podobnych produktów lub tego samego rodzaju użytkowników, może być stosowane w obszarze systemów współpracy i segmentacji klientów.

Serve as a key intermediate step for other data mining tasks- Analiza skupień może wygenerować zwięzłe podsumowanie danych do klasyfikacji, testowania, generowania hipotez; w związku z tym służy jako kluczowy etap pośredni również dla innych zadań eksploracji danych.

Trend detection in dynamic data - Klastrowanie może być również używane do wykrywania trendów w danych dynamicznych poprzez tworzenie różnych klastrów podobnych trendów.

Social network analysis- Klastrowanie może być używane w analizie sieci społecznościowych. Przykładami są generowanie sekwencji w obrazach, filmach lub audio.

Biological data analysis - Klastrowanie może być również wykorzystywane do tworzenia klastrów obrazów, filmów, dzięki czemu może być z powodzeniem wykorzystywane w analizie danych biologicznych.