ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 16/6 - 2002  - pp.685-703  - doi:10.3166/ria.16.685-703
TITRE
Construction d'arbres de décision par optimisation

RÉSUMÉ
L'apprentissage par arbres se prête mal au traitement des très grandes bases de données dans la mesure où il nécessite à chaque noeud de scanner à nouveau l'ensemble de la base. Dans cet article, nous proposons de limiter l'espace de recherche des arbres à celui des arbres par niveau où les différents noeuds de chaque niveau sont segmentés par la même variable. Une telle simplification permet de transformer le problème d'apprentissage en un problème d'optimisation qui autorise une stratégie gloutonne ne nécessitant qu'une seule passe sur les données. Dans le cas de données booléennes, le critère d'optimisation retenu est celui de la maximisation du coefficient de détermination R2 , alors que dans le cas de données catégorielles multivaluées, on se ramène au cas booléen sans altérer la complexité de l'algorithme en raisonnant dans l'espace des paires d'individus décrites par les indicatrices de co-étiquetage. Notre stratégie d'optimisation pénalise la profondeur de l'arbre par le recours à la correction du R2 . Les expérimentations ont montré que la précision en généralisation des arbres par niveau n'est pas détériorée par rapport aux arbres usuels.


ABSTRACT
Induction of decision trees is not well adapted to handling of very large databases. It requires to access the whole database at each node. In this paper, we propose to limit the tree search space to oblivious decision trees The different nodes at the same level are splitted with the same attribute. Such a simplification allows to turn the learning problem into an optimization problem which relies on an hill-climbing strategy requiring only one pass over the database. In the case of boolean attributes, the optimization criterion is the determination coefficient R2 maximisation. Multi-valued attributes can be reduced to boolean attributes by rewriting the problem in the space of pairwise examples spanned with the co-labels of the original attributes, without increasing the complexity of the algorithm. Our strategy penalizes tree depth by using adjusted R2 . The experiments show that generalization error rate of our trees is as good as the one of C4.5, while maintaining the intelligibility of the results.


AUTEUR(S)
Ricco RAKOTOMALALA, Stéphane LALLICH

MOTS-CLÉS
apprentissage, arbre de décision par niveau, optimisation, règles.

KEYWORDS
machine learning, oblivious decision tree, optimization, rules.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (143 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier