Machine Learning Techniques de Clustering PDF

Machine Learning Fz BELHARAR Sommaire Introduction au Machine Learning et Réduction de Dimensions et 01 aux Catégories d’Algorithmes 06 Techniques Avancées de Clustering Algorithmes de Régression 07 Détection d’Anomalies & 02 Supervisée...

Machine Learning Fz BELHARAR Sommaire Introduction au Machine Learning et Réduction de Dimensions et 01 aux Catégories d’Algorithmes 06 Techniques Avancées de Clustering Algorithmes de Régression 07 Détection d’Anomalies & 02 Supervisée Apprentissage d’Association Algorithmes de Classification 08 Apprentissage Semi-Supervisé 03 Supervisée Algorithmes d’Ensemble pour la Introduction aux Réseaux de 04 09 Neurones et Deep Learning Classification Supervisée Techniques de Clustering Non Apprentissage par Renforcement 05 Supervisé 10  Techniques de Clustering Non Supervisé Le clustering est une technique d’apprentissage non supervisé qui consiste à regrouper des points de données en groupes (ou clusters) de telle sorte que : Les points dans un même cluster soient similaires entre eux. Les points appartenant à des clusters différents soient aussi dissemblables que possible.  Techniques de Clustering Non Supervisé Domaines d’application: Analyse des clients en marketing. Segmentation d’images. Identification de groupes dans des données biologiques (ex. : gènes, protéines). Détection d'anomalies. Objectifs du Clustering : Découvrir des structures cachées dans les données. Simplifier l’analyse en regroupant les données similaires. Utiliser les clusters pour prendre des décisions (exemple, recommander un produit à un groupe de clients).  Techniques de Clustering Non Supervisé 3. Types de Clustering Techniques Principales de Étapes Avantages Inconvénients Clustering Partitionnement: K- Choisir k centroides initiaux. Sensible au Means Clustering: Assigner chaque point au choix de k. Partitionne les cluster le plus proche (en Simple et rapide. Ne fonctionne données en k fonction de la distance). Bien adapté aux pas bien pour clusters en Mettre à jour les centroides en données compactes des clusters non minimisant la somme calculant la moyenne des et sphériques. sphériques ou des distances entre points dans chaque cluster. de tailles les points et leurs Répéter jusqu’à convergence. inégales. centroides.  Techniques de Clustering Non Supervisé 🔹 Algorithme K-Means : Principe de fonctionnement L'algorithme K-Means fonctionne en 5 étapes principales : 1. Initialisation : Choisir k centres de clusters initiaux (aléatoirement ou avec K-Means++). 2. Assignation : Chaque point est assigné au cluster le plus proche en fonction de la distance euclidienne. 3. Recalcul des Centroids : On calcule le nouveau centre de gravité pour chaque cluster. 4. Répétition : Répéter les étapes 2 et 3 jusqu’à convergence (plus de changements de clusters). 5. Terminaison : L'algorithme s'arrête lorsque les centroids ne bougent plus ou après un nombre d'itérations fixé. 🔹 Algorithme K-Means : Distance utilisée dans K-Means où x et y sont deux points dans un espace n-dimensionnel. Techniques de Clustering Non Supervisé 🔹 Algorithme K-Means : Principe de fonctionnement  Techniques de Clustering Non Supervisé 🔹 Algorithme K-Means : Principe de fonctionnement Exemple simple avec K = 2 On prend un ensemble de points : (2,3), (3,4), (5,6), (8,8), (9,9), (10,11) On choisit deux centres initiaux au hasard : Centroid 1 = (2,3), Centroid 2 = (9,9) On assigne les points au cluster le plus proche On recalcule les centroids jusqu'à convergence 🔹 Illustration Visuelle Points jaunes-> Cluster 1 🔵 Points bleus -> Cluster 2 Centroides -> Moyenne des points du cluster  Techniques de Clustering Non Supervisé 🔹 Algorithme K-Means : Principe de fonctionnement ✅ Avantages Comment choisir le bon k ? Il existe plusieurs méthodes pour choisir le nombre optimal de Simple et rapide à exécuter clusters. Exp: Méthode du Coude (Elbow Method) Fonctionne bien pour des On trace le graphique de la somme des distances intra- données bien séparées cluster en fonction de k. Facile à comprendre et On choisit le point où l'amélioration diminue fortement implémenter (coude). ❌ Inconvénients Sensible au choix de k (il faut souvent tester plusieurs valeurs) Sensible aux valeurs aberrantes (outliers) Fonctionne mal avec des clusters non sphériques  Techniques de Clustering Non Supervisé 3. Comparaison des Algorithmes d’Ensemble Techniques Principales de Étapes Avantages Inconvénients Clustering Ne nécessite pas de Agglomératif : Commence avec Coûteux en spécifier k au Hierarchical chaque point dans un cluster, termes de calcul départ. Clustering: Crée une puis fusionne les clusters les pour des grands Fournit une vision hiérarchie de plus proches. datasets. globale des clusters représentée Divisif : Commence avec tous Sensible au relations entre les sous forme de les points dans un seul cluster, bruit et aux données. dendrogramme. puis les divise progressivement. outliers.  Techniques de Clustering Non Supervisé 🔹 Hierarchical Clustering : Principe de fonctionnement Le clustering hiérarchique est une méthode de regroupement qui crée une hiérarchie de clusters et est généralement représenté sous forme de dendrogramme. Contrairement à K-Means, il ne nécessite pas de spécifier k au départ. A. L'approche agglomérative suit un processus ascendant (bottom-up). 1. Initialisation : Chaque point est un cluster distinct. 2. Calcul des distances entre les clusters. 3. Fusion des clusters les plus proches en un seul cluster. 4. Mise à jour de la matrice des distances. 5. Répétition jusqu'à ce qu'il ne reste plus qu'un seul cluster. 6. Construction du dendrogramme pour visualiser la hiérarchie.  Techniques de Clustering Non Supervisé 🔹 Hierarchical Clustering : Principe de fonctionnement 🔹 Mesures de distance entre clusters: Le choix de la distance entre clusters influence fortement le regroupement. Type de Distance Description Distance entre les deux points les plus proches de chaque cluster (favorise des Single Linkage clusters allongés (chaînage).) Distance entre les deux points les plus éloignés de chaque cluster ( produit des Complete Linkage clusters plus compacts) Average Linkage Moyenne des distances entre tous les points des deux clusters Centroid Linkage Distance entre les centres de gravité des clusters Ward’s Method Minimise la variance intra-cluster (donne souvent les meilleurs résultats)  Techniques de Clustering Non Supervisé 🔹 Hierarchical Clustering : Principe de fonctionnement La variance intra-cluster est une mesure qui quantifie à quel point les points d'un même cluster sont proches les uns des autres. En d'autres termes, elle mesure la dispersion des points à l'intérieur d'un cluster. Une faible variance intra-cluster signifie que les points du cluster sont très similaires et proches les uns des autres, tandis qu'une variance élevée indique que les points sont plus dispersés. La variance intra-cluster est généralement calculée comme la somme des carrés des écarts (SSE, Sum of Squared Errors) entre chaque point du cluster et le centroïde (le centre de gravité) du cluster.  Techniques de Clustering Non Supervisé 🔹 Hierarchical Clustering : Principe de fonctionnement  Techniques de Clustering Non Supervisé 🔹 Hierarchical Clustering : Principe de fonctionnement B. L'approche divisive suit un processus descendant (top- ✅ Avantages Ne nécessite pas de down). spécifier k à l'avance 1. Initialisation : On commence Produit une représentation avec un seul cluster hiérarchique des données contenant tous les points. Fonctionne bien sur des 2. Division récursive en sous- petits jeux de données clusters en maximisant la ❌ Inconvénients séparation. Complexité élevée, difficile 3. Répétition jusqu'à obtenir N pour de grandes bases de clusters (chaque point données Sensible aux valeurs devient un cluster). aberrantes NB: L'approche divisive est moins Difficile à interpréter utilisée que l'agglomérative, car lorsque beaucoup de points elle est plus coûteuse en calcul. sont présents  Techniques de Clustering Non Supervisé 3. Comparaison des Algorithmes d’Ensemble Techniques Principales de Étapes Avantages Inconvénients Clustering Basé sur la Sensible au choix densité(DBSCAN) Deux paramètres clés Capable de des paramètres :Identifie des ϵ (epsilon) : Rayon détecter des ϵ\epsilonϵ et clusters comme d’influence d’un point. clusters de formes minPts. des régions à minPts : Nombre arbitraires. Moins performant haute densité minimal de points Gère bien le bruit pour des données séparées par des requis pour former un et les outliers. à densités régions à faible cluster. variables. densité.  Techniques de Clustering Non Supervisé 🔹 DBSCAN Clustering : Principe de fonctionnement Étapes de l'algorithme Type de Description DBSCAN Point 1. Sélectionner un point non visité Possède au moins Point central MinPts voisins dans 2. Récupérer ses voisins dans un rayon ε un rayon ε 3. Si le point a au moins MinPts voisins → Création Situé dans le rayon ε Point de d’un point central, d’un nouveau cluster bordure mais avec moins de 4. Expansion du cluster : voisins Ajouter les voisins directs au cluster Étendre récursivement aux Point bruit N’appartient à aucun (outlier) cluster voisins des voisins 5. Ignorer les points de bruit (outliers)  Techniques de Clustering Non Supervisé 🔹 DBSCAN Clustering : Principe de fonctionnement 1. Étape 1 : Initialisation (tous les points en gris). 2. Étape 2 : Sélection d'un point (bleu) avec un cercle représentant le rayon ε. 3. Étape 3 : Création d'un cluster (vert) si le point a au moins MinPts = 5 voisins (orange). 4. Étape 4 : Expansion du cluster (vert) aux voisins des voisins. 5. Étape 5 : Identification des points de bruit (rouge). 6. Étape 6 : Résultat final avec tous les clusters (vert) et les points de bruit (rouge).  Techniques de Clustering Non Supervisé 3. Comparaison des Algorithmes d’Ensemble Techniques Principales de Étapes Avantages Inconvénients Clustering Modélisation Capable de Probabiliste (Mean Déplace les points de détecter Shift) : Identifie données vers des automatiquement Lent pour des des clusters régions de densité plus le nombre de grands datasets. comme des régions élevée jusqu’à clusters. Sensible au choix à haute densité convergence. Fonctionne bien de la fonction de séparées par des Ne nécessite pas de pour des clusters densité. régions à faible spécifier k. de formes densité. arbitraires.  Techniques de Clustering Non Supervisé Métriques de Similarité: Le clustering repose sur une mesure de similarité ou de distance Distance Euclidienne : Distance de Manhattan : Distance de Cosinus :  Techniques de Clustering Non Supervisé 4. Évaluation du Clustering Contrairement à l’apprentissage supervisé, il n’y a pas de véritables "étiquettes" pour évaluer le clustering. Les métriques suivantes sont souvent utilisées : Inertie (Within-Cluster Sum of Squares - WCSS) : Mesure la compacité des clusters. Utilisée dans la méthode du coude pour déterminer k optimal en K-Means. Silhouette Score : Évalue à quel point les points d’un cluster sont proches des points du même cluster et éloignés des autres clusters. Valeurs proches de 1 indiquent un bon clustering. Dunn Index : Mesure le ratio entre la séparation des clusters et leur compacité.  Techniques de Clustering Non Supervisé 5. Choix de la Méthode Critère K-Means Hierarchical DBSCAN Mean Shift Données sphériques oui Non Non oui oui Grand Dataset oui Non Non Formes arbitraires Non Partiellement oui oui Robuste aux Outliers Non Non oui Partiellement Pas besoin de k Non oui oui oui Sommaire Introduction au Machine Learning et Réduction de Dimensions et 01 aux Catégories d’Algorithmes 06 Techniques Avancées de Clustering Algorithmes de Régression 07 Détection d’Anomalies & 02 Supervisée Apprentissage d’Association Algorithmes de Classification 08 Apprentissage Semi-Supervisé 03 Supervisée Algorithmes d’Ensemble pour la Introduction aux Réseaux de 04 09 Neurones et Deep Learning Classification Supervisée Techniques de Clustering Non Apprentissage par Renforcement 05 Supervisé 10 Réduction de Dimensions, Techniques Avancées de Clustering 1. Introduction Dans le domaine du Machine Learning et de l’Intelligence Artificielle, l’analyse de données de grande dimension, l’identification de structures sous-jacentes et la détection de comportements inhabituels sont essentielles. Réduction de dimensions : Simplifier les données tout en conservant l'information pertinente. 2.Réduction de Dimensions 2.1. Pourquoi réduire la dimension des données ? Améliorer la performance des modèles en évitant la malédiction de la dimensionnalité. Faciliter la visualisation des données. Supprimer les redondances et corrélations inutiles. Réduire le temps de calcul et l’espace mémoire nécessaire.  Réduction de Dimensions, Techniques Avancées de Clustering 2.2. Techniques de réduction de dimensionnalité 2.2.1. Analyse en Composantes Principales (PCA - Principal Component Analysis) Transforme les variables initiales en composantes orthogonales maximisant la variance. Étapes principales : a. Centrage et normalisation des données. b. Calcul de la matrice de covariance. c. Extraction des valeurs propres et vecteurs propres. d. Projection des données sur les axes principaux. Application : Réduction du bruit en traitement d’image, analyse génomique. Réduction de Dimensions, Techniques Avancées de Clustering Réduction de Dimensions, Techniques Avancées de Clustering  Réduction de Dimensions, Techniques Avancées de Clustering 2.2. Techniques de réduction de dimensionnalité 2.2.2. Analyse en Composantes Indépendantes (ICA - Independent Component Analysis) Séparation des signaux indépendants. Utilisé dans l’analyse de signaux EEG en neuroscience. 2.2.3. T-SNE (t-Distributed Stochastic Neighbor Embedding) Réduction non linéaire permettant une visualisation en 2D ou 3D de grandes bases de données. Utile pour l’analyse exploratoire des clusters. 2.2.4. UMAP (Uniform Manifold Approximation and Projection) Plus rapide que T-SNE tout en conservant une meilleure structure globale. Très utilisé en bio-informatique et en vision par ordinateur. Sommaire Introduction au Machine Learning et Réduction de Dimensions et 01 aux Catégories d’Algorithmes 06 Techniques Avancées de Clustering Algorithmes de Régression 07 Détection d’Anomalies & 02 Supervisée Apprentissage d’Association Algorithmes de Classification 08 Apprentissage Semi-Supervisé 03 Supervisée Algorithmes d’Ensemble pour la Introduction aux Réseaux de 04 09 Neurones et Deep Learning Classification Supervisée Techniques de Clustering Non Apprentissage par Renforcement 05 Supervisé 10  Détection d’Anomalies & Apprentissage d’Association 3. Techniques Avancées de Clustering et Détection d’Anomalies 3.1. Clustering avancé 3.1.1. Problème des Clusters non sphériques Les algorithmes comme K-Means fonctionnent mal pour des clusters allongés, non convexes. Solutions : DBSCAN (Density-Based Spatial Clustering of Applications with Noise) : basé sur la densité. Clustering hiérarchique : permet d’exploiter des structures arborescentes. Spectral Clustering : basé sur la théorie des graphes. 3.1.2. Algorithmes principaux K-Means++ : amélioration de K-Means pour éviter les minima locaux. Mean-Shift : trouve les zones de forte densité. GMM (Gaussian Mixture Model) : modélise chaque cluster comme une distribution gaussienne. HDBSCAN : amélioration de DBSCAN pour mieux détecter les clusters avec des densités variables.  Détection d’Anomalies & Apprentissage d’Association 3.2. Détection d’Anomalies 3.2.1. Définition Une anomalie est une observation qui s'écarte significativement du comportement général des données. Domaines d’application : Détection de fraudes (cartes bancaires, cybersécurité). Diagnostic médical (identification de maladies rares). Maintenance prédictive (prévention des pannes). 3.2.2. Techniques de détection A. Méthodes basées sur la distance : C. Méthodes basées sur la densité : k-Nearest Neighbors (kNN) : Les points Local Outlier Factor (LOF) : Compare la éloignés de leurs voisins sont considérés densité locale d’un point avec celle de ses comme anomalies. voisins. B. Méthodes probabilistes : D. Autoencodeurs (Deep Learning) : Utilisés Isolation Forest : Isoler progressivement les pour détecter des anomalies complexes en anomalies par des arbres de décision. reconstruction de données.  Détection d’Anomalies & Apprentissage d’Association 4. Apprentissage d’Association 4.1. Introduction L'apprentissage d’association vise à découvrir des relations entre des éléments dans des bases de données. Exemple classique : Analyse du panier d’achat (si un client achète du lait, il est susceptible d’acheter du pain). 4.2. Méthodes principales 4.2.1. Algorithme Apriori Recherche des ensembles fréquents d’items. Utilisation des mesures de support, confiance et lift pour identifier les associations pertinentes. 4.2.2. Algorithme FP-Growth (Frequent Pattern Growth) Alternative à Apriori, plus rapide en exploitant une structure de données optimisée (FP-Tree). Détection d’Anomalies & Apprentissage d’Association 4. Apprentissage d’Association 4.2. Méthodes principales 4.2.3. Applications Systèmes de recommandation : Netflix, Amazon, Spotify. Marketing : Segmentation des clients en fonction des comportements d’achat. Détection de cooccurrences en bioinformatique.