Classification Avancée
Rémi Eyraud (grandement épaulé par Cécile Capponi)
Chapitre 3
Classification Non-Supervisée
Master 2 TSI-IMOVI
Rappel (pour les poissons rouges) : classification supervisée
● Un ensemble X = X1 x ... x Xd où chaque Xi est le domaine d'un
attribut Ai symbolique ou numérique.
● Un ensemble fini de classes Y.
● On suppose l'existence d'une variable aléatoire Z=(X,Y) à
valeurs dans X x Y.
● Les exemples/données sont des couples (x,y) de X x Y tirés
selon la distribution jointe :
P(Z=(x,y)) = P(X=x)P(Y=y|X=x).
● Un échantillon S est un ensemble fini d'exemples {(x1,y1), ... ,
(xn,yn)} i.i.d. selon P.
Classification Non-supervisée
● Les instances du problème sont identiques à la classification
supervisée, mais la classe des exemples n'est pas donnée : les
données font partie de X seulement !
● L'objectif est toujours de trouver un classifieur qui minimise le
risque
● Mais on ne peut même plus évaluer le risque sur l'échantillon
d'apprentissage !
● Il faut donc se servir d'autres informations pour segmenter les
données en classes (information sur le nombre de classes,
topologie de l'espace des attributs, ...)
● Principe : Regroupement (Clustering)
Le Clustering, c’est quoi ?
● Regroupement (Clustering): construire une collection
d’objets
○ Similaires au sein d’un même groupe
○ Dissimilaires quand ils appartiennent à des groupes
différents
● Le Clustering est de la classification non supervisée: pas de
classes prédéfinies
Le Clustering, exemples
Le clustering est le cas le plus souvent rencontré !
● Marketing : groupes distincts de clients (recommandation)
● Image : regroupement de zones similaires (segmentation)
● Analyse de réseau social
● Détection de fraude
● Etc. !
Qu’est-ce qu’un bon regroupement ?
● Une bonne méthode de regroupement permet de garantir
○ Une grande similarité intra-groupe
○ Une faible similarité inter-groupe
● La qualité d’un regroupement dépend donc de la mesure de
similarité utilisée par la méthode et de son implémentation
Mesurer la qualité d’un clustering
● Métrique pour la similarité: la similarité est exprimée par le
biais d’une mesure de distance
● Une autre fonction est utilisée pour la mesure de la qualité
● Les définitions de distance sont très différentes selon que les
domaines d'attributs sont des intervalles (continues), des
catégories, des booléens.
● En pratique, on utilise souvent une pondération des attributs
Plan de cette partie
1. Introduction
2. Algorithmes de Clustering
3. Retours sur la notion de distance - Similarité
Algorithmes de Clustering
Les différentes approches de regroupement
● Algorithmes de Partitionnement : Construire plusieurs partitions
puis les évaluer selon certains critères
● Algorithmes hiérarchiques : Créer une décomposition
hiérarchique des objets selon certains critères
● Algorithmes basés sur la densité : basés sur des notions de
connectivité et de densité
● Algorithmes de grille : basés sur un structure à multi-niveaux de
granularité
● Algorithmes à modèles : Un modèle est supposé pour chaque
cluster. Puis vérifier chaque modèle sur chaque groupe pour
choisir le meilleur
Algorithmes à partitionnement
● Construire une partition à k clusters d’une base D de n objets
● Les k clusters doivent optimiser le critère choisi
○ Global optimal: Considérer toutes les k-partitions
○ Heuristic methods: Algorithmes k-means et k-medoids
●
k-means (MacQueen’67):
Chaque cluster est représenté par son centre de gravité
●
k-medoids or PAM (Partition around medoids) (Kaufman &
Rousseeuw’87):
Chaque cluster est représenté par un de ses objets
L’Algorithme des k-moyennes (k-means)
L’algorithme k-means est en 4 étapes :
1. Choisir k objets Mi formant ainsi k clusters Ci
2. (Ré)affecter chaque donnée x au cluster Ci de centre Mi tel
que distance(x, Mi) est minimal
3. Recalculer Mi de chaque cluster (le barycentre)
4. Aller à l’étape 2 si on vient de faire une affectation
k-means : exemples
En 1D : [Link]
k-means : exemples
En 2 D:
[Standford, 2018]
Commentaires sur la méthode des k-means
● Force :
○ Relativement efficace: O(tkn), où n: nombre de données,
k: nb de clusters, et t: nb itérations. Normalement k, t << n.
○ Passage à l’échelle
○ Tend à réduire la variance inter-cluster (Théorème)
Distance de Manhattan Distance euclidienne
Commentaires sur la méthode des k-means
● Faiblesses :
○ Très dépendant de l’initialisation
○ On doit spécifier k (nombre de clusters)
○ Les clusters sont construits par rapports à des objets
inexistants (les milieux) (solution : k-médoïdes)
○ Ne peut pas découvrir les groupes non-convexes
Autres algorithmes de clustering
● Regroupement hiérarchiques : Ascendant ou descendant
● Autres :
○ Clustering spectral (non-convexe)
○ Algorithme EM (mélanges de gaussiennes, estimation de
densité)
○ Sampling (CLARA, CURE, ...)
Notion de distance - Similarité
Interval : pré-traitement
● Standardiser les données :
○ Calculer l’écart absolu moyen pour la colonne j :
où
○ Calculer la valeur standardisée pour chaque case de la
matrice de données :
Standardisation : exemple
MAge = 60 SAge = 5
MSalaire = 11074 SSalaire = 148
Similarité entre données
Les distances expriment une similarité
● Exemple : distance de Minkowski :
○ Si p = 1, d1 est la distance de Manhattan
○ Si p = 2, d2 est la distance euclidienne
Exemple : distance de Manhattan
d1(p1, p2) = 120
d1(p1, p3) = 132
Conclusion : p1 ressemble
plus à p2 qu’à p3 :-(
d1(p1, p2) = 120
d1(p1, p3) = 132
Conclusion : p1 ressemble
plus à p3 qu’à p2 :-)
Distance pour attributs binaires
● Table de contingence des attributs à valeurs dans {0, 1} :
Donnée j
1 0
1 a b
Donnée i
0 c d
● Exemple : x1 = (1, 1, 0, 1, 0) et x2 = (1, 0, 0, 0, 1)
alors : a = 1, b = 2, c =1, d = 1
Distance pour attributs binaires : distances
● Coefficient d’appariement simple :
Exemple pour x1 = (1, 1, 0, 1, 0) et x2 = (1, 0, 0, 0, 1),
Appariement(x1, x2) = 3/5
● Coefficient de Jaccard (attributs non-symétriques) :
Donnée j
Exemple: Jaccard(x1, x2) = 3/4 1 0
1 a b
Donnée i
0 c d
Distance pour attributs binaires : asymétriques
● Attribut symétrique : Ex. le sexe d’une personne : coder masculin
par 1 et féminin par 0 c’est pareil que le codage inverse
● Attribut asymétrique : Ex. Test HIV. Le test peut être positif ou
négatif (0 ou 1) mais il y a une valeur qui sera plus présente que
l’autre.
Généralement, on code par 1 la modalité la moins fréquente :
2 personnes ayant la valeur 1 pour le test sont plus similaires
que 2 personnes ayant 0 pour le test
Distance pour attributs binaires : asymétriques
Exemple :
Le Genre est un attribut symétrique, les autres non.
Prenons Y = P = 1 et N =0, les distances sur les attributs asymétriques :
Jack et Mary sont les plus similaires : sans doute le même mal
Distance pour les attributs nominaux
● Généralisation du cas binaires. Exemple : valeurs parmi rouge,
vert, bleu
● Méthode 1 : Matching simple. m = nombre d’appariements,
p = nombre d’attributs nominaux :
● Méthode 2 : transformation en attributs binaires. Exemple :
Une colonne “Rouge” qui prend les valeurs vrai ou faux, une
colonne “Vert”, et une colonne “Bleu”
Distance pour les attributs ordinaux
● Les valeurs peuvent être discrètes (ex: classement) ou
continues (ex: temps de course)
● Ce qui compte : l’ordre
● Méthode : traité comme des intervalles : pour l’attribut A
○ Remplacer x par son rang r ∈ {1, …, max(A)} {1, …, max(A)}
i,A i,A
○ Remplacer le rang par une valeur dans [0, 1] avec :
○ Utiliser une distance de Minkowski
Présence d’attributs de différents types
● Pour chaque type d'attributs, utiliser une mesure adéquate.
Problèmes: les regroupements obtenus peuvent être
différents !
● On utilise une formule pondérée pour les combiner.
