CART Pruning Algorithm
CART เป็น decision tree algorithm ที่มีชื่อเสียง สร้างโดย Leo Breiman, Jerome Friedman, Richard Olshen, และ Charles Stone ในปี 1984 CART ย่อมาจาก Classification and Regression Trees CART algorithm สร้าง binary trees และแบ่งต่อไปเรื่อยๆ ตราบใดที่ยังหา new splits ที่เพิ่ม purity ได้
มี simpler subtrees หลายตัว แต่ละตัวแทน trade-off ระหว่าง model complexity และ training set misclassification rate ที่แตกต่างกัน CART algorithm ระบุชุด subtrees เหล่านี้เป็น candidate models Candidate subtrees นี้ถูกนำไปใช้กับ validation set และ tree ที่มี validation set misclassification rate ต่ำสุด ถูกเลือกเป็น final model
กระบวนการ Pruning แบบซ้ำ (Repeated Pruning)
CART ระบุ candidate subtrees ผ่านกระบวนการ pruning แบบซ้ำ วัตถุประสงค์คือ prune ก่อน branches ที่ให้ predictive power น้อยที่สุดต่อ leaf ระบุ branches ที่ไม่คุ้มค่านี้ CART อาศัยแนวคิดที่เรียกว่า adjusted error rate
Adjusted error rate เป็น measure ที่ปรับ misclassification cost ของแต่ละ node บน training set โดยเพิ่ม complexity penalty ขึ้นอยู่กับจำนวน leaves ใน tree Adjusted error rate ระบุ weak branches (ที่ misclassification rate ไม่พอที่จะชดเชย penalty) และทำเครื่องหมายเพื่อ prune
การเลือก Best Subtree
งานต่อไปคือเลือกจาก pool of candidate subtrees ตัวที่ทำงานดีที่สุดบนข้อมูลใหม่ Candidate subtrees ทุกตัวถูกนำไปประเมินกับ validation set Tree ที่ทำภารกิจนี้ด้วย overall error rate ต่ำสุด ถูกกำหนดเป็น winner Winning subtree ถูก prune พอที่จะกำจัดผลกระทบของ overtraining แต่ไม่มากเกินไปที่จะสูญเสียข้อมูลมีค่า
เนื่องจาก pruning algorithm นี้อิง misclassification rate โดยไม่คำนึงถึง probability ของแต่ละ classification มันแทนที่ subtree ที่ leaves ทั้งหมดทำนาย classification เดียวกัน ด้วย common parent ที่ทำนาย classification เดียวกันนั้น
ถ้าวัตถุประสงค์คือเลือกสัดส่วนเล็กของข้อมูล (top 1% หรือ 10%) pruning algorithm นี้อาจทำลายประสิทธิภาพของ tree เพราะบาง leaves ที่ถูกลบมีสัดส่วนสูงมากของ target class มี tools หลายตัว เช่น SAS Enterprise Miner ให้ผู้ใช้ prune trees optimally สำหรับกรณีเหล่านี้
Winning subtree ถูกเลือกจาก overall error rate บน validation set คาดหวังว่า selected subtree จะยังคงเป็น best-performing บน dataset อื่นๆ แต่อย่างไร error rate ที่ทำให้มันถูกเลือก อาจ overstate ความแข็งแกร่งของมันเล็กน้อย
