Chapitre 3: APPRENTISSAGE NON SUPERVISÉ

Module: Machine Learning

LSDM (S5)

Pr. Sidi Mohamed LALAOUI BEN CHERIF1

[email protected]

1 College of Computing

Université Mohammed VI Polytechnique

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 1 / 57

Apprentissage Non Supervisé

Définition :
L’apprentissage non supervisé consiste à analyser des données
sans étiquettes pour en extraire des structures ou motifs
sous-jacents.
Contrairement à l’apprentissage supervisé, il n’existe pas de
sortie cible prédéfinie.

Objectifs principaux :
Découverte de groupes similaires (clustering).
Réduction de dimensionnalité (compression des données).
Analyse des relations entre variables.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 2 / 57

Méthodes Principales en Apprentissage Non Supervisé

1. Clustering :
k-means : Partitionne les données en k groupes pour minimiser la
variance intra-groupe.
Clustering hiérarchique : Construit une hiérarchie de groupes
(fusion ou division).
DBSCAN : Détecte des groupes denses et identifie les points
isolés.

2. Réduction de dimension :
ACP (Analyse en Composantes Principales) : Réduit les
dimensions tout en conservant la variance maximale.
t-SNE : Visualise les données en deux ou trois dimensions.
Autoencodeurs : Utilise les réseaux neuronaux pour compresser
et reconstruire les données.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 3 / 57
Applications de l’Apprentissage Non Supervisé

1. Analyse de clients et segmentation :

Identifier des groupes de clients ayant des comportements
similaires.
Adapter des stratégies marketing en fonction des segments.

2. Détection d’anomalies :
Identifier des transactions frauduleuses ou des événements
inhabituels.

3. Bioinformatique :
Analyse de données génomiques (groupement de gènes ou
protéines).

4. Recommandations :
Utiliser le clustering pour proposer des produits ou contenus
similaires.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 4 / 57
Distance et Similarité entre Deux Observations

Pourquoi est-ce important ?

Regrouper des observations en groupes homogènes nécessite
une définition de similarité ou de différence.
Il faut quantifier la distance ou la similarité entre deux
observations.

Un défi clé :
Cette étape est souvent la plus difficile, mais elle est essentielle
pour toute analyse de partitionnement.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 5 / 57

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 6 / 57
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 7 / 57
 Overview of clustering methods

Overview of clustering methods

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 8 / 57

 Overview of clustering methods

Distances pour des Observations Quantitatives

1. Cas des variables numériques homogènes :

Si les observations sont des vecteurs xi , xj ∈ Rp , une distance
classique est la distance euclidienne :
s
p
d(xi , xj ) = ∑ (xi,k − xj,k )2 .
k=1

Raisonnable si toutes les variables sont de même ordre de

grandeur.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 9 / 57

 Overview of clustering methods

Distances pour des Observations Quantitatives

1. Cas des variables numériques homogènes :

Si les observations sont des vecteurs xi , xj ∈ Rp , une distance
classique est la distance euclidienne :
s
p
d(xi , xj ) = ∑ (xi,k − xj,k )2 .
k=1

Raisonnable si toutes les variables sont de même ordre de

grandeur.
2. Problème des variables de types mixtes :
Que faire si les variables sont binaires, catégoriques ou mixtes
(âge, revenu, sexe, etc.) ?
Nécessité de choisir une distance adaptée (ex. Hamming, Gower,
etc.).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 9 / 57

 Overview of clustering methods

Comparaison des Distances et Domaines d’Application

Résumé des principales distances :

Distance Type de Données Applications

Euclidienne Numériques homogènes Clustering (k-means), PCA
Manhattan (ou L1 ) Numériques (avec outliers) Analyse robuste des données
Hamming Binaires Données catégoriques, génétique
Cosinus Textes, vecteurs creux similarité de documents
Gower Mixtes (num., cat., bin.) Analyse exploratoire
Mahalanobis Numériques corrélées Détection d’anomalies

Notes :
La distance euclidienne est sensible aux échelles : standardisation
nécessaire.
Les distances comme Gower permettent d’analyser des données mixtes
(numériques et catégoriques).
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 10 / 57
 Overview of clustering methods

Mesures de Distance

Une mesure de distance d doit satisfaire les propriétés suivantes pour

tout i, j, k ∈ {1, . . . , n} :
d(i, j) ≥ 0 (positivité) ;
d(i, i) = 0 (distance nulle à soi-même) ;
d(i, j) = d(j, i) (symétrie) ;
d(i, k) ≤ d(i, j) + d(j, k) (inégalité triangulaire).

Exemple : La norme Lq dans Rp

!1/q
p
kxi − xj kq = ∑ |xik − xjk |q .
k=1

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 11 / 57

 Overview of clustering methods

Mesures de Distance

Une mesure de distance d doit satisfaire les propriétés suivantes pour

tout i, j, k ∈ {1, . . . , n} :
d(i, j) ≥ 0 (positivité) ;
d(i, i) = 0 (distance nulle à soi-même) ;
d(i, j) = d(j, i) (symétrie) ;
d(i, k) ≤ d(i, j) + d(j, k) (inégalité triangulaire).

Exemple : La norme Lq dans Rp

!1/q
p
kxi − xj kq = ∑ |xik − xjk |q .
k=1

Cas particulier : distance euclidienne (q = 2).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 11 / 57

 Overview of clustering methods

Sensibilité aux Changements d’Échelle

Problème : La distance Lq n’est PAS invariante à un changement

d’échelle.

Exemple : Jeu de données

Poids (g) Taille (cm)
10 7
20 2
30 10

Distances calculées avec des tailles en cm :

d(1, 2) = 11.2, d(1, 3) = 20.2, d(2, 3) = 12.8

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 12 / 57

 Overview of clustering methods

Sensibilité aux Changements d’Échelle

Problème : La distance Lq n’est PAS invariante à un changement

d’échelle.

Exemple : Jeu de données

Poids (g) Taille (cm)
10 7
20 2
30 10

Distances calculées avec des tailles en cm :

d(1, 2) = 11.2, d(1, 3) = 20.2, d(2, 3) = 12.8
Distances calculées avec des tailles en mm :
d(1, 2) = 51.0, d(1, 3) = 36.1, d(2, 3) = 80.6
Problème : L’échelle des variables influence les distances.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 12 / 57
 Overview of clustering methods

Standardisation des Distances

Solution : Distance standardisée entre les variables

p 
xik − µk xjk − µk 2 p 
xik − xjk 2
 
2
d (xi , xj ) = ∑ − =∑
k=1 sk sk k=1 sk

où :
µk = moyenne de la variable k ;
sk = écart-type de la variable k.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 13 / 57

 Overview of clustering methods

Standardisation des Distances

Solution : Distance standardisée entre les variables

p 
xik − µk xjk − µk 2 p 
xik − xjk 2
 
2
d (xi , xj ) = ∑ − =∑
k=1 sk sk k=1 sk

où :
µk = moyenne de la variable k ;
sk = écart-type de la variable k.
Avantage : La standardisation élimine l’influence de l’unité de mesure.
Distances (standardisées) peu importe l’unité :

d(1, 2) = 16, d(1, 3) = 42, d(2, 3) = 26.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 13 / 57

 Overview of clustering methods

Standardisation des Distances

Solution : Distance standardisée entre les variables

p 
xik − µk xjk − µk 2 p 
xik − xjk 2
 
2
d (xi , xj ) = ∑ − =∑
k=1 sk sk k=1 sk

où :
µk = moyenne de la variable k ;
sk = écart-type de la variable k.
Avantage : La standardisation élimine l’influence de l’unité de mesure.
Distances (standardisées) peu importe l’unité :

d(1, 2) = 16, d(1, 3) = 42, d(2, 3) = 26.

Conclusion : Toujours standardiser les variables dans les analyses

pratiques.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 13 / 57
 Overview of clustering methods

Indices de Similarité

Un indice de similarité s entre des objets doit satisfaire les propriétés

suivantes pour tout i, j, k ∈ {1, . . . , n} :
0 ≤ s(i, j) ≤ 1 (bornes de la similarité) ;
s(i, j) = s(j, i) (symétrie) ;
s(i, i) = 1 (similarité maximale avec soi-même).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 14 / 57

 Overview of clustering methods

Indices de Similarité

Un indice de similarité s entre des objets doit satisfaire les propriétés

suivantes pour tout i, j, k ∈ {1, . . . , n} :
0 ≤ s(i, j) ≤ 1 (bornes de la similarité) ;
s(i, j) = s(j, i) (symétrie) ;
s(i, i) = 1 (similarité maximale avec soi-même).
Transformation distance → similarité :
1
s(i, j) = .
1 + d(i, j)

Une distance peut être transformée en indice de similarité avec

cette formule.
Attention : la relation inverse n’est pas valide (à cause de
l’inégalité triangulaire).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 14 / 57

 Overview of clustering methods

Dissemblance et Types de Variables

Définition : Dissemblance

d∗ (i, j) = 1 − s(i, j).

La dissemblance est complémentaire à l’indice de similarité.

Elle est souvent utilisée dans les analyses exploratoires.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 15 / 57

 Overview of clustering methods

Dissemblance et Types de Variables

Définition : Dissemblance

d∗ (i, j) = 1 − s(i, j).

La dissemblance est complémentaire à l’indice de similarité.

Elle est souvent utilisée dans les analyses exploratoires.
Dépendance au type de variables :
Le choix d’un indice de similarité dépend des types de données :
Variables numériques : Exemple - coefficient de corrélation.
Variables binaires : Exemple - indice de Jaccard.
Variables mixtes : Exemple - mesure de Gower.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 15 / 57

 Overview of clustering methods

Dissemblance et Types de Variables

Définition : Dissemblance

d∗ (i, j) = 1 − s(i, j).

La dissemblance est complémentaire à l’indice de similarité.

Elle est souvent utilisée dans les analyses exploratoires.
Dépendance au type de variables :
Le choix d’un indice de similarité dépend des types de données :
Variables numériques : Exemple - coefficient de corrélation.
Variables binaires : Exemple - indice de Jaccard.
Variables mixtes : Exemple - mesure de Gower.
Conclusion : Bien choisir la méthode selon le type de données
analysées.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 15 / 57

 Overview of clustering methods

Variables Numériques

Définition :
Les variables numériques mesurent des quantités.
Les différences entre les valeurs reflètent les différences entre les
objets.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 16 / 57

 Overview of clustering methods

Variables Numériques

Définition :
Les variables numériques mesurent des quantités.
Les différences entre les valeurs reflètent les différences entre les
objets.
Exemples :
Revenu (en dollars) ;
Masse (en kilogrammes) ;
Âge (en années).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 16 / 57

 Overview of clustering methods

Variables Numériques

Définition :
Les variables numériques mesurent des quantités.
Les différences entre les valeurs reflètent les différences entre les
objets.
Exemples :
Revenu (en dollars) ;
Masse (en kilogrammes) ;
Âge (en années).
Distance utilisée : Distance euclidienne standardisée
p 
xik − xjk 2

2
d (xi , xj ) = ∑ ,
k=1 sk
où :
sk est l’écart-type de la variable k.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 16 / 57

 Overview of clustering methods

Variables Numériques

Définition :
Les variables numériques mesurent des quantités.
Les différences entre les valeurs reflètent les différences entre les
objets.
Exemples :
Revenu (en dollars) ;
Masse (en kilogrammes) ;
Âge (en années).
Distance utilisée : Distance euclidienne standardisée
p 
xik − xjk 2

2
d (xi , xj ) = ∑ ,
k=1 sk
où :
sk est l’écart-type de la variable k.
Avantage : La standardisation permet d’éliminer l’effet de l’échelle des
variables.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 16 / 57
 Overview of clustering methods

Variables Nominales

Définition :
Les variables nominales sont qualitatives (non numériques et non
ordinales).
Deux types :
Binaires : Deux modalités (e.g., sexe : homme/femme).
Polytomiques : Plus de deux modalités (e.g., section d’un cours).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 17 / 57

 Overview of clustering methods

Variables Nominales

Définition :
Les variables nominales sont qualitatives (non numériques et non
ordinales).
Deux types :
Binaires : Deux modalités (e.g., sexe : homme/femme).
Polytomiques : Plus de deux modalités (e.g., section d’un cours).
Symétriques :
Toutes les modalités ont le même niveau d’information.
Exemples : sexe, section de cours.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 17 / 57

 Overview of clustering methods

Variables Nominales

Définition :
Les variables nominales sont qualitatives (non numériques et non
ordinales).
Deux types :
Binaires : Deux modalités (e.g., sexe : homme/femme).
Polytomiques : Plus de deux modalités (e.g., section d’un cours).
Symétriques :
Toutes les modalités ont le même niveau d’information.
Exemples : sexe, section de cours.
Asymétriques :
Les modalités n’ont pas le même niveau d’information.
Exemples :
Daltonisme (oui/non) : "Oui" est informatif, "Non" ne l’est pas.
Fraude (oui/non) : "Oui" contient plus d’information que "Non".
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 17 / 57
 Overview of clustering methods

Variables Nominales Binaires : Symétriques

Définition :
Les variables binaires symétriques ont des modalités (0/1)
également informatives.
Exemple : Réponses à des questions Oui/Non.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 18 / 57

 Overview of clustering methods

Variables Nominales Binaires : Symétriques

Définition :
Les variables binaires symétriques ont des modalités (0/1)
également informatives.
Exemple : Réponses à des questions Oui/Non.
Proportion d’accords : Matching coefficient
Si p est le nombre de variables mesurées pour deux individus i et
j,
p
m= ∑ I(xik = xjk ),
k=1

où m est le nombre d’accords entre les vecteurs.

Similarité :
m
s(i, j) = .
p

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 18 / 57

 Overview of clustering methods

Variables Nominales Binaires : Symétriques

Exemple :

Individu Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10
i 1 0 0 0 0 1 0 0 0 0
j 1 0 0 0 0 0 1 0 0 0

8
s(i, j) = = 0.8.
10

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 19 / 57

 Overview of clustering methods

Variables Nominales Binaires : Symétriques

Exemple :

Individu Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10
i 1 0 0 0 0 1 0 0 0 0
j 1 0 0 0 0 0 1 0 0 0

8
s(i, j) =
= 0.8.
10
Ici, les deux individus ont la même réponse sur 8 des 10 questions.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 19 / 57

 Overview of clustering methods

Variables Nominales Binaires : Asymétriques

Définition :
Les variables binaires asymétriques ont des modalités où 1 est
rare ou plus informative.
Exemple : Présence/absence d’une caractéristique rare.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 20 / 57

 Overview of clustering methods

Variables Nominales Binaires : Asymétriques

Définition :
Les variables binaires asymétriques ont des modalités où 1 est
rare ou plus informative.
Exemple : Présence/absence d’une caractéristique rare.
Indice de Jaccard :
Similitude définie comme :
p
∑k=1 xik xjk
J(i, j) = p .
∑k=1 {1 − (1 − xik )(1 − xjk )}

Numérateur : Nombre de variables pour lesquelles i et j ont tous

deux 1.
Dénominateur : Nombre total de variables où au moins un des
deux a 1.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 20 / 57

 Overview of clustering methods

Variables Nominales Binaires : Asymétriques

Exemple :

Individu Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10
i 1 0 0 0 0 1 0 0 0 0
j 1 0 0 0 0 0 1 0 0 0

1
J(i, j) = = 0.33.
3

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 21 / 57

 Overview of clustering methods

Variables Nominales Binaires : Asymétriques

Exemple :

Individu Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10
i 1 0 0 0 0 1 0 0 0 0
j 1 0 0 0 0 0 1 0 0 0

1
J(i, j) =
= 0.33.
3
Ici, seules les questions Q1, Q6, et Q7 comptent, car i ou j ont 1. Ils
sont en accord une seule fois.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 21 / 57

 Overview of clustering methods

Variables Nominales Polytomiques

Définition :
Lorsque plusieurs variables nominales binaires ou polytomiques
(q) de même nature sont disponibles, on calcule la similarité
séparément pour chacune d’elles.
La similarité globale est ensuite la moyenne des q similarités.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 22 / 57

 Overview of clustering methods

Variables Nominales Polytomiques

Définition :
Lorsque plusieurs variables nominales binaires ou polytomiques
(q) de même nature sont disponibles, on calcule la similarité
séparément pour chacune d’elles.
La similarité globale est ensuite la moyenne des q similarités.
Exemple :
Individu Q1a Q1b Q1c Q2a Q2b Q2c
i 0 1 0 0 1 0
j 0 1 0 0 0 1

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 22 / 57

 Overview of clustering methods

Variables Nominales Polytomiques

Définition :
Lorsque plusieurs variables nominales binaires ou polytomiques
(q) de même nature sont disponibles, on calcule la similarité
séparément pour chacune d’elles.
La similarité globale est ensuite la moyenne des q similarités.
Exemple :
Individu Q1a Q1b Q1c Q2a Q2b Q2c
i 0 1 0 0 1 0
j 0 1 0 0 0 1
Similarité pour une question (Q) :
Modalités identiques
sQ (i, j) = .
Nombre total de modalités pour Q
La similarité globale est :
sQ1 (i, j) + sQ2 (i, j)
s(i, j) = .
2
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 22 / 57
 Overview of clustering methods

Calcul des Similarités pour Q1 et Q2

1. Calcul pour Q1 :
Modalités (Q1a, Q1b, Q1c) :

i = (0, 1, 0), j = (0, 1, 0).

Toutes les modalités coïncident (3/3).

3
sQ1 (i, j) = = 1.
3

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 23 / 57

 Overview of clustering methods

Calcul des Similarités pour Q1 et Q2

1. Calcul pour Q1 :
Modalités (Q1a, Q1b, Q1c) :

i = (0, 1, 0), j = (0, 1, 0).

Toutes les modalités coïncident (3/3).

3
sQ1 (i, j) = = 1.
3
2. Calcul pour Q2 :
Modalités (Q2a, Q2b, Q2c) :

i = (0, 1, 0), j = (0, 0, 1).

Une seule modalité coïncide (Q2a = 0) sur 3.

1
sQ2 (i, j) = .
3
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 23 / 57
 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

Calcul de la similarité globale :

La moyenne des similarités pour Q1 et Q2 est donnée par :

sQ1 (i, j) + sQ2 (i, j)

s(i, j) = .
2

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 24 / 57

 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

Calcul de la similarité globale :

La moyenne des similarités pour Q1 et Q2 est donnée par :

sQ1 (i, j) + sQ2 (i, j)

s(i, j) = .
2

Substitution des valeurs :

1 + 31 4 2
s(i, j) = = = .
2 6 3

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 24 / 57

 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

Calcul de la similarité globale :

La moyenne des similarités pour Q1 et Q2 est donnée par :

sQ1 (i, j) + sQ2 (i, j)

s(i, j) = .
2

Substitution des valeurs :

1 + 31 4 2
s(i, j) = = = .
2 6 3
Conclusion :
La similarité globale tient compte de toutes les modalités, qu’elles
soient activées (1) ou non (0).
Cela garantit une mesure cohérente entre les individus.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 24 / 57
 Overview of clustering methods

Variables Symétriques et Asymétriques

Hypothèse :
Les variables correspondant à Q1 sont symétriques.
Les variables correspondant à Q2 sont asymétriques.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 25 / 57

 Overview of clustering methods

Variables Symétriques et Asymétriques

Hypothèse :
Les variables correspondant à Q1 sont symétriques.
Les variables correspondant à Q2 sont asymétriques.
Données des individus :
Individu Q2a Q2b Q2c
i 0 1 0
j 0 0 1

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 25 / 57

 Overview of clustering methods

Variables Symétriques et Asymétriques

Hypothèse :
Les variables correspondant à Q1 sont symétriques.
Les variables correspondant à Q2 sont asymétriques.
Données des individus :
Individu Q2a Q2b Q2c
i 0 1 0
j 0 0 1

Nous allons calculer la similarité pour chaque question et en déduire la

similarité globale.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 25 / 57

 Overview of clustering methods

Calcul des Similarités

Les modalités de Q1 sont totalement identiques pour i et j.

La similarité est donnée par :
Modalités identiques 2
sQ1 (i, j) = = = 1.
Modalités totales 2

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 26 / 57

 Overview of clustering methods

Calcul des Similarités

Les modalités de Q1 sont totalement identiques pour i et j.

La similarité est donnée par :
Modalités identiques 2
sQ1 (i, j) = = = 1.
Modalités totales 2
Modalités activées (A et B) :
A = {Q2b = 1}, B = {Q2c = 1}.
Interprétation :
A ∩ B = 0,
/ A ∪ B = {Q2b = 1, Q2c = 1}.
Similarité de Jaccard :
|A ∩ B| 0
sQ2 (i, j) = = = 0.
|A ∪ B| 2

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 26 / 57

 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

La similarité globale est donnée par la moyenne des similarités de

Q1 et Q2 :
sQ1 (i, j) + sQ2 (i, j)
s(i, j) = .
2

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 27 / 57

 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

La similarité globale est donnée par la moyenne des similarités de

Q1 et Q2 :
sQ1 (i, j) + sQ2 (i, j)
s(i, j) = .
2

Substitution des valeurs :

1+0 1
s(i, j) = = .
2 2

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 27 / 57

 Overview of clustering methods

Calcul de la Similarité Globale et Conclusion

La similarité globale est donnée par la moyenne des similarités de

Q1 et Q2 :
sQ1 (i, j) + sQ2 (i, j)
s(i, j) = .
2

Substitution des valeurs :

1+0 1
s(i, j) = = .
2 2

La similarité globale entre i et j est s(i, j) = 21 .

Cette approche combine différentes méthodes adaptées à la
nature des variables (symétriques ou asymétriques).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 27 / 57

 Overview of clustering methods

Variables Ordinales

Les variables ordinales permettent d’ordonner les modalités

sans donner de mesure précise.
Exemples :
Revenu : faible, moyen, élevé.
Niveau d’accord : tout à fait en désaccord, en désaccord, pas
d’avis, d’accord, tout à fait d’accord.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 28 / 57

 Overview of clustering methods

Variables Ordinales

Les variables ordinales permettent d’ordonner les modalités

sans donner de mesure précise.
Exemples :
Revenu : faible, moyen, élevé.
Niveau d’accord : tout à fait en désaccord, en désaccord, pas
d’avis, d’accord, tout à fait d’accord.

On assigne des scores numériques à chaque modalité pour

refléter leur ordre.
Les scores doivent être :
Positifs.
Ordonnés selon les modalités.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 28 / 57

 Overview of clustering methods

Variables Ordinales

Les variables ordinales permettent d’ordonner les modalités

sans donner de mesure précise.
Exemples :
Revenu : faible, moyen, élevé.
Niveau d’accord : tout à fait en désaccord, en désaccord, pas
d’avis, d’accord, tout à fait d’accord.

On assigne des scores numériques à chaque modalité pour

refléter leur ordre.
Les scores doivent être :
Positifs.
Ordonnés selon les modalités.
Exemples de scores possibles :
Revenu : faible = 1, moyen = 2, élevé = 3.
Revenu : faible = 15000, moyen = 50000, élevé = 150000.
Ces choix sont subjectifs et relèvent d’un jugement de l’analyste.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 28 / 57
 Overview of clustering methods

Observations constituées de plusieurs types de variables

Si chaque observation est constituée de variables de plusieurs types,

comme l’âge (numérique), le sexe (nominale symétrique), la présence
d’une mutation génétique rare (nominale asymétrique) et le niveau
d’accord avec une politique (ordinale), il existe plusieurs façons de
mesurer la similarité. La méthode la plus courante est la similarité de
Gower.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 29 / 57

 Overview of clustering methods

Observations constituées de plusieurs types de variables

Si chaque observation est constituée de variables de plusieurs types,

comme l’âge (numérique), le sexe (nominale symétrique), la présence
d’une mutation génétique rare (nominale asymétrique) et le niveau
d’accord avec une politique (ordinale), il existe plusieurs façons de
mesurer la similarité. La méthode la plus courante est la similarité de
Gower.
Procédure :
Recoder les variables nominales sous forme binaire.
Recoder les variables ordinales sous forme numérique.
Calculer la similarité de Gower entre les individus.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 29 / 57

 Overview of clustering methods

Similarité de Gower

La similarité de Gower G(i, j) entre les individus i et j est donnée par la

formule : p
∑ wk γk (i, j)sk (i, j)
G(i, j) = k=1p
∑k=1 wk γk (i, j)

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 30 / 57

 Overview of clustering methods

Similarité de Gower

La similarité de Gower G(i, j) entre les individus i et j est donnée par la

formule : p
∑ wk γk (i, j)sk (i, j)
G(i, j) = k=1p
∑k=1 wk γk (i, j)
Où :
wk est un poids associé à la variable k,
γk (i, j) est un facteur dépendant du type de la variable,
sk (i, j) est la mesure de similarité pour la variable k.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 30 / 57

 Overview of clustering methods

Similarité de Gower

La similarité de Gower G(i, j) entre les individus i et j est donnée par la

formule : p
∑ wk γk (i, j)sk (i, j)
G(i, j) = k=1p
∑k=1 wk γk (i, j)
Où :
wk est un poids associé à la variable k,
γk (i, j) est un facteur dépendant du type de la variable,
sk (i, j) est la mesure de similarité pour la variable k.
Selon le type de variable :
|xik −xjk |
Numérique ou ordinale : γk (i, j) = 1, sk (i, j) = 1 − rk ,
Nominale symétrique : γk (i, j) = 1, sk (i, j) = I(xik = xjk ),
Nominale asymétrique : γk (i, j) = 1 − (1 − xik )(1 − xjk ),
sk (i, j) = I(xik = xjk ).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 30 / 57

 Overview of clustering methods

Exemple de Données

Supposons que les réponses de deux individus i et j aux cinq variables

soient les suivantes :

Individu Q1 Q2 Q3 Q4 Q5
i 1 2 0 1 0
j -1 1 0 0 1

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 31 / 57

 Overview of clustering methods

Exemple de Données

Supposons que les réponses de deux individus i et j aux cinq variables

soient les suivantes :

Individu Q1 Q2 Q3 Q4 Q5
i 1 2 0 1 0
j -1 1 0 0 1

Poids attribués :
w1 = 3, w2 = w3 = w4 = w5 = 1,
Nous allons maintenant calculer la similarité de Gower entre i et j.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 31 / 57

 Overview of clustering methods

Calcul de la similarité de Gower

Pour chaque variable :

γ1 (i, j) = 1, s1 (i, j) = 1 − |1−(−1)|
5 = 35 ,
γ2 (i, j) = 1, s2 (i, j) = 1 − |2−1| 4
5 = 5,
γ3 (i, j) = 1, s3 (i, j) = 1,
γ4 (i, j) = 1, s4 (i, j) = 0,
γ5 (i, j) = 1 − (1 − 0)(1 − 1) = 1, s5 (i, j) = 0.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 32 / 57

 Overview of clustering methods

Calcul de la similarité de Gower

Pour chaque variable :

γ1 (i, j) = 1, s1 (i, j) = 1 − |1−(−1)|
5 = 35 ,
γ2 (i, j) = 1, s2 (i, j) = 1 − |2−1| 4
5 = 5,
γ3 (i, j) = 1, s3 (i, j) = 1,
γ4 (i, j) = 1, s4 (i, j) = 0,
γ5 (i, j) = 1 − (1 − 0)(1 − 1) = 1, s5 (i, j) = 0.
La similarité de Gower est calculée comme suit :

3 × 35 + 1 × 45 + 1 × 1 + 1 × 0 + 1 × 0 18
18
G(i, j) = = 5 = ≈ 0.514.
3+1+1+1+1 7 35

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 32 / 57

 Overview of clustering methods

Mesures pour des applications spécifiques : Text Mining

Pour analyser et partitionner n documents écrits (ex. : pages web,

courriels, lettres, documents légaux), on utilise une matrice
documents-termes :
Chaque ligne correspond à un document.
Chaque colonne correspond à un mot unique dans l’ensemble
des documents.
L’élément (i, k) de la matrice représente la fréquence du mot k
dans le document i.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 33 / 57

 Overview of clustering methods

Mesures pour des applications spécifiques : Text Mining

Pour analyser et partitionner n documents écrits (ex. : pages web,

courriels, lettres, documents légaux), on utilise une matrice
documents-termes :
Chaque ligne correspond à un document.
Chaque colonne correspond à un mot unique dans l’ensemble
des documents.
L’élément (i, k) de la matrice représente la fréquence du mot k
dans le document i.
Caractéristiques de cette matrice :
Très grande (p, le nombre de mots, est souvent élevé).
Éparse (majorité des valeurs sont nulles).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 33 / 57

 Overview of clustering methods

Codages et Mesures de Similarité

Codages fréquemment utilisés :

Présence/absence : (i, k) = 1 si le mot k est présent dans le
document i, 0 sinon.
tf-idf : Transformation des fréquences pour refléter l’importance
d’un mot.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 34 / 57

 Overview of clustering methods

Codages et Mesures de Similarité

Codages fréquemment utilisés :

Présence/absence : (i, k) = 1 si le mot k est présent dans le
document i, 0 sinon.
tf-idf : Transformation des fréquences pour refléter l’importance
d’un mot.
Mesures de similarité :
Jaccard : Utile pour les codages binaires, mais peut donner des
similarités faibles dans des matrices éparses.
Cosinus : Fonctionne bien pour les variables binaires ou
numériques.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 34 / 57

 Overview of clustering methods

Similarité du Cosinus

La similarité du cosinus mesure l’angle entre deux vecteurs dans un

espace à p dimensions :
p
∑k=1 wk xik xjk
scos (i, j) = q
p 2 p w x2
∑k=1 wk xik ∑k=1 k jk

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 35 / 57

 Overview of clustering methods

Similarité du Cosinus

La similarité du cosinus mesure l’angle entre deux vecteurs dans un

espace à p dimensions :
p
∑k=1 wk xik xjk
scos (i, j) = q
p 2 p w x2
∑k=1 wk xik ∑k=1 k jk
Interprétation :
xik et xjk représentent les valeurs associées au mot k dans les
documents i et j.
wk est un poids pour le mot k (peut être égal à 1 si aucun
ajustement n’est fait).
La mesure est comprise entre 0 (aucune similarité) et 1 (identité
parfaite).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 35 / 57

 Overview of clustering methods

Similarité du Cosinus

La similarité du cosinus mesure l’angle entre deux vecteurs dans un

espace à p dimensions :
p
∑k=1 wk xik xjk
scos (i, j) = q
p 2 p w x2
∑k=1 wk xik ∑k=1 k jk
Interprétation :
xik et xjk représentent les valeurs associées au mot k dans les
documents i et j.
wk est un poids pour le mot k (peut être égal à 1 si aucun
ajustement n’est fait).
La mesure est comprise entre 0 (aucune similarité) et 1 (identité
parfaite).
Applications :
Détection de similarité entre documents (plagiat, duplication).
Recherche d’extraits similaires dans des bases de données
textuelles.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 35 / 57
 Overview of clustering methods

Utilisation des Méthodes Factorielles

Problème : Lorsque le nombre de variables (p) est très élevé, le calcul

des similarités ou distances entre observations peut devenir complexe
et coûteux.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 36 / 57

 Overview of clustering methods

Utilisation des Méthodes Factorielles

Problème : Lorsque le nombre de variables (p) est très élevé, le calcul

des similarités ou distances entre observations peut devenir complexe
et coûteux.
Solution : Les méthodes factorielles permettent de réduire la
dimension tout en conservant l’essentiel de l’information. Deux
approches courantes :
Analyse en composantes principales (ACP) : pour des
variables numériques/ordinales.
Analyse des correspondances multiples (ACM) : pour des
variables catégorielles (p. ex. : réponses à choix multiples).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 36 / 57

 Overview of clustering methods

Utilisation des Méthodes Factorielles

Problème : Lorsque le nombre de variables (p) est très élevé, le calcul

des similarités ou distances entre observations peut devenir complexe
et coûteux.
Solution : Les méthodes factorielles permettent de réduire la
dimension tout en conservant l’essentiel de l’information. Deux
approches courantes :
Analyse en composantes principales (ACP) : pour des
variables numériques/ordinales.
Analyse des correspondances multiples (ACM) : pour des
variables catégorielles (p. ex. : réponses à choix multiples).
Étapes principales :
1 Réduction de dimension : Calculer les scores des observations
dans les k  p axes principaux.
2 Calcul des distances : Utiliser ces scores et la distance
euclidienne.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 36 / 57
 Overview of clustering methods

Avantages et Limites des Méthodes Factorielles

Avantages :
Réduction de la complexité computationnelle.
Utilisation efficace de l’information : Les axes principaux capturent
une grande part de la variance.
Approche adaptée à différents types de données (numériques ou
catégorielles).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 37 / 57

 Overview of clustering methods

Avantages et Limites des Méthodes Factorielles

Avantages :
Réduction de la complexité computationnelle.
Utilisation efficace de l’information : Les axes principaux capturent
une grande part de la variance.
Approche adaptée à différents types de données (numériques ou
catégorielles).
Limites :
Perte d’information possible : Les groupes clairement séparés en
dimension p peuvent devenir moins distinguables en dimension
k < p.
Nécessite une analyse préliminaire pour choisir un k optimal (ex. :
critère d’inertie expliquée).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 37 / 57

 Overview of clustering methods

Avantages et Limites des Méthodes Factorielles

Avantages :
Réduction de la complexité computationnelle.
Utilisation efficace de l’information : Les axes principaux capturent
une grande part de la variance.
Approche adaptée à différents types de données (numériques ou
catégorielles).
Limites :
Perte d’information possible : Les groupes clairement séparés en
dimension p peuvent devenir moins distinguables en dimension
k < p.
Nécessite une analyse préliminaire pour choisir un k optimal (ex. :
critère d’inertie expliquée).
Applications :
Études exploratoires sur des données multidimensionnelles.
Préparation de données pour des analyses de regroupement
(clustering).
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 37 / 57
 Overview of clustering methods

Clustering : Algorithme des K-moyennes

Contexte :
Applicable aux situations où les p variables sont numériques ou
ordinales (standardisées).
Objectif : Partitionner n observations en K groupes (K fixé au
préalable).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 38 / 57

 Overview of clustering methods

Clustering : Algorithme des K-moyennes

Contexte :
Applicable aux situations où les p variables sont numériques ou
ordinales (standardisées).
Objectif : Partitionner n observations en K groupes (K fixé au
préalable).
Principe :
Minimiser la variabilité intra-groupe W(C), définie comme la
somme des distances au carré des observations à leurs
centroïdes.
L’algorithme diminue W(C) à chaque itération.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 38 / 57

 Overview of clustering methods

Étapes de l’algorithme des K-moyennes

1 Choisir le nombre de groupes K.

2 Partitionner aléatoirement les n observations en K groupes.
3 Calculer les coordonnées des centroïdes µk pour chaque groupe
k:
1
µk = ∑ xi , k = 1, . . . , K
Nk i:C(i)=k

4 Calculer la distance entre chaque observation et chacun des K

centroïdes.
5 Réassigner chaque observation au groupe dont le centroïde est le
plus proche.
6 Répéter les étapes 3 à 5 jusqu’à convergence (aucune
réassignation).

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 39 / 57

 Overview of clustering methods

Variantes et Remarques

Variante : Algorithme des K-médoïdes

Utilise un médoïde (l’observation la plus centrale) au lieu d’un
centroïde.
Étape 4 : Calculer la distance entre chaque observation et les K
médoïdes.
Avantage : Plus robuste aux données bruitées ou contenant des
valeurs aberrantes.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 40 / 57

 Overview of clustering methods

Variantes et Remarques

Variante : Algorithme des K-médoïdes

Utilise un médoïde (l’observation la plus centrale) au lieu d’un
centroïde.
Étape 4 : Calculer la distance entre chaque observation et les K
médoïdes.
Avantage : Plus robuste aux données bruitées ou contenant des
valeurs aberrantes.
Remarques :
Sensibilité au choix initial des groupes : plusieurs exécutions
peuvent être nécessaires.
Complexité : O(n · K · t), où t est le nombre d’itérations.
Utilisation courante dans l’analyse exploratoire et le
regroupement.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 40 / 57

 Overview of clustering methods

Exemple : Algorithme des K-moyennes

Données initiales :
i 1 2 3 4 5
xi1 -1 -0.5 0 0.5 1
xi2 -1 0 0.5 -0.5 1

Paramètres :
Nombre de groupes fixé K = 2.
L’objectif est de minimiser la variabilité intra-groupe W(C).
Itération 1 : Assignation initiale
Groupe 1 : Observations 1, 2, 5.
Groupe 2 : Observations 3, 4.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 41 / 57

 Overview of clustering methods

Itération 1 : Calcul des centroïdes et distances

Centroïdes :
       
1 −1 −0.5 1 −1/6
µ1 = + + =
3 −1 0 1 0
     
1 0 0.5 1/4
µ2 = + =
2 0.5 −0.5 0
Distances au carré :
i 1 2 3 4 5
d2 (i, µ1 ) 1.69 0.11 0.28 0.69 2.36
d2 (i, µ2 ) 2.56 0.56 0.31 0.31 1.57

Nouvelles assignations :
Groupe 1 : Observations 1, 2, 3.
Groupe 2 : Observations 4, 5.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 42 / 57
 Overview of clustering methods

Itération 2 : Calcul des centroïdes et distances

Nouveaux centroïdes :
       
1 −1 −0.5 0 −1/2
µ1 = + + =
3 −1 0 0.5 −1/6
     
1 0.5 1 3/4
µ2 = + =
2 −0.5 1 1/4
Distances au carré :
i 1 2 3 4 5
d2 (i, µ1 ) 0.94 0.03 0.69 1.11 3.61
d2 (i, µ2 ) 4.63 1.63 0.63 0.63 0.63

Nouvelles assignations :
Groupe 1 : Observations 1, 2.
Groupe 2 : Observations 3, 4, 5.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 43 / 57
 Overview of clustering methods

Itération 3 : Convergence

Nouveaux centroïdes :
     
1 −1 −0.5 −3/4
µ1 = + =
2 −1 0 −1/2
       
1 0 0.5 1 1/2
µ2 = + + =
3 0.5 −0.5 1 1/3
Distances au carré :
i 1 2 3 4 5
d2 (i, µ1 ) 0.31 0.31 1.56 1.56 5.31
d2 (i, µ2 ) 4.03 1.11 0.28 0.69 0.69
Assignations finales :
Groupe 1 : Observations 1, 2.
Groupe 2 : Observations 3, 4, 5.
Conclusion : L’algorithme converge, aucune observation ne change
de groupe.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 44 / 57
 Illustration graphique des itérations

Itération 1

Initialisation des groupes : Observations {1, 2, 5} dans le groupe 1 (rouge),

Observations {3, 4} dans le groupe 2 (bleu).
Calcul des centroïdes :
   
−1/6 1/4
µ1 = , µ2 = .
0 0

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 45 / 57

 Illustration graphique des itérations

Itération 2

Mise à jour des groupes : Observations {1, 2, 3} dans le groupe 1 (rouge),

Observations {4, 5} dans le groupe 2 (bleu).
Calcul des nouveaux centroïdes :
   
−1/2 3/4
µ1 = , µ2 = .
−1/6 1/4

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 46 / 57

 Illustration graphique des itérations

Itération 3

Les groupes restent inchangés : {1, 2, 3} dans le groupe 1 (rouge), {4, 5} dans le
groupe 2 (bleu).
Calcul des nouveaux centroïdes :
   
−3/4 1/2
µ1 = , µ2 = .
−1/2 1/3

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 47 / 57

 Illustration graphique des itérations

Compacité & Séparation

Nous analysons cet algorithme en fonction de trois critères :

Compacité : Mesure la cohésion des points au sein d’un cluster.
Séparation : Mesure la distance entre différents clusters.
Indices combinés : Combine compacité et séparation pour une
évaluation globale.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 48 / 57

 Illustration graphique des itérations

K-means : Principe de base

L’algorithme K-means est basé sur la minimisation de la variance

intra-cluster. Il suit les étapes suivantes :
1 Choisir un nombre K de clusters.
2 Initialiser K centroïdes.
3 Assigner chaque point xi au cluster le plus proche :

Ck = {xi | kxi − µk k2 est minimal}

4 Recalculer les centroïdes des clusters :

1
µk = xi
|Ck | xi∑
∈Ck

5 Répéter jusqu’à convergence.

L’objectif est de minimiser la variance intra-cluster pour créer des
clusters compacts.
Pr. LALAOUI Ben Cherif Data Mining 2024/2025 49 / 57
 Illustration graphique des itérations

K-means : Compacité

La compacité de K-means est mesurée par la variance intra-cluster :

K
Compacité = ∑ ∑ kx − µk k2
k=1 x∈Ck

où µk est le centroïde du cluster Ck . K-means minimise cette

compacité en réorganisant les points dans les clusters.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 50 / 57

 Illustration graphique des itérations

K-means : Séparation

La séparation est mesurée par la distance entre les centroïdes des

clusters :
Séparation inter-cluster = min kµi − µj k
i6=j

K-means ne garantit pas une séparation optimale, mais optimise la

compacité.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 51 / 57

 Illustration graphique des itérations

K-means : Indices combinés

Les indices combinés pour K-means sont :

Indice de Silhouette :
b(x) − a(x)
s(x) =
max(a(x), b(x))
où a(x) est la moyenne des distances de x à tous les autres points du même
cluster et b(x) est la distance minimale entre x et les points du cluster le plus
proche.
Indice de Calinski-Harabasz (CH) :

∑Kk=1 |Ck |kµk − µk

2
CH =
∑K
k=1 ∑xi ∈Ck kxi − µk k
2

où µ est le centroïde global de tous les points et |Ck | est le nombre de points
dans le cluster Ck .
Indice Davies-Bouldin (DBI) :

1 K
 
Compacité(Ci ) + Compacité(Cj )
DBI = ∑ max
K i=1 i6=j kµi − µj k

Ces indices donnent une mesure globale de la qualité du clustering.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 52 / 57
 Classification hiérarchique

Qu’est-ce que la classification hiérarchique ?

Méthode de regroupement pour obtenir des partitions imbriquées.

Appropriée si :
on ne connaît pas le nombre de groupes K à priori ;
les observations ne sont pas constituées de variables numériques
ou ordinales.
Résultat : n partitions successives :
Une partition avec un groupe ;
Une partition avec deux groupes ;
... Jusqu’à une partition avec n groupes.
Visualisation : dendrogramme.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 53 / 57

 Types d’algorithmes

Deux types d’algorithmes

Algorithmes descendants :
Départ : toutes les observations dans un seul groupe.
À chaque étape : division du groupe le moins homogène en deux
sous-groupes.
Fin : chaque observation devient son propre groupe.
Algorithmes ascendants :
Départ : chaque observation est un groupe séparé.
À chaque étape : fusion des deux groupes les plus similaires.
Fin : un seul groupe contenant toutes les observations.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 54 / 57

 Algorithmes ascendants

Pourquoi se concentrer sur les algorithmes ascendants ?

Algorithmes descendants :
Très coûteux en temps de calcul.
Complexité : déterminer quel groupe scinder et comment le
découper.
Peu utilisés en pratique.
Algorithmes ascendants :
Simples et efficaces.
Méthode standard pour la classification hiérarchique.
Produit un dendrogramme montrant les fusions successives.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 55 / 57

 Résultats d’un algorithme ascendant

Interprétation des résultats

Chaque étape fusionne les deux groupes les plus similaires.

Résultat final : un dendrogramme.
Comment choisir une partition finale :
Déterminer un seuil de similarité/distance.
Utiliser des critères d’homogénéité.
Exemple :
Une coupe horizontale dans le dendrogramme détermine une
partition.

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 56 / 57

 Résultats d’un algorithme ascendant

Interprétation des résultats : Dendrogramme

Pr. LALAOUI Ben Cherif Data Mining 2024/2025 57 / 57