K-plus proches voisins semi-supervisés
- Introduite par
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Année
- 2002 (semi-supervised extension); 1967 (KNN base)
- Type
- Semi-supervised classifier / label propagation
- Famille
- Machine learning
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Le KNN semi-supervisé étend l'algorithme classique des K-plus proches voisins pour exploiter de grands ensembles de données non étiquetées en complément d'un petit ensemble étiqueté.
En construisant un graphe KNN sur toutes les observations et en propageant les étiquettes connues à travers les arêtes du graphe, la méthode infère les étiquettes des points non étiquetés sans nécessiter une annotation manuelle coûteuse de chaque échantillon.
L’intuition derrière la méthode
Imaginez une salle de classe où seule une poignée d'élèves ont des étiquettes nominatives et les autres sont anonymes. Le KNN standard ne peut classer un élève anonyme qu'en examinant la poignée de voisins étiquetés proches. Le KNN semi-supervisé, quant à lui, cartographie l'ensemble de la salle comme un réseau — chaque élève étant connecté à ses plus proches voisins — et diffuse les étiquettes à partir des élèves étiquetés comme de l'encre se répandant sur du papier humide. Parce que le réseau capture la structure globale des données, les étiquettes atteignent les points non étiquetés de manière rigoureuse qui respecte la géométrie sous-jacente plutôt que d'ignorer la majorité non étiquetée.
Histoire
La propagation d'étiquettes sur les graphes KNN a été systématisée par Zhu et Ghahramani en 2002, s'appuyant sur le SVM transductif de Vapnik et des idées antérieures de diffusion basées sur les graphes. Le cadre a été consolidé dans le volume de MIT Press "Semi-Supervised Learning" (Chapelle et al., 2006), qui reste la référence standard. Les bibliothèques de KNN approximatifs évolutives (FAISS, Annoy) ont ensuite rendu l'approche pratique sur des millions de points, et elle continue d'être utilisée comme une base solide pour la classification semi-supervisée d'images et de textes.
Quand l’utiliser
Utilisez le KNN semi-supervisé lorsque vous disposez d'un petit ensemble étiqueté et d'un grand ensemble non étiqueté provenant de la même distribution, que les données résident dans un espace de dimension relativement faible (moins d'environ 50 caractéristiques), et que vous estimez que les points voisins partagent la même classe. Il est bien adapté à la classification de patchs d'images, à la catégorisation de textes avec des annotations éparses, et aux tâches de dépistage médical où l'étiquetage par des experts est coûteux. Évitez-le lorsque les données étiquetées et non étiquetées proviennent de distributions différentes (décalage de covariables), que l'espace des caractéristiques est de très haute dimension (le graphe KNN devient peu fiable), que l'ensemble de données est suffisamment petit pour que le KNN entièrement supervisé suffise déjà, ou que les frontières de classe ne s'alignent pas avec la structure de densité locale des données.
Limites et points d’attention
- La construction du graphe s'adapte quadratiquement à la taille de l'ensemble de données, à moins que des méthodes de plus proches voisins approximatifs ne soient utilisées.
- Les performances se dégradent fortement dans les espaces de grande dimension où les métriques de distance perdent leur pouvoir discriminant.
- Suppose que les données étiquetées et non étiquetées sont tirées de la même distribution ; un décalage de covariables invalide la méthode.
- Nécessite un réglage minutieux de k, de la bande passante des poids des arêtes et du paramètre de mélange de la propagation.
- La propagation des étiquettes peut amplifier les erreurs d'étiquetage initiales sur de grandes portions du graphe.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Exploite des données non étiquetées peu coûteuses pour améliorer la précision au-delà de ce qui est possible avec le seul ensemble étiqueté.
- Aucune hypothèse de modèle paramétrique : repose uniquement sur la géométrie du voisinage local.
- Gère naturellement les problèmes multi-classes sans modification.
- La construction du graphe KNN est transparente et facile à inspecter.
- Fonctionne bien lorsque les classes forment des grappes compactes et bien séparées dans l'espace des caractéristiques.
Applications
- Classification d'images avec un petit ensemble d'images étiquetées et un grand corpus non étiqueté.
- Catégorisation de textes et de documents où l'étiquetage manuel est coûteux.
- Classification de dossiers médicaux ou de lames de pathologie avec des annotations d'experts limitées.
- Détection de fraude lorsque seul un petit nombre de cas de fraude confirmés est disponible.
- Étiquetage de données de capteurs dans des environnements IoT industriels avec des événements de vérité terrain rares.
Comment ça marche
Comment ça marche
Un graphe est construit sur toutes les observations — étiquetées et non étiquetées. Chaque nœud correspond à un point de données, et des arêtes dirigées ou non dirigées connectent chaque nœud à ses k plus proches voisins dans l'espace des caractéristiques. Le choix de k contrôle la propagation des étiquettes, localement ou globalement : un petit k maintient une propagation serrée ; un grand k permet aux étiquettes de franchir des écarts plus importants.
Les poids des arêtes capturent la force de similarité entre les nœuds connectés, généralement via un noyau gaussien (RBF) appliqué à la distance euclidienne entre les vecteurs de caractéristiques. Un paramètre de bande passante sigma contrôle la vitesse à laquelle la similarité décroît avec la distance. Des arêtes plus fortes transportent plus facilement les étiquettes pendant la propagation.
Formule
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Les étiquettes sont propagées itérativement des nœuds étiquetés vers les voisins non étiquetés. À chaque itération, chaque nœud met à jour sa distribution d'étiquettes "douces" comme une combinaison pondérée des distributions actuelles de ses voisins et de sa propre étiquette initiale (si étiquetée). Un paramètre de mélange alpha équilibre l'influence de la structure du graphe par rapport aux étiquettes "dures", et l'itération se poursuit jusqu'à ce que les distributions convergent.
Formule
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YUne fois la propagation convergée, chaque nœud non étiqueté se voit attribuer la classe avec le score d'étiquette "douce" le plus élevé dans sa distribution convergée. Les nœuds étiquetés sont fixés à leurs vraies étiquettes tout au long du processus, de sorte que les étiquettes connues ne sont jamais écrasées.
Formule
\hat{y}_i = \arg\max_c F_{ic}Pièges courants
- Construire le graphe KNN sans normaliser les caractéristiques, ce qui fait que les caractéristiques à forte variance dominent les calculs de distance.
- Définir k trop grand, ce qui lisse les véritables frontières de classe et produit des distributions d'étiquettes trop lissées.
- Ignorer la possibilité que les données non étiquetées soient hors distribution par rapport à l'ensemble étiqueté.
- Rapporter la précision sur les nœuds non étiquetés comme s'il s'agissait d'une estimation non biaisée de l'ensemble de test — les nœuds non étiquetés ont "fuité" dans le graphe pendant l'entraînement.
- Ignorer les vérifications de convergence et utiliser un nombre fixe et arbitraire d'itérations de propagation.
Questions fréquentes
Comment choisir k ?
Commencez avec k dans la plage 5-15 et ajustez-le par validation de la précision sur un ensemble étiqueté de validation. Un k plus petit donne des frontières plus nettes et plus locales ; un k plus grand permet aux étiquettes de se propager plus loin mais risque de franchir de véritables frontières de classe.
Puis-je évaluer la méthode honnêtement lorsque la plupart des données ne sont pas étiquetées ?
Réservez un ensemble de test étiqueté dédié qui n'est jamais ajouté au graphe. Les nœuds du graphe — même non étiquetés — font partie de l'entraînement, donc tout nœud étiqueté qui participe à la construction du graphe ne doit pas non plus servir de point de test.
Que faire si mon ensemble de données est trop grand pour construire un graphe KNN complet ?
Utilisez des bibliothèques de plus proches voisins approximatifs telles que FAISS ou Annoy pour construire le graphe en O(n log n) plutôt qu'en O(n^2), puis appliquez la propagation d'étiquettes sur le graphe approximatif clairsemé.
Le KNN semi-supervisé surpasse-t-il toujours le KNN supervisé ?
Pas nécessairement. Si les données non étiquetées sont hors distribution ou si l'espace des caractéristiques est de très haute dimension, le graphe est bruité et la propagation peut nuire aux performances. Comparez toujours avec une base de référence KNN supervisée avant de revendiquer un avantage des données non étiquetées.
Est-ce la même chose que la propagation d'étiquettes (label spreading) ou la diffusion d'étiquettes (label propagation) dans scikit-learn ?
C'est étroitement lié. Les implémentations LabelPropagation et LabelSpreading de scikit-learn mettent en œuvre le cadre de Zhu et Ghahramani en utilisant un graphe de noyau KNN ou RBF, ce sont donc des implémentations directes de la méthode décrite ici.
Méthodes associées
Sources
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Ouvrir la référence de la publicationCopié.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN : 978-0-262-03358-9Copié.