Định nghĩaTìm đọc 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 quy mô thuộc đội thuật toán học có giám sát (Supervised Learning).Tìm phát âm thêm về phân loại những thuật toán Machine Learning tại đây.Bạn đang xem: bài tập cây ra quyết định có lời giải

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

Cây quyết định (gọi tắt là DT) là mô hình đưa ra ra quyết định dựa trên những câu hỏi.Dưới đó là mô hình DT về một ví dụ tởm điển.Câu hỏi có đánh tennis hay không? ra 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ả hai bài toán: Phân một số loại (Classification) với Hồi quy (Regression). Mặc dù bài toán phân loại được sử dụng nhiều hơn.

Có các thuật toán để kiến thiết DT, trong bài bác này ta tìm hiểu một thuật toán lừng danh 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 lừng danh để tạo ra Decision Tree, áp dụng cho vấn đề Phân các loại (Classification) cơ mà tất những các ở trong tính đặt ở dạng category.

Để dễ nắm bắt ta cùng tìm hiểu 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 tất cả 4 trực thuộc tính: Engine, Type, Color, 4WD.Để đo lường được DT, ta buộc phải phân chia các thuộc tính vào những node đánh giá. Vậy làm sao để biết được thuộc tính nào quan trọng, nên đặt tại gốc, thuộc tính làm sao ở nhánh…

Trong thuật toán ID3, các thuộc tính được reviews dựa bên trên Hàm số Entropy, hàm số phổ biến trong toán học xác suất.

Hàm số Entropy

Cho một phân phối phần trăm của một vươn lên là rời rạc $x$ có thể nhận $n$ giá trị khác nhau$x_1, x_2, dots, x_n$. Trả sử rằng phần trăm để $x$ nhận các giá trị này là $p_i = p(x = x_i)$

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

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

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

*

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

Với cây quyết định, ta đề xuất tạo cây như vậy nào để cho ta nhiều tin tức nhất, tức là Entropy là cao nhất.

Information Gain

Bài toán của ta trở thành, tại từng tầng của cây, đề nghị chọn nằm trong tính nào để độ bớt Entropy là rẻ nhất.Người ta 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 mix $S$.$H(f, S)$ là Entropy được tính trên ở trong tính $f$.

Tính Entropy của các thuộc tính

Xét nằm trong tính Engine

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

Sắp xếp lại theo ở trong tính Engine ta gồm 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 với Engine 1000cc sẽ sở hữu được Entropy = 0 do tất cả các giá trị mọi là Yes.Ta chỉ câu hỏi tính Entropy với Engine 2000cc. Tiếp đến 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 1 trong những 3 cực hiếm SUV, Senda, sport tương ứng cùng với 3 child node.Gọi tập hợp các điểm trong những child node này thứu tự là$S_u$, $S_e$, $S_p$.

Sắp xếp lại theo thuộc tính Type ta tất cả 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 theo thứ tự tính Entropy như bên 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 thuộc tính Color

Thuộc tính này có thể nhận một trong các 2 giá trị Silver, Blue tương xứng với 2 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_s$, $S_b$.

Sắp xếp lại theo trực thuộc tính Color ta tất 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 giá trị Silver cùng Blue đều sở hữu tỉ lệ Yes, No đồng nhất là 3⁄4 và 1⁄4.Do kia 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 trực thuộc tính 4WD

Thuộc tính này rất có thể nhận 1 trong 2 giá trị Yes, No khớp ứng với 2 child node.Gọi tập hợp những điểm trong những child node này theo thứ tự là$S_y$, $S_n$.

Sắp xếp lại theo thuộc 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 tự Color, ta tính Entropy trung bình:

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

Chọn trực thuộc tính gồm Entropy nhỏ tuổi nhất

Sau khi tính Entropy mức độ vừa phải của 4 thuộc 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 lựa chọn là node review đầu tiên.Với Engine 1000cc, toàn bộ các data đều có giá trị Yes, vị vậy ta nhận được node là Yes sinh hoạt nhánh 1000cc.Ta liên tiếp tính đến nhánh Engine 2000cc cùng với tập data bé dại hơn là

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
32000ccSportBlueNoNo
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

Tương tự ta thứu tự tính Entropy cho 3 trực 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 nằm trong tính Color:Do 2 cực hiếm Silver với Blue có cùng tỉ trọng Yes, No là 1⁄2 và 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 reviews tiếp theo.

Xem thêm: Điểm Chuẩn Đại Học Thăng Long 2015 : Trường Đh Thăng Long, Điểm Chuẩn 2015: Trường Đh Thăng Long

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