Regularized impurity reduction: accurate decision trees with complexity guarantees

Area of Science:

• Machine Learning
• Data Mining
• Artificial Intelligence

Background:

• Decision trees are popular classification models known for accuracy and interpretability.
• Model interpretability deteriorates as tree size increases.
• Traditional algorithms lack theoretical guarantees for producing small trees.

Purpose of the Study:

• To provide theoretical guarantees for producing smaller decision trees.
• To enhance impurity-reduction functions for better complexity control.
• To develop a tree-induction algorithm with approximation guarantees on complexity.

Main Methods:

• Proposed a novel tree-induction algorithm with a logarithmic approximation guarantee on tree complexity.
• Utilized a general family of impurity functions, including entropy and Gini-index.
• Defined a greedy criterion balancing tree balance, cost-efficiency, and discriminative power.

Main Results:

• The enhanced algorithm provides a tight logarithmic approximation factor for tree complexity.
• Achieved an excellent balance between predictive accuracy and tree complexity.
• Demonstrated effectiveness across binary and multi-class classification with non-uniform costs.

Conclusions:

• The proposed enhancement successfully equips impurity functions with complexity guarantees.
• The algorithm offers a practical solution for generating interpretable and accurate decision trees.
• This work contributes to the theoretical understanding and practical application of decision tree induction.