Resumen: Encontrar un árbol de decisión óptimo que minimice el error de clasificación se sabe que es NP-HARD. Si bien los algoritmos exactos basados en MILP, CP, SAT o programación dinámica garantizan la optimización, a menudo sufren de un comportamiento deficiente en cualquier momento, lo que significa que luchan por encontrar árboles de decisión de alta calidad rápidamente cuando la búsqueda se detiene antes de su finalización, debido a la exploración de espacios de búsqueda desequilibrados. Para abordar esto, se han propuesto varias extensiones de métodos exactos, como LDS-DL8.5, Top-K-DL8.5 y Blossom, pero no se han comparado sistemáticamente, lo que dificulta la evaluación de su efectividad relativa. En este artículo, proponemos CA-DL8.5, un algoritmo de búsqueda de haz genérico, completo y en cualquier momento que extienda el marco DL8.5 y unifica algunas estrategias existentes en cualquier momento. En particular, CA-DL8.5 generaliza los enfoques anteriores LDS-DL8.5 y Top-K-DL8.5, al permitir la integración de diversos mecanismos de heurística y relajación a través de un diseño modular. El algoritmo reutiliza la eficiente poda de ramificación y unión de DL8.5 y el almacenamiento en caché basado en TRIE, combinado con una búsqueda de haz basada en el reinicio que relaja gradualmente los criterios de poda para mejorar la calidad de la solución con el tiempo. Nuestras contribuciones son dobles: (1) Introducimos este nuevo marco genérico para el aprendizaje de árbol de decisión exacta y en cualquier momento, lo que permite la incorporación de diversas heurísticas y estrategias de búsqueda; (2) Llevamos a cabo una comparación empírica rigurosa de varias instancias de CA-DL8.5, según la pureza, la ganancia, la discrepancia y las heurísticas de Top-K, utilizando una métrica de evaluación en cualquier momento llamada Integral de la brecha primaria. Los resultados experimentales en los puntos de referencia de clasificación estándar muestran que CA-DL8.5 utilizando SUD (discrepancia limitada) proporciona de manera consistente el mejor rendimiento en cualquier momento, superando las otras variantes CA-DL8.5 y el algoritmo Blossom mientras se mantiene la integridad y las garantías de optimización.
Publicado Originalme en export.arxiv.org El 10 de agosto de 2025.
Ver Fuente Original
