Przekleństwo wymiarowości: klasyfikator kNN

Czytam książkę Kevina Murphy'ego: Machine Learning - A probabilistic Perspective. W pierwszym rozdziale autor wyjaśnia przekleństwo wymiarowości i jest część, której nie rozumiem. Jako przykład autor stwierdza:

Zastanów się, czy dane wejściowe są równomiernie rozmieszczone wzdłuż sześcianu jednostki D-wymiarowej. Załóżmy, że szacujemy gęstość etykiet klas, powiększając hiper sześcian wokół x, aż będzie zawierać pożądaną część punktów danych. Oczekiwana długość krawędzi tego sześcianu to .$f$$e_D(f) = f^{\frac{1}{D}}$

To ostatnia formuła, której nie potrafię zrozumieć. wydaje się, że jeśli chcesz pokryć, powiedz, że 10% punktów niż długość krawędzi powinna wynosić 0,1 wzdłuż każdego wymiaru? Wiem, że moje rozumowanie jest błędne, ale nie rozumiem, dlaczego.

To jest dokładnie nieoczekiwane zachowanie odległości w dużych wymiarach. Dla 1 wymiaru masz interwał [0, 1]. 10% punktów znajduje się w segmencie o długości 0,1. Ale co się dzieje, gdy wzrasta wymiar przestrzeni cech?

To wyrażenie mówi ci, że jeśli chcesz mieć 10% punktów dla 5 wymiarów, musisz mieć długość dla kostki 0,63, w 10 wymiarach 0,79 i 0,98 dla 100 wymiarów.

Jak widać, w celu zwiększenia wymiarów należy odwrócić wzrok, aby uzyskać taką samą liczbę punktów. Co więcej, mówi ci, że większość punktów znajduje się na granicy sześcianu wraz ze wzrostem liczby wymiarów. Co jest nieoczekiwane.

Myślę, że najważniejsze jest to, że wyrażenie

na początku jest naprawdę stroma. Oznacza to, że rozmiar krawędzi, który będziesz musiał objąć określoną część objętości, drastycznie wzrośnie, szczególnie na początku. tzn. potrzebna krawędź stanie się absurdalnie duża wraz ze wzrostem$D$

Aby to jeszcze bardziej wyjaśnić, przypomnij sobie fabułę, którą pokazuje Murphy:

jeśli zauważysz, dla wartości nachylenie jest naprawdę duże, a zatem funkcja rośnie naprawdę gwałtownie na początku. Można to lepiej docenić, jeśli weźmiesz pochodną :$D > 1$$e_D(f)$

Ponieważ rozważamy tylko zwiększenie wymiaru (które są wartościami całkowitymi), dbamy tylko o wartości całkowite . Oznacza to, że . Rozważ wyrażenie dla krawędzi w następujący sposób:$D > 1$$1-D < 0$

Zauważa, że ​​podnosimy do mocy mniejszej niż 0 (tj. Ujemnej). Kiedy podnosimy liczbę do potęg ujemnych, w pewnym momencie robimy odwrotność (tj. ). Wykonanie odwrotności do liczby, która jest już naprawdę bardzo mała (przypominamy ponieważ rozważamy tylko ułamek objętości, ponieważ wykonujemy KNN, tj. najbliższych punktów danych z całkowitej liczby ), oznacza, że ​​liczba „rośnie los". W związku z tym otrzymujemy pożądane zachowanie, tj. Że wraz ze wzrostem moc staje się jeszcze bardziej ujemna, a zatem wymagana krawędź rośnie znacznie w zależności od tego, jak duże zwiększa wykładnik potęgi.$f$$x^{-1} = \frac{1}{x}$$f < 1$$k$$N$$D$$D$

(zauważ, że rośnie wykładniczo w porównaniu do podziału który szybko staje się nieistotny).$f^{1 - D}$$\frac{1}{D}$

Tak, więc jeśli masz kostkę jednostkową lub w twoim przypadku linię jednostkową, a dane są równomiernie rozmieszczone, musisz przejść na długość 0,1, aby przechwycić 10% danych. Teraz, gdy zwiększasz wymiary, zwiększa się D, co zmniejsza moc if mniejszą niż 1, wzrośnie, tak że jeśli D przejdzie w nieskończoność, musisz przejąć całą kostkę, e = 1.

Myślę, że dla kNN odległość odgrywa większą rolę. To, co dzieje się z (hiper) sześcianem, jest analogiczne do tego, co dzieje się z odległością między punktami. Wraz ze wzrostem liczby wymiarów rośnie stosunek między najbliższą odległością do średniej odległości - oznacza to, że najbliższy punkt znajduje się prawie tak daleko, jak punkt średni, wtedy ma tylko nieco większą moc predykcyjną niż punkt średni. Ten artykuł ładnie to wyjaśnia

Joel Grus dobrze opisuje ten problem w Data Science od zera. W tej książce oblicza średnią i minimalną odległość między dwoma punktami w przestrzeni wymiarowej wraz ze wzrostem liczby wymiarów. Obliczył 10 000 odległości między punktami, przy liczbie wymiarów od 0 do 100. Następnie przystępuje do wykreślania średniej i minimalnej odległości między dwoma punktami, a także stosunku najbliższej odległości do średniej odległości (Distance_Closest / Distance_Average) .

Na tych wykresach Joel wykazał, że stosunek najbliższej odległości do średniej odległości wzrósł od 0 przy 0 wymiarach do ~ 0,8 przy 100 wymiarach. I to pokazuje podstawowe wyzwanie związane z wymiarowością przy użyciu algorytmu k-najbliższych sąsiadów; wraz ze wzrostem liczby wymiarów i zbliżaniem się zbliżenia do średniej odległości 1 maleje moc predykcyjna algorytmu. Jeśli najbliższy punkt znajduje się prawie tak daleko jak punkt średni, to ma tylko nieco większą moc predykcyjną niż punkt średni.