Les arbres de décision…
Avertissement : Vous l’aviez
compris, ceci n’est qu’un roman, une fiction, une « pure construction
intellectuelle », du pur jus de neurone garanti 100 % bio, sortie tout droit de
l’imaginaire de son auteur.
Toute ressemblance avec des personnages, des lieux, des actions, des situations ayant existé ou existant par ailleurs dans la voie lactée (et autres galaxies), y compris sur la planète Terre, y est donc purement, totalement et parfaitement fortuite !
Le principe, c’est que dans ces structures d’arbre,
les « feuilles » représentent les valeurs de la variable-cible et les
embranchements correspondent à des combinaisons de variables d’entrée qui
mènent à ces valeurs. En analyse décisionnelle, un « arbre de décision »
peut être utilisé pour représenter de manière explicite les décisions réalisées
et les processus qui les amènent.
En mode apprentissage et en « fouille de données », un arbre de décision décrit les données mais pas les décisions elles-mêmes, l’arbre serait alors utilisé comme point de départ au processus de décision.
C’est en fait une technique d’apprentissage « supervisé » : on utilise un ensemble de données pour lesquelles on connaît la valeur de la variable-cible afin de construire l’arbre, des données dites « étiquetées », puis on extrapole les résultats à l’ensemble des données de test.
C’est ainsi que depuis quelques années, les arbres de décision font partie des algorithmes les plus populaires en apprentissage automatique utilisés par les IA.
L’apprentissage par arbre de décision est ainsi devenu une méthode classique en apprentissage automatique. Et son but avoué est de créer un modèle qui prédit la valeur d’une variable-cible depuis la valeur de plusieurs variables d’entrée.
Lorsqu’une des variables d’entrée est
sélectionnée à chaque nœud intérieur, ou interne, nœud qui n’est pas terminal,
de l’arbre selon une méthode qui dépend de l’algorithme. Chaque arête vers un « nœud-fils »
correspond alors à un ensemble de valeurs d’une variable d’entrée, de manière à
ce que l’ensemble des arêtes vers les « nœuds-fils » couvrent toutes
les valeurs possibles de la variable d’entrée : simple.
Chaque feuille, ou nœud terminal de l’arbre représente soit une valeur de la variable-cible, soit une distribution de probabilité des diverses valeurs possibles de la variable-cible.
La combinaison des valeurs des variables d’entrée est représentée par le chemin de la racine jusqu’à la feuille.
L’arbre est en général construit en séparant l’ensemble des données en sous-ensembles en fonction de la valeur d’une caractéristique d’entrée. Ce processus est répété sur chaque sous-ensemble obtenu de manière récursive, il s’agit donc d’un partitionnement itératif.
La récursion est achevée à un nœud soit lorsque
tous les sous-ensembles ont la même valeur de la caractéristique-cible, ou
lorsque la séparation n’améliore plus la prédiction.
Ce processus est appelé induction descendante d’arbres de décision (top-down induction of decision trees ou TDIDT). C’est un algorithme glouton puisqu’on recherche à chaque nœud de l’arbre le partage optimal, dans le but d’obtenir le meilleur partage possible sur l’ensemble de l’arbre de décision.
C’est la stratégie la plus commune pour apprendre les arbres de décision depuis les données.
En fouille de données, les arbres de décision
peuvent aider à la description, la catégorisation ou la généralisation d’un jeu
de données fixé.
L’ensemble d’apprentissage est généralement fourni sous la forme d’enregistrements du type (x, Y) = (x1, x2, x3… xk, Y), etc.
Mais il existe deux principaux types d’arbre de décision en fouille de données : les arbres de classification qui permettent de prédire à quelle classe la variable-cible appartient, dans ce cas la prédiction est une étiquette de classe, et les arbres de régression qui permettent de prédire une quantité réelle, par exemple, le prix d’une maison ou la durée de séjour d’un patient dans un hôpital. Dans ce dernier cas la prédiction est une valeur numérique.
Le terme d’analyse d’arbre de classification et de régression est un terme générique se référant aux procédures ainsi décrites. Les arbres utilisés dans le cas de la régression et dans le cas de la classification présentent des similarités mais aussi des différences, en particulier en ce qui concerne la procédure utilisée pour déterminer les séparations des branches.
Dans la réalité, « l’apprentissage par
arbre de décision » consiste à construire un arbre depuis un ensemble d’apprentissage
constitué de « n-uplets » étiquetés[1].
Un arbre de décision peut être décrit comme un diagramme de flux de données où
chaque nœud interne décrit un test sur une variable d’apprentissage, chaque
branche représente un résultat du test, et chaque feuille contient la valeur de
la variable cible. Autrement dit une étiquette de classe pour les arbres de
classification, une valeur numérique pour les arbres de régression.
Et usuellement, les algorithmes pour construire les arbres de décision sont construits en divisant l’arbre du sommet vers les feuilles en choisissant à chaque étape une variable d’entrée qui réalise le meilleur partage de l’ensemble d’objets.
Pour choisir la variable de séparation sur un nœud, les algorithmes testent les différentes variables d’entrée possibles et sélectionnent celle qui maximise un critère donné.
Dans le cas des arbres de classification, il s’agit seulement d’un problème de classification automatique. Le critère d’évaluation des partitions caractérise alors l’homogénéité ou le gain en homogénéité des sous-ensembles obtenus par division de l’ensemble.
Ces métriques sont appliquées à chaque sous-ensemble candidat et les résultats sont combinés, par exemple, moyennés, pour produire une mesure de la qualité de la séparation.
Chaque ensemble de valeurs de la variable de
segmentation permet de produire un nœud-fils. Les algorithmes d’apprentissage
peuvent donc différer sur le nombre de nœud-fils produits : certains produisent
systématiquement des arbres binaires, plus facile à traiter par informatique et
cherchent donc la partition binaire qui optimise le critère de segmentation.
D’autres cherchent en revanche à effectuer les regroupements les plus pertinents en s’appuyant sur des critères statistiques.
Selon la technique employée, on obtient des arbres plus ou moins larges.
Pour que la méthode soit efficace, il faut éviter de fractionner exagérément les données afin de ne pas produire des groupes d’effectifs trop faibles qui ne correspondant à aucune réalité statistique.
Et dans le cas de variables de segmentation continues, le critère de segmentation choisi doit être adéquat : le travail d’un cerveau humain…
En général, on trie les données selon la variable à traiter, puis on teste les différents points de coupure possibles en évaluant le critère pour chaque cas, le point de coupure optimal sera celui qui maximise le critère de segmentation.
Mais il n’est pas toujours souhaitable de
construire un arbre dont les feuilles correspondent à des sous-ensembles
parfaitement homogènes du point de vue de la variable-cible. En effet, l’apprentissage
est réalisé sur un échantillon que l’on espère représentatif d’une population.
L’enjeu de toute technique d’apprentissage est d’arriver à saisir l’information
utile sur la structure statistique de la population, en excluant les
caractéristiques spécifiques au jeu de données étudié.
Or, plus le modèle est complexe, plus l’arbre est grand, plus il a de branches, plus il a de feuilles, plus 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 l’on cherche à appréhender !
En particulier, comme ce que devra affronter « BBR 3.0 », dans le cas extrême où l’arbre a autant de feuilles qu’il y a d’individus dans la population et donc d’enregistrements dans le jeu de données, l’arbre ne commet alors aucune erreur sur cet échantillon puisqu’il en épouse absolument toutes les caractéristiques, mais il n’est plus généralisable à un autre échantillon.
Ce problème, nommé « surapprentissage » ou « surajustement », est un sujet classique de l’apprentissage automatique et de la fouille de données.
D’habitude, on cherche plutôt à construire un
arbre qui soit le plus petit possible en assurant la meilleure performance
possible et on le développe ensuite. Suivant le principe de parcimonie, plus un
arbre sera petit, plus il sera stable dans ses prévisions futures.
Mais il faut parfois réaliser un arbitrage entre performance et complexité dans les modèles utilisés.
À performance comparable, on préférera toujours le modèle le plus simple, si l’on souhaite pouvoir utiliser ce modèle sur de nouveaux échantillons.
Et c’est encore à l’intelligence naturelle de faire ces arbitrages…
Car pour réaliser l’arbitrage
performance/complexité des modèles utilisés, on évalue 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 un ou plusieurs échantillons
de validation : des données étiquetées à disposition mais que l’on décide
volontairement de ne pas utiliser dans la construction des modèles.
Ces données sont traitées comme les données de test, la stabilité de la performance des modèles sur ces deux types d’échantillons permettra de juger de son surajustement et donc de sa capacité à être utilisé avec un risque d’erreur maîtrisé dans des conditions réelles où les données ne sont pas connues à l’avance.
Si l’erreur décroît constamment sur l’échantillon d’apprentissage, à partir d’un certain niveau de complexité, c’est que le modèle s’éloigne de la réalité, réalité que l’on cherche à estimer sur l’échantillon de validation, appelé échantillon de test.
Il faut savoir que dans le cas des arbres de
décisions, plusieurs types de solutions algorithmiques ont été envisagées pour
tenter d’éviter autant que possible le surapprentissage des modèles : les
techniques de pré- ou de post-élagage des arbres.
Certaines théories statistiques cherchent à trouver l’optimum entre l’erreur commise sur l’échantillon d’apprentissage et celle commise sur l’échantillon de test.
Par exemple, la théorie de Vapnik-Chervonenkis Structured Risk Minimization (ou SRM), utilise une variable appelée dimension « VC », pour déterminer l’optimum d’un modèle. Elle est utilisable par conséquent pour générer des modèles qui assurent le meilleur compromis entre qualité et robustesse du modèle.
Ces solutions algorithmiques sont complémentaires des analyses de performances comparées et de stabilité effectuées sur les échantillons d’apprentissage et de validation.
Aussi la première stratégie utilisable pour
éviter un surapprentissage des arbres de décision consiste à proposer des
critères d’arrêt lors de la phase d’expansion. C’est le principe du pré-élagage :
lorsque le groupe est d’effectif trop faible, ou lorsque l’homogénéité d’un
sous-ensemble a atteint un niveau suffisant, on considère qu’il n’est plus
nécessaire de séparer l’échantillon.
Un autre critère souvent rencontré dans ce cadre est l’utilisation d’un test statistique pour évaluer si la segmentation introduit un apport d’informations significatif pour la prédiction de la variable-cible.
La seconde stratégie consiste à construire l’arbre en deux temps : on produit d’abord l’arbre dont les feuilles sont le plus homogènes possibles dans une phase d’expansion, en utilisant une première fraction de l’échantillon de données (l’échantillon d’apprentissage à ne pas confondre avec la totalité de l’échantillon), puis on réduit l’arbre, en s’appuyant sur une autre fraction des données de manière à optimiser les performances de l’arbre : c’est la phase de post-élagage.
Selon les cas, cette seconde portion des données est désignée par le terme d’échantillon de validation ou échantillon de test, introduisant une confusion avec l’échantillon utilisé pour mesurer les performances des modèles.
Le terme d’échantillon d’élagage permet alors de le désigner sans ambiguïté.
Mais les données à disposition sont souvent incomplètes, dans le sens où l’on ne dispose que d’une partie des variables d’entrée pour un enregistrement.
Plusieurs possibilités sont envisageables dans
ce cas : tout d’abord les ignorer !
Cela n’est possible que si l'échantillon de données est suffisamment grand pour supprimer des individus du jeu de données, et que si l’on est sûr que lorsque l’arbre de décision sera utilisé en pratique, toutes les données seront toujours disponibles pour tous les individus.
Ou les remplacer par une valeur calculée jugée adéquate : cette technique est parfois utilisée en statistique mais au-delà des problèmes purement mathématiques, elle est contestable du point de vue méthodologique.
Enfin, utiliser des variables substituts : cela consiste, pour un individu qui aurait une donnée manquante pour une variable sélectionnée par l’arbre comme étant discriminante, à utiliser la variable qui parmi l’ensemble des variables disponibles dans la base de données produit localement les feuilles les plus similaires aux feuilles produites par la variable dont la donnée est manquante. On appelle alors cette variable « un substitut ».
Si un individu a une valeur manquante pour la variable initiale, mais aussi pour la variable substitut, on peut utiliser une deuxième variable substitut et ainsi de suite, jusqu'à la limite d’un critère de qualité du substitut.
Cette technique a l’avantage d’exploiter l’ensemble
de l’information disponible pour chaque individu mais peut entrainer des biais…
Dans le cas des arbres de classification, si les feuilles sont homogènes, il n’y a pas d’ambiguïté. Si ce n’est pas le cas, une règle simple consiste à décider de la classe de la feuille en fonction de la classe majoritaire, celle qui est la plus représentée.
Pour mémoire (n’en déplaise à « Poux-tine ») : « LE PRÉSENT
BILLET A ENCORE ÉTÉ RÉDIGÉ PAR UNE PERSONNE « NON RUSSE » ET MIS EN LIGNE PAR
UN MÉDIA DE MASSE « NON RUSSE », REMPLISSANT DONC LES FONCTIONS D’UN AGENT «
NON RUSSE » !
Post-scriptum : Alexeï Navalny est mort en détention pour ses opinions politiques. Les Russes se condamnent à perpétuité à en supporter toute la honte !
Постскриптум: Алексей Навальный умер в заключении за свои политические взгляды. Россияне обрекают себя на всю жизнь нести весь позор!
Parrainez Renommez la rue de l'ambassade de Russie à Paris en rue Alexeï Navalny (change.org)
[1] En mathématiques, un uplet (désigné aussi par « liste », « famille finie », ou « suite finie ») est une collection ordonnée finie d'objets. Plus précisément, si n est un entier naturel, alors un n-uplet, ou n-uple, ou n-liste est une collection ordonnée de n objets, appelés « composantes » ou « éléments » ou « termes » du n-uplet. En programmation informatique, on trouve une notion équivalente dans certains langages, tels que Python, Rust, OCaml, Scala, Swift ou MDX. Dans les langages fonctionnels, les tuples sont réalisés comme types produits ; dans les langages impératifs, on trouve des tuples nommés, où les composantes sont repérées par un nom, sous la forme de struct (C) ou record (Pascal).
Toute ressemblance avec des personnages, des lieux, des actions, des situations ayant existé ou existant par ailleurs dans la voie lactée (et autres galaxies), y compris sur la planète Terre, y est donc purement, totalement et parfaitement fortuite !
En mode apprentissage et en « fouille de données », un arbre de décision décrit les données mais pas les décisions elles-mêmes, l’arbre serait alors utilisé comme point de départ au processus de décision.
C’est en fait une technique d’apprentissage « supervisé » : on utilise un ensemble de données pour lesquelles on connaît la valeur de la variable-cible afin de construire l’arbre, des données dites « étiquetées », puis on extrapole les résultats à l’ensemble des données de test.
C’est ainsi que depuis quelques années, les arbres de décision font partie des algorithmes les plus populaires en apprentissage automatique utilisés par les IA.
L’apprentissage par arbre de décision est ainsi devenu une méthode classique en apprentissage automatique. Et son but avoué est de créer un modèle qui prédit la valeur d’une variable-cible depuis la valeur de plusieurs variables d’entrée.
Chaque feuille, ou nœud terminal de l’arbre représente soit une valeur de la variable-cible, soit une distribution de probabilité des diverses valeurs possibles de la variable-cible.
La combinaison des valeurs des variables d’entrée est représentée par le chemin de la racine jusqu’à la feuille.
L’arbre est en général construit en séparant l’ensemble des données en sous-ensembles en fonction de la valeur d’une caractéristique d’entrée. Ce processus est répété sur chaque sous-ensemble obtenu de manière récursive, il s’agit donc d’un partitionnement itératif.
Ce processus est appelé induction descendante d’arbres de décision (top-down induction of decision trees ou TDIDT). C’est un algorithme glouton puisqu’on recherche à chaque nœud de l’arbre le partage optimal, dans le but d’obtenir le meilleur partage possible sur l’ensemble de l’arbre de décision.
C’est la stratégie la plus commune pour apprendre les arbres de décision depuis les données.
L’ensemble d’apprentissage est généralement fourni sous la forme d’enregistrements du type (x, Y) = (x1, x2, x3… xk, Y), etc.
Mais il existe deux principaux types d’arbre de décision en fouille de données : les arbres de classification qui permettent de prédire à quelle classe la variable-cible appartient, dans ce cas la prédiction est une étiquette de classe, et les arbres de régression qui permettent de prédire une quantité réelle, par exemple, le prix d’une maison ou la durée de séjour d’un patient dans un hôpital. Dans ce dernier cas la prédiction est une valeur numérique.
Le terme d’analyse d’arbre de classification et de régression est un terme générique se référant aux procédures ainsi décrites. Les arbres utilisés dans le cas de la régression et dans le cas de la classification présentent des similarités mais aussi des différences, en particulier en ce qui concerne la procédure utilisée pour déterminer les séparations des branches.
Et usuellement, les algorithmes pour construire les arbres de décision sont construits en divisant l’arbre du sommet vers les feuilles en choisissant à chaque étape une variable d’entrée qui réalise le meilleur partage de l’ensemble d’objets.
Pour choisir la variable de séparation sur un nœud, les algorithmes testent les différentes variables d’entrée possibles et sélectionnent celle qui maximise un critère donné.
Dans le cas des arbres de classification, il s’agit seulement d’un problème de classification automatique. Le critère d’évaluation des partitions caractérise alors l’homogénéité ou le gain en homogénéité des sous-ensembles obtenus par division de l’ensemble.
Ces métriques sont appliquées à chaque sous-ensemble candidat et les résultats sont combinés, par exemple, moyennés, pour produire une mesure de la qualité de la séparation.
D’autres cherchent en revanche à effectuer les regroupements les plus pertinents en s’appuyant sur des critères statistiques.
Selon la technique employée, on obtient des arbres plus ou moins larges.
Pour que la méthode soit efficace, il faut éviter de fractionner exagérément les données afin de ne pas produire des groupes d’effectifs trop faibles qui ne correspondant à aucune réalité statistique.
Et dans le cas de variables de segmentation continues, le critère de segmentation choisi doit être adéquat : le travail d’un cerveau humain…
En général, on trie les données selon la variable à traiter, puis on teste les différents points de coupure possibles en évaluant le critère pour chaque cas, le point de coupure optimal sera celui qui maximise le critère de segmentation.
Or, plus le modèle est complexe, plus l’arbre est grand, plus il a de branches, plus il a de feuilles, plus 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 l’on cherche à appréhender !
En particulier, comme ce que devra affronter « BBR 3.0 », dans le cas extrême où l’arbre a autant de feuilles qu’il y a d’individus dans la population et donc d’enregistrements dans le jeu de données, l’arbre ne commet alors aucune erreur sur cet échantillon puisqu’il en épouse absolument toutes les caractéristiques, mais il n’est plus généralisable à un autre échantillon.
Ce problème, nommé « surapprentissage » ou « surajustement », est un sujet classique de l’apprentissage automatique et de la fouille de données.
Mais il faut parfois réaliser un arbitrage entre performance et complexité dans les modèles utilisés.
À performance comparable, on préférera toujours le modèle le plus simple, si l’on souhaite pouvoir utiliser ce modèle sur de nouveaux échantillons.
Et c’est encore à l’intelligence naturelle de faire ces arbitrages…
Ces données sont traitées comme les données de test, la stabilité de la performance des modèles sur ces deux types d’échantillons permettra de juger de son surajustement et donc de sa capacité à être utilisé avec un risque d’erreur maîtrisé dans des conditions réelles où les données ne sont pas connues à l’avance.
Si l’erreur décroît constamment sur l’échantillon d’apprentissage, à partir d’un certain niveau de complexité, c’est que le modèle s’éloigne de la réalité, réalité que l’on cherche à estimer sur l’échantillon de validation, appelé échantillon de test.
Certaines théories statistiques cherchent à trouver l’optimum entre l’erreur commise sur l’échantillon d’apprentissage et celle commise sur l’échantillon de test.
Par exemple, la théorie de Vapnik-Chervonenkis Structured Risk Minimization (ou SRM), utilise une variable appelée dimension « VC », pour déterminer l’optimum d’un modèle. Elle est utilisable par conséquent pour générer des modèles qui assurent le meilleur compromis entre qualité et robustesse du modèle.
Ces solutions algorithmiques sont complémentaires des analyses de performances comparées et de stabilité effectuées sur les échantillons d’apprentissage et de validation.
Un autre critère souvent rencontré dans ce cadre est l’utilisation d’un test statistique pour évaluer si la segmentation introduit un apport d’informations significatif pour la prédiction de la variable-cible.
La seconde stratégie consiste à construire l’arbre en deux temps : on produit d’abord l’arbre dont les feuilles sont le plus homogènes possibles dans une phase d’expansion, en utilisant une première fraction de l’échantillon de données (l’échantillon d’apprentissage à ne pas confondre avec la totalité de l’échantillon), puis on réduit l’arbre, en s’appuyant sur une autre fraction des données de manière à optimiser les performances de l’arbre : c’est la phase de post-élagage.
Selon les cas, cette seconde portion des données est désignée par le terme d’échantillon de validation ou échantillon de test, introduisant une confusion avec l’échantillon utilisé pour mesurer les performances des modèles.
Le terme d’échantillon d’élagage permet alors de le désigner sans ambiguïté.
Mais les données à disposition sont souvent incomplètes, dans le sens où l’on ne dispose que d’une partie des variables d’entrée pour un enregistrement.
Cela n’est possible que si l'échantillon de données est suffisamment grand pour supprimer des individus du jeu de données, et que si l’on est sûr que lorsque l’arbre de décision sera utilisé en pratique, toutes les données seront toujours disponibles pour tous les individus.
Ou les remplacer par une valeur calculée jugée adéquate : cette technique est parfois utilisée en statistique mais au-delà des problèmes purement mathématiques, elle est contestable du point de vue méthodologique.
Enfin, utiliser des variables substituts : cela consiste, pour un individu qui aurait une donnée manquante pour une variable sélectionnée par l’arbre comme étant discriminante, à utiliser la variable qui parmi l’ensemble des variables disponibles dans la base de données produit localement les feuilles les plus similaires aux feuilles produites par la variable dont la donnée est manquante. On appelle alors cette variable « un substitut ».
Si un individu a une valeur manquante pour la variable initiale, mais aussi pour la variable substitut, on peut utiliser une deuxième variable substitut et ainsi de suite, jusqu'à la limite d’un critère de qualité du substitut.
Dans le cas des arbres de classification, si les feuilles sont homogènes, il n’y a pas d’ambiguïté. Si ce n’est pas le cas, une règle simple consiste à décider de la classe de la feuille en fonction de la classe majoritaire, celle qui est la plus représentée.
Post-scriptum : Alexeï Navalny est mort en détention pour ses opinions politiques. Les Russes se condamnent à perpétuité à en supporter toute la honte !
Постскриптум: Алексей Навальный умер в заключении за свои политические взгляды. Россияне обрекают себя на всю жизнь нести весь позор!
Parrainez Renommez la rue de l'ambassade de Russie à Paris en rue Alexeï Navalny (change.org)
[1] En mathématiques, un uplet (désigné aussi par « liste », « famille finie », ou « suite finie ») est une collection ordonnée finie d'objets. Plus précisément, si n est un entier naturel, alors un n-uplet, ou n-uple, ou n-liste est une collection ordonnée de n objets, appelés « composantes » ou « éléments » ou « termes » du n-uplet. En programmation informatique, on trouve une notion équivalente dans certains langages, tels que Python, Rust, OCaml, Scala, Swift ou MDX. Dans les langages fonctionnels, les tuples sont réalisés comme types produits ; dans les langages impératifs, on trouve des tuples nommés, où les composantes sont repérées par un nom, sous la forme de struct (C) ou record (Pascal).
Aucun commentaire:
Enregistrer un commentaire