lundi 31 mars 2008

K-Means sur variables qualitatives

L’algorithme des K-Means est une méthode de classification automatique (clustering), on l’appelle également K-Moyennes ou encore Nuées dynamiques (bien que cette dénomination constitue en réalité une généralisation).

L’idée est très simple. On choisit K individus au hasard, qui constituent les noyaux initiaux. On fait passer toutes les observations. On affecte chaque observation au noyau qui lui est le plus proche. Les noyaux sont alors remis à jour. Puis on réitère le passage de tous les individus jusqu’à ce que la solution soit stable.

Sa simplicité fait la popularité de cette approche. Autre avantage notable, il n’est pas nécessaire de calculer au préalable les distances deux à deux entre tous les individus, opération très gourmande en temps et en espace mémoire dans certains algorithmes de clustering.

La méthode des K-Means présente néanmoins des inconvénients. On citera notamment l’obligation de fixer au préalable le nombre de groupes, sans qu’aucune indication ne soit fournie. La CAH – classification ascendante hiérarchique - par exemple ne donne pas non plus le bon nombre de groupes, en revanche avec le dendrogramme, nous disposons des indications sur le partitionnement adéquat. On citera aussi la forte dépendance de la méthode au choix des noyaux initiaux. La méthode peut converger vers un optimum local. C’est pour cette raison que l’on propose dans Tanagra (et dans tous les autres logiciels) de réitérer plusieurs fois le processus complet en changeant les conditions initiales.

Dans ce didacticiel, nous abordons un problème supplémentaire. Les descripteurs sont catégoriels. Nous ne pouvons pas directement lancer les K-Means surtout avec la distance euclidienne usuelle. On propose de travailler en 2 étapes : (1) réaliser une analyse en composante multiple ; (2) lancer les K-Means sur les x premiers axes factoriels. L'étape (1) de construction de variables nous permet d'utiliser par la suite l'algorithme standard des K-Means basé sur la distance euclidienne.

Pour interpréter les groupes, nous utiliserons dans un premier temps les statistiques descriptives comparatives. Malgré (ou grâce à) sa simplicité, elle est foncièrement univariée, cette approche est très populaire. Elle permet de détecter rapidement les principales variables qui différencient fortement les groupes.

Dans un second temps, nous comparons les groupes obtenus avec une variable supplémentaire, qui constituerait les classes « naturelles » des observations. On parle dans ce cas de validation externe. Cette démarche est très utilisée dans la recherche, lorsque l’on veut montrer l’efficacité d’une méthode de classification.

Mots clés : classification automatique, clustering, k-means, k-moyennes, nuées dynamiques, analyse factorielle de correspondances mutliples, validation externe, interprétation des classes
Composants : Multiple Correspondance Analysis, K-Means, Group characterization, Cross Tabulation
Lien : dr_clustering_validation_externe.pdf
Données : dr_vote.bdm
Références :
Wikipédia, « K-means algorithm ».
G. Bisson, « Evaluation & Catégorisation ».