प्रूनिंग वह प्रक्रिया है जो निर्णय वृक्षों के आकार को कम करती है। यह वृक्ष के आकार को परिभाषित करके या वृक्ष के उन क्षेत्रों को हटाकर ओवरफिटिंग के जोखिम को कम कर सकती है जो थोड़ी शक्ति प्रदान करते हैं। प्रूनिंग उन शाखाओं को काटकर मदद करती है जो शोर या आउटलेयर्स के कारण प्रशिक्षण जानकारी में विसंगतियों का पालन करती हैं और मूल वृक्ष को इस तरह से समर्थन करती है जो वृक्ष की सामान्यीकरण दक्षता को बढ़ाता है।
विभिन्न विधियां आमतौर पर कम विश्वसनीय विभागों को हटाने के लिए सांख्यिकीय उपायों का उपयोग करती हैं, जिसके परिणामस्वरूप अक्सर तेजी से वर्गीकरण और स्वतंत्र टेस्ट डेटा को सही ढंग से वर्गीकृत करने की वृक्ष की क्षमता में सुधार होता है।
ट्री प्रूनिंग के दो दृष्टिकोण निम्नलिखित हैं:
प्री-प्रूनिंग दृष्टिकोण (Pre-pruning Approach)
प्री-प्रूनिंग दृष्टिकोण में, एक वृक्ष को इसकी निर्माण जल्दी रोककर "प्रून" किया जाता है (उदाहरण के लिए, किसी दिए गए नोड पर प्रशिक्षण नमूनों के उपसमुच्चय को आगे विभाजित या विभाजन नहीं करने का निर्णय लेकर)। रुकने पर, नोड एक पत्ती बन जाता है। पत्ती उपसमुच्चय नमूनों के बीच सबसे आम वर्ग को प्रभावित कर सकती है, या उन नमूनों की संभाव्यता वितरण।
वृक्ष बनाते समय, सांख्यिकीय महत्व, x², सूचना लाभ आदि जैसे उपायों का उपयोग विभाजन की उदारता बनाने के लिए किया जा सकता है। यदि किसी नोड पर नमूनों को विभाजित करने से एक विभाजन होता है जो पूर्व-निर्दिष्ट थ्रेशोल्ड से नीचे आता है, तो दिए गए उपसमुच्चय का विभाजन रोक दिया जाता है। उपयुक्त थ्रेशोल्ड चुनने में समस्याएं हैं। उच्च थ्रेशोल्ड के परिणामस्वरूप ओवरसिम्प्लीफाइड वृक्ष हो सकते हैं, जबकि कम थ्रेशोल्ड के परिणामस्वरूप बहुत कम सरलीकरण हो सकता है।
पोस्ट-प्रूनिंग दृष्टिकोण (Post-pruning Approach)
पोस्ट-प्रूनिंग दृष्टिकोण "पूरी तरह से विकसित" वृक्ष से शाखाओं को हटा देता है। एक वृक्ष नोड को इसकी शाखाओं को हटाकर प्रून किया जाता है। मूल्य जटिलता प्रूनिंग एल्गोरिदम पोस्ट-प्रूनिंग दृष्टिकोण का एक उदाहरण है। प्रून किया गया नोड एक पत्ती बन जाता है और इसकी पिछली शाखाओं के बीच सबसे आम वर्ग द्वारा लेबल किया जाता है।
वृक्ष में प्रत्येक गैर-पत्ती नोड के लिए, एल्गोरिदम अपेक्षित त्रुटि दर की गणना करता है जो दिखाई दे सकती है यदि उस नोड पर उपवृक्ष को छोटा किया गया होता। अगला, अपेक्षित त्रुटि दर की गणना की जाती है यदि नोड को प्रून नहीं किया गया होता, प्रत्येक शाखा के लिए त्रुटि दरों का उपयोग करके, प्रत्येक शाखा के साथ टिप्पणियों के आयाम के अनुसार भारित करके जुड़ा हुआ। यदि नोड को प्रून करने से उच्च अपेक्षित त्रुटि दर होती है, तो उपवृक्ष संरक्षित होता है। इसलिए, इसे प्रून किया जाता है।
तेजी से प्रून किए गए वृक्षों का एक सेट बनाने के बाद, एक स्वतंत्र टेस्ट सेट प्रत्येक वृक्ष की दक्षता का अनुमान लगा सकता है। वह निर्णय वृक्ष जो अपेक्षित त्रुटि लागत को कम करता है, पसंद किया जाता है।
