¿Los árboles de decisión son casi siempre árboles binarios?

Casi todos los ejemplos de árboles de decisión que he encontrado resultan ser un árbol binario. ¿Es esto bastante universal? ¿La mayoría de los algoritmos estándar (C4.5, CART, etc.) solo admiten árboles binarios? Por lo que deduzco , CHAID no se limita a los árboles binarios, sino que parece ser una excepción.

Una división bidireccional seguida de otra división bidireccional en uno de los niños no es lo mismo que una división tridireccional única. Este podría ser un punto académico, pero estoy tratando de asegurarme de entender los casos de uso más comunes.

Esto es principalmente un problema técnico: si no se restringe a las opciones binarias, simplemente hay demasiadas posibilidades para la próxima división en el árbol. Así que definitivamente tiene razón en todos los puntos formulados en su pregunta.

Tenga en cuenta que la mayoría de los algoritmos de tipo árbol funcionan paso a paso y, como tal, no están garantizados para dar el mejor resultado posible. Esta es solo una advertencia adicional.

Para la mayoría de los propósitos prácticos, aunque no durante la construcción / poda del árbol, los dos tipos de divisiones son equivalentes, dado que aparecen inmediatamente uno después del otro.

Una división bidireccional seguida de otra división bidireccional en uno de los niños no es lo mismo que una división tridireccional única

No estoy seguro de lo que quieres decir aquí. Cualquier división multidireccional se puede representar como una serie de divisiones bidireccionales. Para una división de tres vías, puede dividirse en A, B y C dividiendo primero en A&B versus C y luego dividiendo A de B.

Un algoritmo dado podría no elegir esa secuencia particular (especialmente si, como la mayoría de los algoritmos, es codicioso), pero ciertamente podría. Y si se realiza alguna aleatorización o procedimientos por etapas, como en bosques aleatorios o árboles impulsados, aumentan las posibilidades de encontrar la secuencia correcta de divisiones. Como otros han señalado, las divisiones de múltiples vías son computacionalmente costosas, por lo que dadas estas alternativas, la mayoría de los investigadores parecen haber elegido divisiones binarias.

Espero que esto ayude

Con respecto a los usos del árbol de decisión y la división (binario versus lo contrario), solo sé de CHAID que tiene divisiones no binarias, pero probablemente haya otros. Para mí, el uso principal de una división no binaria es en ejercicios de minería de datos, donde estoy viendo cómo agrupar de manera óptima una variable nominal con muchos niveles. Una serie de divisiones binarias no es tan útil como una agrupación realizada por CHAID.

Por favor lea esto

Por razones prácticas (explosión combinatoria), la mayoría de las bibliotecas implementan árboles de decisión con divisiones binarias. Lo bueno es que tienen NP completo (Hyafil, Laurent y Ronald L. Rivest. "Construir árboles de decisión binarios óptimos es NP-completo". Information Processing Letters 5.1 (1976): 15-17.)