Lernzettel: Clustering et réduction dimensionnelle

📋 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 : principes et critères de fusion
5. Évaluation du clustering : inertie intra-classe et coefficient de silhouette
6. Comparaison pratique entre K-means et CAH selon les contextes
7. 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

• Inter-classe : Séparation Les clusters différents doivent être les plus éloignés possible les uns des autres.
• Clustering : À retenir ◆ Le clustering regroupe des données sans supervision : les classes ne sont pas connues à l'avance.

📝 Points essentiels

• L'apprentissage non supervisé consiste à découvrir seul la structure cachée dans les données sans étiquettes fournies.
• L'intra-classe correspond à la compacité des clusters, on cherche à minimiser la somme des distances au centroïde.
• L'inter-classe correspond à la séparation des clusters, on cherche à maximiser la distance entre clusters différents.
• Maximiser dist(Cᵢ, Cⱼ) pour i ≠ j Non supervisé Pas d'étiquettes données.
• L'algorithme doit découvrir seul la structure cachée dans les données.

💡 À retenir

Comprendre que le clustering est une méthode fondamentale d'apprentissage non supervisé visant à structurer des données sans étiquettes, avec des applications variées.

📖 2. Mesures de distance utilisées en clustering

🔑 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.
• Choix de la distance : Décision fondamentale qui influence la qualité du clustering et dépend des caractéristiques spécifiques des données à analyser.

📝 Points essentiels

• La distance Manhattan (L1) est la somme des valeurs absolues des différences de coordonnées.
• La distance Chebyshev (L∞) est la valeur maximale 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 à clusteriser.
• 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

La distance Manhattan (L1) est la somme des valeurs absolues des différences de coordonnées.

📖 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

• K-means alterne assignation des points au cluster le plus proche et recalcul des centroïdes jusqu'à stabilité.
• L'initialisation des centroïdes influence la convergence, avec K-means++ proposant une initialisation plus efficace.

💡 À retenir

Maîtriser le fonctionnement itératif de K-means et l'importance d'une bonne initialisation, comme K-means++, est essentiel pour optimiser le clustering.

📖 4. Classification Ascendante Hiérarchique (CAH) et dendrogramme : principes et critères de fusion

🔑 Notions clés & Définitions

• Critères de liaison (linkage) : Complexité : O(n² log n), adapté aux datasets de taille modérée CAH : Critères de liaison (Linkage) Rappel : à chaque étape CAH, on calcule toutes les distances inter-clusters et on fusionne la paire (i*, j*) = argmin dist(Cᵢ, Cⱼ), le critère de linkage définit ce que signifie 'dist'.

📝 Points essentiels

• La CAH est une méthode bottom-up qui fusionne itérativement les clusters les plus proches jusqu'à n'en avoir qu'un.
• La CAH calcule une matrice de distances inter-clusters à chaque étape pour déterminer la paire à fusionner.
• La complexité de la CAH est O(n² log n), adaptée aux datasets de taille modérée.
• 1 Init : Chaque point = 1 cluster → n clusters de taille 1 2 Matrice de distances : Calculer D[i,j] = dist(Cᵢ, Cⱼ) pour toutes les paires 3 Fusion : Fusionner les 2 clusters (i*,j*) = argmin D[i,j] 4 Mise à jour : Recalculer les distances selon le critère choisi (lien, Ward…) 5 Stop ?
• 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 Classification Ascendante Hiérarchique construit une hiérarchie de clusters par fusion successive des plus proches, visualisée par un dendrogramme qui facilite le choix du nombre de clusters.

📖 5. Évaluation du clustering : inertie intra-classe 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 : Approche consistant à utiliser des indicateurs quantitatifs pour déterminer si un clustering est satisfaisant et pour sélectionner le nombre optimal de clusters.
• 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 J est calculée par la somme des distances au carré entre chaque point et le centre de son cluster, et un J plus petit indique des clusters plus compacts.
• La méthode du coude consiste à repérer le point où la pente de l'inertie change brusquement, indiquant le nombre optimal de clusters où ajouter un cluster supplémentaire apporte peu de gain.
• Le coefficient de silhouette s(x) varie de -1 à +1, où une valeur proche de +1 indique un point bien affecté à son cluster, une valeur proche de 0 un point à la frontière entre deux clusters, et une valeur proche de -1 un point probablement mal affecté.
• La silhouette moyenne permet de comparer la qualité de différents clusterings en évaluant si les points sont plus proches de leur propre cluster que des autres clusters.

💡 À retenir

La qualité d'un clustering peut être quantifiée par l'inertie intra-classe et le coefficient de silhouette, ce qui permet de valider et de choisir le nombre optimal de clusters.

📖 6. Comparaison pratique entre K-means et CAH selon les contextes

🔑 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, alors que CAH permet de déterminer k a posteriori via le dendrogramme.
• Oui (requis) Non (a posteriori) Volume de données Grands datasets (n > 10⁴) Petits/moyens (n < 10⁴) Forme des clusters Sphériques / convexes Quelconque Résultat visuel Partition seule Dendrogramme + partition Outlier : point très éloigné du reste des données, pouvant perturber le clustering.

💡 À retenir

K-means et CAH ont des forces et limites respectives : K-means est efficace pour les grands datasets avec des clusters sphériques, tandis que CAH est plus flexible pour des formes variées et des datasets plus petits.

📖 7. Applications concrètes du clustering dans divers domaines

🔑 Notions clés & Définitions

• Exemple en détail : Une illustration précise d'une application de clustering, détaillant les étapes de collecte, normalisation, choix du nombre de clusters, exécution de l'algorithme et interprétation des résultats.
• Segmentation clients : Une méthode de regroupement des clients en fonction de leurs habitudes d'achat, comme la fréquence, le panier moyen et les catégories préférées, afin de personnaliser les offres commerciales.
• Expression génétique : La mesure des niveaux d'activité des gènes dans des échantillons biologiques, utilisée pour regrouper des gènes ou des patients selon leurs profils d'expression ARN et identifier des sous-types tumoraux.
• Regroupement de documents : Une technique de classification automatique d'articles ou documents en thèmes similaires sans recourir à des étiquettes manuelles, facilitant l'organisation et la recherche d'information.
• Détection d'anomalies : 🔐 Cybersécurité Détection d'anomalies Algo : K-means / DBSCAN Identifier les comportements réseau atypiques (intrusions, malwares) en isolant les points éloignés de tout cluster.

📝 Points essentiels

• En e-commerce, K-means segmente les clients selon leurs habitudes d'achat pour personnaliser les offres.
• En NLP, K-means classe automatiquement des documents par thème sans étiquettes manuelles.
• En cybersécurité, K-means ou DBSCAN détectent des comportements réseau atypiques en isolant les anomalies.
• En urbanisme, CAH regroupe des communes selon indicateurs socio-économiques pour orienter les politiques publiques.
• Heatmap expression génique Gènes → G 1 G 2 G 3 Résultat : 3 sous-types tumoraux identifiés → pronostics et traitements différenciés B O N U S Pour aller plus loin K-means : Problème d'initialisation Problème : K-means converge vers un minimum local, le résultat dépend des centroïdes initiaux.

💡 À retenir

En e-commerce, K-means segmente les clients selon leurs habitudes d'achat pour personnaliser les offres.

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

🔑 Notions clés & Définitions

• Premières composantes : Axes principaux issus de l'Analyse en Composantes Principales (ACP) qui correspondent aux directions de plus grande variance dans les données, permettant de représenter l'information la plus significative dans un espace de dimension réduite.

📝 Points essentiels

• L'ACP réduit la dimension en projetant les données sur les premières composantes principales conservant l'information.
• 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 et de la négligeabilité des suivantes.
• La visualisation 2D des clusters est facilitée après réduction dimensionnelle.

💡 À retenir

Réduire la dimensionnalité avant le clustering permet d'améliorer la pertinence des distances utilisées et facilite la visualisation des clusters en 2D.

📊 Tableaux de Synthèse

Comparaison K-means et CAH

Critère	K-means	CAH
Fixation du nombre de clusters	Oui	Non
Type de données	Grandes datasets, sphériques	Petits/moyens
Visualisation	Partition seule	Dendrogramme + partition
Gestion des outliers	Peu robuste	Plus robuste

Mesures de distance en clustering

Type de distance	Formule	Applications
Euclidienne	√(Σ (xᵢ - yᵢ)²)	Segmentation, bioinformatique
Manhattan	Σ |xᵢ - yᵢ|	Segmentation, compression d'images
Chebyshev	max |xᵢ - yᵢ|	Détection d'anomalies
Cosinus	(A·B) / (‖A‖ · ‖B‖)	NLP, recommandation

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre distance Euclidienne et Manhattan dans la sélection des mesures.
2. Sous-estimer l'impact de l'initialisation dans K-means.
3. Ignorer la sensibilité de CAH aux outliers.
4. Utiliser la même mesure de distance pour tous types de données sans adaptation.
5. Confondre la hiérarchie du dendrogramme avec la partition finale.
6. Ne pas vérifier la stabilité du clustering avec différentes initialisations.
7. Mauvaise interprétation du nombre de clusters optimal.

✅ Checklist Examen

1. Vérifier la cohérence des mesures de distance avec la nature des données.
2. Tester différentes initialisations pour K-means.
3. Analyser la dendrogramme pour choisir le nombre de clusters.
4. Utiliser la méthode du coude pour l'inertie.
5. Comparer K-means et CAH selon la taille du dataset.
6. Vérifier la sensibilité aux outliers.
7. Réduire la dimension avec ACP avant clustering si nécessaire.
8. Visualiser les clusters en 2D après réduction.