Apprentissage inductif en présence de données imprécises :
Construction et utilisation d'arbres de décision flous

Ch. Marsala

LIP6 1998/014: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
232 pages - Mars/March 1998 - French document.

PostScript : 493 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Apprentissage et Acquisition de Connaissances

Titre français : Apprentissage inductif en présence de données imprécises :
Construction et utilisation d'arbres de décision flous
Titre anglais : Inductive learning in presence of imprecise data:
Methods to build and to use fuzzy decision trees

Résumé : 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.

Abstract : The automatic extraction of knowledge from a set of data enables us to discover relationships between these data. Furthermore, these relationships can be generalized to new data. Learning by decision trees is such an inductive method of generalization. Given a set of data described by means of values for attributes and associated with a value for a class, learning by decision trees enables us to construct a set of rules that express the relationships between the values of attributes and the values of the class. In this thesis, we propose to extend the classical ID3 method of decision tree learning by means of fuzzy subset theory. This theory enables us to take into account imprecision in the description of data and, thus, to construct fuzzy decision trees.
A new formalization of the algorithms of construction of decision trees is proposed. It highlights the various parameters that differentiate an algorithm from another: the measure of discrimination is used to minimize the size of the trees and to select coherent nodes for the tree to obtain good results during the generalization step; the splitting strategy defines how to split the training set during the construction of the tree; and the stopping criterion defines when the development of a path of the tree has to be stopped. By means of this formalization, introduction of fuzzy subset theory can be done with respect to the specificity of each kind of parameters.
The method to use fuzzy decision trees when classifying previously unknown cases is given. It is based on the use of a measure of satisfiability to evaluate the adequation between description values of the case and the corresponding values that appear in nodes of the tree. A study of the stability of this method of inference is presented. It highlights the robustness of the decision given by such a fuzzy system.
Afterwards, we propose a method to study the measures of discrimination used during the construction of decision trees. This method is given as a hierarchical model of functions.
It enables us to construct new measures and to validate their pertinence for the evaluation of the discriminating power of an attribute. Moreover, it makes easier the introduction of the fuzzy subset theory in such measures.
Fuzzy decision tree construction requires a fuzzy partition on the universe of values of numerical or numerical-symbolic attribute. However, such a partition is often unknown or it is obtained with difficulties from an expert of the corresponding domain. This is why we introduce a new automatic method of construction of such fuzzy partitions on a set of values. This method is based on the use of operators from mathematical morphology theory. In our context, these operators are formalized by means of the formal language theory. This method allows filtering a training set so as to highlight cores of membership functions related to values of the class.
These works have been implemented as a computer system named Salammbô. This system enables us to construct fuzzy decision trees and to make a choice between several measures of discrimination to build a tree. Classification of new cases is done with the obtained fuzzy tree by means of various kinds of inference rule operators.
To mitigate the consequence of the difficulties lying in the simultaneously measure of the discriminating power of an attribute related to more than two values of the class, we implemented a computer system named Tanit. This system enables us to construct a forest of fuzzy decision trees by means of several Salammbô systems. A fuzzy tree is constructed by each Salammbô to recognize only two values of the class: one value versus all the others joined together.
During the classification of new cases, the membership degrees of values of the class given by each Salammbô have been aggregated by the Tanit system. Several methods of aggregation have been implemented and a study of the independence of such a multi-classifier system is done. This study is based on the previous works of Kampé de Fériet related to the independence of a set of observers.
Both Salammbô and Tanit systems have been tested on various kinds of training sets. These tests enable us to highlight the greater understandability and explainability of decisions given by a fuzzy decision tree. Moreover, it can be shown that the size of fuzzy trees is lower than the size of classical trees, and their classification rate is also improved.

Mots-clés : Théorie des sous-ensembles flous, Apprentissage inductif, Arbre de décision flou, Mesures de discrimination, Discrétisation floue

Key-words : Fuzzy subset theory, Inductive learning, Fuzzy decision tree, Measures of discrimination, Fuzzy partitioning

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr