Machine Learning : Algorithme KNN (K-Nearest Neighbors)

Thèmes abordés

Machine Learning, algorithme KNN K-Nearest Neighbors, apprentissage, régression, classification, ensemble d'apprentissage, k points, k voisins, delta de Kronecker, distance euclidienne, distance de Manhattan, distance de Minkowski, distance de Hamming, corrélation

Résumé du document

KNN est un algorithme d'apprentissage supervisé qui stocke simplement les exemples d'apprentissage étiquetés durant la phase d'apprentissage.
Ensuite, pour faire une prédiction, KNN trouve les k voisins les plus proches de l'exemple en question et calcule l'étiquette de classe (classification) ou la cible continue (régression) sur la base de ces k points.

Extraits

[...] Machine Learning : Algorithme KNN (K-Nearest Neighbors) Machine Learning Séance 2 : KNN Aziz KHAMJANE Principe K-NN est un algorithme d'apprentissage supervisé qui stocke simplement les exemples d'apprentissage étiquetés durant la phase d'apprentissage. Ensuite, pour faire une prédiction, k-NN trouve les k voisins les plus proches de l'exemple en question et calcule l'étiquette de classe (classification) ou la cible continue (régression) sur la base de ces k points. Principe Principe Nécessite les éléments suivants : Un ensemble d'enregistrements étiquetés Une mesure de similarité pour calculer la distance/similarité entre une paire d'enregistrements. [...]

[...] KNN : choix de la valeur de k Choix de la valeur de k : Si k est trop petit, k-NN est trop sensible aux points de bruit. Si k est trop grand, le voisinage peut inclure des points d'autres classes. X KNN : problème des données manquantes Comment gérer les valeurs manquantes dans les ensembles d'apprentissage et de test ? Le calcul des similarités requièrent normalement la présence de tous les attributs. Certaines approches utilisent le sous-ensemble d'attributs présents dans deux instances. Cette approche peut ne pas donner de bons résultats, car elle utilise effectivement différentes mesures de similarité pour chaque paire d'instances. [...]

[...] Pour les documents (le texte), le cosinus est meilleur que la corrélation ou la distance euclidienne. Chaque document est représenté par un vecteur contenant le nombre d'occurrence de chaque mot vs La distance euclidienne = 1,4142 pour les deux paires, mais la mesure de similarité cosinus a des valeurs différentes pour ces paires. KNN : choix de la mesure de similarité Nous pouvons modifier les métriques de distances en ajoutant un poids à chaque variable (dimension). Dans le cas de la distance euclidienne : Pour une implémentation facile, on utilise la notation matricielle suivante : Où KNN : pour la classification Pour la classification, KNN consiste à prédire l'étiquette de classe cible en utilisant le vote majoritaire. [...]

[...] On utilise souvent la moyenne sur les k plus proches voisins: KNN : pondération des distances Dans k-NN, les k voisins participent de la même manière au vote majoritaire ou à la moyenne. Cependant, surtout si le rayon entourant un ensemble de voisins est grand, nous pouvons vouloir donner un poids plus fort aux voisins qui sont plus proches de l'exemple en question. Par exemple, nous pouvons attribuer un poids w aux voisins dans la classification k-NN. De la même manière, on peut définir la fonction suivante pour la régression : KNN : pondération des distances De la même manière, on peut définir la fonction suivante pour la régression : Selon Tom Mitchell, le poids le plus populaire est l'inverse de la distance au carré. [...]