निर्णय ट्री कृंतन (डिसीजन ट्री प्रूनिंग)

कृन्तन से पहले और बाद में

कृन्तन यंत्र अधिगम और खोज कलन विधि में डेटा संपीड़न तकनीक है जो ट्री के उन हिस्सों को हटाकर निर्णय ट्री के आकार को कम करती है जो उदाहरणों को वर्गीकृत करने के लिए गैर-महत्वपूर्ण और अनावश्यक हैं। कृन्तन अंतिम सांख्यिकीय वर्गीकरण की जटिलता को कम कर देता है, और इसलिए अत्युपपन्न को कम करके पूर्वानुमान सटीकता में सुधार करता है।

निर्णय ट्री कलन विधि में उठने वाले प्रश्नों में से एक अंतिम ट्री का इष्टतम आकार है। एक ट्री जो बहुत बड़ा है, प्रशिक्षण डेटा को अत्युपपन्न करने और नए सैम्पल को खराब तरीके से सामान्यीकृत करने का संकट उठाता है। एक छोटा ट्री प्रतिदर्श समष्टि के बारे में महत्वपूर्ण संरचनात्मक जानकारी प्राप्त नहीं कर सकता है। हालाँकि, यह बताना कठिन है कि ट्री कलन विधि को कब बंद करना चाहिए क्योंकि यह बताना असंभव है कि क्या एक भी अतिरिक्त नोड जोड़ने से त्रुटि में प्रभावशाली रूप से कमी आएगी। इस समस्या को क्षितिज प्रभाव के रूप में जाना जाता है। एक सामान्य रणनीति ट्री को तब तक बढ़ाना है जब तक कि प्रत्येक नोड में कम संख्या में उदाहरण न हों, फिर उन नोड्स को हटाने के लिए कृन्तन का उपयोग करें जो अतिरिक्त जानकारी प्रदान नहीं करते हैं।

अंतः वैधीकरण समूह द्वारा मापी गई पूर्वानुमानित सटीकता को कम किए बिना, कृन्तन को लर्निंग ट्री के आकार को कम करना चाहिए। ट्री की कृन्तन के लिए कई तकनीकें हैं जो प्रदर्शन को अनुकूलित करने के लिए उपयोग किए जाने वाले माप में भिन्न होती हैं।

तकनीक

कृन्तन प्रक्रियाओं को दो प्रकारों में विभाजित किया जा सकता है (कृन्तन से पहले और बाद में)।

प्री-कृन्तन प्रक्रियाएं प्रवर्तन कलन विधि में स्टॉप () मानदंड को प्रतिस्थापित करके प्रशिक्षण समूह के पूर्ण प्रेरण को रोकती हैं (उदाहरण के लिए अधिकतम ट्री की गहराई या सूचना लाभ (एटीटीआर)> मिनगैन)। प्री-कृन्तन विधियों को अधिक कुशल माना जाता है क्योंकि वे पूरे समूह को प्रेरित नहीं करते हैं, बल्कि ट्री आरंभ से ही छोटे रहते हैं। प्री-कृन्तन विधियों में एक आम समस्या है, क्षितिज प्रभाव। इसे स्टॉप () मानदंड द्वारा प्रवर्तन की अवांछित समयपूर्व समाप्ति के रूप में समझा जाना चाहिए।

कृन्तन के बाद (या सिर्फ कृन्तन) ट्री को सरल बनाने का सबसे आम तरीका है। यहां, जटिलता को कम करने के लिए नोड्स और उपट्री को पत्तियों से बदल दिया गया है। कृन्तन न केवल आकार को काफी कम कर सकती है बल्कि अनदेखी वस्तुओं की वर्गीकरण सटीकता में भी सुधार कर सकती है। ऐसा हो सकता है कि ट्रेन समूह पर समनुदेशन की सटीकता ख़राब हो जाए, लेकिन ट्री के वर्गीकरण गुणों की सटीकता समग्र रूप से बढ़ जाती है।

प्रक्रियाओं को ट्री में उनके दृष्टिकोण (ऊपर से नीचे या नीचे से ऊपर) के आधार पर विभेदित किया जाता है।

बॉटम-अप (नीचे से ऊपर की ओर) कृन्तन

ये प्रक्रियाएँ ट्री के अंतिम नोड (निम्नतम बिंदु) से आरंभ होती हैं। पुनरावर्ती रूप से ऊपर की ओर चलते हुए, वे प्रत्येक व्यक्तिगत नोड की प्रासंगिकता निर्धारित करते हैं। यदि वर्गीकरण के लिए प्रासंगिकता नहीं दी गई है, तो नोड को हटा दिया जाता है या एक पत्ते से बदल दिया जाता है। लाभ यह है कि इस विधि से कोई भी प्रासंगिक उप-ट्री नष्ट नहीं हो सकता। इन विधियों में रिड्यूस्ड एरर कृन्तन (आरईपी), मिनिमम कॉस्ट कॉम्प्लेक्सिटी कृन्तन (एमसीसीपी), या मिनिमम एरर कृन्तन (एमईपी) युक्त हैं।

टॉप-डाउन (ऊपर से नीचे की ओर) कृन्तन

बॉटम-अप विधि के विपरीत, यह विधि ट्री की जड़ से आरंभ होती है। नीचे दी गई संरचना के बाद, एक प्रासंगिकता जांच की जाती है जो यह तय करती है कि एक नोड सभी एन वस्तुओं के वर्गीकरण के लिए प्रासंगिक है या नहीं। किसी आंतरिक नोड पर ट्री की कृन्तन करने से, ऐसा हो सकता है कि पूरा उप-ट्री (इसकी प्रासंगिकता की परवाह किए बिना) गिरा दिया जाए। इन प्रतिनिधियों में से एक निराशावादी त्रुटि कृन्तन (पीईपी) है, जो अनदेखी वस्तुओं के साथ काफी अच्छे परिणाम लाता है।

कृन्तन कलन विधि

कम त्रुटि कृन्तन

कृन्तन के सबसे सरल रूपों में से एक कम त्रुटि वाली कृन्तन है। पत्तियों से आरंभ करके, प्रत्येक नोड को उसके सबसे लोकप्रिय वर्ग से बदल दिया जाता है। यदि पूर्वानुमान की सटीकता प्रभावित नहीं होती है तो परिवर्तन रखा जाता है। हालांकि कुछ हद तक सरल, कम त्रुटि वाली कृन्तन में सरलता और गति का लाभ होता है।

लागत जटिलता कृन्तन

लागत जटिलता कृन्तन ट्री की एक श्रृंखला $T_{0}\dots T_{m}$ उत्पन्न करती है जहां $T_{0}$ प्रारंभिक ट्री है और $T_{m}$ अकेले जड़ है। चरण $i$ पर, ट्री $i-1$ से एक उपट्री हटाकर ट्री बनाया जाता है और इसे ट्री बिल्डिंग कलन विधि के अनुसार चुने गए मान के साथ लीफ नोड के साथ बदलकर ट्री बनाया जाता है।। हटाया गया उपट्री इस प्रकार चुना गया है:

1. डेटा समूह $S$ पर ट्री $T$ पर $\operatorname {err} (T,S)$ के रूप में परिभाषित करें।
2. उपट्री $t$ जो ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ को न्यूनतम करता है उसे हटाने के लिए चुना गया है।

कार्यक्रम $\operatorname {prune} (T,t)$ ट्री $T$ से उपट्री $t$ की कृन्तन द्वारा प्राप्त ट्री को परिभाषित करता है। एक बार ट्री की श्रृंखला बन जाने के बाद, प्रशिक्षण समूह या क्रॉस-सत्यापन द्वारा मापी गई सामान्यीकृत सटीकता द्वारा सर्वश्रेष्ठ ट्री का चयन किया जाता है।

यह भी देखें

• अल्फा-बीटा कृन्तन
• कृत्रिम तंत्रिका नेटवर्क
• अशक्त-चाल अनुमानी

संदर्भ

• Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 978-0-201-05594-8.
• Mansour, Y. (1997). "Pessimistic decision tree pruning based on tree size". Proc. 14th International Conference on Machine Learning. pp. 195–201.
• Breslow, L. A.; Aha, D. W. (1997). "Simplifying Decision Trees: A Survey". The Knowledge Engineering Review. 12 (1): 1–47. doi:10.1017/S0269888997000015. S2CID 18782652.
• Quinlan, J. R. (1986). "Induction of Decision Trees". Machine Learning. Kluwer. 1: 81–106. doi:10.1007/BF00116251.

अग्रिम पठन

• MDL based decision tree pruning
• Decision tree pruning using backpropagation neural networks

बाहरी संबंध

• Fast, Bottom-Up Decision Tree Pruning Algorithm
• Introduction to Decision tree pruning