วิธีสร้างต้นไม้ตัดสินใจ (Decision Tree) อย่างไร

ต้นไม้ตัดสินใจ (Decision Tree) เป็นกลไกแบบไหลผ่านคล้ายต้นไม้ (Flow-chart-like) ที่แต่ละโหนดภายใน (Internal Node) บ่งชี้การทดสอบบนแอตทริบิวต์ แต่ละกิ่ง (Branch) กำหนดผลลัพธ์ของการทดสอบ และโหนดใบ (Leaf Nodes) อธิบายคลาสหรือการกระจายคลาส โหนดที่ใหญ่ที่สุดในต้นไม้คือโหนดราก (Root Node)

ปัญหาการสร้างต้นไม้ตัดสินใจสามารถกำหนดได้แบบเรียกซ้ำ (Recursively) แรก เลือกแอตทริบิวต์เพื่อวางที่โหนดราก และสร้างกิ่งหนึ่งสำหรับแต่ละค่าที่เป็นไปได้ นี้แบ่งชุดตัวอย่างออกเป็นเซตย่อย หนึ่งสำหรับแต่ละค่าของแอตทริบิวต์ กระบวนการสามารถทำซ้ำได้แบบเรียกซ้ำสำหรับทุกกิ่ง โดยใช้เฉพาะอินสแตนซ์ที่ถึงกิ่งนั้น หากอินสแตนซ์บางส่วนที่โหนดมีการจำแนกประเภทเดียวกัน หยุดสร้างส่วนนั้นของต้นไม้

ขนาดความบริสุทธิ์ (Measure of Purity) ที่เราจะใช้เรียกว่าข้อมูล (Information) และวัดในหน่วยที่เรียกว่าบิต (Bits) เกี่ยวข้องกับแต่ละโหนดของต้นไม้ มันแทนจำนวนข้อมูลที่คาดว่าจะต้องการเพื่อระบุว่าอินสแตนซ์ใหม่ควรถูกจำแนกเป็นใช่หรือไม่ ถ้าอินสแตนซ์ถึงโหนดนั้น

การตัดแต่ง (Pruning)

การตัดแต่ง (Pruning) เป็นกระบวนการที่ลดขนาดของต้นไม้ตัดสินใจ ใช้เพื่อลดความเสี่ยงของการเรียนรู้เกิน (Overfitting) โดยการอธิบายขนาดของต้นไม้หรือกำจัดพื้นที่ของต้นไม้ที่ให้พลังน้อย การตัดแต่งให้ประโยชน์โดยการตัดกิ่งที่ตามมาจากความผิดปกติในข้อมูลฝึกอบรมเนื่องจากสัญญาณรบกวน (Noise) หรือค่าผิดปกติ (Outliers) และให้ต้นไม้เริ่มต้นในวิธีที่ปรับปรุงความมีประสิทธิภาพของการทำให้ทั่วไป (Generalization Effectiveness) ของต้นไม้

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

อัลกอริทึมสำหรับการเรียนรู้ต้นไม้ตัดสินใจ

อัลกอริทึม — สร้างต้นไม้ตัดสินใจจากข้อมูลฝึกอบรมที่กำหนด

อินพุต — ตัวอย่างฝึกอบรม ตัวอย่าง อธิบายโดยแอตทริบิวต์ค่าที่ไม่ต่อเนื่อง (Discrete-valued Attributes); เซตของแอตทริบิวต์นักเรียน (Students Attributes) attribute-list

เอาต์พุต — ต้นไม้ตัดสินใจ

วิธี

• สร้างโหนด N;
• หากตัวอย่างเป็นคลาสเดียวกัน C ดังนั้น
• คืนค่า N เป็นโหนดใบที่ติดฉลากด้วยคลาส C
• หาก attribute-list เป็น null แล้ว
• คืนค่า N เป็นโหนดใบที่ติดฉลากด้วยคลาสที่พบบ่อยที่สุดในตัวอย่าง // การลงคะแนนเสียงส่วนใหญ่ (Majority Voting)
• เลือก test-attribute แอตทริบิวต์ระหว่าง attribute-list ที่มีการเพิ่มข้อมูล (Information Gain) มากที่สุด
• ติดฉลากโหนด N ด้วย test attribute
• สำหรับค่าที่รู้จัก a_i ของ test-attribute // แบ่งพาร์ติชันตัวอย่าง
• เจริญกิ่งจากโหนด N สำหรับเงื่อนไข test-attribute = a_i
• ให้ s_i เป็นเซตของตัวอย่างในตัวอย่างที่ test-attribute = a_i
• หาก s_i ว่างเปล่า ดังนั้น
• สามารถเชื่อมโยงกับใบที่ติดฉลากด้วยคลาสที่พบบ่อยที่สุดในตัวอย่าง
• มิฉะนั้น แนบโหนดที่คืนค่าโดย Generate decision tree ( s_i, attribute-list - test-attribute)