05-Clustering.Rmd

# Classification (clustering)

Les méthodes de classification (= de partitionnement) servent à délimiter des groupes d'individus, ou typologies, à partir des caractéristiques de ces individus. En particulier, elles visent à distinguer des ensembles au sein desquels les individus se ressemblent plus qu'ils ne ressemblent aux individus des autres groupes.

Il faut être prudent dans leur interprétation : le fait que la méthode réussisse à délimiter des groupes ne démontre en rien la pertinence du découpage (c'est-à-dire l'existence de discontinuités entre des groupes plutôt homogènes). Ce n'est pas parce que vous avez découpé, avec un couteau, une tarte en 5 parts, que ce découpage reflète des discontinuités antérieures. Les méthodes de classifications sont, en quelques sortes, des couteaux ... 

## Les k-moyennes

### Principe

L'algorithme des k-moyennes (ou nuées dynamiques, k-means en anglais) consiste à regrouper les individus dans k classes les plus homogènes possibles. Son fonctionnement est très intuitif et il est très peu coûteux en termes de calcul :

- l'utilisateur choisit le nombre de classes $k$.
- l'algorithme prend k points aléatoires (les centres) dans le nuage de point des individus.
- chaque individu est affecté au centre le plus proche.
- on calcule le barycentre des points de chaque classe consitutée $\rightarrow$ les centres bougent.
- on ré-affecte les individus au nouveau centre le plus proche
- on répète les deux étapes précédentes jusqu'à ce que les barycentres ne "bougent plus"

Cet algorithme fonctionne sur des variables **quantitatives** ; on peut le mobiliser sur les coordonnées factorielles des individus et donc l'appliquer sur des variables initialement qualitative (après avoir fait une ACM / AFC). En pratique, il converge assez rapidement et est donc très efficace, même sur de grands jeux de données.

### Mise en oeuvre

Exemple sur les hobbies :

```{r clust_1}
coord <- as.data.frame (acm$ind$coord)
classif <- kmeans (coord, centers = 4)
str (classif)
# Taille des clusters
table (classif$cluster)
```

Remarques :

- Le nombre de classes est choisi de façon arbitraire (comment savoir si ce nombre est correct ?).
- Les résultats changent selon les points initiaux choisis $\Rightarrow$ 2 exécutions consécutives donneront 2 résultats différents ! Deux solutions pour avoir tout le temps le même résultat :
    + fournir les centres initiaux à l'algorithme.
    + fixer la "graine" du générateur de nombres aléatoires.
    
```{r clust_2}
# initialisation des centres avec les quintiles (ça fait 4 points)
# Avec du R de base hyper efficace ^^ 
init <- sapply (coord, function(x) quantile (x, seq(.2,.8,.2)))
classif <- kmeans (coord, centers = init)
# initialisation du générateur de nombres aléatoires
set.seed (1234)
classif <- kmeans (coord, centers = 4)
```

Pour récupérer les résultat dans son *dataframe*, il suffit de rajouter le vecteur résultat dans le *dataframe* initial :

```{r clust_3}
names (coord) <- paste ("Axe", 1:4, sep = "")
coord <- mutate (coord, classe = as.factor (classif$cluster))
ggplot (coord, aes (x = Axe1, y = Axe2, color = classe)) +
  geom_point()
ggplot (coord, aes (x = Axe3, y = Axe4, color = classe)) +
  geom_point()
```

Ici on remarque que les classes 2 et 3 s'opposent sur le premier plan factoriel : la classe 2 est plutôt du côté des personnes ayant peu de hobbies, à l'inverse de la classe 3 est composée d'individus ayant des occupations plutôt culturelles.
Les classes 1 et 4 sont opposées sur l'axe 3, ce qui signifie que la 1 regroupe des individus aux loisirs plutôt domestiques et la 4 des individus ayant des loisirs de plein air.


### Quelques conseils

Pour décrire les classes, on peut, en plus de la représentation sur les axes factoriels, faire un tableau croisé de cette nouvelle variable avec les variables initiales qualitatives ou calculer des rapports de corrélations avec les variables initiales quantitatives. 

Pour choisir le nombre de classes, on peut :

- tester plusieurs configuratons et choisir celle qui est la plus "parlante" (on est dans du descriptif, ne pas l'oublier !)
- faire plusieurs classifications et choisir la meilleure au sens d'un indicateur du type $\dfrac{1}{k} \dfrac{SS_{inter}}{SS_{total}}$
- repérer le nombre optimal avec une CAH

## La classification ascendante hiérarchique (CAH)

Pourquoi cet acronyme ?

- Classification : on regroupe nos individus dans des classes
- Ascendante : on part du niveau le plus fin (ie des individus)
- Hiérarchique : la méthode aboutit à la construction d'un arbre 

Comment faire :  Regrouper les individus les plus proches deux à deux, puis les paquets d'individus deux à deux.

- Notion de distance pour déterminer les *proximités*
- Agrégation des individus puis des groupes d'individus : *métrique* et *hypermétrique*

**On cherche le nombre optimal de classes d'individus**, et pour parvenir à ce nombre, on peut jouer sur plusieurs paramètres :

- Choix des variables prises en compte : initiales ou composantes principales
- Choix de la distance : euclidienne, $\chi^2$, Mahalanobis...
- Choix de l'hypermétrique : Comment vont être regroupés les individus puis les groupes :
    - centres de gravité les plus proches 
    - saut minimum : on agrège les deux groupes pour lesquels la distance entre les deux individus les plus proches est la plus petite
    - diamètre : on agrège les deux groupes pour lesquels la distance entre les deux individus les plus éloignés est la plus petite

Plus de détails sur [cette page](http://maths.cnam.fr/IMG/pdf/Classification-2008-2.pdf)

En général, on utilise le paramétrage suivant :

- Réaliser la classification à partir des composantes principales signifiantes (on prend en compte l'essentiel de l'inertie mais on laisse de côté un certain "bruit", qui correspond aux derniers axes factoriels)
- Utiliser la distance euclidienne classique
- Utiliser la méthode de Ward : à chaque étape, agréger les individus (groupes) font perdre le moins *d'inertie inter-classes*

$\Rightarrow$ la fonction `HCPC` du package factominer le fait directement pour vous.

```{r hcpc, cache=TRUE}
hc <- HCPC (acm, nb.clust = 5, graph=F)
str(hc)
```

### Détermination du nombre de classes

Pour déterminer le nombre optimal de classes, on regarde la perte d'inertie inter-classes (pour ça, il faut lancer une première fois la commande avec un nombre arbitraire de classes). En effet, on part d'une situation où il n'y a que de l'inertie inter-classes (chaque classe comprenant un seul individu, il n'y a pas d'inertie intra-classe). Au fur et à mesure des regroupements, on va donc perdre en inertie inter-classes, jusqu'à la dernière étape où il y a une classe avec tous les individus et donc plus d'inertie inter. Le but du jeu consiste à "stopper" l'aggrégation avant de perdre une forte quantité d'inertie inter-classe. On s'intéresse au dernières étapes pour ne pas alourdir le graphique (et on prendra un nombre de classe inférieur à 20 en général, sinon, ce n'est pas très opérationnel...). Ce diagramme ressemble très fortement à l'éboulis des valeurs propres, et on cherche à peu près la même chose (un saut).

```{r  clust_4}
barplot(hc$call$t$inert.gain[1:20],horiz = T,main="Gain d'inertie intra sur les 20 dernières agrégations ",
          col="lightblue",border = "grey")
```

Autre représentation : le dendogramme représente les étapes d'agrégation. La auteur des branches représente la perte d'inertie inter-classe (ou le gain d'inertie intra)

```{r clust_5}
plot(hc, choice ="tree")
```

### Description des classes

Une fois que l'on a déterminé le nombre de classes, il reste à les décrire. Premier outil : le tableau croisé pour voir la taille de chacun.

```{r clust_6}
table (hc$data.clust$clust)
```

```{r clust_7, eval = FALSE}
hc$desc.var$category$`1`
hc$desc.ind$para
```

- cla/mod indique quelle part (pourcentage) de tous les individus présentant cette modalité se
retrouve dans cette classe 
- mod/cla indique quelle part (pourcentage) de tous les individus de la classe présentent cette
modalité.
- Les parangons sont les individus les plus représentatifs de la classe

Visualisation du dendogrades classes sur les axes factoriels

```{r plot_hc, cache=TRUE}
plot(hc, choice ="3D.map")
```

### Quelques conseils pratiques

Le but d'un classification est d'obtenir des groupes d'individus qui "parlent" (c'est un outils de communication puissant) ; l'application des méthodes à la lettre peut ne pas aboutir à un tel résultat. On peut alors jouer sur différents paramètres :

- Les variables mobilisées
- Le nombre de classes
- La distance
- La méthode d'agrégation
- Utiliser une méthode non hiérarchique (exemple : `kmeans`) $\rightarrow$ pour "consolider" la CAH avec cette méthode (permet de minimiser la variance intra)

Remarque importante : l'algorithme est très coûteux et est très lent quand le nombre d'individus est important. On peut alors réduire le nombre d'individus initial en procédant au préalable à une classification avec kmeans. La fonction `HCPC` permet de le faire avec le paramètre kk=.

Il faut ensuite donner un nom aux classes (pas uniquement les décrire) : attention aux termes utilisés !


## Exercice

Reprendre la base de données sur les iris et réaliser une classification des 150 fleurs

- Avec kmeans
- Avec une CAH
- Que peut-on dire des résultats et leur lien avec la variable Species ?


```{r clust_8,collapse=T}
hc.iris <- HCPC (acp.iris, nb.clust = 3)
kmeans.iris <- kmeans (acp.iris$ind$coord, centers = 3)
res.iris <- data.frame (acp.iris$ind$coord, classe = as.factor (kmeans.iris$cluster),
                       Species = iris$Species)

ggplot (res.iris, aes (x = Dim.1, y = Dim.2, color = classe)) +
  geom_point ()
```

On compare à la vraie classe. Conclusion : la nature est mal faite...

```{r clust_9}
# La vraie classe :

ggplot (res.iris, aes (x = Dim.1, y = Dim.2, color = Species)) +
  geom_point ()
```