Wybór właściwej metody łączenia dla hierarchicznego grupowania

Wykonuję hierarchiczne grupowanie danych zebranych i przetworzonych ze zrzutu danych reddit w Google BigQuery.

Mój proces jest następujący:

• Pobierz najnowsze 1000 postów w / r / politics
• Zbierz wszystkie komentarze
• Przetwarzaj dane i oblicz n x mmacierz danych (n: users / samples, m: posts / features)
• Oblicz macierz odległości dla grupowania hierarchicznego
• Wybierz metodę łączenia i przeprowadź hierarchiczne grupowanie
• Wykreśl dane jako dendrogram

Moje pytanie brzmi: jak określić najlepszą metodę łączenia ? Obecnie używam Ward, ale skąd mam wiedzieć, czy należy używać single, complete, averageitp?

Jestem bardzo nowy w tych sprawach, ale nie mogę znaleźć jasnej odpowiedzi w Internecie, ponieważ nie jestem pewien, czy istnieje. Co może być dobrym pomysłem na moją aplikację? Uwaga: dane są stosunkowo rzadkie w tym sensie, że n x mmatryca ma wiele zer (większość ludzi nie komentuje więcej niż kilku postów).

Przegląd metod

Krótkie odniesienie do niektórych metod łączenia hierarchicznej analizy skupień aglomeracyjnych (HAC).

Podstawowa wersja algorytmu HAC jest ogólna; sprowadza się to do aktualizowania, na każdym etapie, formuły znanej jako formuła Lance-Williamsa, bliskości między powstającą (połączoną z dwoma) gromadą a wszystkimi pozostałymi dotychczasowymi klastrami (w tym obiektami singleton). Istnieją implementacje nie wykorzystujące formuły Lance-Williamsa. Ale korzystanie z niego jest wygodne: pozwala kodować różne metody łączenia według tego samego szablonu.

Receptura zawiera kilka parametrów (alfa, beta, gamma). W zależności od metody powiązania parametry są ustawiane inaczej, więc rozpakowana formuła uzyskuje określony widok. Wiele tekstów na temat HAC pokazuje wzór, jego poglądy specyficzne dla metody i wyjaśnia metody. Polecam artykuły Janos Podani jako bardzo dokładne.

Miejsce i potrzeba różnych metod wynika z faktu, że bliskość (odległość lub podobieństwo) między dwoma skupieniami lub między gromadą a obiektem singletonowym można sformułować na wiele różnych sposobów. HAC łączy na każdym etapie dwa najbardziej zbliżone klastry lub punkty, ale problemem jest sformułowanie sposobu obliczenia wspomnianej wyżej bliskości w obliczu, że wejściowa macierz bliskości została zdefiniowana tylko pomiędzy obiektami singletonowymi.

Tak więc metody różnią się pod względem sposobu definiowania bliskości między dowolnymi dwoma klastrami na każdym etapie. „Współczynnik zderzenia” (dane wyjściowe w harmonogramie / historii aglomeracji i tworzący oś „Y” na dendrogramie) to tylko bliskość dwóch klastrów scalonych na danym etapie.

• Metoda pojedynczego połączenia lub najbliższego sąsiada . Odległość między dwoma skupieniami to odległość między dwoma najbliższymi obiektami. Ta wartość jest jedną z wartości macierzy wejściowej. Konceptualny metafora tego zbudowany z klastra, jego pierwowzór, jest widmo lub łańcuch . Łańcuchy mogą być proste lub krzywoliniowe lub mogą przypominać widok „płatka śniegu” lub „ameby”. Dwóch najbardziej odmiennych członków klastra może się bardzo różnić w porównaniu z dwoma najbardziej podobnymi. Metoda pojedynczego połączenia kontroluje tylko podobieństwo najbliższych sąsiadów.

• Metoda pełnego połączenia lub najdalszego sąsiada . Odległość między dwoma gromadami to odległość między ich dwoma najbardziej odległymi obiektami. Ta wartość jest jedną z wartości macierzy wejściowej. Metaforą tego zbudowanego gromady jest koło (w sensie hobby lub fabuły), w którym dwie najbardziej odległe od siebie członkowie nie mogą być znacznie bardziej odmienne niż inne dość odmienne pary (jak w kole). Takie klastry są „zwartymi” konturami według granic, ale niekoniecznie są zwarte wewnątrz.

• Metoda średniego powiązania między grupami (UPGMA). Odległość między dwoma skupieniami jest średnią arytmetyczną wszystkich bliskości między obiektami jednej, z jednej strony, a obiektami drugiej, z drugiej strony. Metafora tego zbudowanego z gromady jest dość ogólna, po prostu zjednoczona klasa lub zwarty kolektyw; a metoda jest często ustawiana jako domyślna w hierarhicznych pakietach klastrowych. Można wytwarzać klastry o różnych kształtach i konturach.

• Prosta średnia lub metoda równoważnego średniego wiązania między grupami (WPGMA) jest zmodyfikowaną poprzednią. Odległość między dwoma skupieniami jest średnią arytmetyczną wszystkich bliskości między obiektami jednej, z jednej strony, a obiektami drugiej, z drugiej strony; podczas gdy podgrupy, z których każdy z tych dwóch klastrów został niedawno połączony, wyrównywały wpływ na tę bliskość - nawet jeśli podgrupy różniły się liczbą obiektów.

• Metoda średniego powiązania wewnątrz grupy (MNDIS). Odległość między dwoma klastrami jest średnią arytmetyczną wszystkich bliskości w ich wspólnym klastrze. Ta metoda jest alternatywą dla UPGMA. Zwykle traci na tym pod względem gęstości skupienia, ale czasami odkryje kształty skupień, których UPGMA nie zrobi.

• Metoda Centroid (UPGMC). Odległość między dwoma gromadami to odległość między ich geometrycznymi centroidami: [kwadrat] odległość euklidesowa między nimi. Metaforą tego zbudowanego klastra jest bliskość platform (polityka). Podobnie jak w partiach politycznych, takie klastry mogą mieć ułamki lub „frakcje”, ale jeśli ich centralne postaci nie są od siebie oddalone, związek jest spójny. Klastry mogą być różne według zarysu.

• Mediana lub równowagowa metoda centroid (WPGMC) to zmodyfikowana poprzednia metoda. Odległość między dwoma gromadami to odległość między ich geometrycznymi centroidami ([kwadrat] odległość euklidesowa między nimi); podczas gdy centroidy są zdefiniowane w taki sposób, że podgrupy, z których ostatnio połączono każdą z tych dwóch gromad, wyrównywały wpływ na jej środek ciężkości - nawet jeśli podgrupy różniły się liczbą obiektów.

• Warda metodzie lub minimalny wzrost sumy-of-place (MISSQ), czasami błędnie nazywany „minimalna wariancja” metoda. Odległość między dwoma klastrami to wielkość, o jaką zsumowany kwadrat w ich zespole będzie większy niż łączny zsumowany kwadrat w tych dwóch klastrach:$SS_{12}-(SS_1+SS_2)$. (Między dwoma obiektami singletonowymi ta ilość = kwadratowa odległość euklidesowa /$2$.) Metaforą tego zbudowanego klastra jest typ . Intuicyjnie typ jest chmurą gęstszą i bardziej koncentryczną w kierunku jego środka, podczas gdy punktów krańcowych jest niewiele i można je stosunkowo swobodnie rozproszyć.

Niektóre spośród mniej znanych metod (patrz Podany J. Nowe kombinatoryczne metody grupowania // Vegetatio, 1989, 81: 61-77.) [Również zaimplementowane przeze mnie jako makro SPSS znalezione na mojej stronie]:

• Metoda minimalnej sumy kwadratów (MNSSQ). Odległość między dwoma klastrami to zsumowany kwadrat w ich wspólnym klastrze:$SS_{12}$. (Między dwoma obiektami singletonowymi ta ilość = kwadratowa odległość euklidesowa / $2$.)

• Metoda minimalnego wzrostu wariancji (MIVAR). Odległość między dwoma skupieniami jest wielkością, o jaką średni kwadrat w ich skupieniu będzie większy niż ważony (według liczby obiektów) uśredniony średni kwadrat w tych dwóch skupieniach: $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$. (Między dwoma obiektami singletonowymi ta ilość = kwadratowa odległość euklidesowa /$4$.)

• Metoda minimalnej wariancji (MNVAR). Odległość między dwoma klastrami jest średnim kwadratem ich wspólnego klastra:$MS_{12} = SS_{12}/(n_1+n_2)$. (Między dwoma obiektami singletonowymi ta ilość = kwadratowa odległość euklidesowa /$4$.).

Pierwsze 5 metod dopuszcza wszelkie pomiary bliskości (wszelkie podobieństwa lub odległości), a wyniki będą oczywiście zależeć od wybranego środka.

Ostatnie 6 metod wymaga odległości; i całkowicie poprawne będzie użycie z nimi tylko kwadratowych odległości euklidesowych , ponieważ metody te obliczają centroidy w przestrzeni euklidesowej. Dlatego odległości powinny być euklidesowe ze względu na poprawność geometryczną (te 6 metod nazywa się łącznie metodami łączenia geometrycznego ). W najgorszym przypadku możesz wprowadzić inne daneodległości przy przyjmowaniu bardziej heurystycznej, mniej rygorystycznej analizy. Teraz o tym „kwadracie”. Obliczenia centroidów i odchylenia od nich są najwygodniejsze matematycznie / programowo do wykonywania na kwadratowych odległościach, dlatego pakiety HAC zwykle wymagają wprowadzania i są dostrojone do przetwarzania kwadratów. Istnieją jednak implementacje - w pełni równoważne, ale nieco wolniejsze - oparte na wejściach niewymaganych odległości i wymagających ich; patrz na przykład implementacja „Ward-2” dla metody Warda. Powinieneś skonsultować się z dokumentacją swojego programu do tworzenia klastrów, aby wiedzieć, jakie - kwadratowe lub nie - odległości, jakich oczekuje na wejściu do „metody geometrycznej”, aby zrobić to dobrze.

Metody, które MNDIS, MNSSQ i MNVAR wymagają na etapach, oprócz samej aktualizacji formuły Lance-Williamsa, do przechowywania statystyki wewnątrz klastra (która zależy od metody).

Metody najczęściej stosowane w badaniach, w których gromady mają być stałymi mniej więcej okrągłymi chmurami, - są metodami średniego wiązania, kompletnej metody łączenia i metody Warda.

Metoda Warda jest najbliższa, pod względem właściwości i wydajności, klastrowaniu metodą K; mają tę samą funkcję celu - minimalizację puli SS wewnątrz klastra „na końcu”. Oczywiście K-oznacza (jest iteracyjny i jeśli ma przyzwoite początkowe centroidy) jest zwykle lepszym minimalizatorem tego niż Totem. Jednak Totem wydaje mi się nieco bardziej dokładny niż środki K w odkrywaniu gromad o nierównomiernych rozmiarach fizycznych (wariancjach) lub gromad rzucanych wokół przestrzeni bardzo nieregularnie. Metoda MIVAR jest dla mnie dziwna, nie wyobrażam sobie, kiedy mogłaby być zalecana, nie wytwarza wystarczająco gęstych klastrów.

Metody centroid, mediana, minimalny wzrost wariancji - mogą czasami dawać tak zwane odwrócenie : zjawisko, w którym dwie klastry łączone na pewnym etapie wydają się bliżej siebie niż pary klastrów scalane wcześniej. Wynika to z faktu, że metody te nie należą do tzw. Ultrametrycznych. Ta sytuacja jest niewygodna, ale teoretycznie jest OK.

Metody pojedynczego sprzężenia i środka ciężkości należą do tak zwanego kontraktowania przestrzeni lub „łączenia”. Oznacza to - z grubsza mówiąc - że mają tendencję do dołączania obiektów jeden po drugim do klastrów, a zatem wykazują względnie płynny wzrost krzywej „% skupionych obiektów”. Wręcz przeciwnie, metody pełnego łączenia, Totemu, sumy kwadratów, wzrostu wariancji i wariancji zwykle uzyskują znaczny udział obiektów skupionych nawet na wczesnych etapach, a następnie kontynuują scalanie jeszcze tych - dlatego ich krzywa „% skupionych obiektów ”Jest stromy od pierwszych kroków. Metody te nazywane są rozszerzaniem przestrzeni . Inne metody są pośrednie.

Elastyczne wersje . Dodając dodatkowy parametr do formuły Lance-Williansa, można sprawić, że metoda stanie się specjalnie dostosowująca się do jej kroków. Ten parametr wprowadza korektę dla obliczanej bliskości między klastrami, która zależy od wielkości (wielkości rozpakowania) klastrów. Znaczenie tego parametru polega na tym, że powoduje on, że metoda aglomeracji bardziej rozszerza przestrzeń lub kurczy się przestrzeń niż metoda standardowa. Najbardziej znanym dotychczas wdrażaniem elastyczności jest uśrednianie metod łączenia UPGMA i WPGMA (Belbin, L. i in. Porównanie dwóch podejść do Beta-elastycznego grupowania // Multivariate Behavioural Research, 1992, 27, 417–433. ).

Dendrogram. Na osi dendrogramu „Y” zazwyczaj wyświetlana jest odległość między łączącymi się klastrami - zgodnie z powyższymi metodami. Dlatego na przykład w metodzie centroidu zwykle mierzy się kwadrat do odległości (ostatecznie zależy to od pakietu i opcji) - niektóre badania nie są tego świadome. Ponadto, zgodnie z tradycją, metody oparte na wzroście nietrudności, takie jak Warda, zwykle pokazywane na dendrogramie, mają wartość skumulowaną - jest to wcześniej ze względów wygody niż teoretyczne. Tak więc (w wielu pakietach) wykreślony współczynnik w metodzie Warda reprezentuje ogólną, we wszystkich klastrach, sumę kwadratów wewnątrz klastra obserwowaną w momencie danego kroku.

Należy powstrzymać się od oceny, która metoda łączenia jest „lepsza” dla jego danych, porównując wygląd dendrogramów: nie tylko dlatego, że wygląd zmienia się, kiedy zmieniasz jaką modyfikację współczynnika na nim kreślisz - jak to właśnie opisano - ale dlatego, że wygląd będzie się różnił nawet w przypadku danych bez klastrów.

Aby wybrać „właściwą” metodę

Nie ma jednego kryterium. Niektóre wskazówki, jak przejść do wyboru metody analizy skupień (w tym w szczególności metody łączenia w HAC) zostały przedstawione w tej odpowiedzi i w całym wątku.

Korelacja między macierzą odległości a odległością fenenetyczną jest jedną miarą, która pomaga ocenić, które wiązanie klastrowe wybrać. Od ?cophenetic:

Można argumentować, że dendrogram jest odpowiednim podsumowaniem niektórych danych, jeśli korelacja między odległościami pierwotnymi a odległościami fenenetycznymi jest wysoka.

To zastosowanie cor(dist,cophenetic(hclust(dist)))jako metryki wyboru powiązania jest wymienione w str. 38 tej vegan winiety .

Zobacz przykładowy kod poniżej:

# Data
d0=dist(USArrests)

# Hierarchical Agglomerative Clustering
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Cophenetic Distances, for each linkage
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

# Correlations
cor(d0,c1) # 0.7658983
cor(d0,c2) # 0.7636926
cor(d0,c3) # 0.7553367
cor(d0,c4) # 0.5702505

# Dendograms
par(mfrow=c(2,2))
plot(h1,main='Average Linkage')
plot(h2,main='Complete Linkage')
plot(h3,main='Ward Linkage')
plot(h4,main='Single Linkage')
par(mfrow=c(1,1))

Widzimy, że korelacje averagei completesą bardzo podobne, a ich dendogramy wydają się bardzo podobne. Korelacja dla wardprzypomina averagei completenie dendrogram wygląda całkiem inaczej. singlepowiązanie robi swoje. Najlepszy profesjonalny osąd eksperta w danej dziedzinie lub pierwszeństwo w stosunku do określonego łącza w obszarze zainteresowania powinny prawdopodobnie zastąpić dane liczbowe cor().