Techniques de clustering

Résumé du document

- Construire à partir des objets de l'ensemble d'apprentissage k clusters.
- Trouver une partition en k clusters en optimisant la fonction de similarité (critère de partitionnment).
- Approches :
. Global optimal : Considérer toutes les k partitions.
. k-means : Chaque cluster est représenté par son centre.
. k-medoïds : Chaque cluster est représenté par un de ses objets.

(...)

- K-moyenne est appelée aussi méthode des centres mobiles.
- Si on a plusieurs attributs.
-> Nécessité de normaliser les échelles des différents attributs.
- Choix du nombre de classes k dépend de l'utilisateur.
- Résultat dépendant des clusters initiaux choisis.
-> Faire plusieurs expérimentations avec différents clusters initiaux et choisir la meilleure configuration.
- Plusieurs variantes de K-moyenne :
. Sélection des k clusters initiaux.
. Mesure de la distance utilisée.
. Calcul de la moyenne des clusters.

(...)

Par agglomérations = Bottom-up
- Chaque objet constitue un cluster.
- Regrouper les objets (clusters) les plus proches (distance) en des clusters.

(...)

Extraits

[...] Assigner chaque objet au cluster dont le centre est plus proche (distance). Jusqu'à ce que la partition soit stable. Exemple: k-moyenne Les autres objets de T sont affectés au cluster C3 puisque D(O,M3) est minimale. [...]

[...] Créer une variable binaire pour chaque modalité variable rouge qui prend les valeurs vraie ou fausse) Nombre de ressemblances, Nombre total de variables Variables ordinales L'idée est: Remplacer xif par son rang rif  { Mf} Remplacer le rang de chaque variable par une valeur dans en remplaçant la variable n dans l'objet Oi par Utiliser une distance pour calculer la similarité. Une variable ordinale peut être discrète ou continue. L'ordre peut être important. Principales approches Méthodes par partitionnement Méthodes hiérarchiques Cluster Diviser un ensemble de N objets en k clusters Création d'une décomposition hiérarchique des objets selon certains critères Méthodes par partitionnement Construire à partir des objets de l'ensemble d'apprentissage k clusters. Trouver une partition en k clusters en optimisant la fonction de similarité (critère de partitionnment). [...]

[...] Minimiser la similarité au sein des groupes différents (inter-classe). Elouedi2005-03-27T11:04: 30.3468971008 segmentation des marchés: clients ayant un comportement identique Elouedi2005-03-27T11:09: 35.4165831808 Applications Reconnaissance des formes Bio-informatique Textmining Web mining . Marketing Segmentation des marchés Gènes semblables Textes proches Groupes d'accès similaires Divers domaines Elouedi2005-03-27T11:04: 30.3468971008 segmentation des marchés: clients ayant un comportement identique Elouedi2005-03-27T11:09: 35.4165831808 Elouedi2006-03-20T14:50: 15.562725312 Elouedi2006-03-20T14:51: 12.1263586112 But: grouper les individus en groupes, appelés classes ou clusters, aussi homogènes que possibles Ex: grouper les clients selon leur ressemblances comportement d'achat identique mieux adapter les actions sur chaque sous-groupe Proximité Mesure de similarité Mesure de dissimilarité Plus la mesure est grande, plus les éléments sont similaires Plus la mesure est faible, plus les éléments sont similaires Ces mesures sont souvent exprimées en fonction d'une distance qui change selon la nature des variables (continues, catégoriques, ) Matrice de données Structure de données Matrice de similarité Types de variables Binaires Catégoriques Numériques Ordinales (Couleur, Situation familiale, ) (Poids, Taille, ) (Résultat d'un concours, Qualité d'un produit, ) (Service militaire, Option, ) Variables numériques continues Distance Euclidienne Distance de Manhatten Distance de Minkowski = [(x1-y1)2 + (x2-y2)2+ +(xn-yn)2]1/2 = [(x1-y1)q + (x2-y2)q+ +(xn-yn)q]1/q q > 0 Généralisation de la distance Euclidienne = x1-y1 + x2-y2 + + xn-yn Cas particulier de la distance Minkowski = Distance Euclidienne Distance de Manhatten D(P1, P2) = + + (400)2)1/2 = 401.53 D(P1, P3) = + + (-100)2)1/2 = 100.5 D(P1, P4) = + + (450)2)1/2 = 450.03 D(P1, P2) = -35 + + 400 = 437 D(P1, P3) = -10 + + -100 = 111 D(P1, P4) = 5 + 1 + 450 = 456 On peut aussi normaliser Exemple P1 est plus proche de P3 que de P2 et P4 P1 est plus proche de P3 que de P2 et P4 Distance Euclidienne Distance de Manhatten D(P1, P2) = 0.875 + 0.667 + ( 0.728 = 1.319 D(P1, P3) = 0.25 + 0.333 + 0.182 = 0.454 D(P1, P4) = 0.125 + ( 0.333 + ( 0.818 = 0.891 D(P1, P2) = - 0.875 + - 0.667 + 0.728 = 2.27 D(P1, P3) = - 0.25 + - 0.333 + - 0.182 = 0.765 D(P1, P4) = 0.125 + 0.333 + 0.818 = 1.276 Normalisation P1 est plus proche de P3 que de P2 et P4 P1 est plus proche de P3 que de P2 et P4 Variables binaires Table de contingence Oi Oj a = nombre de positions où i est à 1 et j est à 1 Oi = ( Oj = ( d=1 Coefficient de Russel et Rao (Proportion d'occurrences positives): Coefficient de Jaccard (Poids des occurrences fausses est neutralisé): Coefficient de Dice (Poids double pour les occurrences vraies): = 2/5 = 1/2 = 2/3 Variables catégoriques Généralisation des variables binaires. [...]

[...] Approches: k-means: Chaque cluster est représenté par son centre. k-medoïds: Chaque cluster est représenté par un de ses objets. Global optimal: Considérer toutes les k partitions. Méthode k-moyenne (k-means) Choisir le nombre de clusters et une mesure de distance. K-moyenne (Forgy 1965, MacQueen 1967) Construire une partition aléatoire comportant k clusters non vides. Répéter Calculer le centre de chaque cluster de la partition. [...]