CART प्रूनिंग एल्गोरिदम
CART 1984 में लियो ब्रिमन, जेरोम फ्रीडमैन, रिचर्ड ओलशेन, और चार्ल्स स्टोन द्वारा पहली बार विकसित एक प्रसिद्ध निर्णय वृक्ष एल्गोरिदम है। CART का अर्थ है Classification and Regression Trees। CART एल्गोरिदम बाइनरी ट्री विकसित करता है और विभाजित करना जारी रखता है जब तक नए विभाजन नहीं मिलते जो शुद्धता में सुधार करते हैं।
कुछ सरल सबट्रीज़ हैं, जिनमें से प्रत्येक मॉडल जटिलता और प्रशिक्षण समूह गलत वर्गीकरण दर के बीच एक अलग ट्रेड-ऑफ को दर्शाता है। CART एल्गोरिदम ऐसी सबट्रीज़ के एक समूह को उम्मीदवार मॉडल के रूप में पहचानता है। इन उम्मीदवार सबट्रीज़ को वैलिडेशन समूह पर लागू किया जाता है और न्यूनतम वैलिडेशन सेट गलत वर्गीकरण दर वाली ट्री को अंतिम मॉडल के रूप में चुना जाता है।
प्रूनिंग प्रक्रिया
CART एल्गोरिदम बार-बार प्रूनिंग की प्रक्रिया के माध्यम से उम्मीदवार सबट्रीज़ को पहचानता है। उद्देश्य पहले उन शाखाओं को प्रून करना है जो प्रति पत्ते कम से कम अतिरिक्त भविष्यवाणी शक्ति का समर्थन करती हैं। इन कम से कम लाभकारी शाखाओं को पहचानने के लिए, CART समायोजित त्रुटि दर के रूप में जानी जाने वाली अवधारणा पर निर्भर करता है।
यह एक माप है जो प्रशिक्षण सेट पर प्रत्येक नोड की गलत वर्गीकरण लागत को ट्री में पत्तों की संख्या के आधार पर एक जटिलता दंड देकर सुधारता है। समायोजित त्रुटि दर कमजोर शाखाओं (जिनकी गलत वर्गीकरण दर दंड को दूर करने के लिए पर्याप्त नहीं है) की पहचान कर सकती है और उन्हें प्रूनिंग के लिए इंगित कर सकती है।
अगला कार्य, उम्मीदवार सबट्रीज़ के पूल से, उस एक को चुनना है जो नए रिकॉर्ड पर सबसे अच्छा प्रदर्शन करता है। प्रत्येक उम्मीदवार सबट्रीज़ वैलिडेशन सेट में डेटा को परिभाषित कर सकती है। वह ट्री जो इस कार्य को सबसे कम समग्र त्रुटि दर के साथ करता है, विजेता के रूप में परिभाषित किया जाता है। जीतने वाली सबट्री को ओवरट्रेनिंग के प्रभावों को खत्म करने के लिए पर्याप्त रूप से प्रून किया गया है, लेकिन मूल्यवान जानकारी खोने के लिए इतना नहीं।
क्योंकि यह प्रूनिंग एल्गोरिदम गलत वर्गीकरण दर पर निर्भर करता है, बिना प्रत्येक वर्गीकरण की संभावना को ध्यान में रखे, यह एक सबट्री को पुनर्स्थापित करता है जिसके पत्ते सभी एक ही वर्गीकरण बनाते हैं एक सामान्य पैरेंट के साथ जो वह वर्गीकरण भी बनाता है।
उद्देश्य डेटा के एक छोटे अनुपात को चुनना है (उदाहरण के लिए शीर्ष 1 प्रतिशत या 10 प्रतिशत), यह प्रूनिंग एल्गोरिदम ट्री के कार्यान्वयन को नुकसान पहुंचा सकता है, क्योंकि कुछ समाप्त पत्तों में लक्ष्य वर्ग का बहुत अधिक अनुपात शामिल होता है। SAS Enterprise Miner सहित विभिन्न टूल, उपयोगकर्ता को ऐसी विधियों के लिए ट्री को इष्टतम रूप से प्रून करने में सक्षम बनाते हैं।
जीतने वाली सबट्री को वैलिडेशन सेट में डेटा को परिभाषित करने के कार्य में इसके समग्र त्रुटि दर के आधार पर चुना गया था। यह उम्मीद की जा सकती है कि चयनित सबट्री कई डेटासेट्स पर लागू होने पर सर्वश्रेष्ठ कार्यान्वयन सबट्री बनी रहेगी, वह त्रुटि दर जिसने इसे चुना, इसकी ताकत को थोड़ा बढ़ा-चढ़ाकर बता सकती है।
