Lernzettel: Introduction au clustering non supervisé

📋 Plan du Cours

1. Principes et applications du clustering en apprentissage non supervisé
2. Mesures de distance utilisées en clustering
3. Algorithme K-means : fonctionnement et optimisation
4. Classification Ascendante Hiérarchique (CAH) et dendrogramme
5. Critères d’évaluation du clustering : inertie et coefficient de silhouette
6. Comparaison pratique entre K-means et CAH selon contexte, forme des clusters et volume de données
7. Exemples d’applications concrètes du clustering dans divers domaines
8. Réduction de dimension par ACP avant clustering et pipeline associé

📖 1. Principes et applications du clustering en apprentissage non supervisé

🔑 Notions clés & Définitions

• Apprentissage non supervisé : Type d'apprentissage où l'algorithme doit découvrir seul la structure cachée dans les données, sans disposer d'étiquettes.
• Intra-classe (compacité) : Critère visant à minimiser la distance entre les points appartenant à un même cluster pour assurer leur homogénéité.
• Inter-classe (séparation) : Clusters différents doivent être les plus éloignés possible les uns des autres.
• Clustering : La vraie vie !

📝 Points essentiels

• L'apprentissage non supervisé ne dispose pas d'étiquettes, l'algorithme doit découvrir seul la structure cachée dans les données.
• La compacité intra-classe vise à minimiser la distance entre points d'un même cluster.
• La séparation inter-classe vise à maximiser la distance entre clusters différents.
• 3 K-means Algorithme, initialisation, critère d'optimalité 4 Classification Ascendante Hiérarchique (CAH) Dendrogramme, critères de fusion 5 Évaluation et comparaison Silhouette, inertie, K-means vs CAH Le Clustering - Vue d'ensemble Définition : Le clustering est une tâche d'apprentissage non supervisé qui regroupe des données en sous- ensembles homogènes (clusters), sans étiquettes connues a priori.

💡 À retenir

L'apprentissage non supervisé ne dispose pas d'étiquettes, l'algorithme doit découvrir seul la structure cachée dans les données.

📖 2. Mesures de distance utilisées en clustering

🔑 Notions clés & Définitions

• Distance Euclidienne : Une mesure de distance entre deux points dans un espace vectoriel, calculée comme la racine carrée de la somme des carrés des différences de leurs coordonnées.
• Principe : Aucune étiquette fournie.
• Segmentation : Une application du clustering consistant à diviser un ensemble de données en groupes homogènes, par exemple pour la segmentation clients ou la compression d'images.

📝 Points essentiels

• La distance Euclidienne (L₂) est calculée comme √( Σᵢ (xᵢ - yᵢ)² ).
• La distance Manhattan (L₁) est la somme des valeurs absolues des différences de coordonnées.
• La distance Chebyshev (L∞) est le maximum des différences absolues sur une dimension.
• Le choix de la distance est critique et dépend des données.

💡 À retenir

La distance Euclidienne (L₂) est calculée comme √( Σᵢ (xᵢ - yᵢ)² ).

📖 3. Algorithme K-means : fonctionnement et optimisation

🔑 Notions clés & Définitions

• 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

• L'objectif de K-means est de minimiser la somme des distances au carré entre chaque point et le centroïde de son cluster, appelée inertie intra-cluster.
• L'algorithme alterne entre assigner chaque point au cluster dont le centroïde est le plus proche et recalculer les centroïdes comme barycentres des points assignés.
• L'initialisation des centroïdes est cruciale : la méthode K-means++ améliore la convergence en choisissant le premier centroïde aléatoirement puis les suivants avec une probabilité proportionnelle au carré de leur distance au centroïde le plus proche.
• K-means peut converger vers un minimum local ; il est donc recommandé de lancer plusieurs fois l'algorithme avec différentes initialisations et de retenir la solution avec la plus faible inertie.

💡 À retenir

Comprendre le fonctionnement itératif de K-means et l'importance d'une initialisation soignée permet d'assurer une convergence efficace vers un partitionnement compact des données.

📖 4. Classification Ascendante Hiérarchique (CAH) et dendrogramme

🔑 Notions clés & Définitions

• Dendrogramme : Représentation arborescente illustrant les fusions successives des clusters dans la classification ascendante hiérarchique, qui permet de déterminer le nombre de clusters en choisissant un seuil de coupure.
• Critères de liaison (Linkage) : Règles définissant la distance entre clusters lors de la fusion dans la classification ascendante hiérarchique, telles que le lien simple ou le critère de Ward, influençant la forme et la compacité des clusters obtenus.

📝 Points essentiels

• La CAH commence avec n clusters unitaires et fusionne itérativement les plus proches.
• Le dendrogramme permet de visualiser les fusions successives et de choisir le nombre de clusters par coupure.
• Les critères de liaison déterminent la façon dont la distance entre clusters est calculée, affectant la structure finale.
• La complexité de la CAH est de O(n² log n), adaptée aux jeux de données de taille modérée.
• Une coupure haute dans le dendrogramme donne peu de clusters, une coupure basse en donne beaucoup.
• 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 est une méthode hiérarchique flexible offrant une visualisation riche via le dendrogramme, adaptée aux petits et moyens jeux de données.

📖 5. Critères d’évaluation du clustering : inertie et coefficient de silhouette

🔑 Notions clés & Définitions

• Évaluation : Processus d'analyse de la qualité d'un clustering à l'aide de critères quantitatifs mesurant la compacité et la séparation des clusters.
• Idée : Principe consistant à identifier le nombre optimal de clusters en observant un changement significatif dans la pente de la courbe d'inertie ou en utilisant le score de silhouette.
• Méthode du coude : Procédure qui consiste à choisir le nombre de clusters k correspondant au point où la diminution de l'inertie intra-cluster devient marginale lors de l'ajout d'un cluster.

📝 Points essentiels

• L'inertie intra-cluster mesure la compacité des clusters, plus elle est faible, plus les clusters sont homogènes.
• La méthode du coude consiste à choisir k où la diminution d'inertie devient marginale en ajoutant un cluster.
• Le coefficient de silhouette s(x) é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, proche de -1 un point mal affecté.
• Le score de silhouette moyen est utilisé pour comparer la qualité globale de différents clusterings.
• Évaluation : Coefficient de silhouette s(x) = (b(x) − a(x)) / max(a(x), b(x)) avec s(x) [−1, 1]∈ a(x) = distance moyenne de x aux autres points de son cluster b(x) = distance moyenne de x au cluster voisin le plus proche Interprétation Valeur Signification s ≈ +1 Point bien affecté à son cluster s ≈ 0 Point à la frontière entre deux clusters s ≈ −1 Point probablement mal affecté Dans le TP : silhouette_score(X, labels) de sklearn : utilisé dans le bonus Iris pour comparer K-means et CAH.
• 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.

💡 À retenir

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

📖 6. Comparaison pratique entre K-means et CAH selon contexte, forme des clusters et volume de données

🔑 Notions clés & Définitions

• K-means : Rapide, scalable, mais nécessite k fixé.

📝 Points essentiels

• K-means nécessite de connaître k à l'avance, tandis que CAH permet de choisir k a posteriori via le dendrogramme.
• K-means est adapté aux grands jeux de données, CAH aux petits ou moyens en raison de leur complexité respective.
• Les outliers, points très éloignés du reste des données, peuvent perturber le clustering, notamment avec K-means.
• En pratique, il est conseillé de commencer par K-means pour sa rapidité, puis d'explorer avec CAH si la taille des données le permet.
• ◆ En pratique : commencer par K-means puis explorer avec la CAH si n est raisonnable.
• Critère K-means CAH k connu à l'avance ?

💡 À retenir

Le choix entre K-means et CAH dépend de la taille des données, de la forme attendue des clusters et de la connaissance préalable du nombre de clusters.

📖 7. Exemples d’applications concrètes du clustering dans divers domaines

🔑 Notions clés & Définitions

• Exemple en détail : Une illustration complète d'une application de clustering, détaillant les étapes de préparation des données, choix des paramètres, exécution de l'algorithme et interprétation des résultats dans un contexte concret.
• Segmentation clients : Une méthode de regroupement des clients basée sur leurs comportements d'achat, utilisée pour adapter les offres commerciales à différents profils identifiés.
• Expression génétique : Une mesure quantitative des niveaux d'activité des gènes, exploitée pour regrouper des gènes ou des patients selon leurs profils d'ARN afin de distinguer des sous-types de maladies.
• Regroupement de documents : Un processus automatique de classification d'articles ou textes en groupes thématiques, réalisé sans recours à des étiquettes préalables.

📝 Points essentiels

• En e-commerce, K-means segmente les clients selon habitudes d'achat pour personnaliser les offres.
• En bioinformatique, CAH regroupe gènes ou patients selon profils d'expression ARN pour identifier sous-types tumoraux.
• En cybersécurité, K-means ou DBSCAN détectent comportements réseau atypiques en isolant points éloignés.
• En urbanisme, CAH regroupe communes selon indicateurs socio-économiques pour orienter politiques publiques.

💡 À retenir

Le clustering, illustré par divers exemples, montre sa diversité et son utilité pratique dans de nombreux domaines.

📖 8. Réduction de dimension par ACP avant clustering et pipeline associé

🔑 Notions clés & Définitions

• Premières composantes : Vecteurs principaux issus de l'ACP qui correspondent aux directions de plus grande variance dans les données, permettant de conserver la majeure partie de l'information lors de la réduction de dimension.

📝 Points essentiels

• L'ACP réduit la dimensionnalité en projetant les données sur les premières composantes principales conservant l'information majeure.
• Le pipeline consiste à normaliser les données, appliquer l'ACP, puis effectuer 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, en cherchant un palier où l'ajout d'une composante apporte peu.
• La visualisation 2D des clusters est facilitée après réduction dimensionnelle.
• L'ACP réduit d avant d'appliquer K-means ou CAH.

💡 À retenir

La réduction dimensionnelle par ACP améliore la pertinence du clustering en grande dimension et facilite la visualisation des clusters en projetant les données sur un espace de dimension réduite tout en conservant l'information majeure.

📊 Tableaux de Synthèse

Comparaison K-means et CAH

Critère	K-means	CAH
Vitesse	Rapide	Moins rapide
Taille des données	Grandes	Petites à moyennes
Fixation du nombre de clusters	Oui	Non, via dendrogramme
Forme des clusters	Sphériques	Flexibles

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre la forme des clusters et la forme des données.
2. Sous-estimer l'impact des outliers sur K-means.
3. Utiliser la même distance pour tous types de données sans adaptation.
4. Choisir un nombre de clusters sans validation.
5. Ignorer la complexité quadratique de CAH pour grands jeux de données.
6. Ne pas vérifier la convergence de l'algorithme K-means.
7. Confondre inertie et silhouette comme critères d'évaluation.

✅ Checklist Examen

1. Comprendre la différence entre intra-classe et inter-classe.
2. Maîtriser le fonctionnement de K-means et CAH.
3. Savoir choisir la distance adaptée à ses données.
4. Savoir interpréter un dendrogramme.
5. Utiliser l'inertie pour déterminer le nombre optimal de clusters.
6. Comparer K-means et CAH selon le contexte.
7. Appliquer la réduction de dimension par ACP avant clustering.
8. Connaître les applications concrètes du clustering.