Przegląd hierarchicznej analizy skupień

Zanim zrozumiemy hierarchiczną analizę klastrów, spróbujmy zrozumieć, co to jest klaster? A czym jest analiza skupień? Klaster to zbiór obiektów danych; punkty danych w klastrze są bardziej do siebie podobne i niepodobne do punktów danych w drugim klastrze. Analiza klastrowa to w zasadzie zgrupowanie tych punktów danych w klastrze. Klastrowanie jest rodzajem algorytmu uczenia maszynowego bez nadzoru, w którym nie ma zestawów danych oznaczonych szkoleniem. Istnieją różne typy analizy skupień, jednym z nich jest hierarchiczna analiza skupień.

Hierarchiczne grupowanie pomoże w tworzeniu klastrów we właściwej kolejności / hierarchii. Przykład: najczęstszym codziennym przykładem jest sposób, w jaki porządkujemy nasze pliki i foldery na naszym komputerze według właściwej hierarchii.

Rodzaje hierarchicznego grupowania

Grupowanie hierarchiczne dzieli się ponadto na dwa typy, tj. Grupowanie aglomeracyjne i Grupowanie dzielące (DIANA)

Grupowanie aglomeracyjne

W przypadku klastrowania rozkład hierarchiczny odbywa się za pomocą strategii oddolnej, w której rozpoczyna się od utworzenia atomowych (małych) klastrów poprzez dodanie jednego obiektu danych na raz, a następnie łączy je ze sobą, tworząc na końcu duży klaster., gdzie klaster ten spełnia wszystkie warunki zakończenia. Ta procedura jest powtarzalna, dopóki wszystkie punkty danych nie zostaną umieszczone w jednym dużym klastrze.

AGNES (aglomeracyjny NESting) jest rodzajem skupienia aglomeracyjnego, który łączy obiekty danych w klaster na podstawie podobieństwa. Wynikiem tego algorytmu jest drzewna struktura o nazwie Dendrogram. W tym przypadku wykorzystuje metryki odległości, aby zdecydować, które punkty danych należy połączyć z którym klastrem. Zasadniczo konstruuje macierz odległości i sprawdza parę klastrów o najmniejszej odległości i łączy je.

Powyższy rysunek pokazuje grupowanie aglomeracyjne vs. dzielące

W oparciu o sposób pomiaru odległości między poszczególnymi skupieniami możemy zastosować 3 różne metody

  • Pojedyncze połączenie : gdzie najkrótsza odległość między dwoma punktami w każdym klastrze jest zdefiniowana jako odległość między klastrami.
  • Całkowite połączenie : W tym przypadku rozważymy najdłuższą odległość między punktami w każdym klastrze jako odległość między skupieniami.
  • Średnie powiązanie: weźmiemy średnią między każdym punktem w jednym klastrze do każdego innego punktu w drugim klastrze.

Porozmawiajmy teraz o mocnych i słabych stronach AGNES; algorytm ten ma złożoność czasową wynoszącą co najmniej O (n 2 ), dlatego nie radzi sobie dobrze w skalowaniu, a jedną kolejną poważną wadą jest to, że wszystko, co zostało zrobione, nigdy nie może zostać cofnięte, tj. jeśli niepoprawnie zgrupujemy dowolny klaster na wcześniejszym etapie algorytm wtedy nie będziemy w stanie zmienić wyniku / zmodyfikować go. Ale ten algorytm ma również jasną stronę, ponieważ powstaje wiele mniejszych klastrów, może być pomocny w procesie odkrywania i tworzy uporządkowanie obiektów, co jest bardzo pomocne w wizualizacji.

Divisive Clustering (DIANA)

Diana zasadniczo oznacza analizę dzielącą; jest to inny rodzaj hierarchicznego grupowania, w którym zasadniczo działa na zasadzie podejścia odgórnego (odwrotnego do AGNES), w którym algorytm rozpoczyna się od utworzenia dużego klastra i rekurencyjnie dzieli najbardziej odmienny klaster na dwa i trwa do momentu, gdy „ wszystkie podobne punkty danych należą do odpowiednich klastrów. Te algorytmy dzielące dają wysoce dokładne hierarchie niż podejście aglomeracyjne, ale są drogie obliczeniowo.

Powyższy rysunek pokazuje krok po kroku klastrowanie dzielące

Wielofazowe hierarchiczne grupowanie

Aby poprawić jakość klastrów generowanych przez wyżej wymienione hierarchiczne techniki klastrowania, integrujemy nasze hierarchiczne techniki klastrowania z innymi technikami klastrowania; nazywa się to klastrowaniem wielofazowym. Różne typy klastrowania wielofazowego są następujące:

  • BIRCH (Zrównoważone iteracyjne zmniejszanie i grupowanie przy użyciu hierarchii)
  • ROCK (klastrowanie RObust za pomocą linków)
  • KAMELEON

1. Zrównoważone iteracyjne zmniejszanie i grupowanie przy użyciu hierarchii

Ta metoda jest wykorzystywana głównie do grupowania ogromnej ilości danych liczbowych poprzez integrację naszego hierarchicznego / mikroplastra w początkowej fazie i makro klastrowania / iteracyjnego podziału w późniejszej fazie. Ta metoda pomaga przezwyciężyć problem skalowalności, z którym mieliśmy do czynienia w AGNES, oraz niemożność cofnięcia tego, co zostało zrobione przed krokiem. BIRCH wykorzystuje dwa ważne pojęcia w swoim algorytmie

za. Funkcja klastrowania (pomaga w podsumowaniu klastra)

CF jest zdefiniowany jako (n- liczba punktów danych w klastrze, suma liniowa n punktów, suma kwadratowa n punktów). Przechowywanie funkcji klastra w ten sposób pomaga uniknąć przechowywania szczegółowych informacji na jego temat, a CF ma charakter addytywny dla różnych klastrów.

CF 1 + CF 2 = 1+ n 2, LS 1 + LS 2, SS 1 + SS 2 >

b. Drzewo funkcji klastrowania (pomaga reprezentować klaster jako hierarchię)

Drzewo CF jest drzewem zrównoważonym o współczynniku rozgałęzienia B (maksymalna liczba dzieci) i progu T (maksymalna liczba podklastrów, które można przechowywać w węzłach liści).

Algorytm zasadniczo działa w 2 fazach; w fazie 1 skanuje bazę danych i buduje drzewo CF w pamięci, aw fazie 2 używa algorytmu klastrowania, który pomaga w klastrowaniu węzłów liści poprzez usuwanie elementów odstających (rzadkich klastrów) i grupuje klaster o maksymalnej gęstości. Jedyną wadą tego algorytmu jest to, że obsługuje on tylko numeryczny typ danych.

2. Solidne grupowanie za pomocą linków

Łącze definiuje się jako liczbę wspólnych sąsiadów między dwoma obiektami. Algorytm ROCK jest rodzajem algorytmu klastrowego, który wykorzystuje tę koncepcję połączenia z kategorycznym zestawem danych. Ponieważ wiemy, że algorytmy grupowania z pomiarem odległości nie zapewniają klastrów wysokiej jakości dla kategorycznego zestawu danych, ale w przypadku ROCK uwzględnia również sąsiedztwo punktów danych, tj. Jeśli dwa punkty danych mają to samo sąsiedztwo, wówczas są one najprawdopodobniej należeć do tego samego klastra. Algorytm zbuduje rzadki wykres w pierwszym etapie, biorąc pod uwagę macierz podobieństwa z koncepcją progu sąsiedztwa i podobieństwa. W drugim kroku wykorzystuje aglomeracyjną hierarchiczną technikę grupowania na rzadkim wykresie.

3. Kameleon

Ten typ hierarchicznego algorytmu klastrowego wykorzystuje koncepcję modelowania dynamicznego. Zastanawiasz się, dlaczego nazywa się to dynamicznym? Nazywa się to dynamicznym, ponieważ ma zdolność automatycznego dostosowywania się do wewnętrznych cech klastra poprzez ocenę podobieństwa klastra, tj. Tego, jak dobrze połączone punkty danych w klastrze i w pobliżu klastrów. Jedną z wad kameleona jest to, że koszt przetwarzania jest zbyt wysoki (O (n 2 ) dla n obiektów to złożoność czasu najgorszego przypadku).

Źródło obrazu - Google

Wniosek

W tym artykule dowiedzieliśmy się, czym jest klaster, a czym jest analiza klastra, różne rodzaje hierarchicznych technik klastrowania, ich zalety i wady. Każda z omawianych technik ma swoje plusy i minusy, dlatego zanim przejdziemy do algorytmu, musimy zrozumieć nasze dane z odpowiednią analizą danych eksploracyjnych i ostrożnie wybrać algorytm.

Polecane artykuły

Jest to przewodnik po hierarchicznej analizie klastrowej. Tutaj omawiamy przegląd, grupowanie aglomeracyjne, klastrowanie dzielące (DIANA) i hierarchiczne grupowanie wielofazowe. Możesz także przejrzeć poniższe artykuły, aby dowiedzieć się więcej

  1. Hierarchiczne grupowanie w R.
  2. Algorytm grupowania
  3. klastry
  4. Metody grupowania
  5. Grupowanie w uczenie maszynowe
  6. Hierarchiczne grupowanie | Grupowanie aglomeracyjne i dzielące

Kategoria:

Big Data