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

छंटाई से पहले और बाद में

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

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

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

तकनीक

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

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

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

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

नीचे से ऊपर की ओर छंटाई

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

ऊपर से नीचे की ओर छंटाई

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

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

कम त्रुटि छंटाई

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

लागत जटिलता छंटाई

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

1. पेड़ की त्रुटि दर को परिभाषित करें $T$ डेटा समूह पर $S$ जैसा $\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