A novel decision tree classification based on post-pruning with Bayes minimum risk.

Area of Science:

• Machine Learning
• Data Mining
• Artificial Intelligence

Background:

• Overfitting is a common problem in decision tree algorithms, leading to poor generalization on unseen data.
• Existing pruning methods like reduced-error pruning and minimum-error pruning aim to mitigate overfitting but may have limitations.
• Accurate risk estimation is crucial for effective decision tree pruning.

Purpose of the Study:

• To introduce a novel post-pruning method using Bayes minimum risk for estimating risk-rate in decision trees.
• To evaluate the proposed method against established pruning techniques based on multiple performance metrics.
• To identify decision trees with the lowest error rate on unobserved instances while favoring smaller, accurate trees.

Main Methods:

• A bottom-up pruning approach is employed, converting parent nodes to leaves if their estimated risk-rate is lower than their subtree's leaf risk-rates.
• The proposed post-pruning method considers diverse evaluation standards: attribute selection, accuracy, tree complexity, pruning time, precision/recall, TP/FN rates, and Area Under the ROC curve (AUC).
• Bayes minimum risk is utilized for estimating the risk-rate to guide the pruning process.

Main Results:

• The proposed Bayes minimum risk pruning method achieves superior classification accuracy compared to existing approaches.
• The complexity of the proposed method is comparable to reduced-error pruning and minimum-error pruning.
• Satisfactory performance was observed in terms of precision, recall, true positive (TP) rate, false positive (FP) rate, and AUC.

Conclusions:

• Bayes minimum risk pruning offers an effective strategy for combating overfitting in decision trees.
• The method provides a robust balance between classification accuracy and model complexity.
• The proposed approach demonstrates strong performance across various evaluation metrics, making it a valuable tool for decision tree optimization.