ผลต่างระหว่างรุ่นของ "ต้นไม้ตัดสินใจ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข ป้ายระบุ: แก้ไขจากอุปกรณ์เคลื่อนที่ แก้ไขจากเว็บสำหรับอุปกรณ์เคลื่อนที่ |
ล restore contents ป้ายระบุ: ย้อนรวดเดียว |
||
บรรทัด 1:
<!-- เนื่องจากบทความนี้มีทั้งเรื่อง Decision_tree และ Decision_tree_learning รวมอยู่ด้วยกัน จึงต้องการแยกเรื่อง Decision_tree ไปไว้ที่ [[ต้นไม้การตัดสินใจ]] -->
'''การเรียนรู้แบบต้นไม้ตัดสินใจ''' ({{lang-en|decision tree learning}}) เป็นหนึ่งในวิธีการเรียนรู้ซึ่งใช้ใน[[สถิติ]], [[การเรียนรู้ของเครื่อง]] และการทำเหมืองข้อมูล โดยพิจารณาการสังเกตการแบ่งแยกข้อมูลโดยพิจารณาข้อมูล
ใน[[การเรียนรู้ของเครื่อง]] (machine learning) '''ต้นไม้ตัดสินใจ''' เป็น[[แบบจำลองทางคณิตศาสตร์|โมเดลทางคณิตศาสตร์]]ที่ใช้ทำนายประเภทของวัตถุโดยพิจารณาจากลักษณะของวัตถุ [[บัพ]]ภายใน (inner node) ของต้นไม้จะแสดงตัวแปร ส่วนกิ่งจะแสดงค่าที่เป็นไปได้ของตัวแปร ส่วน[[บัพใบ]] (leaf node) จะแสดงประเภทของวัตถุ
ต้นไม้ตัดสินใจที่บัพใบแสดงถึงข้อมูลที่เป็นข้อมูลไม่ต่อเนื่อง (discrete values) จะเรียกว่า'''ต้นไม้ตัดสินใจแบบจำแนก''' (classification trees) และต้นไม้ตัดสินใจที่บัพใบเป็นข้อมูลต่อเนื่อง (continuous values) จะเรียกว่า'''ต้นไม้ตัดสินใจแบบถดถอย''' (regression trees)
ต้นไม้การตัดสินใจใน[[การบริหารธุรกิจ]] เป็น[[ต้นไม้ (ทฤษฎีกราฟ)|แผนผังต้นไม้]]ช่วยในการตัดสินใจ โดยแสดงถึงมูลค่าของทรัพยากรที่จะใช้ ความเสี่ยงในการลงทุนและผลลัพธ์ที่มีโอกาสเกิดขึ้น ต้นไม้ตัดสินใจสร้างขึ้นเพื่อช่วยการตัดสินใจเพื่อใช้ในการสร้าง[[แผนงาน]] นิยมใช้มากใน[[การบริหารความเสี่ยง]] (risk management) ต้นไม้ตัดสินใจเป็นส่วนหนึ่งของ[[ทฤษฎีการตัดสินใจ]] (decision theory) และ [[ทฤษฎีกราฟ]] ต้นไม้ตัดสินใจเป็นวิธีการพื้นฐานอย่างหนึ่งสำหรับ[[การทำเหมืองข้อมูล]]
== ลักษณะของต้นไม้การตัดสินใจ ==
<!-- เดี๋ยวมาเก็บกวาด -->
ต้นไม้การตัดสินใจจะทำการจัดกลุ่ม (classify) ชุดข้อมูลนำเข้าในแต่ละกรณี (Instance) แต่ละบัพ (node) ของต้นไม้การตัดสินใจคือตัวแปร (attribute) ต่างๆของชุดข้อมูล เช่นหากต้องการตัดสินใจว่าจะไปเล่นกีฬาหรือไม่ก็จะมีตัวแปรต้นที่จะต้องพิจารณาคือ ทัศนียภาพ ลม ความชื้น อุณหภูมิ เป็นต้น และมีตัวแปรตามซึ่งเป็นผลลัพธ์จากต้นไม้คือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่า ซึ่งแต่ละตัวแปรนั้นก็จะมีค่าของตัวเอง (value) เกิดเป็นชุดของตัวแปร-ค่าของตัวแปร (attribute-value pair) เช่น ทัศนียภาพเป็นตัวแปร ก็อาจมีค่าได้เป็น ฝนตก แดดออก หรือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่านั้นก็อาจมีค่าได้เป็นใช่ กับ ไม่ใช่ เป็นต้น การทำนายประเภทด้วยต้นไม้ตัดสินใจ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปรของบัพ แล้วจึงตามกิ่งของต้นไม้ที่กำหนดค่า เพื่อไปยังบัพลูกถัดไป การทดสอบนี้จะกระทำไปจนกระทั่งเจอบัพใบซึ่งจะแสดงผลการทำนาย
ต้นไม้ตัดสินใจนี้ใช้ทำนายว่าจะเล่นกีฬาหรือไม่ โดยพิจารณาจากลักษณะอากาศของวันนั้น โดยวัตถุที่ต้องการทำนายประเภท ประกอบด้วยลักษณะหรือตัวแปร 3 ตัว ได้แก่ ทัศนียภาพ ความชื้น และ กระแสลม ดังนั้น ถ้ากำหนดวันวันหนึ่งมีคุณลักษณะแสดงเป็นเวกเตอร์ เช่น [สภาพอากาศ=แดดออก, ความชื้น=สูง] การทำนายว่าจะเล่นกีฬาหรือไม่ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปร "สภาพอากาศ" ซึ่งมีค่าเท่ากับ "แดดออก" จึงไปทดสอบค่าตัวแปร "ความชื้น" ในบัพถัดไป ทำให้ได้ประเภทของวันนี้คือ "ไม่เล่นกีฬา"
== ปัญหาที่เหมาะสมสำหรับต้นไม้การตัดสินใจ ==
เนื่องจากต้นไม้การตัดสินใจเป็นต้นไม้ที่แต่ละกิ่งที่ออกมาจากบัพแทนค่าของข้อมูลที่เป็นไปได้ในบัพนั้น เนื่องจากต้นไม้มีจำนวนกิ่งที่จำกัด ดังนั้นค่าของตัวแปรที่เป็นไปได้จึงต้องจำกัดด้วย จึงต้องมีจำนวนตัวแปรที่จำกัด และนอกจากนั้นยังบังคับว่าค่าของตัวแปรนั้นต้องไม่ต่อเนื่องด้วย โดยข้อมูลที่เข้ามานั้นอาจมีความผิดพลาดได้บ้าง โดยต้นไม้การตัดสินใจจะมีกระบวนการที่จะไม่นำความผิดพลาดนั้นมาพิจารณาเรียกว่าการตัดแต่งกิ่ง (post-pruning)
== ขั้นตอนวิธีการสร้างต้นไม้การตัดสินใจ ==
ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี ({{lang-en|algorithm}}) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ ({{lang-en|greedy search}}) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย [[John Ross Quinlan]] ในปี 1986
'''เอนโทรปี (Entropy) '''
ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด ({{lang-en|recursion}}) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain)
ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้
: <math> E (S) = - \sum^{n}_{j=1} p_{S} (j) \log_{2} p_{S} (j) </math>
เมื่อ
* <math> S </math> คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
* <math> p_{S} (j) </math> คืออัตราส่วนของกรณีใน S ที่ตัวแปรตามหรือผลลัพธ์มีค่า j
โดยสำหรับต้นไม้การตัดสินใจที่มีผลลัพธ์เป็นแค่เพียงค่าตรรกะ (boolean) ใช่กับไม่ใช่เหมือนกับที่ยกมาตอนต้นของบทความนั้น จะมีเอนโทรปีคือ
: <math> E (S) = - p_{yes}log_{2} (p_{yes}) - p_{no}log_{2} (p_{no}) </math>
เมื่อพิจารณาเอนโทรปีแล้วจะเห็นว่าเอนโทรปีจะมีค่าอยู่ระหว่าง 0 กับ 1 โดยจะมีค่าเป็นศูนย์เมื่อทุกๆกรณีมีผลลัพธ์เพียงแบบเดียว เช่น ใช่ทั้งหมด หรือ ไม่ใช่ทั้งหมด และจะมีค่ามากขึ้นเมื่อเริ่มมีค่าที่แตกต่างกันมากขึ้น หรือจะพูดอีกนัยหนึ่งก็คือเอนโทรปีจะมีค่ามากขึ้นหากข้อมูลไม่บริสุทธิ์ และจะตัดสินใจได้ว่าผลลัพธ์จะเป็นอะไรเมื่อเอนโทรปีเป็น 0 เท่านั้น
'''เกนความรู้ (Information Gain) '''
ซึ่งจากการนิยามเอนโทรปีข้างต้น ทำให้เราสามารถนิยามลักษณะของตัวแปรต้นที่ดีได้ โดยตัวแปร A จะเป็นตัวแปรต้นที่ดีก็ต่อเมื่อหากว่าแบ่งข้อมูลตัวอย่าง (Example) ออกเป็นชุดๆมีจำนวนชุดตามจำนวนค่าของ A ที่เป็นไปได้เพื่อให้แต่ละกรณี (Instance) ในชุดนั้นมีค่า A เพียงค่าเดียวและค่าเฉลี่ยของเอนโทรปีของชุดข้อมูลที่ถูกแบ่งออก (partition) มานั้นต่ำที่สุด เรียกค่าคาดหวังของการลดลงของเอนโทรปีหลังจากข้อมูลถูกแบ่งด้วย A ว่าเกนความรู้ของ A นิยามโดย
: <math> Gain (S, A) = E (S) - \sum_{v=value (A)} \frac{|S_{v}|}{|S|}E (S_{v}) </math>
เมื่อ
* <math> S </math> คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
* <math> E </math> คือเอนโทรปีของตัวอย่าง
* <math> A </math> คือตัวแปรต้นที่พิจารณา
* value (A) คือเซตของค่าของ A ที่เป็นไปได้
* <math> S_{v} </math> คือตัวอย่างที่ 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
** สำหรับแต่ละค่าที่เป็นไปได้, <math>v_i</math>, ของ A,
*** สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A = <math>v_i</math>
*** สร้าง Examples (<math>v_i</math>) เป็นสับเซตของ Example ที่ A มีค่า <math>v_i</math>
*** ถ้า Examples (<math>v_i</math>) เป็นเซตว่าง
**** ต่อกิ่งนี้ด้วยบัพที่มีใบมีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
*** มิฉะนั้น ต่อกิ่งนี้ด้วย ID3 (Examples (<math>v_i</math>), Target_Attribute, Attributes – {A})
* จบ
* Return ราก
== ต้นไม้การตัดสินใจกับการค้นหาสมมติฐาน ==
[[ไฟล์:Hypothesis searching.jpg|link=Special:FilePath/Hypothesis_searching.jpg]]
ID3 สามารถมองได้ว่าเป็นการค้นหาสมมติฐาน (hypothesis) จากสเปซของสมมติฐานทั้งหมด (hypothesis space) โดยที่สมมติฐานทั้งหมดคือต้นไม้การตัดสินใจทั้งหมดที่เป็นไปได้จากลักษณะต่างๆที่กำหนดมา ID3 ค้นหาต้นไม้จากรูปแบบง่ายไปสู่รูปแบบที่ซับซ้อน (simple-to-complex) ทั่วสเปซดังรูปด้านบน เริ่มจากต้นไม้ที่ว่างเปล่า และใส่รายละเอียดไปเรื่อยๆเพื่อให้สอดคล้องกับชุดข้อมูลที่นำมาเรียนรู้มากยิ่งขึ้น ฟังก์ชันที่บอกแนวทางการเติบโตของต้นไม้คือเกนความรู้ เมื่อมอง ID3 ในมุมมองของการค้นหาแล้ว สามารถวิเคราะห์ประสิทธิภาพและข้อจำกัดได้ดังนี้
* เนื่องจากสเปซของสมมติฐานทั้งหมดประกอบด้วยต้นไม้การตัดสินใจทุกต้นจากลักษณะที่กำหนดให้ เพราะฉะนั้นต้นไม้ที่ไม่มีตัวแปรตามจึงเป็นสมาชิกของเซตนี้เช่นกัน ID3 สามารถหลีกเลี่ยงความเสี่ยงที่จะได้ผลออกเป็นต้นไม้แบบนั้นได้
* ID3 จะสนใจเฉพาะสมมติฐานปัจจุบันเท่านั้น จึงหาสมมติฐานที่สอดคล้องกับปัญหาได้เพียงสมมติฐานเดียวเท่านั้น ไม่สามารถหาสมมติฐานทั้งหมดที่สอดคล้องได้
* ID3 ในรูปแบบที่ไม่มีการแก้ไขไม่มีการค้นหาย้อนกลับ (backtracking) เมื่อเลือกตัวแปรต้นตัวใดเป็นบัพแล้ว จะไม่สนใจตัวแปรต้นตัวนี้อีก ดังนั้นผลลัพธ์ที่ได้อาจเป็นผลลัพธ์ที่ดี แต่ไม่ดีที่สุด
* ID3 ใช้ข้อมูลทางสถิติคือเกนความรู้ของข้อมูลทุกตัวมาพิจารณารวมกัน มีข้อดีคือจะสามารถลดความผิดพลาดจากข้อมูลนำเข้าบางตัวได้ในระดับหนึ่ง
== ประเด็นอื่นๆของต้นไม้การตัดสินใจ ==
เส้น 31 ⟶ 133:
ในปัญหาบางอย่างการที่จะหาตัวแปรต้นมาพิจารณานั้นจำเป็นที่จะต้องลงทุน เช่น การที่จะตรวจสอบว่าผู้ป่วยเป็นโรครึเปล่าอาจต้องรู้ ความดัน อุณหภูมิ ข้อมูลของเลือด ฟิลม์เอ็กซเรย์ ซึ่งข้อมูลจะได้มาเมื่อเสียต้นทุนไปจำนวนหนึ่ง ดังนั้นในการนิยามความดีของตัวแปรต้นที่เหมาะสมสำหรับการสร้างต้นไม้การตัดสินใจจำเป็นที่จะต้องเอาอีกปัจจัยคือ ราคา เข้ามาร่วมพิจารณาด้วย ในปี 1990 [[Tan]] และ [[Schilimmer]] เสนอค่าความดีของตัวแปรต้นเพื่อใช้ประมวลผลกับการรับรู้ของหุ่นยนต์ผ่านทางเซนเซอร์คือ
: <math> \frac{Gain^{2} (S, A)}{Cost (A)} </math>
== อ้างอิง ==
* Mitchell, Tom. Machine Learning. McGraw-Hill, 1997, p. 52-80.
== ดูเพิ่ม ==
* [[การเรียนรู้ของเครื่อง]]
* [[การเรียนรู้แบบมีผู้สอน]]
* [[การแบ่งประเภทข้อมูล]]
[[หมวดหมู่:การเรียนรู้ของเครื่อง]]
[[หมวดหมู่:การบริหาร]]
[[หมวดหมู่:การจัดการเชิงกลยุทธ์]]
[[หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)]]
{{โครงความรู้}}
| |||