Bài tập cây quyết định có lời giải

Định nghĩaTìm hiểu qua ví dụTính Entropy của các ở trong tínhĐịnh nghĩa

Cây quyết định (Decision Tree) là một quy mô thuộc team thuật tân oán Học có giám sát và đo lường (Supervised Learning).Tìm phát âm thêm về phân một số loại các thuật tân oán Machine Learning tại trên đây.Quý Khách vẫn xem: Những 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ô chỉ dẫn quyết định dựa trên các câu hỏi.Dưới đó là quy mô DT về một ví dụ kinh khủng.Câu hỏi bao gồm chơi tennis tốt không? Quyết định giới thiệu dựa trên các nhân tố về thời tiết: outlook, humidity, wind.

You watching: Bài tập cây quyết định có lời giải


*

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). Tuy nhiên bài xích tân oán phân một số loại được sử dụng nhiều hơn nữa.

Có các thuật toán thù để phát hành DT, trong bài bác này ta mày mò một thuật tân oán lừng danh với cơ bạn dạng độc nhất của DT là thuật toán ID3.

Thuật toán thù ID3

Iterative sầu Dichotomiser 3 (ID3) là thuật tân oán lừng danh nhằm xuất bản Decision Tree, vận dụng mang lại bài bác tân oán Phân nhiều loại (Classification) mà lại vớ những các ở trong tính đặt ở dạng category.

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

Tìm phát âm qua ví dụ

Ta tất cả tập Training Data nlỗi bảng dưới:

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

Data của ta gồm 4 ở trong tính: Engine, Type, màu sắc, 4WD.Để tính toán thù được DT, ta nên phân chia những thuộc tính vào những node đánh giá. Vậy làm sao nhằm biết được nằm trong tính nào đặc biệt quan trọng, cần đặt tại gốc, trực thuộc tính như thế nào ngơi nghỉ nhánh…

Trong thuật toán thù ID3, các thuộc tính được Đánh Giá dựa vào Hàm số Entropy, hàm số thịnh hành vào tân oán học tập Tỷ Lệ.

Hàm số Entropy

Cho một phân păn năn Xác Suất của một biến đổi tránh rạc $x$ hoàn toàn có thể thừa nhận $n$ quý giá khác nhau$x_1, x_2, dots, x_n$. Giả sử rằng Phần Trăm để $x$ thừa nhận những quý hiếm này là $p_i = p(x = x_i)$

Ký hiệu phân phối này là $mathbfp = (p_1, p_2, dots, p_n)$.Entropy của phân pân hậ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 đồ vật thị như sau:

*

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

Với cây đưa ra quyết định, ta buộc phải sản xuất cây ra sao làm cho ta nhiều biết tin duy nhất, tức là Entropy là cao nhất.

Information Gain

Bài toán của ta đổi thay, trên từng tầng của cây, nên lựa chọn trực thuộc tính làm sao nhằm độ giảm Entropy là rẻ độc nhất vô nhị.Người ta tất cả định nghĩa Information Gain được xem bằng$$Gain(S,f) = H(S) - H(f,S)$$trong đó:$H(S)$ là Entropy tổng của toàn bộ tập data set $S$.$H(f, S)$ là Entropy được xem bên trên nằm trong tính $f$.

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

Xét ở trong tính Engine

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

See more: Thiệp 20/10 Tự Làm - 5 Ý Tưởng Làm Thiệp Cho Ngày 20/10 Dễ Dàng Nhất

Sắp xếp lại theo ở trong tính Engine ta bao 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ẽ có được Entropy = 0 vày tất cả các quý hiếm đều là Yes.Ta chỉ việc tính Entropy cùng với Engine 2000cc. Sau kia tính Entropy mức độ vừa phải.Cụ thể nlỗi sau:

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

Xét ở trong tính Type

Thuộc tính này có thể nhấn một trong những 3 giá trị SUV, Senda, Sport tương xứng với 3 child node.Call tập hòa hợp các điểm trong mỗi child node này theo thứ tự là$S_u$, $S_e$, $S_p$.

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

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 hệt như bên dưới:

$$eginalignedH(S_u) &=và 0crH(S_e) &=& -frac23mathcallog_2left(frac23 ight) - frac13mathcallog_2left(frac13 ight)approx 0.918crH(S_p) &=và -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 trực thuộc tính Color

Thuộc tính này có thể dìm một trong các 2 cực hiếm Silver, Blue tương xứng cùng với 2 child node.gọi tập vừa lòng các điểm trong mỗi child node này theo thứ tự là$S_s$, $S_b$.

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

Color Silver ($S_s$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
81000ccSUVSilverNoYes

Màu sắc Blue ($S_b$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
62000ccSportBlueYesYes
71000ccSedanBlueNoYes

Dễ thấy, 2 quý giá Silver và Blue đều sở hữu tỉ lệ Yes, No tương đồng 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 nằm trong tính 4WD

Thuộc tính này hoàn toàn có thể dìm một trong các 2 cực hiếm Yes, No khớp ứng với 2 child node.call tập vừa lòng 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 ở trong tính 4WD ta có 2 bảng bé dại.

4WD Yes ($S_y$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

4WD No ($S_n$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
71000ccSedanBlueNoYes
81000ccSUVSilverNoYes

Tương từ bỏ màu sắc, 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 bé dại nhất

Sau Lúc tính Entropy mức độ vừa phải của 4 ở 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ó mức giá trị Entropy nhỏ tuổi độc nhất vô nhị đề xuất ta lựa chọn là node đánh giá thứ nhất.Với Engine 1000cc, toàn bộ những data đều có quý hiếm Yes, vày vậy ta chiếm được node là Yes nghỉ ngơi nhánh 1000cc.Ta liên tiếp tính mang lại nhánh Engine 2000cc với tập data nhỏ rộng là

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
32000ccSportBlueNoNo
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

Tương từ ta theo lần lượt tính Entropy mang lại 3 ở trong tính là: Type, Color, 4WD

Với trực thuộc 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 ở trong tính Color:Do 2 quý hiếm Silver với Blue tất cả thuộc tỉ lệ thành phần Yes, No là 1⁄2 cùng 1⁄2.$$eginalignedH(color, S) &=& -frac12mathcallog_2left(frac12 ight) - frac12mathcallog_2left(frac12 ight)= 1endaligned$$

Với nằm trong tính 4WD:$$eginalignedH(S_y) &=& -frac23mathcallog_2left(frac23 ight) - frac13mathcallog_2left(frac13 ight) approx 0.918crH(S_n) &=& 0crH(4wd, S) &=và frac34H(S_y) + frac14H(S_n) approx 0.688endaligned$$

Vậy ta chọn Type là node Review tiếp sau.

See more: Tổng Hợp Những Món Ăn Đặc Sản Miền Bắc Việt Nam, Top 10 Đặc Sản Miền Bắc Tốt Cho Sức Khỏe

Với trường thích hợp Type là SUV hoặc Sedan, ta gồm ngay node lá vị chỉ tất cả một công dụng.Với ngôi trường hợp Type là Thể Thao, vì chưng ở trong tính Màu sắc là tương tự nhau với tất cả data, ta chọn node review tiếp theo là 4WD.