Metody nieparametryczne, takie jak K-Nearest-Neighbors w wysoko wymiarowej przestrzeni cech

Główna idea k-Nearest-Neighbor uwzględnia najbliższych punktów i decyduje o klasyfikacji danych większością głosów. Jeśli tak, to nie powinno mieć problemów z danymi o wyższych wymiarach, ponieważ metody takie jak mieszanie wrażliwe na lokalizację mogą skutecznie znaleźć najbliższych sąsiadów. $k$

Ponadto wybór funkcji w sieciach bayesowskich może zmniejszyć wymiar danych i ułatwić uczenie się.

Jednak niniejszy artykuł przeglądowy autorstwa Johna Lafferty w uczeniu statystycznym wskazuje, że uczenie się nieparametryczne w przestrzennych przestrzeniach cech jest nadal wyzwaniem i nierozwiązane.

Co idzie nie tak?

machine-learning artificial-intelligence Strin
źródło

Proszę podać pełne odniesienie do artykułu; autorzy wydają się w nim nie pojawiać (widocznie).

Raphael

Odpowiedzi:

Ten problem jest znany jako przekleństwo wymiarowości . Zasadniczo, gdy zwiększasz liczbę wymiarów, , punkty w przestrzeni zwykle stają się dalekie od wszystkich innych punktów. To sprawia, że podział przestrzeni (tak jak jest to konieczne do klasyfikacji lub grupowania) jest bardzo trudny. $d$

Możesz to zobaczyć bardzo łatwo. Wygenerowałem losowych punktów wymiarowych w jednostkowym hipersześcianie przy 20 równomiernie wybranych wartościach z . Dla każdej wartości obliczyłem odległość od pierwszego punktu do wszystkich innych i wziąłem średnią z tych odległości. Kreśląc to, widzimy, że średnia odległość rośnie wraz z wymiarowością, nawet jeśli przestrzeń, w której generujemy punkty w każdym wymiarze, pozostaje taka sama. $50$ $d$ $d$ $1..1000$ $d$

Średnia odległość a wymiarowość

Nacięcie
źródło

Oczywiście. Zwiększasz liczbę punktów w hipersferze o stałym promieniu wykładniczo w wymiarach, więc jeśli wybierzesz losowo 50 punktów równomiernie, musi się to zdarzyć. Dlatego jeśli twoje rozumowanie jest prawidłowe, partycjonowanie powinno stać się łatwe, jeśli mam wiele próbek; czy to tak?

Raphael

Wierzę, że masz odwrócone. Zwiększając wymiarowość, REDUKUJĘ liczbę punktów w hipersferze. Partycjonowanie staje się trudniejsze, ponieważ miara odległości zasadniczo traci swoje znaczenie (np. Wszystko jest daleko).

Nick

k

$k$

N^{n}

$\mathbb{N}^n$

| N^{n} \cap S_{n} (k) |

$|\mathbb{N}^n \cap S_n(k)|$

n

$n$

n

$n$

d

$d$

n << d

$n << d$

Nie widzę tego z definicji; wydaje się jednak, że jest to konwencja oparta na doświadczeniu.

Raphael

Nie jest to kompletna odpowiedź, ale cytowana strona Wikipedii stwierdza:

Dokładność algorytmu k-NN może zostać poważnie obniżona przez obecność hałaśliwych lub nieistotnych cech lub jeśli skale cech nie są zgodne z ich znaczeniem.

Prawdopodobieństwo tego wystąpienia wzrasta w obecności wielowymiarowych przestrzeni cech.

Dave Clarke
źródło

Ale myślę, że z PCA (analiza podstawowych składników) lub innymi metodami zmniejszania wymiarów i usuwania nieistotnych danych, k-NN może nadal działać. A strony Wikipedia oznaczają, że naiwna k-NN zawiedzie. To nie tłumaczy artykułu przeglądowego.

Strin,

PCA z pewnością może działać, ale nie we wszystkich sytuacjach.

Dave Clarke,