อัลกอริทึมแผนผังการตัดสินใจ – คู่มือฉบับสมบูรณ์

บทความนี้เผยแพร่โดยเป็นส่วนหนึ่งของไฟล์ Blogathon วิทยาศาสตร์ข้อมูล

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

เนื้อหา

1. ต้นไม้การตัดสินใจคืออะไร?

2. ตัวอย่างแผนผังการตัดสินใจ

3. เอนโทรปี

4. ข้อมูลที่ได้รับ

5. เมื่อใดควรหยุดการแยก

6. จะหยุดฟิตได้อย่างไร?

• ความลึกสูงสุด
• min_samples_split
• min_samples_leaf
• max_features

7. การตัดแต่งกิ่ง

• หลังตัดแต่งกิ่ง
• ก่อนตัดแต่งกิ่ง

8. อ้างอิงท้ายเรื่อง

ต้นไม้การตัดสินใจคืออะไร?

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

1 รูปภาพ

ก่อนเรียนรู้เพิ่มเติมเกี่ยวกับแผนผังการตัดสินใจ มาทำความคุ้นเคยกับคำศัพท์บางคำก่อน

โหนดราก – เป็นโหนดที่จุดเริ่มต้นของแผนผังการตัดสินใจจากโหนดนี้ ประชากรเริ่มแบ่งตามลักษณะต่างๆ

โหนดการตัดสินใจ – โหนดที่เราได้รับหลังจากแยกโหนดรูทเรียกว่าโหนดการตัดสินใจ

โหนดใบ – โหนดที่ไม่สามารถแยกออกได้อีกเรียกว่าโหนดปลายสุดหรือโหนดปลายทาง

ต้นไม้ย่อย – เช่นเดียวกับส่วนเล็ก ๆ ของกราฟที่เรียกว่ากราฟย่อย ส่วนย่อยของแผนผังการตัดสินใจนี้เรียกว่าแผนผังย่อย

การตัด – ไม่มีอะไรนอกจากการตัดโหนดบางส่วนเพื่อหยุดการทำงานมากเกินไป

2 รูปภาพ

ตัวอย่างต้นไม้ตัดสินใจ

มาทำความเข้าใจแผนผังการตัดสินใจโดยใช้ตัวอย่าง

3 รูปภาพ

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

ในแผนภาพด้านล่าง ต้นไม้จะถามก่อนว่าสภาพอากาศเป็นอย่างไร? มีแดด มีเมฆมาก หรือฝนตกหรือไม่? ถ้าใช่ก็จะไปที่คุณสมบัติถัดไปคือความชื้นและลม มันจะตรวจสอบอีกครั้งว่ามีลมแรงหรืออ่อนถ้าเป็นลมอ่อนและฝนตกแล้วบุคคลนั้นก็สามารถไปเล่นได้

4 รูปภาพ

คุณสังเกตเห็นอะไรในผังงานด้านบนหรือไม่? เราจะเห็นว่าถ้า อากาศมีเมฆมาก แล้วเราต้องไปเล่น ทำไมไม่แยกออกไปมากกว่านี้? ทำไมมันหยุดอยู่ที่นั่น?

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

เป้าหมายของการเรียนรู้ของเครื่องคือการลดความไม่แน่นอนหรือความผิดปกติจากชุดข้อมูล และด้วยเหตุนี้ เราใช้แผนผังการตัดสินใจ

ตอนนี้คุณต้องคิดว่าฉันจะรู้ได้อย่างไรว่ารูตโหนดควรเป็นอย่างไร โหนดการตัดสินใจควรเป็นอย่างไร เมื่อไหร่ฉันควรหยุดแยก? ในการตัดสินใจ มีเมตริกที่เรียกว่า "เอนโทรปี" ซึ่งเป็นปริมาณความไม่แน่นอนในชุดข้อมูล

เอนโทรปี

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

สมมติว่าคุณมีกลุ่มเพื่อนที่ตัดสินใจว่าจะดูหนังเรื่องไหนด้วยกันในวันอาทิตย์ มี 2 ​​ตัวเลือกสำหรับภาพยนตร์ หนึ่งคือ “ลูซี่” และที่สองคือ "ไททานิค" และตอนนี้ทุกคนต้องบอกทางเลือกของตน หลังจากที่ทุกคนให้คำตอบแล้วเราจะเห็นว่า “ลูซี่” ได้ 4 โหวต และ “ไททานิค” ได้ 5 โหวต. ตอนนี้เราดูหนังเรื่องไหน? เลือกหนังได้ 1 เรื่องไม่ยากเลย เพราะคะแนนโหวตของหนังทั้งสองเรื่องค่อนข้างเท่ากัน

นี่คือสิ่งที่เรียกว่าความไม่เป็นระเบียบ มีคะแนนโหวตเท่ากันสำหรับภาพยนตร์ทั้งสองเรื่อง และเราไม่สามารถตัดสินใจได้จริงๆ ว่าควรดูหนังเรื่องไหน คงจะง่ายกว่านี้มากหากการโหวตของ “Lucy” เป็น 8 และสำหรับ “Titanic” เป็น 2 ในที่นี้ เราสามารถพูดได้อย่างง่ายดายว่าคะแนนโหวตส่วนใหญ่สำหรับ “Lucy” ดังนั้นทุกคนจะได้ชมภาพยนตร์เรื่องนี้

ในแผนผังการตัดสินใจ ผลลัพธ์ส่วนใหญ่เป็น "ใช่" หรือ "ไม่ใช่"

สูตรสำหรับเอนโทรปีแสดงอยู่ด้านล่าง:

ที่นี่ p₊ คือความน่าจะเป็นของชั้นบวก

p_- คือความน่าจะเป็นของชั้นลบ

S เป็นสับเซตของตัวอย่างการฝึก

Decision Trees ใช้เอนโทรปีอย่างไร?

ตอนนี้เรารู้แล้วว่าเอนโทรปีคืออะไรและสูตรของมันคืออะไร ต่อไป เราต้องรู้ว่ามันทำงานอย่างไรในอัลกอริธึมนี้

โดยทั่วไปแล้วเอนโทรปีจะวัดสิ่งเจือปนของโหนด สิ่งเจือปนคือระดับของการสุ่ม มันบอกว่าข้อมูลของเราสุ่มได้อย่างไร อา แยกย่อยบริสุทธิ์ หมายความว่าคุณควรได้รับ "ใช่" หรือคุณควรได้รับ "ไม่"

สมมติว่า ลักษณะ มี 8 "ใช่" และ 4 "ไม่ใช่" ในขั้นต้น หลังจากแยกโหนดด้านซ้ายออกแล้ว ได้ 5 'ใช่' และ 2 'ไม่' ในขณะที่โหนดขวา ได้ 3 'ใช่' และ 2 'ไม่'

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

ในการตรวจสอบสิ่งเจือปนของคุณสมบัติ 2 และคุณสมบัติ 3 เราจะใช้ความช่วยเหลือสำหรับสูตรเอนโทรปี

ที่มาของภาพ: ผู้แต่ง

สำหรับคุณลักษณะที่ 3

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

โปรดจำไว้เสมอว่ายิ่งเอนโทรปีสูงเท่าใด ความบริสุทธิ์ก็จะยิ่งต่ำลงเท่านั้น และยิ่งสูงเท่าใดก็จะยิ่งเป็นมลทิน

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

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

ข้อมูลที่ได้รับ

การรับข้อมูลจะวัดการลดลงของความไม่แน่นอนจากคุณลักษณะบางอย่าง และยังเป็นปัจจัยในการตัดสินใจว่าควรเลือกแอตทริบิวต์ใดเป็นโหนดการตัดสินใจหรือโหนดราก

มันเป็นเพียงเอนโทรปีของชุดข้อมูลทั้งหมด – เอนโทรปีของชุดข้อมูลที่กำหนดคุณลักษณะบางอย่าง

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

ตอนนี้เรามีสองคุณสมบัติที่จะทำนายว่าเขา/เธอจะไปยิมหรือไม่

คุณลักษณะ 1 คือ "พลังงาน" ซึ่งใช้สองค่า "สูงและต่ำ"

คุณลักษณะ 2 คือ "แรงจูงใจ" ซึ่งได้ 3 ค่า “ไม่มีแรงจูงใจ”, “เป็นกลาง” และ “มีแรงจูงใจสูง”

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

ที่มาของภาพ: ผู้แต่ง

ลองคำนวณเอนโทรปี:

ในการดูค่าเฉลี่ยถ่วงน้ำหนักของเอนโทรปีของแต่ละโหนด เราจะทำดังนี้:

ตอนนี้เรามีค่าของ E(Parent) และ E(Parent|Energy) ข้อมูลที่ได้รับจะเป็น:

เอนโทรปีของผู้ปกครองของเราอยู่ใกล้ 0.99 และหลังจากดูค่าของข้อมูลที่ได้รับ เราสามารถพูดได้ว่าเอนโทรปีของชุดข้อมูลจะลดลง 0.37 หากเราสร้าง "พลังงาน" เป็นโหนดรูทของเรา

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

ที่มาของภาพ: ผู้แต่ง

ลองคำนวณเอนโทรปีที่นี่:

ในการดูค่าเฉลี่ยถ่วงน้ำหนักของเอนโทรปีของแต่ละโหนด เราจะทำดังนี้:

ตอนนี้เรามีค่าของ E(Parent) และ E(Parent|Motivation) ข้อมูลที่ได้รับจะเป็น:

ตอนนี้เราเห็นว่าคุณลักษณะ "พลังงาน" ให้การลดลงมากกว่า 0.37 มากกว่าคุณลักษณะ "แรงจูงใจ" ดังนั้นเราจะเลือกคุณสมบัติที่มีการรับข้อมูลสูงสุดแล้วแยกโหนดตามคุณสมบัตินั้น

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

เมื่อไหร่จะหยุดแยก?

คุณต้องถามคำถามนี้กับตัวเองว่าเมื่อไหร่เราจะหยุดปลูกต้นไม้ของเรา? โดยปกติ ชุดข้อมูลในโลกแห่งความเป็นจริงจะมีคุณลักษณะจำนวนมาก ซึ่งจะส่งผลให้มีการแยกส่วนจำนวนมาก ซึ่งจะทำให้ต้นไม้ใหญ่โต ต้นไม้ดังกล่าวต้องใช้เวลาในการสร้างและอาจนำไปสู่การ overfitting นั่นหมายความว่าทรีจะให้ความแม่นยำที่ดีมากในชุดข้อมูลการฝึกอบรม แต่จะให้ความแม่นยำที่ไม่ดีในข้อมูลการทดสอบ

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

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

มีไฮเปอร์พารามิเตอร์เพิ่มเติมเช่น:

min_samples_leaf – หมายถึงจำนวนตัวอย่างขั้นต่ำที่ต้องอยู่ในโหนดปลายสุด ยิ่งคุณเพิ่มจำนวนมากขึ้นเท่าไร โอกาสที่ร่างกายจะฟิตมากเกินไปก็ยิ่งมากขึ้นเท่านั้น

max_features – ช่วยให้เราตัดสินใจได้ว่าต้องพิจารณาคุณลักษณะจำนวนเท่าใดเมื่อมองหาการแบ่งที่ดีที่สุด

หากต้องการอ่านเพิ่มเติมเกี่ยวกับไฮเปอร์พารามิเตอร์เหล่านี้ คุณสามารถอ่านได้  โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม.

การตัด

เป็นอีกวิธีหนึ่งที่สามารถช่วยให้เราหลีกเลี่ยงการใส่มากเกินไป ช่วยในการปรับปรุงประสิทธิภาพของทรีโดยการตัดโหนดหรือโหนดย่อยที่ไม่สำคัญ มันเอากิ่งที่มีความสำคัญต่ำมาก

การตัดแต่งกิ่งมี 2 วิธีหลักๆ คือ

(i) ก่อนตัดแต่งกิ่ง – เราสามารถหยุดปลูกต้นไม้ก่อนหน้านี้ได้ ซึ่งหมายความว่าเราสามารถตัด/ลบ/ตัดโหนดได้หากมีความสำคัญต่ำ ในขณะที่เติบโต ต้นไม้.

(ii) หลังตัดแต่งกิ่ง – ครั้งหนึ่งของเรา ต้นไม้ถูกสร้างขึ้นมาอย่างล้ำลึกเราสามารถเริ่มตัดแต่งโหนดตามความสำคัญของโหนดได้

เชิงอรรถ

โดยสรุป ในบทความนี้ เราได้เรียนรู้เกี่ยวกับแผนผังการตัดสินใจ ต้นไม้แยกโหนดบนพื้นฐานอะไรและจะหยุดการ overfitting ได้อย่างไร ทำไมการถดถอยเชิงเส้นไม่ทำงานในกรณีของปัญหาการจำแนกประเภท

ในบทความถัดไป ผมจะอธิบายเรื่อง Random forests ซึ่งเป็นเทคนิคใหม่เพื่อหลีกเลี่ยงการ overfitting
เพื่อตรวจสอบการใช้งานต้นไม้การตัดสินใจทั้งหมด โปรดดูที่ my Github กรุ

แจ้งให้เราทราบหากคุณมีคำถามใด ๆ ในความคิดเห็นด้านล่าง

เกี่ยวกับผู้เขียน

สื่อที่แสดงในบทความนี้ไม่ใช่ของ Analytics Vidhya และใช้ดุลยพินิจของผู้เขียน

แหล่งรูปภาพ

1. ภาพที่ 1 – https://wiki.pathmind.com/decision-tree
2. ภาพที่ 2 – https://wiki.pathmind.com/decision-tree
3. ภาพที่ 3 – www.hackerearth.com
4. ภาพที่ 4 – www.hackerearth.com

ที่เกี่ยวข้อง

ที่มา: https://www.analyticsvidhya.com/blog/2021/08/decision-tree-algorithm/