Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

I- INTRODUCTION: 1- Définition et historique : L’algorithme des k plus proches

I- INTRODUCTION: 1- Définition et historique : L’algorithme des k plus proches voisins s'écrit en abrégé k-NN ou KNN , de l'anglais k-nearest neighbors, appartient à la famille des algorithmes d’apprentissage automatique (machine learning). Le terme de machine learning a été utilisé pour la première fois par l’informaticien américain Arthur Samuel en 1959. Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt au début des années 2000 notamment grâce à la quantité de données disponibles sur internet. L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées. À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E). À noter qu’il est aussi possible d’utiliser l’algorithme des k plus proches voisins à des fins de régression en statistiques (on cherche à déterminer une valeur à la place d’une classe), mais cet aspect des choses ne sera pas abordé en première. De nombreuses sociétés (exemple les GAFAM) utilisent les données concernant leurs utilisateurs afin de ”nourrir” des algorithmes de machine learning qui permettront à ces sociétés d’en savoir toujours plus sur nous et ainsi de mieux cerné nos ”besoins” en termes de consommation. 2- Principe de l'algorithme : • On calcule les distances entre la donnée u et chaque donnée appartenant à E à l’aide de la fonction d. • On retient les k données du jeu de données E les plus proches de u. • On attribue à u la classe qui est la plus fréquente parmi les k données les plus proches. Suivant que l'on raisonne sur une ,deux, trois dimensions, le calcul de la distance entre deux points est plus au moins simple. Pour appliquer ce principe, il faudra : Algorithme des k-plus proches voisins On suppose que l'ensemble E contiennent n données labellisées et u , une autre donnée n’appartenant pas à E qui ne possède pas de label. Soit d une fonction qui renvoie la distance (qui reste à choisir) entre la donnée u et une donnée quelconque appartenant à E. Soit un entier k inférieur ou égal à n. Le principe de l’algorithme de k-plus proches voisins est le suivant: A.LOUGHANI + JNB 2 • Évaluer la distance qui sépare le nouvel élément de chacun des autres points de l'ensemble E. Chaque point de l'ensemble est caractérisé par son indice i. • Stocker ces valeurs de distance d dans une liste du type : [[d,i],[ …],...], où d est la distance qui sépare le nouvel élément du point d'indice i. • Trier la liste selon les valeurs des distances d. • Choisir les k premiers points de la liste triée qui sont donc les k-plus proches voisins. • Assigner une classe au nouvel élément en fonction de la majorité des classes représentées parmi les k-plus proches voisins. On aura donc besoin de trois fonctions : • une fonction distance pour calculer la distance entre deux points de coordonnées connues. • Une fonctions kvoisins qui détermine les k-plus proches voisins d'un nouvel élément. • Une fonction predire_classe qui détermine le résultat majoritaire des classes d'appartenance des k-plus proches voisins et assigne la classe du nouvel élément à cette classe majoritaire. II- Notion de distance : 1-Distance Euclidienne et distance de Manhattan: a-Sur une droite graduée: distance entre A et B est : d(A,B) = |abscisse de B – abscisse de A| b- Dans un plan : On suppose que le plan est muni d'un repère orthonormal (O;I;J). x 0 O 1 I 4 B -1 A = la plus grande abscisse – la plus petite abscisse = 4-(-1) = 4 + 1 = 5 d(A,B) = 5 unités. On peut donc écrire une fonction distance, avec Python, qui prend en arguments d'entrée deux coordonnées x1 et x2 et qui renvoie la valeur de la distance entre les deux points de coordonnées x1 et x2 Q1 : tester le programme python ci dessous. A.LOUGHANI + JNB 3 Soient A(xA;yA) et B(xB ;yB) deux points du plan, la distance euclidienne entre A et B est : d(A,B) = AB = √(xB−xA)²+( yB−yA)² Exemple : Soit A(-1;-2) et B(2;2) alors AB= √(2−(−1))²+(2−(−2)) ² = √(2+1)²+(2+2)² = √3²+4² = √9+16 = √25 =5 AB = 5 unités En Python , on a : from math import sqrt def distance(p, q): c- Distance de manhattan : La distance de Manhattan a été utilisée dans une analyse de régression en 1757 par Roger Joseph Boscovich. L’interprétation géométrique remonte à la fin du XIXe siècle et au développement de géométries non euclidiennes, notamment par Hermann Minkowski et son inégalité de Minkowski, dont cette géométrie constitue un cas particulier, particulièrement utilisée dans la géométrie des nombres (Minkowski 1910). La distance de Manhattan est appelée aussi taxi-distance, est la distance entre deux points parcourue par un taxi lorsqu'il se déplace dans une ville où les rues sont agencées selon un réseau ou quadrillage. Un taxi-chemin est le trajet fait par un taxi lorsqu'il se déplace d'un nœud du réseau à un autre en utilisant les déplacements horizontaux et verticaux du réseau. """ Renvoie la distance euclidienne entre deux points du plan. """ return sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2) Q2 : Si vous testez ce programme, des erreurs apparaissent : corrigez les pour un fonctionnement correct. Proposez une amélioration à ce programme. A.LOUGHANI + JNB 4 Entre deux points A et B, de coordonnées respectives ( X A , Y A ) et ( X B , Y B )la distance de Manhattan est définie par : d ( A , B ) = | X A − X B | + | Y A − Y B | . Dans l'exemple ci-dessus, on a : d(A,B) = | -1-2|+|-2-2| = |-3|+|-4| =3+4 =7 Réservée aux classifications hiérarchiques, la distance de manhattan ne majore pas la pondération des points extrêmes . En revanche, les temps de calcul sont particulièrement longs… A.LOUGHANI + JNB 5 Illustration : Dans le plan ci-dessus, les points A et B sont séparés de 6 unités sur une variable et de 8 unités sur une autre variable. La distance de Manhattan est donc de 14 (en rouge) tandis que la distance euclidienne est la racine carrée de 6² + 8², soit 10 (en bleu). Manhattan est donc supérieure de 40 %. Si les points étaient très éloignés, mettons de 20 et 40, Manhattan = 60 et Euclide = 44,7, soit une différence de 34,16 %... 2- Distance de Hamming : La distance de Hamming est une notion mathématique, définie par Richard Hamming, et utilisée en informatique. Elle permet de quantifier la différence entre deux séquences de symboles. C'est une distance au sens mathématique du terme. À deux suites de symboles de même longueur, elle associe le nombre de positions où les deux suites diffèrent. Exemples : Considérons les mots binaires suivants : a = (0001111) et b = (1101011) alors d = 1+1+0+0+1+0+0=3 La distance entre a et b est égale à 3 car 3 bits diffèrent. En Python, on a: Q3 : tester ce programme • La distance de Hamming entre "1011101" et "1001001" est 2. • La distance de Hamming entre "2143896" et "2233796" est 3. • La distance de Hamming entre "ramer" et "cases" est 3. En Python on a le code suivant pour le calcul de cette distance de Hamming: Q4 : tester ce programme avec les exemples ci dessus puis avec les mots que vous voulez tester A.LOUGHANI + JNB 6 3- Distance d'édition : Les distances d’édition permettent de comparer deux mots entre eux ou plus généralement deux séquences de symboles entre elles. L’usage le plus simple est de trouver, pour un mot mal orthographié, le mot le plus proche dans un dictionnaire, c’est une option proposée dans la plupart des traitements de texte. La distance présentée est la distance de Levenshtein . Elle est parfois appelée Damerau Levenstein Matching (DLM) . Cette distance fait intervenir trois opérations élémentaires : • comparaison entre deux caractères • insertion d’un caractère • suppression d’un caractère Pour comparer deux mots, il faut construire une méthode associant ces trois opérations afin que le premier mot se transforme en le second mot. L’exemple suivant utilise les mots idstzance et distances, il montre une méthode permettant de passer du premier au second. La distance sera la somme des coûts associés à chacune des opérations choisies. La comparaison entre deux lettres identiques est en général de coût nul, toute autre opération étant de coût strictement positif. mot 1 mot 2 opération coût i d comparaison entre i et d 1 d i comparaison entre d et i 1 s s comparaison entre s et s 0 z . a a comparaison entre a et a 0 t t comparaison entre t et t 0 suppression de z 1 Avec close et cloue, l'instruction dans le console, donne : >>>dist_hamming("close", "cloue") >>>d=1. Tester ce programme avec longmot et liongmot ou encore avec longmot et longmoit puis avec les mots que uploads/Ingenierie_Lourd/ k-voisins.pdf