Évaluation de la qualité de l’algorithme des K-moyennes prédictives

Évaluation de la qualité de l’algorithme des K-moyennes prédictives

Évaluation de la qualité du deuxième type du clustering prédictif

Influence du choix de la meilleure partition 

Dans la phase d’apprentissage, l’algorithme des K-moyennes prédictive converge rarement vers un optimum global. De ce fait, pour un nombre fixe de clusters, cet algorithme doit être exécuté R > 1 fois (voir la boucle Pour de l’algorithme 7) dans le but de choisir la meilleure partition au sens du clustering prédictif du deuxième type. 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. 2) Initialisation des centres. Pour un nombre fixé de partitions, noté R faire 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 = minj 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) Fin Pour 5) Choix de la meilleure partition parmi les R partitions. 6) Attribution des classes aux clusters formés. 7) Prédiction de la classe des nouvelles instances. Fin Sortie – Chaque cluster est représenté par un prototype qui possède la même prédiction de classe. – Chaque cluster est associé à une description donnée par le biais de langage B. – L’inertie intra-clusters est minimale (l’homogénéité des instances est maximale). – L’inertie inter-clusters est maximale (la similarité entre les clusters est minimale). – Le taux de bonnes classifications est maximal. Algorithme 7 – Algorithme des K-moyennes prédictives du deuxième type Il est à rappeler qu’une bonne partition au sens du deuxième type du clustering prédictif est celle qui réalise un bon compromis entre la description et la prédiction. Les trois points à respecter lors de l’évaluation de la qualité des résultats sont notamment la compacité, la séparabilité et la pureté des clusters en termes de classe. Dans ce contexte d’étude, les critères existant dans la littérature permettant de choisir la meilleure partition sont les critères supervisés tels que l’ARI ou les critères non supervisés tels que la MSE. Cependant, les critères supervisés privilégient principalement l’axe de prédiction tandis que les critères non supervisés privilégient principalement l’axe de description. Le choix du critère à utiliser aura donc un impact direct sur la qualité des résultats au sens du clustering prédictif : la meilleure partition va en dépendre. Suivant ce raisonnement, il est naturel de se demander quel est le critère (supervisé ou non supervisé) le plus adéquat à utiliser dans notre cadre d’étude ? Dans ce contexte d’étude, un bon critère (supervisé ou non supervisé) est défini comme celui qui conduit : — soit à une amélioration significative au niveau des deux axes vis-à-vis des résultats obtenus par les autres critères d’évaluation (i.e., les résultats obtenus via ce critère ont tendance à suivre la flèche 3 de la figure 5.3 si les deux critères utilisés pour évaluer l’axe description et l’axe de prédiction sont à maximiser). — soit à une amélioration significative au niveau d’un axe (par exemple, au niveau de l’axe de prédiction si le critère supervisé ARI est utilisé) et à une détérioration très légère (voire aucune détérioration) au niveau de l’autre axe : les résultats obtenus pour la meilleure partition via le critère ont tendance à suivre la flèche 1 de la figure 5.3 si un critère supervisé tel que l’ARI est utilisé pour le choix, ou bien de suivre la flèche 2 de la figure 5.3 si un critère non supervisé tel que MSE est utilisé. Pour être en mesure de connaître l’influence du choix du critère d’évaluation sur la qualité des résultats et donc connaître le critère (ARI ou MSE) le plus adéquat à utiliser pour choisir la meilleure partition, une étude expérimentale est alors menée en utilisant plusieurs jeux de données de l’UCI. Cette étude expérimentale nous permet également d’avoir une idée sur le degré de la corrélation entre les deux critères ARI et MSE. Dans cette étude, pour chaque jeu de données, le nombre de clusters est varié entre J et J + 10, J étant le nombre de classes à prédire. Pour un nombre fixe de clusters, l’algorithme des K-moyennes est exécuté 100 fois dans le but de choisir la meilleure partition en utilisant soit l’ARI soit la MSE. La méthode d’initialisation utilisée à ce stade est la méthode qui garantit un bon compromis entre la prédiction et la description à savoir, S-Bisecting (voir Chapitre 4 Section 4.6).

Lire sur cLicours.com :  Conseils, compléments et exercices algorithme

Choix du nombre optimal de clusters 

L’algorithme des K-moyennes prédictives nécessite une connaissance a priori du nombre optimal du cluster (voir Algorithme 7). Or, il est très difficile dans la réalité de connaître à l’avance, pour chaque jeu de données, ce nombre optimal. Pour remédier à ce problème, l’algorithme des K-moyennes prédictives doit être exécuté plusieurs fois avec différents nombres de clusters dans le but de sélectionner le nombre de clusters permettant ainsi de découvrir au mieux la structure interne de la variable cible. Pour le choix du nombre optimal de clusters, le critère recherché doit être capable de sélectionner la partition découvrant la structure interne « complète » de la variable cible. Il s’agit ici de pouvoir comparer deux partitions ayant un nombre de clusters différents au sens du deuxième type du clustering prédictif. Les critères supervisés et non supervisés existant dans la littérature permettant de comparer des partitions avec différents nombre de clusters n’arrivent pas toujours à détecter le nombre de clusters optimal. En effet, les critères proposés dans le cadre de la classification supervisée privilégient principalement l’axe de prédiction par rapport à l’axe de description. D’une part, l’utilisation des critères tels que la précision (ACC) et l’aire sous la courbe de ROC (AUC) pour mesurer la qualité des résultats s’avère inappropriée dans ce cadre d’étude : l’augmentation du nombre de clusters induit souvent une amélioration, ou une stagnation, au niveau de la performance prédictive du modèle. Par conséquent, la partition optimale sélectionnée par ce type de critère peut contenir un nombre de clusters très grand par rapport au « réel » nombre. D’autre part, l’utilisation des critères d’évaluation tels que l’indice de rand ajusté (ARI) ou les critères basés sur la théorie d’information comme la variation d’information (VI), s’avère également insuffisante : lorsque deux sous-groupes différents d’instances de même classe sont proches comme illustré dans la figure 5.9 (les deux sous-groupes de la classe rouge situés au milieu de la figure), ces deux critères cherchent à les fusionner ensemble. Dans le cas extrême, ces deux sous-groupes peuvent être également fusionnés même s’ils sont très éloignés l’un de l’autre. Enfin, les critères non supervisés proposés dans la littérature pour évaluer la qualité des résultats issus des algorithmes du clustering traditionnel privilégient principalement l’axe de description. L’utilisation de tels critères dans le cadre du clustering prédictif s’avère inappropriée. En effet, l’incapacité des critères non supervisés à mesurer la qualité des résultats issus des algorithmes du clustering prédictif s’illustre principalement dans le cas de la non corrélation entre les clusters et les classes. C’est le cas de la présence de plus de deux classes dans au moins une des régions denses. À titre d’exemple, le jeu de données présenté dans la figure 5.10 possède deux régions denses caractérisées par la présence des deux classes (rouge et noire). Pour cet exemple, il est clair que la partition optimale suivant ces critères est celle qui contient le nombre de régions denses comme nombre de clusters (i.e., 4 clusters). Par conséquent, deux groupes formés dans ce cas vont contenir des instances de classes différentes ce qui conduit à une détérioration au niveau de la prédiction..

Cours gratuitTélécharger le cours complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.

Comments (1)