การสร้าง Decision Tree (Decision Tree Induction)
Decision tree induction คือ การเรียนรู้ decision trees จากทูเพิลฝึกที่มีป้ายกำกับคลาส (class-labeled training tuples) Decision tree เป็นโครงสร้างต้นไม้แบบแผนภาพลำดับ (flowchart-like tree structure) ที่โหนดภายในแต่ละโหนด (internal node/non-leaf node) แสดงการทดสอบบนแอตทริบิวต์ แต่ละสาขาแสดงผลลัพธ์ของการทดสอบ และแต่ละโหนดใบ (leaf node/terminal node) แสดงป้ายกำกับคลาส (class label) โหนดบนสุดในต้นไม้คือ โหนดราก (root node)
มันนิยามแนวคิด buys computer (ซื้อคอมพิวเตอร์) คือ ทำนายว่าผู้ใช้ที่ AllElectronics มีแนวโน้มจะซื้อคอมพิวเตอร์หรือไม่ โหนดภายในแสดงด้วยสี่เหลี่ยมผืนผ้า และโหนดใบแสดงด้วยรูปวงรี มีอัลกอริทึม decision tree หลายตัวสร้างเฉพาะต้นไม้ไบนารี (binary trees) (ที่โหนดภายในแต่ละโหนดแยกสาขาไปยังโหนดอื่นอีกสองโหนดอย่างแม่นยำ) ในขณะที่บางตัวสามารถสร้างต้นไม้ที่ไม่ใช่ไบนารี (non-binary trees) ได้
เมื่อได้รับทูเพิล X ซึ่งป้ายกำกับคลาสที่เกี่ยวข้องไม่ทราบ ค่าแอตทริบิวต์ของทูเพิลจะถูกตรวจสอบกับ decision tree เส้นทางจะถูกติดตามจากรากไปยังโหนดใบ ซึ่งแสดงการทำนายคลาสสำหรับทูเพิลนั้น Decision trees สามารถเปลี่ยนเป็นกฎการจัดประเภท (classification rules) ได้
ข้อดีของ Decision Tree Classifiers
การพัฒนาไม่ต้องการความรู้โดเมน (domain knowledge) หรือการตั้งค่าพารามิเตอร์ (parameter setting) จึงเหมาะสำหรับการค้นพบความรู้เชิงสำรวจ (exploratory knowledge discovery)
จัดการข้อมูลมิติสูง (high dimensional data) ได้
คำอธิบายความรู้ที่ได้ในรูปต้นไม้ เข้าใจง่ายและมักเข้าใจง่ายโดยมนุษย์
ขั้นตอนการเรียนรู้และการจัดประเภท ง่ายและรวดเร็ว
โดยทั่วไปมีประสิทธิภาพดี แต่การใช้งานที่สำเร็จขึ้นอยู่กับข้อมูลที่มีอยู่
Decision tree induction algorithms ถูกใช้สำหรับการจัดประเภทในหลายพื้นที่應用 包括 醫學, 製造和生產, 金融分析, 天文學, 和 分子生物學. Decision trees เป็นพื้นฐานของระบบการนำกฎเชิงพาณิชย์หลายระบบ (commercial rule induction systems)
การตัดแต่งต้นไม้ (Tree Pruning)
ระหว่างการสร้างต้นไม้ Attribute selection measures ใช้เลือกแอตทริบิวต์ที่แบ่งพาร์ติชันทูเพิลออกเป็นคลาสต่างๆ ได้ดีที่สุด เมื่อสร้าง decision trees แล้ว บางสาขาอาจสะท้อน noise หรือ outliers ในระเบียนฝึก Tree pruning พยายามระบุและกำจัดสาขาเหล่านี้ เพื่อเพิ่มความแม่นยำในการจัดประเภทข้อมูลที่ไม่เคยเห็น (unseen data)
อัลกอริทึมหลัก
ID3, C4.5, และ CART ยอมรับวิธีการ greedy (non-backtracking) ที่สร้าง decision trees แบบ top-down recursive divide-and-conquer อัลกอริทึมหลายตัวสำหรับ decision tree induction ก็ปฏิบัติตามแนวทาง top-down ที่เริ่มจากชุดฝึกของทูเพิลและป้ายกำกับคลาสที่เกี่ยวข้อง ชุดฝึกถูกแบ่งแบบเวียนเกิด (recursively) เป็นเซตย่อยเล็กๆ ขณะที่ต้นไม้กำลังสร้าง
