|
|
|
|
|
|
K-means
Une des techniques de classification non supervisée (clustering) les plus utilisées.
Etant donné un entier K, K-means partitionne les données en K groupes, ou "clusters", ou "classes" ne se chevauchant pas. Ce résultat est obtenu en positionnant K "prototypes", ou "centroïdes" dans les régions de l'espace les plus peuplées. Chaque observation est alors affectée au prototype le plus proche (règle dite "de la Distance Minimale"). Chaque classe contient donc les observations qui sont plus proches d'un certain prototype que de tout autre prototype (image inférieure de l'illustration ci-dessous).
Les prototypes sont positionnés par une procédure itérative qui les amène progressivement dans leur position finale stable.
-----
La grande popularité de K-means vient de :
* Sa simplicité conceptuelle.
* Sa rapidité et ses faibles exigences en taille mémoire.
Mais elle souffre également de certains défauts :
* L'utilisateur doit choisir a priori la valeur de K, le nombre de classes. Ce choix peut se faire par simple examen visuel dans le cas de données bidimensionnelles, mais il n'en est pas de même pour des données de dimension supérieure. Il n'existe en général pas d'indication claire sur le nombre approprié de classes, et un "mauvais choix" pour la valeur de K conduira alors à une typologie sans rapport avec la réalité.
* Pour une valeur donnée de K, les classes obtenues dépendent beaucoup de la configuration initiale des prototypes, ce qui rend l'interprétation des classes difficile.
* K-means est une technique objective, ce qui veut dire qu'elle minimise la valeur d'un certain critère numérique. C'est donc une technique d'optimisation. Comme c'est souvent le cas en optimisation, l'algorithme K-means s'arrête lorsqu'il ne peut plus faire baisser la valeur du critère. Cependant, il est tout à fait possible qu'une autre configuration des prototypes conduise à des valeurs encore plus faibles du critère. Dans le vocabulaire de l'optimisation, on dit que K-means atteint un minimum local, mais ne peut pas garantir d'atteindre le minimum global du critère (valeur la plus faible possible).
_______________________________________
|
Tutoriel 1 |
Ce premier Tutoriel passe en revue les aspects élémentaires de K-means. Nous verrons qu'en dépit de sa nature franchement heuristique, K-means est en fait une technique objective qui minimise la valeur d'un critère.
Nous décrivons également la technique moins connue dite "K-means incrémental", qui construit les classes observation par observation.
K-MEANS
|
K-means Type de données Standardisation des données L'algorithme K-means Classes et tessellation de Voronoi Critère de la Somme des Carrés Pour un cluster Pour l'ensemble des données Dispersions "Intra" et "Inter" Limitations du critère de la Somme des Carrés Nature quadratique Dépendance du nombre de classes Convergence de K-means K-means incrémental Utilité du K-means incrémental L'algorithme Ordre de présntation des observations Convergence de K-means incrémental |
||
|
TUTORIEL |
|
|
_____________________________________________________
|
Tutoriel 2 |
Ce second Tutoriel traite de l'importante question de l'initialisation de K-means (nombre de classes et positions initiales des proptotypes). Il n'existe pas de théorie permettant d'apporter de réponse optimale à cette question, mais on peut recourir à des heuristiques efficaces qui apportent des solutions approchées, satisfaisantes dans la plupart des cas.
-----
Obtenir des classes est facile, mais ces classes ont une fâcheuse tendance à dépendre fortement des conditions initiales. Il convient donc de s'assurer que la typologie finale correspond bien à des "clusters" compacts, bien séparés et interprétables. Il existe de nombreuses aides à l'interprétation des résultats d'un K-means, et nous passons en revue les plus connues.
INITIALISATION DE K-MEANS
AIDES A L'INTERPRETATION
|
Initialisation de K-means Initialisation des prototypes Initialisation aléatoire Initialisations multiples Prototypes "morts" Temps de calcul Connaissance experte Distribuer "uniformément" les prototypes initiaux Maximiser les distances initiales entre prototypes Initialisation MaxMin Initialisation par "classe périphérique" Initialisation par intervalles réguliers
Choisir le nombre de classes Comparer plusieurs valeurs de K Classification hiérarchique préliminaire Aide à l'interprétation Intra-classe Populations Distances aux prototypes Diagrammes de dispersion ACP sur classes Inrter-classes Distances entre prototypes La statistique F Diagrammes de dispersion Variables auxiliaires Variables nominales Variables continues |
||
|
TUTORIEL |
|
|
____________________________________________________
|
Etude de cas |
Nous illustrons maintenant K-means par une étude de cas proposée par la Société StatSoft, et illustrée par le logiciel STATISTICA.
K-MEANS : ETUDE DE CAS
|
Les données L'initialisation Analyse des résultats Composition des classes La statistique F Moyennes par classe Croisements variables-classes Croisement entre variables numériques Distance entre les classes |
||
|
ETUDE DE CAS |
|
|
|
Cette Etude de Cas est une contribution de la société StatSoft |
|
__________________________________________
Voir aussi :
|
|
|
|
Téléchargez ce Glossaire |
|
|
|
|
|
