Algoritmo de minimización para árbores de decisión aplicado a explicabilidade

Abstract

[Resumo]: Neste proxecto lévase a cabo o desenvolvemento dunha ferramenta de minimización de Árbores de Decision. Como resultado desta minimización, obténse un conxunto de regras que equivalen á árbore orixinal en termos de clasificación pero as cales son máis xerais, evitando o uso de variables innecesarias. As regras obtidas pódense usar para a obtención de explicacións máis compactas e que evitan o uso de información non relevante. A principal motivación do traballo é a aplicación da ferramenta a ámbitos nos que a decisión dun sistema poida impactar de forma decisiva na vida das persoas coma pode ser o ámbito médico ou o xudicial. Para a implementación, desenvolvese unha xeneralización do algoritmo de Quine-McCluskey para que poida manexar os rangos de valores non booleanos que son naturais nas condicións dunha Árbore de Decisión. Evalúase a validez e a eficiencia desta primera versión, primeiro contrastando a saída contra unha implementación inicial nunha linguaxe declarativa, e despois mediante a xeración e execución probas sintéticas. Detállase tamén tanto o desenvolvemento dun xerador de casos de exemplo coma o proceso de medición dos tempos de execución e a xeración de gráficas, onde se comparan os resultados dos distintos exemplos. Para mellorar os tempos iniciais, deséñase tamén unha heurística, cuxo rendemento é de novo explorado neste traballo. A ferramenta desenvolta atopase dispoñible publicamente e, no momento da redacción deste traballo, resulta única no seu próposito.

[Abstract]: In this project, the development of a Decision Tree minimization tool is carried out. As a result of this minimization, a set of rules is obtained that are equivalent to the original tree in terms of classification but are more general, avoiding the use of unnecessary variables. The obtained rules can be used to obtain more concise explanations that avoid the use of irrelevant information. The main motivation for this work is the application of the tool in areas where a system’s decision can have a significant impact on people’s lives, such as in the medical or judicial field. For the implementation, a generalization of the Quine-McCluskey algorithm is developed to handle non-boolean value ranges that are natural in Decision Tree conditions. The validity and efficiency of this initial version are evaluated by first comparing the output against an initial implementation in a declarative language and then by generating and executing synthetic tests. The development of the example case generator and the process of measuring execution times and generating graphs to compare results from different examples are detailed. To improve initial times, a heuristic is also designed, and its performance is explored in this work. The tool developed is publicly available and, at the time of writing this work, it is unique in its purpose.