Partition des centres mobiles pour données qualitatives

Maurice Roux

Sujets

• Carreleur
• Voyageur représentant placier
• Tableau d'honneur
• Sommervieu
• Bloc de béton
• Jeux vidéo A

Informations

• Publié par: Nozur
• Nombre de lectures: 337
• Langue: Français

Extrait

Partition des centres mobiles pour données qualitatives

Maurice Roux

Faculté des Sciences et Techniques (Case 462)

Université Paul Cézanne (Marseille 3)

Avenue Normandie-Niemen

13397 Marseille Cedex 20, France

RÉSUMÉ. On présente un nouvel algorithme de partitionnement autour de centres mobiles (k-means) pour des

données qualitatives, basé sur la métrique du Khi-carré. Cet algorithme est comparé à trois autres techniques

similaires de partitionnement autour de centres mobiles en utilisant des jeux de données réelles et simulées. Les

résultats sont évalués par le critère de l’inertie interclasse.

MOTS-CLÉS : agrégations autour de centres mobiles, métrique du Khi-carré, inertie interclasse, partitions.

1

Introduction

Un certain nombre de méthodes de classification ont été proposées pour traiter les données qualitatives

[GOV 84, KAU 90, HUA 98]. Mais très peu ont utilisé la métrique du Khi-carré pourtant couramment

utilisée avec succès, avec l’Analyse factorielle des Correspondances (AFC, [BEN 73]), bien adaptée à ce

type de données. Reprenant une idée esquissée par Ralambondrainy [RAL 95] l’algorithme que nous

exposons ici, applique le mécanisme usuel de réallocation-recentrage de la méthode des k-moyennes

[FOR 65, MAC 67], sur les « profils » des objets, lesquels sont munis de poids, comme en AFC. Dans le

paragraphe suivant on présente quelques algorithmes usuels pour traiter des variables qualitatives. Puis on

décrit les étapes du nouvel algorithme. Ensuite on propose une évaluation de cet algorithme. Enfin on

termine par une courte conclusion.

2

Quelques méthodes classiques pour traiter des données qualitatives

2.1

Pré-traitement par l'AFC [ROU 85]

La méthode consiste à traiter par l'AFC les données, mises sous forme disjonctive complète si nécessaire.

On récupère ensuite les coordonnées factorielles pour les introduire comme variables quantitatives dans le

programme de classification. La seule difficulté de cette méthode réside dans le choix du nombre d'axes

factoriels à retenir pour définir les données soumises à la classification. Un certain nombre de règles

empiriques peuvent aider l'utilisateur dans ce choix [SAP 93].

2.2

Utilisation des K-médoïdes [KAU 90]

Dans leur méthode PAM Kaufman et Rousseeuw travaillent directement sur une matrice de distances. Les

représentants des classes sont les individus les plus centraux de ces classes, appelés "médoïdes", qui

minimisent la somme des distances aux autres objets de la classe. Nous avons adapté ce principe dans le

cadre d'une procédure de réallocation-recentrage. Dans la phase de réallocation les objets sont affectés à la

classe dont le médoïde est le plus proche. N'importe quelle distance peut être prise comme point de départ

mais nous avons choisi la distance du Khi-carré en concordance avec les autres méthodes étudiées.

2.3

Méthode des k-modes [HUA 98]

Dans cette méthode les représentants des classes sont des objets artificiels, appelés k-modes, repérés par

les mêmes variables que les objets réels. Leurs composantes sont les modalités de fréquence maximale

dans leur classe. Cette définition est quelque peu ambigüe car il peut y avoir plusieurs modalités de même

fréquence au sein d'une même classe ; dans ce cas l'une d'elle est choisie arbitrairement.

La distance d(i, k), entre un objet i et un objet modal, représentant la classe k, est égale au nombre de

variables pour lesquelles les modalités de l'objet i et du représentant de k sont différentes. Il s'agit, en fait,

de la distance L

1

entre les objets décrits par les indicatrices des modalités de variables. L'auteur montre

que la méthode converge et minimise (localement) la somme des distances entre les individus et leurs

objets modaux respectifs.

3

Le nouvel algorithme : méthode des k-profils.

On appelle x

ij

les valeurs (zéro ou 1) du tableau X des données. La masse x

i.

d'un individu i est donnée par

la somme des valeurs des variables pour cet individu ; elle est donc égale au nombre de 1 présents dans le

vecteur décrivant l'individu. Le profil P(i) d'un objet i est donné par la suite des rapports de ses valeurs à

sa masse :

P(i) = { x

i1

/x

i.

, ..., x

ij

/x

i.

, ...x

ir

/x

i.

}

Le centre de gravité général G, du solide constitué par les profils des objets, munis des masses

correspondantes, a pour j-ème coordonnée :

g

j

= (1/x

..

)

Σ

i

x

i.

( x

ij

/x

i.

) = (1/x

..

)

Σ

i

x

ij

= x

.j

/ x

..

où x

..

représente la masse totale du solide et x

.j

désigne la somme des valeurs de la modalité de variable j,

c'est à dire la fréquence de cette modalité. Un calcul analogue montre que le centre de gravité G

k

d'une

classe k est représenté également par un profil [JAM 78] :

G

k

= {x

k1

/ x

k.

, ... x

kj

/ x

k.

, ... x

kr

/ x

k.

}

où x

kj

désigne la fréquence de la modalité j au sein de la classe k et x

k.

est la somme de toutes ces

fréquences sur l'ensemble de toutes les modalités de variable. Et l'on vérifie facilement que le centre de

gravité général G est bien égal à la moyenne pondérée des centres de gravité des classes de la partition.

Comme les autres méthodes d'agrégations autour de centres mobiles, notre algorithme se compose d'une

phase de recentrage et d'une phase de réaffectation des objets aux classes. Une classe est représentée par

son centre de gravité, tel qu'il a été défini ci-dessus, c'est à dire une sorte de profil moyen de la classe en

question. Les objets sont ensuite réaffectés à la classe dont le centre de gravité est le plus proche au sens

de la formule du Khi-carré :

d

2

(i, k) =

Σ

j

(1/x

.j

) [ x

ij

/x

i.

– x

kj

/x

k.

]

2

dans laquelle chaque modalité de variable est pondérée par l'inverse de sa fréquence x

.j

. Il est clair que

cette procédure n'est qu'un cas particulier de la procédure générale d'agrégation autour de centres mobiles.

Donc cet algorithme converge et optimise le moment d'ordre 2, ou inertie inter-classe. Dans notre cas ce

moment n'est autre (à un coefficient près) que le critère du Khi-carré de contingence entre la partition K et

l'ensemble J des modalités de variables.

4

Evaluation du nouvel algorithme.

4.1

Application à des données connues (Critère externe).

Le premier jeu de données, que nous appelons PHYTOS (pour phytosociologie), est constitué de 16

relevés floristiques caractérisés par la présence ou l'absence d'un ensemble de 66 espèces [ROU 85]. De

nombreux travaux sur ces données nous ont conduits à une partition en 4 classes que nous considérons

comme « bonne ». Cette partition nous servira de référence dans les comparaisons ci-dessous.

Le second jeu de données, que nous appelons BOUCLES, décrit un ensemble de 59 plaques métalliques

ornementées soutenant des boucles de ceintures. Ces boucles proviennent de fouilles archéologiques et

sont d’époque médiévale (6-ème, 8-ème siècle). Elles sont décrites par 29 types de décorations en

présence ou absence [LER 80]. Les auteurs de ce travail proposent plusieurs partitions, dont une en 5

classes qui nous servira de référence.

Un troisième jeu de données a été obtenu par simulation. Nous avons fabriqué une matrice de données en

0-1 constituée de blocs à prédominance de 1 (avec probabilité 0,8) et d’autres blocs à prédominance de

zéros (avec probabilité 0,8 également) à la manière de Govaert [GOV 84]. Le tableau, que nous appelons

BLOCS, comporte 100 objets repérés par 30 caractères. La classification porte sur les 100 objets.

4.2

Comparaison avec d'autres méthodes (Critère interne).

Les trois autres méthodes de classification évoquées au paragraphe 2 ci-dessus ont été mises en

concurrence avec le nouvel algorithme. Les partitions obtenues par chacune des 4 méthodes sont évaluées

par le critère de l’inertie interclasse, calculée selon la métrique du Khi-carré, et appliquée aux données

initiales. Dans les trois jeux de données le tableau brut est traité directement, sans disjonction des

modalités. Dans le cas du prétraitement par l'AFC, on a retenu les 6 premiers axes factoriels pour les

données PHYTOS (représentant 72,4 % de la variation totale), 4 axes factoriels seulement pour les

données BOUCLES (représentant 77,9 % de la variation totale) et 4 axes également pour les données

artificielles BLOCS (représentant 43,1 % de la variation totale).

4.3

Résultats des comparaisons.

Les meilleures partitions obtenues avec chaque algorithme ont été comparées sur la base de l’inertie

interclasse, calculée sur les données brutes avec la métrique du Khi-carré (Tableau 1). Ces partitions ont

été obtenues après 500 tirages aléatoires initiaux pour tous les jeux de données.

Prétraitement

AFC

K-médoïdes

K-modes

K-profils

Partition de

référence

PHYTOS

0,4003

0,3951

0,3922

0,3954

0,3857

BOUCLES

0,7189

0,6269

0,7132

0,7198

0,7119

BLOCS

0,3228

0,2170

0,3136

0, 3251

0,3089

Tableau 1. Valeurs des rapports inertie-inter/inertie-totale selon les algorithmes et les jeux de données.

Les qualités des partitions obtenues sont très voisines et, en général, meilleures que les partitions de

référence. Le nouvel algorithme arrive au deuxième rang dans le premier cas et au premier rang dans les

deux autres cas. Le résultat inattendu est la bonne tenue de la méthode utilisant le prétraitement par l’AFC.

5

Conclusion.

Une adaptation de l'algorithme classique des k-moyennes a été faite pour traiter des données qualitatives.

Le nouvel algorithme repose sur la métrique du Khi-carré appliquée aux profils des individus et aux

profils de leurs classes. Il converge rapidement vers un optimum local de l’inertie inter-classe, optimum

dépendant de la partition initiale. Pour éviter cet inconvénient on réitère un grand nombre de fois des

tirages au hasard de la partition initiale. Appliqué à diverses données le nouvel algorithme donne de bons

résultats ; comparé à ses concurrents immédiats il obtient des résultats équivalents ou meilleurs que ceux-

ci. Toutes les méthodes examinées nécessitent le choix préalable du nombre de classes ce qui est une

opération délicate quand les données ne sont pas connues par ailleurs.

6

Bibliographie

[BEN 73] BENZÉCRI J.P.

L'Analyse des données. Tome 2: L'Analyse des Correspondances.

Dunod,

Paris, 1973.

[FOR 65] FORGY E.W. "Cluster Analysis of Multivariate Data : Efficiency Versus Interpretability of

Classifications",

Biometric Society Meetings

, Riverside, California (Abstract in

Biometrics

Vol. 21, no

3, p 768), 1965.

[GOV 84] GOVAERT G. "Classification simultanée de tableaux binaires". In

Data Analysis and

Informatics III,

E. Diday, M. Jambu, L. Lebart, J. Pagès et R. Tomassone (Eds), Norh-Holland,

Amsterdam, 1984, p. 223-236.

[HUA 98] HUANG Z. "Extensions to the k-means algorithm for clustering large data sets with categorical

values".

Data Mining and Knowledge discovery

, vol. 2, 1998, p. 283-304.

[JAM 78] JAMBU M., LEBEAUX M.O.

Classification automatique pour l'Analyse des données. Tome

1.- Méthodes et Algorithmes,

Dunod, Paris, 1978.

[KAU 90] KAUFMAN L., ROUSSEEUW P.J.

Finding groups in data : an introduction to cluster

analysis.

Wiley, 1984.

[LER 80] LEREDDE H., PERIN P. “Les plaques-boucles mérovingiennes”.

Les dossiers de l’archéologie

,

no 42, 1980, p 83-87.

[MAC 67] MAC QUEEN J.B. "Some methods for classification and analysis of multivariate

observations",

Proc. Symp. Math. Statist. and Probability, 5th,

Berkeley, AD 669871, Univ. of

California Press, Berkeley, Vol. 1, 1967, p 281-297.

[RAL 95] RALAMBONDRAINY H. "A conceptual version of the k-means algorithm".

Pattern

recognition letters,

vol. 16, 1995, p. 1147-1157.

[ROU 85] ROUX M.

Algorithmes de classification.

Masson, Paris. 1985.

[SAP 93] SAPORTA G. "Notions sur les méthodes factorielles". In

Traitement statistique des enquêtes,

D. Grangé et L. Lebart (Eds), Dunod, 1993, p. 75-89.