LIP6 1998/014
- Thèse
Apprentissage inductif en présence de données imprécises.:
Construction et utilisation d'arbres de décision flous - Ch. Marsala
- 232 pages - 16/03/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.014.ps.gz - 505 Ko
- Contact : Christophe.Marsala (at) nulllip6.fr
- Ancien Thème : APA
- Mots clés : Théorie des sous-ensembles flous, Apprentissage inductif, Arbre de décision flou, Mesures de discrimination, Discrétisation floue
- Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
L'extraction automatique de connaissances à partir d'un ensemble de données permet la découverte de relations entre ces données, qui peuvent ensuite être généralisées à toute nouvelle donnée.
L'apprentissage par arbres de décision est une telle méthode d'induction.
Etant donné un ensemble d'exemples décrits par des valeurs d'attributs et associés à une valeur de classe, l'apprentissage par arbres de décision permet de construire un ensemble de règles qui exprime les relations existantes entre les valeurs des attributs et les valeurs de la classe. Dans cette thèse, nous nous proposons d'étendre les méthodes d'apprentissage par arbres de décision en utilisant la théorie des sous-ensembles flous pour prendre en compte l'imprécision dans la description des données, ceci permettant alors la construction d'arbres de décision flous.
Une formalisation des algorithmes de construction d'arbres de décision est proposée.
Elle met en évidence les différents paramètres qui différencient de tels algorithmes : la mesure de discrimination permet de minimiser la taille des arbres et d'obtenir de bons résultats en généralisation ; la stratégie de partitionnement détermine la façon de découper la base d'apprentissage durant le développement de l'arbre ; et le critère d'arrêt définit les choix d'arrêt du développement de l'arbre. Ainsi, l'apport de la théorie des sous-ensembles flous pour la prise en compte de l'imprécision s'effectue relativement à chacun de ces paramètres. Nous donnons la méthode d'utilisation de tels arbres pour le classement d'objets inconnus, basée sur l'utilisation d'une mesure de satisfiabilité pour évaluer l'adéquation des valeurs de l'objet avec les modalités présentes dans les tests des noeuds de l'arbre. La stabilité de cette méthode d'inférence est étudiée. Cette étude met en évidence la robustesse de la décision prise à l'aide d'un tel système. Nous proposons ensuite une méthode d'étude des mesures de discrimination utilisées dans la construction d'un arbre de décision. Cette méthode est basée sur un modèle hiérarchique de fonctions. Elle permet de construire de nouvelles mesures et d'en valider la pertinence pour l'évaluation du pouvoir discriminant d'un attribut. En outre, cette méthode facilite l'introduction des éléments de la théorie des sous-ensembles flous dans de telles mesures. La construction d'un arbre de décision flou nécessite de disposer d'une partition floue de référence sur l'univers des valeurs d'un attribut numérique ou numérique-symbolique. Or une telle partition est souvent inconnue ou difficile à obtenir auprès d'éventuels experts. C'est pourquoi, nous introduisons une méthode automatique de construction d'une partition floue sur un ensemble de valeurs. Cette méthode est basée sur l'utilisation des opérateurs de la théorie de la morphologie mathématique formalisés à l'aide de la théorie des langages formels. Elle permet le filtrage d'une base d'apprentissage, considérée comme un mot sur le langage défini par les valeurs de la classe, pour en faire ressortir des fonctions d'appartenance de référence.
Ces travaux ont donné lieu à la réalisation du système informatique Salammbô. Ce système permet la construction d'arbres de décision flous, en offrant un choix de mesures de discrimination et met en oeuvre la classification de nouveaux exemples avec l'arbre flou construit, en utilisant divers types d'opérateurs d'inférence.
Afin de pallier les difficultés à mesurer le pouvoir discriminant d'un attribut relativement à un ensemble de plus de deux classes simultanément, nous avons été amenés à réaliser le système informatique Tanit. Ce système construit une forêt d'arbres de décision flous en utilisant plusieurs systèmes Salammbô. Chaque Salammbô construit un arbre de décision flou ne devant apprendre à reconnaître que deux classes : une classe contre toutes les autres réunies. Lors de la phase de classification de nouveaux exemples, Tanit agrège les degrés d'appartenance renvoyés par toutes les Salammbô. Différentes méthodes d'agrégation de données ont été implémentées, et l'indépendance des classifieurs d'un système multi- classifieurs, basée sur les travaux de Kampé de Fériet, est étudiée.
Les systèmes Salammbô et Tanit ont été expérimentés sur différents types de bases d'apprentissage. Ces tests ont permis de mettre en évidence la plus grande explicabilité des décisions prises par l'intermédiaire d'un arbre de décision flou, la taille des arbres de décision flous obtenus ainsi que de meilleurs résultats en phase de généralisation.
L'apprentissage par arbres de décision est une telle méthode d'induction.
Etant donné un ensemble d'exemples décrits par des valeurs d'attributs et associés à une valeur de classe, l'apprentissage par arbres de décision permet de construire un ensemble de règles qui exprime les relations existantes entre les valeurs des attributs et les valeurs de la classe. Dans cette thèse, nous nous proposons d'étendre les méthodes d'apprentissage par arbres de décision en utilisant la théorie des sous-ensembles flous pour prendre en compte l'imprécision dans la description des données, ceci permettant alors la construction d'arbres de décision flous.
Une formalisation des algorithmes de construction d'arbres de décision est proposée.
Elle met en évidence les différents paramètres qui différencient de tels algorithmes : la mesure de discrimination permet de minimiser la taille des arbres et d'obtenir de bons résultats en généralisation ; la stratégie de partitionnement détermine la façon de découper la base d'apprentissage durant le développement de l'arbre ; et le critère d'arrêt définit les choix d'arrêt du développement de l'arbre. Ainsi, l'apport de la théorie des sous-ensembles flous pour la prise en compte de l'imprécision s'effectue relativement à chacun de ces paramètres. Nous donnons la méthode d'utilisation de tels arbres pour le classement d'objets inconnus, basée sur l'utilisation d'une mesure de satisfiabilité pour évaluer l'adéquation des valeurs de l'objet avec les modalités présentes dans les tests des noeuds de l'arbre. La stabilité de cette méthode d'inférence est étudiée. Cette étude met en évidence la robustesse de la décision prise à l'aide d'un tel système. Nous proposons ensuite une méthode d'étude des mesures de discrimination utilisées dans la construction d'un arbre de décision. Cette méthode est basée sur un modèle hiérarchique de fonctions. Elle permet de construire de nouvelles mesures et d'en valider la pertinence pour l'évaluation du pouvoir discriminant d'un attribut. En outre, cette méthode facilite l'introduction des éléments de la théorie des sous-ensembles flous dans de telles mesures. La construction d'un arbre de décision flou nécessite de disposer d'une partition floue de référence sur l'univers des valeurs d'un attribut numérique ou numérique-symbolique. Or une telle partition est souvent inconnue ou difficile à obtenir auprès d'éventuels experts. C'est pourquoi, nous introduisons une méthode automatique de construction d'une partition floue sur un ensemble de valeurs. Cette méthode est basée sur l'utilisation des opérateurs de la théorie de la morphologie mathématique formalisés à l'aide de la théorie des langages formels. Elle permet le filtrage d'une base d'apprentissage, considérée comme un mot sur le langage défini par les valeurs de la classe, pour en faire ressortir des fonctions d'appartenance de référence.
Ces travaux ont donné lieu à la réalisation du système informatique Salammbô. Ce système permet la construction d'arbres de décision flous, en offrant un choix de mesures de discrimination et met en oeuvre la classification de nouveaux exemples avec l'arbre flou construit, en utilisant divers types d'opérateurs d'inférence.
Afin de pallier les difficultés à mesurer le pouvoir discriminant d'un attribut relativement à un ensemble de plus de deux classes simultanément, nous avons été amenés à réaliser le système informatique Tanit. Ce système construit une forêt d'arbres de décision flous en utilisant plusieurs systèmes Salammbô. Chaque Salammbô construit un arbre de décision flou ne devant apprendre à reconnaître que deux classes : une classe contre toutes les autres réunies. Lors de la phase de classification de nouveaux exemples, Tanit agrège les degrés d'appartenance renvoyés par toutes les Salammbô. Différentes méthodes d'agrégation de données ont été implémentées, et l'indépendance des classifieurs d'un système multi- classifieurs, basée sur les travaux de Kampé de Fériet, est étudiée.
Les systèmes Salammbô et Tanit ont été expérimentés sur différents types de bases d'apprentissage. Ces tests ont permis de mettre en évidence la plus grande explicabilité des décisions prises par l'intermédiaire d'un arbre de décision flou, la taille des arbres de décision flous obtenus ainsi que de meilleurs résultats en phase de généralisation.