Wybór metody grupowania

73

Używając analizy skupień w zbiorze danych do grupowania podobnych przypadków, należy wybierać spośród wielu metod grupowania i miar odległości. Czasami jeden wybór może wpływać na drugi, ale istnieje wiele możliwych kombinacji metod.

Czy ktoś ma jakieś zalecenia dotyczące wyboru różnych algorytmów / metod grupowania i pomiarów odległości ? W jaki sposób jest to związane z charakterem zmiennych (np. Kategorycznym lub liczbowym) i problemem klastrowania? Czy istnieje optymalna technika?

Brett
źródło
1
Czy możesz spróbować podać bardziej szczegółowy opis tego, co chcesz połączyć? czy jest to tylko najnowocześniejszy sposób tworzenia klastrów, którego potrzebujesz?
robin girard
2
Nie mam na myśli natychmiastowej aplikacji. Interesuje mnie tylko ogólne podejście do wyboru metody klastrowania i miary podobieństwa.
Brett,
Sprawdź także to podobne pytanie.
ttnphns
I pewne zastrzeżenia wrt specjalnie hierarchiczne metody grupowania.
ttnphns

Odpowiedzi:

43

Nie ma ostatecznej odpowiedzi na twoje pytanie, ponieważ nawet w ramach tej samej metody wybór odległości do reprezentowania (dis) podobieństwa może dać różne wyniki, np. Przy użyciu euklidesa w porównaniu do kwadratu euklidesa w hierarchicznym grupowaniu. Jako inny przykład w przypadku danych binarnych można wybrać indeks Jaccard jako miarę podobieństwa i przejść do klasycznego hierarchicznego grupowania; ale istnieją alternatywne podejścia, takie jak Mona ( analiza monotetyczna), który uwzględnia tylko jedną zmienną na raz, podczas gdy inne podejścia hierarchiczne (np. klasyczne HC, Agnes, Diana) używają wszystkich zmiennych na każdym etapie. Podejście k-średnich zostało rozszerzone na różne sposoby, w tym dzielenie wokół medoidów (PAM) lub reprezentatywnych obiektów zamiast centroidów (Kaufman i Rousseuw, 1990), lub rozmytego grupowania (Chung i Lee, 1992). Na przykład główna różnica między średnimi k i PAM polega na tym, że PAM minimalizuje sumę różnic, a nie sumę kwadratowych odległości euklidesowych; rozmyte grupowanie pozwala rozważyć „częściowe członkostwo” (do każdej obserwacji przypisujemy wagę odzwierciedlającą członkostwo klasowe). A dla metod opartych na strukturze probabilistycznej lub tak zwanym klastrowaniu opartym na modelu (lub analizie profilu utajonego)dla psychometrów), jest świetny pakiet: Mclust . Tak więc definitywnie musisz rozważyć, jak zdefiniować podobieństwo jednostek, a także metodę łączenia jednostek ze sobą (rekurencyjne lub iteracyjne grupowanie, ścisłe lub rozmyte członkostwo w klasie, podejście bez nadzoru lub częściowo nadzorowane itp.).

Zwykle, aby ocenić stabilność klastra, interesujące jest porównanie kilku algorytmów, które w zasadzie „dzielą” pewne podobieństwo (np. K-średnie i hierarchiczne grupowanie, ponieważ odległość euklidesowa działa dla obu). W celu oceny zgodności między dwoma rozwiązaniami klastrowymi zasugerowano kilka wskazówek w odpowiedzi na to pytanie: Gdzie wyciąć dendrogram? (patrz także odsyłacze do innych linków na tej stronie). Jeśli używasz R, zobaczysz, że kilka pakietów jest już dostępnych w Widoku zadań na analizie skupień, a kilka pakietów zawiera winiety, które wyjaśniają określone metody lub zapewniają studia przypadków.

Analiza skupień: podstawowe pojęcia i algorytmy zapewnia dobry przegląd kilku technik stosowanych w analizie skupień. Jeśli chodzi o dobrą dobrą książkę z ilustracjami R, poleciłbym rozdział 12 Izenmana, Nowoczesne wielowymiarowe techniki statystyczne (Springer, 2008). Kilka innych standardowych odniesień podano poniżej:

  • Cormack, R., 1971. Przegląd klasyfikacji. Journal of Royal Statistics Society, A 134, 321–367.
  • Everitt, B., 1974. Analiza skupień . Londyn: Heinemann Educ. Książki
  • Gordon, A., 1987. Przegląd hierarchicznej klasyfikacji. Journal of Royal Statistics Society, A 150, 119–137.
  • Gordon, A., 1999. Klasyfikacja , wydanie drugie. Chapman and Hall.
  • Kaufman, L., Rousseuw, P., 1990. Znajdowanie grup w danych: wprowadzenie do analizy skupień . Nowy Jork, Wiley.
chl
źródło
30

Cytat Hastie, Tibshirani i Friedman, Elements of Statistics Learning , s. 506:

„Odpowiednia miara podobieństwa jest o wiele ważniejsza dla osiągnięcia sukcesu w klastrowaniu niż wybór algorytmu klastrowania. Ten aspekt problemu ... zależy od wiedzy specyficznej dla danej dziedziny i jest mniej podatny na ogólne badania”.

(To powiedziawszy, czy nie byłoby miło, gdyby (wibni) istniała strona, na której uczniowie mogliby wypróbować kilka algorytmów i wskaźników na kilku małych standardowych zestawach danych?)

denis
źródło
Dzięki chi; czy możesz zasugerować tag dla „przykładów można uruchomić w sieci”?
denis
Masz na myśli zmianę tagu pytania (nie sądzę, aby to był dobry pomysł, ponieważ OP nie było po narzędziach do testowania online, IMO) lub nowego pytania, które chcesz zadać? W każdym razie nie mam obecnie pomysłu na dobry tag. Zapytaj na Meta?
chl
1
Ten cytat może być mylący - najwyraźniej nie odnosi się do (co prawda wymyślonych) przykładów na wikipedii . Ze względu na silny klaster nieliniowy w drugim zbiorze danych algorytmy łączenia i grupowania gęstości działają znacznie lepiej niż jakakolwiek metoda oparta na centroidach. Nie ma miary podobieństwa, która sprawiłaby, że schemat grupowania centroidów działa lepiej. Ten cytat ma zastosowanie tylko wtedy, gdy założysz, że klastry są z grubsza liniowe (czasem bezpieczne założenie). Jeśli to możliwe, sugeruję najpierw sprawdzenie wizualne danych.
naught101
@ naught101, na pewno - wizualnie inspekcji dane do zobaczyć podobieństwa / odmienność jest najważniejsze, ale łatwiej powiedzieć niż zrobić
denis
ten cytat pochodzi z którego wydania? czy możesz podać jej cytat
MonsterMMORPG
12

Nie możesz z góry wiedzieć, który algorytm grupowania byłby lepszy, ale istnieją pewne wskazówki, na przykład jeśli chcesz grupować obrazy, istnieją pewne algorytmy, które powinieneś wypróbować jak Fuzzy Art, lub jeśli chcesz grupować twarze, powinieneś zacząć z globalnym klastrem geometrycznym (GGCI) dla obrazu.

W każdym razie nie gwarantuje to najlepszego wyniku, więc chciałbym użyć programu, który pozwala metodycznie uruchamiać różne algorytmy klastrowe, takie jak weka, RapidMiner lub nawet R (który nie jest wizualny), a tam ustawię program na uruchomić wszystkie różne algorytmy klastrowania, które mogę, przy wszystkich możliwych odległościach, a jeśli potrzebują parametrów, eksperymentuj z różnymi wartościami parametrów (poza tym, jeśli nie znam liczby klastrów, uruchom każdy z różnymi liczb tego). Po zakończeniu eksperymentu pozostaw go uruchomionym, ale pamiętaj, aby zapisać gdzieś wyniki każdego uruchomienia klastrowania.

Następnie porównaj wyniki w celu uzyskania najlepszego wynikowego grupowania. Jest to trudne, ponieważ istnieje kilka wskaźników, które można porównać i nie wszystkie są dostarczane przez każdy algorytm. Na przykład algorytmy rozmytego klastrowania mają inne metryki niż niezmydlone, ale nadal można je porównać, uznając uzyskane grupy rozmyte za niezmuzowane, pozostanę przy porównaniu do klasycznych metryk, takich jak:

• SSE: suma błędu kwadratowego z elementów każdego klastra.

• Odległość między klastrami: suma odległości kwadratowej między każdym środkiem ciężkości klastra.

• Odległość wewnątrz gromady dla każdej gromady: suma kwadratowej odległości od elementów każdej gromady do jej środka ciężkości.

• Maksymalny promień: największa odległość od instancji do środka ciężkości klastra.

• Średni promień: suma największej odległości od instancji do środka ciężkości klastra podzielona przez liczbę klastrów.

mariana bardziej miękka
źródło
4

Wybór właściwej odległości nie jest podstawowym zadaniem. Gdy chcemy przeprowadzić analizę skupień na zbiorze danych, różne wyniki mogą pojawić się przy różnych odległościach, dlatego bardzo ważne jest, aby uważać, w jakiej odległości wybrać, ponieważ możemy stworzyć fałszywie dobry artefakt, który dobrze uchwyci zmienność, ale w rzeczywistości bez sens w naszym problemie.

Odległość euklidesowa jest odpowiednia, gdy mam ciągłych zmiennych liczbowych i chcę, aby odzwierciedlić bezwzględne odległości. Odległość ta uwzględnia każdą zmienną i nie usuwa redundancji, więc gdybym miał trzy zmienne, które wyjaśniają to samo (są skorelowane), przypisałbym temu efektowi trzy. Co więcej, odległość ta nie jest niezmienna w skali, więc ogólnie muszę skalować wcześniej, aby użyć odległości.
Przykładowa ekologia: Mamy różne obserwacje z wielu miejsc, z których eksperci pobrali próbki niektórych czynników mikrobiologicznych, fizycznych i chemicznych. Chcemy znaleźć wzorce w ekosystemach. Czynniki te mają wysoką korelację, ale wiemy, że każdy jest istotny, więc nie chcemy usuwać tych zwolnień. Używamy odległości euklidesowej ze skalowanymi danymi, aby uniknąć efektu jednostek.

Odległość Mahalanobisa jest odpowiednia, gdy mam ciągłych zmiennych liczbowych i chcę, aby odzwierciedlić bezwzględne odległości, ale chcemy usunąć zwolnień. Jeśli powtórzymy zmienne, ich powtarzalny efekt zniknie.

Rodzina Hellinger , profil gatunku i odległość cięciwy są odpowiednie, gdy chcemy położyć nacisk na różnice między zmiennymi, gdy chcemy różnicować profile. Odległości te są wagami według całkowitych wielkości każdej obserwacji, w taki sposób, że odległości są małe, gdy zmienne po zmiennej osobniki są bardziej podobne, chociaż w absolutnych wielkościach były bardzo różne. Uważaj! Odległości te bardzo dobrze odzwierciedlają różnicę między profilami, ale straciły efekt wielkości. Mogą być bardzo przydatne, gdy mamy różne rozmiary próbek. Przykładowa ekologia: Chcemy badać faunę wielu ziem i mamy matrycę danych spisu ślimaka (miejsca pobierania próbek w rzędach i nazwy gatunków w kolumnach). Matryca charakteryzuje się wieloma zerami i różnymi wielkościami, ponieważ niektóre miejscowości mają niektóre gatunki, a inne mają inne gatunki. Przydałby się dystans Hellingera.

Bray-Curtis jest dość podobny, ale jest bardziej odpowiedni, gdy chcemy zróżnicować profile, a także wziąć pod uwagę względne wielkości.

Gonzalo Espinosa Duelo
źródło
1
Zarejestruj się i / lub połącz swoje konta 1 2 (informacje o tym, jak to zrobić, znajdziesz w sekcji Moje konto w naszym centrum pomocy ). Dzięki temu będziesz mógł śledzić swoje odpowiedzi, odpowiedzi na nie itp., A także inne korzyści. Ponieważ jesteś tutaj nowy, możesz wybrać się na naszą wycieczkę , która zawiera informacje dla nowych użytkowników.
gung
Wcześniej opublikowałeś identyczną odpowiedź stats.stackexchange.com/a/253268/3277 w podobnym temacie . Powielanie odpowiedzi nie jest uważane za uczciwe. Sugeruję usunięcie obecnego. Ale możesz i możesz opublikować link do swoich innych odpowiedzi - jako komentarz pod pytaniem PO lub bądź; odpowiedz na pytanie w bieżącym wątku.
ttnphns,
2

Jeśli chodzi o mnie, jeśli chcesz bezpiecznego wyboru, metody grupowania widmowego osiągają najwyższe wskaźniki dokładności w ostatnich latach - przynajmniej w przypadku grupowania obrazów.

Jeśli chodzi o metrykę odległości, wiele zależy od sposobu organizacji danych. Bezpiecznym wyborem jest prosta odległość euklidesowa, ale jeśli wiesz, że twoje dane zawierają rozmaitości, powinieneś zmapować punkty metodami jądra.

PS: wszystkie odnoszą się do wartości liczbowych, a nie do kategorii. Nie jestem pewien, jak można by przejść do grupowania danych kategorycznych.

felipeduque
źródło
2

Oto podsumowanie kilku algorytmów klastrowania, które mogą pomóc odpowiedzieć na pytanie

„której techniki klastrowania powinienem użyć?”

Nie ma obiektywnie „poprawnego” algorytmu grupowania Ref

Algorytmy klastrowania można kategoryzować na podstawie ich „modelu klastrowego”. Algorytm zaprojektowany dla określonego rodzaju modelu na ogół zawiedzie na innym modelu. Na przykład, k-średnie nie może znaleźć klastrów niewypukłych, może znaleźć tylko klastry o kształcie okrągłym.

Dlatego zrozumienie tych „modeli klastrów” staje się kluczem do zrozumienia, jak wybrać spośród różnych algorytmów / metod klastrowania. Typowe modele klastrów obejmują:

[1] Modele łączności: buduje modele oparte na łączności na odległość. Np. Hierarchiczne grupowanie. Używane, gdy potrzebujemy różnych partycjonowania w zależności od wysokości cięcia drzewa. Funkcja R: hclust w pakiecie statystyk.

[2] Modele centroidów: buduje modele, reprezentując każdy klaster pojedynczym średnim wektorem. Używane, gdy potrzebujemy wyraźnego partycjonowania (w przeciwieństwie do rozmytego grupowania opisanego później). Funkcja R: kmeany w pakiecie statystyk.

[3] Modele dystrybucji: buduje modele na podstawie rozkładów statystycznych, takich jak wielowymiarowe rozkłady normalne stosowane przez algorytm maksymalizacji oczekiwań. Używany, gdy kształty skupień mogą być dowolne, w przeciwieństwie do k-średnich, które zakładają skupienia kołowe. Funkcja R: emcluster w pakiecie emcluster.

[4] Modele gęstości: buduje modele oparte na klastrach jako połączonych gęstych obszarach w przestrzeni danych. Np. DBSCAN i optyka. Używane, gdy kształty skupień mogą być dowolne, w przeciwieństwie do k-średnich, które zakładają okrągłe skupienia. Funkcja R dbscan w pakiecie dbscan.

[5] Modele podprzestrzeni: buduje modele na podstawie zarówno elementów klastra, jak i odpowiednich atrybutów. Np. Biclustering (znany również jako klastrowanie równoległe lub klastrowanie w dwóch trybach). Używany, gdy potrzebne jest jednoczesne grupowanie wierszy i kolumn. Funkcja R biclust w pakiecie biclust.

[6] Modele grup: buduje modele na podstawie informacji o grupowaniu. Np. Wspólne filtrowanie (algorytm rekomendujący). Funkcja R Polecający w pakiecie polecającym.

[7] Modele oparte na grafie: buduje modele oparte na klice. Algorytmy wykrywania struktury społeczności starają się znaleźć gęste podgrafy w grafach skierowanych lub niekierowanych. Np. Funkcja R klaster_walktrap w pakiecie igraph.

[8] Kohonen Samoorganizująca się mapa obiektów: buduje modele oparte na sieci neuronowej. Funkcja R som w pakiecie kohonen.

[9] Gromadzenie spektralne: buduje modele w oparciu o niewypukłą strukturę skupień lub gdy miara środka nie jest odpowiednim opisem pełnego skupienia. Funkcja R specc w pakiecie kernlab.

[10] Klastrowanie podprzestrzeni: w przypadku danych wielowymiarowych funkcje odległości mogą być problematyczne. modele klastrów zawierają odpowiednie atrybuty dla klastra. Np. Funkcja hddc w pakiecie R HDclassif.

[11] Grupowanie sekwencji: powiązane sekwencje grup. Pakiet rBlast.

[12] Propagacja powinowactwa: buduje modele w oparciu o przekazywanie komunikatów między punktami danych Nie wymaga określenia liczby klastrów przed uruchomieniem algorytmu. Jest lepszy w przypadku niektórych zadań związanych z wizją komputerową i biologią obliczeniową, np. Grupowaniem zdjęć ludzkich twarzy i identyfikowaniem regulowanych transkryptów, niż k-średnich, Ref Rpackage APCluster.

[13] Klastrowanie strumieniowe: buduje modele na podstawie stale przybywających danych, takich jak dane telefoniczne, transakcje finansowe itp. Np. Pakiet BIRCH R [ https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Grupowanie dokumentów (lub grupowanie tekstu): buduje modele oparte na SVD. Wykorzystano go w ekstrakcji tematów. Na przykład Carrot [ http://search.carrot2.org] to mechanizm klastrowania wyników wyszukiwania typu open source, który może grupować dokumenty w kategorie tematyczne.

[15] Model klasy utajonej: Odnosi zestaw obserwowanych zmiennych wielowymiarowych do zestawu zmiennych utajonych. LCA może być stosowane w filtrowaniu grupowym. Funkcja R Polecający w pakiecie polecający ma funkcję filtrowania grupowego.

[16] Biclustering: Służy do jednoczesnego grupowania wierszy i kolumn danych w dwóch trybach. Np. Biclust funkcji R w pakiecie biclust.

[17] Miękkie grupowanie (rozmyte grupowanie): Każdy obiekt należy do każdego skupienia w pewnym stopniu. Np. Funkcja R Fclust w pakiecie fclust.

deb2015
źródło