K-Nearest Neighbors semi-supervisionato
- Introdotto da
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Anno
- 2002 (semi-supervised extension); 1967 (KNN base)
- Tipo
- Semi-supervised classifier / label propagation
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il K-Nearest Neighbors semi-supervisionato estende l'algoritmo classico K-nearest neighbors per sfruttare ampi set di dati non etichettati insieme a un piccolo set etichettato.
Costruendo un grafo KNN su tutte le osservazioni e propagando le etichette note attraverso gli archi del grafo, il metodo inferisce etichette per punti non etichettati senza richiedere costose annotazioni manuali di ogni campione.
L’intuizione alla base del metodo
Immagina un'aula in cui solo una manciata di studenti ha cartellini con i nomi e il resto è anonimo. Il KNN standard può classificare uno studente anonimo solo guardando la manciata di vicini etichettati nelle vicinanze. Il KNN semi-supervisionato, invece, mappa l'intera stanza come una rete — ogni studente connesso ai suoi vicini più prossimi — e diffonde le etichette dagli studenti etichettati come inchiostro che si diffonde su carta bagnata. Poiché la rete cattura la struttura generale dei dati, le etichette raggiungono i punti non etichettati in modo principesco che rispetta la geometria sottostante piuttosto che ignorare la maggioranza non etichettata.
Storia
La propagazione delle etichette su grafi KNN è stata sistematizzata da Zhu e Ghahramani nel 2002, basandosi sulla SVM transduttiva di Vapnik e su precedenti idee di diffusione basate su grafi. Il framework è stato consolidato nel volume Semi-Supervised Learning (Chapelle et al., 2006) della MIT Press, che rimane il riferimento standard. Librerie scalabili di KNN approssimati (FAISS, Annoy) hanno successivamente reso l'approccio pratico su milioni di punti, e continua ad essere utilizzato come solida baseline per la classificazione semi-supervisionata di immagini e testi.
Quando usarlo
Utilizzare il KNN semi-supervisionato quando si dispone di un piccolo set etichettato e di un ampio pool non etichettato dalla stessa distribuzione, i dati risiedono in uno spazio relativamente a bassa dimensionalità (meno di circa 50 caratteristiche) e si ritiene che i punti vicini condividano la stessa classe. È ben adatto alla classificazione di patch di immagini, alla categorizzazione di testi con annotazioni sparse e a compiti di screening medico in cui l'etichettatura manuale è costosa. Evitarlo quando i dati etichettati e non etichettati provengono da distribuzioni diverse (covariate shift), lo spazio delle caratteristiche è molto ad alta dimensionalità (il grafo KNN diventa inaffidabile), il set di dati è abbastanza piccolo che il KNN completamente supervisionato è già sufficiente, o i confini di classe non si allineano con la struttura di densità locale dei dati.
Limiti e considerazioni
- La costruzione del grafo scala quadraticamente con la dimensione del set di dati a meno che non vengano utilizzati metodi di vicini più prossimi approssimati.
- Le prestazioni degradano nettamente in spazi ad alta dimensionalità dove le metriche di distanza perdono potere discriminatorio.
- Presuppone che i dati etichettati e non etichettati siano estratti dalla stessa distribuzione; il covariate shift invalida il metodo.
- Richiede un'attenta messa a punto di k, della larghezza di banda dei pesi degli archi e del parametro di miscelazione della propagazione.
- La propagazione delle etichette può amplificare errori di etichettatura iniziali su ampie porzioni del grafo.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Sfrutta dati non etichettati a basso costo per migliorare l'accuratezza oltre quanto possibile con il solo set etichettato.
- Nessuna assunzione di modello parametrico: si basa solo sulla geometria del vicinato locale.
- Gestisce naturalmente problemi multiclasse senza modifiche.
- La costruzione del grafo KNN è trasparente e facile da ispezionare.
- Funziona bene quando le classi formano cluster compatti e ben separati nello spazio delle caratteristiche.
Applicazioni
- Classificazione di immagini con un piccolo set di immagini etichettate e un ampio corpus non etichettato.
- Categorizzazione di testi e documenti dove l'etichettatura manuale è costosa.
- Classificazione di cartelle cliniche o vetrini patologici con annotazioni limitate da esperti.
- Rilevamento di frodi quando sono disponibili solo un piccolo numero di casi di frode confermati.
- Etichettatura di dati da sensori in contesti IoT industriali con eventi di verità a terra sparsi.
Come funziona
Come funziona
Viene costruito un grafo su tutte le osservazioni — sia etichettate che non etichettate. Ogni nodo corrisponde a un punto dati e archi diretti o non diretti collegano ogni nodo ai suoi k vicini più prossimi nello spazio delle caratteristiche. La scelta di k controlla quanto localmente o globalmente verranno propagate le etichette: un k piccolo mantiene la propagazione stretta; un k grande permette alle etichette di saltare attraverso intervalli più ampi.
I pesi degli archi catturano la forza della somiglianza tra nodi connessi, tipicamente tramite un kernel Gaussiano (RBF) applicato alla distanza euclidea tra i vettori delle caratteristiche. Un parametro di larghezza di banda sigma controlla quanto rapidamente la somiglianza decada con la distanza. Archi più forti trasportano le etichette più facilmente durante la propagazione.
Formula
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Le etichette vengono diffuse iterativamente dai nodi etichettati ai vicini non etichettati. Ad ogni iterazione, ogni nodo aggiorna la sua distribuzione di etichette morbide come una combinazione pesata delle distribuzioni correnti dei suoi vicini e della sua etichetta iniziale (se etichettato). Un parametro di miscelazione alpha bilancia l'influenza della struttura del grafo rispetto alle etichette rigide, e l'iterazione continua finché le distribuzioni non convergono.
Formula
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YUna volta che la propagazione converge, a ogni nodo non etichettato viene assegnata la classe con il punteggio di etichetta morbida più alto nella sua distribuzione convergente. I nodi etichettati sono bloccati alle loro vere etichette durante tutto il processo, quindi le etichette note non vengono mai sovrascritte.
Formula
\hat{y}_i = \arg\max_c F_{ic}Errori comuni
- Costruzione del grafo KNN senza normalizzare le caratteristiche, causando la dominanza delle caratteristiche ad alta varianza nei calcoli di distanza.
- Impostare k troppo grande, il che smussa i confini di classe autentici e produce distribuzioni di etichette sovra-smussate.
- Ignorare la possibilità che i dati non etichettati siano fuori distribuzione rispetto al set etichettato.
- Riportare l'accuratezza sui nodi non etichettati come se fosse una stima imparziale del set di test — i nodi non etichettati sono stati inclusi nel grafo durante l'addestramento.
- Saltare i controlli di convergenza e utilizzare un numero fisso e arbitrario di iterazioni di propagazione.
Domande frequenti
Come scelgo k?
Iniziare con k nell'intervallo 5-15 e ottimizzare tramite accuratezza di validazione etichettata tenuta da parte. Un k più piccolo fornisce confini più nitidi e locali; un k più grande permette alle etichette di propagarsi ulteriormente ma rischia di attraversare confini di classe autentici.
Posso valutare il metodo onestamente quando la maggior parte dei dati non è etichettata?
Tenere da parte un set di test etichettato dedicato che non viene mai aggiunto al grafo. I nodi nel grafo — anche quelli non etichettati — fanno parte dell'addestramento, quindi qualsiasi nodo etichettato che partecipa alla costruzione del grafo non deve servire anche come punto di test.
Cosa succede se il mio set di dati è troppo grande per costruire un grafo KNN completo?
Utilizzare librerie di vicini più prossimi approssimati come FAISS o Annoy per costruire il grafo in O(n log n) invece di O(n^2), quindi applicare la propagazione delle etichette sul grafo approssimato sparso.
Il KNN semi-supervisionato supera sempre il KNN supervisionato?
Non necessariamente. Se i dati non etichettati sono fuori distribuzione o lo spazio delle caratteristiche è ad altissima dimensionalità, il grafo è rumoroso e la propagazione può peggiorare le prestazioni. Confrontare sempre con una baseline KNN supervisionata prima di affermare un beneficio dai dati non etichettati.
È la stessa cosa di label spreading o label propagation in scikit-learn?
Strettamente correlato. LabelPropagation e LabelSpreading di scikit-learn implementano il framework di Zhu e Ghahramani utilizzando un grafo con kernel KNN o RBF, quindi sono implementazioni dirette del metodo qui descritto.
Metodi correlati
Fonti
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Apri il riferimento della pubblicazioneCopiato.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiato.