[PDF] Post-élagage Indirect des Arbres de Décision dans le Data Mining

View - Download Post-élagage Indirect des Arbres de Décision dans le Data Mining

Previous PDF

Next PDF

SETIT 2007

4th International Conference: Sciences of Electronic,

Technologies of Information and Telecommunications

March 25-29, 2007 - TUNISIA

- 1 - Post-élagage Indirect des Arbres de Décision dans le

Data Mining

Mansour Mededjel

*, Hafida Belbachir** Département d'Informatique, Faculté des Sciences et Sciences d e l'Ingénieur, Université Abdelhamid Ibn

Badis - Mostaganem, Algérie.

mededjel_mansour@yahoo.fr Département d'Informatique, Faculté des Sciences, Université des Sciences et de la Technologie -

Mohamed Boudiaf - Oran, Algérie.

h_belbach@yahoo.fr Résumé : Cet article présente une approche d'élagage qui porte sur les r ègles générées à partir d'un arbre de décision. Dans ce contexte, deux approches seront proposées. La première, es t une méthode de simplification de règles par le test

d'indépendance statistique ; et la deuxième, utilise des critères de validation inspirés de l

a technique de découverte des règles d'association. Mots-clés : Arbres de décision, Data mining, Elagage, Règles de décision.

INTRODUCTION

Les arbres de décision constituent une technique préliminaire puissante de data mining, qui consiste à extraire des connaissances potentielles à partir des données dans un but de description ou de prédiction. Les arbres de décision sont l'une des techniques de classification, qui peut être utilisée pour prédire les classes des nouveaux cas. Cependant, un des inconvénients de cette technique, est l'utilisation fréquente des variables moins pertinentes pour l'étape de construction de l'arbre (sur-apprentissage). Ce problème est résolu par l'étape d'élagage qui consiste à supprimer les sous-arbres superflus ou trop liés aux données, dans le but d'améliorer l'aspect prédictif de l'arbre d'une part, et réduire sa complexité d'autre part. Plusieurs méthodes d'élagage existent dans la littérature, telles que : MCCP (Minimal Cost-Complexity Pruning) de

BRIEMAN pour l'algorithme CART [BFOS84], cette

méthode consiste à construire une suite emboîtée de sous-arbres en utilisant une formulation dite complexité de coût minimale. En fonction du coût de mauvaise classification et la taille de l'arbre, on dérive un ordre des arbres de complexité décroissante, commençant de l'arbre complet. Cette séquence est récursivement crée en sélectionnant le dernier arbre

dans la séquence (initialement, l'arbre complet) ; examinant chacun de ses sous-arbres, et sélectionnant

celui avec la moindre métrique de complexité de coût et faisant celui-ci le prochain sous-arbre dans la séquence. Le processus s'arrête quand le sous-arbre final est juste le noeud racine. Une fois cette séquence est produite, on fait le choix d'un arbre optimal en fonction du critère suivant : on calcule l'erreur apparente (estimation de l'erreur réelle) de chaque sous-arbre, celui qui minimise cette mesure, est choisi comme modèle final. REP (Reduced Error Pruning) qui consiste à estimer l'erreur réelle d'un sous-arbre donné sur un ensemble d'élagage ou de test. Plus algorithmiquement, l'élagage se fait comme suit : Tant qu'il existe un arbre que l'on peut remplacer par une feuille sans faire croître l'estimation de l'erreur réelle alors élaguer cet arbre. Cette technique donne un arbre légèrement 'conforme' dans le sens où certains exemples seront peut être mal classifiés.

PEP (Pessimistic Error Pruning), afin de pallier

les inconvénients de la méthode précédente, QUINLAN [Qui87] a proposé une stratégie d'élagage qui fait le recours à un seul ensemble de construction et d'élagage de l'arbre.

L'arbre est élagué en

examinant le taux d'erreur à chaque noeud et assumant que le vrai taux d'erreur est considérablement pire. Si un noeud donné contient

N enregistrements dans

lesquels E parmi eux, sont mal classifiés, alors le taux d'erreur est estimé à E/N. La préoccupation centrale de l'algorithme, est de minimiser cette estimation, en

SETIT2007

- 2 - considérant ce taux d'erreur comme une version très optimiste du taux d'erreur réel. [BL04] [Bro05]

MEP (Minimum Error Pruning) de NIBLETT et

BRATKO [NB87], CVP (Critical Value Pruning) de

MINGERS [Min87], et EBP (Error Based Pruning)

proposée par QUINLAN comme une amélioration de la méthode PEP, pour l'algorithme C4.5 [Qui93]. Toutes ces méthodes diffèrent par leur stratégie d'élagage (ascendante ou descendante), échantillon d'élagage utilisé (même échantillon utilisé pour la construction, ou un autre), et le type d'élagage considéré : pré-élagage (élagage au moment de la construction de l'arbre) ou post-élagage (élagage après la construction de l'arbre). Les résultats d'application de ces méthodes, diffèrent ainsi du point de vue performance de généralisation, et de la taille de l'arbre obtenu. Un des problèmes majeur de ces méthodes, est l'utilisation des critères qui ne sont pas très significatifs pour la décision d'élagage. Quoique le taux d'erreur puisse être un critère important pour l'évaluation du modèle construit, mais il reste toujours biaisé par la nature et la qualité du modèle obtenu.

Dans cet article, nous présentons une approche

d'élagage qui porte sur les règles générées à parti r de l'arbre de décision. Dans ce contexte, deux approches seront proposées. La première, est une méthode de simplification de règles par le test d'indépendance statistique, qui sera proposée pour modifier le mécanisme d'élagage de l'algorithme CHAID. Et la deuxième, utilise des critères de validation inspirés de la technique de découverte des règles d'association.

1. Règles issues des arbres de décision et

élagage

Un arbre de décision, une fois construit, peut être converti en un ensemble de règles équivalent, où chaque chemin, du noeud racine au noeud feuille, sera exprimé par une règle, en enregistrant les tests comme antécédents (prémisses), et la classe du noeud feuille comme conséquent (conclusion). Ces règles doivent être par la suite, simplifiées. La conversion d'un arbre de décision en un ensemble de règles avant l'élagage, a les avantages suivants [Win92]: § Elle permet de distinguer parmi les différents contextes, dans quel cas un noeud de décision est utilisé. Puisque chaque chemin produit une règle distincte, la décision d'élagage concernant un test peut être prise différemment pour chaque chemin. En revanche, si l'arbre celui même est élagué, les deux seuls choix seraient : - enlever le noeud de décision complètement, ou - le maintenir tel qu'il est. § Elle enlève la distinction entre les tests d'attributs qui se produisent près de la racine et les autres, qui se produisent près des feuilles.

§ Elle améliore la lisibilité sans perte

d'information. Notre approche consiste à transformer l'arbre de décision en un ensemble de règles, et d'appliquer ensuite l'élagage ; on parlera donc de " post-élagage indirect ». Nous présentons deux variantes de ce type d'élagage : celui basé sur le test d'indépendance statistique, et celui basé sur les mesures d'association.

2. L'élagage basé sur le test

d'indépendance

Ce type d'élagage est tiré des travaux de

WINSTON [Win92]. L'ensemble de règles conçu

d'une construction maximale d'un arbre de décision, est simplifié en éliminant les antécédents des règles (non nécessaires) par le procédé suivant :

· On construit les tables de contingence, que

nous expliciterons par la suite, pour chaque règle composée de plus d'un antécédent (des règles avec un seul antécédent, ne peuvent pas

être encore simplifiées).

· On élimine les antécédents qui n'ont aucun effet sur la conclusion atteinte par la règle.

· L'indépendance d'une conclusion d'un

antécédent est vérifiée en utilisant un test d'indépendance statistique. Nous expliciterons cette étape dans ce qui suit. Une fois que les différentes règles sont simplifiées par élimination des antécédents redondants, on simplifie l'ensemble entier par élimination de quelques règles non pertinentes.

2.1. Table de contingence

La table de contingence est une représentation

tabulaire d'une règle (voir tableau 1). C 1 C 2 L 1 x 11 x 12 L

1T = x11 + x12 L

2 x 21 x
22 L

2T = x21 + x22 C

T1 = x11 + x21 C

T2 = x12 + x22 T = x11 + x12 + x21 + x22 Tableau 1. Table de contingence d'une règle L

1 et L2 représentent les états booléens d'un

antécédent pour les conclusions C1 et C2, (C1 est la négation de C2). x

11, x12, x21 et x22 représentent les fréquences de

chaque paire antécédent-conséquent. L

1T, L2T, CT1 et CT2 sont les sommes marginales

des lignes et des colonnes, respectivement. T est la somme totale de la table, elle est utilisée avec les sommes marginales pour calculer les valeurs prévues des cellules dans la deuxième étape du test d'indépendance.

2.2. Test d'indépendance

Pour vérifier l'indépendance d'un antécédent d'une règle, de sa conclusion, on procède comme suit.

SETIT2007

- 3 - 1. On forme la table de contingence de dimension : l x c (lignes x colonnes) ;

2. On calcule la valeur de Chi² (observé) par la

formule suivante : åå-= j ijijij i eexChi2

2)( (1)

Où xij (1 £ i £ l et 1 £ j £ c) représente la valeur observée de la cellule dans la table de contingence, et eij représente la valeur prévue de la cellule, donnée par : TCLeTjiT ij.= (2) L iT est la somme des colonnes pour la ième ligne, et C Tj est la somme des lignes pour la jème colonne.

3. On utilise la table statistique1 avec les valeurs :

Chi²a

(théorique) et ddl2, correspondantes à un niveau de signification a choisi par l'utilisateur (qui représente le risque d'erreur, par exemple a =25%), pour déterminer si la conclusion est indépendante de l'antécédent selon le test suivant :

· Si Chi2 > Chi2a

; on rejette l'hypothèse nulle de l'indépendance et on accepte l'hypothèse alternative ; § on garde l'antécédent puisqu'il y a une dépendance avec la conclusion.

· Si Chi2 £Chi

2a ; on accepte l'hypothèse nulle de l'indépendance ;

§ on rejette l'antécédent puisqu'il est

indépendant de la conclusion.

2.3. Proposition d'application du post-élagage

indirect à CHAID

Le principe de l'algorithme CHAID [Kas80],

s'appuie sur le mécanisme de pré-élagage qui consiste à arrêter la croissance de l'arbre en fixant un critère d'arrêt local, basé sur le test d'indépendance statistique, dont l'hypothèse nulle est l'indépendance de la variable de division avec l'attribut cible. L'un des inconvénients de ce principe de pré-élagage, est d'arrêter prématurément la construction de l'arbre. Nous proposons de modifier l'élagage dans CHAID en appliquant un post-élagage basé sur les règles selon le mécanisme d'élagage décrit ci-dessus. Cette solution vise à éviter le risque d'un arrêt prématuré de la construction de l'arbre (avant que le sur-apprentissage se produise) d'un coté, et à exploiter les avantages du post-élagage indirect, d'un autre coté.

1 Table de Chi² (ou Khi²) fournie dans les annexes de

statistique.

2 ddl (degré de liberté) = (l - 1) x (c - 1). 2.4. Limites

Bien que le test de Chi² (utilisé dans ce

mécanisme), donne souvent de bons résultats ; il ne faut pas négliger son aspect statistique, c.-à-d. que la qualité des résultats est influencée par la nature et le volume de données étudiées. Le seul paramètre qui permet à l'utilisateur d'intervenir, est bien sûr le choix du seuil d'erreura. Ce paramètre peut être un avantage du fait qu'il permet d'ajuster l'algorithme et de le contrôler suivant par exemple, le domaine étudié et les résultats souhaités. Mais d'un autre coté, il peut poser un autre problème, du fait qu'un mauvais choix de ce paramètre, peut conduire à des résultats inexplicables. Donc la présence d'un expert humain est un atout exigé.

L'approche d'élagage basé sur le test

d'indépendance, souffre ainsi du caractère instable de ce test, lié étroitement à la taille de l'ensemble d'apprentissage (des expériences faites, nous ont montré qu'avec le même seuil d'erreur fixé, les règles générées (après l'élagage) à partir d'un ensem ble de données, diffèrent de celles générées à partir du mê me ensemble multiplié k fois). Une autre limite est l'aspect symétrique du test du fait que les mesures d'indépendance d'une affectation et sa négation, sont égales. Afin de remédier à ces restrictions, une deuxième contribution, tout à fait nouvelle, consiste à appliquer une autre méthode suivant le même principe de post-élagage des règles générées, mais en utilisant des tests différents, basés sur les mesures d'association.

3. L'élagage basé sur les mesures

d'association Dans cette section, nous considérons un autre type d'élagage basé sur les critères d'évaluation utilisé s par la technique de découverte de règles d'association. Avant d'entrer dans les détails, il sera fondamental de donner quelques éclaircissements relatifs à cette technique afin de familiariser le lecteur et l'aider à cerner le contexte de cette vue.

3.1. Que sont les règles d'association ?

La principale application de

cette technique est " l'analyse du panier de la ménagère » qui consiste comme l'indique son nom, en la recherche d'associations entre les objets. La méthode peut être appliquée à tout secteur d'activité pour lequel, il est intéressant de rechercher des groupements potentiels de produits ou de services. Elle utilise un certain nombre d'algorithmes, tel que l'algorithme APRIORI d'AGRAWAL [AS94]. Une règle d'association est de la forme " Si A Alors B », où A et B sont des conjonctions d'attributs.

A est la condition ou la

prémisse de la règle, et B est la conclusion. On peut distinguer deux étapes élémentaires pour cette technique : la première consiste en la génération des itemsets fréquents, et la deuxième consiste en la génération de règles d'association entre ces itemsets, qui seront par la suite, évaluées et validées. Tout cela étant fait avec une concentration particulière sur un

SETIT2007

- 4 - certain nombre de mesures. Notre préoccupation principale, est d'appliquer ces mesures sur les règles de décision pour évaluer leur pertinence vis-à-vis de l'ensemble de données sur lesquelles, elles vont être appliquées. Les règles d'association comme les règles de décision, visent à prédire la classe moyennant un ensemble de conditions, appelées aussi itemsets.

Cependant la principale différence, est que la

quotesdbs_dbs23.pdfusesText_29

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision

[PDF] arbre de décision définition

[PDF] dénombrement cours 1ere s

[PDF] apollon et daphné résumé

[PDF] apollon et daphné leur histoire

[PDF] expression etre nature

[PDF] tp mise en évidence d'une réaction d'oxydoréduction

[PDF] apollon et daphné peinture

[PDF] apollon et daphné le bernin

[PDF] tp chimie réaction d oxydoréduction

[PDF] vertebres avec quilles