ต้นไม้ตัดสินใจ — Entropy, Gini และ Random Forest

ต้นไม้ตัดสินใจทำนายผลโดยการถามคำถามเป็นลำดับ เช่น "ทำแบบทดสอบฝึกหัดเสร็จหรือยัง?" หรือ "รายได้มากกว่า $50{,}000$ หรือไม่?" ในต้นไม้สำหรับการจำแนกประเภท คำถามที่ดีที่สุดมักเป็นคำถามที่ทำให้โหนดลูกมีความปะปนน้อยกว่าโหนดแม่ นี่คือจุดที่ entropy และ Gini impurity เข้ามามีบทบาท

Random forest ใช้แนวคิดพื้นฐานเดียวกัน แต่แทนที่จะเชื่อต้นไม้เพียงต้นเดียว มันจะเฉลี่ยผลจากต้นไม้หลายต้น หากคุณต้องการแค่ใจความสำคัญ ให้จำไว้ว่า entropy และ Gini ช่วยให้ต้นไม้เลือกการแบ่ง ส่วน random forest ช่วยลดความไม่เสถียรของต้นไม้เดี่ยว

Entropy และ Gini ของต้นไม้ตัดสินใจวัดอะไร

Entropy และ Gini impurity เป็นวิธีให้คะแนนว่าโหนดสำหรับการจำแนกประเภทมีความปะปนของคลาสมากแค่ไหน

ถ้าโหนดหนึ่งมีความน่าจะเป็นของคลาสเป็น $p_1, p_2, \dots, p_k$ สูตร entropy ที่ใช้กันทั่วไปคือ

$$H = -\sum_{i=1}^k p_i \log_2 p_i$$

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

Gini impurity คือ

$$G = 1 - \sum_{i=1}^k p_i^2$$

ทั้งสองค่านี้จะเป็น $0$ เมื่อโหนดบริสุทธิ์สมบูรณ์ ทั้งคู่จะมีค่ามากขึ้นเมื่อคลาสต่าง ๆ ปะปนกันมากขึ้น

ในทางปฏิบัติ entropy และ Gini มักจัดอันดับการแบ่งที่เป็นไปได้ได้คล้ายกัน Entropy มีความหมายตรงตามทฤษฎีสารสนเทศ ส่วน Gini คำนวณได้ง่ายกว่าเล็กน้อย

ต้นไม้ตัดสินใจเลือกการแบ่งอย่างไร

สำหรับ entropy เกณฑ์ที่ใช้บ่อยคือ information gain:

$$\text{Information Gain} = H(\text{parent}) - \sum_j \frac{n_j}{n} H(\text{child}_j)$$

ตรงนี้ $n$ คือจำนวนตัวอย่างในโหนดแม่ และ $n_j$ คือจำนวนตัวอย่างในโหนดลูกที่ $j$

สำหรับ Gini แนวคิดก็ขนานกัน คือคำนวณความไม่บริสุทธิ์ถ่วงน้ำหนักของโหนดลูก แล้วเลือกการแบ่งที่ลดค่านี้ได้มากที่สุด

เงื่อนไขของปัญหาสำคัญมาก: entropy และ Gini เป็นมาตรฐานสำหรับต้นไม้จำแนกประเภท ส่วนต้นไม้ถดถอยมักใช้เกณฑ์คนละแบบ เช่น การลดความแปรปรวน เพราะตัวแปรเป้าหมายเป็นค่าตัวเลข ไม่ใช่หมวดหมู่

ตัวอย่างคำนวณ: Entropy และ Gini สำหรับการแบ่งหนึ่งครั้ง

สมมติว่าโหนดหนึ่งมีตัวอย่างฝึกสอน $6$ ตัวอย่างสำหรับการทำนายผ่าน/ไม่ผ่าน:

• $3$ ตัวอย่างเป็น Pass
• $3$ ตัวอย่างเป็น Fail

ดังนั้นโหนดแม่จึงมีการปะปนกันเท่า ๆ กัน

ค่า entropy คือ

$$H_{\text{parent}} = -\frac{3}{6}\log_2\left(\frac{3}{6}\right) - \frac{3}{6}\log_2\left(\frac{3}{6}\right) = 1$$

ค่า Gini impurity คือ

$$G_{\text{parent}} = 1 - \left(\frac{3}{6}\right)^2 - \left(\frac{3}{6}\right)^2 = 0.5$$

ตอนนี้ลองทดสอบการแบ่ง "ทำแบบทดสอบฝึกหัดเสร็จหรือยัง?"

• กิ่ง Yes: มี $4$ ตัวอย่าง โดยเป็น Pass $3$ และ Fail $1$
• กิ่ง No: มี $2$ ตัวอย่าง โดยเป็น Pass $0$ และ Fail $2$

สำหรับกิ่ง Yes,

$$H_{\text{yes}} = -\frac{3}{4}\log_2\left(\frac{3}{4}\right) - \frac{1}{4}\log_2\left(\frac{1}{4}\right) \approx 0.811$$

และ

$$G_{\text{yes}} = 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 = 0.375$$

สำหรับกิ่ง No โหนดนี้บริสุทธิ์ ดังนั้น

$$H_{\text{no}} = 0, \qquad G_{\text{no}} = 0$$

ค่า entropy ถ่วงน้ำหนักหลังการแบ่งคือ

$$\frac{4}{6}(0.811) + \frac{2}{6}(0) \approx 0.541$$

ดังนั้น information gain คือ

$$1 - 0.541 \approx 0.459$$

ค่า Gini ถ่วงน้ำหนักหลังการแบ่งคือ

$$\frac{4}{6}(0.375) + \frac{2}{6}(0) = 0.25$$

ดังนั้นการลดลงของ Gini คือ

$$0.5 - 0.25 = 0.25$$

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

ทำไมต้นไม้ตัดสินใจจึงเข้าใจได้ง่ายในเชิงสัญชาตญาณ

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

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

ทำไม Random Forest มักทำงานได้ดีกว่า

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

Random forest ลดความไม่เสถียรนั้นด้วยการสร้างต้นไม้หลายต้นแทนที่จะมีเพียงต้นเดียว สูตรที่ใช้กันทั่วไปคือ:

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

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

ข้อแลกเปลี่ยนนั้นตรงไปตรงมา Random forest มักแม่นยำและเสถียรกว่าต้นไม้เดี่ยว แต่ก็อธิบายได้ยากกว่าในรูปของกฎชุดเดียวที่ชัดเจน

ข้อผิดพลาดที่พบบ่อยกับต้นไม้ตัดสินใจ

คิดว่า Entropy และ Gini เป็นโมเดลทำนายคนละแบบ

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

ลืมเงื่อนไขว่าเป็นงานจำแนกประเภท

Entropy และ Gini เป็นมาตรฐานสำหรับต้นไม้จำแนกประเภท ถ้าตัวแปรเป้าหมายเป็นค่าตัวเลข ต้นไม้มักใช้เกณฑ์ที่อิงกับความแปรปรวนหรือความคลาดเคลื่อนแทน

พยายามไล่หาความบริสุทธิ์สมบูรณ์ลึกเกินไป

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

คิดว่า Random Forest อธิบายตัวเองได้

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

ควรใช้ต้นไม้ตัดสินใจหรือ Random Forest เมื่อไร

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

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

ลองทำโจทย์ที่คล้ายกัน

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