Udostępnij za pośrednictwem

kNN a ANN

  • Artykuł
  • Dotyczy:
    ✅ NoSQL, ✅ MongoDB vCore, ✅ PostgreSQL

Dwie główne kategorie algorytmów wyszukiwania wektorów to k-najbliższych sąsiadów (kNN) i Przybliżone najbliższe sąsiady (ANN, nie należy mylić ze sztuczną siecią neuronową). KNN jest precyzyjny, ale intensywnie obciąża obliczenia, co sprawia, że jest mniej odpowiedni dla dużych zestawów danych. Z drugiej strony anN zapewnia równowagę między dokładnością a wydajnością, dzięki czemu lepiej nadaje się do zastosowań na dużą skalę.

Jak działa nazwa kNN

  1. Wektoryzacja: każdy punkt danych w zestawie danych jest reprezentowany jako wektor w przestrzeni wielowymiarowej.
  2. Obliczanie odległości: aby sklasyfikować nowy punkt danych (punkt zapytania), algorytm oblicza odległość między punktem zapytania a wszystkimi innymi punktami w zestawie danych przy użyciu funkcji odległości.
  3. Znajdowanie sąsiadów: algorytm identyfikuje k najbliższych punktów danych (sąsiadów) do punktu zapytania na podstawie odległości obliczeniowych. Wartość k (liczba sąsiadów) ma kluczowe znaczenie. Mały k może być wrażliwy na szum, podczas gdy duży k może wygładzić szczegóły.
  4. Przewidywanie:
  • Klasyfikacja: W przypadku zadań klasyfikacji kNN przypisuje etykietę klasy do punktu zapytania, który jest najczęściej spotykany wśród sąsiadów k. Zasadniczo wykonuje "głosowanie większościowe".
  • Regresja: W przypadku zadań regresji kNN przewiduje wartość punktu zapytania jako średnią (lub czasami średnią ważoną) wartości sąsiadów k.

Jak działa ann

  1. Wektoryzacja: każdy punkt danych w zestawie danych jest reprezentowany jako wektor w przestrzeni wielowymiarowej.
  2. Indeksowanie i struktury danych: algorytmy ANN używają zaawansowanych struktur danych (np. KD-trees, skrótów wrażliwych na lokalność lub metod opartych na grafach) do indeksowania punktów danych, co pozwala na szybsze wyszukiwanie.
  3. Obliczanie odległości: zamiast obliczać dokładną odległość do każdego punktu algorytmy ANN używają algorytmów heurystycznych do szybkiego identyfikowania regionów przestrzeni, które mogą zawierać najbliższych sąsiadów.
  4. Znajdowanie sąsiadów: algorytm identyfikuje zestaw punktów danych, które mogą znajdować się w pobliżu punktu zapytania. Ci sąsiedzi nie mają gwarancji, że są dokładnie najbliżej siebie, ale są wystarczająco blisko w praktycznych celach.
  5. Przewidywanie:
  • Klasyfikacja: W przypadku zadań klasyfikacji anN przypisuje etykietę klasy do punktu zapytania, który jest najczęściej spotykany wśród zidentyfikowanych sąsiadów, podobnie jak kNN.
  • Regresja: W przypadku zadań regresji anN przewiduje wartość punktu zapytania jako średnią (lub średnią ważoną) wartości zidentyfikowanych sąsiadów.

Powiązana zawartość