एक निर्णय वृक्ष एक फ्लो-चार्ट जैसी वृक्ष संरचना है, जहां प्रत्येक आंतरिक नोड एक विशेषता पर परीक्षण को इंगित करता है, प्रत्येक शाखा परीक्षण के परिणाम को परिभाषित करती है, और पत्ती नोड्स वर्गों या वर्ग वितरण का वर्णन करते हैं। एक वृक्ष में सबसे ऊंचा नोड रूट नोड है।
निर्णय वृक्ष सीखने के लिए एल्गोरिदम
एल्गोरिदम: दिए गए प्रशिक्षण जानकारी से एक निर्णय वृक्ष बनाएं।
इनपुट: प्रशिक्षण नमूने, नमूने, असतत-मूल्यवान विशेषताओं द्वारा वर्णित; छात्र विशेषताओं का सेट, विशेषता-सूची।
आउटपुट: एक निर्णय वृक्ष।
विधि
एक नोड N बनाएं;
यदि नमूने सभी एक ही वर्ग C के हैं, तो
वर्ग C के साथ लेबल किए गए पत्ती नोड के रूप में N लौटाएं
यदि विशेषता-सूची खाली है तो
नमूनों में सबसे आम वर्ग के साथ लेबल किए गए पत्ती नोड के रूप में N लौटाएं। // बहुमत मतदान
टेस्ट-विशेषता चुनें, विशेषता-सूची में सबसे अधिक सूचना लाभ वाली विशेषता।
नोड N को टेस्ट विशेषता के साथ लेबल करें।
टेस्ट-विशेषता के प्रत्येक ज्ञात मान aᵢ के लिए // नमूनों को विभाजित करें।
नोड N से शर्त टेस्ट-विशेषता = aᵢ के लिए एक शाखा बढ़ाएं।
मान लें sᵢ, नमूनों में नमूनों का सेट है जिसके लिए टेस्ट-विशेषता = aᵢ।
यदि sᵢ खाली है तो
नमूनों में सबसे आम वर्ग के साथ लेबल किए गए पत्ती को जोड़ सकते हैं।
अन्यथा Generate decision tree (sᵢ, विशेषता-सूची - टेस्ट-विशेषता) द्वारा लौटाए गए नोड को जोड़ें
निर्णय वृक्ष प्रेरण (Decision Tree Induction)
उदाहरण के लिए निर्णय नियमों का स्वचालित उत्पादन नियम प्रेरण या स्वचालित नियम प्रेरण के रूप में जाना जाता है। निर्णय वृक्ष के निहित डिजाइन में निर्णय नियम बनाना भी अक्सर नियम प्रेरण के रूप में जाना जाता है, लेकिन वृक्ष प्रेरण या निर्णय वृक्ष प्रेरण शब्दों को लगातार चुना जाता है।
निर्णय वृक्ष प्रेरण के लिए मूल एल्गोरिदम एक लालची एल्गोरिदम है। इसका उपयोग टॉप-डाउन पुनरावर्ती विभाजन-और-विजय तरीके से निर्णय वृक्ष उत्पन्न करने के लिए किया जाता है। निर्णय वृक्ष सीखने के लिए मूल एल्गोरिदम, ID3 का एक रूप है, जो एक प्रसिद्ध निर्णय वृक्ष प्रेरण एल्गोरिदम है।
मूल विधियां निम्नलिखित हैं:
वृक्ष प्रशिक्षण नमूनों को परिभाषित करने वाले एकल नोड के रूप में शुरू होता है।
यदि नमूने सभी समान वर्ग के हैं, तो नोड पत्ती बन जाता है और उस वर्ग के साथ लेबल किया जाता है।
एल्गोरिदम सूचना लाभ के रूप में संदर्भित एन्ट्रॉपी-आधारित माप को लागू करता है जो नमूनों को एकल वर्गों में विभाजित करने वाली विशेषता को चुनने के लिए एक ह्यूरिस्टिक के रूप में होता है। यह विशेषता नोड पर "टेस्ट" या "निर्णय" विशेषता बन जाती है। एल्गोरिदम के इस रूप में, सभी विशेषताएं श्रेणीबद्ध हैं, यानी असतत-मूल्यवान। सतत मूल्यवान विशेषताओं को डिस्क्रीटाइज़ किया जाना चाहिए।
टेस्ट विशेषता के प्रत्येक ज्ञात मान के लिए एक शाखा उत्पन्न होती है, और नमूनों को उचित रूप से विभाजित किया जाता है।
एल्गोरिदम प्रत्येक विभाजन पर नमूनों के लिए निर्णय वृक्ष बनाने के लिए एक समान प्रक्रिया को लूप करता है। चूंकि एक विशेषता एक नोड पर दिखाई दी है, इसे नोड के किसी भी वंशज में नहीं माना जाना आवश्यक है।
