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

อัปเดตบน September 03, 2024 2 นาทีอ่าน

การแนะนำ

แผนผังการตัดสินใจ (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) เพิ่มเติมได้ และสามารถขยายออกไปเพื่อแก้ปัญหาการถดถอยได้เช่นกัน