Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

L'initialisation des k-means

logo

 

 

 

 

 

 

 

 

 

 

K-means : choix des prototypes et du nombre de clusters

Comment choisir le bon nombre de clusters et comment choisir les points prototypes à partir desquels s’effectuera le processus de typologie k-means ?

Le nombre de clusters

S’il est déterminé par la problématique, la question ne se pose pas (bons clients vs mauvais clients = deux classes). Sinon, il est recommandé de d’abord visualiser votre nuage de points avec le secours d’une ACP sur les individus (ou d’une ACP sur variables si vous classez des variables).

Une autre technique consiste à choisir un nombre important de classes k et à observer le résultat. Ensuite, on procède à un « k – 1 means » ! Le fait d’analyser les données avec une classe de moins ne se traduit-il que par le regroupement de deux clusters ? Dans ce cas, on peut tenter une « k – 2 means » et ainsi de suite. Tous les regroupements sont-ils au contraire bouleversés ? Alors on a peut-être trop réduit le nombre de classes !

Les points initiaux

Une typologie k-means ne converge pas forcément vers une solution optimale. Rappelons qu’un calcul d’optimisation globale est incompatible avec les volumes de données utilisés, quelle que soit la puissance des ordinateurs. Ainsi, les k-means vont utiliser des algorithmes itératifs permettant d’arriver à un optimum local. Ils vont « tâtonner » pour minimiser des matrices de covariances intra-classes. C’est aussi un algorithme qui va tenter de trouver les « meilleurs » k points initiaux. Certains logiciels vous donnent la possibilité de le paramétrer.

En effet, plusieurs options peuvent vous être proposées et la qualité finale de votre typologie va en dépendre, tout en sachant qu’il n’existe pas UN bon choix initial. Cela varie en fonction de la configuration des données et même du hasard.

Première solution pour choisir les k points initiaux : on ne se fatigue pas et le logiciel les fixe aléatoirement. Il peut procéder à un certain nombre d’essais et il choisira le plus concluant.

Deuxième solution : l’avis d’expert. Suppose que quelqu’un ait une assez bonne connaissance de la population étudiée pour rattacher à chaque classe un « type idéal ». Ce dernier peut être ou non un individu réel. Tout dépend de ce que votre logiciel vous autorise à faire. A titre d’exemple, le logiciel XLSTAT le permet grâce à l’option « Définie par les centres ».

Troisième solution : le logiciel répartit les k points initiaux selon certains algorithmes. L’initialisation étant décidément de la mécanique de haute précision, Il existe plusieurs façons de paramétrer cette option.

L’initialisation par intervalles réguliers utilise le principe suivant : le logiciel calcule toutes les distances entre observations prises deux par deux puis les trie. La plus grande distance divisée par k, le nombre de classes, donne une distance d. Le logiciel choisit les points initiaux de façon à obtenir d entre deux points consécutifs.

La maximisation des distances initiales : algorithme estimant k points particulièrement distants les uns des autres.

 

crocos

 

© JY Baudot - Droits d'auteur protégés