Un article de Wikipedia.y-project.com.
Article en cours d'écriture
[] Introdution
Dans le domaine de l'aide à la décision (informatique décisionnelle et datawarehouse) et du datamining, certains algorithmes, appelés arbres de décision, sont utilisés pour répartir une population d'individus (de clients par exemple) en groupes homogènes, selon un ensemble de variables discriminantes (l'âge, la catégorie socio-professionnelle, ...) en fonction d'un objectif fixé et connu (chiffres d'affaires, réponse à un mailing, ...).
Ainsi par exemple, le service marketing d'une banque peut utiliser des arbres de décision pour s'intéresser aux caractéristiques des personnes qui seraient susceptibles de répondre favorablement à une nouvelle campagne de recrutement de nouveaux clients (on suppose içi que des campagnes de recrutement ont déjà été effectuées par le passé car les arbres de décision s'appuient nécessairement sur un historique de données.). L'arbre de décision va déterminer automatiquement les caractéristiques des personnes les plus intéressées ainsi que celles des personnes les moins intéressées par ladite campagne. Il ne nous restera plus qu'à contacter les personnes qui ont les memes caractéristiques que les personnes que l'arbre aura identifiées comme intéressées par ce type de campagne. Attention toutefois, les personnes potentiellement intéressées par la campagne ne le sont pas toutes dans la même mesure. Une probabilité "d'intéressement" leur est systématiquement associée, et donc un risque de se tromper, un risque d'erreur.
[] Les feuilles de l'arbre
Un arbre de décision va ainsi créer des groupes d'individus homogènes quant à leur comportement par rapport à l'objectif que l'on s'est fixé. Ces groupes sont appelés des feuilles de l'arbre. Reprenons l'exemple d'une nouvelle campagne marketing de recrutement. Un arbre pourrait produire la feuille suivante, parmi l'ensemble des feuilles produites : 75% des hommes de plus de 50 ans habitant à Paris ont par le passé répondu favorablement à ce type de campagne. Ainsi, si je décide de contacter pour une nouvelle campagne de recrutement tous les hommes de plus de 50 ans habitant à Paris présents dans ma base de données de prospects, je suppose a priori que 75% d'entre eux y répondront favorablement... Je peux ainsi calculer a priori la rentabilité de ma campagne marketing : je sais combien va me couter ma campagne, j'optimise d'ailleurs ses couts puisque je peux choisir de ne contacter que les personnes ayant une probabilité d'être intéressé supérieure à un seuil que je me fixe moi-même (en pratique ce seuil édpend notamment des budgets marketing sui me sont alloués), je sais a priori combien elle devrait me rapporter.
[] Intérêt
L'intérêt des algorithmes d'arbre de décision est qu'ils sont intuitifs : ils représentent graphiquement un ensemble de règles et sont facilement interprétables. Ils reposent très souvent sur un nombre limité d'hypothèses mathématiques ou statistiques, qu'ils sont très simples d'utilisation et qu'il n'est pas nécessaire de restreindre a priori le nombre de variables à étudier : l'algorithme détecte lui-même les variables les plus discriminantes pour l'objectif fixé, élimine les variables "inutiles" et estime un risque d'erreur de se tromper dans l'appréhension de cet objectif étant donné les informations à sa disposition.
[] De nombreux algorithmes différents
De nombreux algorithmes existent. Citons par exemple les suivants :
C4.5 et C5, CART, ID3, QUEST, MARS, CHAID, ECHAID, parmi d'autres... Ils diffèrent par les critères mathématiques utilisés pour trouver parmi toutes les variables disponibles celles qui sont les plus intéressantes ou discriminantes (critères à base de mesure d'entropie, de tests du chi2, de mesure d'impureté...), mais aussi par les types d'objectifs qu'ils sont capables de traiter : variable(s) quantitative(s) (ex:un chiffre d'affaire, une dépense, un revenu...), variable(s) qualitative(s) (répondre favorablement ou non à une capagne marketing, acheter ou non un produit...). Ils se distinguent également, pour les objectifs de type qualitatifs, par le nombre de modalités qu'ils acceptent de traiter (réponse de type oui/non, ou réponse de type produit A, produit B, produit C...). Ils se distinguent par le nombre de feuilles produites à chaque étape de la croissance de l'arbre : certains algorithmes génèrent 2 feuilles, on parle alors d'arbres binaires (CART, C5 par exemple), d'autres sont capables de générer plus de 2 feuilles (CHAID par exemple). Ils se distinguent enfin par leur capacité à gérer des bases de données incomplètes, c'est-à-dire contenant de nombreuses valeurs manquantes. Ce dernier point est essentiel, car, en entreprise, il est rare de travailler avec des bases de données parfaites !
Ces algorithmes sont parfois combinés à des techniques plus classiques de modélisation d'un objectif fixé : analyse discriminante, régressions logisitiques, régression linéaire, réseaux de neurones (perceptrons multicouches, radial basis function network...)... Ils sont également très souvent combinés entre eux pour tirer profit de leurs avantages respectifs. On parle alors parfois de forêts d'arbres... Des procédures d'aggrégation des performances des différents modèles utilisés, ou des procédures de vote doivent alors être mises en place pour obtenir une performance maximale, tout en controlant et en minimisant le niveau de complexité de l'ensemble des modèles utilisés.
[] Le problème du surajustement des modèles
Ces techniques sont très (trop pour certains...) facilement utilisables. Quelques précautions de base doivent cependant être prises. Un arbre de décision est souvent calculé sur un ensemble d'information, de données, représentant une réalité plus vaste appelé échantillon d'apprentissage. La performance de l'arbre est évaluée sur les données mêmes qui ont servi à sa construction : plus le modèle est complexe, plus l'on court le risque de voir ce modèle incapable d'être extrapolé à de nouvelles données, c'est-à-dire de rendre compte de la réalité que nous essayons justement d'appréhender. A la limite, et c'est particulièrement vrai des arbres de décision, un modèle est capable de répliquer exactement n'importe quel échantillon de données, sans pour autant appréhender une quelconque réalité... Reprenons l'exemple de notre nouvelle campagne de recrutement marketing. Si l'on décide de faire pousser notre arbre le plus loin possible, nous pouvons obtenir un arbre composé d'autant de feuilles que d'individus dans la base de données. Notre arbre ne commet donc aucune erreur tant que nous n'essayons pas de l'appliquer sur de nouvelles données où sa performance se rapproche alors de 0...!
Lorsque l'on construit un arbre de décision, on risque donc ce que l'on appelle un surajustement du modèle : le modèle semble performant (son erreur moyenne est très faible) mais il ne l'est en réalité pas du tout ! Passer d'un modèle complexe à un modèle moins complexe tout en conservant un niveau de performance comparable s'appelle une opération d'élagage de l'arbre. Plusieurs types d'algorithmes d'élagages sont possibles. Ils sont généralement différents d'un type d'arbre à un autre.
Pour éviter un surajustement de nos arbres (et c'est également vrai de tous les modèles mathématiques que l'on pourrait construire), il convient d'appliquer un principe de parcimonie et de réaliser des arbitrages performance/complexité des modèles utilisés. A performance comparable, on préfèrera toujours le modèle le plus simple, si l'on souhaite pouvoir utiliser ce modèle sur de nouvelles données totalement inconnues.
Comment réaliser cet arbitrage performance/complexité des modèles utilisés ? En évaluant la performance d'un ou de plusieurs modèles sur les données qui ont servi à sa construction (le ou les échantillons d'apprentissage), mais également sur ce que l'on appelle un (ou plusieurs) échantillon(s) de test, c'est-à-dire des données à notre disposition mais que nous décidons volontairement de ne pas utiliser dans la construction de nos modèles. Tout se passe comme si ces données étaient de nouvelles données, la réalité. La stabilité de la performance de nos modèles sur ces deux types d'échantillon nous permettra de juger de son surajustement et donc de sa capacité à être utilisé avec un risque d'erreur maitrisé dans des conditions réelles où les données ne sont pas connues à l'avance...
Image:Surajustement d'un modèle 2.jpg
Voir également algorithme génétique.
[] Références
- élément A
- élément B
- élément C
[] Liens externes
DernierMirror
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/arbre de décision
