Classification automatique, typologie, clustering

Ricco RAKOTOMALALA
Université Lumière Lyon 2

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 1
 PLAN

1. Classification automatique - Objectifs

2. CAH – Algorithme
3. Détection du nombre de classes
4. Classement d’un nouvel individu
5. Logiciels – Exemple d’analyse
6. Tandem Analysis – CAH sur composantes principales
7. Classification mixte – Traitement des grands fichiers
8. Bilan
9. Bibliographie

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 2
 La typologie ou le Clustering ou l’Apprentissage non-supervisé

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 3
Classification automatique
Typologie, apprentissage non-supervisé, clustering

X (tous quantitatifs)
Pas de Y à prédire
Modele Prix Cylindree Puissance Poids Consommation Groupe
Daihatsu Cuore 11600 846 32 650 5.7 Objectif : identifier des groupes d’observations ayant des
Suzuki Swift 1.0 GLS 12490 993 39 790 5.8
Fiat Panda Mambo L 10450 899 29 730 6.1 caractéristiques similaires (ex. comportement d’achats de
VW Polo 1.4 60 17140 1390 44 955 6.5
Opel Corsa 1.2i Eco
Subaru Vivio 4WD
14825
13730
1195
658
33
32
895
740
6.8
6.8
clients, caractère « polluant » de véhicules, etc.)
Toyota Corolla 19490 1331 55 1010 7.1
Opel Astra 1.6i 16V 25000 1597 74 1080 7.4
Peugeot 306 XS 108 22350 1761 74 1100 9
Renault Safrane 2.2. V 36600 2165 101 1500 11.7 On veut que :
Seat Ibiza 2.0 GTI 22500 1983 85 1075 9.5
VW Golt 2.0 GTI
Citroen Z X Volcane
31580
28750
1984
1998
85
89
1155
1140
9.5
8.8
(1) Les individus dans un même groupe se ressemblent le plus
Fiat Tempra 1.6 Liberty 22600 1580 65 1080 9.3
Fort Escort 1.4i PT 20300 1390 54 1110 8.6
possible
Honda Civic Joker 1.4 19900 1396 66 1140 7.7
Volvo 850 2.5 39800 2435 106 1370 10.8 (2) Les individus dans des groupes différents se démarquent le
Ford Fiesta 1.2 Z etec 19740 1242 55 940 6.6
Hyundai Sonata 3000 38990 2972 107 1400 11.7 plus possible
Lancia K 3.0 LS 50800 2958 150 1550 11.9
Mazda Hachtback V 36200 2497 122 1330 10.8
Mitsubishi Galant 31990 1998 66 1300 7.6
Opel Omega 2.5i V6 47700 2496 125 1670 11.3
Peugeot 806 2.0 36950 1998 89 1560 10.8 Pourquoi ?
Nissan Primera 2.0 26950 1997 92 1240 9.2
Seat Alhambra 2.0 36400 1984 85 1635 11.6  Identifier des structures sous-jacentes dans les données
Toyota Previa salon 50900 2438 97 1800 12.8
Volvo 960 Kombi aut 49300 2473 125 1570 12.7  Résumer des comportements
 Affecter de nouveaux individus à des catégories
 Identifier les cas totalement atypiques

Identifier les catégories (groupes) de voitures «

similaires » (c.-à-d. qui se ressemblent)

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 4
Modele Prix Cylindree Puissance Poids Consommation Groupe
Renault Safrane 2.2. V 36600 2165 101 1500 11.7 c_hac_1 Exemple des voitures
Volvo 850 2.5 39800 2435 106 1370 10.8 c_hac_1
Hyundai Sonata 3000 38990 2972 107 1400 11.7 c_hac_1
Lancia K 3.0 LS 50800 2958 150 1550 11.9 c_hac_1
Mazda Hachtback V 36200 2497 122 1330 10.8 c_hac_1
Opel Omega 2.5i V6 47700 2496 125 1670 11.3 c_hac_1
Peugeot 806 2.0 36950 1998 89 1560 10.8 c_hac_1
Seat Alhambra 2.0 36400 1984 85 1635 11.6 c_hac_1
Toyota Previa s alon 50900 2438 97 1800 12.8 c_hac_1
Volvo 960 Kombi aut 49300 2473 125 1570 12.7 c_hac_1
Opel As tra 1.6i 16V 25000 1597 74 1080 7.4 c_hac_2
Peugeot 306 XS 108 22350 1761 74 1100 9 c_hac_2 Segments « classiques »
Seat Ibiza 2.0 GTI 22500 1983 85 1075 9.5 c_hac_2
VW Golt 2.0 GTI 31580 1984 85 1155 9.5 c_hac_2
des voitures : petites,
Citroen Z X Volcane 28750 1998 89 1140 8.8 c_hac_2 moyennes,
Fiat Tempra 1.6 Liberty 22600 1580 65 1080 9.3 c_hac_2
Fort Es cort 1.4i PT 20300 1390 54 1110 8.6 c_hac_2 berlines/monospaces
Honda Civic Joker 1.4 19900 1396 66 1140 7.7 c_hac_2
Mits ubis hi Galant 31990 1998 66 1300 7.6 c_hac_2
Nis s an Primera 2.0 26950 1997 92 1240 9.2 c_hac_2
Daihats u Cuore 11600 846 32 650 5.7 c_hac_3
Suzuki Swift 1.0 GLS 12490 993 39 790 5.8 c_hac_3
Fiat Panda Mambo L 10450 899 29 730 6.1 c_hac_3
VW Polo 1.4 60 17140 1390 44 955 6.5 c_hac_3
Opel Cors a 1.2i Eco 14825 1195 33 895 6.8 c_hac_3
Subaru Vivio 4WD 13730 658 32 740 6.8 c_hac_3
Toyota Corolla 19490 1331 55 1010 7.1 c_hac_3
Ford Fies ta 1.2 Z etec 19740 1242 55 940 6.6 c_hac_3
(X1) PCA_1_Axis_1 vs. (X2) PCA_1_Axis_2 by (Y) Cluster_HAC_2

0 Axe 1 : 92.5%
Sur les 2 premiers axes de l’ACP

Petites voitures Moyennes Grosses berlines

et/ou monospaces
-1

-3 -2 -1 0 1 2 3

Ricco Rakotomalala
5
c_hac_1 c_hac_2 c_hac_3

Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/

Classification automatique
Objectifs

Principe : Constituer des groupes (classes, clusters) « naturels » de manière à ce que les individus dans
un même groupe se ressemblent, et les individus dans des groupes différents soient dissemblables.

Autres visions :
• Identifier des groupes d’individus ayant un comportement (ou des caractéristiques) homogènes
• Proposer un résumé des données en explicitant ses principales dimensions (oppositions)
• Mettre en évidence les principales structures dans les données (définir des « concepts »)
• Construction d’une taxonomie (classification hiérarchique) d’objets (cf. taxonomie des espèces)
Illustration dans le plan

Points clés dans la constitution des groupes.

Quantifier :
• La proximité entre 2 individus
• La proximité entre 2 groupes
• La proximité entre 1 individu et un groupe (lors de la
construction et l’affectation)

• Le degré de compacité d’un groupe

• L’éloignement global entre les groupes (séparabilité)

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 6
 Une technique très populaire… pour de nombreuses raisons

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 7
CAH - Algorithme

Définir une mesure de

Entrée : tableau de données (X) distance entre individus

Sortie : Indicateur de partition des individus

Calcul du tableau des distances entre individus

Chaque individu constitue un groupe (classe)
Définir une stratégie
REPETER
d’agrégation c.-à-d. une mesure
Détecter les 2 groupes les plus proches
de dissimilarité entre groupes
Les agréger pour n’en former qu’un seul
(entre un individu et un groupe)
JUSQU’À tous les individus forment un seul groupe

Identifier le nombre adéquat de groupes

Procéder au partitionnement
De quel outil peut-on disposer
pour identifier la « bonne »
partition ? Dendrogramme.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 8
CAH – Un exemple (1)
Tableau de données
10

Matrice de distances entre individus

8

5
6

4
x2

3
2 1
2
0

0 2 4 6 8 10 Distance euclidienne entre individus

x1 d (1,3)  8  62  3  42

 4 1
 2.236

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 9
CAH – Un exemple (2)

Cluster Dendrogram
D
10

8
D
8

6
Height
6

4
A
x2

4
C
4

3
B
2 1
A

2
2

1
4

5
0

3
0

0 2 4 6 8 10

x1 d
hclust (*, "ward.D2")

On distingue parfaitement les

étapes de l’algorithme

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 10
CAH – Un exemple (3) – Niveau d’agrégation

Distance entre (1) et (2,3)

Cluster Dendrogram
8

Coordonnées du groupe 56 3 4 

  5.5,  3.5 
(2,3) : centre de classe  2 2 
6
Height

C
4

2.9439
2

n1  n23
1

D2   d 2 (1,23)
4

n1  n23
0

Distance de Ward
entre (1) et (2,3) 1 2
  6.5  4.333
d
1 2
hclust (*, "ward.D2")

On obtient une hiérarchie indicée. Les niveaux

Remarque : Curieusement, le logiciel R (3.3.1) affiche
d’agrégation correspondent en général à l’indice
de dissimilarité entre les deux parties réunies. Height  2  D 2  2.9439

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 11
CAH – Un exemple (4) – Détails sous R

#vecteurs de données
x1 <- c(8,5,6,1,2)
x2 <- c(3,3,4,6,8)

#plot Cluster Dendrogram

plot(x1,x2,xlim=c(0,10),ylim=c(0,10))
text(x1-0.5,x2,1:5,cex=0.75)

8
6
Height
#distance entre individus

4
X <- data.frame(x1,x2)
d <- dist(X)

1
4

5
print(d)

3
#CAH d
cah <- hclust(d,method="ward.D2") hclust (*, "ward.D2")

plot(cah)

#hauteurs d'agrégation
print(cah$height)

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 12
CAH – Distance ultramétrique
Peut-il y avoir des inversions
dans le dendrogramme ? A toute hiérarchie indicée H correspond une
distance entre éléments de H : d(A, B), qui
Cluster Dendrogram est le niveau d’agrégation de A et B
8
6
Height

Elle possède une propriété supplémentaire

4

(propriété ultramétrique)
2

1
4

d ( A, B)  maxd ( A, C ), d ( B, C)
0

d
hclust (*, "ward.D2")

Matrice de distances entre individus

Ex. d(2,3) ≤ max {d(2,1), d(3,1)}

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 13
CAH – Distance entre individus Propriétés d’une distance
(il y en a d’autres…) • Symétrie : d(a,b) = d(b,a)
• Séparation : d(a,b) = 0  a = b
• Inégalité triangulaire : d(a,c) ≤ d(a,b) + d(b,c)

d (a, b)   x j (a)  x j (b) 

p
2 2
Distance euclidienne
j 1

Permet d’éliminer les problèmes

Distance euclidienne de différences d’échelles entre
x (a)  x (b)
p
1
d ( a, b)  
2 2
pondérée par l’inverse les variables. Peut être obtenue
j 1  j
2 j j
en appliquant la distance
de la variance
euclidienne sur données réduites.

a, b
Distance cosinus d (a, b)  1  cos(a, b)  1  Populaire en text mining lorsque les
ab
vecteurs individus comportent de
p

 x j (a)  x j (b)
nombreuses valeurs nulles (parce que
les textes sont de longueurs
j 1
 1 différentes).
 x 2j (a) 
j
 x 2j (b)
j

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 14
 CAH – Distance entre groupes
Matrice de
(il y en a d’autres…)
distances

C1
La distance entre deux groupes est comptabilisée à partir des deux éléments
qui sont le plus proches. Attention, effet de « chaîne » des groupes.
Saut minimum 5.0 C2
d (C1, C 2)  min d (a, b)
(single linkage) aC1,bC 2

La distance entre deux groupes est comptabilisée à partir des deux éléments qui
C1
sont les plus éloignés. Groupes compacts mais problème avec points atypiques.
7.81
Saut maximum d (C1, C 2)  max d (a, b)
aC1,bC 2 C2
(complete linkage)

La distance entre deux groupes est comptabilisée à partir de la distance

(pondérée) entre les barycentres. Privilégié souvent dans les logiciels. C1
G1
n1  n2 2 6.65
Distance de Ward d 2 (C1, C 2)  d (G1, G 2)
n1  n2 C2
 Ce critère maximise l’inertie inter-classes (à voir plus loin) G2
quand on utilise la distance euclidienne

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 15
CAH – Distance entre groupes
Matrice de
Exemple
distances

#CAH - single linkage

cah <- hclust(d,method="single") 5.000000

plot(cah) 2.236068

#hauteurs d'agrégation 2.236068

print(cah$height) 1.414214

#CAH - complete linkage

7.810250
cah <- hclust(d,method="complete")
plot(cah) 3.000000

2.236068
#hauteurs d'agrégation
print(cah$height) 1.414214

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 16
 La CAH fournit une hiérarchie de partitions imbriquées, et autant de
scénarios de solutions

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 17
Identification du « bon » nombre de classes
On peut le définir comme un paramètre (à
fixer) de l’algorithme (ex. K-Means)
Identifier le bon nombre de classes
est un problème « ouvert » en
On peut aussi tester différentes solutions et
classification automatique
utiliser des mesures insensibles au nombre
de classes pour trouver la meilleure
configuration (ex. indice silhouette)

La situation est différente avec la CAH.

Partition en 2 classes
Le dendrogramme décrit un ensemble
de partitions imbriquées cohérentes,
Partition en
qui sont autant de solutions
3 classes
potentielles

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 18
Ecarts entre paliers d’agrégations

2.5
Principe : Des fortes différences entre deux niveaux

2.0
d’agrégation successifs indique une modification

1.5
x2
« significative » de la structure des données lorsqu’on a

1.0
procédé au regroupement.

0.5
2 3 4 5 6 7

x1
Une solution en 2 groupes
est possible, une solution
en 3 groupes est Cluster Dendrogram

envisageable également.

10 12
8
Height

6
4
Remarque : La solution en 2 groupes apparaît

2
toujours comme « évidente » dans le

0
dendrogramme. Il faut savoir aller au-delà.
d
hclust (*, "ward.D2")
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 19
Inertie (1) L’inertie est un indicateur de dispersion. Elle
généralise la variance au cas multidimensionnel. 

d 2
( X ( ), G )
G représente le barycentre global.

Relation de Huygens : suite à une partition des observations, décomposition de l’inertie totale en inertie inter-
classes (expliquée par l’appartenance aux groupes) et inertie intra-classes (résiduelle, intrinsèque aux groupes).



d 2
( X (), G)   ng  d 2 (Gg , G)  d 2 ( X (), Gk )
g g g

T. Dispersion totale. B. Dispersion des centres de W. Dispersion à

groupes autour du centre global. l’intérieur des groupes.

Part d’inertie expliquée B R² = 0, il y a un seul groupe.

par la partition : R²  R² = 1, partition parfaite. Souvent
T partition triviale : 1 individu = 1 groupe.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 20
Inertie (2) – Critère de Ward n1  n2 2
 d (G1, G 2)
n1  n2

Chaque agrégation entraîne une diminution de l’inertie

inter-classes. On fusionnera donc les deux groupes
entraîne la plus petite valeur de Δ. Ils sont les plus
proches au sens du critère de Ward. Leur fusion
entraîne également la plus petite perte d’inertie.

On peut élaborer un graphique Les « coudes »

laissent entendre
qui met en relation la part
des changements
d’inertie expliquée (R²) en structures
significatifs dans les
fonction du nombre de groupes.
données.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 21
Nombre de classes – Intuition, interprétation

Au final, les techniques de visualisation et

l’interprétation des groupes donnent des
indications précieuses quant à l’identification du
nombre de groupes. Nous avons des scénarios de
solutions. Il faut aussi tenir compte du cahier des
charges de l’étude.

Partition en deux groupes. Partition en trois groupes.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 22
 Affectation d’un individu supplémentaire à un des groupes

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 23
Classement d’un individu supplémentaire

La démarche doit être cohérente avec la

distance et la stratégie d’agrégation utilisée. C1
G1
o
C2
« Single linkage » : « o » serait associé à
C2 à cause du point n°3 (vs. n°5 de C1) G2

« Complete linkage » : « o » serait associé

à C1 à cause du point n°4 (vs. n°1 de C2)

« Ward » : Il faut minimiser la quantité…

1 nc 2
o  d (o, G)
1  nc

… ce qui correspond approximativement à

une distance aux centres de classes

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 24
 Classification des données voitures

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 25
Données

Modele Prix Cylindree Puissance Poids Consommation

Daihatsu Cuore 11600 846 32 650 5,7
Suzuki Swift 1.0 GLS 12490 993 39 790 5,8
Fiat Panda Mambo L 10450 899 29 730 6,1 28 observations
VW Polo 1.4 60 17140 1390 44 955 6,5
Opel Corsa 1.2i Eco 14825 1195 33 895 6,8 5 variables actives, toutes
Subaru Vivio 4WD 13730 658 32 740 6,8
Toyota Corolla 19490 1331 55 1010 7,1 quantitatives
Opel Astra 1.6i 16V 25000 1597 74 1080 7,4
Peugeot 306 XS 108 22350 1761 74 1100 9
Renault Safrane 2.2. V 36600 2165 101 1500 11,7
Seat Ibiza 2.0 GTI 22500 1983 85 1075 9,5
VW Golt 2.0 GTI 31580 1984 85 1155 9,5
Citroen ZX Volcane 28750 1998 89 1140 8,8
Fiat Tempra 1.6 Liberty 22600 1580 65 1080 9,3
Fort Escort 1.4i PT 20300 1390 54 1110 8,6
Honda Civic J oker 1.4 19900 1396 66 1140 7,7
L’objectif est d’identifier des groupes
Volvo 850 2.5 39800 2435 106 1370 10,8 naturels de véhicules, et de comprendre
Ford Fiesta 1.2 Zetec 19740 1242 55 940 6,6
Hyundai Sonata 3000 38990 2972 107 1400 11,7 la nature de ces groupes (Remarque :
Lancia K 3.0 LS 50800 2958 150 1550 11,9
Mazda Hachtback V 36200 2497 122 1330 10,8 l’interprétation fait l’objet d’un autre
Mitsubishi Galant 31990 1998 66 1300 7,6
Opel Omega 2.5i V6 47700 2496 125 1670 11,3 support).
Peugeot 806 2.0 36950 1998 89 1560 10,8
Nissan Primera 2.0 26950 1997 92 1240 9,2
Seat Alhambra 2.0 36400 1984 85 1635 11,6
Toyota Previa salon 50900 2438 97 1800 12,8
Volvo 960 Kombi aut 49300 2473 125 1570 12,7

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 26
Logiciel R – Chargement et préparation des données
Les variables ne sont
clairement pas sur les
mêmes échelles

#charger les données

autos <- read.table("voitures_cah.txt",header=T,sep="\t",dec=".",row.names=1)

#vérification des données

print(summary(autos))

#graphiques
pairs(autos)

#centrage et surtout réduction

#pour éviter que les variables à forte variance
#« tirent » les résultats à eux
autos.cr <- scale(autos,center=T,scale=T)

#matrice des distances euclidiennes

#sur données centrées et réduites
d <- dist(autos.cr) Les variables sont fortement corrélées entre elles.
On distingue un peu des groupes déjà.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 27
Logiciel R
La fonction hclust() de « stats »

#cah - critère de ward

cah <- hclust(d,method="ward.D2")
plot(cah,hang=-1,cex=0.75)

#mise en évidence des 3 groupes

rect.hclust(cah,k=3)

#découpage en 3 groupes
p <- cutree(cah,k=3)
print(p)

Un indicateur du groupe d’appartenance permet

de réaliser tous les calculs en aval. Notamment,
ceux utiles à l’interprétation des groupes.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 28
Python
Manipulation des données

#modification du dossier par défaut

import os
os.chdir("...")

#chargement des données

import pandas
autos = pandas.read_table("voitures_cah.txt",sep="\t",header=0,index_col=0)

#stat. descriptives
print(autos.describe())

#graphique, croisement deux à deux

from pandas.tools.plotting import scatter_matrix
scatter_matrix(autos,figsize=(5,5))

#centrage-réduction des variables

from sklearn import preprocessing
autos_cr = preprocessing.scale(autos)

Même chose que sous R, on dispose en sus de la

distribution unidimensionnelle de chaque variable.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 29
Python - Package SciPy
#librairie pour la CAH
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster

#construction de la typologie
Z = linkage(autos_cr,method='ward',metric='euclidean')

#affichage du dendrogramme
plt.title("CAH")
dendrogram(Z,labels=autos.index,orientation='top',color_threshold=0,leaf_rotation=90)
plt.show()

#et matérialisation des 3 classes (hauteur de coupure height = 5)

plt.title('CAH avec matérialisation des 3 classes')
dendrogram(Z,labels=autos.index,orientation='top',color_threshold=5,leaf_rotation=90)
plt.show()

#découpage à la hauteur = 5 ==> 3 identifiants de groupes obtenus

groupes_cah = fcluster(Z,t=5,criterion='distance')
print(groupes_cah)

#index triés des groupes

import numpy as np
idg = np.argsort(groupes_cah)
L’algorithme est déterministe,
#affichage des observations et leurs groupes nous avons exactement les
print(pandas.DataFrame(autos.index[idg],groupes_cah[idg])) mêmes résultats que sous R.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 30
Tanagra
L’outil HAC peut réduire automatiquement
ou non les variables ; le nombre de groupes
peut être détecté (basé sur les écarts de
niveaux d’agrégation, en ignorant la
solution à 2 classes) ; seule méthode de
Ward est disponible ; possibilité de
classement des individus supplémentaires.

L’outil de caractérisation des

classes guide l’interprétation.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 31
 Classification Ascendante Hiérarchique sur Composantes Principales

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 32
Tandem analysis – Principe et intérêt

Réaliser une analyse factorielle sur les données (ex. ACP)

Principe Lancer la CAH à partir des premiers axes factoriels « pertinents »
Il ne faut plus réduire les axes dans ce cas : variance axe = son importance

Quel 1. La distance euclidienne considère implicitement que les

d 2 (a, b)   x j (a)  x j (b) 
p
2

intérêt ? variables ne sont pas liées, ce qui est faux. En utilisant les j 1

axes qui sont par définition orthogonaux deux à deux, la

distance euclidienne devient parfaitement adaptée
2. On procède à un nettoyage des données en ne
considérant que les premiers axes porteurs d’information,
et en laissant de côté les derniers axes correspondant à
des fluctuations d’échantillonnage (du bruit)
3. L’approche permet d’ appliquer la CAH même lorsque les
variables actives ne sont pas toutes quantitatives (ACM si
toutes qualitatives, AFDM si mélange quanti-quali)

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 33
Tandem analysis – Un exemple On conserve malgré tout 2
facteurs pour la visualisation.
#acp normée
acp <- princomp(autos,cor=T,scores=T)
screeplot(acp)
#distance sur les 2 premiers axes
dacp <- dist(acp$scores[,1:2])
#cah
cah.acp <- hclust(dacp)
plot(cah.acp,hang=-1,cex=0.75)
#découpage en 3 groupes
p.acp <- cutree(cah.acp,k=3)
#matérialisation dans le plan factoriel
plot(acp$scores[,1],acp$scores[,2],type="n",xlim=c(-4.5,4.5),ylim=c(-4.5,4.5),xlab="92.56 %",ylab="4.10 %")
text(acp$scores[,1],acp$scores[,2],labels=rownames(autos),col=c("red","green","blue")[p.acp],cex=0.5)

On retrouve les On comprend la nature du

mêmes résultats que regroupement avec la
précédemment. visualisation.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 34
« Tandem Analysis » n’est pas la panacée

Attention, ne retenir que les axes « significatifs » peut

masquer la structuration des données en groupes.

Visuellement, les deux groupes sont évidents.

Le premier axe factoriel porte 97% de

l’information, personne n’aurait l’idée de
retenir le second axe.

Projetés sur le premier axe, les individus des

deux groupes sont indiscernables.

 Faire des graphiques encore et toujours

pour vérifier ce que nous propose le calcul !!!

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 35
 Traitement des grands ensembles de données

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 36
Classification mixte - Principe

La CAH nécessite le calcul des distances entre individus pris deux à deux. Il
Problème nécessite également l’accès à cette matrice à chaque agrégation. Infaisable
sur des grands ensembles de données (en nombre d’observations).

Réaliser un pré-regroupement (ex. en 50 classes) à l’aide de méthodes

Démarche
adaptées (ex. k-means, cartes de Kohonen), démarrer la CAH à partir des pre-
clusters.

Pouvoir traiter des très grandes bases, tout en bénéficiant des avantages de la
Intérêt
CAH (hiérarchie de partitions imbriquées, dendrogramme pour la
compréhension et l’identification des classes).

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 37
Classification mixte – Un exemple 500.000 observations, 68 variables
Core 2 Duo 9400 – 2.53 Ghz – Windows 7 – 4 Go RAM Lancer une CAH directement
dessus est insensé.
Chargement des données : 10 sec.

K-means (50 groupes) : 6 mn 40 sec.

CAH à partir des 50

groupes : 5 sec.

Les solutions alternatives

sont : regroupements en
2, 3 ou 5 groupes.

Voir détails dans « Traitement de gros volumes – CAH Mixte », oct. 2008.
Contient du code R pour la réalisation de la même analyse sous R.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 38
Bilan
Principe :
• Calculer la dissimilarité entre les individus
• Agglomérations successives en fusionnant en priorité les groupes
les plus proches (cf. stratégies d’agrégation : saut minimum,
méthode de WARD, etc.)
• Hauteur = Distance entre groupes

Avantages
• Hiérarchie de partition (taxonomie)
• Indications sur la proximité entre groupes (choix du nombre de
groupes  très difficile, il n’y a pas de solution « optimale »)
• Propose des solutions alternatives (que l’on peut interpréter ou
approfondir)

Inconvénients
• Mise en œuvre sur des grandes bases (cf. stratégies mixtes)

Problèmes récurrents de la classification

• Détection du « bon » nombre de groupes La représentation en
• Interprétation des groupes (avec ou non des variables illustratives) dendrogramme des alternatives
• Classement d’un nouvel individu de solutions est très séduisante.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 39
Bibliographie
Ouvrages
Chandon J.L., Pinson S., « Analyse typologique – Théorie et applications », Masson, 1981.
Diday E., Lemaire J., Pouget J., Testu F., « Eléments d’analyse de données », Dunod, 1982.
L. Lebart, A. Morineau, M. Piron – « Statistique exploratoire multidimensionnelle », DUNOD, 2004.
Saporta G, « Probabilités, analyse des données et statistique », Technip, 2011.

Tutoriels
« Classification automatique sous R », octobre 2015.
« Classification automatique sous Python », mars 2016.

« Classification automatique sur données mixtes », novembre 2013.

« Classification automatique – Déploiement de modèles », octobre 2008.
« Traitement de gros volumes – CAH Mixte », octobre 2008.
« La complémentarité CAH et ACP », mars 2008.

Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/ 40