Extraction de connaissances à partir de données structurées et non structurées

class: center, middle, inverse, title-slide

.title[
# Extraction de connaissances à partir de données structurées et non structurées
]
.subtitle[
## Séance 4 : Classification (CAH et <span class="math inline"><em>k</em></span>-means)
]

---

## 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}$`

`$\rightarrow$` 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 totale

- **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
$$

---
## Inertie intraclasse et interclasse

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 classe
`$$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$` 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

---
## 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
1. Calculer les distances entre chaque élément
1. Regrouper les deux éléments les plus proches, et recalculer les distances entre cette nouvelle classe et les autres
1. 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)
    - 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 en fusionnant les 2 classes
  - version pondérée de la méthode des centroïdes
  - fusion de deux classes `$\rightarrow$` 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

---
## Exemple simple

La matrice de distance initiale

---
## Exemple simple

L'arbre obtenu (lien complet)

---
## Exemple simple

L'ultramétrique obtenu

---
## Iris

---
## Iris - Description des classes obtenue avec CAH *Ward*

#### Avec 2 classes

<table>
 <thead>
  <tr>
   <th style="text-align:right;"> Sepal.Length </th>
   <th style="text-align:right;"> Sepal.Width </th>
   <th style="text-align:right;"> Petal.Length </th>
   <th style="text-align:right;"> Petal.Width </th>
  </tr>
 </thead>
<tbody>
  <tr>
   <td style="text-align:right;"> 5.01 </td>
   <td style="text-align:right;"> 3.43 </td>
   <td style="text-align:right;"> 1.46 </td>
   <td style="text-align:right;"> 0.25 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 6.26 </td>
   <td style="text-align:right;"> 2.87 </td>
   <td style="text-align:right;"> 4.91 </td>
   <td style="text-align:right;"> 1.68 </td>
  </tr>
</tbody>
</table>

#### Avec 3 classes

<table>
 <thead>
  <tr>
   <th style="text-align:right;"> Sepal.Length </th>
   <th style="text-align:right;"> Sepal.Width </th>
   <th style="text-align:right;"> Petal.Length </th>
   <th style="text-align:right;"> Petal.Width </th>
  </tr>
 </thead>
<tbody>
  <tr>
   <td style="text-align:right;"> 5.01 </td>
   <td style="text-align:right;"> 3.43 </td>
   <td style="text-align:right;"> 1.46 </td>
   <td style="text-align:right;"> 0.25 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 5.92 </td>
   <td style="text-align:right;"> 2.75 </td>
   <td style="text-align:right;"> 4.42 </td>
   <td style="text-align:right;"> 1.43 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 6.87 </td>
   <td style="text-align:right;"> 3.09 </td>
   <td style="text-align:right;"> 5.77 </td>
   <td style="text-align:right;"> 2.11 </td>
  </tr>
</tbody>
</table>

---
## 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
  1. Une autre possibilité est d'assigner aléatoirement chaque individu à une des `$k$` classes, et de calculer les centres de ces classes
1. Assigner chaque objet à la classe la plus proche
1. Calculer les nouveaux centres des classes
1. Répéter les étapes 2 et 3 jusqu'à la convergence du critère

### Problème

- 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

---
## Iris - Choix du nombre de classes (avec `$k$`-means)

- Choix de `$k=3$` classes (mais peut-être 2 est intéressant)

---
## Iris - Description des classes obtenue avec `$k$`-means

#### Avec 2 classes

<table>
 <thead>
  <tr>
   <th style="text-align:right;"> Sepal.Length </th>
   <th style="text-align:right;"> Sepal.Width </th>
   <th style="text-align:right;"> Petal.Length </th>
   <th style="text-align:right;"> Petal.Width </th>
  </tr>
 </thead>
<tbody>
  <tr>
   <td style="text-align:right;"> 5.01 </td>
   <td style="text-align:right;"> 3.37 </td>
   <td style="text-align:right;"> 1.56 </td>
   <td style="text-align:right;"> 0.29 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 6.30 </td>
   <td style="text-align:right;"> 2.89 </td>
   <td style="text-align:right;"> 4.96 </td>
   <td style="text-align:right;"> 1.70 </td>
  </tr>
</tbody>
</table>

#### Avec 3 classes

<table>
 <thead>
  <tr>
   <th style="text-align:right;"> Sepal.Length </th>
   <th style="text-align:right;"> Sepal.Width </th>
   <th style="text-align:right;"> Petal.Length </th>
   <th style="text-align:right;"> Petal.Width </th>
  </tr>
 </thead>
<tbody>
  <tr>
   <td style="text-align:right;"> 6.85 </td>
   <td style="text-align:right;"> 3.07 </td>
   <td style="text-align:right;"> 5.74 </td>
   <td style="text-align:right;"> 2.07 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 5.90 </td>
   <td style="text-align:right;"> 2.75 </td>
   <td style="text-align:right;"> 4.39 </td>
   <td style="text-align:right;"> 1.43 </td>
  </tr>
  <tr>
   <td style="text-align:right;"> 5.01 </td>
   <td style="text-align:right;"> 3.43 </td>
   <td style="text-align:right;"> 1.46 </td>
   <td style="text-align:right;"> 0.25 </td>
  </tr>
</tbody>
</table>

---
## `$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 (en 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