निर्णय वृक्ष सीखना

This article is about decision trees in machine learning. For the use of the term in decision analysis, see Decision tree.

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

ट्री मॉडल जहां लक्ष्य चर मूल्यों का असतत सेट ले सकता है उसे वर्गीकरण निर्णय वृक्ष कहा जाता है; इन वृक्ष संरचनाओं में, पर्ण्सन्धि वर्ग लेबल का प्रतिनिधित्व करता है और शाखाएँ उन विशेषताओं के तार्किक संयोजनों का प्रतिनिधित्व करती हैं जो उन वर्ग लेबलों की ओर ले जाती हैं। निर्णय वृक्ष जहां लक्ष्य चर निरंतर मान ले सकता है (आमतौर पर वास्तविक संख्या) को प्रतिगमन विश्लेषण निर्णय वृक्ष कहा जाता है।

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

सामान्य

टाइटैनिक पर यात्रियों के जीवित रहने को दर्शाने वाला एक पेड़ (सिबस्प सवार पति-पत्नी या भाई-बहनों की संख्या है)। पत्तियों के नीचे के आंकड़े जीवित रहने की संभावना और पत्ती में प्रेक्षणों के प्रतिशत को दर्शाते हैं। संक्षेप में: यदि आप (i) एक महिला या (ii) अधिकतम 9.5 वर्ष के पुरुष और 3 से कम भाई-बहन हैं तो आपके जीवित रहने की संभावना अच्छी थी।

डिसीजन ट्री लर्निंग डेटा माइनिंग में आमतौर पर इस्तेमाल की जाने वाली एक विधि है। लक्ष्य एक मॉडल बनाना है जो कई इनपुट चर के आधार पर लक्ष्य चर के मूल्य की भविष्यवाणी करता है।

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

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

डेटा फॉर्म के रिकॉर्ड में आता है:

$({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)$

आश्रित चर, $Y$, वह लक्ष्य चर है जिसे हम समझने, वर्गीकृत करने या सामान्य बनाने का प्रयास कर रहे हैं। सदिश ${\textbf {x}}$ सुविधाओं से बना है, $x_{1},x_{2},x_{3}$ आदि जो उस कार्य में प्रयुक्त होते हैं।

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

निर्णय वृक्ष प्रकार

डेटा माइनिंग में उपयोग किए जाने वाले निर्णय वृक्ष दो मुख्य प्रकार के होते हैं:

• वर्गीकरण ट्री विश्लेषण तब होता है जब अनुमानित परिणाम वह वर्ग (असतत) होता है जिससे डेटा संबंधित होता है।
• प्रतिगमन वृक्ष विश्लेषण तब होता है जब अनुमानित परिणाम को वास्तविक संख्या माना जा सकता है (उदाहरण के लिए घर की कीमत, या अस्पताल में रोगी की रहने की अवधि)।

शब्द वर्गीकरण और प्रतिगमन ट्री (CART) विश्लेषण एक छत्र शब्द है जिसका उपयोग उपरोक्त प्रक्रियाओं में से किसी एक को संदर्भित करने के लिए किया जाता है, जिसे पहले लियो ब्रिमन एट अल द्वारा प्रस्तुत किया गया था। 1984 में। प्रतिगमन के लिए उपयोग किए जाने वाले पेड़ों और वर्गीकरण के लिए उपयोग किए जाने वाले पेड़ों में कुछ समानताएँ हैं - लेकिन कुछ अंतर भी हैं, जैसे कि विभाजित करने के लिए निर्धारित करने के लिए उपयोग की जाने वाली प्रक्रिया।

कुछ तकनीकें, जिन्हें अक्सर पहनावा विधि कहा जाता है, एक से अधिक निर्णय वृक्ष का निर्माण करती हैं:

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

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

• आईडी3 एल्गोरिथम (पुनरावृत्ति डाइकोटोमाइज़र 3)
• C4.5 एल्गोरिथ्म | C4.5 (ID3 का उत्तराधिकारी)
• प्रिडिक्टिव एनालिटिक्स#क्लासिफिकेशन और रिग्रेशन ट्री .28CART.29 (क्लासिफिकेशन एंड रिग्रेशन ट्री)* ची-स्क्वायर स्वचालित इंटरैक्शन डिटेक्शन (CHAID)। वर्गीकरण ट्री की गणना करते समय बहु-स्तरीय विभाजन करता है।
• बहुभिन्नरूपी अनुकूली प्रतिगमन स्प्लिन: संख्यात्मक डेटा को बेहतर ढंग से संभालने के लिए निर्णय पेड़ों का विस्तार करता है।
• सशर्त निष्कर्ष पेड़। सांख्यिकी-आधारित दृष्टिकोण जो गैर-पैरामीट्रिक परीक्षणों को विभाजन मानदंड के रूप में उपयोग करता है, ओवरफिटिंग से बचने के लिए कई परीक्षणों के लिए सही किया जाता है। इस दृष्टिकोण के परिणामस्वरूप निष्पक्ष भविष्यवक्ता चयन होता है और इसमें छंटाई की आवश्यकता नहीं होती है।

ID3 और CART का आविष्कार लगभग एक ही समय (1970 और 1980 के बीच) स्वतंत्र रूप से किया गया था।, फिर भी प्रशिक्षण टुपल्स से निर्णय वृक्ष सीखने के लिए एक समान दृष्टिकोण का पालन करें।

निर्णय ट्री के एक विशेष संस्करण की परिभाषा के लिए फ़ज़ी सेट सिद्धांत की अवधारणाओं का लाभ उठाने का भी प्रस्ताव किया गया है, जिसे फ़ज़ी डिसीज़न ट्री (FDT) के रूप में जाना जाता है। इस प्रकार के फ़ज़ी वर्गीकरण में, आम तौर पर, एक इनपुट वेक्टर ${\textbf {x}}$ कई वर्गों से जुड़ा हुआ है, प्रत्येक एक अलग आत्मविश्वास मूल्य के साथ। एफडीटी के बूस्टेड एनसेंबल की हाल ही में जांच की गई है, और उन्होंने अन्य बहुत ही कुशल फ़ज़ी क्लासिफायर की तुलना में प्रदर्शन दिखाया है।

मेट्रिक्स

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

सकारात्मक शुद्धता का अनुमान

एक सरल और प्रभावी मीट्रिक का उपयोग उस डिग्री की पहचान करने के लिए किया जा सकता है जिस पर सच्ची सकारात्मकता वास्तविक नकारात्मकता से अधिक होती है (भ्रम मैट्रिक्स देखें)। यह मीट्रिक, सकारात्मक शुद्धता का अनुमान नीचे परिभाषित किया गया है:

$E_{P}=TP-FP$ इस समीकरण में, कुल झूठे धनात्मक (FP) को कुल सत्य धनात्मक (TP) से घटाया जाता है। परिणामी संख्या इस बात का अनुमान लगाती है कि सुविधा कितने सकारात्मक उदाहरणों को डेटा के भीतर सही ढंग से पहचान सकती है, उच्च संख्या के साथ जिसका अर्थ है कि सुविधा अधिक सकारात्मक नमूनों को सही ढंग से वर्गीकृत कर सकती है। नीचे एक उदाहरण दिया गया है कि किसी विशेष सुविधा का पूरा भ्रम मैट्रिक्स दिए जाने पर मीट्रिक का उपयोग कैसे किया जाता है:

फ़ीचर ए कन्फ्यूजन मैट्रिक्स

Predicted Class Actual Class	Cancer	Non-cancer
Cancer	8	3
Non-cancer	2	5

यहाँ हम देख सकते हैं कि TP मान 8 होगा और FP मान 2 होगा (तालिका में रेखांकित संख्याएँ)। जब हम इन नंबरों को समीकरण में प्लग करते हैं तो हम अनुमान की गणना करने में सक्षम होते हैं: $E_{p}=TP-FP=8-2=6$. इसका अर्थ है कि इस सुविधा पर अनुमान का उपयोग करने पर इसे 6 का स्कोर प्राप्त होगा।

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

Feature A Confusion Matrix Predicted Class Actual Class Cancer Non-cancer Cancer 8 3 Non-cancer 2 5	फ़ीचर बी कन्फ्यूजन मैट्रिक्स Predicted Class Actual Class Cancer Non-cancer Cancer 6 2 Non-cancer 2 8
$E_{p}=TP-FP=8-2=6$ $TPR=TP/(TP+FN)=8/(8+3)\approx 0.73$	$E_{p}=TP-FP=6-2=4$ $TPR=TP/(TP+FN)=6/(6+2)=0.75$

इस उदाहरण में, फीचर ए का अनुमान 6 और टीपीआर लगभग 0.73 था जबकि फीचर बी का अनुमान 4 और टीपीआर 0.75 था। इससे पता चलता है कि हालांकि कुछ फीचर के लिए सकारात्मक अनुमान अधिक हो सकता है, लेकिन उस फीचर के लिए अधिक सटीक टीपीआर मूल्य कम सकारात्मक अनुमान वाली अन्य सुविधाओं की तुलना में कम हो सकता है। डेटा और डिसीजन ट्री की स्थिति और ज्ञान के आधार पर, कोई अपनी समस्या के त्वरित और आसान समाधान के लिए सकारात्मक अनुमान का उपयोग करने का विकल्प चुन सकता है। दूसरी ओर, एक अधिक अनुभवी उपयोगकर्ता सुविधाओं को रैंक करने के लिए TPR मान का उपयोग करना पसंद करेगा क्योंकि यह डेटा के अनुपात और उन सभी नमूनों को ध्यान में रखता है जिन्हें सकारात्मक के रूप में वर्गीकृत किया जाना चाहिए था।

गिनी अशुद्धता

गिनी अशुद्धता, गिनी की विविधता सूचकांक, या Diversity_index#Gini%E2%80%93Simpson_index|Gini-Simpson Index जैव विविधता अनुसंधान में, वर्गीकरण पेड़ों के लिए CART (वर्गीकरण और प्रतिगमन ट्री) एल्गोरिथ्म द्वारा उपयोग किया जाता है, Gini अशुद्धता (इतालवी गणितज्ञ Corrado Gini के नाम पर) एक उपाय है कि कैसे अक्सर सेट से यादृच्छिक रूप से चुने गए तत्व को गलत तरीके से लेबल किया जाएगा यदि इसे सबसेट में लेबल के वितरण के अनुसार यादृच्छिक रूप से लेबल किया गया हो। गिन्नी अशुद्धता की गणना संभाव्यता को जोड़कर की जा सकती है $p_{i}$ लेबल वाले किसी आइटम का $i$ संभाव्यता से गुणा चुना जा रहा है $\sum _{k\neq i}p_{k}=1-p_{i}$ उस वस्तु को वर्गीकृत करने में गलती के कारण। यह अपने न्यूनतम (शून्य) तक पहुँच जाता है जब नोड के सभी मामले एक लक्ष्य श्रेणी में आते हैं।

गिन्नी अशुद्धता भी एक सूचना सिद्धांत उपाय है और विरूपण गुणांक के साथ सॉलिस एंट्रॉपी से मेल खाती है $q=2$, जो भौतिक विज्ञान में आउट-ऑफ-संतुलन, गैर-व्यापक, विघटनकारी और क्वांटम सिस्टम में जानकारी की कमी से जुड़ा है। सीमा के लिए $q\to 1$ एक सामान्य बोल्ट्जमैन-गिब्स या शैनन एन्ट्रापी को पुनः प्राप्त करता है। इस अर्थ में, गिन्नी अशुद्धता और कुछ नहीं बल्कि निर्णय पेड़ों के लिए सामान्य एन्ट्रापी माप की भिन्नता है।

वस्तुओं के एक सेट के लिए गिन्नी अशुद्धता की गणना करना $J$ वर्ग, मान लीजिए $i\in \{1,2,...,J\}$, और जाने $p_{i}$ वर्ग के साथ लेबल किए गए आइटम का अंश हो $i$ सेट में।

$\operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-p_{i}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}p_{i}^{2}=1-\sum _{i=1}^{J}p_{i}^{2}$

सूचना प्राप्ति

Main article: Information gain in decision trees

ID3 एल्गोरिथ्म, C4.5 एल्गोरिथम | C4.5 और C5.0 ट्री-जेनरेशन एल्गोरिदम द्वारा उपयोग किया जाता है। सूचना लाभ सूचना एन्ट्रापी की अवधारणा और सूचना सिद्धांत से सूचना सामग्री पर आधारित है।

एंट्रॉपी को नीचे परिभाषित किया गया है

$\mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},\ldots ,p_{J}\right)=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}$

कहाँ पे $p_{1},p_{2},\ldots$ अंश हैं जो 1 तक जोड़ते हैं और बच्चे के नोड में मौजूद प्रत्येक वर्ग के प्रतिशत का प्रतिनिधित्व करते हैं जो पेड़ में विभाजन के परिणामस्वरूप होता है। <रेफरी नाम = विटन 2011 102-103>Witten, Ian; Frank, Eibe; Hall, Mark (2011). डेटा माइनिंग. Burlington, MA: Morgan Kaufmann. pp. 102–103. ISBN 978-0-12-374856-0.</रेफरी>

$$\overbrace {IG(T,a)} ^{\text{information gain}}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{sum of entropies (children)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

के संभावित मूल्यों पर औसत $A$,

$$\overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{expected information gain}}=\overbrace {I(T;A)} ^{{\text{mutual information between }}T{\text{ and }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{weighted sum of entropies (children)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

जहां एंट्रॉपी का भारित योग दिया जाता है,

${\mathrm {H} (T\mid A)}=\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

अर्थात्, अपेक्षित सूचना लाभ पारस्परिक सूचना है, जिसका अर्थ है कि औसतन T की एन्ट्रापी में कमी पारस्परिक सूचना है।

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

चार विशेषताओं के साथ एक उदाहरण डेटा सेट पर विचार करें: आउटलुक (धूप, घटाटोप, बरसात), तापमान (गर्म, हल्का, ठंडा), आर्द्रता (उच्च, सामान्य), और हवादार (सच, गलत), बाइनरी (हाँ या नहीं) के साथ लक्ष्य चर, खेल और 14 डेटा बिंदु। इस डेटा पर एक निर्णय ट्री बनाने के लिए, हमें चार पेड़ों में से प्रत्येक के सूचना लाभ की तुलना करने की आवश्यकता है, प्रत्येक चार विशेषताओं में से एक पर विभाजित होता है। उच्चतम सूचना लाभ वाले विभाजन को पहले विभाजन के रूप में लिया जाएगा और यह प्रक्रिया तब तक जारी रहेगी जब तक कि सभी चिल्ड्रन नोड्स में सुसंगत डेटा न हो, या जब तक सूचना लाभ 0 न हो।

विंडी का उपयोग करके विभाजन की जानकारी प्राप्त करने के लिए, हमें पहले विभाजन से पहले डेटा में जानकारी की गणना करनी चाहिए। मूल डेटा में नौ हां और पांच ना शामिल थे।

$I_{E}([9,5])=-{\frac {9}{14}}\log _{2}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.94$

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

$I_{E}([3,3])=-{\frac {3}{6}}\log _{2}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}{\frac {1}{2}}=1$

उस नोड के लिए जहां वाइंडी=फाल्स आठ डेटा बिंदु थे, छह हां और दो नहीं। इस प्रकार हमारे पास है

$I_{E}([6,2])=-{\frac {6}{8}}\log _{2}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}{\frac {1}{4}}=0.81$

विभाजन की जानकारी प्राप्त करने के लिए, हम इन दो संख्याओं के भारित औसत को इस आधार पर लेते हैं कि कितने अवलोकन किस नोड में गिरे।

$I_{E}([3,3],[6,2])=I_{E}({\text{windy or not}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.81=0.89$

अब हम विंडी फीचर पर विभाजन द्वारा प्राप्त सूचना लाभ की गणना कर सकते हैं।

$\operatorname {IG} ({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05$

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

सूचना लाभ को जैव विविधता अनुसंधान में Diversity_index#Shannon_index के रूप में भी जाना जाता है।

भिन्नता में कमी

कार्ट में पेश किया गया,विचरण में कमी अक्सर ऐसे मामलों में नियोजित होती है जहां लक्ष्य चर निरंतर (रिग्रेशन ट्री) होता है, जिसका अर्थ है कि कई अन्य मेट्रिक्स के उपयोग के लिए पहले लागू होने से पहले विवेक की आवश्यकता होगी। एक नोड के विचरण में कमी N लक्ष्य चर के विचरण की कुल कमी के रूप में परिभाषित किया गया है Y इस नोड पर विभाजन के कारण:

$I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(y_{i}-y_{j})^{2}-\left({\frac {|S_{t}|^{2}}{|S|^{2}}}{\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{2}+{\frac {|S_{f}|^{2}}{|S|^{2}}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)$

कहाँ पे $S$, $S_{t}$, तथा $S_{f}$ प्रीस्प्लिट सैंपल इंडेक्स का सेट है, सैंपल इंडेक्स का सेट है जिसके लिए स्प्लिट टेस्ट ट्रू है, और सैंपल इंडेक्स का सेट है जिसके लिए स्प्लिट टेस्ट गलत है। उपरोक्त योगों में से प्रत्येक वास्तव में विचरण अनुमान हैं, हालांकि, सीधे अर्थ का उल्लेख किए बिना एक रूप में लिखा गया है।

अच्छाई का पैमाना

1984 में CART द्वारा उपयोग किया गया, अच्छाई का माप एक ऐसा कार्य है जो समान आकार के बच्चों को बनाने की क्षमता के साथ शुद्ध बच्चों को बनाने के लिए एक उम्मीदवार विभाजन की क्षमता के संतुलन को अनुकूलित करना चाहता है। पेड़ पूरा होने तक प्रत्येक अशुद्ध नोड के लिए यह प्रक्रिया दोहराई जाती है। कार्यक्रम $\varphi (s\mid t)$, कहाँ पे $s$ एक उम्मीदवार नोड पर विभाजित है $t$, नीचे के रूप में परिभाषित किया गया है

$\varphi (s\mid t)=2P_{L}P_{R}\sum _{j=1}^{\text{class count}}|P(j\mid t_{L})-P(j\mid t_{R})|$

कहाँ पे $t_{L}$ तथा $t_{R}$ नोड के बाएँ और दाएँ बच्चे हैं $t$ विभाजन का उपयोग करना $s$, क्रमश; $P_{L}$ तथा $P_{R}$ में रिकॉर्ड के अनुपात हैं $t$ में $t_{L}$ तथा $t_{R}$, क्रमश; तथा $P(j\mid t_{L})$ तथा $P(j\mid t_{R})$ वर्ग के अनुपात हैं $j$ में रिकॉर्ड $t_{L}$ तथा $t_{R}$, क्रमश।

तीन विशेषताओं के साथ एक उदाहरण डेटा सेट पर विचार करें: बचत (निम्न, मध्यम, उच्च), संपत्ति (निम्न, मध्यम, उच्च), आय (संख्यात्मक मूल्य), और एक बाइनरी लक्ष्य चर क्रेडिट जोखिम (अच्छा, बुरा) और 8 डेटा बिंदु।पूरा डेटा नीचे दी गई तालिका में प्रस्तुत किया गया है। निर्णय वृक्ष शुरू करने के लिए, हम अधिकतम मान की गणना करेंगे $\varphi (s\mid t)$ प्रत्येक सुविधा का उपयोग करके यह पता लगाने के लिए कि कौन रूट नोड को विभाजित करेगा। यह प्रक्रिया तब तक चलती रहेगी जब तक कि सभी बच्चे शुद्ध या सभी नहीं हो जाते $\varphi (s\mid t)$ मान एक निर्धारित सीमा से नीचे हैं।

Customer	Savings	Assets	Income ($1000s)	Credit risk
1	Medium	High	75	Good
2	Low	Low	50	Bad
3	High	Medium	25	Bad
4	Medium	Medium	50	Good
5	Low	Medium	100	Good
6	High	High	25	Good
7	Low	Low	25	Bad
8	Medium	Medium	75	Good

ढूँढ़ने के लिए $\varphi (s\mid t)$ सुविधा बचत के लिए, हमें प्रत्येक मान की मात्रा को नोट करना होगा। मूल डेटा में तीन लो, तीन मीडियम और दो हाई शामिल थे। निम्न में से किसी का क्रेडिट जोखिम अच्छा था जबकि मध्यम और उच्च में से 4 का क्रेडिट जोखिम अच्छा था। एक उम्मीदवार विभाजन मान लें $s$ जैसे कि कम बचत वाले रिकॉर्ड बाएं बच्चे में डाल दिए जाएंगे और अन्य सभी रिकॉर्ड दाएं बच्चे में डाल दिए जाएंगे।

$\varphi (s\mid {\text{root}})=2\cdot {\frac {3}{8}}\cdot {\frac {5}{8}}\cdot \left(\left|\left({\frac {1}{3}}-{\frac {4}{5}}\right)\right|+\left|\left({\frac {2}{3}}-{\frac {1}{5}}\right)\right|\right)=0.44$

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

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

उपयोग करता है

लाभ

डेटा माइनिंग के अन्य तरीकों में, डिसीजन ट्री के कई फायदे हैं:

• समझने और व्याख्या करने में आसान। संक्षिप्त विवरण के बाद लोग निर्णय ट्री मॉडल को समझने में सक्षम होते हैं। पेड़ों को रेखांकन के रूप में भी प्रदर्शित किया जा सकता है जो गैर-विशेषज्ञों के लिए व्याख्या करना आसान है।
• संख्यात्मक और श्रेणीबद्ध चर डेटा दोनों को संभालने में सक्षम।अन्य तकनीकें आमतौर पर डेटासेट का विश्लेषण करने में विशिष्ट होती हैं जिनमें केवल एक प्रकार का चर होता है। (उदाहरण के लिए, संबंध नियमों का उपयोग केवल नाममात्र चर के साथ किया जा सकता है, जबकि तंत्रिका नेटवर्क का उपयोग केवल संख्यात्मक चर या श्रेणीबद्ध के साथ 0-1 मानों में परिवर्तित किया जा सकता है।) प्रारंभिक निर्णय पेड़ केवल श्रेणीबद्ध चर को संभालने में सक्षम थे, लेकिन हाल के संस्करण, जैसे C4.5 के रूप में, यह सीमा नहीं है।* थोड़ा डेटा तैयार करने की आवश्यकता है। अन्य तकनीकों में अक्सर डेटा सामान्यीकरण की आवश्यकता होती है। चूंकि पेड़ गुणात्मक भविष्यवाणियों को संभाल सकते हैं, इसलिए डमी चर (सांख्यिकी) बनाने की कोई आवश्यकता नहीं है।* एक सफेद बॉक्स (सॉफ्टवेयर इंजीनियरिंग) या ओपन-बॉक्स का उपयोग करता हैनमूना। यदि किसी मॉडल में दी गई स्थिति को देखा जा सकता है तो स्थिति की व्याख्या बूलियन लॉजिक द्वारा आसानी से समझाई जा सकती है। इसके विपरीत, एक ब्लैक बॉक्स मॉडल में, परिणामों के लिए स्पष्टीकरण को समझना आम तौर पर मुश्किल होता है, उदाहरण के लिए एक कृत्रिम तंत्रिका नेटवर्क के साथ।
• सांख्यिकीय परीक्षणों का उपयोग करके एक मॉडल को मान्य करना संभव है। इससे मॉडल की विश्वसनीयता का पता लगाना संभव हो जाता है।
• गैर-पैरामीट्रिक दृष्टिकोण जो प्रशिक्षण डेटा या भविष्यवाणी अवशेषों की कोई धारणा नहीं बनाता है; उदाहरण के लिए, कोई वितरणात्मक, स्वतंत्रता, या निरंतर भिन्नता धारणा नहीं
• बड़े डेटासेट के साथ अच्छा प्रदर्शन करता है। उचित समय में मानक कंप्यूटिंग संसाधनों का उपयोग करके बड़ी मात्रा में डेटा का विश्लेषण किया जा सकता है।
• अन्य दृष्टिकोणों की तुलना में मानव निर्णय लेने को अधिक बारीकी से प्रतिबिंबित करता है।मानवीय निर्णयों/व्यवहार की मॉडलिंग करते समय यह उपयोगी हो सकता है।
• सह-रैखिकता के खिलाफ मजबूत, विशेष रूप से बढ़ावा देना।
• निर्मित सुविधा चयन में। अतिरिक्त अप्रासंगिक विशेषता का कम उपयोग किया जाएगा ताकि बाद के रन पर उन्हें हटाया जा सके। निर्णय वृक्ष में विशेषताओं का पदानुक्रम विशेषताओं के महत्व को दर्शाता है। इसका मतलब है कि शीर्ष पर मौजूद सुविधाएं सबसे अधिक जानकारीपूर्ण हैं।
• निर्णय वृक्ष किसी भी बूलियन प्रकार्य का अनुमान लगा सकते हैं उदा. एकमात्र।

सीमाएं

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

कार्यान्वयन

कई डाटा माइनिंग सॉफ्टवेयर पैकेज एक या अधिक डिसीजन ट्री एल्गोरिदम के कार्यान्वयन प्रदान करते हैं।

उदाहरणों में शामिल

• सलफोर्ड सिस्टम्स कार्ट (जिसने मूल कार्ट लेखकों के मालिकाना कोड को लाइसेंस दिया था),
• एसपीएसएस मॉडलर,
• रैपिडमाइनर,
• एसएएस (सॉफ्टवेयर) # अवयव,
• Matlab,
• R (प्रोग्रामिंग लैंग्वेज) (सांख्यिकीय कंप्यूटिंग के लिए एक ओपन-सोर्स सॉफ्टवेयर वातावरण, जिसमें कई CART कार्यान्वयन जैसे rpart, पार्टी और रैंडमफॉरेस्ट पैकेज शामिल हैं),
• वीका (मशीन लर्निंग) (एक स्वतंत्र और ओपन-सोर्स डेटा-माइनिंग सूट, जिसमें कई निर्णय ट्री एल्गोरिदम शामिल हैं),
• ऑरेंज (सॉफ्टवेयर),
• नीम,
• माइक्रोसॉफ्ट एसक्यूएल सर्वर [1], और
• scikit-सीखें (पाइथन (प्रोग्रामिंग लैंग्वेज) प्रोग्रामिंग लैंग्वेज के लिए एक फ्री और ओपन-सोर्स मशीन लर्निंग लाइब्रेरी)।

एक्सटेंशन

निर्णय रेखांकन

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

वैकल्पिक खोज विधियाँ

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

यह भी देखें

• निर्णय-वृक्ष छंटाई
• बाइनरी निर्णय आरेख
• छेद
• भविष्य कहनेवाला विश्लेषण # वर्गीकरण और प्रतिगमन पेड़ .28CART.29
• ID3 एल्गोरिथम
• C4.5 एल्गोरिथम
• निर्णय स्टंप, उदाहरण के लिए उपयोग किया जाता है। ऐडाबूस्टिंग
• निर्णय सूची
• वृद्धिशील निर्णय वृक्ष
• वैकल्पिक निर्णय वृक्ष
• संरचित डेटा विश्लेषण (सांख्यिकी)
• लॉजिस्टिक मॉडल ट्री
• पदानुक्रमित क्लस्टरिंग

अग्रिम पठन

• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2017). "Tree-Based Methods" (PDF). An Introduction to Statistical Learning: with Applications in R. New York: Springer. pp. 303–336. ISBN 978-1-4614-7137-0.

इस पेज में लापता आंतरिक लिंक की सूची

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

बाहरी संबंध

• Evolutionary Learning of Decision Trees in C++
• A very detailed explanation of information gain as splitting criterion