Radzenie sobie z powiązaniami, wagami i głosowaniem w kNN

Programuję algorytm kNN i chciałbym wiedzieć, co następuje:

Przerwy w remisie:

1. Co się stanie, jeśli w głosowaniu większościowym nie będzie wyraźnego zwycięzcy? Np. Wszyscy k najbliżsi sąsiedzi należą do różnych klas, czy dla k = 4 są 2 sąsiedzi z klasy A i 2 sąsiedzi z klasy B?
2. Co się stanie, jeśli nie będzie możliwe określenie dokładnie k najbliższych sąsiadów, ponieważ jest więcej sąsiadów o tej samej odległości? Np. Dla listy odległości (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2)nie byłoby możliwe określenie k = 3 lub k = 4 najbliższych sąsiadów, ponieważ wszyscy sąsiedzi od 3 do 5 mają taką samą odległość.

Wagi:

1. Czytam, że dobrze jest zważyć najbliższych sąsiadów k przed wybraniem zwycięskiej klasy. Jak to działa? Tj. W jaki sposób są ważeni sąsiedzi i w jaki sposób określa się klasę?

Większość głosów w wyborach:

1. Czy istnieją inne zasady / strategie określające zwycięską klasę niż głosowanie większością?

Idealnym sposobem na przełamanie krawata dla k najbliższego sąsiada moim zdaniem byłoby zmniejszyć k o 1, dopóki nie złamał krawata. To zawsze będzie działać bez względu na schemat ważenia głosów, ponieważ remis jest niemożliwy, gdy k = 1. Jeśli miałbyś zwiększyć k , do czasu twojego schematu ważenia i liczby kategorii, nie byłbyś w stanie zagwarantować zerwania remisu.

Robiąc kNN, musisz pamiętać o jednej rzeczy, a mianowicie, że nie jest to algorytm ściśle matematyczny, ale raczej prosty klasyfikator / regresor oparty na jednej intuicji - podstawowa funkcja nie zmienia się dużo, gdy argumenty się nie zmieniają wiele. Innymi słowy, podstawowa funkcja jest lokalnie prawie stała. Przy takim założeniu można oszacować wartość funkcji podstawowej w dowolnym punkcie za pomocą (ewentualnie ważonej) średniej wartości najbliższych k punktów.

Mając to na uwadze, możesz zdać sobie sprawę, że nie ma wyraźnego nakazu, co robić, gdy nie ma wyraźnego zwycięzcy w głosowaniu większością. Zawsze możesz użyć nieparzystego k lub użyć wstrzykiwacza.

W przypadku sąsiadów od 3 do 5 znajdujących się w tej samej odległości od interesującego punktu, możesz użyć tylko dwóch lub wszystkich 5. Ponownie, pamiętaj, że kNN nie jest jakimś algorytmem pochodzącym ze złożonej analizy matematycznej, ale tylko prosta intuicja. To od Ciebie zależy, jak poradzisz sobie z tymi szczególnymi przypadkami.

$\frac{1}{||x-y||^2}$

W tym roku pojawił się także miły artykuł autorstwa Samory Kpotufe i Abdeslam Boularias na temat NIPS, poruszający kwestię znalezienia właściwej wagi. Ich ogólna intuicja polega na tym, że podstawowa funkcja zmienia się różnie w różnych kierunkach (tj. Jej różne pochodne cząstkowe mają różną wielkość), dlatego rozsądnie byłoby w pewnym sensie zmienić wskaźniki / wagę zgodnie z tą intuicją. Twierdzą, że ta sztuczka ogólnie poprawia wydajność kNN i regresji jądra, i myślę, że mają nawet teoretyczne wyniki na poparcie tego twierdzenia (chociaż nie jestem pewien, co twierdzą te teoretyczne wyniki, nie miałem czasu iść) przez cały artykuł). Artykuł można pobrać bezpłatnie z ich witryn lub po Googlingu „Gradientowe wagi pomagają w regresorach nieparametrycznych”.

Teraz prawdopodobnie będziesz chciał wiedzieć, jak znaleźć odpowiednie k, metrykę, wagę, akcję do wykonania w przypadku losowań i tak dalej. Smutne jest to, że po pewnym głębokim zastanowieniu zasadniczo trudno jest znaleźć odpowiednie hiperparametry, prawdopodobnie będziesz musiał przetestować różne grupy hiperparametrów i zobaczyć, które z nich działają dobrze na niektórych zestawach sprawdzania poprawności. Jeśli masz jakieś zasoby obliczeniowe i chcesz automatycznie dobierać właściwe parametry przy dobrym zestawie hiperparametrów, istnieje pomysł (bardzo mi się podoba), aby w tym ustawieniu zastosować procesy Gaussa do optymalizacji bez pochodnych.

Pozwól mi rozwinąć - znalezienie zestawu hiperparametrów (tj. Minimalizujących błąd danych walidacyjnych) może być postrzegane jako problem optymalizacji. Niestety, w tym ustawieniu nie możemy uzyskać gradientu funkcji, którą próbujemy zoptymalizować (co zwykle chcemy zrobić, aby wykonać spadek gradientu lub niektóre bardziej zaawansowane metody). W tym ustawieniu można zastosować procesy gaussowskie do znajdowania zestawów hiperparametrów, które mają duże szanse na lepsze wyniki niż te najlepsze, które do tej pory znaleźliśmy. Dlatego możesz iteracyjnie uruchomić algorytm z jakimś zestawem hiperparametrów, a następnie zapytać proces Gaussa, dla którego najlepiej byłoby spróbować później, wypróbować te i tak dalej.

Aby uzyskać szczegółowe informacje, poszukaj artykułu „Praktyczna bayesowska optymalizacja algorytmów uczenia maszynowego” autorstwa Jaspera Snoka, Hugo Larochelle i Ryana P. Adamsa (także na ich stronach internetowych lub w Google).

Jeśli chodzi o tę część remisu, najlepszym pomysłem bazowym dla remisów jest zazwyczaj losowe zrywanie, więc wybranie losowej klasy wszystkich wygranych w głosowaniu i losowy wybór podzbioru powiązanych obiektów wystarczająco dużych, aby wypełnić k.

Takie rozwiązanie podkreśla fakt, że są to przypadki patologiczne, które po prostu nie dostarczają wystarczających informacji, aby podjąć decyzję w reżimie kNN. BTW, jeśli są one wspólne dla twoich danych, może powinieneś spróbować bardziej zróżnicować dystans?

Jednym z możliwych sposobów jest automatyczne zwiększenie lub zmniejszenie algorytmu do momentu uzyskania wyraźnego zwycięzcy.