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

     
Định nghĩa

Cây quyết định (Decision Tree) là một quy mô thuộc team thuật toán học tập có thống kê giám sát (Supervised Learning).Tìm hiểu thêm về phân loại những thuật toán Machine Learning tại đây.

Bạn đang xem: Cây quyết định là gì

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

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


*

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

Có nhiều thuật toán để xây dừng DT, trong bài này ta mày mò một thuật toán khét tiếng và cơ bạn dạng 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 để xuất bản Decision Tree, vận dụng cho câu hỏi Phân các loại (Classification) mà lại tất các các trực thuộc tính để tại dạng category.

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

Tìm hiểu qua ví dụ

Ta gồm 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 nằm trong tính: Engine, Type, Color, 4WD.Để giám sát và đo lường được DT, ta phải phân chia những thuộc tính vào những node đánh giá. Vậy làm sao để biết được thuộc tính làm sao quan trọng, nên đặt tại gốc, nằm trong tính nào ở nhánh…

Trong thuật toán ID3, những thuộc tính được đánh giá 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 biến hóa rời rốc $x$ có thể nhận $n$ giá trị khác nhau$x_1, x_2, dots, x_n$. Mang sử rằng xác suất để $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 phân phối 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 thị như sau:

*

Từ đồ dùng thị ta thấy, hàm Entropy đang đạt giá bán trị nhỏ dại nhất nếu có một giá trị $p_i = 1$, đạt giá bán trị lớn số 1 nếu toàn bộ các$p_i$ bởi nhau.Hàm Entropy càng phệ 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 yêu cầu tạo cây như vậy nào khiến 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 mỗi tầng của cây, buộc phải chọn thuộc tính nào nhằm độ bớt Entropy là tốt 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 toàn cục tập data mix $S$.$H(f, S)$ là Entropy được tính trên trực thuộc tính $f$.

Do $H(S)$ là không đổi với từng tầng, ta lựa chọn thuộc tính $f$ gồm Entropy nhỏ tuổi nhất nhằm thu được $Gain(S,f)$ to nhất.

Xem thêm: Cách Lấy Lại Số Thẻ Bảo Hiểm Y Tế Đơn Giản, Xin Mã Số Thẻ Bảo Hiểm Y Tế

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 1 trong 2 quý hiếm 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 thứu tự là$S_1$, $S_2$.

Sắp xếp lại theo thuộc 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ẽ có Entropy = 0 do tất cả các giá bán trị phần đa là Yes.Ta chỉ câu hỏi tính Entropy với Engine 2000cc. Kế tiếp 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 trực thuộc tính Type

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

Sắp xếp lại theo nằm 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 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 rất có thể nhận 1 trong những 2 quý hiếm 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 lần lượt là$S_s$, $S_b$.

Sắp xếp lại theo nằm trong tính Color ta bao gồm 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ý giá Silver và Blue đều có 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 thuộc tính 4WD

Thuộc tính này rất có thể nhận một trong những 2 giá trị Yes, No tương ứng với 2 child node.Gọi tập hợp những điểm trong mỗi 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 nhỏ.

4WD Yes ($S_y$)

IDEngineTypeColor4WDWant?
12000ccSUVSilverYesYes
21000ccSedanSilverYesYes
52000ccSedanSilverYesNo
62000ccSportBlueYesYes

4WD No ($S_n$)

IDEngineTypeColor4WDWant?
32000ccSportBlueNoNo
41000ccSUVBlueNoYes
71000ccSedanBlueNoYes
81000ccSUVSilverNoYes

Tương từ bỏ Color, ta tính Entropy trung bình:

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

Chọn ở trong tính bao gồm Entropy nhỏ tuổi nhất

Sau khi tính Entropy mức độ 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ó mức giá trị Entropy nhỏ nhất yêu cầu ta lựa chọn là node nhận xét đầu tiên.Với Engine 1000cc, tất cả các data đều phải có giá trị Yes, vày vậy ta nhận được node là Yes làm việc nhánh 1000cc.Ta liên tiếp tính cho 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 theo thứ tự tính Entropy cho 3 trực thuộc tính là: Type, Color, 4WD

Với 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 nằm trong tính Color:Do 2 quý hiếm Silver với Blue tất 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: Thay Pin Iphone 5 Chính Hãng Fpt Giá Sốc, Thanh Toán Khi Nhận

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