Classification non supervisée - Clustering

Méthodes de partitionnement et algorithme k-Means

Qu'est ce qu'une classification non supervisée

• C'est rechercher des regroupements "naturels" entre des individus
• Le nombre de groupes n'est pas connu a priori
• Aucune connaissance sur les classes des individus n'est disponible a priori
• Il s'agit d'une méthode de statistique exploratoire permettant de comprendre les données

Objectifs de la classification non supervisée

• Construire des groupes homogènes et interprétables vis-à-vis de l'objectif recherché
• Les individus au sein d'un groupe doivent être aussi semblables que possible au sens d'un ou plusieurs critères donnés
• Les individus de groupes distincts doivent être aussi différents que possible au sens des mêmes critères

Partition d'un ensemble d'individus

• Soit \(\boldsymbol{X}\) un tableau de données contenant \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\).
• Les ensembles d'indices \(C_{1}, \ldots, C_{k}, \ldots, C_{K} \subseteq \{1, 2, \ldots, N\}\) forment une partition, notée \(C\), des données \(\boldsymbol{X}\) en \(K\) classes si :
  • Pour tout \(k\), \(C_{k} \neq \varnothing\), i.e. aucune classe n'est vide
  • \(\bigcup_{k=1}^{K} C_{k} = \{1, \ldots, N \}\), i.e. la réunion des classes contient les indidces de tous les individus du jeu de données \(\boldsymbol{X}\)
  • Pour tout \(k_{1}, k_{2}\), \(C_{k_{1}} \cap C_{k_{2}} = \varnothing\) si \(k_{1} \neq k_{2}\), i.e. les classes sont deux à deux disjointes

Résumé statistique d'une classe

• Soit \(\boldsymbol{X}\) un tableau de données contenant \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\) définis dans \(\mathbb{R}^{D}\)
• Considérons une partition à \(K\) classes, notée \(C = \{C_{1},\ldots,C_{K}\}\)
• Chaque classe \(C_{k}\) peut, entre autres, être caractérisée par :

• son effectif : \(N_{k} = \text{Card}(C_{k})\)
• son centre (point moyen, centre de gravité) : \[ \boldsymbol{\mu}_{k} = \frac{1}{N_{k}}\sum_{n \in C_{k}} \boldsymbol{x}_{n} = \left(\frac{1}{N_{k}}\sum_{n \in C_{k}} x_{n, 1}, \ldots, \frac{1}{N_{k}}\sum_{n \in C_{k}} x_{n, D}\right) \]
• la dispersion autour de son centre caractérisée par la matrice de variance-covariance empirique de la classe : \[ \boldsymbol{W}_{k} = \frac{1}{N_{k} - 1}\sum_{n \in C_{k}} (\boldsymbol{x}_{n} - \boldsymbol{\mu}_{k})(\boldsymbol{x}_{n} - \boldsymbol{\mu}_{k})^{T} \]
• son inertie de classe (cas équipondéré) : \(I_{\boldsymbol{\mu}_{k}}(C_{k}) = \sum_{n \in C_{k}} d(\boldsymbol{x}_{n}, \boldsymbol{\mu}_{k})^{2}\)

Critère de qualité d'une partition

• Soit \(\boldsymbol{X}\) un ensemble d'individus
• On définit un critère de qualité sur une partition \(C = \{C_{1}, \ldots, C_{K}\} \in \mathcal{C}_{K}(\boldsymbol{X})\) comme étant une fonction de la forme : \[ Q : \mathcal{C}_{K}(\boldsymbol{X}) \rightarrow \mathbb{R}^{+} \]
• Plusieurs critères de qualité \(Q\) peuvent être définis mais tous partagent en général le point commun de mesurer l'homogénéité des classes
• Rappel : \(\mathcal{C}_{K}(\boldsymbol{X})\) est l'ensemble de toutes les partitions possibles de \(\boldsymbol{X}\) en \(K\) classes

Le partitionnement comme problème d'optimisation

• Soit \(\boldsymbol{X}\) un ensemble d'individus
• Soit \(Q\) un critère de qualité de partitionnement en \(K\) classes
• Résoudre le problème de partitionnement des données \(\boldsymbol{X}\) en \(K\) classes revient à trouver la partition optimale \(C^{*} \in \mathcal{C}_{K}(\boldsymbol{X})\) qui maximise le critère de qualité \(Q\)
• Il s'agit donc d'un problème d'optimisation classique que l'on peut écrire formellement : \[ C^{*}_{K} = \arg\max_{C \in \mathcal{C}_{K}(\boldsymbol{X})} Q(C) \]

Principe général des algorithmes de partitionnement

• Soit \(\boldsymbol{X}\) un ensemble d'individus
• Soit \(Q\) un critère de qualité de partitionnement en \(K\) classes
• Les algorithmes de partitionnement reposent sur le schéma itératif général suivant :
  • Initialisation (\(t=0\)): on part d'une partition initiale \(C^{(0)}\) (choisi arbitrairement)
  • À l'étape \(t + 1\), on cherche la partition \(C^{(t+1)} = f(C^{(t)})\) telle que \(Q(C^{(t+1)}) \ge Q(C^{(t)})\)
  • On arrête l'algorithme dès que le critère de qualité a convergé, i.e. qu'il ne varie plus suffisamment d'une itération à l'autre
• La plupart des méthodes utilisées aujourd'hui reposent sur ce schéma et ne diffèrent donc qu'au niveau de la fonction \(f\) permettant d'améliorer la classification des individus à partir d'une partition donnée

Stratégies possibles

1. Expertise : Vous avez une idée plus ou moins précise sur le nombre de groupes à former
2. Tests automatiques : On réalise différents partitionnements en faisant varier le nombre de classes et on utilise un critère pour sélectionner la valeur optimale, e.g. :
   • Méthode du "coude", approche visuelle
   • Critère AIC (Akaïke Information Criterion) ou BIC (Bayesian Information Criterion), approche plus formelle nécessitant une reformulation du problème de classification automatique dans le cadre probabiliste
   • Stabilité des partitions, on retient le nombre de classes qui permet d'obtenir les partitions les plus stables malgré une initialisation aléatoire

Points clés

• Le problème de partition des données est un problème combinatoire extrêmement complexe
• Les algorithmes de partitionnement usuels ne cherchent pas à construire la partition optimale mais plutôt une bonne partition
• La méthode des moyennes mobiles est une méthode de partitionnement géométrique simple à mettre en oeuvre permettant de classer les individus dans des groupes ayant des caractérisques homogènes