เทคนิค Decision Tree เป็นเทคนิคหนึ่งที่ได้รับความนิยมในการนำมาประยุกต์ใชัในงานด้าน data mining วันนี้ผมจะแนะนำการสร้างโมเดล decision tree แบบง่ายๆ ก่อนอื่นเราจะใช้ข้อมูลในตารางที่ 1 ซึ่งเป็นข้อมูลที่เก็บสภาพภูมิอากาศ 14 วันย้อนหลังเพื่อดูว่าจะมีการจัดแข่งขันกีฬาหรือไม่
ตารางที่ 1 แสดงข้อมูล weather
จากข้อมูลในตารางที่ 1 ประกอบด้วย 5 แอตทริบิวต์ คือ
- outlook แสดงสภาพภูมิอากาศ ประกอบด้วย 3 ค่า คือ sunny, overcast, rainny
- temperature แสดงอุณหภูมิ ประกอบด้วย 3 ค่า คือ hot, mild, cool
- humidity แสดงค่าความชื้นในอากาศ ประกอบด้วย 2 ค่า คือ high, normal
- windy แสดงว่าเป็นวันที่ลมแรงหรือไม่ ประกอบด้วย 2 ค่า คือ TRUE, FALSE
- play แสดงการจัดแข่งขันกีฬา ซึ่งเป็นคลาส ประกอบด้วย 2 ค่า คือ yes, no
การสร้างโมเดล decision tree จะทำการคัดเลือกแอตทริบิวต์ที่มีความสัมพันธ์กับคลาสมากที่สุดขึ้นมาเป็นโหนดบนสุดของ tree (root node) หลังจากนั้นก็จะหาแอตทริบิวต์ถัดไปเรื่อยๆ ในการหาความสัมพันธ์ของแอตทริบิวต์นี้จะใช้ตัววัด ที่เรียกว่า Information Gain (IG) ค่านี้คำนวณได้จากสมการดังนี้
IG (parent, child) = entropy(parent) – [p(c1) × entropy(c1) + p(c2) × entropy(c2) + …]
โดยที่ entropy(c1) = -p(c1) log2 p(c1) และ p(c1) คือ ค่าความน่าจะเป็นของ c1
ต่อไปเราจะลองคำนวณค่าแต่ละแอตทริบิวต์เทียบกับคลาสเพื่อหาแอตทริบิวต์ที่มีค่า IG มากที่สุดมาเป็น root ของ decision tree ดังนี้ครับ
1. คำนวณค่า IG ของแอตทริบิวต์ outlook เพื่อให้ดูง่ายขึ้นผมจะแสดงให้เป็นภาพดังในรูปที่ 1
รูปที่ 1 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ outlook
จากรูปที่ 1 สามารถคำนวณค่า IG ได้ดังนี้
entropy (parent) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.64 × log2(0.64) + 0.36 × log2(0.36)]
= -[0.64 × -0.64 + 0.36 × -1.47]
= 0.94
entropy(outlook = sunny) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.4 × log2(0.4) + 0.6 × log2(0.6)]
= -[0.4 × -1.32 + 0.6 × -0.74]
= 0.97
entropy(outlook = overcast) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[1.0 × log2(1.0) + 0 × log2(0)]
= -[1.0 × 0 + 0 × 1]
= 0
entropy(outlook = rainy) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.6 × log2(0.6) + 0.4 × log2(0.4)]
= -[0.6 × -0.74 + 0.4 × -1.32]
= 0.97
IG(parent, child) = entropy (parent) –
[p(outlook = sunny) × entropy(outlook = sunny)+
p(outlook = overcast) × entropy(outlook = overcast)+
p(outlook = rainy) × entropy(outlook = rainy)]
= 0.94 – [0.35 × 0.97 + 0.30 × 0 + 0.35 × 0.97]
= 0.94 – 0.68
= 0.26
รูปที่ 2 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ temperature
จากรูปที่ 2 สามารถคำนวณค่า IG ได้ดังนี้
entropy(temperature = cool) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.75 × log2(0.75) + 0.25 × log2(0.25)]
= 0.81
entropy(temperature = hot) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.5 × log2(0.5) + 0.5× log2(0.5)]
= 1
entropy(temperature = mild) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.67 × log2(0.67) + 0.33 × log2(0.33)]
= 0.91
IG(parent, child) = entropy (parent) –
[p(temperature = cool) × entropy(temperature = cool)+
p(temperature = hot) × entropy(temperature = hot)+
p(temperature = mild) × entropy(temperature = mild)]
= 0.94 – [0.29 × 0.81 + 0.29 × 1 + 0.42 × 0.91]
= 0.94 – 0.91
= 0.03
3. คำนวณค่า IG ของแอตทริบิวต์ humidiy ดังในรูปที่ 3
รูปที่ 3 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ humidity
จากรูปที่ 3 สามารถคำนวณค่า IG ได้ดังนี้
entropy(humidity = high) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.43 × log2(0.43) + 0.57 × log2(0.57)]
= 0.99
entropy(humidity = normal) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.86 × log2(0.86) + 0.14 × log2(0.14)]
= 0.58
IG(parent, child) = entropy (parent) –
[p(humidity = cool) × entropy(humidity = cool)+
p(humidity = hot) × entropy(humidity = hot)]
= 0.94-[0.5 × 0.99 + 0.5 × 0.58]
= 0.94 – 0.79
= 0.15
4. คำนวณค่า IG ของแอตทริบิวต์ windy ดังในรูปที่ 4
รูปที่ 4 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ windy
จากรูปที่ 4 สามารถคำนวณค่า IG ได้ดังนี้
entropy(windy = FALSE) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.75 × log2(0.75) + 0.25 × log2(0.25)]
= 0.81
entropy(windy = TRUE) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.5 × log2(0.5) + 0.5 × log2(0.5)]
= 1
IG(parent, child) = entropy (parent) –
[p(windy = FALSE) × entropy(windy = FALSE)+
p(windy = TRUE) × entropy(windy = TRUE)]
= 0.94-[0.57 × 0.81 + 0.43 × 1]
= 0.94 – 0.89
= 0.05
5. จากการคำนวณค่า IG ของทุกแอตทริบิวต์พบว่าค่า IG ของแอตทริบิวต์ outlook มีค่ามากที่สุด (0.28) ดังนั้นจึงเลือกแอตทริบิวต์ outlook ขึ้นมาเป็นโหนด root ณ ขั้นนี้เราจะเห็นว่าข้อมูลที่อยู่ในโหนดที่แอตทริบิวต์ outlook = overcast มีคลาสเดียวกันหมดคือ play = yes ดังนั้นโหนดนี้ไม่ต้องทำการแตกกิ่งต่อไปอีกแล้ว แต่โหนดอื่นๆ จะต้องทำการแตกกิ่งออกไปจนข้อมูลในแต่ละโหนดมีคลาสคำตอบเดียวกันแล้ว ผมจะขอยกตัวอย่างการแตกกิ่งออกจากโหนดที่มีแอตทริบิวต์ outlook = sunny ดังแสดงในรูปที่ 5
รูปที่ 5 แสดง decision tree เมื่อแตกกิ่งโดยใช้แอตทริบิวต์ humidity
จากรูปที่ 5 จะเห็นได้ว่าข้อมูลที่อยู่ในโหนด outlook = sunny และ humidity = high มีคลาสเป็น no และ ข้อมูลที่อยู่ในโหนด outlook = sunny และ humidity = normal มีคลาสเป็น yes เมื่อเป็นแบบนี้แล้วก็แสดงว่าสามารถหยุดทำการแตกกิ่งต่อจากโหนดเหล่านี้ได้ แต่เพื่อให้เข้าใจการคำนวณค่า IG สำหรับโหนดในชั้นถัดไปผมจะแสดงวิธีการคำนวณให้ดูดังนี้
จากรูปที่ 5 สามารถคำนวณค่า IG ได้ดังนี้
entropy (parent) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.4 × log2(0.4) + 0.6 × log2(0.6)]
= 0.97
entropy(outlook = sunny & humidity = high) = -p(Play=yes) × log2 p(Play=yes) +
-p(Play=no) × log2 p(Play=no)
= -[0.0 × log2(0.0) + 1.0 × log2(1.0)]
= 0
entropy(outlook = sunny & humidity = normal) = -p(Play=yes) × log2 p(Play=yes)
+ -p(Play=no) × log2 p(Play=no)
= -[1.0 × log2(1.0) + 0.0 × log2(0.0)]
= 0
IG(parent, child) = entropy (parent) –
[p(outlook = sunny & humidity = high) ×
entropy(outlook = sunny & humidity = high)+
p(outlook = sunny & humidity = normal) ×
entropy(outlook = sunny & humidity = normal)]
= 0.97-[0.60 × 0.0 + 0.40 × 0.0]
= 0.97 – 0.0
= 0.97
ทั้งหมดนี้คือขั้นตอนการสร้างโมเดล decision tree ซึ่งข้อดีของโมเดลนี้มีดังนี้
- เป็นโมเดลที่เข้าใจง่าย สามารถแปลความจากโมเดลได้เลย เช่น ถ้าวันไหนที่สภาพอากาศเป็นแบบ outlook แล้วจะมีการจัดแข่งขันกีฬา
- โมเดลที่สร้างได้คัดเลือกแอตทริบิวต์ที่มีความสัมพันธ์กับคลาสคำตอบมาแล้ว ดังนั้นอาจจะไม่ได้ใช้ทุกแอตทริบิวต์ในข้อมูล training
ในปัจจุบันนี้เราสามารถใช้ซอฟต์แวร์ทางด้าน Data Mining เช่น RapidMiner Studio 9 เพื่อสร้างโมเดล decision tree ได้อย่างง่ายๆ แถมสามารถแสดงโมเดลให้เป็นรูปแบบที่สวยงามได้อีกด้วยดังแสดงในรูปที่ 6
รูปที่ 6 แสดงโมเดล decision tree จากซอฟต์แวร์ RapidMiner Studio 9
ถ้าท่านใดสนใจอบรมการวิเคราะห์ข้อมูลด้วยเทคนิค Data Mining และ RapidMiner Studio 6 สามารถเข้าร่วมอบรมกับทางเราได้ครับ รายละเอียดเพิ่มเติมดูได้จาก “หลักสูตรการวิเคราะห์ข้อมูลด้วยเทคนิค Data Mining โดยซอฟต์แวร์ RapidMiner Studio 9 (ขั้นพื้นฐานและปานกลาง) รุ่นที่ 37 (ปี 2563)“
เอกสารอ้างอิง
- Foster Provost and Tom Fawcett, Data Science for Business, O’ REILLY 2013