ต้นไม้ตัดสินใจ
ขั้นตอนวิธีการสร้างต้นไม้การตัดสินใจ

ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี (อังกฤษ: algorithm) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ (อังกฤษ: greedy search) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย John Ross Quinlan ในปี 1986
เอนโทรปี (Entropy)
ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด (อังกฤษ: recursion) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain)
ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้
เมื่อ
S คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
p_{S}(j) คืออัตราส่วนของกรณีใน S ที่ตัวแปรตามหรือผลลัพธ์มีค่า j
โดยสำหรับต้นไม้การตัดสินใจที่มีผลลัพธ์เป็นแค่เพียงค่าตรรกะ (boolean) ใช่กับไม่ใช่เหมือนกับที่ยกมาตอนต้นของบทความนั้น จะมีเอนโทรปีคือ
เมื่อพิจารณาเอนโทรปีแล้วจะเห็นว่าเอนโทรปีจะมีค่าอยู่ระหว่าง 0 กับ 1 โดยจะมีค่าเป็นศูนย์เมื่อทุกๆกรณีมีผลลัพธ์เพียงแบบเดียว เช่น ใช่ทั้งหมด หรือ ไม่ใช่ทั้งหมด และจะมีค่ามากขึ้นเมื่อเริ่มมีค่าที่แตกต่างกันมากขึ้น หรือจะพูดอีกนัยหนึ่งก็คือเอนโทรปีจะมีค่ามากขึ้นหากข้อมูลไม่บริสุทธิ์ และจะตัดสินใจได้ว่าผลลัพธ์จะเป็นอะไรเมื่อเอนโทรปีเป็น 0 เท่านั้น
เกนความรู้ (Information Gain)
ซึ่งจากการนิยามเอนโทรปีข้างต้น ทำให้เราสามารถนิยามลักษณะของตัวแปรต้นที่ดีได้ โดยตัวแปร A จะเป็นตัวแปรต้นที่ดีก็ต่อเมื่อหากว่าแบ่งข้อมูลตัวอย่าง (Example) ออกเป็นชุดๆมีจำนวนชุดตามจำนวนค่าของ A ที่เป็นไปได้เพื่อให้แต่ละกรณี (Instance) ในชุดนั้นมีค่า A เพียงค่าเดียวและค่าเฉลี่ยของเอนโทรปีของชุดข้อมูลที่ถูกแบ่งออก (partition) มานั้นต่ำที่สุด เรียกค่าคาดหวังของการลดลงของเอนโทรปีหลังจากข้อมูลถูกแบ่งด้วย A ว่าเกนความรู้ของ A นิยามโดย
เมื่อ
S คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
E คือเอนโทรปีของตัวอย่าง
A คือตัวแปรต้นที่พิจารณา
value (A) คือเซตของค่าของ A ที่เป็นไปได้
S_{v} คือตัวอย่างที่ A มีค่า v ทั้งหมด
จะเห็นว่าหากเกนความรู้ของ A ยิ่งมากแสดงว่าหลังจากแบ่งตัวอย่าง S ด้วย A แล้วในแต่ละชุดที่แบ่งได้จะมี Entropy เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา
การใช้ ID3 สอนต้นไม้การตัดสินใจ
เมื่อเราสามารถบอกความดีของตัวแปรต้นได้จึงสามารถนำไปช่วยในการหาต้นไม้การตัดสินใจด้วย ID3 ได้โดยมีกระบวนการดังนี้
นำตัวแปรต้นที่ยังไม่ถูกนำมาใช้ทั้งหมดมาหาเกนความรู้
เลือกตัวที่มีเกนสูงที่สุด
สร้างต้นไม้ที่มีบัพรากเป็นของตัวแปรต้นตัวนั้น
นำมาเขียนเป็นรหัสเทียม (pseudo code) ได้ดังนี้ โดยยกตัวอย่างมาเฉพาะกรณีที่ตัวแปรตามมีแค่เพียงใช่กับไม่ใช่เท่านั้น
Examples คือตัวอย่างที่นำมาสอน
Target_Attribute คือตัวแปรตาม
Attribute คือตัวแปรต้น
ID3 (Examples, Target_Attribute, Attributes)
สร้างบัพซึ่งเป็นรากเปล่าๆสำหรับต้นไม้
ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นใช่
return รากที่มีค่า + (ใช่)
ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นไม่ใช่
return รากที่มีค่า - (ไม่ใช่)
ถ้าเซตของ Attribute เป็นเซตว่าง
return รากที่มีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
ถ้ามิฉะนั้น เริ่ม
A = ตัวแปรต้นที่มีค่าของเกนความรู้สูงที่สุด
ให้รากที่ค่าเป็น A
สำหรับแต่ละค่าที่เป็นไปได้, v_{i} , ของ A,
สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A =  v_{i}
สร้าง Examples ( v_{i}) เป็นสับเซตของ Example ที่ A มีค่า  v_{i}
ถ้า Examples ( v_{i} ) เป็นเซตว่าง
ต่อกิ่งนี้ด้วยบัพที่มีใบมีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
มิฉะนั้น ต่อกิ่งนี้ด้วย ID3 (Examples ( v_{i}), Target_Attribute, Attributes – {A})
จบ
Return ราก