การเรียนรู้ต้นไม้ตัดสินใจ

จากวิกิพีเดีย สารานุกรมเสรี


การเรียนรู้ต้นไม้ตัดสินใจ (อังกฤษ: decision tree learning) เป็นวิธีหนึ่งที่จะประมาณฟังก์ชันที่มีค่าไม่ต่อเนื่อง (discrete-value function) ด้วย แผนผังต้นไม้ อาจประกอบด้วยเซตของกฎต่างๆแบบ ถ้า-แล้ว (if-then) เพื่อให้มนุษย์สามารถอ่านแล้วเข้าใจการตัดสินใจของต้นไม้ได้

ในการเรียนรู้ของเครื่อง (machine learning) ต้นไม้ตัดสินใจ เป็นโมเดลทางคณิตศาสตร์ที่ใช้ทำนายประเภทของวัตถุโดยพิจารณาจากลักษณะของวัตถุ บัพภายใน (inner node) ของต้นไม้จะแสดงตัวแปร ส่วนกิ่งจะแสดงค่าที่เป็นไปได้ของตัวแปร ส่วนบัพใบจะแสดงประเภทของวัตถุ

ต้นไม้การจัดสินใจในการบริหารธุรกิจ เป็นแผนผังต้นไม้ช่วยในการตัดสินใจ โดยแสดงถึงมูลค่าของทรัพยากรที่จะใช้ ความเสี่ยงในการลงทุนและและผลลัพธ์ที่มีโอกาสเกิดขึ้น ต้นไม้ตัดสินใจสร้างขึ้นเพื่อช่วยการตัดสินใจเพื่อใช้ในการสร้างแผนงาน นิยมใช้มากในการบริหารความเสี่ยง (risk management) ต้นไม้ตัดสินใจเป็นส่วนหนึ่งของทฤษฎีการตัดสินใจ (decision theory) และ ทฤษฎีกราฟ ต้นไม้ตัดสินใจเป็นวิธีการพื้นฐานอย่างหนึ่งสำหรับการทำเหมืองข้อมูล

ลักษณะของต้นไม้การตัดสินใจ[แก้]

ต้นไม้การตัดสินใจจะทำการจัดกลุ่ม (classify) ชุดข้อมูลนำเข้าในแต่ละกรณี (Instance) แต่ละบัพ (node) ของต้นไม้การตัดสินใจคือตัวแปร (attribute) ต่างๆของชุดข้อมูล เช่นหากต้องการตัดสินใจว่าจะไปเล่นกีฬาหรือไม่ก็จะมีตัวแปรต้นที่จะต้องพิจารณาคือ ทัศนียภาพ ลม ความชื้น อุณหภูมิ เป็นต้น และมีตัวแปรตามซึ่งเป็นผลลัพธ์จากต้นไม้คือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่า ซึ่งแต่ละตัวแปรนั้นก็จะมีค่าของตัวเอง (value) เกิดเป็นชุดของตัวแปร-ค่าของตัวแปร (attribute-value pair) เช่น ทัศนียภาพเป็นตัวแปร ก็อาจมีค่าได้เป็น ฝนตก แดดออก หรือการตัดสินใจว่าจะไปเล่นกีฬารึเปล่านั้นก็อาจมีค่าได้เป็นใช่ กับ ไม่ใช่ เป็นต้น การทำนายประเภทด้วยต้นไม้ตัดสินใจ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปรของบัพ แล้วจึงตามกิ่งของต้นไม้ที่กำหนดค่า เพื่อไปยังบัพลูกถัดไป การทดสอบนี้จะกระทำไปจนกระทั่งเจอบัพใบซึ่งจะแสดงผลการทำนาย

ต้นไม้ตัดสินใจนี้ใช้ทำนายว่าจะเล่นกีฬาหรือไม่ โดยพิจารณาจากลักษณะอากาศของวันนั้น โดยวัตถุที่ต้องการทำนายประเภท ประกอบด้วยลักษณะหรือตัวแปร 3 ตัว ได้แก่ ทัศนียภาพ ความชื้น และ กระแสลม ดังนั้น ถ้ากำหนดวันวันหนึ่งมีคุณลักษณะแสดงเป็นเวกเตอร์ เช่น [สภาพอากาศ=แดดออก, ความชื้น=สูง] การทำนายว่าจะเล่นกีฬาหรือไม่ จะเริ่มจากบัพราก โดยทดสอบค่าตัวแปร "สภาพอากาศ" ซึ่งมีค่าเท่ากับ "แดดออก" จึงไปทดสอบค่าตัวแปร "ความชื้น" ในบัพถัดไป ทำให้ได้ประเภทของวันนี้คือ "ไม่เล่นกีฬา"

ปัญหาที่เหมาะสมสำหรับต้นไม้การตัดสินใจ[แก้]

เนื่องจากต้นไม้การตัดสินใจเป็นต้นไม้ที่แต่ละกิ่งที่ออกมาจากบัพแทนค่าของข้อมูลที่เป็นไปได้ในบัพนั้น เนื่องจากต้นไม้มีจำนวนกิ่งที่จำกัด ดังนั้นค่าของตัวแปรที่เป็นไปได้จึงต้องจำกัดด้วย จึงต้องมีจำนวนตัวแปรที่จำกัด และนอกจากนั้นยังบังคับว่าค่าของตัวแปรนั้นต้องไม่ต่อเนื่องด้วย โดยข้อมูลที่เข้ามานั้นอาจมีความผิดพลาดได้บ้าง โดยต้นไม้การตัดสินใจจะมีกระบวนการที่จะไม่นำความผิดพลาดนั้นมาพิจารณาเรียกว่าการตัดแต่งกิ่ง (post-pruning)

ขั้นตอนวิธีการสร้างต้นไม้การตัดสินใจ[แก้]

ในปัจจุบันนั้นมีการพัฒนาขั้นตอนวิธี (อังกฤษ: algorithm) ในการสอน (training) ต้นไม้การตัดสินใจมากมาย ซึ่งส่วนมากมาจากวิธีพื้นฐานวิธีหนึ่งซึ่งเป็นการค้นหาแบบละโมภ (อังกฤษ: greedy search) จากบนลงล่าง (top-down) ชื่อว่า ID3 ซึ่งถูกพัฒนาโดย John Ross Quinlan ในปี 1986

เอนโทรปี (Entropy)

ID3 นั้นสร้างต้นไม้การตัดสินใจจากบนลงล่างด้วยการถามว่าลักษณะใด (ขอใช้คำว่าลักษณะแทนตัวแปรต้น) ควรจะเป็นรากของต้นไม้การตัดสินใจต้นนี้ และถามซ้ำๆไปเรื่อยๆเพื่อหาต้นไม้ทั้งต้นด้วยการเขียนโปรแกรมด้วยความสัมพันธ์แบบเวียนเกิด (อังกฤษ: recursion) โดยในการเลือกว่าลักษณะใดดีที่สุดนั้นดูจากค่าของลักษณะเรียกว่าเกนความรู้ (Information gain) ก่อนที่จะรู้จักเกนความรู้จะต้องนิยามค่าหนึ่งที่ใช้บอกความไม่บริสุทธิ์ของข้อมูลก่อน เรียกว่าเอนโทรปี (Entropy) โดยนิยามเอนโทรปีของต้นไม้การตัดสินใจในตัวในเซตของตัวอย่าง S คือ E (S) ดังนี้

 E (S) = - \sum^{n}_{j=1} p_{S} (j) \log_{2} p_{S} (j)

เมื่อ

  •  S คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
  •  p_{S} (j) คืออัตราส่วนของกรณีใน S ที่ตัวแปรตามหรือผลลัพธ์มีค่า j

โดยสำหรับต้นไม้การตัดสินใจที่มีผลลัพธ์เป็นแค่เพียงค่าตรรกะ (boolean) ใช่กับไม่ใช่เหมือนกับที่ยกมาตอนต้นของบทความนั้น จะมีเอนโทรปีคือ

 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 นิยามโ้ดย

 Gain (S, A) = E (S) - \sum_{v=value (A)} \frac{|S_{v}|}{|S|}E (S_{v})

เมื่อ

  •  S คือตัวอย่างที่ประกอบด้วยชุดของตัวแปรต้นและตัวแปรตามหลายๆกรณี
  •  E คือเอนโทรปีของตัวอย่าง
  •  A คือตัวแปรต้นที่พิจารณา
  • value (A) คือเซตของค่าของ A ที่เป็นไปได้
  •  S_{v} คือตัวอย่างที่ A มีค่า v ทั้งหมด

จะเห็นว่าหากเกนความรู้ของ A ยิ่งมากแสดงว่าหลังจากแบ่งตัวอย่าง S ด้วย A แล้วในแต่ละชุดที่แบ่งได้จะมี Entropy เข้าใกล้ศูนย์มากยิ่งขึ้น ทำให้ใกล้ที่จะตัดสินใจได้มากขึ้น เกนความรู้จึงเป็นค่าที่ดีที่จะบอกความดีของตัวแปรต้นที่นำมาพิจารณา

การใช้ ID3 สอนต้นไม้การตัดสินใจ

เมื่อเราสามารถบอกความดีของตัวแปรต้นได้จึงสามารถนำไปช่วยในการหาต้นไม้การตัดสินใจด้วย ID3 ได้โดยมีกระบวนการดังนี้

  1. นำตัวแปรต้นที่ยังไม่ถูกนำมาใช้ทั้งหมดมาหาเกนความรู้
  2. เลือกตัวที่มีเกนสูงที่สุด
  3. สร้างต้นไม้ที่มีบัพรากเป็นของตัวแปรต้นตัวนั้น

นำมาเขียนเป็นรหัสเทียม (pseudo code) ได้ดังนี้ โดยยกตัวอย่างมาเฉพาะกรณีที่ตัวแปรตามมีแค่เพียงใช่กับไม่ใช่เท่านั้น


  • Examples คือตัวอย่างที่นำมาสอน
  • Target_Attribute คือตัวแปรตาม
  • Attribute คือตัวแปรต้น

ID3 (Examples, Target_Attribute, Attributes)

  • สร้างบัพซึ่งเป็นรากเปล่าๆสำหรับต้นไม้
  • ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นใช่
    • return รากที่มีค่า + (ใช่)
  • ถ้าทุกตัวอย่างในต้นไม้มีค่าผลลัพธ์ของตัวแปรตามเป็นไม่ใช่
    • return รากที่มีค่า - (ไม่ใช่)
  • ถ้าเซตของ Attribute เป็นเซตว่าง
    • return รากที่มีค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
  • ถ้ามิฉะนั้น เริ่ม
    • A = ตัวแปรต้นที่มีค่าของเกนความรู้สูงที่สุด
    • ให้รากที่ค่าเป็น A
    • สำหรับแต่ละค่าที่เป็นไปได้, v_i, ของ A,
      • สร้างกิ่งต่อจากรากที่จะตัดสินใจมาทางนี้เมื่อ A = v_i
      • สร้าง Examples (v_i) เป็นสับเซตของ Example ที่ A มีค่า v_i
      • ถ้า Examples (v_i) เป็นเซตว่าง
        • ต่อกิ่งนี้ด้วยบัพที่มีใบมีึค่าเป็นค่าของ Target_Attribute ที่มีจำนวนมากที่สุดใน Examples
      • มิฉะนั้น ต่อกิ่งนี้ด้วย ID3 (Examples (v_i), Target_Attribute, Attributes – {A})
  • จบ
  • Return ราก

ต้นไม้การตัดสินใจกับการค้นหาสมมติฐาน[แก้]

ไฟล์:Hypothesis searching.jpg

ID3 สามารถมองได้ว่าเป็นการค้นหาสมมติฐาน (hypothesis) จากสเปซของสมมติฐานทั้งหมด (hypothesis space) โดยที่สมมติฐานทั้งหมดคือต้นไม้การตัดสินใจทั้งหมดที่เป็นไปได้จากลักษณะต่างๆที่กำหนดมา ID3 ค้นหาต้นไม้จากรูปแบบง่ายไปสู่รูปแบบที่ซับซ้อน (simple-to-complex) ทั่วสเปซดังรูปด้านบน เริ่มจากต้นไม้ที่ว่างเปล่า และใส่รายละเอียดไปเรื่อยๆเพื่อให้สอดคล้องกับชุดข้อมูลที่นำมาเรียนรู้มากยิ่งขึ้น ฟังก์ชันที่บอกแนวทางการเติบโตของต้นไม้คือเกนความรู้ เมื่อมอง ID3 ในมุมมองของการค้นหาแล้ว สามารถวิเคราะห์ประสิทธิภาพและข้อจำกัดได้ดังนี้

  • เนื่องจากสเปซของสมมติฐานทั้งหมดประกอบด้วยต้นไม้การตัดสินใจทุกต้นจากลักษณะที่กำหนดให้ เพราะฉะนั้นต้นไม้ที่ไม่มีตัวแปรตามจึงเป็นสมาชิกของเซตนี้เช่นกัน ID3 สามารถหลีกเลี่ยงความเสี่ยงที่จะได้ผลออกเป็นต้นไม้แบบนั้นได้
  • ID3 จะสนใจเฉพาะสมมติฐานปัจจุบันเท่านั้น จึงหาสมมติฐานที่สอดคล้องกับปัญหาได้เพียงสมมติฐานเดียวเท่านั้น ไม่สามารถหาสมมติฐานทั้งหมดที่สอดคล้องได้
  • ID3 ในรูปแบบที่ไม่มีการแก้ไขไม่มีการค้นหาย้อนกลับ (backtracking) เมื่อเลือกตัวแปรต้นตัวใดเป็นบัพแล้ว จะไม่สนใจตัวแปรต้นตัวนี้อีก ดังนั้นผลลัพธ์ที่ได้อาจเป็นผลลัพธ์ที่ดี แต่ไม่ดีที่สุด
  • ID3 ใช้ข้อมูลทางสถิติคือเกนความรู้ของข้อมูลทุกตัวมาพิจารณารวมกัน มีข้อดีคือจะสามารถลดความผิดพลาดจากข้อมูลนำเข้าบางตัวได้ในระดับหนึ่ง

ประเด็นอื่นๆของต้นไม้การตัดสินใจ[แก้]

การหลีกเลี่ยงการจำกัดอยู่กับตัวอย่างที่นำมาสอนมากเกินไป (overfit) ของต้นไม้การตัดสินใจ

ในหลายๆครั้งการเรียนรู้ด้วยต้นไม้การตัดสินใจทำให้ฟังก์ชันที่ได้ออกมาจำกัดอยู่กับข้อมูลที่นำมาสอน ตัวอย่างเช่น สมมติฐานสำหรับต้นไม้การตัดสินใจ h อัตราความถูกต้องในชุดที่นำมาสอนเป็น 90% แต่ในความเป็นจริงถูกต้อง 30% แต่สมมติฐานสำหรับต้นไม้การตัดสินใจ h' อัตราความถูกต้องในชุดที่นำมาสอนเป็น 70% แต่ในความเป็นจริงถูกต้อง 50% จะเรียนสมมติฐาน h ว่าโอเวอร์ฟิต (overfit)

Overfitting data.jpg

การเข้ากันมากเกินไปของข้อมูลเกิดได้ดังตัวอย่างด้านบน ในตอนแรกต้นไม้ยังว่างเปล่าแล้วค่อยๆมีบัพเพิ่มมากขึ้นเรื่อยๆตามขั้นตอนวิธีการ ID3 ทำให้ความถูกต้องของข้อมูลในชุดที่นำมาเรียนรู้นั้นมากขึ้นเรื่อยๆตามลำดับ เมื่อพิจารณาความถูกต้องในข้อมูลจริงก็เพิ่มขึ้นด้วยเช่นกัน แต่เมื่อจำนวนบัพเพิ่มขึ้นถึงจุดหนึ่งความถูกต้องในข้อมูลจริงกลับลดลง เรียกเหตุการณ์นี้ว่าการเข้ากันมากเกินไป อาจเกิดจากการที่มีบางตัวแปรต้นที่ต้นไม้การตัดสินใจนำมาพิจารณาที่ไม่เกี่ยวข้อง หรือเกี่ยวข้องน้อยมากกับตัวแปรตาม เมื่อนำตัวแปรนี้มาพิจารณาด้วยจึงเกิดการแบ่งส่วนของข้อมูลเพิ่มจึ้นโดยไม่จำเป็น ทำให้เกิดเหตุการณ์ที่เรียกว่าการเข้ากันมากเกินไปขึ้น ซึ่งมีกระบวนการการแก้ไขเหตุการณ์นี้ได้ด้วยสองวิธีคือ

  1. หยุดการโตของต้นไม้ก่อนจะเริ่มโอเวอร์ฟิต
  2. ให้ต้นไม้โอเวอร์ฟิตแล้วนำมาตัดแต่งภายหลัง (post-pruning)

ซึ่งแบบแรกนั้นในทางปฏิบัติเป็นไปได้ยากกว่าแบบที่สองเพราะเราไม่รู้ว่าเมื่อไรควรจะหยุดการเจริญเติบโตของต้นไม้ จึงใช้วิธีที่สองมากกว่าซึ่งในวิธีที่สองนี้เริ่มต้นจะแบ่งตัวอย่าง (Example) ออกเป็น 3 ส่วนด้วยกันคือ

  • ส่วนเรียนรู้สำหรับต้นไม้ (training set) ในส่วนนี้จะนำไปผ่านกระบวนการเรียนรู้ต่างๆ เช่น ID3 เพื่อให้ต้นไม้เจริญเติบโต
  • ส่วนปรับปรุงต้นไม้ให้ถูกต้องยิ่งขึ้น (validating set) ในส่วนนี้จะทำไปผ่านการตัดแต่งเพื่อหลีกเลี่ยงการโอเวอร์ฟิตของสมมติฐาน
  • ส่วนทดสอบ (test set) ในส่วนนี้จะบอกประสิทธิภาพของต้นไม้ว่าดีเท่าใด

ซึ่งในกระบวนการตัดแต่งนั้นจะพิจารณาบัพในต้นไม้ว่าหากตัดบัพใดทิ้งแล้วความแม่นยำใน validating set ไม่ลดลงก็จะตัดทิ้งและจะตัดไปเรื่อยๆจนกว่าจะไม่สามารถตัดทิ้งตามเงื่อนไขได้อีก

การจัดการกับชุดข้อมูลที่นำมาเรียนรู้ที่ให้ค่าลักษณะของตัวแปรมาไม่ครบ

ในบางกรณีข้อมูลที่มีให้มีบางตัวขาดหายไป เช่น การวิเคราะห์โรคของผู้ป่วยอาจต้องใช้ผลเลือดในการวิเคราะห์ แต่ไม่สามารถหามาได้ จึงอาจต้องประมาณผลเลือดโดยการประมาณวิธีหนึ่งคือการใช้ผลเลือดที่คนส่วนใหญ่เป็นมากที่สุดซึ่งถูกใช้โดย Mingers (1989) หรืออีกวิธีคือการวิเคราะห์อัตราส่วนซึ่งถ่วงน้ำหนักการตัดสินใจในแต่ละอย่างด้วยสถิติที่ผ่านมา วิธีนี้ถูกนำมาใช้ใน C4.5 โดย Quinlan (1993)

การจัดการกับตัวแปรต้นที่มีค่าต่อเนื่อง

เมื่อตัวแปรต้นมีค่าต่อเนื่องจำเป็นที่จะต้องมีการแบ่งค่าต่อเนื่องออกมาเป็นช่วงๆแบบไม่ต่อเนื่อง ซึ่งไม่ต่อเนื่องทำให้สามารถประมวลผลได้ด้วยต้นไม้การตัดสินใจ แต่หากต้องการข้อมูลนำเขาและส่งออกที่ต่อเนื่องจริงๆจำเป็นที่จะต้องใช้วิธีอื่นๆ เช่น ข่ายงานประสาทเทียม (Neural Network)

การจัดการกับตัวแปรต้นที่มีราคา

ในปัญหาบางอย่างการที่จะหาตัวแปรต้นมาพิจารณานั้นจำเป็นที่จะต้องลงทุน เช่น การที่จะตรวจสอบว่าผู้ป่วยเป็นโรครึเปล่าอาจต้องรู้ ความดัน อุณหภูมิ ข้อมูลของเลือด ฟิลม์เอ็กซเรย์ ซึ่งข้อมูลจะได้มาเมื่อเสียต้นทุนไปจำนวนหนึ่ง ดังนั้นในการนิยามความดีของตัวแปรต้นที่เหมาะสมสำหรับการสร้างต้นไม้การตัดสินใจจำเป็นที่จะต้องเอาอีกปัจจัยคือ ราคา เข้ามาร่วมพิจารณาด้วย ในปี 1990 Tan และ Schilimmer เสนอค่าความดีของตัวแปรต้นเพื่อใช้ประมวลผลกับการรับรู้ของหุ่นยนต์ผ่านทางเซนเซอร์คือ

 \frac{Gain^{2} (S, A)}{Cost (A)}

อ้างอิง[แก้]

  • Mitchell, Tom. Machine Learning. McGraw-Hill, 1997, p. 52-80.

ดูเพิ่ม[แก้]