Jak działa algorytm k najbliższych sąsiadów?
KNN mierzy odległość od nowego punktu do każdego zapisanego przykładu i zostawia k najbliższych. W klasyfikacji sąsiedzi głosują; w regresji ich wartości docelowe są uśredniane. KNN nie ma prawdziwego etapu treningu: dopasowanie zapisuje dane, a każda predykcja płaci za wyszukiwanie.
Przykład: nowe zgłoszenie do supportu zamieniamy na embedding, a jego pięć najbliższych wcześniejszych zgłoszeń to:
| Sąsiad | Odległość | Etykieta |
|---|---|---|
| 1 | 0,12 | Płatności |
| 2 | 0,18 | Płatności |
| 3 | 0,21 | Wysyłka |
| 4 | 0,30 | Płatności |
| 5 | 0,33 | Wysyłka |
Przy k = 5 i równych wagach płatności wygrywają trzema głosami do dwóch, co daje prawdopodobieństwo 0,6. Przy wagach odwrotnie proporcjonalnych do odległości płatności uzyskują 1/0,12 + 1/0,18 + 1/0,30 ≈ 17,2 wobec 1/0,21 + 1/0,33 ≈ 7,8 dla wysyłki, więc najbliżsi sąsiedzi liczą się bardziej.
Jak dobrać k i metrykę odległości?
Zacznij od domyślnych ustawień biblioteki i dostrój k na odłożonych danych. KNeighborsClassifier w scikit-learn 1.9.1 domyślnie używa n_neighbors=5, równych wag i metryki Minkowskiego z p=2, czyli odległości euklidesowej (dokumentacja scikit-learn, dostęp 16 listopada 2026). Przewodnik użytkownika ujmuje kompromis wprost: „a larger k suppresses the effects of noise, but makes the classification boundaries less distinct” (przewodnik Nearest Neighbors, dostęp 16 listopada 2026). k równe 1 zapamiętuje zbiór treningowy, a k bliskie rozmiarowi zbioru wszędzie przewiduje klasę większościową: pierwsze prowadzi do przeuczenia, drugie do niedouczenia.
Przeskaluj cechy przed mierzeniem odległości, bo inaczej o każdym głosowaniu przesądzi cecha o największych jednostkach: dochód w euro przytłoczy wiek w latach. Dla embeddingów tekstu typowym wyborem jest odległość kosinusowa.
Dlaczego KNN zwalnia na dużych lub wielowymiarowych danych?
Wyszukiwanie siłowe (brute force) porównuje zapytanie z każdym zapisanym punktem. Przewodnik scikit-learn podaje ten koszt jako O[DN²] dla N próbek w D wymiarach w skali całego zbioru. Indeksy drzewiaste pomagają przy małej liczbie wymiarów: drzewo KD „is very fast for low-dimensional (D < 20) neighbors searches”, a algorithm='auto' w scikit-learn powyżej 15 wymiarów wraca do wyszukiwania siłowego (ten sam przewodnik). W wysokich wymiarach odległości skupiają się blisko siebie, co nazywa się przekleństwem wymiarowości, i dokładne wyszukiwanie przestaje się skalować.
Czym różni się KNN od przybliżonego wyszukiwania najbliższych sąsiadów?
Dokładny KNN zwraca prawdziwe k najbliższych punktów; przybliżone wyszukiwanie najbliższych sąsiadów (ANN) zwraca prawie najbliższe, za to znacznie szybciej.
| Dokładny KNN | Przybliżone (ANN) | |
|---|---|---|
| Recall | Pełny | Poniżej 100%, regulowany |
| Koszt zapytania | Rośnie z każdym zapisanym wektorem | Mniej więcej logarytmiczny dla HNSW |
| Typowy indeks | Brak albo drzewa KD i ball tree | HNSW, IVFFlat |
| Gdzie go spotkasz | Małe modele na danych tabelarycznych | Bazy wektorowe |
pgvector domyślnie „performs exact nearest neighbor search, which provides perfect recall”, a indeks HNSW lub IVFFlat „trades some recall for speed” (README pgvector, v0.8.7, dostęp 16 listopada 2026). HNSW pochodzi od Malkova i Yashunina, których warstwowe wyszukiwanie w grafie „allows a logarithmic complexity scaling” (arXiv:1603.09320, 30 marca 2016, dostęp 16 listopada 2026). Każde zapytanie wyszukiwania semantycznego w systemie RAG to zapytanie o najbliższych sąsiadów, więc gdy wyszukiwanie pomija fragment, sprawdź recall indeksu, zanim obwinisz model.