Condividi tramite

kNN e ANN

  • Articolo
  • Si applica a:
    ✅ NoSQL, ✅ MongoDB vCore, ✅ PostgreSQL

Due categorie principali di algoritmi di ricerca vettoriale sono k-Nearest Neighbors (kNN) e Approximate Nearest Neighbors (ANN, non da confondere con la rete neurale artificiale). KNN è preciso ma a elevato utilizzo di calcolo, rendendolo meno adatto per set di dati di grandi dimensioni. ANN, d'altra parte, offre un equilibrio tra accuratezza ed efficienza, rendendolo più adatto ad applicazioni su larga scala.

Funzionamento di kNN

  1. Vettorizzazione: ogni punto dati nel set di dati è rappresentato come vettore in uno spazio multidimensionale.
  2. Calcolo della distanza: per classificare un nuovo punto dati (punto di query), l'algoritmo calcola la distanza tra il punto di query e tutti gli altri punti del set di dati utilizzando una funzione distanza.
  3. Ricerca di vicini: l'algoritmo identifica i punti dati k più vicini (vicini) al punto di query in base alle distanze calcolate. Il valore di k (il numero di vicini) è fondamentale. Un k di piccole dimensioni può essere sensibile al rumore, mentre un k di grandi dimensioni può attenuare i dettagli.
  4. Esecuzione di stime:
  • Classificazione: per le attività di classificazione, kNN assegna l'etichetta di classe al punto di query più comune tra i k vicini. In sostanza, esegue un "voto di maggioranza".
  • Regressione: per le attività di regressione, kNN predice il valore per il punto di query come media (o talvolta media ponderata) dei valori dei k vicini.

Funzionamento di ANN

  1. Vettorizzazione: ogni punto dati nel set di dati è rappresentato come vettore in uno spazio multidimensionale.
  2. Indicizzazione e strutture di dati: gli algoritmi ANN usano strutture di dati avanzate (ad esempio, KD-trees, hashing sensibile alla località o metodi basati su grafo) per indicizzare i punti dati, consentendo ricerche più rapide.
  3. Calcolo della distanza: invece di calcolare la distanza esatta a ogni punto, gli algoritmi ANN usano un'euristica per identificare rapidamente le aree dello spazio che probabilmente contengono i vicini più prossimi.
  4. Ricerca di vicini: l'algoritmo identifica un set di punti dati che probabilmente si avvicinano al punto di query. Questi vicini non sono garantiti come punti esattamente più vicini, ma sono abbastanza vicini per scopi pratici.
  5. Esecuzione di stime:
  • Classificazione: per le attività di classificazione, ANN assegna l'etichetta di classe al punto di query più comune tra i vicini identificati, simile a kNN.
  • Regressione: per le attività di regressione, ANN predice il valore per il punto di query come media (o media ponderata) dei valori dei k vicini identificati.

Contenuto correlato