डाटा माइनिंग - डिसीजन ट्री इंडक्शन

एक निर्णय पेड़ एक संरचना है जिसमें एक रूट नोड, शाखाएं, और पत्ती नोड्स शामिल हैं। प्रत्येक आंतरिक नोड एक विशेषता पर परीक्षण को दर्शाता है, प्रत्येक शाखा एक परीक्षण के परिणाम को दर्शाता है, और प्रत्येक पत्ती नोड एक कक्षा लेबल रखता है। पेड़ में सबसे ऊपरी नोड रूट नोड है।

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

निर्णय वृक्ष होने के लाभ इस प्रकार हैं -

इसके लिए किसी भी डोमेन ज्ञान की आवश्यकता नहीं है।
समझ लेना आसान है।
निर्णय वृक्ष के सीखने और वर्गीकरण के चरण सरल और तेज हैं।

निर्णय ट्री इंडक्शन एल्गोरिथम

1980 में जे। रॉस क्विनलान नामक एक मशीन शोधकर्ता ने एक निर्णय ट्री एल्गोरिथ्म विकसित किया जिसे ID3 (Iterative Dichotomiser) के नाम से जाना जाता है। बाद में, उन्होंने C4.5 प्रस्तुत किया, जो ID3 का उत्तराधिकारी था। ID3 और C4.5 एक लालची दृष्टिकोण अपनाते हैं। इस एल्गोरिथ्म में, कोई पीछे नहीं है; पेड़ों का निर्माण शीर्ष-नीचे पुनरावर्ती विभाजन और विजय तरीके से किया जाता है।

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

पेड़ की छँटाई

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