Artificial Intelligence - Master 2 Notes - PDF

University of Science and Technology Mohamed-Boudiaf Faculty of Electrical Engineering Department of Electronics Course support entitled : Artificial Intelligence Master 2 Specialty : Networks and Telecommunications...

University of Science and Technology Mohamed-Boudiaf Faculty of Electrical Engineering Department of Electronics Course support entitled : Artificial Intelligence Master 2 Specialty : Networks and Telecommunications Presented by : Mr. Mohammed Hicham HACHEMI Senior Lecturer (HDR) 1  Chapter V Unsupervised Learning 2  V.1. Introduction Apprentissage consiste à enseigner à la machine des supervisé choses que nous connaissons déjà C.à.d. Construisons à l’avance un Dataset qui contient des questions 𝑿𝑿 et des réponses 𝒚𝒚 Que faire alors si vous disposez d’un Dataset sans valeur 𝒚𝒚 ? Que faire si vous voulez que la machine vous aide à compléter vos connaissances en apprenant certaines choses que vous ignorez ? 3 V.1. Introduction Comment apprendre sans exemple de ce qu’il faut apprendre ? Pouvez-vous les regrouper en 2 familles selon leur ressemblance ? 4  V.1. Introduction La réponse est OUI Nul besoin de savoir s’il s’agit de cellules animales, de bactéries ou de protéines pour apprendre à classer ces images. Votre cerveau a en fait reconnu des structures communes dans les données que vous lui avez montrées. 5  V.1. Introduction Dans l’apprentissage on dispose ainsi d’un Dataset non-supervisé (𝑥𝑥) sans valeur (𝑦𝑦) et la machine apprend à reconnaitre des structures dans les données (𝑥𝑥) qu’on lui montre. On peut ainsi regrouper des donnés dans Des clusters (c’est le Clustering), Détecter des anomalies, Ou encore réduire la dimension de données. 6  V.2. Algorithme de Clustering - K-Mean l’algorithme le plus populaire pour les problèmes de Clustering C.à.d. Regrouper des données selon leur structure commune L’algorithme fonctionne en 2 étapes répétées en boucle. Cette méthode est la plus souvent utilisée pour la classification de documents, la segmentation d’images 7 V.2. Algorithme de Clustering - K-Mean notre nuage de points = Dataset 8  V.2. Algorithme de Clustering - K-Mean Placer au hasard un nombre K de centres dans notre nuage de points. Dans l’exemple K=2. noyau de chaque groupe appelé le centroïde soit choisi au hasard, 9 V.2. Algorithme de Clustering - K-Mean L’étape 1 consiste à rallier chaque exemple au centre le plus proche. La méthode la plus répandue pour calculer la distance entre un point et un noyau est le carré de la distance Euclidienne. 10  V.2. Algorithme de Clustering - K-Mean L’étape 2 consiste à déplacer les centres au milieu de leur Cluster 11 V.2. Algorithme de Clustering - K-Mean Répétez les étapes 1 et 2 en boucle jusqu’à ce que les centres ne bougent plus. 12  V.3. Algorithme de Clustering - K-Mean V.3.1. Avantages et inconvénients Avantages Simple à comprendre et à mettre en œuvre. Si nous avons un grand nombre de variables, les K-means seraient plus rapides que le clustering hiérarchique (autre algorithme). Lors du recalcul des centroïdes, une instance peut modifier le cluster. Des clusters plus regroupé sont formés avec des K-moyennes par rapport au clustering hiérarchique. 13  V.3. Algorithme de Clustering - K-Mean V.3.1. Avantages et inconvénients Inconvénients Un peu difficile de prédire le nombre de clusters, c'est-à-dire la valeur de k. La sortie est fortement influencée par les entrées initiales telles que le nombre de clusters (valeur de k). L'ordre des données a un impact très fort sur le résultat final. Très sensible au redimensionnement. Si nous redimensionnons nos données au moyen d’une normalisation ou d’une standardisation, le résultat changera complètement. Il n'est pas bon de faire un travail de clustering si les clusters ont une forme géométrique compliquée. 14  V.3. Algorithme de Clustering - K-Mean V.3.2. Applications de l'algorithme de clustering K-Means Objectifs de l’analyse groupée : Obtenir une intuition significative à partir des données avec lesquelles nous travaillons. Regroupez puis prédiction : différents modèles seront construits pour différents sous-groupes. Atteindre ces objectifs, le clustering K-means fonctionne suffisamment bien. Il peut être utilisé dans les applications suivantes : Regroupement Compression Segmentation Segmentation de documents d'images d'image client …etc. 15  V.4. Algorithme de Clustering - Mean Shift Contrairement au il ne fait aucune il s'agit d'un algorithme clustering K-means hypothèse non paramétrique Mean Shift attribue les points de Algorithm données aux clusters de manière itérative Différence Ne spécifier PAS le nombre de clusters sera entre K-Means le nombre de déterminé par l'algorithme et Mean-Shift clusters à l'avance par rapport aux données 16  V.4. Algorithme de Clustering - Mean Shift V.4.1. Fonctionnement Step1: Attribue les centroïdes initiaux à partir des données elles-mêmes ou de manière aléatoire. Ils servent de points de départ pour les itérations de l’algorithme. Step2: l’étape d’itération, les points sont déplacés en fonction de la densité des points environnants. Step3: Les centroïdes sont à mis à jour à chaque fois et les points sont déplacés en direction des régions de densité maximale. Step4: Le processus s’arrête une fois que les centroïdes auront atteint une position à partir de laquelle il ne peut plus bouger. 17  V.4. Algorithme de Clustering - Mean Shift V.4.1. Fonctionnement la taille de la fenêtre L’un des est influe distance maximale de recherche sur laquelle les paramètres clés (appelé bande points sont déplacés passante où Radius) La sélection de la taille de la fenêtre (bande passante) est Sans importance, 18  V.4. Algorithme de Clustering - Mean Shift V.4.1. Fonctionnement Exemple ici est un peu flou Pour mieux Appelé comprendre l’isobarycentre(barycentre) = voici un autre centre de masse exemple 19  V.4. Algorithme de Clustering - Mean Shift V.4.1. Fonctionnement Le processus s’arrête une fois que les centroïdes auront atteint une position à partir de laquelle il ne peut plus bouger. Chaque point est un lui-même un cluster 20  V.4. Algorithme de Clustering - Mean Shift V.4.2. Avantages et inconvénients Avantages Il n'est pas nécessaire de faire d'hypothèse de modèle comme dans le cas des K-means ou du Gaussian mixture. Modéliser des clusters complexes de forme non convexe. Il n'a besoin que d'un seul paramètre nommé bande passante qui détermine automatiquement le nombre de clusters. 21  V.4. Algorithme de Clustering - Mean Shift V.4.2. Avantages et inconvénients Inconvénients Ne fonctionne pas bien en cas de dimension élevée, où le nombre de clusters change brusquement. Aucun contrôle direct sur le nombre de clusters mais dans certaines applications, nous avons besoin d'un nombre spécifique de clusters. 22  V.5. Algorithme de Clustering - Clustering Hiérarchique utilisé pour regrouper les points de données non étiquetés ayant se répartit en deux catégories: des caractéristiques similaires Algorithmes hiérarchiques agglomérés (bottom-up approach) Chaque point de données est traité comme un seul cluster. Puis fusionner ou agglomérer les paires clusters La hiérarchie des clusters est représentée sous forme de dendrogramme ou tree structure. Algorithmes hiérarchiques qui divisent (Top-down approach) Tous les points de données sont traités comme un grand cluster. Le processus de regroupement implique de diviser le grand cluster en plusieurs petits clusters 23 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Distance Metrics La première étape du clustering agglomératif est le calcul des distances entre les points de données ou clusters Les mesures de distance couramment utilisées : Euclidean Distance Manhattan Distance 24  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Linkage L'étape de création de liens dans le clustering agglomératif est celle où la distance entre les clusters est calculée. Il existe plusieurs méthodes de création de liens. Certains d'entre eux sont: Single Linkage Complete Linkage Average Linkage 25  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Single Linkage La distance entre deux clusters = la distance minimale entre les points de données des clusters. 26  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Complete Linkage La distance entre deux clusters = la distance maximale entre les points de données des clusters. 27  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Average Linkage La distance entre deux clusters = la distance moyenne entre chaque point de données d'un cluster et chaque point de données de l'autre cluster. 28  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Exemple Clustering hiérarchique à lien unique 29  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés dendrogramme outil incontournable pour la classification hiérarchique two clusters are formed : Cluster 1 : (7,10) Cluster 2 : (20,28,35) 30  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Exemple de Clustering hiérarchique à lien Complet Supposons qu’on a : 31 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés 32 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Notation 33  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Identifiez la paire avec la distance la plus courte 34  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés la paire avec la distance la plus courte c’est (1,5) 35  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Créez une nouvelle matrice avec la paire combinée (de l'étape 1). À ce stade, nous savons que la diagonale sera entièrement composée de zéros (car la distance entre n'importe quel point et lui-même est nulle) : (1,5) 2 3 4 (1,5) 0 2 0 3 0 4 0 36  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Remplissez la première entrée en trouvant la distance maximale 2ème ligne et la paire {1,5} dmax(2, {1,5}) = dmax ({2,1}, {2,5}) = max(4,3)=4 (1,5) 2 3 4 (1,5) 0 2 0 3 0 4 0 37 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 3 4 (1,5) 0 2 4 0 3 0 4 0 38  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Remplissez la première entrée en trouvant la distance maximale 3ème ligne et la paire {1,5} dmax(3, {1,5}) = dmax ({3,1}, {3,5}) = max(7,6)=7 (1,5) 2 3 4 (1,5) 0 2 4 0 3 0 4 0 39 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 3 4 (1,5) 0 2 4 0 3 7 0 4 0 40  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés dmax(4, {1,5}) = dmax ({4,1}, {4,5}) = max(9,8)=9 (1,5) 2 3 4 (1,5) 0 2 4 0 3 7 0 4 0 41 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 3 4 (1,5) 0 2 4 0 3 7 0 4 9 0 42 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Automatiquement (1,5) 2 3 4 (1,5) 0 4 7 9 2 4 0 3 7 0 4 9 0 43  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Complétez !!! (1,5) 2 3 4 (1,5) 0 4 7 9 2 4 0 ? ? 3 7 ? 0 ? 4 9 ? ? ? 44 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 3 4 (1,5) 0 4 7 9 2 4 0 3 5 3 7 3 0 2 4 9 5 2 0 45  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Identifiez la paire avec la distance la plus courte ??? (1,5) 2 3 4 (1,5) 0 4 7 9 2 4 0 3 5 3 7 3 0 2 4 9 5 2 0 46 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 3 4 (1,5) 0 4 7 9 2 4 0 3 5 3 7 3 0 2 4 9 5 2 0 la paire avec la distance la plus courte c’est (3,4) 47  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 (3,4) Nouveau (1,5) 0 4 tableau Complétez !!! 2 4 0 (3,4) 0 (1,5) 2 3 4 (1,5) 0 4 7 9 Ancien 2 4 0 3 5 tableau 3 7 3 0 2 4 9 5 2 0 48  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés (1,5) 2 (3,4) Nouveau (1,5) 0 4 ? tableau Complétez !!! 2 4 0 ? (3,4) 9 5 0 (1,5) 2 3 4 (1,5) 0 4 7 9 Ancien 2 4 0 3 5 tableau 3 7 3 0 2 4 9 5 2 0 49  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Identifiez la paire avec la distance la plus courte ??? (1,5) 2 (3,4) (1,5) 0 4 9 2 4 0 5 (3,4) 9 5 0 50  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés la paire avec la distance la plus courte c’est ({1,5},2) (1,5) 2 (3,4) (1,5) 0 4 9 2 4 0 5 (3,4) 9 5 0 Complétez le nouveau tableau ??? 51 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés ((1,5),2) (3,4) Nouveau tableau ((1,5),2) 0 9 (3,4) ? 0 (1,5) 2 (3,4) Ancien (1,5) 0 4 9 tableau 2 4 0 5 (3,4) 9 5 0 52 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés ((1,5),2) (3,4) Nouveau tableau ((1,5),2) 0 9 (3,4) 9 0 (1,5) 2 (3,4) Ancien (1,5) 0 4 9 tableau 2 4 0 5 (3,4) 9 5 0 53 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés Que représentent ces valeurs? 54  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés une fois le gros cluster formé La ligne horizontale croise deux points Indique le nombre de clusters = deux 55 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés 56 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés la méthode de liaison complète Schématisez cet exemple Sous forme : 1- Matrice de distance 2- Dendrogramme 57  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés cluster individuel au départ Calcul des distances entre tous les clusters 58 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés cluster individuel au départ 59 V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés cluster individuel au départ 60  V.5. Algorithme de Clustering - Clustering Hiérarchique V.5.1. Algorithmes hiérarchiques agglomérés two clusters are formed : Cluster 1 : (7,10,20) Cluster 2 : (28,35) 61