การขุดข้อมูล - การเหนี่ยวนำโครงสร้างการตัดสินใจ

แผนผังการตัดสินใจคือโครงสร้างที่มีโหนดรากกิ่งก้านและโหนดใบ โหนดภายในแต่ละโหนดหมายถึงการทดสอบกับแอ็ตทริบิวต์แต่ละสาขาแสดงถึงผลลัพธ์ของการทดสอบและโหนดลีฟแต่ละโหนดมีเลเบลคลาส โหนดบนสุดในทรีคือโหนดราก

โครงสร้างการตัดสินใจต่อไปนี้ใช้สำหรับแนวคิด buy_computer ที่ระบุว่าลูกค้าใน บริษัท มีแนวโน้มที่จะซื้อคอมพิวเตอร์หรือไม่ แต่ละโหนดภายในแทนการทดสอบแอตทริบิวต์ แต่ละโหนดลีฟแสดงถึงคลาส

ประโยชน์ของการมีแผนผังการตัดสินใจมีดังนี้ -

ไม่จำเป็นต้องมีความรู้โดเมนใด ๆ
เป็นเรื่องง่ายที่จะเข้าใจ
ขั้นตอนการเรียนรู้และการจัดหมวดหมู่ของแผนผังการตัดสินใจนั้นง่ายและรวดเร็ว

ขั้นตอนวิธีการเหนี่ยวนำต้นไม้ตัดสินใจ

นักวิจัยเครื่องจักรชื่อ J.Ross Quinlan ในปีพ. ศ. 2523 ได้พัฒนาอัลกอริธึมแผนผังการตัดสินใจที่เรียกว่า 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;