Cos'è il vicino K-nearest? Un algoritmo ML per classificare i dati

Gli algoritmi guidano il mondo dell'apprendimento automatico.

Sono spesso elogiati per le loro capacità predittive e detti lavoratori che consumano enormi quantità di dati per produrre risultati immediati.

Tra questi, c'è un algoritmo spesso etichettato come pigro. Ma è piuttosto un esecutore quando si tratta di classificare i punti dati. Si chiama algoritmo k-nearest neighbors ed è spesso citato come uno dei più importanti   apprendimento automatico   algoritmi.

Qual è l'algoritmo dei k-vicini più vicini?

L' algoritmo k-nearest neighbors (KNN) è un metodo di classificazione dei dati per stimare la probabilità che un punto dati diventi membro di un gruppo o di un altro in base al gruppo a cui appartengono i punti dati più vicini.

L'algoritmo k-neiest neighbor è un tipo di   apprendimento automatico supervisionato   algoritmo utilizzato per risolvere problemi di classificazione e regressione. Tuttavia, viene utilizzato principalmente per problemi di classificazione.

KNN è un algoritmo di apprendimento pigro e non parametrico .

Si chiama algoritmo di apprendimento pigro o discente pigro perché non esegue alcun addestramento quando fornisci i dati di addestramento. Invece, memorizza solo i dati durante il tempo di addestramento e non esegue alcun calcolo. Non crea un modello finché non viene eseguita una query sul set di dati. Questo rende KNN ideale per   estrazione dei dati.

È considerato un metodo non parametrico perché non fa ipotesi sulla distribuzione dei dati sottostante. In poche parole, KNN cerca di determinare a quale gruppo appartiene un punto dati osservando i punti dati attorno ad esso.

Considera che ci sono due gruppi, A e B.

Per determinare se un punto dati si trova nel gruppo A o nel gruppo B, l'algoritmo esamina gli stati dei punti dati vicini ad esso. Se la maggior parte dei punti dati si trova nel gruppo A, è molto probabile che il punto dati in questione sia nel gruppo A e viceversa.

In breve, KNN implica la classificazione di un punto dati osservando il punto dati annotato più vicino, noto anche come vicino più vicino .

Non confondere la classificazione K-NN con il clustering K-medie. KNN è un algoritmo di classificazione supervisionato che classifica i nuovi punti dati in base ai punti dati più vicini. D'altra parte, il clustering di K-medie è un   senza supervisione   algoritmo di clustering che raggruppa i dati in un numero K di cluster.

Come funziona KNN?

Come accennato in precedenza, l'algoritmo KNN viene utilizzato principalmente come classificatore. Diamo un'occhiata a come funziona KNN per classificare i punti dati di input non visti.

A differenza della classificazione che utilizza reti neurali artificiali, la classificazione dei vicini più vicini è facile da capire e semplice da implementare. È ideale in situazioni in cui i punti dati sono ben definiti o non lineari.

In sostanza, KNN esegue un meccanismo di voto per determinare la classe di un'osservazione invisibile. Ciò significa che la classe con il voto di maggioranza diventerà la classe del punto dati in questione.

Se il valore di K è uguale a uno, useremo solo il vicino più vicino per determinare la classe di un punto dati. Se il valore di K è uguale a dieci, useremo i dieci vicini più vicini e così via.

Per metterlo in prospettiva, considera un punto dati non classificato X. Esistono diversi punti dati con categorie note, A e B, in un grafico a dispersione.

Supponiamo che il punto dati X sia posizionato vicino al gruppo A.

Come sapete, classifichiamo un punto dati osservando i punti annotati più vicini. Se il valore di K è uguale a uno, useremo solo un vicino più vicino per determinare il gruppo del punto dati.

In questo caso, il punto dati X appartiene al gruppo A poiché il suo vicino più vicino è nello stesso gruppo. Se il gruppo A ha più di dieci punti dati e il valore di K è uguale a 10, il punto dati X apparterrà comunque al gruppo A poiché tutti i suoi vicini più vicini sono nello stesso gruppo.

Supponiamo che un altro punto dati non classificato Y sia posizionato tra il gruppo A e il gruppo B. Se K è uguale a 10, scegliamo il gruppo che ottiene il maggior numero di voti, il che significa che classifichiamo Y nel gruppo in cui ha il maggior numero di vicini. Ad esempio, se Y ha sette vicini nel gruppo B e tre vicini nel gruppo A, appartiene al gruppo B.

Il fatto che il classificatore assegni la categoria con il maggior numero di voti è vero indipendentemente dal numero di categorie presenti.

Potresti chiederti come viene calcolata la metrica della distanza per determinare se un punto dati è un vicino o meno.

Esistono quattro modi per calcolare la distanza misurata tra il punto dati e il suo vicino più vicino: distanza euclidea , distanza di Manhattan , distanza di Hamming e distanza di Minkowski . Delle tre, la distanza euclidea è la funzione o metrica di distanza più comunemente usata.

Per convalidare l'accuratezza della classificazione KNN, a   matrice di confusione   viene usato. Per la convalida vengono utilizzati anche altri metodi statistici come il test del rapporto di verosimiglianza.

Nel caso della regressione KNN, la maggior parte dei passaggi è la stessa. Invece di assegnare la classe con i voti più alti, viene calcolata la media dei valori dei vicini e assegnata al punto dati sconosciuto.

Perché usare l'algoritmo KNN?

La classificazione è un problema critico nella scienza dei dati e nell'apprendimento automatico. Il KNN è uno degli algoritmi più antichi ma accurati utilizzati per la classificazione dei modelli e i modelli di regressione.

Ecco alcune delle aree in cui è possibile utilizzare l'algoritmo k-nearest neighbor:

• Rating di credito: l'algoritmo KNN aiuta a determinare il rating di credito di un individuo confrontandolo con quelli con caratteristiche simili.
• Approvazione del prestito: simile al rating del credito, l'algoritmo del vicino più vicino è utile nell'identificare le persone che hanno maggiori probabilità di inadempiere sui prestiti confrontando le loro caratteristiche con individui simili.
• Preelaborazione dei dati: i set di dati possono avere molti valori mancanti. L'algoritmo KNN viene utilizzato per un processo chiamato imputazione dei dati mancanti che stima i valori mancanti.
• Riconoscimento dei modelli: la capacità dell'algoritmo KNN di identificare i modelli crea un'ampia gamma di applicazioni. Ad esempio, aiuta a rilevare i modelli nell'utilizzo della carta di credito e individuare schemi insoliti. Il rilevamento dei modelli è utile anche per identificare i modelli nel comportamento di acquisto dei clienti.
• Previsione del prezzo delle azioni: poiché l'algoritmo KNN ha un talento per prevedere i valori di entità sconosciute, è utile per prevedere il valore futuro delle azioni sulla base di dati storici.
• Sistemi di raccomandazione: poiché KNN può aiutare a trovare utenti con caratteristiche simili, può essere utilizzato nei sistemi di raccomandazione. Ad esempio, può essere utilizzato in una piattaforma di streaming video online per suggerire contenuti che è più probabile che un utente guardi analizzando ciò che utenti simili guardano.
• Visione artificiale: l'algoritmo KNN viene utilizzato per la classificazione delle immagini. Poiché è in grado di raggruppare punti dati simili, ad esempio raggruppando gatti e cani in una classe diversa, è utile in diversi   visione computerizzata   applicazioni.

Come scegliere il valore ottimo di K

Non esiste un modo specifico per determinare il miglior valore K, in altre parole, il numero di vicini in KNN. Ciò significa che potresti dover sperimentare alcuni valori prima di decidere con quale andare avanti.

Un modo per farlo è considerare (o fingere) che una parte dei campioni di addestramento sia "sconosciuta". Quindi, puoi classificare i dati sconosciuti nel set di test utilizzando l'algoritmo k-neiest neighbors e analizzare quanto è buona la nuova categorizzazione confrontandola con le informazioni che hai già nei dati di addestramento.

Quando si ha a che fare con un problema a due classi, è meglio scegliere un valore dispari per K. Altrimenti, può verificarsi uno scenario in cui il numero di vicini in ogni classe è lo stesso. Inoltre, il valore di K non deve essere un multiplo del numero di classi presenti.

Un altro modo per scegliere il valore ottimale di K consiste nel calcolare sqrt(N), dove N indica il numero di campioni nel set di dati di addestramento.

Tuttavia, K con valori inferiori, come K=1 o K=2, può essere rumoroso e soggetto agli effetti di valori anomali. Anche la possibilità di overfitting è alta in questi casi.

D'altra parte, K con valori più grandi, nella maggior parte dei casi, darà luogo a confini decisionali più uniformi, ma non dovrebbe essere troppo grande. In caso contrario, i gruppi con un numero inferiore di punti dati verranno sempre eliminati da altri gruppi. Inoltre, un K più grande sarà computazionalmente costoso.

Vantaggi e svantaggi di KNN

Uno dei vantaggi più significativi dell'utilizzo dell'algoritmo KNN è che non è necessario creare un modello o regolare diversi parametri. Poiché si tratta di un algoritmo di apprendimento pigro e non di uno studente desideroso, non è necessario addestrare il modello; invece, tutti i punti dati vengono utilizzati al momento della previsione.

Naturalmente, questo è computazionalmente costoso e richiede tempo. Ma se hai le risorse di calcolo necessarie, puoi usare KNN per risolvere problemi di regressione e classificazione. Tuttavia, esistono diversi algoritmi più veloci in grado di produrre previsioni accurate.

Naturalmente, KNN non è un algoritmo di apprendimento automatico perfetto. Poiché il predittore KNN calcola tutto da zero, potrebbe non essere l'ideale per set di dati di grandi dimensioni.

KNN e la maledizione della dimensionalità

Quando si dispone di enormi quantità di dati a portata di mano, può essere piuttosto difficile estrarne informazioni rapide e dirette. Per questo, possiamo utilizzare algoritmi di riduzione della dimensionalità che, in sostanza, fanno "arrivare direttamente al punto" i dati.

Il termine "maledizione della dimensionalità" potrebbe dare l'impressione che provenga direttamente da un film di fantascienza. Ma ciò che significa è che i dati hanno troppe funzionalità.

Se i dati hanno troppe funzionalità, c'è un alto rischio di overfitting del modello, portando a modelli imprecisi. Troppe dimensioni rendono inoltre più difficile raggruppare i dati poiché ogni campione di dati nel set di dati apparirà equidistante l'uno dall'altro.

L'algoritmo k-nearest neighbors è altamente suscettibile all'overfitting a causa della maledizione della dimensionalità. Tuttavia, questo problema può essere risolto con il   attuazione della forza bruta   dell'algoritmo KNN. Ma non è pratico per set di dati di grandi dimensioni.

KNN non funziona bene se ci sono troppe funzionalità. Pertanto, le tecniche di riduzione della dimensionalità come l'analisi dei componenti principali (PCA) e la selezione delle caratteristiche devono essere eseguite durante la fase di preparazione dei dati.

KNN: l'algoritmo pigro che ha conquistato i cuori

Nonostante sia il più pigro tra gli algoritmi, KNN si è costruito una reputazione impressionante ed è un algoritmo di riferimento per diversi problemi di classificazione e regressione. Naturalmente, a causa della sua pigrizia, potrebbe non essere la scelta migliore per i casi che coinvolgono grandi set di dati. Ma è uno degli algoritmi più antichi, semplici e accurati in circolazione.

L'addestramento e la convalida di un algoritmo con una quantità limitata di dati può essere un compito arduo. Ma c'è un modo per farlo in modo efficiente. Si chiama convalida incrociata e comporta la prenotazione di una parte dei dati di addestramento come set di dati di test.