Introduction au Machine Learning PDF

Introduction au Machine Learning Florian Landry Rakiswende SAWADOGO Université Virtuelle – Burkina Faso (UV-BF) L3 Analyse de données Florian Landry Rakiswende SAWADOGO...

Introduction au Machine Learning Florian Landry Rakiswende SAWADOGO Université Virtuelle – Burkina Faso (UV-BF) L3 Analyse de données Florian Landry Rakiswende SAWADOGO UV-BF L3 Analyse de données Introduction ► Le Machine Learning (ML) est un sous domaine de l’intelligence artifielle (IA) qui vise à apprendre à la machine à extraire et analyser des enseignements issus de données et à s’améliorer avec l’expérience. L’utilisateur alimente un algorithme avec une quantité considérable de données et lui demande d’effectuer des recommandations à partir de ces données. Apprend la relation entre les données Prédire des événements pour d'autres données Améliorer les performances par rapport à l'expérience ► Quelques applications pratiques du ML: Détection de cancer et de tumeurs au cerveau Détecter les anomalies, les activités suspicieuses et prédire les cyber-attaques Détecter et filtrer les spams des emails Prédire les besoins en approvisionnement et/ou les ventes futures Netflix, YouTube, Amazon, et autres entreprises Google maps, détection des visages pour déverrouiller un appareil, Siri, Cortana, Alexa et toutes ces technologies utilisent le ML en technologie de fond. Jekaterina Dmitrijeva Deux principales familles de ML ► L’apprentissage supervisée: elle désigne l'action de surveiller et de diriger la réalisation d'un travail, d'un projet ou d'une opération. Elle utilise des données d’apprentissage étiquetées et une collection d'échantillons de test pour estimer une fonction. ► L’apprentissage non supervisée: elle désigne l’apprentissage automatique dans lequel les données d'apprentissage sont fournies au système sans étiquettes ou valeurs pré- assignées. Jekaterina Dmitrijeva Deux principales familles de ML Apprentissage Apprentissage Non Supervisée Supervisée Analyse en Composantes Principales Régression Logistique ACP Méthodes des Centres Mobiles Arbres de Décisions K-means Classification Ascendante Hiérarchique Séparateur à Vaste Marge CAH SVM Il existe d’autres méthodes d’apprentissage supervisée et non supervisée. Jekaterina Dmitrijeva Apprentissage Non supervisée Partitionnement Hiérarchique K-means CAH Jekaterina Dmitrijeva Apprentissage Non supervisée ► Classification (Clustering) : Les méthodes de classification (de partitionnement) servent à délimiter des groupes d’individus les plus homogènes possibles à partir de leurs caractéristiques. Elles visent à regrouper les individus par groupe de similarité de manière à distinguer des ensembles au sein desquels les individus se ressemblent plus qu’ils ne ressemblent aux individus des autres groupes. Deux individus se ressemblent le plus si les points qui les représentent dans le nuage de points sont les plus proches. Cela nécessite donc une métrique de la distance : distance Euclidienne, distance de Ward, etc. 1 Un critère d’évaluation d’une classification I t o t = I inter + I intra 3 2 Jekaterina Dmitrijeva Apprentissage Non supervisée CA H Classifi c ation : Regroupemen t d’individus da ns des classes les plus homog ènes Asc endante : On par t du niveau le p lus fi n ( ie des individus) Hiérarchique : Co nstruc tion d’un ar bre Jekaterina Dmitrijeva CAH ► Principe de l’algorithme : Considérer chacun des points du jeu de données est un centroïde. Regrouper chaque centroïde avec son centroïde voisin le plus proche. Ce dernier prend l’étiquette du centroïde qui l’a « absorbé ». De nouveaux centroïdes créés; lesquels seront les centres de gravité des clusters nouvellement formés. ► Deux questions clés se posent : Quelle métrique utilisée pour évaluer la distance entre les centroïdes ? : Nécessité de se munir d’une métrique de dissimilarité entre les centroides. A chaque étape de regroupement de deux centroïdes on obtiendra un nouveau cluster et un nouveau centroïde. La distance euclidienne classique est l’une des métriques qui permet d’évaluer cette distance entre les centroides. Quel est le nombre optimal de classes ou de clusters à choisir ? : Nécessité de se munir d’une métrique d’agrégation des nouveaux centroïdes créés qui minimise la perte d’inertie inter-classe: l’Indice de ward. Il n’y a pas d’internie intra-classe au départ; c’est la constitution de clusters conduit à une perte progressive de l’inertie inter-classe au profit de celle intra-classe (somme des distances euclidiennes entre chaque point associé au cluster et le centre gravité nouvellement calculé). Jekaterina Dmitrijeva CAH ► Dendrogramme: diagramme en arborescence illustrant des différents clusters de la CAH Durant les étapes d’un algorithme de classification hiérarchique, on est en train de construire un dendrogramme. Le dendrogramme indique les objets et classes qui ont été fusionnés à chaque itération. Le dendrogramme indique aussi la valeur du critère choisi pour chaque partition rencontrée. Il donne un résumé de la classification hiérarchique Chaque palier correspond à une fusion de classes Le niveau d’un palier donne une indication sur la qualité de la fusion correspondante Toute coupure horizontale correspond à une partition Jekaterina Dmitrijeva CAH ► Dendrogramme: On « coupe » l'arbre là où les branches sont longues 6 À un niveau de 5, il ne reste que 2 5 classes 4 Data Mining- 4GL-TWIN © 3 ESPRIT20 20-2021 Si on fixe un niveau de 3 (si on exige une 2 distance d’au moins 3 entre objets de classes différentes), il y a 4 classes 1 CAH ► Dendrogramme: la hauteur d’une branche est proportionnelle à la perte 6 d’inertie interclasse À un niveau de 5, il ne reste que 2 5 classes 4 Data Mining- 4GL-TWIN © 3 ESPRIT20 20-2021 Si on fixe un niveau de 3 (si on exige une 2 distance d’au moins 3 entre objets de classes différentes), il y a 4 classes 1 CAH ► Quelques limites de la C A H Complexité algorithmique non linéaire (en n2 ou n3, parfois n2log(n)) Deux observations placées dans des classes différentes ne sont jamais plus comparées Définir le nombre de partitions à l’avance n’est pas infaillible L’usage et l’interprétation de la CAH n’est pas toujours aisée en fonction du jeu de données. ' Apprentissage Non supervisée K- Means L’algorithme des k-moyennes (k-means en anglais) consiste à regrouper les individus dans k classes les plus homogènes possibles, d’individus décrits par des variables quantitatives. Les classes construites n’entretiennent pas de relations hiérarchiques: une classe n’est jamais incluse dans une autre classe. L’algorithme fonctionne en précisant le nombre de classes attendues. L’algorithme calcule les distances Intra-Classe et Inter-Classe. L’algorithme opère sur des variables continues Jekaterina Dmitrijeva K - Means ► Principe de l’algorithme : Étant donnés des points et un entier k, l’algorithme vise à diviser les points en k groupes, appelés clusters, homogènes et compacts. Définir 3 centroides aléatoirement et analyser leurs distances avec chaque point le plus proche : cela revient à étiqueter nos données. Recalculer 3 nouveaux centroïdes qui seront les centres de gravité de chaque nuage de points labellisés. On répète ces étapes jusqu’à ce que les nouveaux centroïdes ne bougent plus des précédents. ► Deux questions clés se posent : Quelle métrique utilisée pour évaluer la distance entre les points et les centroïdes ? : La distance euclidienne classique est l’une des métriques généralement utilisées. Elle permet d’évaluer la distance entre chaque point et les centroides. Quel est le nombre optimal de classes ou de clusters à choisir ? : La méthode du coude est la plus connue des méthodes de détermination du nombre optimal de clusters. Elle s’appuit sur l’inertie : la somme des distances euclidiennes entre chaque point et son centroïde associé. On fixe un nombre initial de clusters élevés et plus on réduit l’inertie plus les points ont de chance d’être à côté d’un centroïde. Jekaterina Dmitrijeva K - Means Méthode du coude On remarque que l’inertie stagne à partir de 3 clusters. Cette méthode est concluante. Jekaterina Dmitrijeva K-Means Simulation du K – Means 1 k1 Y Data Mining- 4GL-TWIN k2 3 © ESPRIT20 Choisir 20-2021 Centres de classes (au hasard) k3 X K-Means Simulation du K – Means 2 k1 Y Data Mining- 4GL-TWIN © k2 ESPRIT20 20-2021 Affecter chaque point à la classe dont le centre est le plus k3 proche X K-Means Simulation du K – Means 3 k1 k1 Y Data Mining- 4GL-TWIN © k2 ESPRIT20 20-2021 k3 Déplacer chaque k2 centre de classe vers la moyenne de chaque classe k3 X K-Means Simulation du K – Means 4 k1 Y Data Mining- 4GL-TWIN © ESPRIT20 20-2021 k3 Réaffecter les points k2 qui sont plus proches du centre d'une autre classe X K-Means Simulation du K – Means 5 k1 Y les trois points qui changent k3 de classe k2 X K-Means Simulation du K – Means 6 k1 Y Data Mining- 4GL-TWIN © ESPRIT20 20-2021 k3 k2 Re-calculer les moyennes des classes X K-Means Simulation du K – Means 7 k1 Y Data Mining- 4GL-TWIN © ESPRIT20 20-2021 k2 k3 Déplacer les centres des classes vers les moyennes X K-Means ► Quelques limites du K - Means Le choix du nombre de groupes est subjectif dans le cas où le nombre de classes est inconnu au sein de l’échantillon. L'algorithme du K-Means ne trouve pas nécessairement la configuration optimale correspondant à la fonction objective minimale. Les résultats de l'algorithme du K-Means sont sensibles à l'initialisation aléatoires des centres. On ne peut l’utiliser que lorsque l’on peut définir la valeur moyenne du cluster, ce qui peut ne pas convenir à certaines applications. ' Dans l’algorithme K-means, on donne K à l’avance, et le choix de cette valeur K est très difficile à estimer. Souvent, on ne sait pas à l’avance en combien de catégories on doit diviser un ensemble de données donné. Lorsque l’on veut appliquer l’algorithme K-means, il est d’abord nécessaire de déterminer une partition initiale basée sur le centre de regroupement initial, puis d’optimiser la partition initiale. La sélection de ce centre de clustering initial a un impact plus important sur les résultats du clustering. Si l’on ne sélectionne pas bien la valeur initiale, on risque de ne pas obtenir de résultats de clustering efficaces. Apprentissage Non supervisée Application Pratique Data Mining- 4GL-TWIN CAH ET KMEANS R © ESPRIT20 20-2021 SUR Apprentissage Non supervisée : Application K - Means Etudier la qualité des résultats de K - Means dans la construction de groupes de fleurs selon leurs caractéristiques. > iris Apprentissage Non supervisée : Application K - Means > iris_for_kmeans km plot(iris[,1], iris[,2], col=km$cluster) > points(km$centers[,c(1,)], col=1:3, pch=8, cex=2) > table(km$cluster, iris$Species) setosa versicolor virginica 1 0 48 14 2 50 0 0 3 0 2 36 setosa versicolor virginica Taux de 100% 96% 72% classificatio n % individus 0% 4% 28% « mal classés » 10,67 % Apprentissage Non supervisée : Application C A H Application de la CAH sur la base IRIS en utilisant la distance euclidienne et les 4 variables de longueur et largeur des pétales et des sépales. 1. Calcul de la matrice des distances sur les colonnes de 1 à 4 > d_euc = dist(iris[,1:4], method = 'euc’) 2. Application de la fonction hclust Data >Mining- hc = hclust(d_euc,method ='ave') 4GL-TWIN © >ESPRIT20 plot (hc) 20-2021 3. Extraire – à partir du dendrogramme – la classification en 3 groupes : > classe d_euc = dist(iris[,1:4], method = 'euc’) 2. Application de la fonction hclust Data >Mining- hc = hclust(d_euc,method ='ave') 4GL-TWIN © >ESPRIT20 plot (hc) 20-2021 3. Extraire – à partir du dendrogramme – la classification en 3 groupes : > classe table(classe , iris$Species) setosa versicolor virginica setosa versicolor virginica 1 0 50 14 1 0 48 14 2 50 0 0 2 50 0 0 3 0 0 36 3 0 2 36 setosa versicolor virginica setosa versicolor virginica Taux de 100% 100% 72% Taux de 100% 96% 72% classificati classificati on Data on %Mining- individus 4GL-TWIN 0% 0% 28% % individus 0% 4% 28% « mal « mal © classés » classés » 9,33 % 10,67 % ESPRIT20 CA Kmeans 20-2021 H Apprentissage Supervisée Classification Classification Régression logistique Arbres de décisions Classification Séparateur à Vaste Marge (SVM) Jekaterina Dmitrijeva Apprentissage Supervisée Régression logistique Modéliser la variable cible (ou d’intérêt) Y par une fonction des variables X (potentiellement) explicatives La variable cible Y qui est le plus souvent une variable binaire Expliquer et prédire la survenue d’un évènement Jekaterina Dmitrijeva Régression logistique ► Le Un nuage de points dont la variable décisionnelle est une variable qualitative binaire {0,1} ► Un tel nuage ne peut être représenté que par une fonction mathématique qui donne une courbe en S e  1 x  ( x )  P (Y  1 / X )  0 Régression logistique binaire simple 1  e  0 1 x  ( x )  P (Y  1 / X = x )  e0 1x1 ...k xk Régression logistique binaire multiple Jekaterina Dmitrijeva Régression logistique ► INTERPRÉTATION DE Y – PROBABILITÉ DE SUCCÈS  Prédire une variable décisionnelle ayant deux modalités Y = { 0 (absence), 1 (présence)}  L’une désigne un succès (Y = 1) et l’autre un échec (Y = 0)  Le principe de la régression dans ce cas est de chercher la probabilité d’obtenir le succès P(Y = 1) → Obtenir la probabilité de l’échec Y  Obtenir la probabilité du cas succès  P(Y = 0) = 1 - P(Y = 1) 1 Mohamed Heny Pour décider : SELMI ©  Se munir d’une règle de décision θ = 0,5  Pour un seuil θ (ou cut off) : 𝟏 𝐬𝐢 𝐏 𝐘 = 𝟏 𝐘 = *𝟎 𝐬𝐢 𝐏 𝐘 0 =𝟏 Xi > 𝛉  En approximation : θ = 0,5≤ 𝛉 Régression logistique ► Conclusion Modèle simple et précis Estime la probabilité de succès / d’échec à postériori Flexible et multi-usage (détection de fraudes, scoring…) Jekaterina Dmitrijeva Apprentissage Supervisée Arbres de décisions Expliquer et prédire une variable quantitative (arbre de régression) ou qualitative (arbre de classification) à partir de variables quantitatives et/ou qualitatives. Résultats sous forme de règles logiques de décision. Jekaterina Dmitrijeva Arbres de décisions ►Principe de l’algorithme en deux phases: Phase 1 -> Construction :sur base d'un ensemble d'apprentissage, processus récursif de division (souvent binaire) de l’espace des données en sous régions de plus en plus pures en termes de classes (estimé sur base d’un critère). Dans le cas de données numériques 2 approches possibles: séparations parallèles aux axes versus obliques Phase 2 -> Etalage : Supprimer les branches (parties terminales) peu représentatives pour garder de bonnes performances prédictives (généralisation) => nécessité d'un critère pour désigner les branches à élaguer. Jekaterina Dmitrijeva Arbres de décisions ► Processus récursif : Production d'une série de tests relatifs aux différentes variables (qualitatives ou quantitatives): Pour les variables quantitatives (discrète ou continue): tests (généralement) binaires: X ≤ ou > seuil (=> seuil à déterminer); Pour les variables qualitatives (ou déclarées comme telles): chacune des valeurs possibles est considérée comme une alternative (des sous-ensembles de valeurs peuvent aussi être considérés). Sélection du meilleur test (au niveau considéré) d'après un certain critère dont l'objectif est de diminuer le plus possible le mélange des classes au sein de chaque sous-ensemble créé par les différentes alternatives du test. Conditions d'arrêt: différentes possibilités (dépendent des algorithmes): Ex: pourcentage de cas appartenant à la classe majoritaire > seuil, ou nombre de cas dans une feuille < seuil, ou combinaison des 2,... Þ stratégie de "diviser-pour-régner". Jekaterina Dmitrijeva Arbres de décisions ► Quel critère de sélection? : Souvent basé sur la théorie de l’information et la notion d’entropie Soit un ensemble E d'exemples divisés en classes ω1,..., ωk,..., ωq. L'entropie de la distribution des classes = quantité moyenne d'information (ici en bits => log2) nécessaire pour identifier la classe d'un exemple de E: où P(ωk) est la probabilité a priori de la classe ωk L'entropie de la partition résultante, c'est-à-dire l'entropie conditionnelle de E étant donné T, est définie comme l'entropie moyenne des sous-ensembles: Le gain d'information apporté par le test T est donc: Il existe de nombreux critères basés sur différentes mesures caractérisant l'efficacité d'un test T, dont notamment les mesures statistiques d'association entre 2 variables qualitatives (ex: Gini index, mesure du Chi2). On a montré qu'il n'existait pas de différences significatives quant à la qualité des arbres utilisant différents critères basés sur ces notions (ils ont tous leurs points forts et leurs points faibles). Jekaterina Dmitrijeva Arbres de décisions ► Limites des Arbres de décision : Traitement des variables numériques génération des tests (choix des seuils) ne tient pas compte des propriétés de densité (proximité) des valeurs. => nouveaux développements avec de nouveaux critères de sélection pour les variables numériques. Algorithmes séquentiels sans remise en cause des étapes précédentes (d'où rapidité), un peu assoupli dans la production de systèmes de règles. Instabilité: sensibles aux variations (même assez faibles) de l'ensemble d'apprentissage en termes d'exemples, des variables considérées; => variations dans les arbres produits (variables sélectionnées, seuils des variables numériques, structure de l'arbre,...) et de leurs performances. Jekaterina Dmitrijeva Apprentissage Supervisée Séparateur à Vaste Marge (SVM) Trouver un hyperplan de l’espace des variables qui séparent « au mieux » les observations La variable cible Y à expliquée est binaire Jekaterina Dmitrijeva Séparateur à Vaste Marge (SVM) ► Qu’est-ce qu’un classifieur ? Y Algorithme de classement statistique. Son rôle est de séparer des échantillons Les échantillons séparés ont des propriétés similaires, mesurées sur des observations Xi Séparateur à Vaste Marge (SVM) ► Qu’est-ce qu’une marge? Y C’est la distance entre les échantillons séparés Distance = hyperplan : Plan de séparation - Espace vectoriel Données séparables linéairement : si tous les points associés aux données peuvent être séparés correctement par une frontière linéaire Hyperpl an valide Xi Séparateur à Vaste Marge (SVM) ► Choix d’un classifieur à vaste marge MAUVAIS Jekaterina Dmitrijeva 45 / 39 Séparateur à Vaste Marge (SVM) Hyperplans Séparateurs ► On cherche h sous forme d’une fonction linéaire : h(x) = w.x + b ► La surface de séparation est donc l’hyperplan w.x + b = 0 ► w.x + b = 0 est valide si x est sur la marge Jekaterina Dmitrijeva 46 / 39 Séparateur à Vaste Marge (SVM) Classe à prédire +1 Wx + b = +1 Objectif : maximiser la Wx + b =0 marge Wx + b =- 1 Classe à prédire -1  Séparateur à Vaste Marge (SVM) Vecteurs Supports Machines Vecteurs supports (Support vector machine) : Se sont les points les plus proches, qui seuls sont utilisés pour la détermination de l’hyperplan  Séparateur à Vaste Marge (SVM) Calcul de la Marge entre hyperplans séparateurs Séparateur à Vaste Marge (SVM) PROBLÉMATIQUE DES INDIVIDUS MAL PLACÉS Y Xi  Séparateur à Vaste Marge (SVM) Problème linéairement non séparable la séparation linéaire est impossible : Exemp Recours à d’autres type de classifieurs le Classifieur non linéaire Fonction Noyau