Clustering Gilles Gasso INSA Rouen - Département ASI Laboratoire LITIS 27 septe

Clustering Gilles Gasso INSA Rouen - Département ASI Laboratoire LITIS 27 septembre 2016 Gilles Gasso Clustering 1 / 56 Plan 1 Introduction 2 Problématiques Proximité Qualité des clusters 3 Méthodes de clustering CHA Principe Métrique Une variante du CHA : CHAMELEON K-means Principe Algorithme Variantes 4 Clustering par modèle de mélange Gilles Gasso Clustering 2 / 56 Introduction Introduction Objectifs D = {xi ∈Rd}N i=1 : ensemble de points décrits par d attributs. But : structuration des données en classes homogènes On cherche à regrouper les points en clusters ou classes tels que les données d’un cluster soient les plus similaires possibles Clustering ≡apprentissage non supervisé. C’est une technique d’exploration des données servant à résumer les informations sur les données ou à déterminer des liens entre les points. Exemples de classes Gilles Gasso Clustering 3 / 56 Introduction Introduction Domaines d’application Domaine Forme des données Clusters Text mining Textes Textes proches Mails Dossiers automatiques Web mining Textes et images Pages web proches BioInformatique Gènes Gènes ressemblants Marketing Infos clients, Segmentation produits achetés de la clientèle Segmentation Images Zones homogènes d’images dans l’image Web log analysis Clickstream Profils utilisateurs Gilles Gasso Clustering 4 / 56 Problématiques Problématiques Nature des observations : Données binaires, textuelles, numériques, arbres, ... ? Notion de similarité (ou de dissimilarité) entre observations Définition d’un cluster Evaluation de la validité d’un cluster Nombre de clusters pouvant être identifiés dans les données Quels algorithmes de clustering ? Comparaison de différents résultats de clustering Gilles Gasso Clustering 5 / 56 Problématiques Proximité Proximité entre points Mesure de la distance D(x1, x2) entre 2 points x1 et x2 Distance de Minkoswski : D(x1, x2) = Pd j=1 |x1,j −x2,j|q 1 q Distance Euclidienne correspond à q = 2 : D(x1, x2) = qPd j=1 (x1,j −x2,j)2 = p (x1 −x2)t(x1 −x2) Distance de Manhattan (q = 1) : D(x1, x2) = Pd j=1 |x1,j −x2,j| Métrique liée à une matrice W définie positive : D2(x1, x2) = (x1 −x2)⊤W (x1 −x2) Distance de Mahalanobis : W = C −1 avec C=matrice de covariance des données Gilles Gasso Clustering 6 / 56 Problématiques Proximité Proximité entre clusters Mesure de la distance D(x1, x2) entre 2 points x1 et x2 à valeurs discrètes Utiliser une matrice de contingence A(x1, x2) = [aij] x1 = 0 1 2 1 2 1
⊤et x2 = 1 0 2 1 0 1
⊤ A(x1, x2) =   0 1 0 1 2 0 1 0 1   Distance de Hamming : nombre de places où les 2 vecteurs diffèrent : D(x1, x2) = d X i=1 d X j=1,j̸=i aij Exemple : D(x1, x2) = 3 Gilles Gasso Clustering 7 / 56 Problématiques Proximité Notion de proximité (2) Mesure de la distance D(C1, C2) entre 2 classes C1 et C2 plus proche voisin : Dmin(C1, C2) = min {D(xi, xj), xi ∈C1, xj ∈C2} diamètre maximum : Dmax(C1, C2) = max {D(xi, xj), xi ∈C1, xj ∈C2} distance moyenne : Dmoy(C1, C2) = P xi∈C1 P xj∈C2 D(xi, xj) n1n2 distance de Ward : DWard(C1, C2) = q n1n2 n1+n2 D(µ1, µ2) Gilles Gasso Clustering 8 / 56 Problématiques Proximité Illustration Distance min Diamètre maximum Distance moyenne Distance des centres de gravité Gilles Gasso Clustering 9 / 56 Problématiques Qualité des clusters Qualité d’un clustering (2) Caractéristiques d’un cluster Chaque cluster Ck est caractérisé par Son centre de gravité : µk = 1 Nk P i∈Ck xi avec Nk = card(Ck) Son inertie : Jk = P i∈Ck D2(xi, µk) L’inertie mesure la concentration des points autour de µk. Plus Jk est faible, plus petite est la dispersion des points autour de µk Sa matrice de variance-covariance : Σk = P i∈Ck(xi −µk)(xi −µk)⊤ Remarque : on a la propriété suivante Jk = trace(Σk). L’inertie d’un cluster représente la variance des points de ce cluster Inertie Intra-cluster Inertie intra-cluster : Jw = P k P i∈Ck D2(xi, µk) = P i∈Ck Jk Gilles Gasso Clustering 10 / 56 Problématiques Qualité des clusters Qualité d’un clustering (2) Inertie inter-cluster Soit µ le centre de gravité du nuage de points : µ = 1 N P i xi Les centres de gravité des clusters forment eux aussi un ensemble de points caractérisé par Inertie inter-cluster : Jb = P k NkD2(µk, µ) L’inertie inter-cluster mesure "l’éloignement" des centres des clusters entre eux. Plus cette inertie est grande, plus les clusters sont bien séparés Une matrice de covariance inter-cluster : Σb = P k(µk −µ)(µk −µ)⊤ Remarque : Jb = trace(Σb) Gilles Gasso Clustering 11 / 56 Problématiques Qualité des clusters Bonne partition (1) Illustration (Bisson 2001) : g g1 g g2 g3 g4 C1 C2 C3 C4 Inertie totale des points = Inertie Intra-cluster + Inertie Inter-cluster Comment obtenir une bonne partition ? Il faut minimiser l’inertie intra-cluster et maximiser l’inertie inter-cluster Gilles Gasso Clustering 12 / 56 Problématiques Qualité des clusters Bonne partition (2) Illustration (Bisson 2001) : g1 g2 Forte inertie inter-classes Faible inertie intra-classes g3 g4 Faible inertie inter-classes Forte inertie intra-classes Gilles Gasso Clustering 13 / 56 Méthodes de clustering CHA Approches de clustering Différentes approches sont possibles Clustering hiérachique Clustering hiérarchique ascendant (CHA) et variantes Clustering par partitionnement Algorithme des K-means Clustering par modélisation Notion de modèles de mélange Gilles Gasso Clustering 14 / 56 Méthodes de clustering CHA CHA - principe Principe Chaque point ou cluster est progressivement "absorbé" par le cluster le plus proche. Algorithme Initialisation : Chaque point forme un cluster, Calcul de la matrice de distance M entre chaque couple de clusters (ici les points) Répéter Sélection dans M des deux clusters les plus proches CI et CJ Fusion de CI et CJ pour former un cluster CG Mise à jour de M en calculant la distance entre CG et les autres clusters Jusqu’à la fusion des 2 derniers clusters Gilles Gasso Clustering 15 / 56 Méthodes de clustering CHA CHA : principe Exemple (Bisson 2001) Hiérarchie (indicée) C10 C1 C6 C5 C4 C3 C2 C9 C8 C7 C1 C2 C3 C4 C5 C6 C8 C10 C7 C9 i Schéma du milieu : dendrogramme = représentation des fusions successives Hauteur d’un cluster dans le dendrogramme = distance entre les 2 clusters avant fusion (sauf exception avec certaines mesures de similarité)... Gilles Gasso Clustering 16 / 56 Méthodes de clustering CHA CHA : métrique Problème Trouver l’ultramétrique (distance entre clusters) la plus proche de la métrique utilisée pour les points. Saut minimal (single linkage) basé sur la distance Dmin(C1, C2) tendance à produire des classes générales (par effet de chaînage) sensibilité aux individus bruités. Saut maximal (complete linkage) basé sur la distance Dmax(C1, C2) tendance à produire des classes spécifiques (on ne regroupe que des classes très proches) sensibilité aux individus bruités. Gilles Gasso Clustering 17 / 56 Méthodes de clustering CHA CHA : métrique Saut moyen basé sur la distance Dmoy(C1, C2) tendance à produire des classes de variance proche Barycentre basé sur la distance DWard(C1, C2) bonne résistance au bruit Gilles Gasso Clustering 18 / 56 Méthodes de clustering CHA CHA : métrique Illustration : exemple (Bisson 2001) Données (métrique : dist. Eucl.) 4 3 2 1 0 4 3 2 1 0 A C B E F D Saut minimal F E A B C D i 0,5 1,1 0,9 0,7 Saut maximal C D A B E F i 0,5 4,0 2,8 1,7 Pas les mêmes résultats selon la métrique utilisée ... Gilles Gasso Clustering 19 / 56 Méthodes de clustering CHA CHA : ASI4 Clustering 26 individus d’ASI4, 2003 Données = 5 valeurs 0/1 (inscription en IR, MGPI, DM1, DM2, TIM) Saut minimal BARO CAST CORD BONV PESQ BOIT TRAO WAAG CHAM LEDI BOND SPER GREM CAMP PERS WEYC CAPR FOUR GESL JEAN LEHO HAUT OHAN RABA RABI ZEHN Pas moyen de faire de sous-groupes, tout le monde est à une distance de 0 ou 1 des autres clusters. Gilles Gasso Clustering 20 / 56 Méthodes de clustering CHA CHA : clustering avec saut maximal données ASI4 BARO CAST CORD GREM RABI ZEHN CAMP PERS WEYC CAPR FOUR GESL JEAN LEHO BOIT TRAO WAAG BONV PESQ HAUT OHAN RABA BOND SPER CHAM LEDI En changeant de métrique, on observe plus de sous-regroupements Pour construire les clusters, on coupe l’arbre à la hauteur voulue Gilles Gasso Clustering 21 / 56 Méthodes de clustering CHA CHA : Autre exemple de saut maximal 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 Indice des points regroupés Distance Dendrogramme 1 4 17 26 6 20 24 3 25 13 21 7 2 8 22 5 14 18 10 16 11 23 9 19 12 15 27 35 40 29 28 36 31 32 39 30 33 34 37 38 fusion des clusters 7 et 8 1 2 3 4 5 6 7 8 9 10 Gilles Gasso Clustering 22 / 56 Méthodes de clustering CHA CHA : Autre exemple de saut maximal 10 clusters cluster 7 cluster 8 fusion des clusters 7 et 8 étape suivante : Gilles uploads/Marketing/clustering-cours-pdf.pdf

• Détails
• Publié le Dec 10, 2021
• Catégorie Marketing
• Langue French
• Taille du fichier 4.1103MB