ต้นไม้ตัดสินใจ

การเรียนรู้แบบต้นไม้ตัดสินใจ  เป็นหนึ่งในวิธีการเรียนรู้ซึ่งใช้ในสถิติ, การเรียนรู้ของเครื่อง และการทำเหมืองข้อมูล โดยพิจารณาการสังเกตการแบ่งแยกข้อมูลโดยพิจารณาข้อมูล 
ในการเรียนรู้ของเครื่อง (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)
ขั้นตอนวิธีการสร้างต้นไม้การตัดสินใจ.
ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี  ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ  จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย John Ross Quinlan ในปี 1986
เอนโทรปี (Entropy) 
ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด  โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain)
ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้
 <math> E (S) = - \sum^{n}_{j=1} p_{S} (j) \log_{2} p_{S} (j) </math>
เมื่อ
โดยสำหรับต้นไม้การตัดสินใจที่มีผลลัพธ์เป็นแค่เพียงค่าตรรกะ (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)} \fracE (S_{v}) </math>
เมื่อ
จะเห็นว่าหากเกนความรู้ของ A ยิ่งมากแสดงว่าหลังจากแบ่งตัวอย่าง S ด้วย A แล้วในแต่ละชุดที่แบ่งได้จะมี Entropy เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา
การใช้ ID3 สอนต้นไม้การตัดสินใจ
เมื่อเราสามารถบอกความดีของตัวแปรต้นได้จึงสามารถนำไปช่วยในการหาต้นไม้การตัดสินใจด้วย ID3 ได้โดยมีกระบวนการดังนี้
นำมาเขียนเป็นรหัสเทียม (pseudo code) ได้ดังนี้ โดยยกตัวอย่างมาเฉพาะกรณีที่ตัวแปรตามมีแค่เพียงใช่กับไม่ใช่เท่านั้น
ID3 (Examples, Target_Attribute, Attributes)
ต้นไม้การตัดสินใจกับการค้นหาสมมติฐาน.
ID3 สามารถมองได้ว่าเป็นการค้นหาสมมติฐาน (hypothesis) จากสเปซของสมมติฐานทั้งหมด (hypothesis space) โดยที่สมมติฐานทั้งหมดคือต้นไม้การตัดสินใจทั้งหมดที่เป็นไปได้จากลักษณะต่างๆที่กำหนดมา ID3 ค้นหาต้นไม้จากรูปแบบง่ายไปสู่รูปแบบที่ซับซ้อน (simple-to-complex) ทั่วสเปซดังรูปด้านบน เริ่มจากต้นไม้ที่ว่างเปล่า และใส่รายละเอียดไปเรื่อยๆเพื่อให้สอดคล้องกับชุดข้อมูลที่นำมาเรียนรู้มากยิ่งขึ้น ฟังก์ชันที่บอกแนวทางการเติบโตของต้นไม้คือเกนความรู้ เมื่อมอง ID3 ในมุมมองของการค้นหาแล้ว สามารถวิเคราะห์ประสิทธิภาพและข้อจำกัดได้ดังนี้
ประเด็นอื่นๆของต้นไม้การตัดสินใจ.
การหลีกเลี่ยงการจำกัดอยู่กับตัวอย่างที่นำมาสอนมากเกินไป (overfit) ของต้นไม้การตัดสินใจ
ในหลายๆครั้งการเรียนรู้ด้วยต้นไม้การตัดสินใจทำให้ฟังก์ชันที่ได้ออกมาจำกัดอยู่กับข้อมูลที่นำมาสอน ตัวอย่างเช่น สมมติฐานสำหรับต้นไม้การตัดสินใจ h อัตราความถูกต้องในชุดที่นำมาสอนเป็น 90% แต่ในความเป็นจริงถูกต้อง 30% แต่สมมติฐานสำหรับต้นไม้การตัดสินใจ h' อัตราความถูกต้องในชุดที่นำมาสอนเป็น 70% แต่ในความเป็นจริงถูกต้อง 50% จะเรียนสมมติฐาน h ว่าโอเวอร์ฟิต (overfit)
การเข้ากันมากเกินไปของข้อมูลเกิดได้ดังตัวอย่างด้านบน ในตอนแรกต้นไม้ยังว่างเปล่าแล้วค่อยๆมีบัพเพิ่มมากขึ้นเรื่อยๆตามขั้นตอนวิธีการ ID3 ทำให้ความถูกต้องของข้อมูลในชุดที่นำมาเรียนรู้นั้นมากขึ้นเรื่อยๆตามลำดับ เมื่อพิจารณาความถูกต้องในข้อมูลจริงก็เพิ่มขึ้นด้วยเช่นกัน แต่เมื่อจำนวนบัพเพิ่มขึ้นถึงจุดหนึ่งความถูกต้องในข้อมูลจริงกลับลดลง เรียกเหตุการณ์นี้ว่าการเข้ากันมากเกินไป อาจเกิดจากการที่มีบางตัวแปรต้นที่ต้นไม้การตัดสินใจนำมาพิจารณาที่ไม่เกี่ยวข้อง หรือเกี่ยวข้องน้อยมากกับตัวแปรตาม เมื่อนำตัวแปรนี้มาพิจารณาด้วยจึงเกิดการแบ่งส่วนของข้อมูลเพิ่มจึ้นโดยไม่จำเป็น ทำให้เกิดเหตุการณ์ที่เรียกว่าการเข้ากันมากเกินไปขึ้น ซึ่งมีกระบวนการการแก้ไขเหตุการณ์นี้ได้ด้วยสองวิธีคือ
ซึ่งแบบแรกนั้นในทางปฏิบัติเป็นไปได้ยากกว่าแบบที่สองเพราะเราไม่รู้ว่าเมื่อไรควรจะหยุดการเจริญเติบโตของต้นไม้ จึงใช้วิธีที่สองมากกว่าซึ่งในวิธีที่สองนี้เริ่มต้นจะแบ่งตัวอย่าง (Example) ออกเป็น 3 ส่วนด้วยกันคือ
ซึ่งในกระบวนการตัดแต่งนั้นจะพิจารณาบัพในต้นไม้ว่าหากตัดบัพใดทิ้งแล้วความแม่นยำใน validating set ไม่ลดลงก็จะตัดทิ้งและจะตัดไปเรื่อยๆจนกว่าจะไม่สามารถตัดทิ้งตามเงื่อนไขได้อีก
การจัดการกับชุดข้อมูลที่นำมาเรียนรู้ที่ให้ค่าลักษณะของตัวแปรมาไม่ครบ
ในบางกรณีข้อมูลที่มีให้มีบางตัวขาดหายไป เช่น การวิเคราะห์โรคของผู้ป่วยอาจต้องใช้ผลเลือดในการวิเคราะห์ แต่ไม่สามารถหามาได้ จึงอาจต้องประมาณผลเลือดโดยการประมาณวิธีหนึ่งคือการใช้ผลเลือดที่คนส่วนใหญ่เป็นมากที่สุดซึ่งถูกใช้โดย Mingers (1989) หรืออีกวิธีคือการวิเคราะห์อัตราส่วนซึ่งถ่วงน้ำหนักการตัดสินใจในแต่ละอย่างด้วยสถิติที่ผ่านมา วิธีนี้ถูกนำมาใช้ใน C4.5 โดย Quinlan (1993)
การจัดการกับตัวแปรต้นที่มีค่าต่อเนื่อง
เมื่อตัวแปรต้นมีค่าต่อเนื่องจำเป็นที่จะต้องมีการแบ่งค่าต่อเนื่องออกมาเป็นช่วงๆแบบไม่ต่อเนื่อง ซึ่งไม่ต่อเนื่องทำให้สามารถประมวลผลได้ด้วยต้นไม้การตัดสินใจ แต่หากต้องการข้อมูลนำเขาและส่งออกที่ต่อเนื่องจริงๆจำเป็นที่จะต้องใช้วิธีอื่นๆ เช่น ข่ายงานประสาทเทียม (Neural Network)
การจัดการกับตัวแปรต้นที่มีราคา
ในปัญหาบางอย่างการที่จะหาตัวแปรต้นมาพิจารณานั้นจำเป็นที่จะต้องลงทุน เช่น การที่จะตรวจสอบว่าผู้ป่วยเป็นโรครึเปล่าอาจต้องรู้ ความดัน อุณหภูมิ ข้อมูลของเลือด ฟิลม์เอ็กซเรย์ ซึ่งข้อมูลจะได้มาเมื่อเสียต้นทุนไปจำนวนหนึ่ง ดังนั้นในการนิยามความดีของตัวแปรต้นที่เหมาะสมสำหรับการสร้างต้นไม้การตัดสินใจจำเป็นที่จะต้องเอาอีกปัจจัยคือ ราคา เข้ามาร่วมพิจารณาด้วย ในปี 1990 Tan และ Schilimmer เสนอค่าความดีของตัวแปรต้นเพื่อใช้ประมวลผลกับการรับรู้ของหุ่นยนต์ผ่านทางเซนเซอร์คือ
 <math> \frac{Gain^{2} (S, A)}{Cost (A)} </math>