Les arbres de décision sont-ils presque toujours des arbres binaires?

Presque chaque exemple d'arbre de décision que j'ai rencontré se trouve être un arbre binaire. Est-ce à peu près universel? La plupart des algorithmes standard (C4.5, CART, etc.) prennent-ils uniquement en charge les arbres binaires? D'après ce que je comprends, CHAID n'est pas limité aux arbres binaires, mais cela semble être une exception.

Une séparation bidirectionnelle suivie d'une autre séparation bidirectionnelle sur l'un des enfants n'est pas la même chose qu'une séparation triple unique. Cela peut être un point académique, mais j'essaie de m'assurer de comprendre les cas d'utilisation les plus courants.

C'est principalement un problème technique: si vous ne vous limitez pas aux choix binaires, il y a tout simplement trop de possibilités pour la prochaine division dans l'arborescence. Vous avez donc certainement raison sur tous les points soulevés dans votre question.

Sachez que la plupart des algorithmes de type arbre fonctionnent par étapes et ne sont même pas garantis comme tels pour donner le meilleur résultat possible. Ce n'est qu'une mise en garde supplémentaire.

Pour la plupart des cas pratiques, mais pas pendant la construction / l'élagage de l'arbre, les deux types de divisions sont cependant équivalents, étant donné qu'elles apparaissent immédiatement l'une après l'autre.

Un partage bidirectionnel suivi d'un autre partage bidirectionnel sur l'un des enfants n'est pas la même chose qu'un partage triple unique

Je ne sais pas ce que tu veux dire ici. Tout fractionnement multidirectionnel peut être représenté comme une série de séparations bidirectionnelles. Pour une séparation à trois, vous pouvez diviser en A, B et C en divisant d'abord en A et B contre C, puis en séparant A de B.

Un algorithme donné peut ne pas choisir cette séquence particulière (surtout si, comme la plupart des algorithmes, il est gourmand), mais il le pourrait certainement. Et si des procédures de randomisation ou d'étape sont effectuées comme dans des forêts aléatoires ou des arbres boostés, les chances de trouver la bonne séquence de divisions augmentent. Comme d'autres l'ont souligné, les divisions multi-voies sont coûteuses en termes de calcul, donc étant donné ces alternatives, la plupart des chercheurs semblent avoir choisi des divisions binaires.

J'espère que cela t'aides

En ce qui concerne les utilisations de l'arbre de décision et du fractionnement (binaire ou autre), je ne connais que CHAID qui a des divisions non binaires mais il y en a probablement d'autres. Pour moi, l'utilisation principale d'un fractionnement non binaire est dans les exercices d'exploration de données où je cherche à regrouper de manière optimale une variable nominale à plusieurs niveaux. Une série de divisions binaires n'est pas aussi utile qu'un regroupement effectué par CHAID.

Veuillez lire ceci

Pour des raisons pratiques (explosion combinatoire), la plupart des bibliothèques implémentent des arbres de décision avec des divisions binaires. La bonne chose est qu'ils sont NP-complets (Hyafil, Laurent et Ronald L. Rivest. "Construire des arbres de décision binaires optimaux est NP-complet." Information Processing Letters 5.1 (1976): 15-17.)