K-nearest neighbors

A questa voce o sezione va aggiunto il template sinottico {{Algoritmo}}

Puoi aggiungere e riempire il template secondo le istruzioni e poi rimuovere questo avviso. Se non sei in grado di riempirlo in buona parte, non fare nulla; non inserire template vuoti.

Questa voce o sezione sull'argomento informatica è priva o carente di note e riferimenti bibliografici puntuali.

---

Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento.

Il k-nearest neighbors (traducibile come primi k-vicini), abbreviato in K-NN, è un algoritmo utilizzato nel riconoscimento di pattern per la classificazione di oggetti basandosi sulle caratteristiche degli oggetti vicini a quello considerato. In entrambi i casi, l'input è costituito dai k esempi di addestramento più vicini nello spazio delle funzionalità. L'output dipende dall'utilizzo di k-NN per la classificazione o la regressione:

Nella classificazione k-NN, l'output è un'appartenenza a una classe. Un oggetto è classificato da un voto di pluralità dei suoi vicini, con l'oggetto assegnato alla classe più comune tra i suoi k vicini più vicini (k è un numero intero positivo, tipicamente piccolo). Se k = 1, l'oggetto viene semplicemente assegnato alla classe di quel singolo vicino più prossimo.

Nella regressione k-NN, l'output è il valore della proprietà per l'oggetto. Questo valore è la media dei valori di k vicini più vicini.

È l'algoritmo più semplice fra quelli utilizzati nell'apprendimento automatico (machine learning).

Un oggetto è classificato in base alla maggioranza dei voti dei suoi k vicini. k è un intero positivo tipicamente non molto grande. Se k=1 allora l'oggetto viene assegnato alla classe del suo vicino. In un contesto binario in cui sono presenti esclusivamente due classi è opportuno scegliere k dispari per evitare di ritrovarsi in situazioni di parità.

Questo metodo può essere utilizzato per la tecnica di regressione assegnando all'oggetto la media dei valori dei k oggetti suoi vicini.

Considerando solo i voti dei k oggetti vicini c'è l'inconveniente dovuto alla predominanza delle classi con più oggetti. In questo caso può risultare utile pesare i contributi dei vicini in modo da dare, nel calcolo della media, maggior importanza in base alla distanza dall'oggetto considerato.

La scelta di k dipende dalle caratteristiche dei dati. Generalmente all'aumentare di k si riduce il rumore che compromette la classificazione, ma il criterio di scelta per la classe diventa più labile. La scelta può esser presa attraverso tecniche di euristica, come ad esempio la convalida incrociata.

Lo spazio viene partizionato in regioni in base alle posizioni e alle caratteristiche degli oggetti di apprendimento. Questo può essere considerato come l'insieme d'apprendimento per l'algoritmo, anche se esso non è esplicitamente richiesto dalle condizioni iniziali.

Ai fini del calcolo della distanza gli oggetti sono rappresentati attraverso vettori di posizione in uno spazio multidimensionale. Di solito viene usata la distanza euclidea, ma anche altri tipi di distanza sono ugualmente utilizzabili, ad esempio la distanza Manhattan. Nel caso in cui si debbano manipolare stringhe e non numeri si possono usare altre distanze quali ad esempio la distanza di Hamming. L'algoritmo è sensibile alla struttura locale dei dati.

Un punto (che rappresenta un oggetto) è assegnato alla classe C se questa è la più frequente fra i k esempi più vicini all'oggetto sotto esame, la vicinanza si misura in base alla distanza fra punti. I vicini sono presi da un insieme di oggetti per cui è nota la classificazione corretta. Nel caso della regressione per il calcolo della media (classificazione) si usa il valore della proprietà considerata.

In figura è rappresentato un esempio di classificazione mediante kNN. Il punto sotto osservazione è il pallino verde. Le classi sono due:

• quella dei triangolini rossi;
• quella dei quadratini blu.

Se k = 3 (cioè vengono considerati i 3 oggetti più vicini), allora il pallino verde viene inserito nella stessa classe dei triangolini rossi perché sono presenti 2 triangolini e 1 quadratino. Se k = 5 allora viene inserito nella stessa classe dei quadratini blu perché sono presenti 3 quadratini e 2 triangolini.

Il calcolo delle distanze è computazionalmente oneroso e proporzionale alla taglia dell'insieme di dati sotto esame. Gli algoritmi proposti che migliorano questo inconveniente cercano principalmente di diminuire il numero di distanze da calcolare per la decisione. In alcuni casi si cerca di partizionare lo spazio vettoriale e si calcolano solo le distanze tra volumi dello spazio vettoriale.

Di seguito sono elencati alcuni algoritmi della tipologia k-NN:

• k-Most Similar Neighbour (k-MSN)
• Linear scan
• Kd-trees
• Balltrees
• Metric trees
• Locality-sensitive hashing (LSH)
• Agglomerative-Nearest-Neighbour
• Redundant Bit Vectors (RBV)

Al tendere della quantità di dati all'infinito l'algoritmo non supera mai di due volte il Bayes error rate (il minimo errore dovuto alla distribuzione dei dati). Per alcuni valori di k, con k che cresce in funzione della mole di dati, l'algoritmo raggiunge il Bayes error rate.

k-NN può essere utilizzato, con opportuni adattamenti, per stimare variabili continue. Questo tipo di implementazione utilizza una media pesata basata sull'inverso della distanza.

• Belur V. Dasarathy, editor (1991) Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques, ISBN 0-8186-8930-7
• Nearest-Neighbour Methods in Learning and Vision, edited by Shakhnarovish, Darrell, and Indyk, The MIT Press, 2005, ISBN 0-262-19547-X
• Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data. Forest Ecology and Management, Volume 196, Issues 2-3, 26 July 2004, Pages 245-255. Helena Mäkelä and Anssi Pekkarinen
• Estimation and mapping of forest density, volume, and cover type using the k-nearest neighbour method. Remote Sensing of Environment, Volume 77, Issue 3, September 2001, Pages 251-274. Hector Franco-Lopez, Alan R. Ek and Marvin E. Bauer

• k-nearest neighbour algorithm in Visual Basic and Java Archiviato il 29 settembre 2007 in Internet Archive. (includes executable and source code)
• how does knn classification work, su 360digitmg.com.
• Weighted distance learning for nearest neighbour error minimization by R. Paredes and E. Vidal, su dsic.upv.es. URL consultato il 3 marzo 2009 (archiviato dall'url originale il 15 dicembre 2007).
• K-Nearest neighbour algoritm in C# (includes executable and source code)

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Regole di associazione · Apprendimento non supervisionato · Apprendimento supervisionato · Apprendimento per rinforzo · Apprendimento profondo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random fields CRF · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modelli grafici · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Rete neurale a base radiale · Rete bayesiana · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · Torch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

Portale Informatica

Portale Ingegneria

Portale Statistica