Skąd mam wiedzieć, że mój algorytm grupowania k-średnich cierpi z powodu przekleństwa wymiarowości?

12

Uważam, że tytuł tego pytania mówi wszystko.

Mathieu
źródło
3
Myślę, że będziesz musiał wyjaśnić nam, co rozumiesz przez symptom.
mdewey
Jeśli „symptom” jest wersją „testu” z odręcznym sprawdzaniem, być może mógłbyś wziąć podpróbki zestawu danych - być może 66% wielkości próbki, przeprowadzić analizę (w twoim przypadku kmeans), a następnie zobaczyć, jak nerwowy wyniki są. Na przykład można zobaczyć, jak często poszczególne obserwacje są przypisywane do tego samego klastra. Z drugiej strony może to nie być warte wysiłku. Jeśli martwisz się możliwością wystąpienia problemu z wymiarowością, prawdopodobnie masz taki problem. Możesz rozważyć inne metody grupowania, które nieco zmniejszają wymiarowość.
generic_user
@generic_user, gdyby ten komentarz był odpowiedzią, liczyłbym go jako odpowiedź zaakceptowaną :)
mathieu
1
To pytanie jest wystarczająco jasne, aby pozostać otwarte, IMO.
Gung - Przywróć Monikę
1
Często napotykasz znacznie poważniejsze problemy k-średnich wcześniej niż „przekleństwo wymiarowości”. K-średnich może pracować na danych 128-wymiarowych (np. wektory kolorów SIFT), jeśli atrybuty mają dobrą naturę. Do pewnego stopnia może czasem działać nawet na 10000-wymiarowych danych tekstowych. Teoretyczny model klątwy nigdy nie dotyczy prawdziwych danych. Większe problemy to nieporównywalne cechy, rzadkość i niemożność wizualizacji i dwukrotnego sprawdzenia wyniku.
Ma ZAKOŃCZENIE - Anony-Mousse

Odpowiedzi:

18

Pomaga myśleć o tym, czym jest Klątwa Wymiarowości . Istnieje kilka bardzo dobrych wątków w CV, które warto przeczytać. Oto miejsce na początek: wyjaśnij dziecku „Klątwę wymiarowości” .

Zwracam uwagę, że jesteś zainteresowany tym, jak to dotyczy klastrowania oznacza. Warto pamiętać, że oznacza oznacza strategię wyszukiwania, która minimalizuje (tylko) kwadratową odległość euklidesową. W związku z tym warto zastanowić się, w jaki sposób odległość euklidesowa odnosi się do przekleństwa wymiarowości (patrz: Dlaczego odległość euklidesowa nie jest dobrą miarą w dużych wymiarach? ). kk

Krótka odpowiedź z tych wątków jest taka, że ​​objętość (rozmiar) przestrzeni rośnie w niewiarygodnym tempie w stosunku do liczby wymiarów. Nawet wymiarów (co wydaje mi się, że nie jest to dla mnie bardzo „wielowymiarowe”) może przynieść klątwę. Jeśli dane zostały rozmieszczone równomiernie w tej przestrzeni, wszystkie obiekty stały się w przybliżeniu jednakowo oddalone od siebie. Jednak, jak zauważa @ Anony-Mousse w swojej odpowiedzi na to pytanie, zjawisko to zależy od tego, jak dane są rozmieszczone w przestrzeni; jeśli nie są jednolite, niekoniecznie masz ten problem. Prowadzi to do pytania, czy równomiernie rozmieszczone wysokowymiarowe dane są w ogóle bardzo powszechne (patrz: Czy „przekleństwo wymiarowości” naprawdę istnieje w rzeczywistych danych? ). 10

Twierdziłbym, że liczy się niekoniecznie liczba zmiennych (dosłowna wymiarowość danych), ale efektywna wymiarowość danych. Przy założeniu, że wymiarów jest „zbyt wysoki” dla średnich, najprostszą strategią byłoby policzenie liczby posiadanych funkcji. Ale jeśli chcesz myśleć o efektywnej wymiarowości, możesz przeprowadzić analizę podstawowych składników (PCA) i sprawdzić, jak wypadają wartości własne. Często jest tak, że większość odmian występuje w kilku wymiarach (które zazwyczaj przecinają oryginalne wymiary zestawu danych). Oznaczałoby to, że rzadziej masz problem z średnimi w tym sensie, że twoja efektywna wymiarowość jest w rzeczywistości znacznie mniejsza. 10kk

Bardziej zaangażowanym podejściem byłoby zbadanie rozkładu odległości parami w zbiorze danych wzdłuż linii sugerowanych w jego odpowiedzi @ hxd1011 . Patrząc na proste rozkłady krańcowe da ci pewną wskazówkę co do możliwej jednolitości. Jeśli znormalizujesz wszystkie zmienne, aby mieściły się w przedziale , odległości parami muszą mieścić się w przedziale . Wysoko skoncentrowane odległości spowodują problemy; z drugiej strony może być nadzieja na dystrybucję multimodalną (możesz zobaczyć przykład w mojej odpowiedzi tutaj: Jak używać jednocześnie zmiennych binarnych i ciągłych w grupowaniu? ).[0, 1][0, re]

Jednak to, czy „ oznacza „zadziała”, jest wciąż skomplikowanym pytaniem. Przy założeniu, że w twoich danych są znaczące utajone grupowania, niekoniecznie istnieją one we wszystkich twoich wymiarach lub w wymiarach konstruowanych, które maksymalizują zmienność (tj. Podstawowe składniki). Klastry mogą mieć wymiary o mniejszej zmienności (patrz: przykłady PCA, w których komputery o niskiej wariancji są „przydatne” ). Oznacza to, że możesz mieć klastry z punktami, które są blisko siebie i są dobrze oddzielone tylko na kilku twoich wymiarach lub na komputerach o mniejszej zmienności, ale nie są zdalnie podobne na komputerach o dużej zmienności, co spowodowałoby średnie aby zignorować poszukiwane klastry i zamiast tego wybrać sztuczne klastry (niektóre przykłady można zobaczyć tutaj:kkJak zrozumieć wady K-środków ).

gung - Przywróć Monikę
źródło
Okazuje się, że istnieje już znacznik do różnorodnego uczenia się (powinien był najpierw zajrzeć!). Podsumowując, dla tych, którzy mogą nie wiedzieć, chodzi o to, że chociaż dane wielowymiarowe są raczej rzadkie pod względem całej przestrzeni, mogą być gęste na niektórych hiperpowierzchniach w tej przestrzeni.
GeoMatt22,
+1 za doskonałą odpowiedź. Czy mógłbyś bardziej szczegółowo rozwinąć część dotyczącą wartości własnych? Jeśli efektywna wymiarowość jest niewielka, to czy zalecamy wykonanie PCA i zachowanie tylko pierwszych kilku wyników z wysokimi wartościami własnymi?
DataD'oh
@ DataD'oh, to z pewnością jedna możliwość, ale mówię, że nie musisz tego robić. W efekcie dane nie są wielowymiarowe (gdy tylko kilka pierwszych wektorów własnych ma wysokie wartości własne), więc niekoniecznie musisz nic robić - przekleństwo wymiaru po prostu się nie zastosuje.
Gung - Przywróć Monikę
@gung Wysłałem nowe pytanie . Mam nadzieję, że nie jest to zbyt trywialne.
DataD'oh
7

Moja odpowiedź nie ogranicza się do środków K, ale sprawdź, czy mamy przekleństwo wymiarowości dla metod opartych na odległości. Średnie K opiera się na pomiarze odległości (na przykład odległości euklidesowej)

Przed uruchomieniem algorytmu możemy sprawdzić rozkład metryki odległości, tj. Wszystkie metryki odległości dla wszystkich par danych. Jeśli maszN. punkty danych, powinieneś mieć 0,5N.(N.-1)wskaźniki odległości. Jeśli dane są zbyt duże, możemy sprawdzić ich próbkę.

Jeśli mamy problem przekleństwa wymiarowości, zobaczycie, że wartości te są bardzo do siebie zbliżone. Wydaje się to bardzo sprzeczne z intuicją, ponieważ oznacza, że ​​każdy jest blisko lub daleko od każdego, a pomiar odległości jest w zasadzie bezużyteczny.


Oto niektóre symulacje pokazujące takie sprzeczne z intuicją wyniki. Jeśli wszystkie funkcje są równomiernie rozmieszczone, a jeśli ma zbyt wiele wymiarów, wszystkie wskaźniki odległości powinny być zbliżone16, który pochodzi z xja=01xjot=01(xja-xjot)2)rexjarexjot. Możesz zmienić jednolity rozkład na inne rozkłady. Na przykład, jeśli przejdziemy do rozkładu normalnego (zmień runifna rnorm), zbieżnie do innej liczby o dużych wymiarach liczbowych.

Oto symulacja wymiaru od 1 do 500, cechy są równomiernie rozmieszczone od 0 do 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}

wprowadź opis zdjęcia tutaj

Haitao Du
źródło
1
Co jest P.?
ameba
1
Głosowałem za tym, ponieważ demonstrowałem zjawisko skurczu euklidesowego w dużych wymiarach. Ale odpowiedź nie pokazuje cierpienia k-średnich skupionych od klątwy. Cierpienie oznaczałoby, że w wysokich wymiarach stosunkowo dobrze rozdzielone klastry (i niejednolite losowe dane, takie jak twoje) mogą nie zostać odkryte z takim samym powodzeniem, jak w małych wymiarach. Nie dotknąłeś tego tematu.
ttnphns
@ameba P.jest liczbą wymiarów. Przejrzę fabułę i dodam kod. Dzięki.
Haitao Du
@ttnphns dzięki za komentarz i głosowanie. Zobaczę, czy mogę dodać jeden akapit, aby omówić wpływ na środki k.
Haitao Du