การจำแนกแผนผังการตัดสินใจ

การแนะนำ

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

เอนโทรปี

เป้าหมายของการฝึกอบรมคือการค้นหาการแยกที่ดีที่สุดในโหนดเพื่อค้นหาแผนผังที่เหมาะสมที่สุด การแยกทำได้โดยใช้เกณฑ์บางอย่าง เช่น เอนโทรปี

มีคำจำกัดความของเอนโทรปีอยู่มากมาย เช่น:

• เอนโทรปีสอดคล้องกับปริมาณข้อมูลที่มีอยู่ในแหล่งข้อมูล.

• เอนโทรปียังอาจมองว่าเป็นการสุ่มหรือการวัดความประหลาดใจในชุด

• เอนโทรปีเป็นตัวชี้วัดที่ใช้วัดความไม่แน่นอนหรือความไม่บริสุทธิ์ในระบบ

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

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

เอนโทรปี $H$ ของชุด $X$ มีสูตรทางคณิตศาสตร์ดังนี้:

$$H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)$$

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

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

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

ที่ไหน:

• $H(.)$ คือเอนโทรปี

• $Y$ คือจำนวนประชากรก่อนการแยก ซึ่งแสดงถึงโหนดหลัก

• $X$ คือตัวแปรที่เราต้องการใช้สำหรับการแยก

• $x$ เป็นค่าเฉพาะของ X

• $Y[X==x]$ เป็นรายการแยกที่มีค่า $x$ เท่านั้น

ลองยกตัวอย่างที่เหมาะสม:

เราจะคำนวณ Information Gain เมื่อเราแบ่งโหนดหลักโดยใช้ค่าของ X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

ขั้นแรก เราคำนวณเอนโทรปีของโหนดหลัก:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

จากนั้น เราจะคำนวณความน่าจะเป็นภายในของแต่ละโหนดย่อยหลังการแยกโดยใช้ค่าเฉพาะของ X:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

เช่น:

• $H(Y | X = Square)$ : แสดงถึงเอนโทรปีของโหนดลูกแรก

• $H(Y | X = Circle)$ : แสดงถึงเอนโทรปีของโหนดลูกที่สอง

เราเริ่มต้นด้วยโหนดลูกแรก:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

จากนั้นโหนดลูกที่สอง:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

สุดท้าย เราแทนที่เอนโทรปีในสูตร Information Gain:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

ตามที่ระบุไว้ก่อนหน้านี้ วัตถุประสงค์ของการแยกโหนดคือเพื่อเพิ่มการได้รับข้อมูลให้สูงสุด และลดเอนโทรปีในโหนดลูกที่เป็นผลลัพธ์ ในการทำเช่นนี้ เราจำเป็นต้องลองแยกโหนดด้วยชุดอินพุตที่แตกต่างกัน $X_1, X_2, \ldots, Xn$ และเราเก็บเฉพาะการแยกที่เพิ่มการรับข้อมูลสูงสุดเท่านั้น:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

##เมื่อไรจะเลิกแตกแยก.

การแยกโหนดในแผนผังการตัดสินใจเป็นแบบเรียกซ้ำ ดังนั้นจึงต้องมีเกณฑ์ที่เราสามารถใช้เพื่อหยุดการแยก เกณฑ์ที่นำมาใช้มากที่สุดบางส่วนเหล่านี้:

• เมื่อโหนดบริสุทธิ์: H(โหนด) = 0 การแยกโหนดเพิ่มเติมนั้นไม่มีประโยชน์

• จำนวนความลึกสูงสุด: เราสามารถกำหนดความลึกสูงสุดที่โมเดลสามารถเข้าถึงได้ หมายความว่าแม้ว่าโหนดจะไม่บริสุทธิ์ การแยกก็จะหยุดลง

• จำนวนตัวอย่างขั้นต่ำต่อโหนด: นอกจากนี้เรายังกำหนดจำนวนตัวอย่างขั้นต่ำ $N$ ต่อโหนดได้ด้วย หากจำนวนตัวอย่างต่อโหนดเท่ากับ $N$ เราจะหยุดการแยกแม้ว่าโหนดจะไม่บริสุทธิ์ก็ตาม

เมื่อสิ้นสุดการฝึก (การแยก) แต่ละโหนดที่อาศัยจุดสิ้นสุดของแผนผังการตัดสินใจจะถูกเรียกว่า "ลีฟ" เนื่องจากไม่ใช่รากของแผนผังย่อยใดๆ แต่ละลีฟจะเป็นตัวแทนของคลาสผลผลิตที่มีตัวอย่างมากที่สุด

บทสรุป

แผนผังการตัดสินใจเป็นหนึ่งในอัลกอริธึมการเรียนรู้ของเครื่องที่มีชื่อเสียงที่สุด เนื่องจากมีประสิทธิภาพ พื้นหลังที่ใช้งานง่าย และการใช้งานที่เรียบง่าย อัลกอริธึมนี้สามารถใช้กับตัวแปรอิสระเชิงตัวเลข (Gaussian Decision Tree) เพิ่มเติมได้ และสามารถขยายออกไปเพื่อแก้ปัญหาการถดถอยได้เช่นกัน