DATA MINING
LA SEGMENTATION
CLUSTERING
Mohamed Heny SELMI – Wiem Trabelsi
[Link]@[Link]
Data Mining-4INFINI © ESPRIT2022-2023
TYPES D’APPLICATIONS
Techniques Techniques
Non Supervisées Supervisées
Selon la catégorie des
Pas de variables cibles variables cibles
Discrimination
Clustering Prédiction
Scoring
Classification Automatique Variable « cible » qualitative Variable « cible » quantitative
Visualisation
Analyse spatiale Classement
Variable « cible » qualitative
Association
Analyse du chariot
Data Mining-4GL-TWIN © ESPRIT2020-2021
DEUX FAMILLES DE TECHNIQUES
Méthodes Méthodes
Non Supervisées Supervisées
Analyse en Composantes
Principales Arbres de Décisions
ACP
Méthodes des Centres Analyse Linéaire Discriminante
Mobiles
K-means
Régression Linéaire
Classification Ascendante
Hiérarchique
CAH
Régression Logistique
Règles
Associatives
Réseaux de Neurones
Séparateur à Vaste Marge
SVM
Data Mining-4GL-TWIN © ESPRIT2020-2021
UTILITÉ DE LA SEGMENTATION
Banque / Assurance
• Catégoriser la clientèle : chercher un profil qui représente les membres de
chaque classe
• Regrouper les clients selon des critères et caractéristiques communs : cibler
« les mailing »
Médecine
•Déterminer des segments de patients susceptibles d’être soumis à des protocoles
thérapeutiques déterminés, chaque segment regroupant tous les patients réagissant
identiquement
•Retrouver les différents comportements similaires
Biologie – Zoologie – Ethologie – Sciences humaines
•Expliquer les relations entre espèces, races, genres, familles,
•Retrouver de nouvelles répartitions
- Profiling
- Analyse sémantique, sentimentale,
- Analyse et mesure de la tonalité d’un contenu textuel
- Catégorisation des concepts ou des entités nommés
- Construction d’agrégateur synthétique à partir des flux d’actualités
Data Mining-4GL-TWIN © ESPRIT2020-2021
PROBLÉMATIQUE
1 2 3 4
5 7 9
6 8
10 12
11 13
14 16 18
15 17
Data Mining-4GL-TWIN © ESPRIT2020-2021
age race coul taille sexe post Nbre type Taille
eur ure chie de
n l’ima
ge
I1 0
Data Mining-4GL-TWIN © ESPRIT2020-2021
PROBLÉMATIQUE
Y = autre combinaison unique de ttes les vbles descriptives
How many clusters?
X = combinaison unique de ttes les vbles descriptives
Data Mining-4GL-TWIN © ESPRIT2020-2021
PROBLÉMATIQUE
How many clusters? Six Clusters
Two Clusters Four Clusters
Data Mining-4GL-TWIN © ESPRIT2020-2021
IDÉE DE BASE DE LA SEGMENTATION
Deux individus se ressemblent le plus
SI
les points qui les représentent dans le
nuage de points sont les plus proches
Nécessité d’une métrique de la distance
Distance Euclidienne
Distance de Mahalanobis
Distance de Manhattan
Distance de Ward
….
Data Mining-4GL-TWIN © ESPRIT2020-2021
IDÉE DE BASE DE LA SEGMENTATION
Deux individus se ressemblent le plus
1 SI
les points qui les représentent dans le
nuage de points sont les plus proches
Nécessité d’une métrique de la distance
Distance Euclidienne
Distance de Mahalanobis
Distance de Manhattan
Distance de Ward
…..
3 Un critère d’évaluation d’une classification
2
Itot= Iinter + Iintra
Data Mining-4GL-TWIN © ESPRIT2020-2021
MÉTHODOLOGIES
Partitionnement Hiérarchique
Kmeans CAH
Data Mining-4GL-TWIN © ESPRIT2020-2021
K-MEANS
MÉTHODE DES CENTRES MOBILES
Data Mining-4GL-TWIN © ESPRIT2020-2021
PRÉSENTATION DU K-MEANS
L’algorithme des K-moyennes est un algorithme qui permet de trouver des
classes dans des données.
les classes qu’il construit n’entretiennent jamais de relations hiérarchiques:
une classe n’est jamais incluse dans une autre classe.
L’algorithme fonctionne en précisant le nombre de classes attendues.
L’algorithme calcule les distances Intra-Classe et Inter-Classe.
Il opère sur des variables continues.
Data Mining-4GL-TWIN © ESPRIT2020-2021
PRINCIPE ALGORITHMIQUE
Algorithme K-Means
Entrée : k le nombre de groupes cherchés
DEBUT
Choisir aléatoirement les centres des groupes
REPETER
i. Affecter chaque cas au groupe dont il est le plus proche au son centre
ii. Recalculer le centre de chaque groupe
JUSQU‘A (stabilisation des centres)
OU (nombre d'itérations =t)
OU (stabilisation de l’inertie totale de la population)
FIN
Data Mining-4GL-TWIN © ESPRIT2020-2021
STABILISATION DE L’INERTIE
TOTALE DE LA POPULATION
Inertie totale Itot : somme de l’inertie intraclasse IA et de l’inertie
interclasse IC
Itot= I + Ic
A
Inertie intraclasse IA : somme des inerties totales de chaque classe
Inertie interclasse Ic : moyenne (pondérée par la somme des poids de
chaque classe) des carrés des distances des barycentres de chaque classe
au barycentre global
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 1
Choisir 3
Centres de
classes
(au hasard)
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 1
k1
Y
k2
Choisir 3
Centres de
classes
(au hasard)
k3
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 2
k1
Y
k2
Affecter chaque
point à la classe
dont le centre est
le plus proche
k3
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 3
k1 k1
Y
k2
k3
Déplacer chaque k2
centre de classe vers
la moyenne de chaque
classe
k3
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 4
k1
Y
k3
Réaffecter les points k2
qui sont plus proches
du centre d'une autre
classe
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 5
k1
Y
les trois points
qui changent de k3
classe k2
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 6
k1
Y
k3
k2
Re-calculer les
moyennes des classes
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU K-MEANS 7
k1
Y
k2
k3
Déplacer les
centres des classes
vers les moyennes
X
Data Mining-4GL-TWIN © ESPRIT2020-2021
ILLUSTRATION K-MEANS
Soit le tableau1 de 7 individus
caractérisés par 2 variables. Tab.1
On souhaite construire deux groupes
homogènes à partir de ces individus.
On propose de commencer
la construction à partir des deux
groupes du tableau 2.
Continuer la construction des groupes Tab.1
en utilisant la distance euclidienne
pour mesurer la similarité entre
individus.
d(i, j) = (| xi1 x j1 |2 + | xi 2 x j 2 |2 +...+ | xip x jp |2 )
Tab.2
Data Mining-4GL-TWIN © ESPRIT2020-2021
ILLUSTRATION K-MEANS 1
Soit le tableau1 de 7 individus
caractérisés par 2 variables. Tab.1
On souhaite construire deux groupes
homogènes à partir de ces individus.
On propose de commencer
la construction à partir des deux
groupes du tableau 2.
Continuer la construction des groupes
en utilisant la distance euclidienne
pour mesurer la similarité entre
individus.
d(i, j) = (| xi1 x j1 |2 + | xi 2 x j 2 |2 +...+ | xip x jp |2 )
Data Mining-4GL-TWIN © ESPRIT2020-2021
ILLUSTRATION K-MEANS 2
Soit le tableau1 de 7 individus
caractérisés par 2 variables.
On souhaite construire deux groupes
homogènes à partir de ces individus.
On propose de commencer
la construction à partir des deux
groupes du tableau 2.
Continuer la construction des groupes
en utilisant la distance euclidienne
pour mesurer la similarité entre
individus.
d(i, j) = (| xi1 x j1 |2 + | xi 2 x j 2 |2 +...+ | xip x jp |2 )
Data Mining-4GL-TWIN © ESPRIT2020-2021
POINTS FAIBLES DE K-MEANS
Original Points K-means (2 Clusters)
Data Mining-4GL-TWIN © ESPRIT2020-2021
POINTS FAIBLES DE K-MEANS
Le choix du nombre de groupes est subjectif dans le cas où le nombre de
classes est inconnu au sein de l’échantillon.
L'algorithme du K-Means ne trouve pas nécessairement la configuration
optimale correspondant à la fonction objective minimale.
Les résultats de l'algorithme du K-Means sont sensibles à l'initialisation
aléatoires des centres.
Data Mining-4GL-TWIN © ESPRIT2020-2021
CAH
CLASSIFICATION ASCENDANTE HIÉRARCHIQUE
Data Mining-4GL-TWIN © ESPRIT2020-2021
PRINCIPE ALGORITHMIQUE
i. Créer à chaque étape une partition obtenue en agrégeant 2 à 2 les éléments
les plus proches ! -- Eléments : individus ou groupe d’individus
ii. L’algorithme fournit une hiérarchie de partitions : arbre contenant
l’historique de la classification et permettant de retrouver n-1 partitions.
iii. Nécessité de se munir d’une métrique (distance euclidienne, chi2, Ward…)
iv. Nécessité de fixer une règle pour agréger un individu et un groupe
d’individus (ou bien 2 groupes d’individus)
Data Mining-4GL-TWIN © ESPRIT2020-2021
I1 I2 I3 I4 I5
I1 D(I1,i1) = 0 D(I1,I2)
I2 D(i2,i1)
I3
I4
I5
Nbre de distance = (25 – 5)/2
Data Mining-4GL-TWIN © ESPRIT2020-2021
LE DENDROGRAMME
Durant les étapes d’un algorithme de classification hiérarchique, on est en train de construire
un dendrogramme.
Le dendrogramme indique les objets et classes qui ont été fusionnés à chaque itération.
Le dendrogramme indique aussi la valeur du critère choisi pour chaque partition rencontrée.
1. Il donne un résumé de la classification hiérarchique
2. Chaque palier correspond à une fusion de classes
3. Le niveau d’un palier donne une indication sur la qualité de la fusion correspondante
4. Toute coupure horizontale correspond à une partition
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 1
n individus / n classes
3
2
4
On construit la matrice de distance entre les n éléments
et on regroupe les 2 éléments les plus proches
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 2
n -1 classes
3
2
4
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 3
3
2
4
5
1 2
Comment mesurer la distance entre une classe et un élément individuel ?
Critères des centres de gravité, de la distance minimale, maximale, critère de Ward…
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 4
n -2 classes
1
3
2
4
5
1 2 3 4
Comment mesurer la distance entre une classe et un élément individuel ?
Critères des centres de gravité, de la distance minimale, maximale, critère de Ward…
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 5
3
2
4
5
n -3 classes
1 2 3 4 5
Comment mesurer la distance entre une classe et un élément individuel ?
Critères des centres de gravité, de la distance minimale, maximale, critère de Ward…
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DU CAH 6
3
2
4
n -4 classes
5
1 2 3 4 5
Comment mesurer la distance entre une classe et un élément individuel ?
Critères des centres de gravité, de la distance minimale, maximale, critère de Ward…
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DES CLASSES
2 classes
1
3
2
4
5
1 2 3 4 5
classes1 classes2
Data Mining-4GL-TWIN © ESPRIT2020-2021
SIMULATION DES CLASSES
1 3 classes
3
2
4
5
1 2 3 4 5
classes1 classes2 classes3
Data Mining-4GL-TWIN © ESPRIT2020-2021
EXEMPLE DE DENDROGRAMME
On « coupe » l'arbre là où les branches sont longues
À un niveau de 5, il ne reste que 2 classes
5
3
Si on fixe un niveau de 3 (si on exige une distance
d’au moins 3 entre objets de classes différentes),
2
il y a 4 classes
Data Mining-4GL-TWIN © ESPRIT2020-2021
EXEMPLE DE DENDROGRAMME
la hauteur d’une branche est proportionnelle à la perte d’inertie interclasse
6
À un niveau de 5, il ne reste que 2 classes
5
3
Si on fixe un niveau de 3 (si on exige une distance
d’au moins 3 entre objets de classes différentes),
2
il y a 4 classes
Data Mining-4GL-TWIN © ESPRIT2020-2021
DENDROGRAMME -> CLUSTERS ?
5
1
3
5 0.2
2 1 0.15
2 3 6 0.1
0.05
4
4 0
3 6 2 5 4 1
Nested Clusters Dendrogram
Data Mining-4GL-TWIN © ESPRIT2020-2021
APPLICATION PRATIQUE
SIMULATION
KMEANS ET CAH
SUR R
Data Mining-4GL-TWIN © ESPRIT2020-2021
APPLICATION K-MEANS « IRIS »
Etudier la qualité des résultats de K-means dans la construction de groupes de fleurs
selon leurs caractéristiques.
> iris
Data Mining-4GL-TWIN © ESPRIT2020-2021
APPLICATION K-MEANS « IRIS »
> iris_for_kmeans<-iris[,1:4] > km <- kmeans(iris_for_kmeans, 3)
Data Mining-4GL-TWIN © ESPRIT2020-2021
APPLICATION K-MEANS « IRIS »
> plot(iris[,1], iris[,2], col=km$cluster)
> points(km$centers[,c(1,)], col=1:3, pch=8, cex=2)
> table(km$cluster, iris$Species)
setosa versicolor virginica
1 0 48 14
2 50 0 0
3 0 2 36
setosa versicolor virginica
Taux de
classification
100% 96% 72%
% individus
« mal classés » 0% 4% 28%
10,67 %
Data Mining-4GL-TWIN © ESPRIT2020-2021
CAH SUR IRIS
Application de la CAH sur la base IRIS en utilisant la distance
euclidienne et les 4 variables de longueur et largeur des pétales et
des sépales.
1. Calcul de la matrice des distances sur les colonnes de 1 à 4
> d_euc = dist(iris[,1:4], method = 'euc’)
2. Application de la fonction hclust
> hc = hclust(d_euc,method ='ave')
> plot (hc)
3. Extraire – à partir du dendrogramme – la classification en 3
groupes :
> classe<-cutree(hc,3)
Data Mining-4GL-TWIN © ESPRIT2020-2021
Height
0 1 2 3 4
15
16 42
33
34
37
21
32
44
24
27
38
505 36
8
40
28
29
41
18
1 45
6
19
17
Data Mining-4GL-TWIN © ESPRIT2020-2021
11
49
4 7
20
22 23
14
943
39 12
25 7
13
46 2
26
10
35
30
31 3
48
129 1405
133104 112
117
138
111
148
113
140
142
146116
137
149
121 125101
144
141
145 109
118 135
110
106 132
119
d_euc
123
108 136
131 103
126
130
9961
58
94
66
hclust (*, "average")
76559578
77
87
51
53
Cluster Dendrogram
52 86
7957
74
64
9275
98 72
69
88 120
122
114 115
102
143 150
128
139 71
124147
12784
13473
83 63 107
936862
95
100
89
96
9767
8556
9165
54 8060
90
70
81
82
CAH SUR IRIS
Application de la CAH sur la base IRIS en utilisant la distance
euclidienne et les 4 variables de longueur et largeur des pétales et
des sépales.
1. Calcul de la matrice des distances sur les colonnes de 1 à 4
> d_euc = dist(iris[,1:4], method = 'euc’)
2. Application de la fonction hclust
> hc = hclust(d_euc,method ='ave')
> plot (hc)
3. Extraire – à partir du dendrogramme – la classification en 3
groupes :
> classe<-cutree(hc,3)
Data Mining-4GL-TWIN © ESPRIT2020-2021
APPLICATION CAH « IRIS »
> table(classe , iris$Species)
setosa versicolor virginica setosa versicolor virginica
1 0 50 14 1 0 48 14
2 50 0 0 2 50 0 0
3 0 0 36 3 0 2 36
setosa versicolor virginica setosa versicolor virginica
Taux de Taux de
classification
100% 100% 72% classification
100% 96% 72%
% individus % individus
« mal classés » 0% 0% 28% « mal classés » 0% 4% 28%
9,33 % 10,67 %
CAH Kmeans
Data Mining-4GL-TWIN © ESPRIT2020-2021
AVANTAGES DE LA CAH
Permet de classer : des individus, des variables, des moyennes de classes
obtenues en sortie d’un algorithme des centres mobiles.
si on classe des moyennes, on améliore les résultats si on connaît non
seulement les moyennes des classes, mais aussi les inerties intraclasse et les
effectifs des classes.
S’adapte aux diverses formes de classes, par le choix de la distance.
Permet de choisir le nombre de classes de façon optimale, grâce à des
indicateurs de qualité de la classification en fonction du nombre de classes.
Data Mining-4GL-TWIN © ESPRIT2020-2021
INCONVÉNIENTS DE LA CAH
Complexité algorithmique non linéaire (en n2 ou n3, parfois n2log(n))
Deux observations placées dans des classes différentes ne sont
jamais plus comparées
Data Mining-4GL-TWIN © ESPRIT2020-2021
OBJECTIFS DES TECHNIQUES DESCRIPTIVES
visent à mettre en évidence des informations présentes mais cachées par le
volume des données
il n’y a pas de variable « cible » à prédire
projection du nuage de points sur un espace de dimension inférieure pour obtenir une
visualisation de l’ensemble des liaisons entre : Individus, Variables… tout en
minimisant la perte d’information
trouver dans l’espace de travail des groupes homogènes d’individus ou de
variables
détection d’associations entre des objets
Data Mining-4GL-TWIN © ESPRIT2020-2021
