Clustering prédictif du premier type

Le clustering prédictif du premier type englobe l’ensemble des algorithmes du clustering modifiés permettant de prédire correctement la classe des nouvelles instances sous la contrainte d’avoir un nombre minimal de clusters. Dans ce cadre d’étude, l’axe de prédiction est principalement privilégié. L’algorithme des K-moyennes prédictives du premier type proposé dans cette thèse est donc l’algorithme incorporant les méthodes de prétraitement et d’initialisation des centres les plus performants en termes de prédictions. Entrée – Un ensemble de données D, où chaque instance Xi est décrite par un vecteur de d dimensions et par une classe Yi ∈ {1, . . . , J}. – Le nombre de clusters souhaité, noté K. Début 1) Prétraitement des données : Conditional Info (CI-CI) 2) Initialisation des centres : Rocchio-And-Split Répéter 3) Affectation : générer une nouvelle partition en assignant chaque instance Xi au groupe dont le centre est le plus proche. Xi ∈ Ck∀j ∈ 1, . . . , K k = argminj k Xi − µj k avec µk est le centre de gravité du cluster Ck. 4) Représentation : calculer les centres associés à la nouvelle partition µk = 1 Nk P Xi∈Ck Xi jusqu’à ce que (convergence de l’algorithme) 5) Attribution des classes aux clusters formés : vote majoritaire 6) Prédiction de la classe des nouvelles instances : un plus proche voisin Fin Algorithme 8 – Algorithme des K-moyennes prédictives du premier type pour le cas CI-RS En s’appuyant sur les résultats présentés dans la figure 6.1, l’algorithme des K-moyennes prédictives du premier type proposé est l’algorithme intégrant la méthode supervisée du prétraitement des données Conditional Info (CI) et la méthode supervisée d’initialisation des centres Rocchio-And-Split (RS). Pour un nombre fixe de clusters (K), l’algorithme 8 présente sous forme des lignes de code l’algorithme des K-moyennes prédictives du premier type. L’un des principaux avantages de cet algorithme est qu’il n’est exécuté qu’une seule fois en raison de l’utilisation d’une méthode d’initialisation déterministe (i.e., la méthode Rocchio-AndSplit). Cette section est consacrée à la comparaison des performances prédictives de cet algorithme des K-moyennes prédictives avec celles d’autres algorithmes du clustering prédictif les plus répandus dans la littérature. Cette section expérimentale est divisée en deux grandes parties. Dans la première partie (Section 6.2.1), on considère le nombre de clusters (K) comme une entrée de l’algorithme. Pour chaque jeu de données, on considère que le nombre de clusters (K) est égal au nombre de classes (J). Dans ce cas, le problème du départ devient un problème de classification supervisée. L’objectif de cette première partie est de tester la capacité de l’algorithme des Kmoyennes prédictives présenté ci-dessus à atteindre l’objectif des algorithmes de la classification supervisée (i.e., prédire correctement la classe des nouvelles instances). La deuxième partie (Section 6.2.2) considère le nombre de clusters comme une sortie de l’algorithme (K≥J). L’objectif de cette partie est de tester la capacité de l’algorithme des Kmoyennes prédictives à atteindre l’objectif des algorithmes de clustering prédictif du premier 6.2. Clustering prédictif du premier type 137 type (i.e., prédire correctement la classe des nouvelles instances sous contrainte d’obtenir un nombre minimal de clusters). Les jeux de données utilisés dans cette partie expérimentale sont des jeux de données de l’UCI. Le tableau 6.1 présente les caractéristiques de ces jeux de données. Ces derniers ont été choisis afin d’avoir des bases de données illustratives diverses dans ce chapitre de synthèse en termes de nombre de classes J, de variables (continues Mn et/ou catégorielles Mc) et d’instances N. Pour chacun de ces jeux de données, on effectue un 2 × 5 folds cross validation.

 Le nombre de clusters (K) est une entrée

 Dans cette partie expérimentale, on cherche à tester la capacité de l’algorithme des Kmoyennes prédictives présenté dans l’algorithme 8 à atteindre l’objectif des algorithmes de la classification supervisée. Les performances prédictives de l’algorithme des K-moyennes prédictives seront d’une part comparées à celles de l’algorithme des K-moyennes standard. Cette comparaison nous permet de savoir à quel point la version modifiée parvient à dépasser la version originale dans le contexte de la classification supervisée. D’autre part, l’algorithme des K-moyennes prédictives sera comparé à un des algorithmes de la classification supervisée le plus interprétable et le plus répandu dans la littérature, à savoir l’arbre de décision. Ce dernier est considéré comme une hiérarchie de clusters où chaque feuille représente un cluster. Pour une comparaison cohérente, le nombre de feuilles généré par l’arbre de décision est contrôlé de telle sorte d’avoir un nombre égal au nombre de classes du jeu de données utilisé (la taille du modèle est fixé K = J). Pour évaluer la performance prédictive de ces trois algorithmes, le critère « Variation d’Information » (VI) est utilisé. Plus la valeur de VI est proche de 0, meilleure est la performance prédictive du modèle. Les deux figures 6.4 et 6.5 présentent les performances prédictives (en termes de VI) des trois algorithmes d’apprentissage lorsque le nombre de clusters (K) est égal au nombre de classes (J). Les résultats des deux figures montrent que l’algorithme des K-moyennes prédictives parvient à atteindre soit de meilleures performances prédictives par rapport à l’arbre de décision (résultats de la figure 6.4) ou des performances compétitives avec celles de l’arbre de décision (résultats de la figure 6.5). De plus, l’algorithme des K-moyennes prédictive arrive à atteindre des performances prédictives significativement meilleures que celles obtenues par l’algorithme des K-moyennes standard sachant que ce dernier est exécuté 100 fois avec différentes initialisations (en utilisant la même méthode K++) pour choisir la meilleure partition.

Le nombre de clusters (K) est une sortie

 Dans cette partie expérimentale, on cherche à tester la capacité de l’algorithme des Kmoyennes prédictives présenté par l’algorithme 8 à atteindre l’objectif du clustering prédictif du premier type. Il s’agit ici de prédire correctement la classe des nouvelles instances sous la contrainte d’obtenir un nombre minimal de clusters (K). Les algorithmes utilisés dans cette comparaison sont : 

1. L’arbre de décision (A.D) : l’algorithme utilisé est l’arbre de décision de type CART. Dans cette étude expérimentale, nous utilisons l’algorithme élagué existant dans le logiciel R dans la librairie rpart [98]. Le nombre de clusters dans ce cas correspond au nombre de feuilles généré dans la phase d’apprentissage. 
2. Algorithme de Eick (Eick) : cet algorithme nécessite un paramètre utilisateur β qui permet d’équilibrer le critère permettant d’évaluer la pureté des clusters en termes de classes et la contrainte sur le nombre de clusters générés. Les résultats présentés dans cette étude expérimentale sont obtenus lorsque β est égal à 0.1. Dans [46], Eick et al. montrent qu’avec cette valeur, ils parviennent à obtenir de meilleures performances. Pour plus de détails sur cet algorithme, voir la section 2.5.2 du chapitre 2. 6.2. Clustering prédictif du premier type 139 3. 

L’arbre du clustering prédictif (PCT)

l’algorithme utilisé dans cette partie expérimentale est l’algorithme présentédans « http ://clus.sourceforge.net/doku.php ».Les résultats présentés dans cette section sont obtenus en utilisant l’arbre élagué présenté par cet algorithme. Dans ce cas, le nombre de clusters (K) correspond au nombre de feuilles générées par celui-ci dans la phase d’apprentissage. Pour plus de détails sur cet algorithme, voir la section 2.5.2 du chapitre 2. 4. 

Les K-moyennes prédictives (P.C)

pour avoir le nombre de clusters comme une sortie, l’algorithme des K-moyennes prédictives présenté par l’algorithme 8, est exécuté plusieurs fois avec différents nombres de clusters K dans le but de sélectionner la partition optimale au sens du clustering prédictif du premier type. Cette sélection est effectuée à l’aide de l’indice de rand ajusté « ARI ». 5. 

Les K-moyennes standard (S.C)

pour avoir le nombre de clusters comme une sortie, l’algorithme des K-moyennes standard est exécuté plusieurs fois avec différent nombres de clusters K dans le but de sélectionner la partition optimale au sens du clustering prédictif du premier type. Cette sélection est effectuée à l’aide de l’indice de rand ajusté « ARI ». Les deux figures 6.6 et 6.7 présentent les performances prédictives (en termes de VI) des cinq modèles d’apprentissage. Les résultats de ces figures montrent qu’avec la supervision des deux étapes de prétraitement des données et d’initialisation des centres, l’algorithme des K-moyennes prédictives parvient à être très compétitif avec l’arbre de clustering prédictif (PCT). Cependant, l’algorithme des K-moyennes prédictives parvient à obtenir un nombre plus faible de clusters par rapport aux autres algorithmes. À titre d’exemple, pour le jeu de données German présenté dans la partie milieu de la figure 6.6, l’algorithme des K-moyennes prédictives obtient deux à trois clusters. Par contre, les arbres de décision, PCT, l’algorithme de Eick et les K-moyennes standard obtiennent respectivement 6, {63, 75}, {5 − 9}, 9 clusters.