16/01/2022

IND6212
Valorisation de données industrielles
Bruno Agard
Laboratoire en Intelligence des Données ([Link]
Département de Mathématiques et Génie Industriel
École Polytechnique de Montréal
[Link]@[Link]

Bruno Agard IND6212 - Valorisation de données industrielles 1/X

Segmentation
Clustering

Bruno Agard IND6212 - Valorisation de données industrielles 2/X

1
 16/01/2022

Prédiction
X1 X2 X3 Y1
C1 1 0 1 2
X1 X2 X3 Y1
C2 1 1 0 3
C1 1 0 1 2
C3 1 0 1 2
C2 1 1 0 3
C4 1 0 1 2
C3 1 0 1 2
C5 1 0 .. 2
C4 1 0 1 ..
C6 .. 1 0 3
C5 1 0 .. 2
C7 1 1 0 4
C6 .. 1 0 3
C7 1 1 0 4 Segmentation
X1 X2 X3 Y1
C1 1 0 1 2
C2 1 1 0 3
Description
C3 1 0 1 2
If X1=1 then X3 =1 [6, 3/6] C4 1 0 1 ..
If (X1=1 and X2=0) then X3=1 [3, 3/3] C5 1 0 .. 2
If X1=1 then !X1=0 [6, 100%]
C6 .. 1 0 3
….
C7 1 1 0 4

Bruno Agard IND6212 - Valorisation de données industrielles 3/X

Sommaire

• Introduction/Définitions
• Métriques
• Classification des algorithmes
• Exemples de méthodes…
• Conclusions

Bruno Agard IND6212 - Valorisation de données industrielles 4/X

2
 16/01/2022

Introduction/
Définitions

Bruno Agard IND6212 - Valorisation de données industrielles 5/X

Introduction/Définitions

• La segmentation (clustering) a pour but de partager un ensemble de

données en plus petits groupes d’objets similaires.

• Principe:
• Maximiser l’homogénéité à l’intérieur de chaque groupe
• Minimiser une distance interne
• Maximiser l’hétérogénéité entre les groupes
• Maximiser une distance externe

• => simplification, mais perte de détails

• Niveau d’agrégation, nombre de groupes (clusters)

Bruno Agard IND6212 - Valorisation de données industrielles 6/X

3
 16/01/2022

Métriques

Entre deux points

Entre un point et un ensemble

Bruno Agard IND6212 - Valorisation de données industrielles 7/X

Métriques

• Il existe de très nombreuses métriques, qui dépendent :

• Du type de données: numériques, discrètes (oui/non, rouge/noir/vert)
• Du type d’éléments: point/groupe
• Du type de partition désirée

Bruno Agard IND6212 - Valorisation de données industrielles 8/X

4
 16/01/2022

Distances entre deux points

• Distance Euclidienne d ( x1 , x2 ) = å (x i
1,i - x2,i ) 2

• Distance de Manhattan d ( x1 , x2 ) = å x1,i - x2,i

i
• Distances de Hamming "
𝛿𝑖 = 0, 𝑖𝑓𝑥#,! == 𝑥%,!
𝑑1 𝑥1, 𝑥2 = % 𝛿𝑖, 𝑤𝑖𝑡ℎ + Nombre de coordonnées différentes
𝛿𝑖 = 1, 𝑒𝑙𝑠𝑒
!
d1 ( x1 , x2 )
d 2 ( x1 , x2 ) = Pourcentage de coordonnées différentes
n
" 𝛿𝑖 = 𝑝, 𝑖𝑓𝑥#,! == 𝑥%,! == 1
Nombre pondéré de coordonnées identiques
𝑑3 𝑥1, 𝑥2 = % 𝛿𝑖, 𝑤𝑖𝑡ℎ 2𝛿𝑖 = 1, 𝑖𝑓𝑥#,! == 𝑥%,! == 0
! 𝛿𝑖 = 0, 𝑒𝑙𝑠𝑒
𝑑4 𝑥1, 𝑥2 = ⋯
• …
Bruno Agard IND6212 - Valorisation de données industrielles 9/X

Distances d’un point à un ensemble

B
• Plus proche voisin (single linkage) A
C

B
• Voisin le plus éloigné (complete linkage) A
C

B
• Distance moyenne (average linkage) A
C

B
• Distance au centre de gravité A
C
•…

Bruno Agard IND6212 - Valorisation de données industrielles 10/X

10

5
 16/01/2022

Distances entre 2 groupes

G2
G1 B
• Plus proche voisin (single linkage) A
C
𝐷 = 𝑚𝑖𝑛 𝑑 𝑃𝑖 , 𝑃𝑗 , ∀𝑃𝑖 ∈ 𝐺1, ∀𝑃𝑗 ∈ 𝐺2 D

• Voisin le plus éloigné (complete linkage) G1 B

G2
A
𝐷 = 𝑚𝑎𝑥 𝑑 𝑃𝑖 , 𝑃𝑗 , ∀𝑃𝑖 ∈ 𝐺1, ∀𝑃𝑗 ∈ 𝐺2 C
D
• Distance moyenne (average linkage)
G2
G1 B
∑67 69
5 ∑8 𝑑 𝑃𝑖, 𝑃𝑗
A
𝐷= C
𝑛1 + 𝑛2 D

• Distance des centres de gravité G2

G1 B
A
𝐷 = 𝑑(𝜃1, 𝜃2) C
D
• Attention : Distance Ward : minimise la variance des groupes fusionnés
•…
Bruno Agard IND6212 - Valorisation de données industrielles 11/X

11

Principe

• Maximiser l’homogénéité à l’intérieur de chaque groupe, devient:

• Minimiser les d(xi, xj), pour des xi, xj appartenant au même groupe
æ ö
minçç åå d ( xi , x j ) ÷÷ ?, min (max(d ( xi , x j ) )) ?, ...
è i j ø

• Maximiser l’hétérogénéité entre les groupes, devient

• Maximiser D, entre les groupes,
æ ö
maxçç åå d ( xi , x j ) ÷÷ ?, max (min (d ( xi , x j ) )) ?, ...
è i j ø
xi Î G1 , x j Î G2

Bruno Agard IND6212 - Valorisation de données industrielles 12/X

12

6
 16/01/2022

Classification des algorithmes

Bruno Agard IND6212 - Valorisation de données industrielles 13/X

13

Algorithm classification

• Méthodes par partitionnement

• K-means
• Minibatch K-means
• K-medoids (PAM)
• CLARA
• Méthodes hiérarchiques
• Algorithmes par agglomération (CHA, CURE)
• Algorithmes par division (BIRCH)
• Algorithmes basés sur la densité
• DBSCAN
• OPTICS
• Méthodes par grilles
• STING
• CLIQUE

Bruno Agard IND6212 - Valorisation de données industrielles 14/X

14

7
 16/01/2022

Méthodes par
partitionnement

Bruno Agard IND6212 - Valorisation de données industrielles 15/X

15

K-means

Bruno Agard IND6212 - Valorisation de données industrielles 16/X

16

8
 16/01/2022

Méthode K-means

• Principe
• Nombre de classes connu
• Rechercher des classes homogènes
• Données de base
• Matrice de points
• Points connu en coordonnées
• Métrique (distance)
• Pb
• Non unicité de la solution, le résultat dépends des points de départ

Bruno Agard IND6212 - Valorisation de données industrielles 17/X

17

Algorithme (MacQueen, 1967)

• Initialisation
• N centres de classes = N premiers points
• Déterminer les classes
• stable = faux
• Tant que non stable faire
• Début : calculer les centres de classes
• Affecter chaque point au centre le plus proche
• Si les classes évoluent Alors stable = faux
• Sinon stable = vrai
• Fin
• Fin

Bruno Agard IND6212 - Valorisation de données industrielles 18/X

18

9
 16/01/2022

Exemple

Bruno Agard IND6212 - Valorisation de données industrielles 27/X

27

Propriétés
• K-means peut converger vers un optimum local.
• Le problème peut être résolu en choisissant de meilleurs point de
départ (choix judicieux, chance, exhaustivité).
• Le nombre de clusters est une donnée de la méthode, il dépend de la
granularité escomptée de l’analyse.
K-means

Bruno Agard IND6212 - Valorisation de données industrielles 28/X

28

10
 16/01/2022

Mini-Batch K-Means

Bruno Agard IND6212 - Valorisation de données industrielles 29/X

29

Mini Batch K-means

• Utilise de petits lots aléatoires de données de taille fixe, afin qu'ils

puissent être stockés en mémoire.

• Pour chaque itération

• Sélectionnez un nouvel échantillon aléatoire dans l'ensemble de données
• Mettre à jour les clusters Mini Batch K-means
• Répéter jusqu'à convergence

Bruno Agard IND6212 - Valorisation de données industrielles 30/X

30

11
 16/01/2022

Difference between k-means and

minibatch k-means

From [Link]

Bruno Agard IND6212 - Valorisation de données industrielles 31/X

31

K-MEDOIDS

Bruno Agard IND6212 - Valorisation de données industrielles 32/X

32

12
 16/01/2022

Principe K-medoids

• PAM: Partitioning Around Medoids

• Il faut connaitre k, le nombre de groupes

• Trouver un élément dans chaque cluster, pour représenter le groupe: medoid

• Le point medoid est celui qui dans le groupe minimise la distance aux autres points du
groupe

• Particularités:
• Choix des points de départ
• Choix de la métrique
• Choix du représentant

Bruno Agard IND6212 - Valorisation de données industrielles 33/X

33

Algorithme
(Kaufman et Rousseeuw, 1987)
• On considère le critère d’erreur suivant:
k
E = å å d ( p, mi ) 2
i =1 pÎCi
• Algorithme
• Initialisation
• Choisir K représentants, appelés medoids
• Tant que non stable faire
• Affecter tout les points restants au medoid le plus proche
• Sélectionner un point non medoid et interchanger si le critère d’erreur diminue
• Si le critère d’erreur ne peut plus diminuer stable = vrai

Bruno Agard IND6212 - Valorisation de données industrielles 34/X

34

13
 16/01/2022

PAM example
J. Han and M. Kamber

E’-E<0

E’-E>0

E’-E<0

Bruno Agard IND6212 - Valorisation de données industrielles 35/X

35

Exemple PAM

Bruno Agard IND6212 - Valorisation de données industrielles 36/X

36

14
 16/01/2022

CLARA

Bruno Agard IND6212 - Valorisation de données industrielles 37/X

37

CLARA

• CLARA (Clustering LARge Applications)

• Kaufmann and Rousseeuw, 1990
• Tire des échantillons successifs de la base et applique PAM à chaque
échantillon
• retourne le meilleur partitionnement obtenu

• Rq:
• La qualité du résultat dépend de la taille de l’échantillon
• Si les échantillons ne sont pas représentatifs de l’ensemble de la population, le
résultat est biaisé

Bruno Agard IND6212 - Valorisation de données industrielles 38/X

38

15
 16/01/2022

Méthodes hiérarchiques

Bruno Agard IND6212 - Valorisation de données industrielles 39/X

39

Classification hiérarchique

• Créer une chaîne de partitions

• Au sommet une seule classe
• En bas, autant de classes que de points
• Entre, une partition décompose l’autre
• Approches
• Méthodes d’agglomération
• Méthodes de division
• Permet de choisir le niveau de découpage
• Représentation sur un dendrogramme

Bruno Agard IND6212 - Valorisation de données industrielles 40/X

40

16
 16/01/2022

Algorithmes par agglomération

CHA – Classification hiérarchique ascendante

Bruno Agard IND6212 - Valorisation de données industrielles 41/X

41

CHA

• Algorithme:
1. Initialisation:
• Chaque individu forme un cluster
• Calcul de la matrice de proximité entre chaque paire de points
2. Fusion:
• Sélectionner les deux points les plus proches
• Fusionner les deux points en question dans un cluster
• Mettre à jour la matrice de proximité
3. Arrêter lorsqu’il ne reste plus qu’un cluster

Bruno Agard IND6212 - Valorisation de données industrielles 42/X

42

17
 16/01/2022

Exemple
Machines
a b c d e f g h i j k
1 1 1 0 0 1 1 0 1 0 1 0
2 1 0 0 0 1 0 0 0 1 1 0

Produits
3
4
0
1
1
0
0
0
0
1
0
1
1
0
1
0
1
1
0
0
1
0
0
1
Distances
5 0 1 1 1 1 0 1 0 1 1 0 de Hamming
6 0 1 0 1 1 1 1 0 0 0 0
7 1 1 0 1 1 1 1 0 1 1 1
8 1 1 1 1 1 1 1 1 0 0 1

1 2 3 4 5 6 7 8
Étape 1 1 0 4 3 5 7 5 5 5
2 4 0 7 5 5 7 5 9
3 3 7 0 8 6 4 6 6
4 5 5 8 0 8 6 6 4
5 7 5 6 8 0 4 4 6
6 5 7 4 6 4 0 4 4
7 5 5 6 6 4 4 0 4
8 5 9 6 4 6 4 4 0

Bruno Agard IND6212 - Valorisation de données industrielles 43/X

43

Ultramétrique supérieure minimale

Voisin le plus éloigné – complete link

Étape 1 - suite
1 2 3 4 5 6 7 8 1;3 2 4 5 6 7 8
1 0 4 3 5 7 5 5 5 1;3 0 7 3 8 7 5 6 6
2 4 0 7 5 5 7 5 9 2 7 0 7 5 5 7 5 9
3 3 7 0 8 6 4 6 6 3 7 0 8 6 4 6 6
4 5 5 8 0 8 6 6 4 4 8 5 8 0 8 6 6 4
5 7 5 6 8 0 4 4 6 5 7 5 6 8 0 4 4 6
6 5 7 4 6 4 0 4 4 6 5 7 4 6 4 0 4 4
7 5 5 6 6 4 4 0 4 7 6 5 6 6 4 4 0 4
8 5 9 6 4 6 4 4 0 8 6 9 6 4 6 4 4 0

Distance de 2
Groupe (1,3):
Au groupe (1,3):
Distance=3
Max(d(2,1),d(2,3))

Bruno Agard IND6212 - Valorisation de données industrielles 44/X

44

18
 16/01/2022

Ultramétrique supérieure minimale

Voisin le plus éloigné – complete link
Étape 2
1;3 2 4 5 6 7 8 1;3 2 4 5 6 7;8
1;3 0 7 8 7 5 6 6 1;3 0 7 8 7 5 6 6
2 7 0 5 5 7 5 9 2 7 0 5 5 7 9 9
4 8 5 0 8 6 6 4 4 8 5 0 8 6 6 4
5 7 5 8 0 4 4 6 5 7 5 8 0 4 6 6
6 5 7 6 4 0 4 4 6 5 7 6 4 0 4 4
7 6 5 6 4 4 0 4 7;8 6 9 6 6 4 0 4
8 6 9 4 6 4 4 0 6 9 4 6 4 4 0

Étape 3
1;3 2 4 5 6 7;8 1;3 2 4 5 6;7;8
1;3 0 7 8 7 5 6 1;3 0 7 8 7 6 6
2 7 0 5 5 7 9 2 7 0 5 5 9 9
4 8 5 0 8 6 6 4 8 5 0 8 6 6
5 7 5 8 0 4 6 5 7 5 8 0 6 6
6 5 7 6 4 0 4 6;7;8 6 9 6 6 0 4
7;8 6 9 6 6 4 0 6 9 6 6 4 0

Bruno Agard IND6212 - Valorisation de données industrielles 45/X

45

Ultramétrique supérieure minimale

Voisin le plus éloigné – complete link
Etape 4
1;3 2 4 5 6;7;8 1;3 2;4 5 6;7;8
1;3 0 7 8 7 6 1;3 0 8 8 7 6
2 7 0 5 5 9 2;4 8 0 5 8 9
4 8 5 0 8 6 8 5 0 8 6
5 7 5 8 0 6 5 7 8 8 0 6
6;7;8 6 9 6 6 0 6;7;8 6 9 6 6 0

Etape 5
1;3 2;4 5 6;7;8 1;3 2;4 5;6;7;8
1;3 0 8 7 6 1;3 0 8 7 6
2;4 8 0 8 9 2;4 8 0 9 9
5 7 8 0 6 5;6;7;8 7 9 0 6
6;7;8 6 9 6 0 6 9 6 0

Etape 6
1;3 2;4 5;6;7;8 2;4 1;3;5;6;7;8
1;3 0 8 7 0 8 7
2;4 8 0 9 2;4 8 0 9
5;6;7;8 7 9 0 1;3;5;6;7;8 7 9 0

Bruno Agard IND6212 - Valorisation de données industrielles 46/X

46

19
 16/01/2022

Resultat

Dendrogram

CHA

Bruno Agard IND6212 - Valorisation de données industrielles 47/X

47

From [Link]

Bruno Agard IND6212 - Valorisation de données industrielles 48/X

48

20
 16/01/2022

Algorithmes par agglomération

CURE

Supports à partir de Clément Piriou

Bruno Agard IND6212 - Valorisation de données industrielles 49/X

49

Introduction

• CURE: Clustering Using REprentatives

• Guha, Rastogi, Shim, « CURE: an efficient clustering algorithm for
large database », 2000

Bruno Agard IND6212 - Valorisation de données industrielles 50/X

50

21
 16/01/2022

Présentation

• Segmentation en k groupes
• Méthode hiérarchique par agglomération
• Chaque cluster est représenté non pas par sa moyenne mais par c
éléments du cluster «bien répartis»
• Métrique quelconque pour la distance entre deux individus
(Euclidienne, Manhattan, Hamming…)

Bruno Agard IND6212 - Valorisation de données industrielles 51/X

51

Métriques

dist ( p, u ) = min (dist (cu , p ))

cu Îcaract (u )

dist (u , v) = min (dist (cu , cv ))

cu Îcaract ( u ) , cv Îcaract ( v )

Bruno Agard IND6212 - Valorisation de données industrielles 52/X

52

22
 16/01/2022

L’algorithme

• Initialisation
• Chaque individu forme un cluster

• Tant que nombre de clusters >k, faire:

• Fusion des 2 clusters les plus proches
• Sélection des c nouveaux représentants « bien répartis »
• Si le nombre d’individus dans le cluster < c, tous les individus sont caractéristiques
• Sinon
• Initialisation: le premier représentant est le point le plus éloigné de la moyenne
• Pour i = 2 à c
• Sélectionnez le point avec la distance maximale des représentants réels
• Ajouter le nouveau point sélectionné à la liste des représentants

Bruno Agard IND6212 - Valorisation de données industrielles 53/X

53

Sélection des 5 représentants « bien répartis »

dans le cluster w

Ce point devient un point caractéristique.

On a bien trouver nos 5 points caractéristiques qui sont bien

répartis sur l’ensemble du cluster.

Bruno Agard IND6212 - Valorisation de données industrielles 54/X

54

23
 16/01/2022

Revenons à l’algorithme

• Initialisation
• Chaque individu forme un cluster
• Tant que nombre de clusters >k, faire:
• Fusion des 2 clusters les plus proches
• Sélection des c nouveaux représentants « bien répartis »

Bruno Agard IND6212 - Valorisation de données industrielles 66/X

66

Améliorations suggérées dans l’article

• Formes complexes
• K-means et HAC seulement pour les formes « sphériques »
• Mais fonctionne mal pour les formes convexes

• Mais, les points abérants deviennent les « meilleurs représentants du

groupe »
• utilisation d’un facteur alpha pour diminuer l’importance du bruit (points isolés)
• Recommndtion : alpha (entre 0,2 et 0,7)
• Pour accélérer le processus
• Les c nouveaux représentants du groupe sont choisis parmi les 2c représentants des
groupes fusionnés.
• Recommandation : c > 10
Bruno Agard IND6212 - Valorisation de données industrielles 67/X

67

24
 16/01/2022

Algorithmes par division

BIRCH

Bruno Agard IND6212 - Valorisation de données industrielles 68/X

68

BIRCH

• Semblable au regroupement par agglomérations du CHA, mais inversé.

• Tous les points appartiennent au même cluster
• À chaque itération, un groupe est divisé en sous-groupes
BIRCH

Bruno Agard IND6212 - Valorisation de données industrielles 69/X

69

25
 16/01/2022

Méthodes par densité

Bruno Agard IND6212 - Valorisation de données industrielles 70/X

70

Algorithmes par densité

DBSCAN

Bruno Agard IND6212 - Valorisation de données industrielles 71/X

71

26
 16/01/2022

Méthodes par densité

• Principe:
• Utilisation de la densité à la place de la distance
• Un point est voisin d’un autre s’il est à une distance inférieure à une valeur
fixée
• Un point est dense si le nombre de ses voisins dépasse un certain seuil
• Paramètres de densité:
• Rayon
• Nombre minimal de points q
p

p est dense, q ne l’est pas

Bruno Agard IND6212 - Valorisation de données industrielles 72/X

72

Principe DBSCAN

• Faire:
1. Sélection aléatoire d’un point dense
2. Tous les points atteignables à partir de ce point, forment un cluster, et sont
retirés de l’espace
3. Recommencer en 1, jusqu’à ce que tous les points soit retirés

Bruno Agard IND6212 - Valorisation de données industrielles 73/X

73

27
 16/01/2022

DBSCAN

DBSCAN

Bruno Agard IND6212 - Valorisation de données industrielles 74/X

74

Comparaison K-means et DBSCAN

J. Han and M. Kamber

Résultat de K-means Résultat de Density

Bruno Agard IND6212 - Valorisation de données industrielles 75/X

75

28
 16/01/2022

Algorithmes par densité

OPTICS

Bruno Agard IND6212 - Valorisation de données industrielles 76/X

76

OPTICS

• OPTICS (Ordering Points To Identify the Clustering Structure)

OPTICS
• Semblable au DBSCAN :
• Trouve des éléments de haute densité et en développe des grappes
• Mais, garde la hiérarchie des clusters

Bruno Agard IND6212 - Valorisation de données industrielles 77/X

77

29
 16/01/2022

Méthodes par grilles

Bruno Agard IND6212 - Valorisation de données industrielles 78/X

78

Algorithmes par grilles

STING

Bruno Agard IND6212 - Valorisation de données industrielles 79/X

79

30
 16/01/2022

STING: Principe

• STING: A Statistical Information Grid Approach

• Wang, Yang and Muntz (VLDB’97)
• L’espace est divisé en cellules rectangulaires
• Il y a différents niveaux de cellules qui correspondent à
différents niveaux de résolution

J. Han and M. Kamber

Bruno Agard IND6212 - Valorisation de données industrielles 80/X

80

STING: Algorithme

• Chaque cellule à un niveau supérieur est divisé en des cellules plus petites au
niveau inférieur
• Les informations statistiques de chaque cellule sont calculées et stockées
• Nombre d’éléments, min, max, moyenne, écart-type, …
• Type de distribution (normale, exponentielle, uniforme, …)
• Par affinages successifs
• On détermine la probabilité que les cellules du niveau inférieur soit denses
• On supprime les cellules non denses

Bruno Agard IND6212 - Valorisation de données industrielles 81/X

81

31
 16/01/2022

Algorithmes par grilles

CLIQUE

Supports à partir de Claude McKenzie

Bruno Agard IND6212 - Valorisation de données industrielles 82/X

82

CLIQUE

• CLIQUE = CLustering In QUEst

• Basé sur:
• la division de l’espace en sous-espaces égaux (grille) – Grid based
• mais aussi sur la recherche de clusters, dérivé de APRIORI – Density based
• CLIQUE fut développé afin de traiter des bases de données dont les
entrées possèdent plusieurs dimensions (high dimensional data)

Bruno Agard IND6212 - Valorisation de données industrielles 83/X

83

32
 16/01/2022

CLIQUE : Algorithme

1. Partitionner l’espace de recherche en sous-espaces

2. Identifier les sous-espaces denses
3. Identifier les clusters
4. Générer des descriptions minimales des clusters… plus
compréhensibles pour les utilisateurs des données.

Bruno Agard IND6212 - Valorisation de données industrielles 84/X

84

CLIQUE: Définitions

• Unité : Après avoir formé une structure en grille dans l’espace, chaque
cellule rectangulaire est appelée UNITÉ. Chaque unité possède une taille
(T) définie par l’utilisateur…,
• Densité: Une UNITÉ est dense si la fraction totale des points qu’elle
contient égale ou exède le paramètre de densité (E), défini par
l’utilisateur…
• Cluster: Un CLUSTER est défini comme un maximum d’UNITÉS DENSES
interconnectés.

Bruno Agard IND6212 - Valorisation de données industrielles 85/X

85

33
 16/01/2022

Exemple de densité en 3-D

Bruno Agard IND6212 - Valorisation de données industrielles 86/X

86

Les CLUSTERS

• Sont formés par le groupement d’unités considérées comme denses.

• CLIQUE considère que si l’espace K est dense, les sous-espaces k-1 le
sont par association (idem a-priori).
• Les clusters sont générés à partir des régions denses avec
descripteurs couvrants 2 ou plus dimensions.

Bruno Agard IND6212 - Valorisation de données industrielles 87/X

87

34
 16/01/2022

CLIQUE

• Méthode mixte Grille & Densité

• Principe de base:
• Dans un sous-espace donné, une cellule est dense si le pourcentage d’objets qu’elle
contient est supérieur à un seuil donné è Tout sous-espace d'un espace dense est
dense
• On recherche les sous-espaces denses de dimension (k-1), puis on les intersecte
pour former les sous-espaces candidats de dimension k
• Sorte de généralisation de Apriori à N dimensions

Bruno Agard IND6212 - Valorisation de données industrielles 88/X

88

Forces et faiblesses de CLIQUE

• Forces
• Trouve automatiquement les unités les plus denses dans tous les sous espaces.
• Efficacité a regrouper les clusters
• Insensible à l’ordre d’entrée des données
• Peut travailler avec des données manquantes
• Fournit des descriptions des clusters compréhensible. pour les utilisateurs
• Faiblesse
• La précision dans la détection des Clusters dépend en grande partie du
positionnement de la grille dans l’espace (choix de la taille de la grille). Certains
auteurs soulignent aussi la trop grande simplicité de la méthode.

Bruno Agard IND6212 - Valorisation de données industrielles 89/X

89

35
 16/01/2022

Evaluation des résultats

Bruno Agard IND6212 - Valorisation de données industrielles 90/X

90

Index Silhouette

• Silhouette
• a: distance moyenne entre un élément et tous les autres points de la même classe.
• b: distance moyenne entre un élément et tous les autres points du groupe suivant le plus proche..
• Le Coefficient Silhouette s est donné par:
𝑏−𝑎
𝑠=
max(𝑎, 𝑏)
• Le coefficient de silhouette pour un ensemble d’éléments est donné par la moyenne du
coefficient de silhouette pour chaque élément.

• Le score est limité entre -1 pour un regroupement incorrect et +1 pour un regroupement très
dense.

• Des scores autour de zéro indiquent des groupes qui se chevauchent.

• Le score est plus élevé lorsque les groupes sont denses et bien séparés.

Bruno Agard IND6212 - Valorisation de données industrielles 91/X

91

36
 16/01/2022

Index Calinski-Harabasz

• rapport de la somme de la dispersion entre les groupes et de la

dispersion intergroupes pour tous les groupes
• (où la dispersion est définie comme la somme des distances au carré)

• Le score est plus élevé lorsque les grappes sont denses et bien
séparées, ce qui correspond à un concept standard de groupe.

Bruno Agard IND6212 - Valorisation de données industrielles 92/X

92

Index Davies-Bouldin

• Utilise :
• la distance moyenne entre chaque point du groupe et le centroïde de ce
groupe (diamètre du groupe).
• La distance entre les centres des groupes.

• Calcule un indice de "similarité" moyen entre les groupes

• (compare la distance entre les groupes avec la taille de ces groupes).

• Zéro est le score le plus bas possible. Des valeurs plus proches de zéro
indiquent une meilleure partition.

Bruno Agard IND6212 - Valorisation de données industrielles 93/X

93

37
 16/01/2022

• Ces indices permettent de comparer différents niveaux d'agrégation pour

une même méthode
Indexes

Bruno Agard IND6212 - Valorisation de données industrielles 94/X

94

Analyse des groupes

Bruno Agard IND6212 - Valorisation de données industrielles 95/X

95

38
 16/01/2022

Qualité des résultats

• Notation: N points M1..MN M i = (xi , j )i =1.. N , j =1..M

• K classes de cardinalité nk et de centre de gravité θk

æ 1 é ùö
q k = ççq k , j = êå xi , j ú ÷÷
è nk ë iÎk û ø j =1..M
• Deux indices : 1
• Dispersion des classes dk =
nk
å d ( M ,q
iÎk
i k )

• Dispersion inter classe Dk1,k 2 = d (q k1 , q k 2 )

Bruno Agard IND6212 - Valorisation de données industrielles 96/X

96

Analyse des groupes

• Taille du groupe
• Dispersion au sein d'un groupe
Analyses
• Dispersion entre les groupes
• Représentants d’un groupe

Bruno Agard IND6212 - Valorisation de données industrielles 97/X

97

39
 16/01/2022

Conclusions

Bruno Agard IND6212 - Valorisation de données industrielles 98/X

98

Rappels

• La segmentation (clustering) a pour but de partager un ensemble de

données en plus petits groupes d’objets similaires.
• Principe:
• Maximiser l’homogénéité à l’intérieur de chaque groupe
• Minimiser une distance interne
• Maximiser l’hétérogénéité entre les groupes
• Maximiser une distance externe
• Différents (nombreux) algorithmes, pas de méthode « idéale »

Bruno Agard IND6212 - Valorisation de données industrielles 99/X

99

40
 16/01/2022

Sélection des méthodes

• Méthodes par partitionnement

• K-means
Nombre de groupes, distance
• Minibatch K-means Vitesse
• K-medoids (PAM)
Nombre de groupes, distance
• CLARA + Échantillonnage
• Méthodes hiérarchiques
• Algorithmes par agglomération (CHA, CURE) Distance (points et groupes)
Dendrogramme
• Algorithmes par division (BIRCH) + nombre de représentants (CURE)

• Algorithmes basés sur la densité

• DBSCAN
Définir la densité
• OPTICS
Interprétation
• Méthodes par grilles
• STING
Construire la grille
• CLIQUE

Bruno Agard IND6212 - Valorisation de données industrielles 100/X

100

Partitions vs hiérarchies

Bruno Agard IND6212 - Valorisation de données industrielles 101/X

101

41
 16/01/2022

Densité vs grilles

Bruno Agard IND6212 - Valorisation de données industrielles 102/X

102

103 © 2020 Executive Education HEC Montréal. All rights reserved. From [Link]
Bruno Agard IND6212 - Valorisation de données industrielles 103/X

103

42