ต้นไม้การตัดสินใจคืออะไร?

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

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

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

ป้อนข้อมูล − ตัวอย่างการฝึกอบรม ตัวอย่าง อธิบายโดยคุณลักษณะที่แยกมูลค่า ชุดคุณลักษณะของนักเรียน คุณลักษณะ-รายการ

ผลผลิต − ต้นไม้ตัดสินใจ

วิธีการ

• สร้างโหนด N;

• หากตัวอย่างเป็นคลาสเดียวกันทั้งหมด C แล้ว

• ส่งคืน N เป็นโหนดปลายสุดที่มีคลาส C

• หากรายการแอตทริบิวต์เป็นโมฆะ

• ส่งคืน N เป็นโหนดปลายสุดที่ติดป้ายกำกับคลาสที่พบบ่อยที่สุดในตัวอย่าง // คะแนนเสียงข้างมาก

• เลือกแอตทริบิวต์การทดสอบ ซึ่งเป็นแอตทริบิวต์ในรายการแอตทริบิวต์ที่มีการรับข้อมูลสูงสุด

• ป้ายกำกับโหนด N พร้อมแอตทริบิวต์การทดสอบ

• สำหรับแต่ละค่าที่รู้จัก ai ของ test-attribute // แบ่งพาร์ติชั่นตัวอย่าง

• ขยายสาขาจากโหนด N สำหรับเงื่อนไข test-attribute=a_i .

• ให้ _i เป็นชุดของตัวอย่างในตัวอย่างที่ test-attribute=a_i .

• ถ้า si ว่างแล้ว

• มันสามารถเชื่อมใบไม้ที่ติดฉลากกับคลาสที่พบบ่อยที่สุดในตัวอย่างได้

• มิฉะนั้นจะแนบโหนดที่ส่งคืนโดยสร้างแผนผังการตัดสินใจ ( si,attribute-list - test-attribute)

การชักนำแผนภูมิการตัดสินใจ

ตัวอย่างเช่น การผลิตกฎการตัดสินใจโดยอัตโนมัติเรียกว่าการเหนี่ยวนำกฎหรือการเหนี่ยวนำกฎอัตโนมัติ สามารถสร้างกฎการตัดสินใจในการออกแบบโดยนัยของแผนผังการตัดสินใจซึ่งมักเรียกกันว่าการเหนี่ยวนำกฎ แต่จะมีการเลือกใช้เงื่อนไขการเหนี่ยวนำแผนภูมิหรือการเหนี่ยวนำแผนภูมิการตัดสินใจอย่างต่อเนื่อง

อัลกอริทึมพื้นฐานสำหรับการเหนี่ยวนำแผนผังการตัดสินใจคืออัลกอริธึมที่โลภ ใช้เพื่อสร้างแผนผังการตัดสินใจในลักษณะการแบ่งและพิชิตแบบเรียกซ้ำจากบนลงล่าง อัลกอริธึมพื้นฐานสำหรับการเรียนรู้แผนผังการตัดสินใจ คือรูปแบบของ ID3 ซึ่งเป็นอัลกอริธึมการเหนี่ยวนำแผนผังการตัดสินใจที่มีชื่อเสียง

วิธีการพื้นฐานมีดังนี้ −

• ต้นไม้เริ่มต้นเป็นโหนดแต่ละโหนดที่กำหนดตัวอย่างการฝึก

• หากตัวอย่างเป็นคลาสที่คล้ายกันทั้งหมด โหนดจะเปลี่ยนเป็นลีฟและมีป้ายกำกับว่าคลาสนั้น

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

• มีการสร้างแผนกขึ้นสำหรับค่าที่ทราบแต่ละค่าของแอตทริบิวต์การทดสอบ และกลุ่มตัวอย่างจะถูกแบ่งอย่างเหมาะสม

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