Que veut-on faire ?

• Répartir les individus (ou objets) dans des groupes distincts
• Obtenir des groupes homogènes
  • deux individus proches dans une même classe
  • deux individus éloignés dans des classes différentes
• Déterminer le nombre de classes adapté
  • trop faible : peu informatif
  • trop élevé : trop spécifique et peu exploitable

Exemple : données faithful

Objectif sur l’exemple

Problème et histoire

• Comment trouver ces groupes de manière automatique ?
• Première classification connue : Aristote
  • Classification des animaux (Parties des Animaux)
  • utilisée jusqu’au milieu du XVIIème siècle
• Lamarck, Buffon ou bien von Linn : nouvelles classifications
  • Travaux de Lamarck à l’origine des travaux de Darwin et de la théorie de l’évolution
• Au milieu du XXème siècle, premiers pas de la classification phylogénétique par Hennig, utilisée encore de nos jours
• Toutes basées sur une approche hiérarchique et manuelle

Notions

• \(X = \{x_1,\ldots,x_n\}\) ensemble des objets à classer
• Partie de \(X\) : sous-ensemble \(A = \{a_1,\ldots,a_p\}\)
  • chaque \(a_j \in X, \forall j=1,\ldots,p\)
  • Si on compte l’ensemble vide et l’ensemble tout entier, il existe \(2^n\) parties de \(X\)
• Ensemble des parties muni de la relation d’ordre partiel
  • \(A \subseteq B \Leftrightarrow(x \in A \Rightarrow x \in B)\)
  • Deux parties d’un ensemble sont
    • soit chevauchantes (non égales et d’intersection non nulle),
    • soit disjointes (sans élément commun),
    • soit incluses l’une dans l’autre,
    • soit identiques.

Partition

• Partition \(Z = \{z_1,\ldots,z_K\}\) : sous-ensemble de parties \(z_k\)
  • 2 à 2 disjointes : \(k \neq k' \Rightarrow z_k \cap z_{k'} = \emptyset\)
  • Union = ensemble : \(\cup_{k = 1}^K z_k = X\)
• Complexité de la classification automatique due en grande partie au nombre de partitions possible de \(n\) éléments
  • Nombre de Bell : \[ B_n = \frac{1}{e} \sum_{k=1}^\infty \frac{k^n}{k!} \]
  • Pour \(n=4\) objets, 15 partitions différences
  • Pour \(n=30\) objets, nombre de partitions possibles = \(8.47 \times 10^{23}\)

Nécessité de définir des critères de bonne classification et d’avoir des algorithmes performants, et optimisant la recherche d’une partition

Hiérachie

• Classification hiérarchique : ensemble de classes, appelé hiérarchie
  • Arbre binaire : dendrogramme
• Hiérarchie de classes : ensemble de parties de \(X\) ayant les propriétés suivantes :
  • Partie vide \(\emptyset\) incluse
  • Parties réduites à un seul élément (\({x_i} \forall i=1,\ldots,n\)) incluses
  • Ensemble \(X\) inclus
  • Pour chaque couple de classes \((z, z')\)
    • soit \(z \subseteq z'\),
    • soit \(z' \subseteq z\),
    • soit \(z \cap z' = \emptyset\)
• Hiérarchie valuée : pour toute classe \(z_k\), association d’une valeur \(f(x_k)\) vérifiant
  • si \(x_k \subseteq x_{k'}\), alors \(f(x_k) \leq f(x_{k'})\).

Exemple simple

Considérons \(X=\{a,b,c,d,e\}\).

• Ensemble des parties de \(X\) : \[\emptyset\] \[\{a\}, \{b\}, \{c\}, \{d\}, \{e\}\] \[\{ab\}, \{ac\}, \{ad\}, \{ae\}, \{bc\}, \{bd\}, \{be\}, \{cd\}, \{ce\}, \{de\}\] \[\{abc\}, \{abd\}, \{abe\}, \{acd\}, \{ace\}, \{ade\}, \{bcd\}, \{bce\}, \{bde\}, \{cde\}\] \[\{abcd\}, \{abce\}, \{acde\}, \{bcde\}\] \[X=\{abcde\}\]
• Exemple de partition \[\{abc\}, \{de\}\]
• Exemple de hiérarchie de classes \[\{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{ab\}, \{cd\}, \{cde\}, \{abcde\}\]

Inertie intraclasse et interclasse

• Inertie totale \(I\) d’une population : moyenne des carrés des distances des individus au barycentre \[ I = \frac{1}{n} \sum_{i=1}^n {(x_i - g)}^2 \]
• Avec une partition en \(K\) classes
  • Inertie intraclasse \(W\) : somme des inerties \(W_k\) de chaque classe \[ W = \frac{1}{n} \sum_{k=1}^K W_k \mbox{ avec } W_k = \sum_{i \in z_k} {(x_i - g_k)}^2 \]
    • Classe homogène : inertie faible
  • Inertie interclasse \(B\) : inerties des centres des classes pondérés par le nombre d’individus par class \[ B = \frac{1}{n} \sum_{k=1}^K n_k {(g_k - g)}^2 \]
    • Plus \(B\) grand, plus les classes seront séparées

Illustration de l’inertie

Illustration – \(I\)

Illustration – \(W\)

Illustration – \(B\)

Objectif

• Bonne classification : inertie intraclasse \(W\) petite et inertie interclasse \(B\) grande
• Formule de Huygens : ces deux valeurs sont liées \[ I = B + W \]
• Optimisation des deux critéres équivalente
• Partition en \(K+1\) classes : inertie interclasse \(B\) plus élevée (et donc une inertie intraclasse \(W\) plus faible) qu’une partition en \(K\) classes

Avec comme seul critère l’inertie :

• Meilleure partition : partition en \(n\) classes (chaque individu dans sa propre classe)
• Pire partition : partition en 1 classe (tous les individus dans la même classe).

Qualité d’une partition

• Nombre optimum de classes : sujet complexe et difficile
• Classes naturelles souvent loin d’être évidente
• Utilisation d’analyses factorielles pas toujours d’une grande aide
• Utilisation de critères de choix (principalement graphique)
  • Aide au choix
  • Différents nombres de classes intéressants parfois
  • Discussion avec le métier importante pour cette étape
• Vu ici : \(R^2\), \(CCC\) et \(PseudoF\)

Critères

\(R^2\)

• Proportion de l’inertie explique par les classes \[ R^2 = B / I \]
• Plus il est proche de 1, meilleure est la classification
• Un bon critère est de prendre \(k+1\) classes lorsque le passage entre \(K\) et \(K+1\) reprèsente le dernier saut important.

\(PseudoF\)

• Séparation entre toutes les classes \[ PseudoF = \frac{ \frac{R^2}{K - 1} }{ \frac{1 - R^2}{n - K} } \]
• Nombre de classes \(K\) pour \(Pseudo F\) maximal

Iris

Classification hiérarchique

• Recherche d’une hiérarchie valuée
• Partition compatible avec cette hiérarchie : partition dont les classes sont des éléments (disjoints)
  • Coupure de l’arbre selon une horizontale
• Basée sur la notion de dissimilarité/distance entre individus
  • Application \(d\) : indice de distance si
    • \(d(i,j) = d(j,i)\)
    • \(d(i,j) = 0 \Leftrightarrow i = j\) (dissimilarité si uniquement \(\Leftarrow\))
• Données quantitatives : distance euclidienne (ou \(L_2\)) \(d^2(x_i,x_{i'}) = \sum_{j=1}^d (x_i^j - x_{i'}^j)^2\)
• Données binaires : distance \(L_1\) (de manhattan) \(d_{L_1}(x_i,x_{i'}) = \sum_{j=1}^d |x_i^j - x_{i'}^j|\)

Distance entre parties

• Indice de distance entre éléments de \(H\) : \(d(A,B)\)
  • Niveau d’agrégation de \(A\) et de \(B\)
  • Indice de la plus petite partie de \(H\) contenant \(A\) et \(B\)
• Propriété ultramétrique : \[ d(a,b) \leq \sup\{d(a,c);d(b,c)\} \ \forall a, b, c \]

Recherche de d’une classification hiérarchique = recherche d’une ultramétrique.

Connaissant une métrique sur \(X\), en déduire une ultramétrique aussi proche que possible de la métrique de départ

Classification Ascendante Hiérachique (CAH)

Algorithme

1. Chaque élément dans sa propre classe
2. Calculer les distances entre chaque élément
3. Regrouper les deux éléments les plus proches, et recalculer les distances entre cette nouvelle classe et les autres
4. Recommencer l’étape précédente jusqu’à n’avoir plus qu’une seule classe avec tous les éléments

Problème

• Distance entre éléments (cf plus haut)
• Distance entre classes (cf ci-après)

Distance entre deux classes : critères d’agrégation

• Lien complet : distance maximale entre deux points de chaque classe
  • très sensible aux outliers et assez peu utilisée
  • critère du saut maximum, critère du diamètre, complete linkage \[ d(z_a, z_b) = \max(d(x_i,x_{i'})), x_i \in a, x_{i'} \in b \]
• Lien simple : distance minimale entre deux points de chaque classe
  • sensible à l’effet de chaîne (parfois inconvénient, parfois avantage)
  • critère du saut minimum, single linkage \[ d(z_a, z_b) = \min(d(x_i,x_{i'})), x_i \in a, x_{i'} \in b \]
• Lien moyen : distance moyenne entre les points de chaque classe
  • intermédiaire entre complet et simple, moins sensible au bruit
  • critèrre du saut moyen, average linkage \[ d(z_a, z_b) = \frac{1}{\#z_a \#z_b} \sum_{x_i \in a, x_{i'} \in b} d(x_i,x_{i'}) \]

Distance entre deux classes : critères d’agrégation

• Méthode des centroïdes : distance entre les barycentres (ou centroïdes) des deux classes
  • plus robuste mais moins précise
  • plus simple à calculer \[ d(z_a, z_b) = d^2(g_a, g_b) \]
• Critère de Ward : baisse d’inertie interclasse obtenue en fusionnant ces deux classes
  • version pondérée de la méthode des centroïdes
  • fusion de deux classes occasionnant obligatoirement une baisse de l’inertie interclasse \[ d(z_a, z_b) = \frac{d^2(g_a, g_b)}{\frac{1}{\#z_a} + \frac{1}{\#z_b}} \]
  • calcul récursif possible \[ d(z_a, z_b) = \frac{(\#z_{a_1} + \#z_b) d(a_i, b) + (\#z_{a_2} + \#z_b) d(a_2, b) - \#z_b d(a_1, a_2) }{\#z_{a_1} + \#z_{a_2} + \#z_b} \]
  • classes sphériques et de même effectifs
  • la plus utilisée en CAH

Exemple simple

Les données

La matrice de distance initiale

L’arbre obtenu (lien complet)

L’ultramétrique obtenu

Iris

Classification directe

• Pour \(n\) grand, classification hiérarchique trop coûteuse en temps
• Recherche d’une partition en \(k\) classes
  • \(k\) devant être fourni en paramètre de la méthode
• Méthode de base :
  • A partir d’une partition initiale, amélioration à chaque étape jusqu’à convergence
  • Dépendant de l’initialisation (non déterministe - doit être effectué plusieurs fois)
  • Critère de convergence à définir
• Méthode la plus courante : \(k\)-means

\(k\)-means

Algorithme

1. Choisir \(k\) individus différents, considérés comme les centres initiaux des classes
2. Une autre possibilité est d’assigner aléatoirement chaque individu à une des \(k\) classes, et de calculer les centres de ces classes
3. Assigner chaque objet à la classe la plus proche
4. Calculer les nouveaux centres des classes
5. Répéter les étapes 2 et 3 jusqu’à la convergence du critère

A définir :

• Distance entre les individus
• Critère de convergence
• Nombre de classes \(k\)

\(k\)-means

Distance

On utilise généralement la distance euclidienne entre l’individu \(i\) et la classe \(k\) : \[ d^2(x_i,g_k) = \sum_{j=1}^d (x_i^j - g_k^j)^2 \]

Critère

En se basant sur la distance euclidienne, on cherche à minimiser l’inertie intra-classe : \[ W = \sum_{k=1}^K \sum_{i \in z_k} d^2 (x_i, g_k) = \sum_{k=1}^K \sum_{i \in z_k} \sum_{j=1}^d (x_i^j - g_k^j)^2 \]

Quelques points à noter

• Il est nécessaire de normaliser les variables (sauf cas particulier)
• On remarque qu’il suffit généralement de moins d’une trentaine d’itérations pour converger
• Il est possible d’obtenir des classes vides, on a alors 2 possibilités :
  • Stopper l’algorithme
  • Choisir un nouveau centre aléatoirement
• Pour décrire chaque classe, on utilise les centres des classes

Initialisation

Comme nous pouvons l’imaginer, le résultat de cet algorithme dépend très fortement de l’initialisation. On a donc 2 points à noter :

• Lorsqu’on lance l’algorithme 2 fois, nous n’obtenons pas forcément le même résultat
• Le résultat obtenu est un maximum local, et non un maximum global

Pour éviter ce problème, nous avons 2 possibilités :

• Lancer l’algorithme plusieurs fois et garder le meilleur résultat (i.e. celui avec \(W\) minimal)
• Choisir \(k\) points initiaux les plus distants les uns des autres

\(k\)-means vs CAH

Classification hybride

Pour combiner les avantages des 2 algorithmes (et finalement éviter les inconvénients des deux), on utilise la méthode de Wong, nommée classification hybride, présentée ci-dessous :

1. Réduire les données, en appliquant \(k\)-means avec un nombre de classes important (entre 10 et 100 - avec une limite a \(n^{0.3}\))
   • On obtient ainsi des classes très compacts et homogènes, avec très peu de perte d’iformations
2. Trouver un nombre de classes approprié avec une CAH (e, utilisant le critière de Ward) sur les centres des classes obtenues dans l’étape 1
3. Regrouper les classes de \(k\)-means en se basant sur la méta-partition obtenue dans l’étape 2
4. Optimiser la partition précédente avec \(k\)-means

Quelques alternatives

Il existe bien d’autres méthodes, donc les suivantes :

• Méthode hiérarchique
  • BIRCH
• Méthodes directes
  • Fuzzy \(c\)-means
  • DBSCAN
  • Spectral clustering

DBSCAN

DBSCAN : Density-based spatial clustering of applications with noise

• Basé sur la notion de densité
• Une classe est définie sur l’accessibilité de la densité
  • Un individu est directement accessible à un autre individu si la distance entre les deux est plus petite qu’un seuil défini en amont
  • 2 individus sont accessible entre eux s’il existe une chaîne de points directement accessible 2 à 2 entre les deux
  • Une classe est composée d’individus accessibles entre eux
• Algorithme
  • Pour chaque nouvel individu, on cherche les individus accessible directement
  • S’il y en a un dans une classe, on affecte ce nouveau point à la classe
  • A la fin, les classes avec peu d’individus ne sont pas conservées
• On obtient donc un ensemble de classes et un ensemble d’outliers (individus dans aucune classe)
• Deux paramètres sont à déterminer :
  • Seuil minimal de distance pour considéré deux points comme accessible
  • Nombre minimal d’objets dans une classe