K-Nearest Neighbours (KNN): cos'è e come viene utilizzato nell'apprendimento automatico

K-nearest neighbors (KNN) è una tecnica fondamentale nell'apprendimento automatico (ML). Questa guida ti aiuterà a comprendere KNN, come funziona e le sue applicazioni, vantaggi e sfide.

Sommario

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

Come funziona KNN?

Differenza tra k-vicini più vicini e altri algoritmi

Come viene utilizzato KNN nell'apprendimento automatico?

Applicazioni della KNN

Vantaggi di KNN

Svantaggi del KNN

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

L'algoritmo k-nearest neighbors (KNN) è una tecnica di apprendimento supervisionato utilizzata sia per la classificazione che per la regressione. KNN determina l'etichetta (classificazione) o il valore previsto (regressione) di un dato punto dati valutando i punti dati vicini nel set di dati.

Come funziona KNN?

KNN si basa sulla premessa che i punti dati spazialmente vicini tra loro in un set di dati tendono ad avere valori simili o ad appartenere a categorie simili. KNN utilizza questa idea semplice ma potente per classificare un nuovo punto dati trovando un numero preimpostato (l'iperparametro k) di punti dati vicini all'interno del set di dati di addestramento etichettato. Questo valore, k, è uno degli iperparametri KNN, ovvero variabili di configurazione preimpostate che i professionisti del machine learning utilizzano per controllare il modo in cui l'algoritmo apprende.

Quindi, l'algoritmo determina quale dei valori vicini è più vicino al nuovo punto dati e gli assegna la stessa etichetta o categoria dei suoi vicini. Il valore scelto di k influisce sulle prestazioni del modello. Valori più piccoli aumentano la sensibilità al rumore, mentre valori più grandi aumentano la robustezza ma possono far sì che il KNN manchi i modelli locali.

La vicinanza, o distanza, tra i punti dati viene calcolata utilizzando parametri originariamente sviluppati per misurare la somiglianza dei punti in uno spazio matematico. Le metriche comuni includono la distanza euclidea, la distanza di Manhattan e la distanza di Minkowski. Le prestazioni di KNN sono influenzate dalla metrica scelta e diverse metriche funzionano meglio con diversi tipi e dimensioni di dati.

Ad esempio, il numero di dimensioni nei dati, che sono attributi individuali che descrivono ciascun punto dati, può influenzare le prestazioni della metrica. Indipendentemente dalla metrica di distanza scelta, l'obiettivo è classificare o prevedere un nuovo punto dati in base alla sua distanza da altri punti dati.

• La distanza euclideaè la distanza lungo una linea retta tra due punti nello spazio ed è la metrica più comunemente utilizzata. È particolarmente indicato per i dati con un numero inferiore di dimensioni e senza valori anomali significativi.
• La distanza di Manhattanè la somma delle differenze assolute tra le coordinate dei punti dati misurati. Questa metrica è utile quando i dati sono ad alta dimensione o quando i punti dati formano una struttura a griglia.
• La distanza di Minkowskiè una metrica regolabile che può agire come la distanza euclidea o quella di Manhattan a seconda del valore di un parametro regolabile. La regolazione di questo parametro controlla il modo in cui viene calcolata la distanza, il che è utile per adattare KNN a diversi tipi di dati.

Altri parametri meno comuni includono le distanze di Chebyshev, Hamming e Mahalanobis. Queste metriche sono più specializzate e sono adatte a particolari tipi di dati e distribuzioni. Ad esempio, la distanza Mahalanobis misura la distanza di un punto da una distribuzione di punti, tenendo conto delle relazioni tra le variabili. Pertanto, la distanza Mahalanobis è particolarmente adatta per lavorare con dati in cui le caratteristiche utilizzano scale diverse.

KNN è spesso definito un algoritmo di apprendimento “pigro” perché non necessita di addestramento, a differenza di molti altri algoritmi. KNN archivia invece i dati e li utilizza per prendere decisioni solo quando nuovi punti dati necessitano di regressione o classificazione. Tuttavia, ciò significa che le previsioni spesso hanno requisiti computazionali elevati poiché per ciascuna previsione viene valutato l’intero set di dati. ∫

Differenza tra k-vicini più vicini e altri algoritmi

KNN fa parte di una famiglia più ampia di tecniche ML supervisionate orientate alla classificazione e alla regressione, che include alberi decisionali/foreste casuali, regressione logistica e macchine a vettori di supporto (SVM). Tuttavia, KNN differisce da queste tecniche per la sua semplicità e l’approccio diretto alla gestione dei dati, tra gli altri fattori.

Alberi decisionali e foreste casuali

Come KNN, gli alberi decisionali e le foreste casuali vengono utilizzati per la classificazione e la regressione. Tuttavia, questi algoritmi utilizzano regole esplicite apprese dai dati durante l'addestramento, a differenza dell'approccio basato sulla distanza di KNN. Gli alberi decisionali e le foreste casuali tendono ad avere velocità di previsione più elevate perché dispongono di regole preaddestrate. Ciò significa che sono più adatti di KNN per attività di previsione in tempo reale e per la gestione di set di dati di grandi dimensioni.

Regressione logistica

La regressione logistica presuppone che i dati siano distribuiti linearmente e li classifica utilizzando una linea retta o un iperpiano (un confine che separa i punti dati in spazi dimensionali superiori) per separare i dati in categorie. KNN, d'altro canto, non presuppone una particolare distribuzione dei dati. Pertanto, KNN può adattarsi più facilmente a dati complessi o non lineari, mentre la regressione logistica viene utilizzata al meglio con dati lineari.

Supporta macchine vettoriali

Invece di considerare le distanze tra punti come KNN, le macchine a vettori di supporto (SVM) si concentrano sulla creazione di una chiara linea di demarcazione tra gruppi di punti dati, spesso con l'obiettivo di rendere il divario tra loro il più ampio possibile. SVM è eccezionale nella gestione di set di dati complessi con molte funzionalità o quando è necessaria una chiara separazione tra gruppi di punti dati. In confronto, KNN è più semplice da usare e comprendere, ma non funziona altrettanto bene su set di dati di grandi dimensioni.

Come viene utilizzato KNN nell'apprendimento automatico?

Molti algoritmi ML possono gestire solo un tipo di attività. KNN si distingue per la sua capacità di gestire non uno ma due casi d'uso comuni: classificazione e regressione.

Classificazione

KNN classifica i punti dati utilizzando una metrica di distanza per determinare i k vicini più vicini e assegnando un'etichetta al nuovo punto dati in base alle etichette dei vicini. I casi d'uso comuni della classificazione KNN includono la classificazione dello spam via e-mail, il raggruppamento dei clienti in categorie in base alla cronologia degli acquisti e il riconoscimento dei numeri scritti a mano.

Regressione

KNN esegue la regressione stimando il valore di un punto dati in base alla media (o media ponderata) dei suoi k vicini più vicini. Ad esempio, KNN può prevedere i prezzi delle case sulla base di proprietà simili nel quartiere, i prezzi delle azioni sulla base di dati storici per azioni simili o la temperatura sulla base di dati meteorologici storici in località simili.

Applicazioni dell'algoritmo KNN in ML

Grazie alla sua relativa semplicità e alla capacità di eseguire sia la classificazione che la regressione, KNN ha una vasta gamma di applicazioni. Questi includono il riconoscimento delle immagini, i sistemi di raccomandazione e la classificazione del testo.

Riconoscimento delle immagini

Il riconoscimento delle immagini è una delle applicazioni più comuni di KNN grazie alle sue capacità di classificazione. KNN esegue il riconoscimento delle immagini confrontando le caratteristiche dell'immagine sconosciuta, come colori e forme, con le caratteristiche di un set di dati di immagine etichettato. Ciò rende KNN utile in campi come la visione artificiale.

Sistemi di raccomandazione

KNN può consigliare prodotti o contenuti agli utenti confrontando i loro dati sulle preferenze con i dati di utenti simili. Ad esempio, se un utente ha ascoltato diversi brani jazz classici, KNN può trovare utenti con preferenze simili e consigliare brani che gli utenti hanno apprezzato. Pertanto, KNN può aiutare a personalizzare l'esperienza dell'utente consigliando prodotti o contenuti basati su dati simili.

Classificazione del testo

La classificazione del testo cerca di classificare il testo non categorizzato in base alla sua somiglianza con il testo precategorizzato. La capacità di KNN di valutare la vicinanza dei modelli di parole lo rende uno strumento efficace per questo caso d'uso. La classificazione del testo è particolarmente utile per attività come l'analisi del sentiment, in cui i testi vengono classificati come positivi, negativi o neutri, o per determinare la categoria di un articolo di notizie.

Vantaggi dell'algoritmo KNN in ML

KNN presenta numerosi vantaggi degni di nota, tra cui la semplicità, la versatilità e l'assenza di una fase di formazione.

Semplicità

Rispetto a molti altri algoritmi ML, KNN è facile da comprendere e utilizzare. La logica alla base di KNN è intuitiva: classifica o prevede (regressione) nuovi punti dati in base ai valori dei punti dati vicini, rendendolo una scelta popolare per i professionisti del machine learning, in particolare i principianti. Inoltre, oltre alla scelta di un valore per k, per utilizzare KNN è necessaria una regolazione minima dell'iperparametro.

Versatilità

KNN può essere utilizzato sia per compiti di classificazione che di regressione, il che significa che può essere applicato a un'ampia gamma di problemi e tipi di dati, dal riconoscimento delle immagini alla previsione dei valori numerici. A differenza degli algoritmi specializzati limitati a un tipo di attività, KNN può essere applicato a qualsiasi set di dati etichettato opportunamente strutturato.

Fase di formazione esplicita

Molti modelli ML richiedono una fase di formazione ad alta intensità di tempo e risorse prima di diventare utili. KNN, invece, memorizza semplicemente i dati di allenamento e li utilizza direttamente al momento della previsione. Pertanto, KNN può essere aggiornato con nuovi dati, che sono immediatamente disponibili per l'utilizzo nella previsione. Ciò rende KNN particolarmente interessante per piccoli set di dati.

Svantaggi dell'algoritmo KNN in ML

Nonostante i suoi punti di forza, KNN presenta anche diverse sfide. Questi includono elevati costi computazionali e di memoria, sensibilità al rumore e alle caratteristiche irrilevanti e la “maledizione della dimensionalità”.

Costo computazionale della previsione

Poiché KNN calcola la distanza tra un nuovo punto dati e ogni punto dati nel suo set di dati di addestramento complessivo ogni volta che effettua una previsione, il costo computazionale della previsione aumenta rapidamente con la crescita del set di dati. Ciò può comportare previsioni lente quando il set di dati è di grandi dimensioni o quando KNN viene eseguito su hardware insufficiente.

Maledizione della dimensionalità

KNN soffre della cosiddetta “maledizione della dimensionalità”, che limita la sua capacità di gestire dati ad alta dimensionalità. All’aumentare del numero di caratteristiche in un set di dati, la maggior parte dei punti dati diventa sparsa e quasi equidistante l’uno dall’altro. Pertanto, le misurazioni della distanza diventano meno utili, il che rende difficile per KNN trovare vicini in set di dati ad alta dimensione che siano veramente vicini.

Ad alta intensità di memoria

Una caratteristica unica di KNN è che memorizza l'intero set di dati di addestramento in memoria per l'utilizzo al momento della previsione. Quando si ha a che fare con memoria limitata o set di dati di grandi dimensioni, ciò può essere problematico e poco pratico. Altri algoritmi ML evitano questa sfida condensando e distillando i dati di addestramento in funzionalità apprese attraverso l'addestramento del modello e l'ottimizzazione dei parametri. KNN, d'altro canto, deve conservare ogni punto dati, il che significa che la memoria cresce linearmente con la dimensione del set di dati di addestramento.

Sensibilità al rumore e caratteristiche irrilevanti

La potenza di KNN risiede nel suo calcolo della distanza semplice e intuitivo. Tuttavia, ciò significa anche che caratteristiche o rumori non importanti possono causare calcoli della distanza fuorvianti, influenzando negativamente la precisione della previsione. Pertanto, con KNN vengono spesso utilizzate tecniche di selezione delle caratteristiche o di riduzione della dimensionalità, come l'analisi delle componenti principali (PCA), per assicurarsi che le caratteristiche importanti abbiano la maggiore influenza sulla previsione.