L’algorithme des K-moyennes l’un des algorithmes de clustering

Initialisation des centres

Introduction

L’algorithme des K-moyennes est l’un des algorithmes de clustering le plus répandu dans la littérature. Il doit sa popularité essentiellement à sa rapidité et à sa simplicité. Cet algorithme consiste à construire une partition initiale des données de cardinalité K. A partir de cette étape d’initialisation, l’algorithme des K-moyennes cherche à améliorer itérativement le partitionnement en déplaçant les objets d’un groupe à un autre jusqu’à atteindre un critère terminal de stabilité. Pour plus de détail sur cet algorithme, le lecteur pourra se référer à. Afin d’atteindre notre objectif décrit dans la section 2.6.1 du chapitre 2, à savoir « la recherche d’un algorithme permettant de prédire et de décrire d’une manière simultanée », nous avons commencé par définir dans le chapitre 3, un prétraitement supervisé (interprétable) basé sur une estimation des distributions uni-variées conditionnellement aux classes. Ce prétraitement permet d’obtenir une distance dépendante de la classe qui aide l’algorithme des K-moyennes standard à avoir de bonnes performances au sens du clustering prédictif (i.e. le compromis entre la prédiction et la description). La deuxième étape qui suit l’étape de prétraitement est l’initialisation des centres (voir Algorithme 3 de la section 2.6.2 du Chapitre 2). Cette dernière a une grande influence sur les résultats fournis par l’algorithme des K-moyennes. Ce chapitre a donc pour but de discuter l’impact des méthodes d’initialisation supervisées sur la qualité des résultats de l’algorithme des K-moyennes classique au sens du clustering prédictif (ou la classification à base de clustering). De par sa nature, l’algorithme standard des K-moyennes converge rarement vers un optimum global. La qualité 6 de cet optimum local et le temps requis par l’algorithme pour converger dépendent entre autre du choix des centres initiaux. Une mauvaise initialisation peut produire une solution (optimum local, «Figure 4.1 a») qui peut être très différente (ou loin) de la solution optimale «Figure 4.1 b». A titre d’exemple, la figure 4.1 présente une configuration dans laquelle l’algorithme des K-moyennes (K est fixé à 3) converge vers un minimum local qui ne reflète pas la vraie structure interne des données.

État de l’art

La recherche d’une méthode appropriée pour initialiser les centres des K-moyennes est un domaine de recherche très actif. Jusqu’à présent, une grande variété de méthodes existe dans la littérature. Dans cette section, nous allons présenter une brève description des méthodes les plus répandues. Ces méthodes peuvent être classées selon leur complexité en N (nombre d’instances du jeu de données) : linéaire, log-linéaire, quadratique, etc. Des articles de revue plus détaillés existent dans la littérature, le lecteur souhaitant une description plus détaillée de ces méthodes pourra se référer à..

Les méthodes ayant une complexité linéaire en N

Les méthodes d’initialisation (quelle que soit leur complexité algorithmique), peuvent être catégorisées en deux grandes familles : déterministes et non déterministes. La première famille regroupe les méthodes capables de fournir un résultat unique quel que soit le nombre d’exécution de l’algorithme. Les résultats générés par l’algorithme des K-moyennes sont dans ce cas reproductibles. La deuxième famille, quant-à-elle, regroupe les méthodes basées sur l’aléatoire. Elles fournissent à chaque fois une solution différente de la précédente

Les méthodes non déterministes

La première méthode d’initialisation proposée dans la littérature est celle de Forgy en 1965 [49]. Cette méthode consiste à choisir aléatoirement les K centres initiaux parmi les N instances de l’ensemble de données. La motivation derrière cette proposition réside dans le fait que la sélection aléatoire est susceptible de capter des points qui sont de bons candidats (par exemple, les points appartenant aux régions denses). Cependant, des points aberrants ou des points proches les uns des autres peuvent être choisis comme centres initiaux ce qui est clairement sous-optimal.
Bradley et Fayyad [24] ont proposé une méthode d’initialisation qui commence par une division aléatoire du jeu de données en B groupes. Ensuite, l’algorithme des K-moyennes est appliqué sur chacun de ces groupes en sélectionnant à chaque fois les centres aléatoirement. Les B × K centres obtenus sont alors regroupés et considérés comme une entrée de l’algorithme des K-moyennes. Ce dernier est ensuite exécuté B fois et est initialisé à chaque fois par des centres différents. Finalement, les centres qui forment la partition ayant une valeur minimale de MSE (i.e., l’erreur quadratique moyenne) sont considérés comme les centres finaux. Le principal avantage de cette méthode est qu’elle augmente l’efficacité du résultat par le fait que les centres initiaux sont obtenus après des exécutions multiples de l’algorithme des K-moyennes. Cependant, l’inconvénient majeur de cette méthode est qu’elle nécessite beaucoup d’effort de calcul. Sample est une simple méthode d’initialisation qui consiste à appliquer un algorithme de partitionnement sur un échantillon de l’ensemble de données (souvent 10%). Les centres résultant sont alors considérés comme les centres initiaux. L’inconvénient majeur de cette méthode est qu’il se peut que l’échantillon sélectionné ne soit pas vraiment un échantillon représentatif de l’ensemble des données