Clustering par méthodes hiérarchiques et non-hierarchiques : analyse des données numériques

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

16

AgeSalairePersonne15011000Personne27011100Personne36011122Personne46011074AgeSalairePersonne1-2-0,5Personne220,175Personne300,324Personne4002-Variables binaires

 Une table de contingence pour données binaires

Objet j

Objet i

a= nombre de positions où i a 1

et

j a 1

 Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)

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

17

pdbcasumdcdcbabasum0101Mesures de distances

 Coefficient d’appariement (matching) simple

(invariant pour variables symétriques):

Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)

d(oi, oj)=3/5

 Coefficient de Jaccard

d(oi, oj)=3/4

18

dcbacb jid),(cbacb jid),(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)

 Exemple

 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

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

21

Nom Sexe Fièvre Toux Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Mary F Y N P N P N Jim M Y P N N N N 75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd3-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

 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

pmpjid),(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 xif par son rang  Remplacer le rang de chaque variable par une valeur dans [0, 1] en remplaçant la variable f dans l’objet I par

 Utiliser une distance pour calculer la similarité

23

11fififMrz},...,1{fifMr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

 f est binaire ou nominale:

dij

(f) = 0 si xif = xjf , sinon dij

(f) = 1

 f est de type intervalle: utiliser une distance

normalisée  f est ordinale

 calculer les rangs rif et  Ensuite traiter zif comme une variable de type

intervalle

24

)(1)()(1),(fijpffijfijpfdjid11fifMrzifApproches 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: Pn,k = nombre de partitions en k classes de n individus Pn,k = Pn1,k 1  k Pn1,k (récurrence) (nombre de Stirling de 2ème

espèce)

Ex : P12,5  1 379 400

 Pn = nombre total de partitions (nombres de Bell) nombre

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

Ex : P12  4 213 597

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

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

2.

Inertie within et Inertie between-classe

2i,i distance euclidienne n points d Soit une partition en k classes de poids Pi

I = IB +Iw

g = centre de gravité des n individus

x

x

x

x

x

x

x

x

x

x

x

x

x

g1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

g2

x

x

x

x

x

x

x

g

x

x

x

x

x

x

x

x

x

g

k x

x

x

Comparaison de deux partitions en k classes :

La meilleure est celle qui a l’inertie IW la plus faible (ou l’inertie IB la plus forte).

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ées dynamiques, 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 le une méthode de classification itérative dont principe est simple.

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

on

les

deux

regroupe

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

objets

dont

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 soient regroupés.

jusqu'à ce que tous les objets

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.

choisir une partition en On peut alors 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