ต้นไม้ตัดสินใจ
การเรียนรู้ต้นไม้ตัดสินใจ (English: decision tree learning) ถูกคิดค้นโดย Dr.Dome และ Dr.JA เป็นวิธีหนึ่งที่จะประมาณฟังก์ชันที่มีค่าไม่ต่อเนื่อง (discrete-value function) ด้วย แผนผังต้นไม้ อาจประกอบด้วยเซตของกฎต่างๆแบบ ถ้า-แล้ว (if-then) เพื่อให้มนุษย์สามารถอ่านแล้วเข้าใจการตัดสินใจของต้นไม้ได้
ในการเรียนรู้ของเครื่อง (machine learning) ต้นไม้ตัดสินใจ เป็นโมเดลทางคณิตศาสตร์ที่ใช้ทำนายประเภทของวัตถุโดยพิจารณาจากลักษณะของวัตถุ บัพภายใน (inner node) ของต้นไม้จะแสดงตัวแปร ส่วนกิ่งจะแสดงค่าที่เป็นไปได้ของตัวแปร ส่วนบัพใบจะแสดงประเภทของวัตถุ
ต้นไม้การตัดสินใจในการบริหารธุรกิจ เป็นแผนผังต้นไม้ช่วยในการตัดสินใจ โดยแสดงถึงมูลค่าของทรัพยากรที่จะใช้ ความเสี่ยงในการลงทุนและและผลลัพธ์ที่มีโอกาสเกิดขึ้น ต้นไม้ตัดสินใจสร้างขึ้นเพื่อช่วยการตัดสินใจเพื่อใช้ในการสร้างแผนงาน นิยมใช้มากในการบริหารความเสี่ยง (risk management) ต้นไม้ตัดสินใจเป็นส่วนหนึ่งของทฤษฎีการตัดสินใจ (decision theory) และ ทฤษฎีกราฟ ต้นไม้ตัดสินใจเป็นวิธีการพื้นฐานอย่างหนึ่งสำหรับการทำเหมืองข้อมูล
ต้นไม้การตัดสินใจจะทำการจัดกลุ่ม (classify) ชุดข้อมูลนำเข้าในแต่ละกรณี (Instance) แต่ละบัพ (node) ของต้นไม้การตัดสินใจคือตัวแปร (attribute) ต่างๆของชุดข้อมูล เช่นหากต้องการตัดสินใจว่าจะไปเล่นกีฬาหรือไม่ก็จะมีตัวแปรต้นที่จะต้องพิจารณาคือ ทัศนียภาพ ลม ความชื้น อุณหภูมิ เป็นต้น และมีตัวแปรตามซึ่งเป็นผลลัพธ์จากต้นไม้คือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่า ซึ่งแต่ละตัวแปรนั้นก็จะมีค่าของตัวเอง (value) เกิดเป็นชุดของตัวแปร-ค่าของตัวแปร (attribute-value pair) เช่น ทัศนียภาพเป็นตัวแปร ก็อาจมีค่าได้เป็น ฝนตก แดดออก หรือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่านั้นก็อาจมีค่าได้เป็นใช่ กับ ไม่ใช่ เป็นต้น() การทำนายประเภทด้วยต้นไม้ตัดสินใจ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปรของบัพ แล้วจึงตามกิ่งของต้นไม้ที่กำหนดค่า เพื่อไปยังบัพลูกถัดไป การทดสอบนี้จะกระทำไปจนกระทั่งเจอบัพใบซึ่งจะแสดงผลการทำนาย
ต้นไม้ตัดสินใจนี้ใช้ทำนายว่าจะเล่นกีฬาหรือไม่ โดยพิจารณาจากลักษณะอากาศของวันนั้น โดยวัตถุที่ต้องการทำนายประเภท ประกอบด้วยลักษณะหรือตัวแปร 3 ตัว ได้แก่ ทัศนียภาพ ความชื้น และ กระแสลม ดังนั้น ถ้ากำหนดวันวันหนึ่งมีคุณลักษณะแสดงเป็นเวกเตอร์ เช่น [สภาพอากาศ=แดดออก, ความชื้น=สูง] การทำนายว่าจะเล่นกีฬาหรือไม่ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปร "สภาพอากาศ" ซึ่งมีค่าเท่ากับ "แดดออก" จึงไปทดสอบค่าตัวแปร "ความชื้น" ในบัพถัดไป ทำให้ได้ประเภทของวันนี้คือ "ไม่เล่นกีฬา"
เนื่องจากต้นไม้การตัดสินใจเป็นต้นไม้ที่แต่ละกิ่งที่ออกมาจากบัพแทนค่าของข้อมูลที่เป็นไปได้ในบัพนั้น เนื่องจากต้นไม้มีจำนวนกิ่งที่จำกัด ดังนั้นค่าของตัวแปรที่เป็นไปได้จึงต้องจำกัดด้วย จึงต้องมีจำนวนตัวแปรที่จำกัด และนอกจากนั้นยังบังคับว่าค่าของตัวแปรนั้นต้องไม่ต่อเนื่องด้วย โดยข้อมูลที่เข้ามานั้นอาจมีความผิดพลาดได้บ้าง โดยต้นไม้การตัดสินใจจะมีกระบวนการที่จะไม่นำความผิดพลาดนั้นมาพิจารณาเรียกว่าการตัดแต่งกิ่ง (post-pruning)
ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี (English: algorithm) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ (English: greedy search) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย John Ross Quinlan ในปี 1986
เอนโทรปี (Entropy)
ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด (English: recursion) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain) ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้
E ( S ) = − ∑ j = 1 n p S ( j ) log 2 ⁡ p S ( j ) {\displaystyle E(S)=-\sum _{j=1}^{n}p_{S}(j)\log _{2}p_{S}(j)}
S {\displaystyle S} คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี p S ( j ) {\displaystyle p_{S}(j)} คืออัตราส่วนของกรณีใน S ที่ตัวแปรตามหรือผลลัพธ์มีค่า j
โดยสำหรับต้นไม้การตัดสินใจที่มีผลลัพธ์เป็นแค่เพียงค่าตรรกะ (boolean) ใช่กับไม่ใช่เหมือนกับที่ยกมาตอนต้นของบทความนั้น จะมีเอนโทรปีคือ
E ( S ) = − p y e s l o g 2 ( p y e s ) − p n o l o g 2 ( p n o ) {\displaystyle E(S)=-p_{yes}log_{2}(p_{yes})-p_{no}log_{2}(p_{no})}
เมื่อพิจารณาเอนโทรปีแล้วจะเห็นว่าเอนโทรปีจะมีค่าอยู่ระหว่าง 0 กับ 1 โดยจะมีค่าเป็นศูนย์เมื่อทุกๆกรณีมีผลลัพธ์เพียงแบบเดียว เช่น ใช่ทั้งหมด หรือ ไม่ใช่ทั้งหมด และจะมีค่ามากขึ้นเมื่อเริ่มมีค่าที่แตกต่างกันมากขึ้น หรือจะพูดอีกนัยหนึ่งก็คือเอนโทรปีจะมีค่ามากขึ้นหากข้อมูลไม่บริสุทธิ์ และจะตัดสินใจได้ว่าผลลัพธ์จะเป็นอะไรเมื่อเอนโทรปีเป็น 0 เท่านั้น
เกนความรู้ (Information Gain)
ซึ่งจากการนิยามเอนโทรปีข้างต้น ทำให้เราสามารถนิยามลักษณะของตัวแปรต้นที่ดีได้ โดยตัวแปร A จะเป็นตัวแปรต้นที่ดีก็ต่อเมื่อหากว่าแบ่งข้อมูลตัวอย่าง (Example) ออกเป็นชุดๆมีจำนวนชุดตามจำนวนค่าของ A ที่เป็นไปได้เพื่อให้แต่ละกรณี (Instance) ในชุดนั้นมีค่า A เพียงค่าเดียวและค่าเฉลี่ยของเอนโทรปีของชุดข้อมูลที่ถูกแบ่งออก (partition) มานั้นต่ำที่สุด เรียกค่าคาดหวังของการลดลงของเอนโทรปีหลังจากข้อมูลถูกแบ่งด้วย A ว่าเกนความรู้ของ A นิยามโ้ดย
G a i n ( S , A ) = E ( S ) − ∑ v = v a l u e ( A ) | S v | | S | E ( S v ) {\displaystyle Gain(S,A)=E(S)-\sum _{v=value(A)}{\frac {|S_{v}|}{|S|}}E(S_{v})}
S {\displaystyle S} คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี E {\displaystyle E} คือเอนโทรปีของตัวอย่าง A {\displaystyle A} คือตัวแปรต้นที่พิจารณา value (A) คือเซตของค่าของ A ที่เป็นไปได้ S v {\displaystyle S_{v}} คือตัวอย่างที่ 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 สำหรับแต่ละค่าที่เป็นไปได้, v i {\displaystyle v_{i}} , ของ A, สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A = v i {\displaystyle v_{i}} สร้าง Examples ( v i {\displaystyle v_{i}} ) เป็นสับเซตของ Example ที่ A มีค่า v i {\displaystyle v_{i}} ถ้า Examples ( v i {\displaystyle v_{i}} ) เป็นเซตว่าง ต่อกิ่งนี้ด้วยบัพที่มีใบมีึค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples มิฉะนั้น ต่อกิ่งนี้ด้วย ID3 (Examples ( v i {\displaystyle v_{i}} ), Target_Attribute, Attributes – {A}) จบ Return ราก
ID3 สามารถมองได้ว่าเป็นการค้นหาสมมติฐาน (hypothesis) จากสเปซของสมมติฐานทั้งหมด (hypothesis space) โดยที่สมมติฐานทั้งหมดคือต้นไม้การตัดสินใจทั้งหมดที่เป็นไปได้จากลักษณะต่างๆที่กำหนดมา ID3 ค้นหาต้นไม้จากรูปแบบง่ายไปสู่รูปแบบที่ซับซ้อน (simple-to-complex) ทั่วสเปซดังรูปด้านบน เริ่มจากต้นไม้ที่ว่างเปล่า และใส่รายละเอียดไปเรื่อยๆเพื่อให้สอดคล้องกับชุดข้อมูลที่นำมาเรียนรู้มากยิ่งขึ้น ฟังก์ชันที่บอกแนวทางการเติบโตของต้นไม้คือเกนความรู้ เมื่อมอง ID3 ในมุมมองของการค้นหาแล้ว สามารถวิเคราะห์ประสิทธิภาพและข้อจำกัดได้ดังนี้
เนื่องจากสเปซของสมมติฐานทั้งหมดประกอบด้วยต้นไม้การตัดสินใจทุกต้นจากลักษณะที่กำหนดให้ เพราะฉะนั้นต้นไม้ที่ไม่มีตัวแปรตามจึงเป็นสมาชิกของเซตนี้เช่นกัน ID3 สามารถหลีกเลี่ยงความเสี่ยงที่จะได้ผลออกเป็นต้นไม้แบบนั้นได้ ID3 จะสนใจเฉพาะสมมติฐานปัจจุบันเท่านั้น จึงหาสมมติฐานที่สอดคล้องกับปัญหาได้เพียงสมมติฐานเดียวเท่านั้น ไม่สามารถหาสมมติฐานทั้งหมดที่สอดคล้องได้ ID3 ในรูปแบบที่ไม่มีการแก้ไขไม่มีการค้นหาย้อนกลับ (backtracking) เมื่อเลือกตัวแปรต้นตัวใดเป็นบัพแล้ว จะไม่สนใจตัวแปรต้นตัวนี้อีก ดังนั้นผลลัพธ์ที่ได้อาจเป็นผลลัพธ์ที่ดี แต่ไม่ดีที่สุด ID3 ใช้ข้อมูลทางสถิติคือเกนความรู้ของข้อมูลทุกตัวมาพิจารณารวมกัน มีข้อดีคือจะสามารถลดความผิดพลาดจากข้อมูลนำเข้าบางตัวได้ในระดับหนึ่ง
การหลีกเลี่ยงการจำกัดอยู่กับตัวอย่างที่นำมาสอนมากเกินไป (overfit) ของต้นไม้การตัดสินใจ
ในหลายๆครั้งการเรียนรู้ด้วยต้นไม้การตัดสินใจทำให้ฟังก์ชันที่ได้ออกมาจำกัดอยู่กับข้อมูลที่นำมาสอน ตัวอย่างเช่น สมมติฐานสำหรับต้นไม้การตัดสินใจ h อัตราความถูกต้องในชุดที่นำมาสอนเป็น 90% แต่ในความเป็นจริงถูกต้อง 30% แต่สมมติฐานสำหรับต้นไม้การตัดสินใจ h' อัตราความถูกต้องในชุดที่นำมาสอนเป็น 70% แต่ในความเป็นจริงถูกต้อง 50% จะเรียนสมมติฐาน h ว่าโอเวอร์ฟิต (overfit)
การเข้ากันมากเกินไปของข้อมูลเกิดได้ดังตัวอย่างด้านบน ในตอนแรกต้นไม้ยังว่างเปล่าแล้วค่อยๆมีบัพเพิ่มมากขึ้นเรื่อยๆตามขั้นตอนวิธีการ ID3 ทำให้ความถูกต้องของข้อมูลในชุดที่นำมาเรียนรู้นั้นมากขึ้นเรื่อยๆตามลำดับ เมื่อพิจารณาความถูกต้องในข้อมูลจริงก็เพิ่มขึ้นด้วยเช่นกัน แต่เมื่อจำนวนบัพเพิ่มขึ้นถึงจุดหนึ่งความถูกต้องในข้อมูลจริงกลับลดลง เรียกเหตุการณ์นี้ว่าการเข้ากันมากเกินไป อาจเกิดจากการที่มีบางตัวแปรต้นที่ต้นไม้การตัดสินใจนำมาพิจารณาที่ไม่เกี่ยวข้อง หรือเกี่ยวข้องน้อยมากกับตัวแปรตาม เมื่อนำตัวแปรนี้มาพิจารณาด้วยจึงเกิดการแบ่งส่วนของข้อมูลเพิ่มจึ้นโดยไม่จำเป็น ทำให้เกิดเหตุการณ์ที่เรียกว่าการเข้ากันมากเกินไปขึ้น ซึ่งมีกระบวนการการแก้ไขเหตุการณ์นี้ได้ด้วยสองวิธีคือ
หยุดการโตของต้นไม้ก่อนจะเริ่มโอเวอร์ฟิต ให้ต้นไม้โอเวอร์ฟิตแล้วนำมาตัดแต่งภายหลัง (post-pruning)
ซึ่งแบบแรกนั้นในทางปฏิบัติเป็นไปได้ยากกว่าแบบที่สองเพราะเราไม่รู้ว่าเมื่อไรควรจะหยุดการเจริญเติบโตของต้นไม้ จึงใช้วิธีที่สองมากกว่าซึ่งในวิธีที่สองนี้เริ่มต้นจะแบ่งตัวอย่าง (Example) ออกเป็น 3 ส่วนด้วยกันคือ
ส่วนเรียนรู้สำหรับต้นไม้ (training set) ในส่วนนี้จะนำไปผ่านกระบวนการเรียนรู้ต่างๆ เช่น ID3 เพื่อให้ต้นไม้เจริญเติบโต ส่วนปรับปรุงต้นไม้ให้ถูกต้องยิ่งขึ้น (validating set) ในส่วนนี้จะทำไปผ่านการตัดแต่งเพื่อหลีกเลี่ยงการโอเวอร์ฟิตของสมมติฐาน ส่วนทดสอบ (test set) ในส่วนนี้จะบอกประสิทธิภาพของต้นไม้ว่าดีเท่าใด
ซึ่งในกระบวนการตัดแต่งนั้นจะพิจารณาบัพในต้นไม้ว่าหากตัดบัพใดทิ้งแล้วความแม่นยำใน validating set ไม่ลดลงก็จะตัดทิ้งและจะตัดไปเรื่อยๆจนกว่าจะไม่สามารถตัดทิ้งตามเงื่อนไขได้อีก
การจัดการกับชุดข้อมูลที่นำมาเรียนรู้ที่ให้ค่าลักษณะของตัวแปรมาไม่ครบ
ในบางกรณีข้อมูลที่มีให้มีบางตัวขาดหายไป เช่น การวิเคราะห์โรคของผู้ป่วยอาจต้องใช้ผลเลือดในการวิเคราะห์ แต่ไม่สามารถหามาได้ จึงอาจต้องประมาณผลเลือดโดยการประมาณวิธีหนึ่งคือการใช้ผลเลือดที่คนส่วนใหญ่เป็นมากที่สุดซึ่งถูกใช้โดย Mingers (1989) หรืออีกวิธีคือการวิเคราะห์อัตราส่วนซึ่งถ่วงน้ำหนักการตัดสินใจในแต่ละอย่างด้วยสถิติที่ผ่านมา วิธีนี้ถูกนำมาใช้ใน C4.5 โดย Quinlan (1993)
การจัดการกับตัวแปรต้นที่มีค่าต่อเนื่อง
เมื่อตัวแปรต้นมีค่าต่อเนื่องจำเป็นที่จะต้องมีการแบ่งค่าต่อเนื่องออกมาเป็นช่วงๆแบบไม่ต่อเนื่อง ซึ่งไม่ต่อเนื่องทำให้สามารถประมวลผลได้ด้วยต้นไม้การตัดสินใจ แต่หากต้องการข้อมูลนำเขาและส่งออกที่ต่อเนื่องจริงๆจำเป็นที่จะต้องใช้วิธีอื่นๆ เช่น ข่ายงานประสาทเทียม (Neural Network)
การจัดการกับตัวแปรต้นที่มีราคา
ในปัญหาบางอย่างการที่จะหาตัวแปรต้นมาพิจารณานั้นจำเป็นที่จะต้องลงทุน เช่น การที่จะตรวจสอบว่าผู้ป่วยเป็นโรครึเปล่าอาจต้องรู้ ความดัน อุณหภูมิ ข้อมูลของเลือด ฟิลม์เอ็กซเรย์ ซึ่งข้อมูลจะได้มาเมื่อเสียต้นทุนไปจำนวนหนึ่ง ดังนั้นในการนิยามความดีของตัวแปรต้นที่เหมาะสมสำหรับการสร้างต้นไม้การตัดสินใจจำเป็นที่จะต้องเอาอีกปัจจัยคือ ราคา เข้ามาร่วมพิจารณาด้วย ในปี 1990 Tan และ Schilimmer เสนอค่าความดีของตัวแปรต้นเพื่อใช้ประมวลผลกับการรับรู้ของหุ่นยนต์ผ่านทางเซนเซอร์คือ
G a i n 2 ( S , A ) C o s t ( A ) {\displaystyle {\frac {Gain^{2}(S,A)}{Cost(A)}}}
Mitchell, Tom. Machine Learning. McGraw-Hill, 1997, p. 52-80.
การเรียนรู้ของเครื่อง การเรียนรู้แบบมีผู้สอน การแบ่งประเภทข้อมูล
หมวดหมู่:การเรียนรู้ของเครื่อง หมวดหมู่:การบริหาร หมวดหมู่:การจัดการเชิงกลยุทธ์ หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)