ขั้นตอนการสร้างโมเดล Decision Tree

[บทความนี้เป็นเนื้อหาบางส่วนจากหนังสือ An Introduction to Data Mining Techniques (ฉบับภาษาไทย]
เทคนิค Decision Tree เป็นเทคนิคหนึ่งที่ได้รับความนิยมในการนำมาประยุกต์ใชัในงานด้าน data mining วันนี้ผมจะแนะนำการสร้างโมเดล decision tree แบบง่ายๆ ก่อนอื่นเราจะใช้ข้อมูลในตารางที่ 1 ซึ่งเป็นข้อมูลที่เก็บสภาพภูมิอากาศ 14 วันย้อนหลังเพื่อดูว่าจะมีการจัดแข่งขันกีฬาหรือไม่

ตารางที่ 1 แสดงข้อมูล weather

Nooutlooktemperaturehumiditywindyplay
1sunnyhothighFALSEno
2sunnyhothighTRUEno
3overcasthothighFALSEyes
4rainymildhighFALSEyes
5rainycoolnormalFALSEyes
6rainycoolnormalTRUEno
7overcastcoolnormalTRUEyes
8sunnymildhighFALSEno
9sunnymildnormalFALSEyes
10rainymildnormalFALSEyes
11sunnymildnormalTRUEyes
12overcastmildhighTRUEyes
13overcasthotnormalFALSEyes
14rainymildhighTRUEno

จากข้อมูลในตารางที่ 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) log p(c1) และ p(c1) คือ ค่าความน่าจะเป็นของ c1

ต่อไปเราจะลองคำนวณค่าแต่ละแอตทริบิวต์เทียบกับคลาสเพื่อหาแอตทริบิวต์ที่มีค่า IG มากที่สุดมาเป็น root ของ decision tree ดังนี้ครับ

1. คำนวณค่า IG ของแอตทริบิวต์ outlook เพื่อให้ดูง่ายขึ้นผมจะแสดงให้เป็นภาพดังในรูปที่ 1

Screen Shot 2557-03-17 at 7.10.21 AM

รูปที่ 1 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ outlook

จากรูปที่ 1 สามารถคำนวณค่า IG ได้ดังนี้
entropy (parent) = -p() × logp() – p() × logp()
= -[0.64 × log2(0.64) + 0.36 × log2(0.36)]
= -[0.64 × -0.64 + 0.36 × -1.47]
= 0.94
entropy(outlook = sunny) = -p() × logp() – p() × logp()

= -[0.4 × log2(0.4) + 0.6 × log2(0.6)]
= -[0.4 × -1.32 + 0.6 × -0.74]
= 0.97

entropy(outlook = overcast) = -p() × logp() – p() × logp()
= -[1.0 × log2(1.0) + 0 × log2(0)]
= -[1.0 × 0 + 0 × 1]
= 0

entropy(outlook = rainy) = -p() × logp() – p() × logp()
= -[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.96 – 0.68
= 0.28

2. คำนวณค่า IG ของแอตทริบิวต์ temperature ดังในรูปที่ 2

Screen Shot 2557-03-17 at 7.57.33 AM

รูปที่ 2 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ temperature

จากรูปที่ 2 สามารถคำนวณค่า IG ได้ดังนี้
entropy(temperature = cool) = -p() × logp() – p() × logp()
= -[0.75 × log2(0.75) + 0.25 × log2(0.25)]
= 0.81

entropy(temperature = hot) = -p() × logp() – p() × logp()
= -[0.5 × log2(0.5) + 0.5× log2(0.5)]
= 1

entropy(temperature = mild) = -p() × logp() – p() × logp()
= -[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.96 – 0.91
= 0.05

3. คำนวณค่า IG ของแอตทริบิวต์ humidiy ดังในรูปที่ 3 ซึ่งได้ค่า IG = 0.16

Screen Shot 2557-03-17 at 7.57.39 AM

รูปที่ 3 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ humidity

จากรูปที่ 3 สามารถคำนวณค่า IG ได้ดังนี้
entropy(humidity = high) = -p() × logp() – p() × logp()
= -[0.43 × log2(0.43) + 0.57 × log2(0.57)]
= 0.99

entropy(humidity = normal) = -p() × logp() – p() × logp()
= -[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.96 – 0.79
= 0.17

4. คำนวณค่า IG ของแอตทริบิวต์ windy ดังในรูปที่ 4 ซึ่งได้ค่า IG = 0.05

Screen Shot 2557-03-17 at 7.57.45 AM

รูปที่ 4 แสดงค่าความน่าจะเป็นเมื่อใช้แอตทริบิวต์ windy

จากรูปที่ 4 สามารถคำนวณค่า IG ได้ดังนี้
entropy(windy = FALSE) = -p() × logp() – p() × logp()
= -[0.75 × log2(0.75) + 0.25 × log2(0.25)]
= 0.81

entropy(windy = TRUE) = -p() × logp() – p() × logp()
= -[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.96 – 0.89
= 0.07

5. จากการคำนวณค่า IG ของทุกแอตทริบิวต์พบว่าค่า IG ของแอตทริบิวต์ outlook มีค่ามากที่สุด (0.28) ดังนั้นจึงเลือกแอตทริบิวต์ outlook ขึ้นมาเป็นโหนด root ณ ขั้นนี้เราจะเห็นว่าข้อมูลที่อยู่ในโหนดที่แอตทริบิวต์ outlook = overcast มีคลาสเดียวกันหมดคือ play = yes ดังนั้นโหนดนี้ไม่ต้องทำการแตกกิ่งต่อไปอีกแล้ว แต่โหนดอื่นๆ จะต้องทำการแตกกิ่งออกไปจนข้อมูลในแต่ละโหนดมีคลาสคำตอบเดียวกันแล้ว ผมจะขอยกตัวอย่างการแตกกิ่งออกจากโหนดที่มีแอตทริบิวต์ outlook = sunny ดังแสดงในรูปที่ 5

Screen Shot 2557-03-17 at 8.21.38 AM

รูปที่ 5 แสดง decision tree เมื่อแตกกิ่งโดยใช้แอตทริบิวต์ humidity

จากรูปที่ 5 จะเห็นได้ว่าข้อมูลที่อยู่ในโหนด outlook = sunny และ humidity = high มีคลาสเป็น no และ  ข้อมูลที่อยู่ในโหนด outlook = sunny และ humidity = normal มีคลาสเป็น yes เมื่อเป็นแบบนี้แล้วก็แสดงว่าสามารถหยุดทำการแตกกิ่งต่อจากโหนดเหล่านี้ได้ แต่เพื่อให้เข้าใจการคำนวณค่า IG สำหรับโหนดในชั้นถัดไปผมจะแสดงวิธีการคำนวณให้ดูดังนี้

จากรูปที่ 5 สามารถคำนวณค่า IG ได้ดังนี้

entropy (parent) = -p() × logp() – p() × logp()
= -[0.4 × log2(0.4) + 0.6 × log2(0.6)]
= 0.97

entropy(humidity = high) = -p() × logp() – p() × logp()
= -[0.0 × log2(0.0) + 1.0 × log2(1.0)]
= 0

entropy(humidity = normal) = -p() × logp() – p() × logp()
= -[1.0 × log2(1.0) + 0.0 × log2(0.0)]
= 0

IG(parent, child) = entropy (parent) – [p(humidity = high) × entropy(humidity = high)+p(humidity = normal) × entropy(humidity = normal)]
= 0.97-[0.60 × 0.0 + 0.40 × 0.0]
= 0.97 – 0.0
= 0.97

ทั้งหมดนี้คือขั้นตอนการสร้างโมเดล decision tree ซึ่งข้อดีของโมเดลนี้มีดังนี้

  • เป็นโมเดลที่เข้าใจง่าย สามารถแปลความจากโมเดลได้เลย เช่น ถ้าวันไหนที่สภาพอากาศเป็นแบบ outlook แล้วจะมีการจัดแข่งขันกีฬา
  • โมเดลที่สร้างได้คัดเลือกแอตทริบิวต์ที่มีความสัมพันธ์กับคลาสคำตอบมาแล้ว ดังนั้นอาจจะไม่ได้ใช้ทุกแอตทริบิวต์ในข้อมูล training

ในปัจจุบันนี้เราสามารถใช้ซอฟต์แวร์ open source เพื่อสร้างโมเดล decision tree ได้อย่างง่ายๆ แถมสามารถแสดงโมเดลให้เป็นรูปแบบที่สวยงามได้อีกด้วย วันนี้ผมจะยกตัวอย่างภาพโมเดล decision tree จากข้อมูลนี้ให้ดู 2 ภาพ คือ รูปที่ 6 และ 7

Screen Shot 2557-03-17 at 8.41.51 AM

รูปที่ 6 แสดงโมเดล decision tree จากซอฟต์แวร์ Weka

Screen Shot 2557-03-17 at 8.42.35 AM

รูปที่ 7 แสดงโมเดล decision tree จากซอฟต์แวร์ RapidMiner Studio 6

  • รูปที่ 6 เป็นโมเดลที่สร้างขึ้นมาจากเทคนิค J48 ในซอฟต์แวร์ Weka ขั้นตอนการสร้างโมเดล J48 นี้ดูได้จากบทความเรื่อง “การสร้างโมเดล classification ด้วย Weka Explorer” และเปลี่ยนเทคนิคให้เป็น J48
  • รูปที่ 7 เป็นโมเดลที่สร้างขึ้นจากเทคนิค Decision Tree ในซอฟต์แวร์ RapidMiner Studio 6 ขั้นตอนการสร้างโมเดล Decision Tree นี้ดูได้จากบทความเรื่อง “บทที่ 1 แนะนำการใช้งาน RapidMiner Studio 6

ท่านผู้อ่านจะชอบ decision tree ที่สร้างได้จากซอฟต์แวร์แบบไหนก็เลือกกันเอาเองนะครับ ^^

Reference

  • Foster Provost and Tom Fawcett, Data Science for Business, O’ REILLY 2013

Posted in data mining, data science, machine learning, RapidMiner, weka and tagged , , , , , .

3 Comments

  1. อ่านแล้ว งง ตรงค่า IG เช่น 4. คำนวณค่า IG ของแอตทริบิวต์ windy ดังในรูปที่ 4 ซึ่งได้ค่า IG = 0.05 แต่ดูที่คำนวณมันเป็น 0.07 หรือ
    IG(parent, child) = entropy (parent) – [p(windy = FALSE) × log2p(windy = FALSE)+p(windy = TRUE) × log2p(windy = TRUE)]

    = 0.94-[0.57 × 0.81 + 0.43 × 1]
    = 0.96 – 0.89
    = 0.07
    ค่า p(windy = FALSE)=0.81 ดังนั้น log ของ log2p(windy = FALSE) จะเป็น log2(0.81)รึเปล่าครับ คือหาค่า log มันไม่ตรงกับของท่านอะครับ (หรือผมคำนวณ log ผิด)ขอบคุณครับ

    • ขอบคุณมากครับ ผมแก้ไขให้แล้วครับ จริงๆ ต้องเป็น IG(parent, child) = entropy (parent) – [p(windy = FALSE) × entropy(windy = FALSE)+p(windy = TRUE) × entropy(windy = TRUE)] ครับ

  2. Pingback: การสร้างโมเดล Decision Tree สำหรับแอตทริบิวต์ที่เป็นตัวเลข | Data Mining Trend

Leave a Reply

Your email address will not be published. Required fields are marked *