ปลูกต้นไม้เพื่อการตัดสินใจ

เช่นเดียวกับโมเดลแมชชีนเลิร์นนิงที่มีการควบคุมดูแลทั้งหมด แผนภูมิการตัดสินใจได้รับการฝึกให้อธิบายชุดตัวอย่างการฝึกได้ดีที่สุด การฝึกอบรมแผนผังการตัดสินใจแบบเพิ่มประสิทธิภาพสูงสุดเป็นปัญหา NP-Hard ดังนั้น โดยทั่วไปการฝึกจะทําโดยใช้การหาค่าประมาณ ซึ่งเป็นอัลกอริทึมการเรียนรู้ที่สร้างได้ง่ายซึ่งให้แผนภูมิการตัดสินใจที่ไม่ใช่แบบที่ดีที่สุด แต่ใกล้เคียงกับแบบที่ดีที่สุด

อัลกอริทึมส่วนใหญ่ที่ใช้ฝึกแผนผังการตัดสินใจทํางานด้วยกลยุทธ์การแบ่งแยกและพิชิตแบบโลภ อัลกอริทึมเริ่มต้นด้วยการสร้างโหนดเดียว (รูท) และเติบโตเป็นต้นไม้การตัดสินใจแบบซ้ำซ้อนและโลภ

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

เช่น ในชุดข้อมูลนกเพนกวินแอดลี (ใช้สำหรับตัวอย่างโค้ดในภายหลังของหลักสูตรนี้) นกเพนกวินแอดลีและนกเพนกวินชินสแทรปส่วนใหญ่มีความยาวของปากมากกว่า 16 มม. ส่วนนกเพนกวินเจนตูส่วนใหญ่มีปากที่เล็กกว่า ดังนั้น เงื่อนไข bill_length_mm ≥ 16 จึงทําให้การคาดการณ์เกือบสมบูรณ์แบบสําหรับนกเพนกวิน Gentoo แต่ไม่สามารถแยกแยะระหว่างนกเพนกวิน Adelie กับนกเพนกวินชินสแทรป อัลกอริทึมอาจเลือกเงื่อนไขนี้

รูปที่ 7 ขั้นตอนแรกในการปลูกต้นไม้

 

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

อัลกอริทึมมีดังนี้

หมายเหตุ: คุณไม่จําเป็นต้องเขียนอัลกอริทึมนี้ เว้นแต่จะใช้คลัง Decision Forest ของคุณเอง

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 โหนด

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

รหัส YDF

ใน YDF ต้นไม้การตัดสินใจจะเติบโตขึ้นด้วยอัลกอริทึม "การแบ่งแยกและเอาชนะอย่างตะกลาม" ที่อธิบายไว้ข้างต้นโดยค่าเริ่มต้น หรือจะเปิดใช้การเติบโตทั่วโลกด้วยพารามิเตอร์ growing_strategy="BEST_FIRST_GLOBAL" ก็ได้ ดูรายละเอียดเพิ่มเติมใน เอกสารประกอบ

จำนวนเงื่อนไขที่เป็นไปได้ของโหนดหนึ่งๆ อาจมากมหาศาลหรือไม่มีขีดจำกัด ทั้งนี้ขึ้นอยู่กับจำนวนและประเภทของฟีเจอร์อินพุต ตัวอย่างเช่น เมื่อให้เงื่อนไขเกณฑ์เป็น $\mathrm{feature}_i \geq t$ การรวมค่าเกณฑ์ที่เป็นไปได้ทั้งหมดสําหรับ $t \in \mathbb{R}$ จะเป็นค่าอนันต์

รูทีนที่มีหน้าที่ค้นหาเงื่อนไขที่ดีที่สุดเรียกว่า splitter เนื่องจากต้องทดสอบเงื่อนไขที่เป็นไปได้จํานวนมาก ตัวแยกจึงเป็นจุดคอขวดเมื่อฝึกต้นไม้การตัดสินใจ

คะแนนสูงสุดที่ตัวแยกได้คือคะแนนที่ขึ้นอยู่กับงาน เช่น

• การได้ข้อมูลและ Gini (ทั้ง 2 รายการจะอธิบายในภายหลัง) มักใช้เพื่อการแยกประเภท
• ความคลาดเคลื่อนเฉลี่ยกำลังสองมักใช้กับการถดถอย

อัลกอริทึมตัวแบ่งมีหลายประเภท โดยแต่ละประเภทจะรองรับสิ่งต่อไปนี้แตกต่างกันไป

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

นอกจากนี้ ยังมีตัวแปรตัวแบ่งที่เทียบเท่ากันซึ่งมีข้อเสียแตกต่างกันไป ในแง่ของการใช้หน่วยความจํา การใช้ CPU การกระจายการประมวลผล และอื่นๆ

รหัส YDF

ใน YDF ระบบจะเลือกตัวแบ่งโดยนัยจากประเภทฟีเจอร์ ไฮเปอร์พารามิเตอร์ และความเร็วโดยประมาณของตัวแบ่งแต่ละรายการที่ตรวจพบโดยอัตโนมัติ (หรือระบุด้วยตนเอง) (ระหว่างการฝึก YDF จะเรียกใช้โมเดลขนาดเล็กเพื่อคาดการณ์ความเร็วของตัวแบ่งที่เป็นไปได้แต่ละรายการ)