แผนผังการตัดสินใจจะได้รับการฝึกให้อธิบายชุดตัวอย่างการฝึกได้อย่างดีที่สุด เช่นเดียวกับโมเดลแมชชีนเลิร์นนิงที่มีการควบคุมดูแลทั้งหมด การฝึกที่ดีที่สุดสำหรับแผนผังการตัดสินใจ เป็นปัญหาหนักด้านขั้วโลก ดังนั้น โดยปกติการฝึกจะดำเนินไปโดยใช้การเรียนรู้แบบคาดเดา ซึ่งเป็นอัลกอริทึมการเรียนรู้ ที่สร้างไม่ยาก ซึ่งให้โครงสร้างการตัดสินใจที่มีประสิทธิภาพที่สุด
อัลกอริทึมส่วนใหญ่ที่ใช้ฝึกต้นไม้การตัดสินใจนั้นทำงานร่วมกับกลยุทธ์การแบ่งแยกอย่างละโมบและเอาชนะ อัลกอริทึมนี้จะเริ่มต้นโดยการสร้างโหนดเดียว (ราก) และขยายโครงสร้างการตัดสินใจอย่างค่อยเป็นค่อยไปและค่อยๆ เติบโต
ในแต่ละโหนด ระบบจะประเมินและให้คะแนนเงื่อนไขที่เป็นไปได้ทั้งหมด อัลกอริทึมจะเลือกเงื่อนไข "ดีที่สุด" ซึ่งก็คือเงื่อนไขที่มีคะแนนสูงสุด ในตอนนี้โปรดทราบว่าคะแนนเป็นเมตริกที่สัมพันธ์กับงาน และระบบจะเลือกเงื่อนไขเพื่อใช้เมตริกดังกล่าวให้เกิดประโยชน์สูงสุด
เช่น ในชุดข้อมูล Palmer Penguins (ใช้สำหรับตัวอย่างโค้ดในช่วงท้ายของหลักสูตรนี้) เพนกวิน Adelie และ Chinstrap ส่วนใหญ่มีความยาวบิลมากกว่า 16 มม. และเพนกวิน Gentoo ส่วนใหญ่จะมีบิลน้อยกว่า ดังนั้น เงื่อนไข bill_length_mm ≥ 16 จึงเป็นการคาดคะเนที่เกือบสมบูรณ์สำหรับ เพนกวิน Gentoo แต่ไม่สามารถแยกความแตกต่างระหว่าง Adelies กับ Chinstraps ได้ อัลกอริทึมอาจจะเลือกเงื่อนไขนี้
รูปที่ 7 ขั้นตอนแรกในการปลูกต้นไม้
จากนั้นอัลกอริทึมจะทำซ้ำแบบอิสระและต่อเนื่องกันในโหนดย่อยทั้ง 2 โหนด เมื่อไม่พบเงื่อนไขที่ตรงกัน โหนดจะกลายเป็น Leaf การคาดคะเน 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}$ จะเป็นอนันต์
กิจวัตรที่มีหน้าที่ค้นหาสภาวะที่ดีที่สุดเรียกว่าสปลิตเตอร์ เนื่องจากต้องทดสอบเงื่อนไขที่เป็นไปได้จำนวนมาก ตัวแยกจึงเป็นจุดคอขวดเมื่อฝึกโครงสร้างการตัดสินใจ
คะแนนที่ได้จากตัวแยกคะแนนสูงสุดจะขึ้นอยู่กับงาน เช่น
- ข้อมูลที่ได้รับและ Gini (ทั้ง 2 อย่างนี้กล่าวถึงในภายหลัง) มักนำมาใช้ในการแยกประเภท
- ค่าเฉลี่ยความคลาดเคลื่อนกำลังสองมักใช้สำหรับการถดถอย
อัลกอริทึมการแยกมีอัลกอริทึมของตัวแยกมากมายที่มีการสนับสนุนที่แตกต่างกันสำหรับ:
- ประเภทของฟีเจอร์ เช่น ตัวเลข หมวดหมู่ ข้อความ
- งาน เช่น การจำแนกประเภทไบนารี การจัดประเภทแบบหลายคลาส การถดถอย
- ประเภทของเงื่อนไข เช่น เงื่อนไขเกณฑ์ เงื่อนไขที่ระบุ เงื่อนไขแบบเอียง
- เกณฑ์การกำหนดปกติ เช่น ตัวแยกแบบตรงหรือโดยประมาณสำหรับเงื่อนไขของเกณฑ์
นอกจากนี้ยังมีตัวแปรของตัวแยกที่เทียบเท่าซึ่งมีข้อดีข้อเสียแตกต่างกันไป ไม่ว่าจะเป็นการใช้งานหน่วยความจำ การใช้งาน CPU การกระจายการคำนวณ และอื่นๆ