Lernzettel: Introduction au clustering en IA

📋 Plan du Cours

1. Apprentissage supervisé et non supervisé en intelligence artificielle
2. Définition, objectifs et applications du clustering en apprentissage non supervisé
3. Mesures de distance utilisées en clustering : Euclidienne, Manhattan, Chebyshev et cosinus
4. Algorithme K-means : principe, étapes, initialisation et critère d'optimalité
5. Classification Ascendante Hiérarchique (CAH) : fonctionnement, dendrogramme et critères de fusion
6. Évaluation des clusters : inertie intra-classe, méthode du coude et coefficient de silhouette
7. Comparaison pratique entre K-means et CAH selon taille de données, forme des clusters et visualisation
8. Pipeline combinant ACP et clustering pour réduire la dimensionnalité avant classification

📖 1. Apprentissage supervisé et non supervisé en intelligence artificielle

🔑 Notions clés & Définitions

• Supervisé Données d'entrainement : Ensemble d'exemples pour lesquels les étiquettes sont connues et fournies au modèle afin qu'il apprenne à reproduire ces étiquettes.
• Apprentissage supervisé : Approche d'apprentissage où un modèle est entraîné à partir de données d'entraînement étiquetées pour apprendre à prédire ces étiquettes sur de nouveaux exemples.

📝 Points essentiels

• Les tâches principales de l'apprentissage supervisé sont la classification et la régression.
• L'apprentissage non supervisé ne dispose pas d'étiquettes et doit découvrir seul la structure cachée des données.
• Les algorithmes typiques de l'apprentissage non supervisé incluent K-means, CAH et ACP.
• L'algorithme doit découvrir seul la structure cachée dans les données.
• Il apprend à reproduire ces étiquettes pour prédire celles d'exemples inconnus.

💡 À retenir

Comprendre la distinction fondamentale entre apprentissage supervisé et non supervisé pour choisir la bonne approche selon la disponibilité des étiquettes.

📖 2. Définition, objectifs et applications du clustering en apprentissage non supervisé

🔑 Notions clés & Définitions

• Clustering : Tâche d'apprentissage non supervisé qui consiste à regrouper des données en sous-ensembles homogènes sans étiquettes connues a priori.
• Intra-classe : Objectif de maximiser la compacité des clusters en minimisant la distance entre points d'un même cluster.
• Inter-classe : Objectif de maximiser la séparation entre différents clusters en augmentant la distance entre eux.
• Doivent être les plus : Les points d'un même cluster doivent être les plus proches possibles entre eux.

📝 Points essentiels

• Le clustering regroupe des données sans supervision : les classes ne sont pas connues à l'avance.
• Les applications du clustering incluent segmentation clients, détection d'anomalies, compression d'images, recommandation et bioinformatique.

💡 À retenir

Saisir le rôle du clustering comme méthode clé pour structurer des données non étiquetées en groupes significatifs et ses usages concrets.

📖 3. Mesures de distance utilisées en clustering : Euclidienne, Manhattan, Chebyshev et cosinus

🔑 Notions clés & Définitions

• Distance Euclidienne : Mesure de distance calculée comme la racine carrée de la somme des carrés des différences entre les coordonnées correspondantes de deux points.

📝 Points essentiels

• La distance Manhattan (L₁) est la somme des valeurs absolues des différences de coordonnées.
• La distance Chebyshev (L∞) correspond au maximum des différences absolues sur toutes les dimensions.
• Le choix de la mesure de distance est critique et dépend des caractéristiques des données.
• Applications Segmentation clients · Compression d'images · Détection d'anomalies · Recommandation · Bioinformatique Mesures de distance Euclidienne (L₂) d(A,B) = √( Σᵢ (xᵢ - yᵢ)² ) Manhattan (L₁) d(A,B) = Σᵢ |xᵢ - yᵢ| Chebyshev (L∞) d(A,B) = max |xᵢ - yᵢ| Cosinus sim = (A·B) / (‖A‖ · ‖B‖) ⚠ Le choix de la distance est critique et dépend des données.

💡 À retenir

Le choix de la métrique de distance adaptée est crucial pour garantir la qualité du clustering.

📖 4. Algorithme K-means : principe, étapes, initialisation et critère d'optimalité

🔑 Notions clés & Définitions

• Principe : Aucune étiquette fournie.
• Inertie intra-cluster : Notations : A, B = deux points dans ᵈℝ xᵢ, yᵢ = coordonnées de A et B selon la dimension i d = dimension de l'espace A·B
• K-means : Notations : A, B = deux points dans ᵈℝ xᵢ, yᵢ = coordonnées de A et B selon la dimension i d = dimension de l'espace A·B

📝 Points essentiels

• K-means vise à minimiser l'inertie intra-cluster, c'est-à-dire la somme des distances au carré entre points et centroïdes.
• L'algorithme alterne entre assignation des points au cluster le plus proche et recalcul des centroïdes jusqu'à convergence.
• L'initialisation peut être aléatoire ou améliorée avec K-means++ pour une meilleure convergence.
• K-means nécessite de fixer le nombre de clusters k à l'avance.
• Le critère d'optimalité est la minimisation de l'inertie intra-cluster.
• Remarque : Il existe une version K-means++ : “initialisation intelligente” - 1er centroïde aléatoire, suivants choisis avec prob.

💡 À retenir

Le fonctionnement itératif de K-means repose sur l'alternance entre assignation et mise à jour des centroïdes, tandis que l'initialisation, notamment via K-means++, influence fortement la qualité finale du clustering.

📖 5. Classification Ascendante Hiérarchique (CAH) : fonctionnement, dendrogramme et critères de fusion

🔑 Notions clés & Définitions

• Critères de liaison (linkage) : Une méthode dans la CAH qui définit la distance entre deux clusters en fonction des distances entre leurs points, influençant la forme des clusters obtenus.

📝 Points essentiels

• La CAH est une méthode bottom-up qui commence avec n clusters unitaires et fusionne itérativement les deux clusters les plus proches jusqu'à n'en avoir qu'un.
• Les critères de liaison, tels que le lien simple ou Ward, définissent la distance entre clusters et influencent la forme des clusters finaux.
• La complexité de la CAH est de O(n² log n), ce qui la rend adaptée aux jeux de données de taille modérée.
• CAH - Classification Ascendante Hiérarchique Approche bottom-up : on part de n singletons et on fusionne itérativement les 2 clusters les plus proches jusqu'à n'en avoir qu'un.

💡 À retenir

La CAH offre une méthode flexible et visuelle pour explorer la structure hiérarchique des données sans nécessiter de fixer le nombre de clusters à l'avance.

📖 6. Évaluation des clusters : inertie intra-classe, méthode du coude et coefficient de silhouette

🔑 Notions clés & Définitions

• Évaluation : Inertie & Méthode du coude Question : Comment savoir si mon clustering est bon ?
• Idée : Principe consistant à identifier le nombre optimal de clusters en observant le point où l'ajout d'un cluster supplémentaire apporte un gain marginal en termes de compacité.
• Exemple en détail : Application pratique illustrant la segmentation de clients e-commerce en utilisant K-means, la normalisation des données, la méthode du coude pour choisir k, et l'interprétation des segments pour définir des stratégies marketing.
• Inertie intra-classe : J = Σ Σₓ C ‖x − μ ‖²ₖ ₖ ₖ∈ (plus J est petit, plus les clusters sont compacts) Idée : Chercher le k où la pente change brusquement, ie.

📝 Points essentiels

• L'inertie intra-classe mesure la compacité des clusters, plus elle est faible, plus les clusters sont homogènes.
• La méthode du coude consiste à choisir k au point où la diminution d'inertie devient marginale.
• Le coefficient de silhouette évalue la qualité d'affectation d'un point à son cluster, variant entre -1 et +1.
• Une silhouette proche de +1 indique un point bien affecté, proche de 0 un point à la frontière, et proche de -1 un point mal affecté.
• Le score de silhouette moyen est utilisé pour comparer différentes partitions.

💡 À retenir

L'inertie intra-classe mesure la compacité des clusters, plus elle est faible, plus les clusters sont homogènes.

📖 7. Comparaison pratique entre K-means et CAH selon taille de données, forme des clusters et visualisation

🔑 Notions clés & Définitions

• K-means : Rapide, scalable, mais nécessite k fixé.
• Algo : Méthode de regroupement utilisant des centroïdes pour partitionner les données.

📝 Points essentiels

• K-means est adapté aux grands datasets (n > 10⁴), CAH aux petits ou moyens (n < 10⁴) en raison de sa complexité.
• K-means détecte des clusters sphériques/convexes, CAH peut détecter des clusters de forme quelconque.
• K-means produit une partition seule, CAH fournit un dendrogramme riche pour visualiser la hiérarchie.
• Les outliers peuvent perturber le clustering, notamment K-means.

💡 À retenir

Le choix entre K-means et CAH dépend de la taille des données, de la forme des clusters et du besoin de visualisation hiérarchique.

📖 8. Pipeline combinant ACP et clustering pour réduire la dimensionnalité avant classification

🔑 Notions clés & Définitions

• Init : Méthode d'initialisation des centroïdes dans l'algorithme K-means, pouvant être aléatoire ou basée sur une stratégie spécifique comme K-means++.
• Malédiction de la dimension : Phénomène en grande dimension où les distances entre points deviennent peu discriminantes, rendant les méthodes basées sur la distance moins efficaces.

📝 Points essentiels

• La malédiction de la dimension rend les distances peu discriminantes en grande dimension.
• L'ACP réduit la dimensionnalité en projetant les données sur les premières composantes principales.
• Le pipeline normalise les données, applique l'ACP puis réalise le clustering sur l'espace réduit.
• Le choix du nombre de composantes r se fait en fonction de la quantité d'information conservée.
• Cette approche améliore la qualité et la visualisation des clusters.
• 1 Données brutes n × d (d potentiellement grand) Ex : 1000 images de 128×128 pixels → 2 Normalisation Centrage-réduction → 3 ACP Projection sur les r premières composantes (r << d) → 4 Clustering K-means ou CAH sur l'espace réduit ʳℝ → 5 Visualisation Projection 2D pour inspecter les clusters Choisir r : nombre de composantes On projette sur les r premières composantes principales.

💡 À retenir

Intégrer la réduction de dimension par ACP avant clustering permet de surmonter les limites des données haute dimension.

📊 Tableaux de Synthèse

Comparaison K-means et CAH

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre distance Euclidienne et Manhattan dans le choix des mesures.
2. Erreur en fixant le nombre de clusters sans méthode d'évaluation.
3. Mauvaise initialisation de K-means menant à un mauvais minimum local.
4. Utilisation inappropriée de CAH pour de très grands jeux de données sans réduction préalable.
5. Interprétation erronée du dendrogramme en choisissant un seuil de fusion.
6. Confusion entre inertie intra-classe et silhouette pour l'évaluation.
7. Négliger la normalisation des données avant clustering.

✅ Checklist Examen

1. Comprendre la différence entre apprentissage supervisé et non supervisé.
2. Savoir définir le clustering et ses objectifs.
3. Connaître les mesures de distance et leur impact.
4. Maîtriser le principe et les étapes de K-means.
5. Comprendre le fonctionnement et l'intérêt de la CAH.
6. Savoir évaluer la qualité des clusters avec inertie et silhouette.
7. Comparer K-means et CAH selon contexte.
8. Utiliser ACP pour réduire la dimension avant clustering.
9. Identifier la malédiction de la dimension.
10. Savoir choisir le nombre de composantes en ACP.
11. Visualiser les clusters en espace réduit.
12. Connaître l'initialisation de K-means et K-means++.