Segmentation (Clustering)

Introduction à la fouille de données

M. Ledmi
m_ledmi@[Link]
Département d’Informatique Khenchela

2020/2021

M. Ledmi Introduction à la fouille de données

 Segmentation (Clustering)

Plan

1 Segmentation (Clustering)
Introduction
Problématique
Distance et Dissimilarité
Algorithme k-Means

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Vous êtes ici

1 Segmentation (Clustering)
Introduction
Problématique
Distance et Dissimilarité
Algorithme k-Means

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Segmentation( Clustering)

La segmentation se rapporte à la
catégorisation d’un ensemble d’objets de
données dans des clusters.
Elle est aussi appelée classification non
supervisée.
Un cluster est une collection d’objets de
données :
Similaires les uns aux autres dans le même
segment,
Différents des objets dans d’autres segments.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Segmentation( Clustering)

La segmentation se rapporte à la
catégorisation d’un ensemble d’objets de
données dans des clusters.
Elle est aussi appelée classification non
supervisée.
Un cluster est une collection d’objets de
données :
Similaires les uns aux autres dans le même
segment,
Différents des objets dans d’autres segments.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Segmentation( Clustering)

La segmentation se rapporte à la
catégorisation d’un ensemble d’objets de
données dans des clusters.
Elle est aussi appelée classification non
supervisée.
Un cluster est une collection d’objets de
données :
Similaires les uns aux autres dans le même
segment,
Différents des objets dans d’autres segments.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Segmentation( Clustering)

La segmentation se rapporte à la
catégorisation d’un ensemble d’objets de
données dans des clusters.
Elle est aussi appelée classification non
supervisée.
Un cluster est une collection d’objets de
données :
Similaires les uns aux autres dans le même
segment,
Différents des objets dans d’autres segments.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthode de partitionnement :
Créer un partitionnement initial.
Utiliser une stratégie de contrôle itérative
pour l’optimiser.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthode de partitionnement :
Créer un partitionnement initial.
Utiliser une stratégie de contrôle itérative
pour l’optimiser.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthode de partitionnement :
Créer un partitionnement initial.
Utiliser une stratégie de contrôle itérative
pour l’optimiser.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthode de partitionnement :
Créer un partitionnement initial.
Utiliser une stratégie de contrôle itérative
pour l’optimiser.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthode de partitionnement :
Créer un partitionnement initial.
Utiliser une stratégie de contrôle itérative
pour l’optimiser.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthodes hiérarchiques :
Construire une hiérarchie de clusters (appelé
dendrogramme),
Non seulement un partitionnement unique
des objets.
Utiliser une condition de terminaison. (ex.
Nombre de clusters).
Méthodes basées sur la densité : utiliser les
fonctions de densité de voisinage.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthodes hiérarchiques :
Construire une hiérarchie de clusters (appelé
dendrogramme),
Non seulement un partitionnement unique
des objets.
Utiliser une condition de terminaison. (ex.
Nombre de clusters).
Méthodes basées sur la densité : utiliser les
fonctions de densité de voisinage.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthodes hiérarchiques :
Construire une hiérarchie de clusters (appelé
dendrogramme),
Non seulement un partitionnement unique
des objets.
Utiliser une condition de terminaison. (ex.
Nombre de clusters).
Méthodes basées sur la densité : utiliser les
fonctions de densité de voisinage.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthodes hiérarchiques :
Construire une hiérarchie de clusters (appelé
dendrogramme),
Non seulement un partitionnement unique
des objets.
Utiliser une condition de terminaison. (ex.
Nombre de clusters).
Méthodes basées sur la densité : utiliser les
fonctions de densité de voisinage.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Approches de clustering

Méthodes hiérarchiques :
Construire une hiérarchie de clusters (appelé
dendrogramme),
Non seulement un partitionnement unique
des objets.
Utiliser une condition de terminaison. (ex.
Nombre de clusters).
Méthodes basées sur la densité : utiliser les
fonctions de densité de voisinage.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Exemples d’application de la segmentation

La reconnaissance de formes et le traitement d’images.

Analyse des données spatiales : créer des cartes thématiques dans les
systèmes d’information géographique (SIG).
Bioinformatique : la détermination des groupes de signatures à partir
d’une base de données de gènes.
Web : clustering des fichiers log pour découvrir des modèles d’accès
similaires.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Exemples d’application de la segmentation

La reconnaissance de formes et le traitement d’images.

Analyse des données spatiales : créer des cartes thématiques dans les
systèmes d’information géographique (SIG).
Bioinformatique : la détermination des groupes de signatures à partir
d’une base de données de gènes.
Web : clustering des fichiers log pour découvrir des modèles d’accès
similaires.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Exemples d’application de la segmentation

La reconnaissance de formes et le traitement d’images.

Analyse des données spatiales : créer des cartes thématiques dans les
systèmes d’information géographique (SIG).
Bioinformatique : la détermination des groupes de signatures à partir
d’une base de données de gènes.
Web : clustering des fichiers log pour découvrir des modèles d’accès
similaires.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Exemples d’application de la segmentation

La reconnaissance de formes et le traitement d’images.

Analyse des données spatiales : créer des cartes thématiques dans les
systèmes d’information géographique (SIG).
Bioinformatique : la détermination des groupes de signatures à partir
d’une base de données de gènes.
Web : clustering des fichiers log pour découvrir des modèles d’accès
similaires.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Problèmatique
Problèmatique
Soit P une polpulation d’instances de données à N attributs, trouver un
partitionnement en K clusters (groupes) {C1 , C2, . . . CK } de P telque :
K
[
Ck = P
k=1

Où les clusters Ck soient :

1 Homogènes que possible (similaires au sein d’un même groupe).
2 Distincts que possible (dissimilaires quand ils appartiennent à des
groupes différents).

K peut être donné, ou “découvert”.

M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Problèmatique
Problèmatique
Soit P une polpulation d’instances de données à N attributs, trouver un
partitionnement en K clusters (groupes) {C1 , C2, . . . CK } de P telque :
K
[
Ck = P
k=1

Où les clusters Ck soient :

1 Homogènes que possible (similaires au sein d’un même groupe).
2 Distincts que possible (dissimilaires quand ils appartiennent à des
groupes différents).

K peut être donné, ou “découvert”.

M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Problèmatique
Problèmatique
Soit P une polpulation d’instances de données à N attributs, trouver un
partitionnement en K clusters (groupes) {C1 , C2, . . . CK } de P telque :
K
[
Ck = P
k=1

Où les clusters Ck soient :

1 Homogènes que possible (similaires au sein d’un même groupe).
2 Distincts que possible (dissimilaires quand ils appartiennent à des
groupes différents).

K peut être donné, ou “découvert”.

M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Qualité d’un clustering

Une bonne méthode de clustering produira des clusters d’excellente

qualité avec :
Similarité intra-classe importante.
Similarité inter-classe faible.
La qualité d’un clustering dépend de :
La mesure de similarité utilisée.
L’implémentation de la mesure de similarité.
La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “pattern” cachés.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance et Dissimilarité

Distance
On appelle distance sur un ensemble E, une application d : E × E ← R+
telle que :

1 Séparation : ∀(x, y) ∈ E 2 : d(x, y) = 0 ssi x = y

2 Symétrie : ∀(x, y) ∈ E 2 : d(x, y) = d(y, x)
3 Inégalité triangulaire : ∀(x, y, z) ∈ E 3 : d(x, z) ≤ d(x, y) + d(y, z)

Une dissimilarité est une application qui a les propriétés de la distance

sauf éventuellement l’inégalité triangulaire.
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance et Dissimilarité

Distance
On appelle distance sur un ensemble E, une application d : E × E ← R+
telle que :

1 Séparation : ∀(x, y) ∈ E 2 : d(x, y) = 0 ssi x = y

2 Symétrie : ∀(x, y) ∈ E 2 : d(x, y) = d(y, x)
3 Inégalité triangulaire : ∀(x, y, z) ∈ E 3 : d(x, z) ≤ d(x, y) + d(y, z)

Une dissimilarité est une application qui a les propriétés de la distance

sauf éventuellement l’inégalité triangulaire.
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance et Dissimilarité

Distance
On appelle distance sur un ensemble E, une application d : E × E ← R+
telle que :

1 Séparation : ∀(x, y) ∈ E 2 : d(x, y) = 0 ssi x = y

2 Symétrie : ∀(x, y) ∈ E 2 : d(x, y) = d(y, x)
3 Inégalité triangulaire : ∀(x, y, z) ∈ E 3 : d(x, z) ≤ d(x, y) + d(y, z)

Une dissimilarité est une application qui a les propriétés de la distance

sauf éventuellement l’inégalité triangulaire.
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance et Dissimilarité

Distance
On appelle distance sur un ensemble E, une application d : E × E ← R+
telle que :

1 Séparation : ∀(x, y) ∈ E 2 : d(x, y) = 0 ssi x = y

2 Symétrie : ∀(x, y) ∈ E 2 : d(x, y) = d(y, x)
3 Inégalité triangulaire : ∀(x, y, z) ∈ E 3 : d(x, z) ≤ d(x, y) + d(y, z)

Une dissimilarité est une application qui a les propriétés de la distance

sauf éventuellement l’inégalité triangulaire.
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance et Dissimilarité

Distance
On appelle distance sur un ensemble E, une application d : E × E ← R+
telle que :

1 Séparation : ∀(x, y) ∈ E 2 : d(x, y) = 0 ssi x = y

2 Symétrie : ∀(x, y) ∈ E 2 : d(x, y) = d(y, x)
3 Inégalité triangulaire : ∀(x, y, z) ∈ E 3 : d(x, z) ≤ d(x, y) + d(y, z)

Une dissimilarité est une application qui a les propriétés de la distance

sauf éventuellement l’inégalité triangulaire.
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Définir une distance sur chacun des attributs :

Distance : d(x, y) = |x − y|,
|x−y|
Distance normalisée : d(x, y) = dmax

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Définir une distance sur chacun des attributs :

Distance : d(x, y) = |x − y|,
|x−y|
Distance normalisée : d(x, y) = dmax

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Définir une distance sur chacun des attributs :

Distance : d(x, y) = |x − y|,
|x−y|
Distance normalisée : d(x, y) = dmax
Exemple : Age, taille, poids.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Attributs discrets :
Données binaires : d(0, 0) = d(1, 1) = 0, d(0, 1) = d(1, 0) = 1.
Données énumératives : distance nulle si les valeurs sont égales et 1 sinon.
Données énumératives ordonnées : On peut définir une distance utilisant la
relation d’ordre.
Données de types complexes : textes, images, données génétiques,
. . . etc.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Attributs discrets :
Données binaires : d(0, 0) = d(1, 1) = 0, d(0, 1) = d(1, 0) = 1.
Données énumératives : distance nulle si les valeurs sont égales et 1 sinon.
Données énumératives ordonnées : On peut définir une distance utilisant la
relation d’ordre.
Données de types complexes : textes, images, données génétiques,
. . . etc.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Attributs discrets :
Données binaires : d(0, 0) = d(1, 1) = 0, d(0, 1) = d(1, 0) = 1.
Données énumératives : distance nulle si les valeurs sont égales et 1 sinon.
Données énumératives ordonnées : On peut définir une distance utilisant la
relation d’ordre.
Données de types complexes : textes, images, données génétiques,
. . . etc.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Attributs discrets :
Données binaires : d(0, 0) = d(1, 1) = 0, d(0, 1) = d(1, 0) = 1.
Données énumératives : distance nulle si les valeurs sont égales et 1 sinon.
Données énumératives ordonnées : On peut définir une distance utilisant la
relation d’ordre.
Données de types complexes : textes, images, données génétiques,
. . . etc.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Choix d’une Distance

Attributs discrets :
Données binaires : d(0, 0) = d(1, 1) = 0, d(0, 1) = d(1, 0) = 1.
Données énumératives : distance nulle si les valeurs sont égales et 1 sinon.
Données énumératives ordonnées : On peut définir une distance utilisant la
relation d’ordre.
Données de types complexes : textes, images, données génétiques,
. . . etc.

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Standardiser les données

Calculer l’écart absolu moyen :
Sf = n1 (|x1f − Mf | + |x2f − Mf | + · · · + |xnf − Mf |) où
Mf = n1 (x1f + x2f + · · · + xnf )
xif −Mf
Calculer la mesure standardisée (z-score) : zif = Sf
Utiliser une distance : Soient x = (x1 , . . . , xn ) et y = (y1 , . . . , yn )
qP
n 2
Distance Euclidienne : d(x, y) = i=1 (xi − yi )
Pn
Distance de Manhattan : d(x, y) = i=1 |xi − yi |
qP
n q
i=1 |xi − yi |
q
Distance de Minkowski : d(x, y) =

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Standardiser les données

Calculer l’écart absolu moyen :
Sf = n1 (|x1f − Mf | + |x2f − Mf | + · · · + |xnf − Mf |) où
Mf = n1 (x1f + x2f + · · · + xnf )
xif −Mf
Calculer la mesure standardisée (z-score) : zif = Sf
Utiliser une distance : Soient x = (x1 , . . . , xn ) et y = (y1 , . . . , yn )
qP
n 2
Distance Euclidienne : d(x, y) = i=1 (xi − yi )
Pn
Distance de Manhattan : d(x, y) = i=1 |xi − yi |
qP
n q
i=1 |xi − yi |
q
Distance de Minkowski : d(x, y) =

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Standardiser les données

Calculer l’écart absolu moyen :
Sf = n1 (|x1f − Mf | + |x2f − Mf | + · · · + |xnf − Mf |) où
Mf = n1 (x1f + x2f + · · · + xnf )
xif −Mf
Calculer la mesure standardisée (z-score) : zif = Sf
Utiliser une distance : Soient x = (x1 , . . . , xn ) et y = (y1 , . . . , yn )
qP
n 2
Distance Euclidienne : d(x, y) = i=1 (xi − yi )
Pn
Distance de Manhattan : d(x, y) = i=1 |xi − yi |
qP
n q
i=1 |xi − yi |
q
Distance de Minkowski : d(x, y) =

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données numériques

Exemple :
Age Salaire
P1 50 11000
Calculer d(P1,P2), d(P1,P3) sans P2 70 11100
P3 60 11122
standardiser les données : P4 60 11074
Conclusion : P1 ressemble plus à P2
qu’à P3 d(P1,P2)=120 d(P1,P3)=132
Calculer d(P1,P2), d(P1,P3) après avoir Age Salaire
standardisé les données : P1 -2 -2
P2 2 0.7
Conclusion : P1 ressemble plus à P3 P3 0 1.3
P4 0 0
qu’à P2
d(P1,P2)=6.7 d(P1,P3)=4.3
M. Ledmi Introduction à la fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Coefficient de correspondance
simple : (similarité invariante, si la
variable binaire est symétrique) :
Objet J
b+c
d(i, j) = 1 0 Somme
a+b+c+d 1 a b a+b
Objet I
Coefficient de Jaccard : (similarité 0 c d c+d
Somme a+c b+d n
non invariante, si la variable binaire est
asymétrique) : Table – Table de dissimilarité

b+c
d(i, j) =
a+b+c

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Coefficient de correspondance
simple : (similarité invariante, si la
variable binaire est symétrique) :
Objet J
b+c
d(i, j) = 1 0 Somme
a+b+c+d 1 a b a+b
Objet I
Coefficient de Jaccard : (similarité 0 c d c+d
Somme a+c b+d n
non invariante, si la variable binaire est
asymétrique) : Table – Table de dissimilarité

b+c
d(i, j) =
a+b+c

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Exemple :
Nom Fièvre Toux Test-1 Test-2 Test-3 Test-4
Salim Oui N P N N N
Karima Oui N P N P N
Ali Oui P N N N N

Table – Table de patients

Calculer la distance entre patients, basée sur le coefficient de Jaccard.

0+1
d(Salim, Karima) = = 0.33
2+0+1
1+1
d(Salim, Ali) = = 0.67
1+1+1
2+1
d(Karima, Ali) = = 0.75
M. Ledmi 1Introduction
+ 2 +à la1fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Exemple :
Nom Fièvre Toux Test-1 Test-2 Test-3 Test-4
Salim Oui N P N N N
Karima Oui N P N P N
Ali Oui P N N N N

Table – Table de patients

Calculer la distance entre patients, basée sur le coefficient de Jaccard.

0+1
d(Salim, Karima) = = 0.33
2+0+1
1+1
d(Salim, Ali) = = 0.67
1+1+1
2+1
d(Karima, Ali) = = 0.75
M. Ledmi 1Introduction
+ 2 +à la1fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Exemple :
Nom Fièvre Toux Test-1 Test-2 Test-3 Test-4
Salim Oui N P N N N
Karima Oui N P N P N
Ali Oui P N N N N

Table – Table de patients

Calculer la distance entre patients, basée sur le coefficient de Jaccard.

0+1
d(Salim, Karima) = = 0.33
2+0+1
1+1
d(Salim, Ali) = = 0.67
1+1+1
2+1
d(Karima, Ali) = = 0.75
M. Ledmi 1Introduction
+ 2 +à la1fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données binaires

Exemple :
Nom Fièvre Toux Test-1 Test-2 Test-3 Test-4
Salim Oui N P N N N
Karima Oui N P N P N
Ali Oui P N N N N

Table – Table de patients

Calculer la distance entre patients, basée sur le coefficient de Jaccard.

0+1
d(Salim, Karima) = = 0.33
2+0+1
1+1
d(Salim, Ali) = = 0.67
1+1+1
2+1
d(Karima, Ali) = = 0.75
M. Ledmi 1Introduction
+ 2 +à la1fouille de données
 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données énumératives

Généralisation des variables binaires, avec plus de 2 états : rouge,

jaune, bleu, vert . . . etc.
Méthode 1 : Correpondance simple m : # de correspondances, p :
# total de variables
p−m
d(i, j) =
p
Méthode 2 : Utiliser un grand nombre de variables binaires :
Créer une variable binaire pour chaque modalité (ex : variable rouge qui prend
les valeurs vrai ou faux).

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données énumératives

Généralisation des variables binaires, avec plus de 2 états : rouge,

jaune, bleu, vert . . . etc.
Méthode 1 : Correpondance simple m : # de correspondances, p :
# total de variables
p−m
d(i, j) =
p
Méthode 2 : Utiliser un grand nombre de variables binaires :
Créer une variable binaire pour chaque modalité (ex : variable rouge qui prend
les valeurs vrai ou faux).

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données énumératives

Généralisation des variables binaires, avec plus de 2 états : rouge,

jaune, bleu, vert . . . etc.
Méthode 1 : Correpondance simple m : # de correspondances, p :
# total de variables
p−m
d(i, j) =
p
Méthode 2 : Utiliser un grand nombre de variables binaires :
Créer une variable binaire pour chaque modalité (ex : variable rouge qui prend
les valeurs vrai ou faux).

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Distance : Données énumératives

Généralisation des variables binaires, avec plus de 2 états : rouge,

jaune, bleu, vert . . . etc.
Méthode 1 : Correpondance simple m : # de correspondances, p :
# total de variables
p−m
d(i, j) =
p
Méthode 2 : Utiliser un grand nombre de variables binaires :
Créer une variable binaire pour chaque modalité (ex : variable rouge qui prend
les valeurs vrai ou faux).

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means (MacQueen’67) :

Entrées : un ensemble de m enregistrements

x1 , . . . , x m
1 Choisir k centres initiaux c1 , . . . , ck ;
2 Répartir chacun des m enregistrements dans le
groupe i dont le centre ci est le plus proche.;
3 Si aucun élément ne change de groupe alors arrêt et
sortir les groupes;
4 Calculer les nouveaux centres : pour tout i, ci est la
moyenne des éléments du groupe i.;
5 Aller en 2.;

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means
Exemple :
8 points A, B, . . . , H de l’espace euclidien 2D. k = 2 (2 groupes)
Tire aléatoirement 2 centres : B et D choisi.
Point Centre Centre Centre
B(2,2) D(2,4) J(7/4,12/4)
D(2,4) I(27/7,17/7) K(22/4,9/4)
A(1,3) B D J
B(2,2) B D J
C(2,3) B D J
D(2,4) D D J
E(4,2) B I K
F(5,2) B I K
G(6,2) B I K
H(7,3) B I K

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means
Exemple :
8 points A, B, . . . , H de l’espace euclidien 2D. k = 2 (2 groupes)
Tire aléatoirement 2 centres : B et D choisi.
Point Centre Centre Centre
B(2,2) D(2,4) J(7/4,12/4)
D(2,4) I(27/7,17/7) K(22/4,9/4)
A(1,3) B D J
B(2,2) B D J
C(2,3) B D J
D(2,4) D D J
E(4,2) B I K
F(5,2) B I K
G(6,2) B I K
H(7,3) B I K

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means
Exemple :
8 points A, B, . . . , H de l’espace euclidien 2D. k = 2 (2 groupes)
Tire aléatoirement 2 centres : B et D choisi.
Point Centre Centre Centre
B(2,2) D(2,4) J(7/4,12/4)
D(2,4) I(27/7,17/7) K(22/4,9/4)
A(1,3) B D J
B(2,2) B D J
C(2,3) B D J
D(2,4) D D J
E(4,2) B I K
F(5,2) B I K
G(6,2) B I K
H(7,3) B I K

M. Ledmi Introduction à la fouille de données

 Introduction
Problématique
Segmentation (Clustering)
Distance et Dissimilarité
Algorithme k-Means

Algorithme k-Means
Exemple :
8 points A, B, . . . , H de l’espace euclidien 2D. k = 2 (2 groupes)
Tire aléatoirement 2 centres : B et D choisi.
Point Centre Centre Centre
B(2,2) D(2,4) J(7/4,12/4)
D(2,4) I(27/7,17/7) K(22/4,9/4)
A(1,3) B D J
B(2,2) B D J
C(2,3) B D J
D(2,4) D D J
E(4,2) B I K
F(5,2) B I K
G(6,2) B I K
H(7,3) B I K

M. Ledmi Introduction à la fouille de données