Towards the improvement of decision tree learning: a perspective on search and evaluation

Abstract

Data mining and machine learning (ML) are increasingly at the core of many aspects of modern life. With growing concerns about the impact of relying on predictions we cannot understand, there is widespread agreement regarding the need for reliable interpretable models. One of the areas where this is particularly important is clinical decision-making. Specifically, explainable models have the potential to facilitate the elaboration of clinical guidelines and related decision-support tools. The presented research focuses on the improvement of decision tree (DT) learning, one of the most popular interpretable models, motivated by the challenges posed by clinical data. One of the limitations of interpretable DT algorithms is that they involve decisions based on strict thresholds, which can impair performance in the presence noisy measurements. In this regard, we proposed a probabilistic method that takes into account a model of the noise in the distinct learning phases. When considering this model during training, the method showed moderate improvements in accuracy compared to the standard approach, but significant reductions in number of leaves. Standard DT algorithms follow a locally-optimal approach which, despite providing good performances at a low computational cost, does not guarantee optimal DTs. The second direction of research therefore concerned the development of a non-greedy DT learning approach that employs Monte Carlo tree search (MCTS) to heuristically explore the space of DTs. Experiments revealed that the algorithm improved the trade-off between performance and model complexity compared to locally-optimal learning. Moreover, dataset size and feature interactions played a role in the behavior of the method. Despite being used for their explainability, DTs are chiefly evaluated based on prediction performance. The need for comparing the structure of DT models arises frequently in practice, and is usually dealt with by manually assessing a small number of models. We attempted to fill this gap by proposing an similarity measure to compare the structure of DTs. An evaluation of the proposed distance on a hierarchical forest of DTs indicates that it was able to capture structure similarity. Overall, the reported algorithms take a step in the direction of improving the performance of DT algorithms, in particular in what concerns model complexity and a more useful evaluation of such models. The analyses help improve the understanding of several data properties on DT learning, and illustrate the potential role of DT learning as an asset for clinical research and decision-making.

La minería de datos y el aprendizaje de patrones se encuentran cada vez más debajo de muchos aspectos de la vida cotidiana moderna. La preocupación creciente sobre el impacto de basarse en predicciones difíciles de explicar o comprender hace que haya un consenso amplio respecto a la necesidad de modelos interpretables y robustos. Una de las áreas donde esto es particularmente importante es en la toma de decisiones clínicas. Específicamente, los modelos interpretables tienen el potencial para facilitar la elaboración de guías clínicas y herramientas relacionadas de soporte a la decisión. La investigación que se presenta en este manuscrito se centra en la mejora del aprendizaje de los árboles de decisión (“Decision Trees”, DT, en inglés), uno de los modelos interpretables más populares, motivada por los retos que ofrecen los datos clínicos. Una de las limitaciones actuales de los algoritmos de DT interpretables es que implican decisiones basadas estrictamente en umbrales que pueden deteriorar la precisión en presencia de medidas con ruido. Al respecto, hemos propuesto un método probabilístico que considera un modelo de ruido en las distintas fases de aprendizaje. Al considerar este modelo en la fase de entrenamiento, el método demuestra mejoras moderadas en la precisión del algoritmo DT, comparado con el método clásico, aunque produce reducciones significativas en el número de hojas (e.g. niveles) del árbol de decisión. Los algoritmos clásicos de DT siguen un enfoque óptimo a nivel local que, a pesar de proporcionar buenos resultados a un coste computacional bajo, no garantiza árboles de decisión óptimos. Así, la segunda dirección de la investigación en este doctorado se dirigió al desarrollo de una metodología de aprendizaje de árboles de decisión no voraz (“non-greedy” en inglés) que usa una búsqueda de árboles de Monte Carlo (“Monte Carlo Tree Search”, MCDS en inglés) para explorar de manera heurística el espacio de DTs posibles. Los experimentos realizados revelaron que el algoritmo usando MCTS mejoró el balance entre la precisión en los resultados y la complejidad del modelo, comparado con el aprendizaje óptimo a nivel local. Asimismo, el tamaño de los datos y las interacciones entre las características tuvieron un rol importante en el comportamiento del método. A pesar de emplearse por su explicabilidad, los árboles de decisión son principalmente evaluados con criterios basados en la predicción. La necesidad de poder comparar la estructura de diferentes modelos de DT es frecuente en la práctica y usualmente se trata evaluando manualmente un pequeño número de modelos. Durante esta tesis intentamos cubrir esta necesidad proponiendo una medida de similitud para comparar la estructura de los árboles de decisión. Una evaluación basada en la medida propuesta aplicada a un bosque jerárquico de DTs indicó que era capaz de capturar la similitud estructural. De manera global, los algoritmos descritos dan un paso hacia la dirección de mejorar la precisión de los algoritmos basados en árboles de decisión, especialmente en lo concerniente a la reducción de la complejidad de los modelos y a una evaluación más práctica de ellos. Los análisis efectuados mejoran la comprensión de varias de las propiedades de los datos en el aprendizaje de DT, demostrando su rol potencial como recurso en la investigación y toma de decisiones clínicas.