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

Abstract

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

ÖZ: Budama, en düşük hata oranı ile karar ağacını tanımlama sırasında meydana gelen aşırı-uydurma sorunu ile mücadele etmek amacıyla uygulanır. Sonradan-budama yaklaşımları karar ağaçlarında en etkili budama yöntemlerinden olup her bir ana düğümün ve yapraklarının yanlış sınıflandırma hata oranına dayanarak verimsiz dallarını çıkartarak ağacı aşağıdan yukarıya doğru inceler. Bu tezde, Bayes Minimum Risk (PBMR) ve Sıfır-Bir Kayıp Fonksiyonu (ZOLFP) temel alınarak geliştirilen iki sonradan-budama yaklaşımı önerilmiştir. PBMR yaklaşımında, bir alt ağacın ana düğümü, bu alt ağacın ana düğümünün tahmini risk oranının yapraklarının toplam risk oranlarından daha az olması durumunda bir yaprak düğümüne dönüştürülür. ZOLFP yaklaşımı, Sıfır-bir kayıp fonksiyonuna bağlı bir yöntem kullanarak ağacın beklenen kaybını en aza indirir. Önerilen iki yöntem performans doğruluğu, ağaç karmaşıklığı, hassasiyet/geri-çağırmaskoru, Gerçek Pozitif (TP) ve Yanlış Pozitif (FP) oranları, öznitelik seçimi veKarar Vericinin Etkinliği (ROC) altındaki alan dikkate alınarak değerlendirilmiştir. Deneysel sonuçlar, önerilen her iki yöntemin, Azaltılmış Hata Budama (REP) ve Minimum Hata Budama (MEP) yöntemlerinin karmaşıklığına yakınbir karmaşıklık ile budamayı gerçekleştirdiğini vebu yöntemler ile karşılaştırıldığında daha iyi sınıflandırma doğruluğu ürettiğini göstermektedir. Deneyler, önerilen yöntemlerin, hassasiyet skoru, geri-çağırma skoru, TP oranı, FP oranı ve ROC altındaki alan açısından da tatmin edici bir performans sergilediğini göstermektedir. Anahtar Kelimeler: karar ağacı, budama, sonradan-budama, Bayes minimum risk, Sıfır-bir kayıp