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

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

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? ). $k$$k$

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. $10$$k$$k$

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,\ \sqrt{\sum D}]$

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:$k$$k$Jak zrozumieć wady K-środków ).

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 masz$N$ punkty danych, powinieneś mieć $0.5\cdot N\cdot(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żone$\frac 1 6$, który pochodzi z $\int_{x_i=0}^1\int_{x_j=0}^1 (x_i-x_j)^2 dx_i dx_j$. 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))
}