Tableau de données individus-variables et caractéristiques associées

CH 2 : METHODES DE CLASSIFICATION A-PROBLEMATIQUE Généralités L'objectif d'une méthode de classification est la recherche d'une typologie
ou segmentation, c'est à dire d'une partition ou répartition des n
individus de notre population dans des classes, sur la base de
l'observation des p descripteurs [pic] quelconques (on supposera pour
simplifier les individus affectés du même poids).
Chacune de ces classes doit être la plus homogène possible et, entre elles,
les plus distinctes possibles. Ceci est fait en optimisant un critère de
dispersion à définir. L'idée la plus simple serait de comparer toutes les partitions possibles
afin de choisir la meilleure, au sens du critère que l'on se serait fixé.
Malheureusement, le nombre de partitions augmente très rapidement avec le
nombre d'individus observés. Par exemple, pour n = 4 (A,B,C et D), il
existe 15 partitions possibles :
ABCD ABC D ABD C ACD B BCD A
AB CD AC BD AD BC AB C D AC B D
AD B C BC A D BD A C CD A B A B C D Or, en analyse des données, on a généralement à traiter des ensembles de
plusieurs milliers d'individus ! On conçoit bien que, même avec les outils
de calcul modernes, une telle méthode n'est pas réaliste. Il n'est donc pas
question d'optimiser un critère sur toutes les partitions possibles. C'est
la raison pour laquelle ont été développées des méthodes algorithmiques
variées répondant à cette problématique. Ces méthodes utilisent des
algorithmes itératifs convergeant vers une bonne partition, qui correspond
en général à un optimum local.
Nous en présenterons ici quelques unes parmi les plus utilisées et
indiquerons comment les faire fonctionner au mieux. Pour mettre en ?uvre une classification, différents choix sont laissés à
l'utilisateur :
- la mesure de l'éloignement (dissimilarité, distance) entre individus
- le critère d'homogénéité des classes à optimiser ; dans le cas de
variables quantitatives, il est généralement défini a partir de
l'inertie inter et intra-classes
- la méthode utilisée : la Classification Ascendante Hiérarchique (CAH)
ou celle par réallocation dynamique sont les plus utilisées
- le choix du nombre de classes et leur interprétation
Mesure de dissimilarité (ou d'éloignement)
Notons [pic] l'ensemble des individus. La première étape pour effectuer une
classification est de définir une mesure de[pic] permettant de mesurer
l'éloignement entre individus. Diverses propriétés sont souhaitables pour
une telle mesure, et notamment, [pic]
[pic] Selon les propriétés vérifiées par d, la terminologie diffère. On parle
ainsi de : Indice de dissimilarité : (1) (2)
Indice de distance : (1) (2) (3) : évite les incohérences pouvant
apparaître entre dissemblances par exemple, [pic]avec [pic].
Ecart : (1) (2) (4)
Distance : (1) (2) (3) (4)
Ecart ultramétrique : (1) (2) (4) (5)
Distance ultramétrique : (1) (2) (3) (4) (5) De nombreuses mesures sont ainsi proposées dans la littérature. Le choix
d'une mesure dépend essentiellement de la nature des descripteurs. Le plus
souvent, le choix se porte sur une distance euclidienne (i.e. engendrée par
un produit scalaire) appropriée. - Données quantitatives (X numérique) : on définit généralement une
matrice M de produit scalaire sur l'espace [pic] des variables. Un
choix élémentaire et courant est d'utiliser la distance canonique
[pic] . C'est une choix adapté si l'ensemble des variables est
homogène. Si les variables sont de variance hétérogène, il est
vivement conseillé de les réduire, ce qui revient à considérer comme
matrice de distance la distance inverse des écarts-types [pic]. La
distance de Mahalanobis ([pic], où V est la matrice de variance-
covariance) peut être aussi utilisée pour atténuer la structure de
corrélation. Dans la suite, la distance choisie sera notée [pic]. - Données qualitatives : dans le cas très particulier où toutes les
variables sont binaires, de nombreux indices de dissimilarités ou de
distance ont été proposés dans la littérature. Ils sont basés sur les
quantités suivantes et définis pour deux individus i et j :
Aij=nombre de caractères communs à i et j sur les p considérés
Bij=nombre de caractères possédés par i mais pas par j
Cij= nombre de caractères possédés par j mais pas par i
Dij=nombre de caractères possédés ni par i ni par j Dans le cas plus général de p variables qualitatives, la distance la
plus utilisée est celle, euclidienne, dite du Chi2 entre profils-
lignes du tableau disjonctif (cf cours stat) :
[pic]
où [pic] est le nombre de modalités de la variable qualitative [pic], [pic]
est l'effectif de la l° modalité de [pic] et [pic]vaut 1 si les individus
i et k présentent une discordance pour la l° modalité de [pic] et 0 sinon. - Données mixtes : deux stratégies sont possibles
o rendre tout qualitatif : les variables quantitatives sont
rendues qualitatives par découpage en classes (d'effectifs
relativement égaux, bornes des classes les quantiles). La
métrique à utiliser est alors celle du Chi2.
o rendre tout quantitatif : à l'aide d'une AFCM, calculée sur les
seules variables qualitatives ou sur l'ensemble des variables
après découpage en classes des quantitatives. L'AFCM calculée
par AFC du tableau disjonctif produit des scores (quantitatifs)
qui sont les composantes principales de l'ACP des profils
lignes. Une fois ces formalités accomplies, nous nous retrouvons avec un tableau
n*p de mesures quantitatives associé à une métrique euclidienne, ou avec
une matrice de dissemblance ou distances entre individus . Un critère d'homogénéité : Inerties
Il s'agit ensuite de définir un critère d'homogénéité des classes. Au
centre des méthodes les plus utilisées - car ayant de bonnes propriétés
généralistes, et cohérentes avec les méthodes d'analyse factorielle
notamment -, on retrouve la notion d'inertie : si l'on a déjà défini dans
le cadre de l'ACP l'inertie totale I du nuage de points, et G son centre
d'inertie, on va ici définir de nouvelles notions.
Si l'ensemble de nos points est regroupé en K classes (i.e. K sous-nuages
[pic]), de poids [pic], de centre d'inertie [pic], et d'inertie [pic], on
définit : - l'inertie intra-classes : [pic]
- l'inertie inter-classes : [pic]
D'après le théorème de Huyghens, on montre que : [pic] Notons que dans le cas de variables quantitatives, l'inertie de la
partition correspond à la trace de la matrice des variances et covariances
interclasses. Un critère usuel de classification sera alors, à K fixé, de minimiser
l'inertie intra-classes (i.e. rendre les classes les plus homogènes
possible) - ce qui revient donc à maximiser l'inertie interclasse (i.e.
séparer le plus possible les classes).
La qualité d'une classification pourra alors être évaluée par le ratio
[pic], interprétable comme une part d'inertie des n points expliquée par
leur synthèse en K barycentres.
Méthodes
B. ALGORITHMES DE PARTITIONNEMENT: les « centres mobiles »
Principe
Plusieurs algorithmes de classification sont d'inspiration géométrique :
ils sont connus sous le nom de « méthodes de partitionnement »: on part
d'une partition arbitraire, améliorée itérativement jusqu'à la convergence.
Ils nécessitent de choisir un nombre de classes K a priori. Ayant
initialisé k centres de classes aléatoirement, tous les individus sont
affectés à la classe dont le centre est le plus proche au sens de la
distance choisie (en principe, euclidienne pour cette méthode). Dans une
deuxième étape, l'algorithme calcule les barycebtres de ces classes qui
deviennent les nouveaux centres le procédé est itéré jusqu'à convergence
vers un minimum local du critère choisi ou un nombre maximum d'iterations
fixé.
- La plus connue de ces méthodes est celle des centres mobiles. Son
principe est le suivant : si l'on veut K classes, on choisit
aléatoirement K points dans l'espace des individus ; on affecte chacun
des n individus à celui de ces K points qui lui est le plus proche (au
sens de la distance d choisie au départ, généralement euclidienne) ;
dans une deuxième étape, on calcule les K barycentres des classes
précédemment crées, qui deviennent les nouveaux centres ; on réitère
l'affectation jusqu'à convergence vers un minimum local ou un nombre
d'itérations maximum fixé a priori.
Le critère est généralement la minimisation de l'inertie intra-classes. On peut montrer que cet algorithme fait diminuer à chaque itération la
variance intraclasse. Ou, de manière équivalente fait augmenter l'inertie
inter-classes Démonstration. A l'étape t soit [pic] les K sous-nuages constitués et
[pic] les barycentres des points auxquels ils se rattachent.
Considérons le critère suivant :
[pic]. On a [pic]. Donc,
[pic]d'après Huygens et [pic]. On peut montrer de même que [pic]. Le minimum obtenu est un minimum local, c'est à dire que la répartition en
classes dépend du choix initial des centres. Plusieurs exécutions de
l'algorithme permettent de s'assurer de la présence de formes fortes,
c'est à dire de classes ou portions de classes présentes de manière stable
dans la majorité des partitions obtenues.
Algorithme
. Initialisation : tirer au hasard ou sélectionner, pour des raisons
extérieures à la méthode, K points dans l'espace des individus, en
général K individus de l'ensemble, appelés centres.
. Itérer les deux étapes suivantes jusqu'à ce que le critère de variance
interclasses ne croisse plus de manière significative, c'est à dire
jusqu'à le stabilisation des classes :
- allouer chaqu