Chapitre I - Introduction aux algorithmes d’apprentissage automatique PDF

Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Chapitre I : Introduction aux algorithmes d’apprentissage automatique I- Définition En 1959, le terme "apprentissage automatiq...

Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Chapitre I : Introduction aux algorithmes d’apprentissage automatique I- Définition En 1959, le terme "apprentissage automatique" a été introduit pour la première fois par professeur ArthurSamuel. Il fut le premier à introduire le terme "apprentissage automatique". L'apprentissage automatique est un domaine de l'intelligence artificielle. Il utilise des méthodes statistiques pour donner à l'ordinateur la capacité "d'apprendre" à partir des données, sans être explicitement programmé. Le professeur Samuel adéfini alors le terme machine Learning comme suit : « le domaine d'étude qui donne aux ordinateurs la capacité à apprendre sans être explicitement programmé ». L’apprentissage machine génère un modèle mathématique à partir des données par l’implication d’un nombre important de variables inconnues au départ. Les paramètres sont configurés au cours d’une phase d’apprentissage, par l’utilisation d’un ensemble de données d’entrainement pour chercher des liens et les classifie. Le processus d'apprentissage améliore le modèle de la machine au cours du temps. Le modèle évolué est utilisé pour faire des prédictions futures. L’apprentissage peut varier de très simple, comme le fait de noter un numéro de téléphone, au très profond. Les différentes méthodes d’apprentissage machine sont sélectionnées en fonction de la nature de la tâche à exécuter. Dans ce chapitre, nous nous concentrerons sur une classe de problèmes d’apprentissage qui peut sembler restreinte, mais possèdeen fait un champ d’application très large : il s’agit d’apprendre à partir d’un couple d’entrée-sortie, une fonction qui prédise la valeur de sortie pour de nouvelles valeurs d’entrée. II- Algorithmes de Machine Learning L'algorithme d'apprentissage automatique est une technique par laquelle lesystème extrait des modèles utiles à partir de données historiques. Ces motifspeuvent être appliqués à des nouvelles données. L’objectif est que le système apprenne une transformationspécifiqueentrée/sortie.La qualité des données est essentielle à la précision des résultats de l'apprentissage automatique. 1 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI 1- Les approches de Machine Learning a- Apprentissage supervisé : c’est un apprentissage par l’utilisation des données étiquetées. La machine pourra par la suite lire et prédire de nouveaux labels pour de nouvelles données. En effet, Un algorithme d'apprentissage supervisé analyseN exemples de couples d’entrée-sortie (x1, y1), (x2, y2), …, (xN, yN), où chaque yj a été produit par une fonction inconnue y=f(x) et produit une fonction inférée h qui approche la vraie fonction f. Ici x et y peuvent prendre toute valeur, ce ne sont pas nécessairement des nombres réels. La fonction h est une hypothèse. L’apprentissage est une recherche dans l’espace des hypothèses possibles, d’une hypothèse qui se comporte bien, même sur de nouveaux exemples n’appartenant pas à l’ensemble d’apprentissage. Pour mesure l’exactitude d’une hypothèse, on lui fournit un ensemble de test contenant des exemples différents de ceux de l’ensemble d’apprentissage. On dit qu’une hypothèse généralise bien si elle prédit correctement la valeur de y pour des exemples inédits. Dans la pratique, les problèmes qui sont résolus en utilisant l'apprentissage supervisé sont regroupés enproblèmes de régression ou de classification. En effet : 2 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI La classification consiste à prédire une étiquette de classe discrète, telle que « ensoleillé, nuageux, ou pluvieux », « noir, blanc ou gris » et « tumeur ou non tumeur ». Il s’agit d’une « classification booléenne » ou « binaire » s’il n’y a que deux valeurs. La régression est la prédiction d’une quantité continu tels que « la température qu’il fera demain », « poids », « probabilité » et « coût». Techniquement, résoudre un problème de régression revient à trouver une espérance conditionnelle, ou valeur moyenne de y, car la probabilité de trouver exactement la bonne valeur réelle de y est zéro. La figure 1 représente un exemple simple : approcher par une fonction linéaire un ensemble de points donnés. Il s’agit d’un ensemble de points du plan (x,y), où y=f(x). On ne connait pas f, mais on va l’approcher par une fonction h choisie dans un espace d’hypothèsesH, qui représentera dans cet exemple, l’ensemble des polynômes. La fig. 1a représente des points de données qui peuvent être joignable par une droite d’équation 0,4x+3. On appelle cette droite une hypothèse cohérente parce qu’elle passe par toutes les données. La fig. 1b montre un polynôme de degré élevé qui est aussi cohérent avec les mêmes données. Il s’agit d’un problème fondamental en apprentissage automatique inductif. La question est comment choisir parmi plusieurs hypothèses cohérentes ? Nous pouvons sélectionner l’hypothèse la plus simple des hypothèses cohérentes avec les données. Ce principe s’appelle le rasoir d’Occam. Fig.1 : (a) Exemples de couples (x, f(x)) avec une hypothèse linéaire cohérente, (b) une hypothèse cohérente sous forme d’un polynôme de degré 7 pour le même ensemble de données. 3 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI (a) (b) Fig.2 :a)Un ensemble de données exactement recouvert par un polynôme de degré 6 ou approché par une fonction linéaire, (b) une fonction sinusoïdale simple qui recouvre exactement le même ensemble de données. La figure 2a montre un 2ème ensemble de données, un polynôme de degré 6 pour approcher exactement ces points. On montre qu’une ligne droite qui n’est pas cohérente avec aucun des points de données, mais qui pourrait généraliser avec des valeurs non montrées de x. En général, il existe un compromis entre des hypothèses complexes qui approchent bien les données d’apprentissage et des hypothèses plus simples qui peuvent mieux généraliser. A la figure 2b, on élargie l’espace des hypothèses H pour autoriser des polynômes en x et sin x et on trouve que les données pourraient être rapprochées par une fonction simple de la forme : ax + b + c. sinx. On voit bien l’importance du choix de l’espace des hypothèses. b- Apprentissage non supervisé : l’agent apprend des structures dans les données d’entrée, il détecte des modèles et les relations entre données sans utiliser de données étiquetées. Un des algorithmes des plus populaires d’apprentissage non supervisé est l’algorithme de clustering. En effet, il s’agit de découvrir comment diviser l'ensemble de données en un nombre de groupes de façon où les points de données dans les mêmes groupes soient plus similaires les uns aux autres comparés aux points de données dans d'autres groupes. c- Apprentissage semi-supervisé : c’est une technique d’apprentissage automatique qui se situe entre apprentissage supervisé et apprentissage non supervisé. Cette technique inclue quelques données étiquetées et une grande portion de données non-étiquetées. ci-dessous un exemple qui utilise un pseudo-labelling : - Utiliser des données étiquetées pour entrainer le model ; - Utiliser le modèle obtenu pour attribuer des étiquettes aux données non- étiquetées ; 4 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI - Utiliser les données étiquetées et la nouvelle génération des données étiquetées pour créer un nouveau model. d- Apprentissage par renforcement L’agent apprend une série de renforcements, c’est-à-dire de récompenses et de punitions c’est-à-dire il utilise des essais et des erreurs (une approche enrichissante).L'algorithme découvre une association entre le but et laséquence d'événements qui mène à un résultat positif. Exemples d'applications d'apprentissage par renforcement : Robotique : Un robot qui doit trouver son chemin. Voitures autonomes. 2- Algorithmes de Machine Learning Nous allons explorer les différents algorithmes supervisés et non supervisés d’apprentissage automatique, les algorithmes de régression et de classification linéaires et non linéaires.Lorsqu’on essaye de comprendre un problème et les algorithmes de machine Learning, nous pourrons sélectionner l’algorithme le plus adéquat. Dans ce qui suit, nous allons définir le principe de quelques algorithmes : - Classification Naïve Bayes (classification supervisée – probabiliste) - Régression linéaire (régression supervisée) - Régression logistique (classification supervisée) - Machine à vecteurs de support (SVM) (supervisé linéaire ou classification non linéaire) - Arbre de décision (classification non linéaire supervisée) - Regroupement K-means (apprentissage non supervisé) a- Classement naïf de Bayes Les classificateurs Bayes naïfs supposent que la valeur d'une caractéristique particulière estindépendante de la valeur de toute autre caractéristique, compte tenu de la classe de la variable. Par exemple, un fruit peut être assimilé à une pomme s'il est rouge, rond etenviron 10 cm de diamètre. 5 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Caractéristiques : couleur, rondeur et diamètre. Hypothèse : Chacune de ces caractéristiques contribue indépendamment à laprobabilité que ce fruit soit une pomme, quelles que soient les corrélations possiblesentre les caractéristiques de couleur, de rondeur et de diamètre. Exemple : utilisez Naïve Bayes pour prédire si une pomme rouge, de forme ronde, de diamètre 10 cm représente une pomme ou non. Echantillon N° Couleur Forme Diamètre Est une pomme 1 Rouge Arrondie >=10 cm Oui 2 Rouge Arrondie >=10 cm Non 3 Rouge Arrondie >=10 cm Oui 4 Jaune Arrondie >=10 cm Non 5 Jaune Arrondie 10cm | Pomme = Oui). Naïve Bayes suppose que les caractéristiques des données d'entrée (la pommeParamètres) sont indépendantes. 𝐷 𝑝(𝑥|𝐶𝑘 ) = ∏ 𝑝(𝑥𝑖 |𝐶𝑘 ) 𝑖=1 La formule de Naïve Bayes est donnée par ce modèle. Notre objectif est de calculer la formule pour atteindrep(CK |x), où K est une classe quelconque (CY ou CN). 5. Calculez la probabilité conditionnelle d'avoir chaque caractéristique étant donné que la classe est CY : p(x|CY) =p(Couleur = Rouge, Forme = rond, Diamètre =>10 cm | Pomme = Oui). Naïve Bayes suppose que les caractéristiques des données d'entrée (les caractéristiques de l'objet) sontindépendantes, pour obtenir la valeur p(x|CY), nous calculons la probabilité conditionnelle de chaque caractéristique à untemps avec la classe CY, puis multiplier toutes les valeurs. Ainsi, on peut réécrire p(x|CY) comme suit : 7 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI = p(Couleur = Rouge | Pomme = Oui) X p(Forme = rond | Pomme = Oui) XP(Diamètre => 10 cm | Pomme = Oui) Identique pour p(x| CN) : = p(Couleur = Rouge | Pomme = Non) X p(Forme = rond | Pomme = Non) X P(Diamètre => 10 cm | Pomme = Non) 6. Calculez chaque probabilité conditionnelle : P(Couleur = Rouge | Pomme = Oui) = 3/5 (Sur cinq pommes, trois d'entre elles étaient rouges.) P(Couleur = Rouge | Pomme = Non) = 2/5 P(Forme = Rond | Pomme = Oui) = 4/5 P(Forme = Rond | Pomme = Non) = 2/5 P(Diamètre => 10 cm | Pomme = Oui) = 2/5 P(Diamètre => 10 cm | Pomme = Non) = 3/5 Couleur Forme Diamètre Pomme ? Rouge Arrondie >=10 cm Oui Rouge Arrondie >=10 cm Non Rouge Arrondie >=10 cm Oui Jaune Arrondie >=10 cm Non Jaune Arrondie < 10 cm Oui Jaune Cylindrique < 10 cm Non Jaune Cylindrique < 10 cm Oui Jaune Cylindrique >=10 cm Non Rouge Cylindrique < 10 cm Non Rouge Arrondie < 10 cm Oui Maintenant, nous avons toutes les valeurs dont nous avons besoin. Comme mentionné à l'étape 5, nous multiplions les probabilités conditionnelles comme suit : 8 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI P (Couleur = Rouge | Pomme = Oui) X p (Forme = rond | Pomme = Oui) XP (Diamètre => 10 cm | Pomme = Oui)= (3/5) × (4/5) × (2/5) = 0,192 p(Couleur = Rouge | Pomme = Non) X p(Forme = rond | Pomme = Non) XP(Diamètre => 10 cm | Pomme = Non)= (2/5) × (2/5) × (3/5) = 0,096 p(Pomme = Oui) = 5/10 p(Pomme = Non) = 5/10 Comparer p (CY | x) à p (CN | x) : p(𝐶𝑌 |𝑥 ) If 𝑥 = > 1 ∴ 𝑋 ∈ 𝐶𝑌 , 𝑒𝑙𝑠𝑒𝑥 ∈ 𝐶𝑁 p(𝐶𝑁 |𝑥 ) 𝑝(𝐶𝑌 |𝑥) 𝑝(𝑥|𝐶𝑌 )𝑝(𝐶𝑌 ) 0.192 × 0.5 = = =2 𝑝(𝐶𝑁 |𝑥) 𝑝(𝑥|𝐶𝑁 )𝑝(𝐶𝑁 ) 2𝑎0.096 × 0.5 Par conséquent, le verdict est qu'il s'agit d'une pomme. b- Régression linéaire à une variable Une fonction linéaire d’une seule variable (une ligne droite) d’entrée x et de sortie en y est de la forme linéaire y=w1.x+w0 où w0 et w1 sont des coefficients réels à chercher. On interprète les coefficients w0 et w1 comme des poids (weight). La valeur de y change en modifiant les valeurs des poids. On définit le vecteur w comme [w0, w1] et on pose :ℎ𝑤 = 𝑤1. 𝑥 + 𝑤0 Fig.3. : (a) Des données des coûts des maisons en vente à Californie en 2009 avec l’hypothèse linéaire qui minimise la perte quadratique : y= 0.232x+246. (b) Graphe de la fonction de perte pour différentes valeurs de (w0, w1). 9 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI La fig.3 représente un exemple d’ensemble d’apprentissage à n points du plan x, y, où chaque point représente la taille en pieds carrés, et le prix d’une maison à vendre. On appelle régression linéaire le problème qui consiste à trouver la fonction ℎ𝑤 qui approche le mieux ces données c’est-à-dire trouver les poids [w0, w1] qui rendent la perte empirique minimale. On utilise la fonction de perte quadratique L2,qu’on somme sur tous les exemples d’apprentissage : 𝑁 𝑁 𝑁 2 2 𝑃𝑒𝑟𝑡𝑒(ℎ𝑤 ) = ∑ 𝐿2 (𝑦𝑗 , ℎ𝑤 (𝑥𝑗 )) = ∑(𝑦𝑗 − ℎ𝑤 𝑥𝑗 ) = ∑ (𝑦𝑗 − (𝑤1 𝑥𝑗 + 𝑤0 )). 𝑗=1 𝑗=1 𝑗=1 La fonction atteint un minimum lorsque les dérivées partielles par rapport à w0 et w1 valent zéro : 𝑁 𝑁 𝜕 2 𝜕 2 ∑ (𝑦𝑗 − (𝑤1 𝑥𝑗 + 𝑤0 )) = 0 𝑒𝑡 ∑ (𝑦𝑗 − (𝑤1 𝑥𝑗 + 𝑤0 )) = 0. 𝜕𝑤0 𝜕𝑤1 𝑗=1 𝑗=1 𝑁(∑ 𝑥𝑗.𝑦𝑗 )−(∑ 𝑥𝑗 )(∑ 𝑦𝑗 ) (∑ 𝑦𝑗 −𝑤1 (∑ 𝑥𝑗 )) Ces solutions ont un poids unique : 𝑤1 = 2 ; 𝑤0 = ; 𝑁(∑ 𝑥𝑗2 )−(∑ 𝑥𝑗 ) 𝑁 Dans le cas de la fig.3, la solution est w1=0.232, w0=246, et la ligne correspondante à ces poids est tracée en pointillés sur la fig.3a. Pour une régression linéaire à une seule variable, l’espace des points définis par w0 et w1 est un graphe 3D. La fig.3breprésente le graphe de la fonction de perte pour différentes valeurs de (w0, w1),on note que la fonction de perte est convexe, avec un seul minimum global. Cela vaut pour tout problème de régression linéaire avec une fonction de perte L2, ce qui a pour conséquence l’absence de minima locaux. Exemples d’applications : - Analyser l'efficacité du marketing, les prix et les promotions sur la vente d'un produit ; - Prévoir les ventes en analysant les anciennes ventes mensuelles de l'entreprise au cours de quelques années ; - Prédire le cout des bâtiments. Exercice : Supposons qu’on est en train d’étudier l’état réel du marché immobilier. L’objectif est de prédire le cout d’un appartement étant donné sa superficie en se basant sur l’historique des ventes. Superficie Coût 30 30.000 70 40.000 90 55.000 10 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI 110 60.000 130 80.000 150 90.000 180 95.000 190 110.000 Question : pour un appartement de 140 m2, qu’elle est son coût estimé ? Quelle est la réponse correcte ? : - $ 60.000 - $ 95.000 - $ 85.000 Pour répondre à cette question, nous avons besoin de tracer une ligne la plus représentative de la distribution des points. Dans un espace de dimensions supérieur à 2, nous avons plus qu’une entrée (X), la ligne est appelée un plan ou un hyper plan. L’équation peut être générée à partir d’une régression linéaire simple à une régression linéaire multiple comme suit : Y(X)=p0 +p1 *X1 +p2 *X2 +...+pn*Xn Fig.3.: Régression linéaire 11 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI */ Fig.4. : Régression logistique c- Régression logistique La régression logistique est un algorithme de classification supervisé. Il est différent de la régression linéaire où la variable de sortie est une catégorie ou une classe. La cible est une catégorie discrète ou une classe et non pas une valeur continue comme dans le cas de la régression linéaire. Nous pourrons citer comme exemple les classes « temps nuageux », « temps pluvieux » et « temps ensoleillé ». La régression logistique est nommée pour la fonction utilisée dans le corps de l’algorithme. La fonction logistique ou fonction sigmoïde est une courbe de forme en S pour la classification des données à travers des classes multiples. Elle peut avoir un nombre réel entre 0 et 1. Son équation est : 𝑒𝑡 1 ℎ(𝑡) = 𝑡 = 𝑒 + 1 1 + 𝑒 −𝑡 Durant la phase d’apprentissage, le système essaye de générer le meilleur model (estimation de l’ensemble de paramètres p0, p1, …) qui peut prédire la probabilité que Y soit dans la classe A ou B étant donné l’entrée X. La fonction sigmoïde classe la valeur de l’entrée dans l’intervalle [0,1].Si la sortie est de valeur 0.85, la classe prédite est 1. d- Machines à vecteurs de support Les machines à vecteurs de support, SVM (Support Vector Machines), est l’approche la plus populaire pour l’apprentissage supervisé. Elles sont caractérisées par les propriétés suivantes qui les rendent séduisantes : 12 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI */ les SVM génèrent un séparateur à marge maximale, c’est une frontière de décision ayant la plus grande distance possible entre les exemples d’entrainement. Cela leur permet de bien généraliser. */ Les SVM créent un hyperplan linéaire séparateur, mais sont capables de représenter les données dans un espace de dimension plus grande. Il arrive souvent que des données inséparables linéairement dans l’espace d’entrée d’origine le soient dans un espace de plus grande dimension. */ Les SVM ont la flexibilité de représenter des fonctions complexes, mais sont résistantes au surapprentissage. La figure 5a traite un problème de classification binaire avec 3 candidats comme frontière de décision qui sont tous trois des séparateurs linéaires. La régression logistique trouverait une droite séparatrice dont la position exacte dépend des tous les points exemples. L’idée fondamentale des SVM est que certains exemples sont plus importants que d’autres, et que se concentrer sur ceux-là peut donner une meilleure généralisation. Considérons la plus basse des trois droites dans (a). Elle s’approche beaucoup de cinq des cercles noirs. Malgré qu’elle classe tous les exemples correctement et rende donc la perte minimale, il est quelque peu inquiétant que tant d’exemples soient proches de la droite ; il se peut que d’autres cercles noirs apparaissent de l’autre côté de la droite. Fig.5. : Classification par une machine à vecteurs de support : (a) Deux classes de points (cercles noirs et blancs) et trois séparateurs linéaires possibles. (b) La séparatrice à maximum 13 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI de marge est au milieu de la marge (l’aires entre les lignes pointillées). Les vecteurs de support (points indiqués par des cercles larges) sont les exemples les plus proches de la séparatrice. Les SVM s’intéressent à ce problème : au lieu de rendre minimale la perte empirique, les MVS tendent de rendre minimale la perte en généralisation attendue. La théorie algorithmique de l’apprentissage fournit des arguments qui suggèrent qu’on rendra la perte de généralisation minimale en choisissant le séparateur situé le plus loin possible des exemples qu’on a déjà vus. Le séparateur représenté par la figure 5b est appelé séparateur à marge maximale. La marge est la zone située entre les droites en pointillés sur la figure et vaut le double de la distance de la droite séparatrice au point exemple le plus proche. e- Apprentissage d’arbres de décision Un arbre de décision est une fonction qui a pour entrée un vecteur de valeurs d’attributs et renvoie en sortie une seule valeur, la « décision ». Les valeurs d’entrée et de sortie peuvent être discrètes ou continues.On s’intéressera aux problèmes où les entrées sont discrètes et les sorties prennent exactement deux valeurs possibles : vrai ou faux. Un arbre de décision atteint sa décision par la réalisation d’une série de tests. Chaque nœud interne est associé à un test sur la valeur de l’un des attributs d’entrée Ai, et la branches quittant ce nœud sont libellées avec les valeurs possibles de cet attribut, Ai=vik. Chaque feuille de l’arbre donne une valeur de retour de fonction. f- K-means clustering C’est un algorithme d’apprentissage non supervisé. Il groupe un ensemble d’objets dans le même groupe (appelé cluser) de telle façon que les objets sont plus similaires les uns aux autres qu’aux autres groupes (les autres clusters). 14 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Fig.6. : K-means clustering Exemple : Etant donné les points suivants, utiliser k-means clustering pour affecter chacune des données à chacun des deux clusters C1 et C2. x2 (5,8) (4,6) (1,2) (2,2) x1 Fig.7. : Position des points On suppose que les coordonnées initiales des 2 centroïdes sont celles des deux pointsreprésentés en bas de la figure 7 : (1,2) et (2,2) x2 (5,8) (4,6) (1,2) (2,2) C1 C2 x1 15 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Fig.8. : Position initiale des centroïdes Pour calculer les nouvelles coordonnées des centroïdes, on utilise une procédure itérative où chaque point est examiné à part pour voir s’il appartient à un cluster ou un autre. Ensuite on calcule les nouvelles coordonnées en cherchant la moyenne de tous les points comme suit : 𝑚 1 𝐶𝑛𝑒𝑤 = × ∑(𝑥 𝑖 ) 𝑚 𝑖=1 Itération 1 : On commence par calculer, pour chaque point, à quel centre il appartient. Le résultat dépend de la distance qui sépare le point du centre par une utilisation de la distance Euclidienne. Point 1 (1,2) : d11=oui, d12=non ; c’est-à-dire le point 1 est proche de C1 que C2 ; Point 2 (2,2) : d21=non, d12=oui ; c’est-à-dire le point 2 est proche de C2 que C1 ; Point 3 (4,6) : d31=non, d32=oui ; c’est-à-dire le point 3 est proche de C2 que C1 ; Point 4 (5,8) : d41=non, d42=oui ; c’est-à-dire le point 4 est proche de C2 que C1. On calcule maintenant les coordonnées des nouveaux centroïdes comme suit : C1= (1,2) ; C2= 1/3. ((2,2) + (4,6) + (5,8)) = (3.67, 5.33) Les nouvelles des positions des centroïdes (coloriés en rouge)seront comme suit (figure 9) : x2 (5,8) (4,6) C2 (1,2) (2,2) C1 x1 Fig.8. : Nouvelles positions des centroïdes (itération 1) 16 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI On appelle à une deuxième itération pour bien placer ces nouveaux centroïdes. Itération 2 : Point 1 (1,2) : d11=oui, d12=non ; c’est-à-dire le point 1 est proche de C1 que C2 ; Point 2 (2,2) : d21=non, d12=non ; c’est-à-dire le point 2 est proche de C1 que C2 ; Point 3 (4,6) : d31=non, d32=oui ; c’est-à-dire le point 3 est proche de C2 que C1 ; Point 4 (5,8) : d41=non, d42=oui ; c’est-à-dire le point 4 est proche de C2 que C1. Maintenant on calcule les nouvelles coordonnées de centroïdes comme suit : C1= ½. ((1,2) + (2,2)) = (1.5,2) ; C2= ½. ((4,6) + (5,8)) = (4.5, 7). Les nouvelles positions des centroïdes sont indiquées dans la figure 8. L’algorithme s’arrête quand les centroïdes ne changent pas ou changent légèrement, ou si un nombre maximal d’itérations est défini à l’avance. x2 C2 (5,8) (4,6) (1,2) (2,2) C1 x1 Fig.8. : Nouvelles positions des centroïdes (itération 1) 17 Chapitre I : Introduction aux algorithmes d’apprentissage automatique Enseignant : Mohamed HAYOUNI Bibliographie Stuart Russell, Peter Norvig, Fabrice Popineau. Intelligence Artificielle. Pearson Education, 2010, 978-0-13-604259-4. 18