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

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

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

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

तकनीक

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

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

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

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

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

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

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

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

प्रूनिंग एल्गोरिदम

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

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

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

लागत जटिलता छंटाई पेड़ों की एक श्रृंखला उत्पन्न करती है $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