Classification non supervisée - Clustering

Introduction et notions fondamentales

Objectifs de la séance

• Définir la problématique de classification non supervisée
• Replacer cette technique dans le paysage méthodologique de l'analyse de données
• Rappeler et généraliser la notion de distance
• Introduire le concept d'inertie dans le cadre d'une partition des données
• Comprendre comment évaluer la qualité d'une partition

Principes d'une classification

Construire des groupes d'individus homogènes et différenciés à partir de leurs caractéristiques.

Autrement dit, après classification, on souhaite que :

• Les individus au sein d'un groupe soient aussi semblables que possible
• Les groupes soient aussi différents que possible
• Les groupes puissent être interprétés eu égard de l'objectif (métier) recherché

Objectifs

• Affecter à chaque individu une et une seule classe
• Le résultat d'une classification est donc une nouvelle variable qualitative contenant le label (ou numéro) de la classe pour chaque individu

Principe général

• Classer des individus, c'est regroupé des individus qui "se ressemblent"
• On doit donc définir :
  1. La notion d'"individus semblables"
  2. Le nombre de groupes/classes à construire

Représentation matricielle des données

Mathématiquement, il est commode de représenter un tableau de données par une matrice de \(N\) lignes et \(D\) colonnes :

• \(N\) correspond au nombre d'individus/observations contenus dans les données
• \(D\) correspond à la dimension des données, autrement dit le nombre de variables observées
• Le vecteur colonne \(\boldsymbol{x}_{\cdot, d}=(x_{1,d}, \ldots, x_{n,d}, \ldots, x_{N,d})\) représente les valeurs prises par la variable \(d\) de chaque individu/observation
• Le vecteur ligne \(\boldsymbol{x}_{n} = \boldsymbol{x}_{n, \cdot}=(x_{n,1}, \ldots, x_{n,d}, \ldots, x_{n,D})\) représente le \(n\) -ème individu/observation

Notion de proximité

• Deux individus sont semblables s'ils sont proches au sens d'une mesure de proximité
• La proximité géométrique entre deux individus est généralement mesurée à l'aide d'une dissimilarité ou d'une distance
• Par extension, il est possible de définir et calculer des distances entre classes, entre individus et classes, entre groupes d'individus, etc.

Distance euclidienne

La distance euclidienne est une fonction \(d\) définie pour tous vecteurs \(\boldsymbol{x}_{\ell} = (x_{\ell, 1}, \ldots, x_{\ell, D}) \in \mathbb{R}^{D}\) et \(\boldsymbol{x}_{m} = (x_{m, 1}, \ldots, x_{m, D}) \in \mathbb{R}^{D}\) : \[ d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) = \sqrt{\sum_{d = 1}^{D} \left(x_{\ell,d} - x_{m,d}\right)^{2}} \]

Distance

Soit \(d\) une distance définie sur \(\mathbb{R}^{D}\). Nous avons alors pour tout \(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m} \in \mathbb{R}^{D}\), les propriétés suivantes :

• (positivité) \(d\) est une application \(\mathbb{R}^{D} \times \mathbb{R}^{D}\) dans \(\mathbb{R}^{+}\), i.e. \[ d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) \ge 0 \]
• (symétrie) \(d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) = d(\boldsymbol{x}_{m}, \boldsymbol{x}_{\ell})\)
• (séparation) \(d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) = 0 \iff \boldsymbol{x}_{\ell} = \boldsymbol{x}_{m}\)
• (inégalité triangulaire) Pour tout \(\boldsymbol{x}_{p} \in \mathbb{R}^{D}\), \({x}_{p} \neq {x}_{\ell}, {x}_{m}\) \[ d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) < d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{p}) + d(\boldsymbol{x}_{p}, \boldsymbol{x}_{m}) \]

Matrice de distances

Soit \(\boldsymbol{X}\) un tableau de données contenant un ensemble de \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\). En choisissant une distance \(d\), nous pouvons regrouper les distances de tous les couples \((\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m})\) dans une matrice \(\boldsymbol{\Delta}_{d}\) de taille \(N \times N\) telle que : \[ \boldsymbol{\Delta}_{d}(\ell, m) = d(\boldsymbol{x}_{\ell}, \boldsymbol{x}_{m}) \]

La matrice \(\boldsymbol{\Delta}_{d}\) est appelée matrice de distances des données \(\boldsymbol{X}\) par rapport à la distance \(d\) (e.g. distance euclidienne, Mahalanobis, etc.)

Inertie d'un ensemble d'individus par rapport à un point

• Soit \(\boldsymbol{X}\) un tableau de données contenant un ensemble de \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\)
• Chaque individu est défini par \(D\) variables, i.e. tout individu \(n\) est représenté par un vecteur \(\boldsymbol{x}_{n} = (x_{n, 1}, \ldots, x_{n, D}) \in \mathbb{R}^{D}\)
• Nous supposons également que chaque individu \(\boldsymbol{x}_{n}\) possède un poids \(\omega_{n} \ge 0\)
• Considérons ensuite :
  • un sous groupe d'individus caractérisé par leurs indices \(\mathcal{G} \subseteq \{1, 2, \ldots, N\}\)
  • un point/vecteur \(\boldsymbol{a} = (a_{1}, \ldots, a_{D})\) de l'espace \(\mathbb{R}^{D}\)
  • une distance \(d\) définie sur l'espace \(\mathbb{R}^{D}\)
• L'inertie des individus du groupe \(\mathcal{G}\) par rapport au point \(\boldsymbol{a}\) est alors : \[ I_{\boldsymbol{a}}(\mathcal{G}) = \sum_{i \in \mathcal{G}} \omega_{i} d(\boldsymbol{x}_{i}, \boldsymbol{a})^{2} \]

Inertie dans le cas équipondéré

• Supposons à présent que les individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\) soient équipondérés
• La définition générale précédente de l'inertie d'un groupe d'individus par rapport à un point devient :
  • Si \(\omega_{n} = 1/N\), pour tout individu \(\boldsymbol{x}_{n}\) : \[ I_{\boldsymbol{a}}(\mathcal{G}) = \frac{1}{N} \sum_{i \in \mathcal{G}} d(\boldsymbol{x}_{i}, \boldsymbol{a})^{2} \]
  • Si \(\omega_{n} = 1\), pour tout individu \(\boldsymbol{x}_{n}\) : \[ I_{\boldsymbol{a}}(\mathcal{G}) = \sum_{i \in \mathcal{G}} d(\boldsymbol{x}_{i}, \boldsymbol{a})^{2} \]

Centre de gravité d'un sous-groupe d'individus

• Soit \(\boldsymbol{X}\) un tableau de données contenant un ensemble de \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\) caractérisés dans \(\mathbb{R}^{D}\) et pondérés par \(\omega_{1}, \ldots, \omega_{N}\)
• Considérons un sous groupe d'individus \(\mathcal{G} \subseteq \{1, 2, \ldots, N\}\)
• Le centre de gravité du groupe \(\mathcal{G}\), noté \(\boldsymbol{\mu}_{\mathcal{G}} \in \mathbb{R}^{D}\) est défini par : \[ \boldsymbol{\mu}_{\mathcal{G}} = \frac{1}{\Omega_{\mathcal{G}}} \sum_{i \in \mathcal{G}} \omega_{i} \boldsymbol{x}_{i} \] avec \(\Omega_{\mathcal{G}} = \sum_{i \in \mathcal{G}} \omega_{i}\)

Cas équipondéré

• Dans le cas où, pour tout \(n\), \(\omega_{n} = \omega > 0\), i.e. tous les individus ont le même poids
• Le centre de gravité du groupe \(\mathcal{G}\) devient : \[ \boldsymbol{\mu}_{\mathcal{G}} = \frac{1}{N_{\mathcal{G}}} \sum_{i \in \mathcal{G}} \boldsymbol{x}_{i} \] avec \(N_{\mathcal{G}} = \text{Card}(\mathcal{G})\)

Inertie totale

• Soit \(\boldsymbol{X}\) un tableau de données contenant \(N\) individus \(\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{N}\}\) de \(\mathbb{R}^{D}\) et pondérés par \(\omega_{1}, \ldots, \omega_{N}\)
• L'inertie totale des individus \(\boldsymbol{X}\), notée \(I_{\text{T}}\), est : \[ I_{\text{T}} = I_{\boldsymbol{\mu}_{\boldsymbol{X}}}(\boldsymbol{X}) = \sum_{n = 1}^{N} \omega_{n} d(\boldsymbol{x}_{n}, \boldsymbol{\mu}_{\boldsymbol{X}})^{2} \] où \(\boldsymbol{\mu}_{\boldsymbol{X}} \in \mathbb{R}^{D}\) est le centre de gravité du nuage d'individus \(\boldsymbol{X}\)

Inertie intra-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}\) et pondérés par \(\omega_{1}, \ldots, \omega_{N}\)
• Considérons une partition de \(\boldsymbol{X}\) à \(K\) classes, notée \(C = \{C_{1},\ldots,C_{K}\}\)
• L'inertie intra-classe de la partition \(C\), notée \(I_{\text{W}}(C)\) ("W" pour within en anglais), est : \[ I_{\text{W}}(C) = \sum_{k=1}^{K} I_{\boldsymbol{\mu}_{k}}(C_{k}) = \sum_{k=1}^{K} \sum_{i \in C_{k}} \omega_{i} d(\boldsymbol{x}_{i}, \boldsymbol{\mu}_{k})^{2} \] où \(I_{\boldsymbol{\mu}_{k}}(C_{k})\) est l'inertie des individus de la classe \(k\) par rapport à son centre \(\boldsymbol{\mu}_{k}\)
• \(\boldsymbol{\mu}_{k} \in \mathbb{R}^{D}\) est le centre de gravité du nuage d'individus appartenant à la classe \(k\) avec : \[ \boldsymbol{\mu}_{k} = \frac{1}{\Omega_{k}} \sum_{i \in C_{k}} \omega_{i} \boldsymbol{x}_{i} \] où \(\Omega_{k} = \sum_{i \in C_{k}} \omega_{i}\) correspond au poids de la classe \(k\)

Inertie de classe

• En considérant une partition de \(\boldsymbol{X}\) à \(K\) classes \(\{C_{1},\ldots,C_{K}\}\)
• Le terme \(I_{\boldsymbol{\mu}_{k}}(C_{k})\) correspond à l'inertie des individus de la classe \(k\) par rapport à son centre \(\boldsymbol{\mu}_{k}\)
• On peut désigner le terme \(I_{\boldsymbol{\mu}_{k}}(C_{k})\) comme l'inertie interne de la classe \(k\)
• L'inertie interne de la classe \(k\) s'interprète comme la quantité d'information perdue lorsque l'on résume le nuage d'individus de la classe \(k\) par le centre de la classe
• Une bonne partition pourra donc consister à minimiser les inerties internes de chaque classe de manière à minimiser globalement l'inertie intra-classe du nuage d'individus

Inertie inter-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}\) et pondérés par \(\omega_{1}, \ldots, \omega_{N}\)
• Considérons une partition de \(\boldsymbol{X}\) à \(K\) classes, notée \(C = \{C_{1},\ldots,C_{K}\}\)
• L'inertie inter-classe de la partition \(C\), notée \(I_{\text{B}}(C)\) ("B" pour between en anglais), est : \[ I_{\text{B}}(C) = \sum_{k=1}^{K} \Omega_{k} d(\boldsymbol{\mu}_{k}, \boldsymbol{\mu}_{\boldsymbol{X}})^{2} \] où \(\Omega_{k} = \sum_{i \in C_{k}} \omega_{i}\) correspond au poids de la classe \(k\)

Décomposition de l'inertie totale

• Soient \(\boldsymbol{X}\) un tableau de données et une partition \(C\) de \(\boldsymbol{X}\)
• Nous avons la décomposition suivante de l'inertie totale : \[ I_{\text{T}}(\boldsymbol{X}) = I_{\text{W}}(C) + I_{\text{B}}(C) \]

Théorème de Huygens

• Soit \(\mathcal{C} = \{1, \ldots, N_{\mathcal{C}}\}\), un ensemble d'indices caractérisant \(N_{\mathcal{C}}\) individus \(\{\boldsymbol{x}_{i} ; i \in \mathcal{C}\}\) définis dans \(\mathbb{R}^{D}\)
• Chaque individu \(\boldsymbol{x}_{i}\) est pondéré par \(\omega_{i} \in \mathbb{R}\)
• On note \(\boldsymbol{\mu}_{\mathcal{C}} = \frac{1}{\sum_{i \in \mathcal{C}} \omega_{i}} \sum_{i \in \mathcal{C}} \omega_{i} \boldsymbol{x}_{i}\)
• On a alors pour tout \(\boldsymbol{a} \in \mathbb{R}^{D}\) : \[ I_{\boldsymbol{a}}(\mathcal{C}) = I_{\boldsymbol{\mu}_{\mathcal{C}}}(\mathcal{C}) + (\sum_{i \in \mathcal{C}} \omega_{i}) d(\boldsymbol{a}, \boldsymbol{\mu}_{\mathcal{C}})^{2} \]

Pourcentage d'inertie expliquée par une partition

• Soient \(\boldsymbol{X}\) un tableau de données et une partition \(C\) de \(\boldsymbol{X}\)
• Le pourcentage d'inertie expliquée par \(C\) est : \[ \%I(\boldsymbol{X}, C) = 100 \times \frac{I_{\text{B}}(C)}{I_{\text{T}}(\boldsymbol{X})} = 100 \times \left(1 - \frac{I_{\text{W}}(C)}{I_{\text{T}}(\boldsymbol{X})}\right) \]

Points clés

• Formalisation de la problématique de classification non supervisée pour le traitement des données quantitatives
• Introduction des notions de classe, partition et hiérarchie
• Définition de la notion de distance et calcul pratique
• Introduction du concept d'inertie et étude de ses propriétés dans le cadre de l'analyse de données
• Application de l'inertie pour évaluer la qualité d'une partition des données