Question:
Créer un arbre de décision unique à partir d'une forêt aléatoire
Lembik
2015-09-12 11:48:04 UTC
view on stackexchange narkive permalink

J'utilise scikit learn pour créer un classificateur Random Forest. J'ai entendu dire qu'il pourrait être possible de construire un arbre de décision unique à partir d'une forêt aléatoire. La suggestion est que même si l'arbre de décision n'est peut-être pas un aussi bon classificateur que la forêt aléatoire, il peut être meilleur que l'arbre de décision que vous obtiendriez en utilisant la méthode standard.

Cependant, je n'ai pas pu pour trouver cette méthode en ligne. Existe-t-il?


Ma question ne concerne pas l'extraction d'un des arbres de décision d'une forêt aléatoire. Il s'agit d'une méthode pour construire un nouvel arbre de décision à partir de toute la forêt aléatoire, peut-être en combinant les arbres de la forêt aléatoire d'une manière ou d'une autre.

Cela a encore moins de sens.Pourquoi construiriez-vous un seul arbre à partir d'un RF, alors que vous avez déjà un RF?Utilisez simplement le RF.À propos, RF combine déjà les arbres de décision (en faisant la moyenne de leurs prédictions).Mais peut-être que vous n'êtes toujours pas clair, alors avez-vous une référence pour «ce que vous avez entendu»?Cela vous aiderait à obtenir des réponses qui correspondent à ce que vous voulez vraiment.
Peut-être que vous voulez une méthode pour extraire les * règles de décision * d'un RF?Je ne suis pas sûr que cet ensemble de règles puisse être représenté comme un arbre de décision.
Le terme clé dont vous avez besoin est _Combined Multiple Models_ (CMM).Domingos 1997 décrit ceci pour mettre en sac les règles C4.5: http://homes.cs.washington.edu/~pedrod/papers/mlc97.pdf Ce serait amusant d'avoir un exemple de faire cela avec Random Forests dans `sklearn`.
Antoine, pour être clair, la plupart des algorithmes de construction d'arbres de décision sont des algorithmes gourmands qui ne trouvent pas l'arbre de décision optimal.L'OP suggère qu'après avoir entraîné un RF, on pourrait obtenir des informations sur l'assemblage d'un arbre plus puissant que celui que vous obtiendriez à partir des algorithmes gourmands typiques.Comme il le mentionne, ses motivations sont l'interprétabilité et la rapidité.
Mon avis: Un ajustement aléatoire de la forêt peut être vu comme un grand ensemble de règles qui peuvent être réduites à un ensemble plus petit de règles plus simples acceptant une augmentation donnée du biais comme dans cet article [10].http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4243592/ Mais .. si un ensemble minimal de règles reste à être un grand nombre, cette réduction est encore incompréhensible.Souvent, si vous pouvez réduire la forêt à un petit arbre avec peu de biais, vous devriez pouvoir utiliser un modèle plus simple en premier lieu.
Je ne suis pas d'accord pour dire que les arbres de décision sont simples à interpréter - du moins s'ils sont d'une taille réaliste.Laisser quatre ou cinq niveaux inférieurs est extrêmement difficile à expliquer parce que chaque décision est conditionnelle à toutes les décisions de niveau supérieur.+1 au commentaire de Soren.
Six réponses:
Antoine
2015-09-14 14:46:09 UTC
view on stackexchange narkive permalink

Les arbres en RF et les arbres simples sont construits en utilisant le même algorithme (généralement CART). La seule différence mineure est qu’un seul arbre essaie tous les prédicteurs à chaque division, alors que les arbres en RF n’essayent qu’un sous-ensemble aléatoire de prédicteurs à chaque division (cela crée des arbres indépendants ). En outre, chaque arborescence d'un RF est construite sur un échantillon bootstrap des données d'entraînement d'origine, plutôt que sur l'ensemble d'apprentissage complet. Cela fait de chaque arbre de la forêt un expert sur certains domaines de l'espace de données, et mauvais ailleurs.

Donc, pour ces raisons, cela n'a aucun sens d'extraire un seul arbre d'une forêt aléatoire afin de utilisez-le comme classificateur. En fonction de ses domaines d'expertise, il pourrait vous donner de meilleurs résultats qu'un arbre traditionnel construit avec CART sur l'ensemble de données complet, ou bien pire. Ce qui permet à un RF d'être bien meilleur qu'un seul arbre, c'est qu'il fait pousser de nombreux arbres décorrélés et fait la moyenne de leur sortie. Ce n'est que lorsque le comité d'experts comprend suffisamment de membres (généralement entre 200 et 2000) que la variance est réduite. Mais individuellement, chaque arbre d'un RF serait plus faible qu'un seul arbre construit via CART traditionnel.

Vous pouvez certainement extraire un arbre d'un RF pour avoir une idée de ce qui se passe dans la forêt (voir le lien que j'ai fourni dans mon commentaire ci-dessus). N'utilisez pas cet arbre unique comme classificateur.

Désolé, je pense que ma question n'était pas claire à 100%.Je ne demande pas d'extraire l'un des arbres de décision du RF.Mais plutôt sur la construction d'un arbre de décision unique à partir du RF par une méthode.J'imagine que cela impliquerait de combiner les arbres de décision dans RF d'une manière ou d'une autre, mais comment cela est fait est le point de ma question.
La motivation principale est l'interprétabilité.Un arbre de décision vous indique quelque chose de simple et facilement compréhensible sur vos données.En outre, les arbres de décision de taille raisonnable sont extrêmement rapides à exécuter sur des données massives.
Une fois que le RF est formé, son utilisation pour faire des prédictions est également très rapide.Et si votre arbre de décision est construit en "combinant les arbres de décision dans RF d'une manière ou d'une autre", cela nécessiterait de toute façon de créer le RF en premier lieu, non?
Il est vrai que faire des prédictions avec un RF est rapide mais pas tout à fait rapide si vous comptez les microsecondes.Dans ma situation, je créerais le RF sur certaines données d'entraînement, puis je l'exécuterais sur des données futures qui peuvent être beaucoup plus volumineuses.Mais comme je l'ai dit, l'interprétabilité est une propriété très intéressante des arbres de décision pour ma situation.
Vous pouvez extraire [l'importance de la variable] (https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#varimp) d'une forêt aléatoire qui vous montre à quel point vos variables sont "importantes" pour faire des prédictions.C'est la première étape pour essayer de tirer une certaine interprétation d'un RF.
@Lembik Donc, en substance, vous voulez bénéficier de la précision d'un RF sans avoir à le sacrifier pour l'interprétabilité.Je pense que c'est tout simplement impossible.Vous ne pouvez pas extraire beaucoup plus d'informations de modèles d'apprentissage d'ensemble tels que RF, Boosting, etc. que ce que les mesures d'importance variable peuvent fournir.Les ensembles sont par nature des boîtes noires (ou plutôt des boîtes grises).
rien n'est impossible quand on ne sait pas ce qu'on peut faire!J'ai entendu dire que certaines entreprises réussissaient à rendre la RF plus interprétable.Ils sont maintenant «en quelque sorte», lorsqu'ils prennent la décision, sont capables d'expliquer quelle variable est la raison de cette décision, et pourquoi!Ce n'est pas tout à fait clair comme CART, mais nous rendons RF moins noir!c'est le bon signe.
Abraham D Flaxman
2015-09-17 01:55:05 UTC
view on stackexchange narkive permalink

Ce que vous recherchez peut-être, c'est l'approche Combining Multiple Models (CMM) développée par Domingos dans les années 90. Les détails de son utilisation avec un ensemble ensaché de règles C4.5 sont décrits dans son article ICML

Domingos, Pedro. «Acquisition de connaissances à partir d'exemples via plusieurs modèles». Dans Actes de la quatorzième conférence internationale sur l'apprentissage automatique . 1997.

Le pseudo-code du tableau 1 n'est pas spécifique au C4.5 ensaché, cependant: enter image description here

Pour appliquer ceci à Random Forests, le problème clé semble être de savoir comment générer l'exemple généré aléatoirement $ \ overrightarrow {x} $. Voici un cahier montrant une façon de le faire avec sklearn .

Cela m'a amené à me demander quel travail de suivi a été effectué sur CMM, et si quelqu'un a trouvé une meilleure façon de générer $ \ overrightarrow {x} $. J'ai créé une nouvelle question à ce sujet ici.

JohnRos
2015-09-20 15:11:34 UTC
view on stackexchange narkive permalink

À l'exception de scénarios très improbables, une prédiction aléatoire de la forêt ne peut pas être représentée par un seul arbre. En effet, ils apprennent des prédicteurs dans différentes classes d'hypothèses: une forêt aléatoire apprend des prédicteurs sur l'espace de combinaisons linéaires d'arbres, qui comprend des prédicteurs qui ne sont pas des arbres. En d'autres termes, les forêts apprennent des prédicteurs dans la durée de l'espace des arbres.

Cela dit, il y a l'espoir qu'il existe un arbre qui est une bonne approximation du prédicteur de la forêt. Une manière rapide et sale de trouver cet arbre, est d'adapter un arbre aux prédictions de la forêt. La qualité de ses prévisions dépendra de la "distance" entre le meilleur prédicteur de forêt et sa meilleure approximation d'arbre.

Tchotchke
2015-09-14 19:30:09 UTC
view on stackexchange narkive permalink

Il semble que vous cherchiez à répondre à deux préoccupations - 1. l'interprétabilité et 2. l'efficacité de la prédiction. Comme déjà mentionné dans les commentaires ci-dessus, vous pouvez extraire l ' importance variable en Python, de sorte que les adresses point 1.

Pour aborder le point 2, si vous êtes préoccupé par l'efficacité jusqu'à microsecondes, vous souhaiterez peut-être explorer d'autres algorithmes, tels que la régression logistique, et comparer les performances hors échantillon à celles générées par Random Forest; si les performances sont presque équivalentes mais que la régression logistique est beaucoup plus rapide, vous pouvez alors prendre la décision d’opter pour la régression logistique.

Si vous êtes prêt à utiliser Random Forest, la réponse courte est que techniquement, vous pourrait construire un arbre aléatoire en définissant ntree = 1 et cela pourrait produire une prédiction décente, mais une collection d'arbres sera bien meilleure qu'un seul arbre. Il n'est donc pas logique de créer un seul arbre à partir du sous-ensemble d'arbres, à moins que vous ne souhaitiez échanger des performances hors échantillon contre de l'efficacité.

De plus, vous pouvez également accélérer les prédictions en un facteur de 10 ou plus en utilisant uniquement un sous-ensemble d'arbres dans la prédiction finale. Si vous entraînez 1500 arbres, vous pouvez sélectionner le sous-ensemble qui contribue le mieux à la prédiction finale. Je pense à quelque chose du genre Sélection d'ensemble à partir d'un modèle de bibliothèques, où chaque arbre de votre forêt serait le modèle de votre ensemble.

DaL
2015-09-20 13:39:05 UTC
view on stackexchange narkive permalink

L'un des classiques de la combinaison de ces fonctions est "Algorithmes basés sur des graphes pour la manipulation de fonctions booléennes". Il contient plus de 3000 citations. Vous pouvez traiter les arbres comme un cas particulier de fonctions booléennes.

Veuillez noter que si votre modèle de forêt aléatoire est grand, le modèle d'arbre unique sera probablement aussi grand.

Laurent Deborde
2019-03-24 20:39:56 UTC
view on stackexchange narkive permalink

Comme le dit JohnRos ci-dessus, vous pouvez en effet rechercher une approximation globale d'arbre unique de Random Forest en essayant d'adapter un seul arbre à la prédiction de la forêt aléatoire sur un (très) grand nombre de points.Cela peut fonctionner pour un autre modèle de boîte noire.C'est ce qu'on appelle l'approche "oracle" de l'approximation globale d'un arbre unique par [1] (parce que la boîte noire est utilisée comme un oracle pour s'adapter à l'arbre unique). Si j'ose, j'ai chargé quelques exemples et plus d'explications sur Github ici: https://github.com/ljmdeb/GSTA

[1] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti et Dino Pedreschi.2018. Une enquête sur les méthodes pour expliquer les modèles de boîtes noires.ACM Comput.Surv.51, 5, article 93 (août 2018), 42 pages.(en particulier le tableau à la page 93:26)



Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Continuer la lecture sur narkive:
Loading...