Chap 7 Classification (clustering)

1

Opérer des regroupements en classes homogènes d’un ensemble d’individus. Les données se présentent en général sous la forme d’un tableau individus variables.

2

3

4

1-Méthodes NON HIERARCHIQUES:

Partition en k classes Exemples : Centres mobiles Nuées dynamiques

Avantages : Permettent la classification d’ensembles volumineux.

Inconvénients : On impose au départ le nombre de classes.

5

2- Méthodes HIERARCHIQUES

6

Apprentissage Supervisé vs non supervisé

 Apprentissage Supervisé (classification)

 Supervision: les données d’apprentissage

(observations) sont accompagnés par les labels indiquant leurs classes

 Les nouvelles données sont classifiées en se basant

sur le training set

 Apprentissage non supervisé (regroupement)

 Le label de classe des éléments observés (training

set) n’est pas connu

 Le but est de déceler l’existence de classes ou

groupes dans les données

8

Un bon clustering ?

 Lorsqu’on garantit:

 Une grande similarité within

 Une faible similarité between

 La qualité d’un regroupement dépend donc de la

mesure de similarité utilisée par la méthode et de son implémentation

9

Structures de données



      



 Matrice de données

 Matrice de similarité



      





     



x ... x ... x 11 1f 1p

... ... ... ... ...

x ... x ... x i1 if ip

... ... ... ... ...

x ... x ... x n1 nf np

0

d(2,1) 0

d(3,1 ) d (,32) 0

: : :

d ( n 1,) d ( n 2,) ... ... 0



     



10

Métriques d’un clustering

 La similarité est évaluée par une mesure de

distance

 Les distances diffèrent selon le type de

variables: intervalles, qualitatives (catégorielles), binaires ou ordinales

11

1-Intervalle (numériques)

 Rendre la variable centrée réduite:

Calculer la mesure standardisée (z-score)

x 

if



x  m

if

z 

if f



if

~~s~~

f

12

Exemple

Col1	Age	Salaire
Personne1	-2	-0,5
Personne2	2	0,175
Personne3	0	0,324
Personne4	0	2

13

Similarité entre objets

 Ex: la distance de Minkowski :

où i= (x, x, …, x ) et j= (x, x, …, x ) sont deux i1 i2 ip j1 j2 jp

objets p-dimensionnels et qun entier positif

 Si q= 1, d est la distance de Manhattan

d,( i j )  |  x |  |  x |  ...  |  x | ix 1 j 1 ix 2 j 2 ixp jp

14

Similarité entre objets(I)

 Si q= 2, d est la distance Euclidienne:

 Propriétés

 d(i,j) 0

 d(i,i)= 0

 d(i,j)= d(j,i)

 d(i,j) d(i,k)+ d(k,j)

15

Exemple: distance de Manhattan

d(p1,p2)=120

d(p1,p3)=132

Conclusion: p1 ressemble plus à p2 qu’à p3

d(p1,p2)=4,675

d(p1,p3)=2,324

Conclusion: p1 ressemble plus à p3 qu’à p2 

16

Col1	Age	Salaire
Personne1	-2	-0,5
Personne2	2	0,175
Personne3	0	0,324
Personne4	0	0

2-Variables binaires

 Une table de contingence pour données binaires

1 0

sum

a b a  b

c d c  d

Objet j a= nombre de

0 sum

positions où i a 1





et

j a 1

Objet i

1

0

sum a  c b  d p

 Exemple o =(1,1,0,1,0) et o =(1,0,0,0,1) i j

a=1, b=2, c=1, d=1

17

Mesures de distances

 Coefficient d’appariement (matching) simple

(invariant pour variables symétriques):

b  ( i, j ) 

b  c d ( i, j )  a  b  c 

a  b  c  d

Exemple o =(1,1,0,1,0) et o =(1,0,0,0,1) i j

d(o, o )=3/5 i j

 Coefficient de Jaccard

d(o, o )=3/4 i j

b  c d ( i, j )  a  b 

b  ( i, j ) 

a  b  c

18

19

Variables binaires (I)

 Variable symétrique: Ex. le sexe d’une personne, i.e

coder masculin par 1 et féminin par 0 c’est pareil que le codage inverse

 Variable asymétrique: Ex. Test HIV. Le test peut être

positif ou négatif (0 ou 1) mais il y a une valeur qui sera plus présente que l’autre. Généralement, on code par 1 la modalité la moins fréquente

 2 personnes ayant la valeur 1 pour le test sont plus

similairesque 2 personnes ayant 0 pour le test

20

Variables binaires(II)

mple	Col2	Col3	Col4	Col5	Col6	Col7	Col8
Nom	Sexe M F M	Fièvre	Toux N N P	Test-1	Test-2 N N N	Test-3	Test-4 N N N
Jack Mary Jim	Jack Mary Jim	Y Y Y	Y Y Y	P P N	P P N	N P N	N P N

 Sexe est un attribut symétrique

 Les autres attributs sont asymétriques

 Y et P  1, N  0, la distance n’est mesurée que sur les asymétriques

0  1 ( jack, mary ) 

d ( jack, mary

0 



 0.33

~~2~~ ~~~~ ~~0~~ ~~~~ ~~1~~

 ~~~~ ~~0~~ ~~~~ ~~1~~

1  1 ( jack, jim ) 

d ( jack, jim

1 



 0.67

~~1~~ ~~~~ ~~1~~ ~~~~ ~~1~~

 ~~~~ ~~1~~ ~~~~ ~~1~~

1  2 ( jim, mary ) 

d ( jim, mary

1 



 0.75

~~1~~ ~~~~ ~~1~~ ~~~~ ~~2~~

 ~~~~ ~~1~~ ~~~~ ~~2~~

Les plus similaires sont Jack et Maryatteints du même mal

21

3-Variables Nominales

 Une généralisation des variables binaires, ex: rouge, vert

et bleu

 Méthode 1: Matching simple

 m: # d’appariements, p: # total de variables

p  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)

22

4-Variables Ordinales

 Une variable ordinale peut être discrète ou continue

 L’ordre peut être important, ex: classement

 Peuvent être traitées comme les variables intervalles

 remplacer x par son rang if

r  {1,..., M } if f

 Remplacer le rang de chaque variable par une valeur

dans [0, 1] en remplaçant la variable f dans l’objet I par

r  1

 if

~~M~~ ~~~~ ~~1~~

r z 

 if

if ~~M~~

f

 Utiliser une distance pour calculer la similarité

23

En Présence de Variables de différents Types

 Pour chaque type de variables utiliser une mesure

adéquate. Problèmes: les clusters obtenus peuvent être différents

 On utilise une formule pondérée pour faire la

combinaison

 p  ( f ) d

d ( i, j )  f  1 ij

p ( f

~~~~ ~~~~

p  ( f ) d ( f

f  1 ij ij

 f est binaire ou nominale:

 p  ( f ) d ( f )

( i, j )  f  1 ij ij p ( f )

~~~~ ~~~~

f  1 ij

p

  f  ~~~~

( f )

~~~~

1 ij

f



(f) = 1

d ij

(f) = 0 si x = x, sinon d if jf ij

 f est de type intervalle: utiliser une distance

normalisée

 f est ordinale

1

f

1

 calculer les rangs r et if

r z  if

 if 

if ~~M~~



 Ensuite traiter z comme une variable de type if

intervalle

24

Approches de Clustering

 Méthodes non hiérarchiques: Construire plusieurs partitions

puis les évaluer selon certains critères

 Méthodes hiérarchiques: Créer une décomposition

hiérarchique des objets selon certains critères

25

I.MÉTHODES DE PARTITIONNEMENT

1) Difficulté combinatoire: P = nombre de partitions en k classes n,k de n individus

P = P  k P (récurrence) (nombre de Stirling de 2 [ème ] n,k n  1,k  1 n  1,k

espèce)

Ex : P  1 379 400 12,5

• P = nombre total de partitions (nombres de Bell) nombre n

de partitions d'un ensemble à néléments distincts

Ex : P  4 213 597 12

 Nécessité d’algorithmes pour trouver une bonne partition.

Comment définir la qualité d’une partition ?

2. Inertie within et Inertie between-classe

n points d [2]  i,i  distance euclidienne

Soit une partition en k classes de poids P i

x

x x

I = IB +Iw

x x x x

x

x

x

x

x

x

x

x x

x

x

x

x

x

x

x x

x x

x

x

x

g1 x x

x g

x 2

x

x

x

x

x

x

x x

x

x

k x

x

x

x

g

x x

x

x

x

x

x

x

g

x

x x

Comparaison de deux partitions en k classes :

La meilleure est celle qui a l’inertie I la plus faible (ou W

l’inertie I la plus forte). B

Remarque : Ce critère ne permet pas de comparer des

partitions à nombres différents de classe.

1.2 Méthode des centres mobiles

• choix de centres ci et partition associée (les ci sont choisis

au hasard). La classe Eci est formée de tous les points plus proches de ci que de tout autre centre.

• calcul des centres de gravité de chaque classe → définition

d’une nouvelle partition.

L’inertie intra-classe diminue à chaque étape.

Exemple:

Exemple:

Exemple:

33

1,3 Généralisation: Nuées dynamiques K-means:

La segmentation par nuées dynamiques (ou k-means) est une méthode de classification automatique qui a pour objectif de partionner

L’idée est d’associer à une classe un représentant différent de son centre de gravité. Exemple :

 un ensemble d’individus (noyau formé de points appelés les

étalons)  une droite  une loi de probabilité

34

35

Algorithme:

Il faut faire décroître le critère U mesurant l’adéquation entre les classes et leurs représentants

1, Initialisation Deux possibilités :

1. Soit on se donne au départ une fonction d’affectation qui génère une partition . Les noyaux pour chaque classe sont calculés.
2. Soit on se donne k noyaux.

36

2, Étape d’affectation Pour chaque individu, déterminer la classe à laquelle on doit l’affecter (nécessité d’avoir défini une distance entre un point et un noyau, ou un groupe de points). Étape de représentation Pour chaque classe définie, calculer le nouveau noyau. ARRÊT DE L’ALGORITHME quand la décroissance atteint un seuil fixé a priori.

37

Exemple : Quels sont les groupes de programmes de

télévision identifiables qui attirent des publics similaires au

sein de chaque groupe ? Grâce à l'analyse de cluster de

nuéesdynamiques, vous pouvez classer les programmes de

télévision (observations) en kgroupes homogènes d'après les

caractéristiques des téléspectateurs.

Cette méthode peut être utilisée pour identifier des segments

à des fins commerciales. Vous pouvez aussi classer les villes

(observations) en groupes homogènes pour permettre la

sélection de villes comparables afin de tester diverses

stratégies commerciales.

38

fonction kmeans sous R

À l'issue de son exécution, kmeans() a associé chaque donnée à un groupe ; les groupes sont numérotés de 1 à k. La fonction kmeans() fournit en sortie une liste d'objets cluster : est un vecteur qui contient le numéro du groupe de chacune des données ; centers : spécifie la position des K centres ; withinss : est un vecteur de K nombres, chacun valant la somme des distances au carré des éléments du groupe considéré (c'est donc presque la même chose que l'inertie du groupe) ; size : est un vecteur indiquant la taille de chacun des groupes.

39

40

41

42

43

44

2, Principes de la classification ascendante hiérarchique La classification ascendante hiérarchique (CAH) est une méthode de classification itérative dont le principe est simple.

On commence par calculer la dissimilarité entre les N objets (individus).

Puis on regroupe les deux objets dont le regroupement minimise un critère d'agrégation donné, créant ainsi une classe comprenant ces deux objets.

45

46

On calcule ensuite la dissimilarité entre cette classe et les N-2 autres objets en utilisant le critère d'agrégation.

Puis on regroupe les deux objets ou classes d'objets dont le regroupement minimise le critère d'agrégation.

47

On continue ainsi jusqu'à ce que tous les objets soient regroupés.

Ces regroupements successifs produisent un arbre binaire de classification (dendrogramme), dont la racine correspond à la classe regroupant l'ensemble des individus.

48

49

Ce dendrogramme représente une hiérarchie de partitions.

On peut alors choisir une partition en tronquant l'arbre à un niveau donné, le niveau dépendant soit des contraintes de l'utilisateur

(l'utilisateur sait combien de classes il veut obtenir), soit de critères plus objectifs.

50

51

52

53

54

Sous R: Hclust()

55

56