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

 Comme évoqué précédemment dans le chapitre 2 Section 2.5.2, il existe deux types de clustering prédictif. Le premier type consiste à discerner un nombre minimal de groupes d’instances purs en termes de classes dans le but de prédire ultérieurement la classe des nouvelles instances (voir la figure 5.1). Il s’agit de découvrir partiellement la structure interne de la variable cible. Comme pour la classification supervisée, le but majeur de ces algorithmes est de prédire correctement la classe des nouvelles instances. De ce fait, pour évaluer la qualité des résultats issus de ce type d’algorithme, l’un des critères supervisés dédiés à la classification supervisée, tels l’indice de rand Ajusté (ARI) [57] ou la variation d’information (VI) [76], peut être utilisé. …. Figure 5.1 – Premier type du clustering prédictif Figure 5.2 – Deuxième type du clustering prédictif …. Le deuxième type, quant à lui, a pour but de discerner des groupes d’instances compacts, purs en termes de classe et éloignés les uns des autres (voir la figure 5.2). Contrairement à la classification supervisée, les algorithmes appartenant à ce type d’apprentissage cherchent à découvrir la structure interne complète de la variable cible. Puis, munie de cette structure, ils cherchent à prédire la classe des nouvelles instances. Dans ce cadre d’étude, aucun axe n’est privilégié par rapport à l’autre (i.e.,, la description et la prédiction). Une bonne partition au sens du deuxième type du clustering prédictif est donc celle qui réalise un bon compromis entre la description et la prédiction. Le critère choisi pour mesurer la qualité des résultats issus par les algorithmes du deuxième type du clustering prédictif doit impérativement équilibrer les trois points suivant : 1. Inertie intra-clusters minimale. 2. Inertie inter-clusters maximale. 3. Taux de bonnes classifications maximal. Ce chapitre traite exclusivement la problématique d’évaluation de la qualité pour l’algorithme des K-moyennes prédictives du deuxième type. Dans la phase d’apprentissage, l’algorithme des Kmoyennes prédictives nécessite une évaluation de la qualité à deux niveaux : 1) Pour le choix de la meilleure partition à K fixé. En effet, l’algorithme des K-moyennes prédictives converge rarement vers un optimum global. Pour cette raison, pour un nombre fixe de clusters, cet algorithme doit être exécuté plusieurs fois dans le but de choisir, via un critère analytique, la meilleure partition au sens du deuxième type du clustering prédictif, 2) Pour la sélection du nombre optimal de clusters (Kopti). En effet, l’algorithme des K-moyennes prédictives nécessite une connaissance a priori du nombre optimal de clusters ce qui n’est pas une tâche aisée dans la réalité. Pour surmonter ce problème, l’algorithme peut être exécuté plusieurs fois avec différents nombres de 110 Chapitre 5. Évaluation de la qualité de l’algorithme des K-moyennes prédictives clusters dans le but de sélectionner le nombre optimal de clusters permettant ainsi de mieux décrire la structure interne de la variable cible. Le critère utilisé dans ce cas doit impérativement être capable de comparer deux partitions ayant des nombres de clusters différents ce qui n’est pas une obligation pour le critère utilisé au premier niveau d’évaluation. Les critères qui peuvent être utilisés pour choisir la meilleure partition (à K fixé) sont notamment les critères supervisés tel que l’indice de Rand Ajusté « ARI » ou les critères non supervisés tel que l’erreur quadratique moyenne « MSE ». Le choix du critère à utiliser aura donc un impact direct sur les résultats : la meilleure partition va donc en dépendre. Pour pouvoir effectuer ce choix, il est important tout d’abord de connaître l’influence de l’utilisation d’un des critères (supervisé ou non supervisé) sur les résultats obtenus. Dans ce contexte d’étude, le bon critère à utiliser est celui qui conduit soit à une amélioration significative au niveau des deux axes (i.e., la description et la prédiction) vis-à-vis des résultats obtenus par les autres critères ou soit à une amélioration significative sur l’un des deux axes (par exemple, 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) de l’autre axe (voir Figure 5.3). La section 5.2.1 de ce chapitre présente une étude expérimentale permettant de répondre à cette question. Pour le deuxième niveau d’évaluation, les critères supervisés et non supervisés existant dans la littérature n’arrivent pas dans tous les cas à sélectionner le nombre optimal de clusters permettant de mieux découvrir la structure interne de la variable cible. Par exemple, pour les critères non supervisés, cette incapacité s’illustre essentiellement dans le cas de la présence des régions denses possédant au moins deux classes. En effet, la majorité de ces critères se basent sur une métrique permettant de mesurer la proximité entre les instances indifféremment de leurs classes d’appartenance. Par conséquent, des instances de différentes classes peuvent être vues comme similaires si elles sont proches en termes de distance. Pour tenter de résoudre cette problématique, ce chapitre propose une version supervisée de l’indice de Davies-Bouldin, noté SDB. Cet indice est basé sur une nouvelle mesure de similarité ’supervisée’ permettant de relier la proximité des instances en termes de distance à leur classe d’appartenance : deux instances sont considérées comme similaires si et seulement si elles sont proches en termes de distance et appartiennent à la même classe. Le lecteur pourra trouver une description plus détaillée de cette problématique dans la section 5.3 de ce chapitre.

É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 112 Chapitre 5. Évaluation de la qualité de l’algorithme des K-moyennes prédictives 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é.