ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี (อังกฤษ: algorithm) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ (อังกฤษ: greedy search) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย John Ross Quinlan ในปี 1986

เอนโทรปี (Entropy)

ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด (อังกฤษ: recursion) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain)ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้

E ( S ) = − ∑ j = 1 n p S ( j ) log 2 ⁡ p S ( j ) {\displaystyle E(S)=-\sum _{j=1}^{n}p_{S}(j)\log _{2}p_{S}(j)}

เมื่อ

• S {\displaystyle S} คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
• p S ( j ) {\displaystyle p_{S}(j)} คืออัตราส่วนของกรณีใน S ที่ตัวแปรตามหรือผลลัพธ์มีค่า j

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

E ( S ) = − p y e s l o g 2 ( p y e s ) − p n o l o g 2 ( p n o ) {\displaystyle E(S)=-p_{yes}log_{2}(p_{yes})-p_{no}log_{2}(p_{no})}

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

เกนความรู้ (Information Gain)

ซึ่งจากการนิยามเอนโทรปีข้างต้น ทำให้เราสามารถนิยามลักษณะของตัวแปรต้นที่ดีได้ โดยตัวแปร A จะเป็นตัวแปรต้นที่ดีก็ต่อเมื่อหากว่าแบ่งข้อมูลตัวอย่าง (Example) ออกเป็นชุดๆมีจำนวนชุดตามจำนวนค่าของ A ที่เป็นไปได้เพื่อให้แต่ละกรณี (Instance) ในชุดนั้นมีค่า A เพียงค่าเดียวและค่าเฉลี่ยของเอนโทรปีของชุดข้อมูลที่ถูกแบ่งออก (partition) มานั้นต่ำที่สุด เรียกค่าคาดหวังของการลดลงของเอนโทรปีหลังจากข้อมูลถูกแบ่งด้วย A ว่าเกนความรู้ของ A นิยามโดย

G a i n ( S , A ) = E ( S ) − ∑ v = v a l u e ( A ) | S v | | S | E ( S v ) {\displaystyle Gain(S,A)=E(S)-\sum _{v=value(A)}{\frac {|S_{v}|}{|S|}}E(S_{v})}

เมื่อ

• S {\displaystyle S} คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
• E {\displaystyle E} คือเอนโทรปีของตัวอย่าง
• A {\displaystyle A} คือตัวแปรต้นที่พิจารณา
• value (A) คือเซตของค่าของ A ที่เป็นไปได้
• S v {\displaystyle S_{v}} คือตัวอย่างที่ A มีค่า v ทั้งหมด

จะเห็นว่าหากเกนความรู้ของ A ยิ่งมากแสดงว่าหลังจากแบ่งตัวอย่าง S ด้วย A แล้วในแต่ละชุดที่แบ่งได้จะมี Entropy เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา

การใช้ ID3 สอนต้นไม้การตัดสินใจ

เมื่อเราสามารถบอกความดีของตัวแปรต้นได้จึงสามารถนำไปช่วยในการหาต้นไม้การตัดสินใจด้วย ID3 ได้โดยมีกระบวนการดังนี้

1. นำตัวแปรต้นที่ยังไม่ถูกนำมาใช้ทั้งหมดมาหาเกนความรู้
2. เลือกตัวที่มีเกนสูงที่สุด
3. สร้างต้นไม้ที่มีบัพรากเป็นของตัวแปรต้นตัวนั้น

นำมาเขียนเป็นรหัสเทียม (pseudo code) ได้ดังนี้ โดยยกตัวอย่างมาเฉพาะกรณีที่ตัวแปรตามมีแค่เพียงใช่กับไม่ใช่เท่านั้น

---

• Examples คือตัวอย่างที่นำมาสอน
• Target_Attribute คือตัวแปรตาม
• Attribute คือตัวแปรต้น

ID3 (Examples, Target_Attribute, Attributes)

• สร้างบัพซึ่งเป็นรากเปล่าๆสำหรับต้นไม้
• ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นใช่
  • return รากที่มีค่า + (ใช่)
• ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นไม่ใช่
  • return รากที่มีค่า - (ไม่ใช่)
• ถ้าเซตของ Attribute เป็นเซตว่าง
  • return รากที่มีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
• ถ้ามิฉะนั้น เริ่ม
  • A = ตัวแปรต้นที่มีค่าของเกนความรู้สูงที่สุด
  • ให้รากที่ค่าเป็น A
  • สำหรับแต่ละค่าที่เป็นไปได้, v i {\displaystyle v_{i}} , ของ A,
    • สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A = v i {\displaystyle v_{i}}
    • สร้าง Examples ( v i {\displaystyle v_{i}} ) เป็นสับเซตของ Example ที่ A มีค่า v i {\displaystyle v_{i}}
    • ถ้า Examples ( v i {\displaystyle v_{i}} ) เป็นเซตว่าง
      • ต่อกิ่งนี้ด้วยบัพที่มีใบมีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
    • มิฉะนั้น ต่อกิ่งนี้ด้วย ID3 (Examples ( v i {\displaystyle v_{i}} ), Target_Attribute, Attributes – {A})
• จบ
• Return ราก