Post-Pruning Decision Tree Algorithms Based on Bayes Minimum Risk and Loss Minimization to Combat Over-Fitting Problem

Pruning is applied in order to combat over-fitting problem where the tree is pruned with the goal of identifying decision tree with the lowest error rate on previously unobserved instances. Post-pruning approach is one of the most powerful and effective pruning methods in decision trees. This method traverses the tree in bottom-up fashion removing the unproductive branches based on the misclassification error rate of each parent node and its leaves. In this thesis, two post-pruning approaches named as Pruning with Bayes Minimum Risk (PBMR) and Pruning based on Zero-One Loss Function (ZOLFP) are proposed. In PBMR approach, the tree is pruned based on the estimating risk-rate and a parent node of a subtree is converted to a leaf node if the estimated risk-rate of the parent node for that subtree is less than the sum of the risk-rates of its leaves. ZOLFP approach minimizes the expected loss of the tree by employing Zero-One loss function method. A subtree is pruned when expected loss of the node is less than or equal to the sum of the loss of its leaves. The two proposed methods are evaluated in terms of performance accuracy, tree complexity, precision/recall scores, True Positive (TP) and False Positive (FP) rates and area under ROC considering attribute selection. The experimental results show that the two proposed methods produce better classification accuracy compared to un-pruned decision tree, Reduced-Error Pruning (REP), and Minimum-Error Pruning (MEP) with complexity not much different than the complexities of REP and MEP. The experiments also demonstrate that the proposed methods show satisfactory performance in terms of precision/recall score, TP rate, FP rate and area under ROC. Keywords: decision tree, pruning, post-pruning, Bayes minimum risk, Zero-One loss