Czym jest k-najbliższych sąsiadów (kNN)?
Definicja
Algorytm k-najbliższych sąsiadów (kNN) to metoda uczenia nadzorowanego, która klasyfikuje punkt według najczęstszej klasy wśród jego k najbliższych zapisanych punktów.
kNN nie ma jawnego etapu trenowania. Zapisuje oznaczone przykłady i wykonuje obliczenia, gdy nadejdzie zapytanie. Scikit-learn nazywa to uczeniem opartym na instancjach, bez uogólniania.
Jak działa
- Wybierz k i miarę odległości. Najczęstszym wyborem jest odległość euklidesowa.
- Znajdź k zapisanych punktów najbliższych punktowi zapytania.
- Przypisz punktowi zapytania klasę, jaką ma większość z tych k punktów.
Domyślnie każdy sąsiad ma jeden głos. W ważonym kNN bliżsi sąsiedzi liczą się bardziej, na przykład z wagą 1/d, gdzie d to odległość od sąsiada.
Wybór k
Najlepsza wartość k zależy od danych. Większe k tłumi szum, ale sprawia, że granice klas są mniej wyraźne. Walidacja krzyżowa znajduje dobrą wartość k na podstawie danych. Dla dwóch klas nieparzyste k pozwala uniknąć remisów w głosowaniu.
Ograniczenia
- Jeśli cechy mają różne jednostki lub skale, normalizacja każdej cechy może znacznie poprawić dokładność.
- Wyszukiwanie typu brute force porównuje zapytanie z każdym zapisanym punktem. Staje się to niewykonalne, gdy liczba punktów rośnie.
- Wyszukiwanie oparte na drzewach, na przykład drzewie KD, jest szybkie tylko w niskich wymiarach (poniżej około 20). W wysokich wymiarach odległość euklidesowa jest też mniej użyteczna, ponieważ wszystkie wektory są prawie równie odległe od zapytania.
- Biblioteki takie jak Faiss przeszukują duże zbiory wektorów. Oferują wyszukiwanie dokładne i skompresowane indeksy. Skompresowane indeksy dają mniej precyzyjne wyniki.
Historia
Evelyn Fix i Joseph Hodges po raz pierwszy opracowali tę metodę w 1951 roku w raporcie dla USAF School of Aviation Medicine. Thomas Cover i Hart opublikowali „Nearest neighbor pattern classification” w 1967 roku. Przy nieograniczonej liczbie danych treningowych współczynnik błędu reguły 1-najbliższego sąsiada nie przekracza dwukrotności błędu Bayesa.
Często zadawane pytania
- Jak wybrać k w kNN?
- Sprawdź kilka wartości k walidacją krzyżową i wybierz tę, która daje najlepszy wynik na danych odłożonych. Najlepsze k zależy od danych. Większe k tłumi szum, ale sprawia, że granice klas są mniej wyraźne. W zadaniu z dwiema klasami nieparzyste k pozwala uniknąć remisów w głosowaniu.
- Czy kNN wymaga trenowania?
- Nie, kNN nie ma jawnego etapu trenowania. Zapisuje oznaczone przykłady i wykonuje całe obliczenia, gdy nadejdzie zapytanie. Scikit-learn nazywa to uczeniem opartym na instancjach, bez uogólniania.
- Czym jest ważony kNN?
- Ważony kNN pozwala, by bliżsi sąsiedzi liczyli się w głosowaniu bardziej niż dalsi. Częstym wyborem jest waga 1/d, gdzie d to odległość od sąsiada. W scikit-learn domyślnie stosowane są jednakowe wagi, a weights = 'distance' daje wagi proporcjonalne do odwrotności odległości.
Bibliografia
- sklearn-neighbors
- scikit-learn User Guide, 1.6 Nearest Neighbors scikit-learn
- wikipedia-knn
- k-nearest neighbors algorithm Wikipedia
- faiss-readme
- Faiss: a library for efficient similarity search and clustering of dense vectors Meta Research (facebookresearch/faiss on GitHub)
- faiss-getting-started
- Faiss wiki: Getting started Meta Research (facebookresearch/faiss on GitHub)
To wpis referencyjny. TarmacView świadczy usługi inspekcji dronami i nie sprzedaje sprzętu ani materiałów opisanych w tym słowniczku.