ต้นไม้การตัดสินใจได้รับการฝึกให้ดีที่สุด เช่นเดียวกับโมเดลแมชชีนเลิร์นนิงที่มีการควบคุมดูแลทั้งหมด อธิบายชุดตัวอย่างการฝึก การฝึกที่มีประสิทธิภาพสูงสุดของแผนผังการตัดสินใจคือ ปัญหา NP ได้ยาก ดังนั้น โดยทั่วไปการฝึกจะทำโดยใช้การประเมินพฤติกรรม อัลกอริทึมการเรียนรู้ที่สร้างได้ง่าย มอบคุณลักษณะที่ไม่ใช่ผลลัพธ์ที่ดีที่สุด ที่ดีที่สุด นั่นคือแผนผังการตัดสินใจ
อัลกอริทึมส่วนใหญ่ที่ใช้ในการฝึกแผนผังการตัดสินใจจะทำงานกับการแบ่งอย่างโล่งและ พิชิตกลยุทธ์ อัลกอริทึมจะเริ่มต้นด้วยการสร้างโหนดเดียว (ราก) และ ทำให้แผนผังการตัดสินใจเติบโตซ้ำๆ และละโมบ
ในแต่ละโหนด เงื่อนไขที่เป็นไปได้ทั้งหมดจะได้รับการประเมินและให้คะแนน อัลกอริทึมจะเลือกมาตรฐานที่ "ดีที่สุด" ซึ่งก็คือเงื่อนไขที่มี คุณภาพ ในตอนนี้ โปรดทราบว่าคะแนนคือเมตริกที่สัมพันธ์กับ งาน และเงื่อนไขแต่ละรายการเพื่อเพิ่มเมตริกนั้นให้สูงสุด
ตัวอย่างเช่น ใน Palmer เพนกวิน ชุดข้อมูล (ใช้สำหรับตัวอย่างโค้ดภายหลังในหลักสูตรนี้) Adelie และ Chinstrap ส่วนใหญ่ เพนกวินมีความยาวของบิลตัวมากกว่า 16 มม. ในขณะที่เพนกวินส่วนใหญ่ของเจนทู เพนกวินมีบิลน้อยกว่า ดังนั้น เงื่อนไข bill_length_mm ≥ 16 ทำนายได้เกือบสมบูรณ์แบบสำหรับ เพนกวินเจนทู แต่แยกความแตกต่างไม่ได้ ระหว่าง Adelies และ Chinstraps อัลกอริทึมอาจเลือกเงื่อนไขนี้
รูปที่ 7 ขั้นตอนแรกในการปลูกต้นไม้
จากนั้นอัลกอริทึมจะทำงานซ้ำแบบวนซ้ำและอิสระบนโหนดย่อยทั้งสอง เมื่อไม่พบเงื่อนไขที่น่าพอใจ โหนดจะกลายเป็น Leaf ใบไม้ การคาดคะเนได้รับการกำหนดค่าเป็นค่าป้ายกำกับตัวแทนที่ดีที่สุดในตัวอย่าง
โดยมีอัลกอริทึมดังนี้
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
เรามาดูขั้นตอนต่างๆ ของการฝึกแผนผังการตัดสินใจหนึ่งๆ กันใน รายละเอียดเพิ่มเติม
ขั้นตอนที่ 1: สร้างรูท
ขั้นตอนที่ 2: ขยายโหนด #1 เงื่อนไข "x1 ≥ 1" พบแล้ว สร้างโหนดย่อย 2 โหนดดังนี้
ขั้นตอนที่ 3: ขยายโหนด #2 ไม่พบเงื่อนไขที่พึงพอใจ ดังนั้น ทำให้โหนด เป็นใบไม้:
ขั้นตอนที่ 4: ขยายโหนด #3 เงื่อนไข "x2 ≥ 0.5" พบแล้ว เด็ก 2 คน ขึ้น
นอกจากนี้ยังมีวิธีอื่นๆ ในการปลูกแผนผังการตัดสินใจ อีกทางเลือกหนึ่งที่ได้รับความนิยมคือ เพิ่มประสิทธิภาพโหนดได้ทั่วโลกแทนการใช้กลยุทธ์การแบ่งแยกและเอาชนะ
growing_strategy="BEST_FIRST_GLOBAL"
โปรดดู
ได้ในเอกสารประกอบ เพื่อดูรายละเอียดเพิ่มเติม
จำนวนและประเภทของคุณลักษณะการป้อนข้อมูล เงื่อนไขที่เป็นไปได้สำหรับโหนดหนึ่งๆ อาจมีขนาดใหญ่มาก โดยทั่วไปไม่มีที่สิ้นสุด ตัวอย่างเช่น เมื่อระบุเงื่อนไขเกณฑ์ $\mathrm{feature}_i \geq t$, โดยใช้ ที่เป็นไปได้ ค่าเกณฑ์สำหรับ $t \in \mathbb{R}$ เป็นอนันต์
กิจวัตรที่มีหน้าที่ในการค้นหาสภาพที่ดีที่สุดเรียกว่า splitter เนื่องจากต้องทดสอบเงื่อนไขต่างๆ ที่อาจเกิดขึ้น ตัวแยกสัญญาณ เป็นจุดคอขวดเมื่อฝึกแผนผังการตัดสินใจ
คะแนนที่เพิ่มขึ้นจากตัวแยกจะขึ้นอยู่กับงานนั้นๆ สำหรับ ตัวอย่าง:
- การได้ข้อมูล และ Gini (ทั้งคู่ ซึ่งจะกล่าวถึงในภายหลัง) มักจะใช้ในการจำแนกประเภท
- ความคลาดเคลื่อนกำลังสองเฉลี่ยมักใช้กับการถดถอย
มีอัลกอริทึมตัวแยกจำนวนมาก ซึ่งแต่ละแบบรองรับสิ่งต่อไปนี้
- ประเภทของสถานที่ ตัวอย่างเช่น ตัวเลข หมวดหมู่ ข้อความ
- งาน ตัวอย่างเช่น การจัดประเภทแบบไบนารี แบบหลายคลาส การจำแนกประเภท, การถดถอย
- ประเภทของเงื่อนไข เช่น เงื่อนไขเกณฑ์ เงื่อนไขในชุด เงื่อนไขเอียง
- เกณฑ์การกำหนดมาตรฐาน เช่น ตัวแยกที่แน่นอนหรือค่าโดยประมาณ สําหรับเงื่อนไขของเกณฑ์
นอกจากนี้ยังมีตัวแปรตัวแยกที่เทียบเท่ากันซึ่งมีข้อเสียต่างกัน เกี่ยวกับการใช้งานหน่วยความจำ การใช้ CPU การกระจายการคำนวณ และอื่นๆ