Les méthodes de partitionnement

add

\bullet Présentation:

Les méthodes de partitionnement font parties des trois familles d’outils d’analyse non supervisée les plus répandues avec la classification ascendante hiérarchique (CAH) et les méthodes à estimation de densité.

Les méthodes de partitionnement sont particulièrement intéressantes dans la construction de clusters/groupes d’observations d’une matrice de données à P \geq 1 variable(s) continue(s), \mathbf{X} = (X ^1, \cdots, X ^P), à partir de la structure même des données sans apport informatif d’une variable auxiliaire. A noter que des travaux récents ont permis d’étendre cette famille d’outils au cas des variables qualitatives.

Les méthodes de partitionnement les plus connues sont les nuées dynamiques, la méthode des centres mobiles, des K-means, des K-medoids, des K-modes, des K-prototypes et des K-médianes. La littérature diverge assez souvent au sujet des nuées dynamiques, dans certains cas elles sont mentionnées comme l’algorithme commun à toutes les variantes de méthodes de partitionnement, dans d’autres elles sont assimilées aux K-means.

Les avantages de cet outil d’analyse sont, principalement, sa simplicité et sa rapidité d’exécution même sur un grand nombre d’observations. A contrario, nous pourrons lui reprocher une classification finale un peu trop approximative et le besoin de spécifier à priori un nombre de classes à obtenir en fin de procédure. Par conséquent, les méthodes de partitionnement sont généralement utilisées dans un objectif d’analyse préliminaire avant le déploiement d’une méthode plus robuste comme la classification hiérarchique ascendante ou encore les méthodes à estimation de densité.

\bullet L’Algorithme des nuées dynamiques:

Par abus de langage, nous partirons du postulat que l’algorithme commun des méthodes de partitionnement est celui des nuées dynamiques.

L’Algorithme des nuées dynamiques a été conçu par Hugo Steinhaus et Stuart Lloyd en 1957. Les nuées dynamiques reposent sur la convergence d’un algorithme itératif relativement trivial. Il nécessite de paramétrer le nombre de clusters K que nous souhaitons obtenir en fin de procédure. L’algorithme se décrit ainsi,

– Itération 1: Sélectionner K points aléatoirement au sein du jeu de données. Ensuite, séparer le jeu de données en K premiers groupes selon une méthode de partitionnement fixée. Nous obtenons ainsi une première partition des données.

– Jusqu’à convergence des K groupes: Recalculer les centres des K clusters selon le noyau sélectionné et appliquer le même repartitionnement qu’en étape une.

La convergence est obtenue lorsque les groupes ne varient plus.

\bullet Les variantes:

Globalement, toutes les méthodes de partitionnement se base sur l’algorithme des nuées dynamiques. Difficile de partir sur un langage commun étant donné que d’un pays à l’autre les appellations divergent. Parmi les variantes des nuées dynamiques nous avons,

– La méthode des centres mobiles: conçue par Edward Forgy en 1965,  c’est la distance avec le centre de gravité le plus proche de chaque partition qui est utilisée pour déterminer les K classes.

– La méthode des K-moyennes ou K-means: conçue par James McQueen en 1967, c’est la distance moyenne entre les points et le centre de gravité de chaque partition qui est utilisée pour déterminer les K classes.

– La méthode des K-medoids: conçue par Leonard Kaufman et Peter J. Rousseeuw en 1987, c’est la distance entre les observations sélectionnées via permutation et le désigné de la classe (medoïd) de chaque partition qui est utilisée pour déterminer les K classes.

– La méthode des K-médianes: décrite par Anil K. Jain et Richard C. Dubes en 1988, c’est la distance médiane entre les points et le centre de gravité de chaque partition qui est utilisée pour déterminer les K classes.

– La méthode des K-modes: décrite par Zhexue Huang en 1988 et qui est adaptée aux variables exclusivement qualitatives. C’est la similarité entre les observations de chaque partition qui est utilisée pour déterminer les K classes.

– La méthode des K-prototypes: conçue par Zhexue Huang en 1988, qui est adaptée aux mixtes de variables continues et qualitatives et combine l’approche par méthode des K-modes et des K-means. C’est la similarité et la distance moyenne au barycentre entre les observations de chaque partition qui est utilisée pour déterminer les K classes.

\bullet Exemple:

Soit le jeu de données ci-dessous,

add1

La projection des observations nous donne la carte des individus suivante,

add2.png

Appliquons l’algorithme des nuées dynamiques pour déterminer nos K = 2 clusters fixés au préalable.

Itération 1: La première itération consiste donc à sélectionner deux points au hasard et qui formeront nos deux premiers clusters. Nous tirons donc l’observation N°5 et l’observation N°2.

add

Cette première itération divise le plan en deux clusters, celui regroupant les observations N°3, 5, 6, 7, 8. Et celui regroupant les observations N° 1, 2, 4, 9, 10.

Itération 2: Nous calculons maintenant les centres de gravité relatifs aux deux groupes construit au cours de l’itération 1. Nous obtenons le barycentre du groupe vert, de coordonnées (6.3236,10.5678), et celui du groupe bleu, de coordonnées (9.0579,10.7572).

add

Cette seconde itération met à jour les deux clusters construit auparavant. Ainsi, pour le groupe vert, les observations 3, 6, 7, 8 sont conservées et l’observation 5 est envoyé dans le groupe bleu qui contient toujours les observations 1, 2, 4, 9, 10.

Itération 3: Nous calculons maintenant les centres de gravité relatifs aux deux groupes construits. Nous obtenons le barycentre du groupe vert, de coordonnées (3.3650,5.898), et celui du groupe bleu, de coordonnées (9.113,7.754).

add.png

La division de l’itération 3 confirme celle de l’itération 2, nous en déduisons que l’algorithme a convergé et que les deux clusters conçus sont,

– groupe 1: observations N°3, 6, 7, 8,

– groupe 2: observations N° 1, 2, 4, 5, 9, 10.

\bullet Application informatique:

– Procédure SAS: https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#cluster_toc.htm

– Package et fonction R: https://stat.ethz.ch/R-manual/R-devel/library/stats/html/hclust.html

\bullet Bibliographie:

– Comprendre et utiliser les statistiques dans les sciences de la vie de Bruno Falissard

– Data mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry

– The Elements of Statistical Learning de Trevor Hastie, Robert Tibshirani, Jerome Friedman

– Probabilités, analyse des données et statistique de Gilbert Saporta

Sur la division des corps matériels en parties de Hugo Steinhaus

– Least square quantization in PCM de Stuart Lloyd

– Cluster analysis of multivariate data: efficiency versus interpretability of classifications de  Edward Forgy

– Some Methods for classification and Analysis of Multivariate Observations de James McQueen

Clustering by means of Medoids, in Statistical Data Analysis Based on the L_1–Norm and Related Methods de Leonard Kaufman et Peter J. Rousseeuw

– Algorithms for clustering data de Anil K. Jain et Richard C. Dubes

– Clustering large data sets with mixed numeric and categorical values de Zhexue Huang