ผลต่างระหว่างรุ่นของ "ต้นไม้ตัดสินใจ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Octahedron80 (คุย | ส่วนร่วม) เก็บกวาด |
|||
บรรทัด 3:
'''ต้นไม้การตัดสินใจ''' ({{lang-en|decision tree}}) เป็นวิธีหนึ่งที่จะประมาณฟังก์ชันที่มีค่าไม่ต่อเนื่อง (discrete-value function) ด้วย [[ต้นไม้ (ทฤษฎีกราฟ)|แผนผังต้นไม้]] อาจประกอบด้วยเซตของกฎต่างๆแบบ ถ้า-แล้ว (if-then) เพื่อให้มนุษย์สามารถอ่านแล้วเข้าใจการตัดสินใจของต้นไม้ได้
ใน[[การเรียนรู้ของเครื่อง]] (machine learning) '''ต้นไม้ตัดสินใจ''' เป็น[[แบบจำลองทางคณิตศาสตร์|โมเดลทางคณิตศาสตร์]]ที่ใช้ทำนายประเภทของวัตถุโดยพิจารณาจากลักษณะของวัตถุ [[บัพ]]ภายใน (inner node) ของต้นไม้จะแสดงตัวแปร ส่วนกิ่งจะแสดงค่าที่เป็นไปได้ของตัวแปร ส่วน[[บัพใบ]]จะแสดงประเภทของวัตถุ
ต้นไม้การจัดสินใจใน[[การบริหารธุรกิจ]] เป็น[[ต้นไม้ (ทฤษฎีกราฟ)|แผนผังต้นไม้]]ช่วยในการตัดสินใจ โดยแสดงถึงมูลค่าของทรัพยากรที่จะใช้ ความเสี่ยงในการลงทุนและและผลลัพธ์ที่มีโอกาสเกิดขึ้น ต้นไม้ตัดสินใจสร้างขึ้นเพื่อช่วยการตัดสินใจเพื่อใช้ในการสร้าง[[แผนงาน]] นิยมใช้มากใน[[การบริหารความเสี่ยง]] (risk management) ต้นไม้ตัดสินใจเป็นส่วนหนึ่งของ[[ทฤษฎีการตัดสินใจ]] (decision theory) และ [[ทฤษฎีกราฟ]] ต้นไม้ตัดสินใจเป็นวิธีการพื้นฐานอย่างหนึ่งสำหรับ[[การทำเหมืองข้อมูล]]
== ลักษณะของต้นไม้การตัดสินใจ ==
ต้นไม้การตัดสินใจจะทำการจัดกลุ่ม (classify) ชุดข้อมูลนำเข้าในแต่ละกรณี (Instance) แต่ละบัพ (node) ของต้นไม้การตัดสินใจคือตัวแปร (attribute) ต่างๆของชุดข้อมูล เช่นหากต้องการตัดสินใจว่าจะไปเล่นกีฬาหรือไม่ก็จะมีตัวแปรต้นที่จะต้องพิจารณาคือ ทัศนียภาพ ลม ความชื้น อุณหภูมิ เป็นต้น และมีตัวแปรตามซึ่งเป็นผลลัพธ์จากต้นไม้คือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่า ซึ่งแต่ละตัวแปรนั้นก็จะมีค่าของตัวเอง (value) เกิดเป็นชุดของตัวแปร-ค่าของตัวแปร (attribute-value pair) เช่น ทัศนียภาพเป็นตัวแปร ก็อาจมีค่าได้เป็น ฝนตก แดดออก หรือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่านั้นก็อาจมีค่าได้เป็นใช่ กับ ไม่ใช่ เป็นต้น การทำนายประเภทด้วยต้นไม้ตัดสินใจ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปรของบัพ แล้วจึงตามกิ่งของต้นไม้ที่กำหนดค่า เพื่อไปยังบัพลูกถัดไป การทดสอบนี้จะกระทำไปจนกระทั่งเจอบัพใบซึ่งจะแสดงผลการทำนาย
ต้นไม้ตัดสินใจนี้ใช้ทำนายว่าจะเล่นกีฬาหรือไม่ โดยพิจารณาจากลักษณะอากาศของวันนั้น โดยวัตถุที่ต้องการทำนายประเภท ประกอบด้วยลักษณะหรือตัวแปร 3 ตัว ได้แก่ ทัศนียภาพ ความชื้น และ กระแสลม ดังนั้น ถ้ากำหนดวันวันหนึ่งมีคุณลักษณะแสดงเป็นเวกเตอร์ เช่น [สภาพอากาศ=แดดออก, ความชื้น=สูง] การทำนายว่าจะเล่นกีฬาหรือไม่ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปร "สภาพอากาศ" ซึ่งมีค่าเท่ากับ "แดดออก" จึงไปทดสอบค่าตัวแปร "ความชื้น" ในบัพถัดไป ทำให้ได้ประเภทของวันนี้คือ "ไม่เล่นกีฬา"
บรรทัด 17:
== ขั้นตอนวิธีการสร้างต้นไม้การตัดสินใจ ==
ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี ({{lang-en|algorithm}}) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ ({{lang-en|greedy search}}) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย [[John Ross Quinlan]] ในปี 1986
'''เอนโทรปี (Entropy) '''▼
ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด ({{lang-en|recursion}}) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain)▼
▲'''เอนโทรปี(Entropy)'''
ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้▼
▲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 นิยามโ้ดย▼
▲'''เกนความรู้(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 เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา ▼
▲จะเห็นว่าหากเกนความรู้ของ A ยิ่งมากแสดงว่าหลังจากแบ่งตัวอย่าง S ด้วย A แล้วในแต่ละชุดที่แบ่งได้จะมี Entropy เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา
'''การใช้ ID3 สอนต้นไม้การตัดสินใจ'''
เมื่อเราสามารถบอกความดีของตัวแปรต้นได้จึงสามารถนำไปช่วยในการหาต้นไม้การตัดสินใจด้วย ID3 ได้โดยมีกระบวนการดังนี้
เส้น 68 ⟶ 62:
----------------------------------------------------------------------------------------------------------------------------------
* Examples คือตัวอย่างที่นำมาสอน
* Target_Attribute คือตัวแปรตาม
* Attribute คือตัวแปรต้น
ID3 (Examples, Target_Attribute, Attributes)
* สร้างบัพซึ่งเป็นรากเปล่าๆสำหรับต้นไม้▼
▲*สร้างบัพซึ่งเป็นรากเปล่าๆสำหรับต้นไม้
▲*ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นใช่
▲** return รากที่มีค่า + (ใช่)
▲*ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นไม่ใช่
▲** return รากที่มีค่า - (ไม่ใช่)
▲*ถ้าเซตของ Attribute เป็นเซตว่าง
* ถ้ามิฉะนั้น เริ่ม▼
▲** return รากที่มีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
▲*ถ้ามิฉะนั้น เริ่ม
** ให้รากที่ค่าเป็น A
▲** A = ตัวแปรต้นที่มีค่าของเกนความรู้สูงที่สุด
**
*** สร้าง Examples (<math>v_i</math>) เป็นสับเซตของ Example ที่ A มีค่า <math>v_i</math>
▲*** สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A = <math>v_i</math>
*** ถ้า Examples
**** ต่อกิ่งนี้ด้วยบัพที่มีใบมีึค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
* จบ▼
* Return ราก▼
▲*จบ
▲*Return ราก
== ต้นไม้การตัดสินใจกับการค้นหาสมมติฐาน ==
ID3 สามารถมองได้ว่าเป็นการค้นหาสมมติฐาน (hypothesis) จากสเปซของสมมติฐานทั้งหมด (hypothesis space) โดยที่สมมติฐานทั้งหมดคือต้นไม้การตัดสินใจทั้งหมดที่เป็นไปได้จากลักษณะต่างๆที่กำหนดมา ID3 ค้นหาต้นไม้จากรูปแบบง่ายไปสู่รูปแบบที่ซับซ้อน (simple-to-complex) ทั่วสเปซดังรูปด้านบน เริ่มจากต้นไม้ที่ว่างเปล่า และใส่รายละเอียดไปเรื่อยๆเพื่อให้สอดคล้องกับชุดข้อมูลที่นำมาเรียนรู้มากยิ่งขึ้น ฟังก์ชันที่บอกแนวทางการเติบโตของต้นไม้คือเกนความรู้ เมื่อมอง ID3 ในมุมมองของการค้นหาแล้ว สามารถวิเคราะห์ประสิทธิภาพและข้อจำกัดได้ดังนี้
* เนื่องจากสเปซของสมมติฐานทั้งหมดประกอบด้วยต้นไม้การตัดสินใจทุกต้นจากลักษณะที่กำหนดให้ เพราะฉะนั้นต้นไม้ที่ไม่มีตัวแปรตามจึงเป็นสมาชิกของเซตนี้เช่นกัน ID3 สามารถหลีกเลี่ยงความเสี่ยงที่จะได้ผลออกเป็นต้นไม้แบบนั้นได้
เส้น 108 ⟶ 100:
== ประเด็นอื่นๆของต้นไม้การตัดสินใจ ==
'''การหลีกเลี่ยงการจำกัดอยู่กับตัวอย่างที่นำมาสอนมากเกินไป (overfit) ของต้นไม้การตัดสินใจ'''
ในหลายๆครั้งการเรียนรู้ด้วยต้นไม้การตัดสินใจทำให้ฟังก์ชันที่ได้ออกมาจำกัดอยู่กับข้อมูลที่นำมาสอน ตัวอย่างเช่น สมมติฐานสำหรับต้นไม้การตัดสินใจ h อัตราความถูกต้องในชุดที่นำมาสอนเป็น 90% แต่ในความเป็นจริงถูกต้อง 30% แต่สมมติฐานสำหรับต้นไม้การตัดสินใจ h' อัตราความถูกต้องในชุดที่นำมาสอนเป็น 70% แต่ในความเป็นจริงถูกต้อง 50% จะเรียนสมมติฐาน h ว่าโอเวอร์ฟิต (overfit)
[[ไฟล์:Overfitting_data.jpg]]
เส้น 116 ⟶ 108:
การเข้ากันมากเกินไปของข้อมูลเกิดได้ดังตัวอย่างด้านบน ในตอนแรกต้นไม้ยังว่างเปล่าแล้วค่อยๆมีบัพเพิ่มมากขึ้นเรื่อยๆตามขั้นตอนวิธีการ ID3 ทำให้ความถูกต้องของข้อมูลในชุดที่นำมาเรียนรู้นั้นมากขึ้นเรื่อยๆตามลำดับ เมื่อพิจารณาความถูกต้องในข้อมูลจริงก็เพิ่มขึ้นด้วยเช่นกัน แต่เมื่อจำนวนบัพเพิ่มขึ้นถึงจุดหนึ่งความถูกต้องในข้อมูลจริงกลับลดลง เรียกเหตุการณ์นี้ว่าการเข้ากันมากเกินไป อาจเกิดจากการที่มีบางตัวแปรต้นที่ต้นไม้การตัดสินใจนำมาพิจารณาที่ไม่เกี่ยวข้อง หรือเกี่ยวข้องน้อยมากกับตัวแปรตาม เมื่อนำตัวแปรนี้มาพิจารณาด้วยจึงเกิดการแบ่งส่วนของข้อมูลเพิ่มจึ้นโดยไม่จำเป็น ทำให้เกิดเหตุการณ์ที่เรียกว่าการเข้ากันมากเกินไปขึ้น ซึ่งมีกระบวนการการแก้ไขเหตุการณ์นี้ได้ด้วยสองวิธีคือ
# หยุดการโตของต้นไม้ก่อนจะเริ่มโอเวอร์ฟิต
# ให้ต้นไม้โอเวอร์ฟิตแล้วนำมาตัดแต่งภายหลัง (post-pruning)
ซึ่งแบบแรกนั้นในทางปฏิบัติเป็นไปได้ยากกว่าแบบที่สองเพราะเราไม่รู้ว่าเมื่อไรควรจะหยุดการเจริญเติบโตของต้นไม้ จึงใช้วิธีที่สองมากกว่าซึ่งในวิธีที่สองนี้เริ่มต้นจะแบ่งตัวอย่าง (Example) ออกเป็น 3 ส่วนด้วยกันคือ
* ส่วนเรียนรู้สำหรับต้นไม้ (training set) ในส่วนนี้จะนำไปผ่านกระบวนการเรียนรู้ต่างๆ เช่น ID3 เพื่อให้ต้นไม้เจริญเติบโต
* ส่วนปรับปรุงต้นไม้ให้ถูกต้องยิ่งขึ้น (validating set) ในส่วนนี้จะทำไปผ่านการตัดแต่งเพื่อหลีกเลี่ยงการโอเวอร์ฟิตของสมมติฐาน
* ส่วนทดสอบ (test set) ในส่วนนี้จะบอกประสิทธิภาพของต้นไม้ว่าดีเท่าใด
ซึ่งในกระบวนการตัดแต่งนั้นจะพิจารณาบัพในต้นไม้ว่าหากตัดบัพใดทิ้งแล้วความแม่นยำใน validating set ไม่ลดลงก็จะตัดทิ้งและจะตัดไปเรื่อยๆจนกว่าจะไม่สามารถตัดทิ้งตามเงื่อนไขได้อีก
เส้น 128 ⟶ 120:
'''การจัดการกับชุดข้อมูลที่นำมาเรียนรู้ที่ให้ค่าลักษณะของตัวแปรมาไม่ครบ'''
ในบางกรณีข้อมูลที่มีให้มีบางตัวขาดหายไป เช่น การวิเคราะห์โรคของผู้ป่วยอาจต้องใช้ผลเลือดในการวิเคราะห์ แต่ไม่สามารถหามาได้ จึงอาจต้องประมาณผลเลือดโดยการประมาณวิธีหนึ่งคือการใช้ผลเลือดที่คนส่วนใหญ่เป็นมากที่สุดซึ่งถูกใช้โดย Mingers (1989) หรืออีกวิธีคือการวิเคราะห์อัตราส่วนซึ่งถ่วงน้ำหนักการตัดสินใจในแต่ละอย่างด้วยสถิติที่ผ่านมา วิธีนี้ถูกนำมาใช้ใน C4.5 โดย Quinlan (1993)
'''การจัดการกับตัวแปรต้นที่มีค่าต่อเนื่อง'''
เมื่อตัวแปรต้นมีค่าต่อเนื่องจำเป็นที่จะต้องมีการแบ่งค่าต่อเนื่องออกมาเป็นช่วงๆแบบไม่ต่อเนื่อง ซึ่งไม่ต่อเนื่องทำให้สามารถประมวลผลได้ด้วยต้นไม้การตัดสินใจ แต่หากต้องการข้อมูลนำเขาและส่งออกที่ต่อเนื่องจริงๆจำเป็นที่จะต้องใช้วิธีอื่นๆ เช่น [[ข่ายงานประสาทเทียม]] (Neural Network)
'''การจัดการกับตัวแปรต้นที่มีราคา'''
ใน
: <math> \frac{Gain^{2} (S, A)}{Cost (A)} </math>
== อ้างอิง ==
* [
* [
* [
* Mitchell, Tom. Machine Learning. McGraw-Hill, 1997, p. 52-80.
| |||