Jak stwierdzić, czy dane są „klastrowane” wystarczająco, aby algorytmy klastrowania mogły dać znaczące wyniki?

78

Skąd miałbyś wiedzieć, czy twoje (wysokowymiarowe) dane wykazują wystarczającą liczbę klastrów, aby wyniki z kmeans lub innego algorytmu klastrowania były rzeczywiście znaczące?

W szczególności w przypadku algorytmu k-średnich, jak duże powinno być zmniejszenie wariancji wewnątrz klastra, aby rzeczywiste wyniki grupowania były znaczące (a nie fałszywe)?

Czy klastrowanie powinno być widoczne, gdy drukowana jest forma danych o zmniejszonych wymiarach, i czy wyniki z kmeans (lub innych metod) są bez znaczenia, jeśli klastrowania nie można wizualizować?

xuexue
źródło
1
Odręczne cyfry stanowią dobry test dla grupowania: można by oczekiwać 10 dobrze oddzielonych klastrów, ale to wcale nie pokazuje kolana przy k = 10, przynajmniej w metodzie euklidesowej w 64d.
denis
Zobacz także stackoverflow.com/q/15376075/134830
Richie Cotton
2
Pytanie to wiąże się w pewnym stopniu z pytaniem, jak sprawdzić poprawność wyników grupowania i jak wybrać „lepszą” metodę. Zobacz np . Stats.stackexchange.com/q/195456/3277 .
ttnphns,

Odpowiedzi:

77

W szczególności o k-średnich, możesz użyć statystyki Gap. Zasadniczo chodzi o obliczenie dobroci miary grupowania na podstawie średniej dyspersji w porównaniu z rozkładem odniesienia dla rosnącej liczby klastrów. Więcej informacji można znaleźć w oryginalnym artykule:

Tibshirani, R., Walther, G., i Hastie, T. (2001). Szacowanie liczby klastrów w zbiorze danych za pomocą statystyki luki . JR Statist. Soc. B, 63 (2): 411–423.

Odpowiedź, którą udzieliłem na powiązane pytanie, podkreśla inne ogólne wskaźniki poprawności, które mogą być użyte do sprawdzenia, czy dany zestaw danych wykazuje jakąś strukturę.

Jeśli nie masz pojęcia, czego byś się spodziewał, gdyby był tylko hałas, dobrym rozwiązaniem jest ponowne próbkowanie i badanie stabilności klastrów. Innymi słowy, ponownie próbkuj dane (przez bootstrap lub dodając do niego niewielki szum) i oblicz „bliskość” wynikowych partycji, mierzoną podobieństwami Jaccard . Krótko mówiąc, pozwala oszacować częstotliwość, z jaką podobne klastry były odzyskiwane w danych. Ta metoda jest łatwo dostępna w pakiecie fpc R jako clusterboot(). Bierze jako dane wejściowe albo surowe dane, albo macierz odległości i pozwala na zastosowanie szerokiego zakresu metod grupowania (metody hierarchiczne, średnie k, metody rozmyte). Metodę omówiono w powiązanych odnośnikach:

Hennig, C. (2007) Ocena stabilności skupień pod kątem klastrów . Statystyka obliczeniowa i analiza danych , 52, 258–271.

Hennig, C. (2008) Punkt rozpuszczania i odporność na izolację: kryteria odporności dla ogólnych metod analizy skupień . Journal of Multivariate Analysis , 99, 1154-1176.

Poniżej znajduje się mała demonstracja z algorytmem k-średnich.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Wyniki są dość pozytywne w tym sztucznym (i dobrze ustrukturyzowanym) zbiorze danych, ponieważ żaden z trzech klastrów ( krange) nie został rozpuszczony w próbkach, a średnie podobieństwo Jaccard w klastrze wynosi> 0,95 dla wszystkich klastrów.

Poniżej znajdują się wyniki dla 20 próbek bootstrap. Jak można zauważyć, jednostki statystyczne zwykle pozostają zgrupowane w tej samej grupie, z kilkoma wyjątkami dla obserwacji leżących pomiędzy nimi.

wprowadź opis zdjęcia tutaj

Możesz oczywiście rozszerzyć ten pomysł na dowolny indeks ważności: wybierz nową serię obserwacji za pomocą bootstrapu (z zamiennikiem), oblicz swoją statystykę (np. Szerokość sylwetki, korelację kopenetyczną, gamma Huberta, w ramach sumy kwadratów) dla zakresu liczby klastrów (np. 2 do 10), powtórz 100 lub 500 razy i spójrz na wykres pudełkowy swojej statystyki jako funkcję liczby klastrów.

Oto, co otrzymuję z tym samym symulowanym zestawem danych, ale używając hierarchicznego grupowania Warda i biorąc pod uwagę korelację kopenetyczną (która ocenia, jak dobrze odtwarzane są informacje o odległości w wynikowych partycjach) i szerokość sylwetki (miara kombinacji oceniająca jednorodność wewnątrz gromady i inter- separacja klastrowa).

Korelacja kopenetyczna wynosi od 0,6267 do 0,7511 z wartością mediany 0,7031 (500 próbek ładowania początkowego). Szerokość sylwetki wydaje się maksymalna, gdy weźmiemy pod uwagę 3 skupienia (mediana 0,8408, zakres 0,7371-0,8769).

wprowadź opis zdjęcia tutaj

chl
źródło
Dzięki za tę BARDZO pouczającą odpowiedź! Wygląda na to, że klasterboot jest dokładnie tym, czego szukam. Dziękujemy również za dołączenie linków.
xuexue
1
Niektóre magiczne liczby do interpretacji wartości sylwetki: stats.stackexchange.com/a/12923/12359
Franck Dernoncourt,
1
Jakich poleceń użyłeś do zbudowania tych wykresów w gifie?
Travis Heeter
2
@Travis Obrazy zostały zapisane jako osobne pliki PNG, a następnie przekonwertowane na animowany plik GIF za pomocą ImageMagick . Zobacz także ten post .
chl
10

Jednym ze sposobów szybkiego wizualizacji, czy dane wielowymiarowe wykazują wystarczającą liczbę klastrów, jest zastosowanie t-Distributed Stochastic Neighbor Embedding ( t-SNE ). Projektuje dane do niewielkiej przestrzeni (np. 2D, 3D) i całkiem nieźle radzi sobie z utrzymaniem struktury klastra, jeśli taka istnieje.

Np. Zestaw danych MNIST :

wprowadź opis zdjęcia tutaj

Zestaw danych Olivetti:

wprowadź opis zdjęcia tutaj

Franck Dernoncourt
źródło
1
Czy istnieje sposób na zastosowanie twarzy (lub jakichkolwiek obrazów) w R?
Travis Heeter
1
@TravisHeeter Nie wiem
Franck Dernoncourt
3
Nie grupuj rzutowanych danych tSNE. Zobacz np. Tę odpowiedź: stats.stackexchange.com/a/264647/7828
Anony-Mousse 10.10.17
9

Z pewnością zdolność do wizualnego rozróżniania klastrów w możliwej do wykreślenia liczbie wymiarów jest wątpliwym kryterium przydatności algorytmu klastrowania, szczególnie jeśli redukcja wymiarów odbywa się niezależnie od samego skupienia (tj. Próżna próba ustalenia, czy klastrowanie będzie działać).

W rzeczywistości metody grupowania mają największą wartość w znajdowaniu klastrów, w których ludzkie oko / umysł nie jest w stanie zobaczyć klastrów.

Prosta odpowiedź brzmi: zrób klastrowanie, a następnie dowiedz się, czy zadziałało (przy którymkolwiek z kryteriów, którymi jesteś zainteresowany, zobacz także odpowiedź @ Jeffa).

Nick Sabbe
źródło
1
Tak, a klastry niekoniecznie są ładnymi okrągłymi grupami punktów, co zasadniczo jest założeniem kmeans.
Wayne,
@chl Czy stworzyłeś ten animowany obraz za pomocą R?
Stéphane Laurent,
7

Kiedy w ogóle wyniki są znaczące ? W szczególności wyniki k-średnich?

Faktem jest, że k-znaczy optymalizuje pewną statystykę matematyczną. Nie ma z tym żadnego „znaczącego”.

W szczególności w przypadku danych wielowymiarowych pierwsze pytanie powinno brzmieć: czy odległość euklidesowa jest nadal znacząca ? Jeśli nie, nie używaj k-średnich. Odległość euklidesowa ma znaczenie w świecie fizycznym, ale szybko traci znaczenie, gdy masz inne dane. W szczególności, kiedy sztucznie przekształcasz dane w przestrzeń wektorową, czy jest jakiś powód, dla którego powinna to być euklidesowa?

Jeśli weźmiesz klasyczny „stary wierny” zestaw danych i uruchomisz na nim k-średnie bez normalizacji, ale z czystą odległością euklidesową, to już nie ma już znaczenia. EM, który w rzeczywistości wykorzystuje jakąś formę „klastrowego lokalnego” dystansu Mahalanobisa, będzie działał o wiele lepiej. W szczególności dostosowuje się do osi o bardzo różnych skalach.

Btw, kluczową siłą k-średnich jest to, że tak naprawdę zawsze dzieli dane na partycje, bez względu na to, jak to wygląda. Możesz użyć k-średnich, aby podzielić jednolity hałas na k klastrów . Można oczywiście twierdzić, że k-średnie klastry nie mają znaczenia. Lub można to zaakceptować jako: użytkownik chciał podzielić dane na partycje, aby zminimalizować kwadratowe odległości euklidesowe, bez wymagania, aby klastry były „znaczące”.

Anony-Mus
źródło
@ Anony-Mousse A przypadek użycia dla „równomiernego podziału hałasu na klastry”
CodeFarmer
Nie ma żadnego. Chodzi o to, że k-średnich to nie obchodzi, podzieli jednolite dane na „klastry”, tj. Produkuje bzdury.
Anony-Mousse
6

Niedawno zacząłem używać algorytmów klastrowania, więc mam nadzieję, że ktoś bardziej kompetentny może udzielić bardziej kompletnej odpowiedzi, ale oto kilka uwag:

„Sensowne”, jak jestem pewien, że wiesz, jest bardzo subiektywne. Zatem to, czy klastrowanie jest wystarczająco dobre, zależy całkowicie od tego, dlaczego musisz skupiać się w pierwszej kolejności. Jeśli próbujesz przewidzieć członkostwo w grupie, prawdopodobne jest, że każde grupowanie będzie lepsze niż przypadek (i nic gorszego), więc wyniki powinny być do pewnego stopnia znaczące.

Jeśli chcesz się dowiedzieć, na ile niezawodne jest to grupowanie, potrzebujesz danych, aby je porównać. Jeśli masz zestaw podmiotów o znanym członkostwie, możesz użyć analizy dyskryminacyjnej, aby sprawdzić, jak dobre były prognozy. Jeśli nie masz zestawu encji o znanych członkostwach, musisz wiedzieć, jaka wariancja jest typowa dla klastrów w swojej dziedzinie. Fizyczne atrybuty bytów o sztywnych kategoriach prawdopodobnie będą miały znacznie niższą wariancję wewnątrz grupy niż dane psychometryczne na ludziach, ale to niekoniecznie czyni „klastrowanie gorszym”.

Twoje drugie pytanie odnosi się do „Jaką wartość k wybrać?” Ponownie nie ma tutaj trudnej odpowiedzi. W przypadku braku jakiegokolwiek zestawu kategorii a priori prawdopodobnie chcesz zminimalizować liczbę klastrów, a jednocześnie zminimalizować średnią wariancję klastra. Prostym podejściem może być wykreślenie „liczby klastrów” względem „średniej wariancji klastra” i poszukiwanie „łokcia” - gdzie dodanie większej liczby klastrów nie ma znaczącego wpływu na wariancję klastra.

Nie powiedziałbym, że wyniki k-średnich są bez znaczenia, jeśli nie można ich wizualizować, ale z pewnością są atrakcyjne, gdy klastry są widoczne wizualnie. To znów prowadzi do pytania: dlaczego potrzebujesz grupować i jak wiarygodny musisz być? Ostatecznie jest to pytanie, na które należy odpowiedzieć w oparciu o sposób wykorzystania danych.

Jeff
źródło
3

Aby stwierdzić, czy klastrowanie jest znaczące, możesz uruchomić algorytm zliczający liczbę klastrów i sprawdzić, czy generuje coś większego niż 1.

kk

kk

raegtin
źródło