Chapitre 4 Techniques de classification
Data Mining
Classification = segmentation = clustering
C’est la méthode la plus répandue des techniques descriptives de DM utilisée si on fait face à
un grand volume de données où on cherche à distinguer des sous ensembles homogènes prêts à
l’analyse de données.
Définition
C’est un opération statistique qui consiste à regrouper les objets (variables) en un nombre limité
de classes ( segments , clusters) possédant les propriétés suivantes :
- Elles ne sont pas prédéfinies par l’analyste mais découvertes au cours de l’opération.
- Ces classes de classification regroupent les objets ayant les caractéristiques similaires
et séparent les objets ayant des caractéristiques différentes ( homogénéité interne et
hétérogénéité externe) .
Domaine d’application :
Le marketing, le secteur commercial, le domaine médical , la sociologie ….
Soit n objets à classer , selon Bell , le nombre de partitions possibles est
1
Bn =
𝑒
∑ 𝑘𝑛
∞
𝑘:0
𝑘!
Exemple
Soit l’ensemble (a,b,c,d)
Les différentes classifications sont les suivantes :
- Une classe : (abcd)
- Deux classes : (ab, cd) ; (ad,cb) ; (ac, bd) ; (a,b cd) ; (b,acd); (c,abd); (d,abc) .
- Trois classes: (ab,c,d) ; (ad,b,c) ; (ad,b,c); (ac,b,d);
- Quatre classes: (a,b,c,d).
1 MOME 2 2021-2022
Data Mining
Inputs :
- Une matrice rectangulaire dont les lignes sont les individus et les colonnes sont les
variables.
- Une matrice carrée de similarités respectant des distances entre les individus ou entre
les variables.⟹
Distance euclidienne = ∑(𝑥𝑖 − 𝑦𝑖)2 ; Distance Manhattan = ∑|𝑥𝑖 − 𝑦𝑖|
Outputs :
2 classes sont disjointes : méthodes de partitionnement : classification par agrégation de
similarités
Méthodes :
-Centres mobiles ; k-means, nuées dynamiques.
-k-medoids , k*modes ; k-prototypes.
-réseau
de
Kohonen.
2 classes sont disjointes ou l’une contient l’autre ‘méthode hiérarchique ascendante » :
agglomérat
ives
(basée sur
la notion de distance ou de densité)
. méthode
Publicité
hiérarchique descendante ‘divisives’.
2 classes peuvent avoir plusieurs objets en commun ( classes empiétantes’ ou recouvrantes ‘⇌
⇒ analyse floue : dans laquelle chaque objet a un certaine probabilité d’appartenir à une classe
donnée.
Méthodologie :
La détermination du nombre optimal de classes dépend de la méthode utilisée :
Si on utilise les centres mobiles et les variantes ⇒ choix arbitraire : on fixe à priori le
nombre.
S’il s’agit d’une classification par agrégation de similarités : les logiciels déterminent
automatiquement le nombre optimal de classes.
Evaluation de la qualité de classification
On veut avoir une classification facile à comprendre.
2 MOME 2 2021-2022
Data Mining
Interprétation :
Etablir un arbre de décision après avoir déterminé la classification en prenant pour variable
cible de l’arbre le numéro de la classe ( et pour variable explicative celles qui sont intervenues
dans la classification ) . Si l’arbre de décision est imprécis , alors il faut recourir à une régression
logistique multinomiale .
On peut aussi pour chaque classe définir une variable qualitative indicatrice de cette classe égale
1 pour les individus de cette classe et égale zéro pour les autres individus . ⇒ le nombre de
variables indicatrices = nombre de classes.
On peut alors pour chaque variable explicative mesurer l’intensité de sa liaison avec chaque
indicatrice de classe Test de la variance si la variable explicative est continue.
Test de 𝜒2 si la variable explicative est qualitative .
Si la variable explicative est continue découpée en classe ou qualitative : on procède à une
classification de variables portant sur les indicatrices de modalités des variables de
classification et les indicatrices de classes prédéfinies.
Les critères de bonne classification :
Une bonne classification ⇒
Détecter les structures présentes dans les données
Permet de déterminer le nombre optimal de classes
Fournir des classes bien différenciées
Fournir des classes stables vis-à-vis de légères modifications de données.
Traiter efficacement les grands volumes de données
Traiter tous les types de variables (quantitatives et qualitatives)
Inertie interclasse et intraclasse
Inertie totale : ∑ 𝑝𝑖 (𝑥𝑖 − 𝑥̅)2
Inertie d’une classe = ∑ 𝑝𝑖 (𝑥𝑖 − 𝑥̅𝑗)2
Si la population est observée en K classes d’inertie I1, I2, ……IK
𝐾
L’inertie intra classe IA = ∑ 𝐼𝑗
𝑗:1
Une classe est plus homogène si son inertie est plus faible .
La classification de la population est meilleure si IA est petite.
3 MOME 2 2021-2022
Data Mining
L’inertie interclasse IR de la classification : ∑
𝑗é𝑚𝑒𝑐𝑙𝑎𝑠𝑠𝑒
∑
𝑖∈𝐼𝑗
𝑝𝑖
(𝑥̅𝑗 − 𝑥̅)2
Publicité
La moyenne pondérée pour la somme des poids de chaque classe 𝑝𝑖 des carrés des distances
des barycentres de chaque classe du barycentre global .
+ IR est grande , plus les classes sont séparées les unes des autres ⟹ bonne classification
Il y a alors 2 critères de bonne classification :
IR grande et IA petite ⇒ formule de Huygens
I = IR + IA
∑ 𝑝𝑖 (𝑥𝑖 − 𝑥̅)2 = ∑
𝑗é𝑚𝑒𝑐𝑙𝑎𝑠𝑠𝑒
∑
𝑖∈𝐼𝑗
𝑝𝑖
(𝑥𝑖 − 𝑥̅𝑗)2
+ ∑ ∑ 𝑝𝑖 (𝑥̅𝑗 − 𝑥̅)2
Méthode de centres mobiles
Les différentes étapes sont :
1. On choisit k individus comme centres initiaux des classes ( on tire au hasard ou on prend
k premiers ).
2. On calcule les distances entre chaque individu et chaque centre Ci.
3. On remplace les k centres Ci par les barycentres des k classes définies précédemment.
4. On regarde si les entres sont restés suffisamment stables ( en comparant leur
déplacement aux distances entre entres initiaux ) ou si un nombre fixé d’opérations a
été atteint : Si oui , on arrête
Si non , on revient à l’étape 2.
Application
Soit l'ensemble D des entiers suivants : D= { 2, 5, 8, 10, 11, 18, 20 } On veut répartir les données
de D en trois (3) clusters, en utilisant l'algorithme K-means.
La distance d entre deux nombres a et b est calculée ainsi : d(a , b) = |a - b|
1/ Appliquez K-means en choisissant comme centres initiaux des 3 clusters respectivement : 8,
10 et 11.
Initialisation : des centres de gravité : µ1=8 µ2=10 µ3=11 des clusters :
C1=Ø C2=Ø C3=Ø
Itération 1 : Calcul des distances
4 MOME 2 2021-2022
Data Mining
Nombre 2 : d(2, µ1)=|2-8|=6
d(2, µ2)=|2-10|=8
d(2, µ3)=|2-11|=9
2 est affecté au cluster C1.
Nombre 5 : d(5, µ1)=|5-8|=3
d(5, µ2)=|5-10|=5
d(5, µ3)=|5-11|=6
5 est affecté au cluster C1.
Nombre 8 : d(8, µ1)=|8-8|=0
d(8, µ2)=|8-10|=2
d(8, µ3)=|8-11|=3
8 est affecté au cluster C1.
Nombre 10 : d(10, µ1)=|10-8|=2
d(10, µ2)=|10-10|=0
d(10, µ3)=|10-11|=1
10 est affecté au cluster C2.
Nombre 11 : d(11, µ1)=|11-8|=3
d(11, µ2)=|11-10|=1
d(11, µ3)=|11-11|=0
Publicité
11 est affecté au cluster C3.
Nombre 18 : d(18, µ1)=|18-8|=10
d(18, µ2)=|18-10|=8
d(18, µ3)=|18-11|=7
18 est affecté au cluster C3.
5 MOME 2 2021-2022
Data Mining
Nombre 20 : d(20, µ1)=|20-8|=12
d(20, µ2)=|20-10|=10
d(20, µ3)=|20-11|=9
20 est affecté au cluster C3.
Mise à jour des clusters : C1={ 2, 5, 8} C2={10} C3={11, 18, 20}
Estimation des centres de gravité :
µ1= (2+5+8)/3 =5 ; µ2=10/1= 10 µ3=(11+18+20)/3 =16.33
Itération 2 : Calcul des distances
Nombre 2 : d(2, µ1)=|2-5|=3
d(2, µ2)=|2-10|=8
d(2, µ3)=|2-16.33|=14.33
2 est affecté au cluster C1.
Nombre 5 : 3/9 d(5, µ1)=|5-5|=0
d(5, µ2)=|5-10|=5
d(5, µ3)=|5-16.33|=11.33
5 est affecté au cluster C1.
Nombre 8 : d(8, µ1)=|8-5|=3
d(8, µ2)=|8-10|=2
d(8, µ3)=|8-16.33|=8.33
8 est affecté au cluster C2.
Nombre 10 : d(10, µ1)=|10-5|=5
d(10, µ2)=|10-10|=0
d(10, µ3)=|10-16.33|=6.33
10 est affecté au cluster C2.
6 MOME 2 2021-2022
Data Mining
Nombre 11 : d(11, µ1)=|11-5|=6
d(11, µ2)=|11-10|=1
d(11, µ3)=|11-16.33|=5.33
11 est affecté au cluster C2.
Nombre 18 : d(18, µ1)=|18-5|=13
d(18, µ2)=|18-10|=8
d(18, µ3)=|18-16.33|=1.67
18 est affecté au cluster C3.
Nombre 20 : d(20, µ1)=|20-5|=15
d(20, µ2)=|20-10|=10
d(20, µ3)=|20-16.33|=3.67
20 est affecté au cluster C3.
Mise à jour des clusters : C1={ 2, 5} C2={8, 10, 11} C3={18, 20}
estimation des centres de gravité :
µ1= (2+5)/2 = 3.5 ; µ2=(8+10+11)/3 = 9.66 ; µ3=(18+20)/2 =19
Itération 3 :
Calcul des distances
Nombre 2 : d(2, µ1)=|2-3.5|=1.5
d(2, µ2)=|2-9.66|=7.66
d(2, µ3)=|2-19|=17
Publicité
2 est affecté au cluster C1.
Nombre 5 : d(5, µ1)=|5-3.5|=1.5
d(5, µ2)=|5-9.66|=4.66
d(5, µ3)=|5-19|=14 5 est affecté au cluster C1.
7 MOME 2 2021-2022
Data Mining
Nombre 8 : d(8, µ1)=|8-3.5|=4.5
d(8, µ2)=|8-9.66|=1.66
d(8, µ3)=|8-19|=11 8 est affecté au cluster C2.
Nombre 10 : d(10, µ1)=|10-3.5|=6.5
d(10, µ2)=|10-9.66|=0.34
d(10, µ3)=|10-19|=9 10 est affecté au cluster C2.
Nombre 11 : d(11, µ1)=|11-3.5|=7.5
d(11, µ2)=|11-9.66|=1.34
d(11, µ3)=|11-19|=8
11 est affecté au cluster C2.
Nombre 18 : d(18, µ1)=|18-3.5|=14.5
d(18, µ2)=|18-9.66|=8.34 d(18, µ3)=|18-19|=1
18 est affecté au cluster C3.
Nombre 20 : d(20, µ1)=|20-3.5|=16.5
d(20, µ2)=|20-9.66|=10.34
d(20, µ3)=|20-19|=1
20 est affecté au cluster C3.
Mise à jour des clusters : C1={ 2, 5} C2={8, 10, 11} C3={18, 20}
Estimation des centres de gravité :
µ1= (2+5)/2 = 3.5 µ2=(8+10+11)/3= 9.66 µ3=(18+20)/2 =19
Stabilité : Les centres de gravité n'ont pas changé. L'algorithme s'arrête
2- le résultat final : Les clusters résultats : C1={ 2, 5} C2={8, 10, 11} C3={18, 20}
Nombre d'itérations =3
8 MOME 2 2021-2022
Classification selon l’ACP
Axe 1
Data Mining
+ -
Axe 2 axe 2
+ - + -
17 22 31
Genre : Xi = 1 s il s agit d un homme
= 0 femme
Genre
H f
Age age
C1 c2 c3 c4 c5
Rayon rayon rayon ……..
R1 R2 R3 R4 R5 R6
Fréquence
F1 F2 F3 F4 F5
9 MOME 2 2021-2022