Định nghĩaTìm gọi qua ví dụTính Entropy của những thuộc tínhĐịnh nghĩa

Cây quyết định (Decision Tree) là một mô hình thuộc team thuật toán học tập có đo lường (Supervised Learning).Tìm gọi thêm về phân loại các thuật toán Machine Learning trên đây.Bạn sẽ xem: bài tập cây đưa ra quyết định có lời giải

Cây đưa ra quyết định là gì?

Cây quyết định (gọi tắt là DT) là quy mô đưa ra ra quyết định dựa trên những câu hỏi.Dưới đây là mô hình DT về một ví dụ tởm điển.Câu hỏi có chơi tennis hay không? quyết định đưa ra dựa trên những yếu tố về thời tiết: outlook, humidity, wind.

Bạn đang xem: Bài tập cây quyết định có đáp án


*

DT được áp dụng vào cả 2 bài toán: Phân các loại (Classification) với Hồi quy (Regression). Mặc dù bài toán phân các loại được thực hiện nhiều hơn.

Có nhiều thuật toán để xây dựng DT, trong bài này ta tò mò một thuật toán nổi tiếng và cơ phiên bản nhất của DT là thuật toán ID3.

Thuật toán ID3

Iterative Dichotomiser 3 (ID3) là thuật toán khét tiếng để xây cất Decision Tree, áp dụng cho câu hỏi Phân các loại (Classification) mà lại tất những các nằm trong tính đặt tại dạng category.

Để dễ nắm bắt ta cùng tò mò thuật toán này qua ví dụ.

Tìm đọc qua ví dụ

Ta có tập Training Data như bảng dưới:

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
52000ccSedanSilverYesNo
62000ccSportBlueYesYes
71000ccSedanBlueNoYes
81000ccSUVSilverNoYes

Data của ta bao gồm 4 thuộc tính: Engine, Type, Color, 4WD.Để thống kê giám sát được DT, ta bắt buộc phân chia những thuộc tính vào các node tấn công giá. Vậy làm sao để hiểu rằng thuộc tính nào quan trọng, nên đặt ở gốc, thuộc tính nào ở nhánh…

Trong thuật toán ID3, những thuộc tính được nhận xét dựa bên trên Hàm số Entropy, hàm số thịnh hành trong toán học tập xác suất.

Hàm số Entropy

Cho một phân phối xác suất của một thay đổi rời rạc $x$ rất có thể nhận $n$ quý giá khác nhau$x_1, x_2, dots, x_n$. Mang sử rằng tỷ lệ để $x$ nhận những giá trị này là $p_i = p(x = x_i)$

Ký hiệu triển lẵm này là $mathbfp = (p_1, p_2, dots, p_n)$.Entropy của bày bán này là:

$$H(mathbfp) = -sum_i=1^n p_i log_2(p_i)quadquad$$

Hàm Entropy được màn biểu diễn dưới dạng trang bị thị như sau:

*

Từ đồ gia dụng thị ta thấy, hàm Entropy vẫn đạt giá bán trị nhỏ nhất nếu tất cả một cực hiếm $p_i = 1$, đạt giá bán trị lớn số 1 nếu tất cả các$p_i$ bằng nhau.Hàm Entropy càng mập thì độ ngẫu nhiên của những biến rời rạc càng cao (càng ko tinh khiết).

Với cây quyết định, ta buộc phải tạo cây như thế nào khiến cho ta nhiều tin tức nhất, có nghĩa là Entropy là cao nhất.

Information Gain

Bài toán của ta trở thành, tại mỗi tầng của cây, cần chọn thuộc tính nào nhằm độ sút Entropy là rẻ nhất.Người ta bao gồm khái niệm Information Gain được tính bằng$$Gain(S,f) = H(S) - H(f,S)$$trong đó:$H(S)$ là Entropy tổng của cục bộ tập data set $S$.$H(f, S)$ là Entropy được xem trên ở trong tính $f$.

Tính Entropy của những thuộc tính

Xét trực thuộc tính Engine

Thuộc tính này hoàn toàn có thể nhận một trong các 2 quý giá 1000cc, 2000cc, tương xứng với 2 child node.Gọi tập hợp những điểm trong mỗi child node này theo lần lượt là$S_1$, $S_2$.

Sắp xếp lại theo nằm trong tính Engine ta tất cả 2 bảng nhỏ.

Engine 1000cc ($S_1$)

IDEngineTypeColor4WDWant?
21000ccSedanSilverYesYes
41000ccSUVBlueNoYes
71000ccSedanBlueNoYes
81000ccSUVSilverNoYes

Engine 2000cc ($S_2$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
32000ccSportBlueNoNo
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

Child node ứng cùng với Engine 1000cc sẽ sở hữu được Entropy = 0 do toàn bộ các giá chỉ trị phần đa là Yes.Ta chỉ việc tính Entropy cùng với Engine 2000cc. Tiếp nối tính Entropy trung bình.Cụ thể như sau:

$$eginalignedH(S_1) &=& 0crH(S_2) &=& -frac24mathcallog_2left(frac24 ight) - frac24mathcallog_2left(frac24 ight)= 1crH(engine, S) &=& frac48H(S_1) + frac48H(S_2) = 0.5endaligned$$

Xét thuộc tính Type

Thuộc tính này rất có thể nhận một trong 3 giá trị SUV, Senda, thể thao tương ứng với 3 child node.Gọi tập hợp các điểm trong những child node này theo lần lượt là$S_u$, $S_e$, $S_p$.

Sắp xếp lại theo ở trong tính Type ta gồm 3 bảng nhỏ.

Type SUV ($S_u$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
41000ccSUVBlueNoYes
81000ccSUVSilverNoYes

Type Sedan ($S_e$)

IDEngineTypeColor4WDWant?
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
71000ccSedanBlueNoYes

Type Sport ($S_p$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
62000ccSportBlueYesYes

Tương tự, ta lần lượt tính Entropy như mặt dưới:

$$eginalignedH(S_u) &=& 0crH(S_e) &=& -frac23mathcallog_2left(frac23 ight) - frac13mathcallog_2left(frac13 ight)approx 0.918crH(S_p) &=& -frac12mathcallog_2left(frac12 ight) - frac12mathcallog_2left(frac12 ight) = 1crH(type, S) &=& frac38H(S_u) + frac38H(S_e) + frac28H(S_p) approx 0.594endaligned$$

Xét nằm trong tính Color

Thuộc tính này rất có thể nhận một trong những 2 cực hiếm Silver, Blue tương xứng với 2 child node.Gọi tập hợp những điểm trong những child node này thứu tự là$S_s$, $S_b$.

Sắp xếp lại theo thuộc tính Color ta có 2 bảng nhỏ.

Color Silver ($S_s$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
81000ccSUVSilverNoYes

Color Blue ($S_b$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
62000ccSportBlueYesYes
71000ccSedanBlueNoYes

Dễ thấy, 2 quý hiếm Silver với Blue đều có tỉ lệ Yes, No giống hệt là 3⁄4 cùng 1⁄4.Do đó ta tính luôn luôn Entropy trung bình:

$$eginalignedH(color, S) &=& -frac34mathcallog_2left(frac34 ight) - frac14mathcallog_2left(frac14 ight) approx 0.811endaligned$$

Xét nằm trong tính 4WD

Thuộc tính này hoàn toàn có thể nhận một trong những 2 quý giá Yes, No tương ứng với 2 child node.Gọi tập hợp các điểm trong mỗi child node này thứu tự là$S_y$, $S_n$.

Sắp xếp lại theo nằm trong tính 4WD ta gồm 2 bảng nhỏ.

4WD Yes ($S_y$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

4WD No ($S_n$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
71000ccSedanBlueNoYes
81000ccSUVSilverNoYes

Tương trường đoản cú Color, ta tính Entropy trung bình:

$$eginalignedH(4wd, S) &=& -frac34mathcallog_2left(frac34 ight) - frac14mathcallog_2left(frac14 ight) approx 0.811endaligned$$

Chọn thuộc tính có Entropy nhỏ dại nhất

Sau lúc tính Entropy vừa phải của 4 nằm trong tính ta thu được:$H(engine, S) = 0.5$$H(type, S) approx 0.594$$H(color, S) approx 0.811$$H(4wd, S) approx 0.811$

Thuộc tính Engine có giá trị Entropy bé dại nhất yêu cầu ta chọn là node review đầu tiên.Với Engine 1000cc, toàn bộ các data đều phải sở hữu giá trị Yes, vày vậy ta chiếm được node là Yes sinh sống nhánh 1000cc.Ta thường xuyên tính cho nhánh Engine 2000cc cùng với tập data nhỏ hơn là

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
32000ccSportBlueNoNo
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

Tương từ bỏ ta theo thứ tự tính Entropy mang lại 3 thuộc tính là: Type, Color, 4WD

Với nằm trong tính Type:$$eginalignedH(S_u) &=& 0crH(S_e) &=& 0crH(S_p) &=& -frac12mathcallog_2left(frac12 ight) - frac12mathcallog_2left(frac12 ight)= 1crH(type, S) &=& frac14H(S_u) + frac14H(S_e) + frac24H(S_p) = 0.5endaligned$$

Với trực thuộc tính Color:Do 2 cực hiếm Silver và Blue có cùng tỉ trọng Yes, No là 1⁄2 cùng 1⁄2.$$eginalignedH(color, S) &=& -frac12mathcallog_2left(frac12 ight) - frac12mathcallog_2left(frac12 ight)= 1endaligned$$

Với trực thuộc tính 4WD:$$eginalignedH(S_y) &=& -frac23mathcallog_2left(frac23 ight) - frac13mathcallog_2left(frac13 ight) approx 0.918crH(S_n) &=& 0crH(4wd, S) &=& frac34H(S_y) + frac14H(S_n) approx 0.688endaligned$$

Vậy ta chọn Type là node review tiếp theo.

Xem thêm: Lý Thuyết Công Nghệ 11: Bài 3 : Thực Hành Vẽ Các Hình Chiếu Của Vật Thể Đơn Giản

Với trường thích hợp Type là SUV hoặc Sedan, ta gồm ngay node lá vì chỉ gồm một kết quả.Với trường hòa hợp Type là Sport, vì thuộc tính color là tương đương nhau với tất cả data, ta chọn node đánh giá tiếp theo là 4WD.