Dans Une introduction à l'apprentissage statistique avec applications en R , les auteurs écrivent que l'ajustement d'un arbre de décision est très rapide, mais cela n'a aucun sens pour moi. L'algorithme doit passer en revue toutes les fonctionnalités et les partitionner de toutes les manières possibles afin de trouver la division optimale. Pour les entités numériques avec observations, cela peut entraîner partitions pour chaque entité.
Est-ce que je comprends mal comment fonctionne la division binaire? Ou y a-t-il une raison pour que cet algorithme ne prenne pas longtemps?
Réponses:
Les algorithmes d'arbres de décision ne calculent pas tous les arbres possibles lorsqu'ils correspondent à un arbre. S'ils le faisaient, ils seraient en train de résoudre un NP-difficileproblème. Les algorithmes d’ajustement des arbres décisionnels prennent généralement des décisions gloutonnes dans le processus d’ajustement: à chaque étape, ils optimisent le sous-problème afin de trouver une division optimale avec les données du nœud donné et de continuer à avancer dans le processus d’ajustement. En outre, à mesure que vous avancez dans l'arbre de décision, vous avez un ensemble de données plus petit qui a été redirigé vers le nœud donné, de sorte que vous optimiserez la règle de fractionnement sur un sous-ensemble de données plus petit. Tous ces choix sont des analyses linéaires des données dans le nœud donné. Ce n'est pas compliqué à faire, mais cela peut coûter un peu cher en calcul si vous avez un grand nombre d'observations ou un grand nombre de covariables sur lesquelles vous séparer. Cependant, une grande partie du travail peut être scindée et transmise à différentes machines. Il existe donc des moyens de développer votre architecture informatique afin de l'intensifier.
la source
Il existe certaines différences entre les algorithmes CART et C4.5 pour la création d'arbres de décision. Par exemple, CART utilise Gini Impurity pour sélectionner des fonctionnalités, tandis que C.4.5 utilise Shannon Entropy. Je ne pense pas que les différences soient pertinentes pour la réponse, donc je ne ferai pas de distinction entre celles-ci.
Ce qui rend les arbres de décision plus rapidement que vous ne le pensez est:
and
donnerait un meilleur arbre. Cela signifie que vous devez être très prudent / intelligent lors de l'ingénierie des fonctionnalités. Par exemple, si vous essayez de prédire la quantité de boissons que les gens boivent, vous voudrez peut-être présenter des éléments tels que ceux d'ingénieurnew_feature = hour > 22 & hour < 4 & (friday_night | saturday_night)
. Les arbres de décision peuvent passer à côté de telles règles ou leur donner moins d'importance qu'ils ne le devraient.X <= 1
X <= 1.5
X <= 2
X <= 1
X <= 1.5
xgboost
si rapides. L'amélioration du gradient est séquentielle et ne peut pas être mise en parallèle, mais les arbres eux-mêmes le peuvent.la source
Juste pour enrichir les réponses,
Les arbres de décision parallèles aux axes hiérarchiques sont rapides (CART, C4.5), mais il existe d'autres alternatives telles que les arbres de décision non hiérarchiques ou celles qui effectuent des partitions obliques qui ne le sont pas, bien qu'elles puissent être plus précises. Vérifiez les références suivantes si vous êtes intéressé (elles ne constituent pas une sélection exhaustive).
Non hiérarchique:
Grubinger, T., Zeileis, A. et Pfeiffer, K.-., 2014. Evtree: apprentissage évolutif d'arbres de classification et de régression globalement optimaux dans RJStat.Logiciel 61 (1), 1-29.
Fractures obliques:
Murthy, SK, Kasif, S. et Salzberg, S., 1994. Système d'induction d'arbres de décision obliques. J. Artif. Intell. Res. 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63 . Cantú-Paz, E. et Kamath, C., 2003. Induire des arbres de décision obliques avec des algorithmes d'évolution. IEEE Trans. Evol. Comput. 7 (1), 54-68. http://dx.doi.org/10.1109/TEVC.2002.806857 . Heath, D., Kasif, S. et Salzberg, S., 1993. Induction d'arbres de décision obliques. J. Artif. Intell. Res. 2 (2), 1002-1007.
Bonne chance!
la source