Le mécanisme de vote

Construire une collection de prédicteurs n’est pas une condition su_sante pour avoir une bonne classi_cation, une autre étape est très importante pour la construction d’une forêt aléatoire, c’est l’agrégation de l’ensemble des prédictions. L’objectif visé est que ce pré- dicteur _nal soit meilleur que chacun des prédicteurs individuels. Dans l’étape suivante nous présentons les travaux qui améliorent cette étape. Dans une forêt aléatoire classique, l’agrégation est représentée par un vote majoritaire des prédictions des classi_eurs individuels. Plusieurs travaux ont mis au point des alternatives au vote majoritaire par l’application d’autres mécanismes de vote. Robnik-Sikonja propose dans [53] d’étudier une amélioration du système de vote majoritaire classique des forêts aléatoires, dans le but d’obtenir des classi_eurs _naux plus performants. L’idée proposée est d’établir une sélection d’arbres de décision qui participent au vote _nal sur les données « similaires » en terme de voisinage.

Plus simplement, pour chaque exemple de la base de test, ce système détermine parmi les données d’apprentissage, celles qui lui ressemblent le plus. Il décide alors de ne faire con_ance qu’aux arbres de décision qui savent le mieux classer ces données dites « similaires ». Ce système de vote majoritaire s’appuie sur la procédure utilisée par Breiman dans [51] pour mesurer la similarité. Dans [56] Evanitha et al., présentent des améliorations au système du vote ordinaire. Il s’agit de proposer six diversités de l’algorithme de vote pondéré. Le premier algorithme [53] est le même que celui utilisé par Breiman dans [51]. Ce principe est basé sur les performances individuelles des arbres sur les donnés similaires. Le deuxième algorithme [88], le troisième [89] et le cinquième algorithme [90] sont basés sur des métriques entre les données. Le quatrième [91] et le sixième [92] utilisent la pondération des arbres selon leurs taux de classi_cation. Evanitha et al. e_ectuent un certain nombre d’expérimentations sur la base de données Alzheimer pour étudier l’évolution des performances des forêts aléatoires lorsqu’elles implémentent le vote pondéré ou le vote majoritaire classique.

État de l’art Il existe différentes possibilités pour la génération des ensembles de classi_eurs. La premi ère possibilité consiste à manipuler les données comme dans le Bagging [37] avec l’utilisation du principe de Bootstrap ou dans le RSM (Random Subspace Methods [39]) où nous appliquons uniquement un sous-ensemble aléatoire de l’espace des caractéristiques. Une deuxième possibilité d’induire des ensembles de classi_eurs est de faire appel a diff érents algorithmes de classi_cation (ou un algorithme avec di_érents paramètres) tout en formant chacun sur le même ensemble de données (ici nous parlons des méthodes d’ensemble hétérogènes) [93_96]. Une troisième possibilité consiste à combiner les deux premières méthodes en randomisant les données (Bootstraping 1 par exemple) et l’algorithme d’apprentissage (en utilisant diff érents algorithmes ou bien un seul avec di_érents paramètres). Dans cette optique, Breiman a proposé les Forêts Aléatoires (Random Forests) [51]. L’algorithme des Forêts Aléatoires est l’une des réalisations les plus populaires de la recherche consacrée à l’agrégation d’arbres aléatoires. Depuis leur proposition, plusieurs chercheurs ont tenté d’améliorer les forêts aléatoires par la modi_cation du mécanisme de vote ou la technique d’induction des arbres.

L’algorithme PERT (pour « PErfect Random Tree » les arbres aléatoires parfaits) en est un exemple, il a été proposé par Cutler et Guohua (2001) [97]. Dans cet algorithme, pour la division de chaque n÷ud non-terminal, deux exemples de di_érentes classes sont d’abord tirés au hasard parmi l’ensemble d’apprentissage. Ensuite, un attribut aléatoire est sélectionné et le point de découpage est aléatoirement et uniformément établi entre les valeurs de cet attribut pour les deux exemples pris au hasard. Geurts et al. (2006) [85] ont mis en place un autre algorithme intégrant plus d’aléatoire au sein de l’arbre de décision connu sous le nom d’Extra-trees (Pour Extremely Randomized trees) qui est similaire à PERT et qui combine la randomisation des attributs de la méthode RSM avec une sélection totalement aléatoire du point de découpage. Dans un autre travail, Panov et al. [71] ont combiné les Sous-espaces aléatoires et le Bagging pour construire de meilleurs ensembles. L’idée du SubBag (pour Subspaces Bagging) consiste à sélectionner des échantillons aléatoires avec remplacement à partir de l’ensemble originel (comme dans le Bagging) et pour chaque échantillon, seulement 75% des attributs sont choisis au hasard (en utilisant le RSM [39]). Ainsi, les sous-bases obtenues sont plus randomisées par rapport à celles générées par le Bootsrping. Dans leur papier [71], Panov et al. ont prouvé que cette approche donne des performances comparables à celles des forêts aléatoires, avec l’avantage supplémentaire d’être applicable à n’importe quel algorithme d’apprentissage sans la nécessité de le randomiser. Louppes et Geurts ont proposé dans [72] un travail similaire au SubBag appelé Random Patches où chaque modèle de l’ensemble est construit à partir d’un sous ensemble de données et de variables obtenues par tirage aléatoire de l’ensemble originel des données. Leur méthode est très e_cace pour l’application des grandes bases de données, car elle réduit considérablement l’espace mémoire et le temps d’exécution.

Optimisation des Forêts Aléatoires Floues 1 Objectifs Pour certains domaines d’application, il est essentiel de produire des procédures de classiffcation compréhensibles par l’utilisateur. C’est en particulier le cas pour l’aide au diagnostic médical où le médecin doit pouvoir interpréter les raisons du diagnostic automatique. A ce titre plusieurs travaux sont e_ectués a_n de développer des outils d’aide au diagnostic et de classi_cation des maladies interprétables et transparents. Les arbres de décision répondent à ces contraintes car ils représentent graphiquement un ensemble de règles et sont aisément interprétables mais leur instabilité a conduit à l’élaboration de méthodes comme le Bagging (pour Bootstrap Aggregating) [37]. La Forêt Aléatoire _Random Forest_ de Breiman [51] nous permet dans une certaine mesure de remédier à ce problème. Malgré la puissance de performance de ce dernier, la notion de stabilité n’est pas forcément présente. L’idée proposée est d’intégrer le _ou pour retrouver la stabilité grâce aux arbres _ous. Dans ce travail [59], nous traitons l’extraction de la connaissance à partir des données, en appliquant les forêts aléatoires _oues (Fuzzy Random Forest FRF) qui combinent la robustesse des arbres de décision, la puissance du caractère aléatoire qui augmente la diversité des arbres dans la forêt ainsi que la _exibilité de la logique _oue. Les FRF’s ont la spéci_cité de contrôler des données imparfaites, de réduire le taux d’erreurs et de mettre en évidence plus de robustesse et plus d’interprétabilité. De ce fait, nous nous focalisons sur l’étude des forêts aléatoires _oues, et plus particuli èrement leur l’amélioration par la méthode C-moyennes _ous (FCM : Fuzzy C-Means) et ce a_n d’optimiser l’apprentissage structurel des paramètres _ous. Cette technique permet de réduire le nombre de sous-ensembles _ous et de minimiser le nombre de règles pour une connaissance plus ciblée. Ce chapitre est composé de 5 sections décrites comme suit : en premier lieu, un état de l’art sur les forêts aléatoires _oues est réalisé dans ce contexte. En second lieu, nous présentons les méthodes et l’approche proposée. Par la suite, nous exposons les résultats et interprétations des algorithmes implémentés avec une synthèse sur les di_érentes techniques. En dernier lieu, seront présentées une conclusion générale et les perspectives futures pour ce travail .

Conclusion

Les méthodes de classi_cation ont pour but d’identi_er les classes auxquelles appartiennent des objets à partir de certains traits descriptifs. Elles conviennent en particulier au problème de la prise de décision automatisée. La procédure de classi_cation sera extraite automatiquement à partir d’un ensemble d’exemples, ce dernier consiste en la description d’un cas avec la classi_cation correspondante. Un système d’apprentissage doit alors, à partir de cet ensemble d’exemples, extraire une procédure de classi_cation, il s’agit en e_et d’extraire une règle générale à partir des données observées. La tâche générée tentera d’identi_er les classes auxquelles appartiennent des objets à partir de certains traits descriptifs et avoir une meilleure prédiction pour classi_er les nouveaux exemples. Les méthodes d’ensemble constituent l’une des principales orientations actuelles de la recherche sur l’apprentissage par machine, elles ont été appliquées à un large éventail de problèmes réels. Malgré l’absence d’une théorie uni_ée sur des ensembles de données, il y a beaucoup de raisons théoriques pour combiner plusieurs apprenants, et la preuve empirique con_rme l’e_cacité de cette approche. Parmi les algorithmes issus des méthodes d’ensemble, les forêts aléatoires (« Random Forest » RF) [51] sont l’une des derniers aboutissements de la recherche et les plus e_caces pour l’apprentissage d’arbres de décision. RF permet l’agrégation d’arbres randomisés tout en synthétisant les approches développées respectivement par Breiman 1996 [37], Amit et Geman 1997 [52].

Les performances d’une forêt d’arbres dépendent de la qualité des exemples qui la compose et de leur indépendance. Aussi les forêts aléatoires sont fondées sur des arbres non élagués a_n de réduire l’erreur de biais ; en outre, le processus aléatoire permet d’assurer une faible corrélation entre les arbres pour sauvegarder leur diversité. Nous nous sommes intéressés dans ce travail à étudier et améliorer les performances du modèle ensembliste Forêt Aléatoire sur une tâche de classi_cation reliée au domaine médical. À cet e_et, nous avons procédé en premier temps à une analyse de travaux e_ectués dans le domaine qui a permis de mettre en évidence plusieurs avantages ainsi que certaines limites des forêts aléatoires employées dans le cadre de la classi_cation des données médicales. Nous avons constaté en conséquence que les classi_eurs déjà proposés à base des forêts aléatoires font preuve de bonnes performances mais peuvent être encore améliorés pour apporter plus de précisions aux résultats. Nous avons en premier lieu, fait appel à la forêt aléatoire en utilisant l’indice de Gini et le vote majoritaire, puis nous avons procédé au développement de plusieurs variances du même classi_eur en utilisant l’indice de Déviance et Twoing rule au niveau du choix de la variable de division des n÷uds des arbres et en_n nous avons appliqué le vote pondéré comme méthode d’agrégation de l’ensemble d’arbres. En second lieu, une nouvelle méthode de génération d’arbres appelée Subspaces Random Forest (Sub_RF) qui regroupe les principes du Bagging, la méthode des Sous-espaces aléatoires et les Forêts Aléatoires a été essentiellement proposée. Cette méthode s’est, en e_et, avérée e_cace par rapport à la forêt aléatoire classique.

En dernier lieu, un modèle de classi_cation des forêts aléatoires _oues est proposé. Spéci- _quement, nous nous sommes plus intéresses à deux critères pour évaluer cette approche. Le premier est la stabilité des performances du classi_eur, le second est la bonne reconnaissance. L’algorithme de Fuzzy C-Means (FCM) a permis d’optimiser l’arbre Fuzzy CART en réduisant son temps d’exécution mais tout en gardant une très bonne stabilit é et un bonne reconnaissance. Avec l’hybridation de ces méthodes une extraction de connaissances par le système d’inférence _ou a pu être faite passant de 60 règles avec le Fuzzy CART à 2 avec Fuzzy FCM. La connaissance réalisée est plus _able, précise et su_samment simple pour être comprise, le tout en améliorant les performances avec un bon taux de classi_cation pour les deux bases de données. Il reste plusieurs questions et limites à nos approches auxquelles nous souhaitons répondre à l’avenir. Nous prévoyons dans les perspectives de ce travail, de renforcer ces résultats avec une analyse théorique ainsi que tester nos algorithmes sur de grandes bases de données. Aussi l’adaptation aux problèmes multi-classes et multi-labels [118].