Decision Tree (ต้นไม้ตัดสินใจ) เป็นโครงสร้างแบบไหลงาน (flow-chart-like tree structure) ที่แต่ละโหนดภายใน (internal node) แสดงการทดสอบบนแอตทริบิวต์ (attribute) แต่ละกิ่ง (branch) แสดงผลลัพธ์ของการทดสอบ และโหนดใบ (leaf nodes) แสดงคลาสหรือการกระจายของคลาส โหนดสูงสุดในต้นไม้คือโหนดราก (root node)
อัลกอริทึมสำหรับการเรียนรู้ Decision Trees
อัลกอริทึม − สร้าง Decision Tree จากข้อมูลฝึกอบรม (training data) ที่ให้มา
Input − ตัวอย่างฝึกอบรม (training samples) ที่อธิบายด้วยแอตทริบิวต์ที่เป็นค่าต่อเนื่อง (discrete-valued attributes); เซตของแอตทริบิวต์ (attribute-list)
Output − Decision Tree
วิธีการ (Method)
สร้างโหนด N;
ถ้าตัวอย่างทั้งหมดเป็นคลาสเดียวกัน C แล้ว
คืนค่า N เป็นโหนดใบที่ติดฉลากด้วยคลาส C
ถ้า attribute-list เป็น null แล้ว
คืนค่า N เป็นโหนดใบที่ติดฉลากด้วยคลาสที่พบมากที่สุดในตัวอย่าง (majority voting)
เลือก test-attribute คือแอตทริบิวต์จาก attribute-list ที่มี information gain สูงสุด
ติดฉลากโหนด N ด้วย test attribute
สำหรับค่าที่รู้จักแต่ละค่า ai ของ test-attribute // แยกตัวอย่าง (partition the samples)
สร้างกิ่งจากโหนด N สำหรับเงื่อนไข test-attribute = ai
ให้ si เป็นเซตของตัวอย่างใน samples ที่ test-attribute = ai
ถ้า si ว่างเปล่า แล้ว
เชื่อมโหนดใบที่ติดฉลากด้วยคลาสที่พบมากที่สุดในตัวอย่าง
มิฉะนั้น ให้เชื่อมโหนดที่คืนค่าจาก Generate decision tree (si, attribute-list - test-attribute)
Decision Tree Induction (การ 유도 ต้นไม้ตัดสินใจ)
การสร้างกฎตัดสินใจ (decision rules) โดยอัตโนมัติเรียกว่า Rule Induction หรือ Automatic Rule Induction การสร้างกฎตัดสินใจในรูปแบบ Decision Tree ก็มักเรียกว่า Tree Induction หรือ Decision Tree Induction
อัลกอริทึมพื้นฐานสำหรับ Decision Tree Induction เป็น Greedy Algorithm ใช้สร้าง Decision Tree แบบ Top-down recursive divide-and-conquer อัลกอริทึมพื้นฐานสำหรับการเรียนรู้ Decision Tree เป็นรูปแบบหนึ่งของ ID3 ซึ่งเป็นอัลกอริทึม Decision Tree Induction ที่มีชื่อเสียง
วิธีการพื้นฐานมีดังนี้ −
ต้นไม้เริ่มต้นเป็นโหนดเดียวที่แทนตัวอย่างฝึกอบรม
ถ้าตัวอย่างทั้งหมดเป็นคลาสเดียวกัน โหนดจะกลายเป็นโหนดใบและติดฉลากด้วยคลาสนั้น
อัลกอริทึมใช้การวัดแบบเอนโทรปี (entropy-based measure) ที่เรียกว่า Information Gain เป็น heuristic สำหรับเลือกแอตทริบิวต์ที่จะแบ่งตัวอย่างให้เป็นคลาสเดี่ยว แอตทริบิวต์นี้จะกลายเป็น "test" หรือ "decision" attribute ที่โหนด ในรูปแบบนี้ ทุกแอตทริบิวต์เป็น categorical (discrete-valued) แอตทริบิวต์ต่อเนื่อง (continuous-valued) ควรทำให้เป็น discrete
สร้างกิ่งสำหรับค่าที่รู้จักแต่ละค่าของ test attribute และแบ่งตัวอย่างตามเหมาะสม
อัลกอริทึมใช้กระบวนการซ้ำ (recursive) เพื่อสร้าง Decision Tree สำหรับตัวอย่างที่แต่ละการแบ่ง เนื่องจากแอตทริบิวต์ปรากฏที่โหนดแล้ว จึงไม่ควรพิจารณาใน descendants ของโหนดนั้นอีก
