TẬP QUYẾT ĐỊNH Cây có lời giải

Định nghĩaTìm hiểu bằng ví dụ Tính toán entropy của các thuộc tính Định nghĩa

Cây quyết định (Cây quyết định) là một mô hình thuộc nhóm thuật toán học có giám sát (Giảng dạy có giám sát). Tìm hiểu thêm về phân loại các thuật toán học máy tại đây Bạn đang xem: Bài tập cây quyết định có lời giải.

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

Cây quyết định (gọi là DT) là một mô hình ra quyết định dựa trên câu hỏi. Dưới đây là mô hình DT của một ví dụ cổ điển. Câu hỏi đặt ra là có nên chơi tennis hay không? Các quyết định được đưa ra dựa trên các yếu tố khí tượng: tầm nhìn, độ ẩm, gió.

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

*

DT áp dụng cho cả hai vấn đề:Phân loại) và hồi quy (hồi quy). Tuy nhiên, bài toán phân loại được sử dụng nhiều hơn.

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

ID3. Thuật toán

Bộ phân đôi lặp đi lặp lại 3 (ID3) là một thuật toán nổi tiếng để xây dựng cây quyết định, được áp dụng cho bài toán phân loại (Phân loại) nhưng tất cả các thuộc tính đều nằm trong danh mục.

Để dễ hiểu, chúng ta cùng tìm hiểu thuật toán này qua một ví dụ.

Tìm hiểu bằng ví dụ

Chúng tôi có một bộ dữ liệu đào tạo như được hiển thị trong bảng dưới đây:

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
2 1000cc Sedan màu bạc Đúng Đúng
3 2000cc thể thao Màu xanh da trời Không Không
4 1000cc SUV Màu xanh da trời Không Đúng
5 2000cc Sedan màu bạc Đúng Không
6 2000cc thể thao Màu xanh da trời Đúng Đúng
bảy 1000cc Sedan Màu xanh da trời Không Đúng
số 8 1000cc SUV màu bạc Không Đúng

Dữ liệu của chúng tôi có 4 thuộc tính: Động cơ, Loại, Màu sắc, 4WD. Để tính DT, chúng ta cần chia các thuộc tính thành các nút đánh giá. Vậy làm cách nào để biết thuộc tính nào là quan trọng, thuộc tính nào nên đặt ở gốc, thuộc tính nào ở nhánh …

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

Hàm Entropy

Hãy xem xét phân phối xác suất của một biến $ x $ rời rạc có thể nhận $ n $ các giá trị khác nhau $ x_1, x_2, dot, x_n $. Giả 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 cho phân phối này là $ mathbf {p} = (p_1, p_2, dot, p_n) $. Entropy của phân phối này là:

$$ H ( mathbf {p}) = – sum_ {i = 1} ^ n p_i log_2 (p_i) quad quad $$

Hàm Entropy được biểu diễn bằng đồ thị như sau:

*

Từ đồ thị, chúng ta có thể thấy rằng hàm entropy sẽ đạt giá trị nhỏ nhất nếu có giá trị $ p_i = 1 $, giá trị lớn nhất nếu tất cả $ p_i $ bằng nhau. Hàm entropy càng lớn thì độ ngẫu nhiên của các biến càng lớn, biến rời rạc càng cao (càng không tinh khiết).

Với cây quyết định, chúng ta cần tạo một cây cung cấp cho chúng ta nhiều thông tin nhất, tức là entropy là cao nhất.

Thu thập thông tin

Vấn đề của chúng ta là, ở mỗi cấp của cây, phải chọn thuộc tính nào để mức giảm Entropy là thấp nhất. Chúng ta có một khái niệm. Thu thập thông tin được tính bằng $$ Gain (S, f) = H (S) – H (f, S) $$ trong đó: $ H ({S}) $ là tổng entropy của tập dữ liệu $ S $. $ H (f , S) $ là Entropy được tính trên thuộc tính $ f $.

Tính toán Entropy thuộc tính

Xem xét thuộc tính Động cơ.

Thuộc tính này có thể nhận 1 trong 2 giá trị 1000cc, 2000cc, tương ứng với 2 nút con. Chúng ta hãy lần lượt gọi tập hợp các điểm trong mỗi nút con này là $ S_1 $, $ S_2 $.

Xem thêm: Tự làm thiệp 20/10 – 5 Ý tưởng làm thiệp đơn giản nhất cho ngày 20/10

Sắp xếp theo thuộc tính Động cơ Chúng tôi có 2 bàn nhỏ.

Động cơ 1000cc ($ S_1 $)

IDEngineTypeColor4WDBạn muốn?
2 1000cc Sedan màu bạc Đúng Đúng
4 1000cc SUV Màu xanh da trời Không Đúng
bảy 1000cc Sedan Màu xanh da trời Không Đúng
số 8 1000cc SUV màu bạc Không Đúng

Động cơ 2000cc ($ S_2 $)

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
3 2000cc thể thao Màu xanh da trời Không Không
5 2000cc Sedan màu bạc Đúng Không
6 2000cc thể thao Màu xanh da trời Đúng Đúng

Nút con tương ứng với động cơ 1000cc sẽ có Entropy = 0 vì tất cả các giá trị là ĐúngChúng ta chỉ cần tính toán entropy với động cơ 2000cc. Sau đó, tính toán entropy trung bình, chính xác hơn như sau:

$$ begin {align} H (S_1) & = & 0 crH (S_2) & = & – frac {2} {4} mathcal {log} _2 left ( frac {2} {4} phải) – frac {2} {4} mathcal {log} _2 left ( frac {2} {4} right) = 1 crH ({motor}, S) & = & frac {4} {8} H (S_1) + frac {4} {8} H (S_2) = 0,5 end {căn chỉnh} $$

Xem xét thuộc tính Type.

Thuộc tính này có thể nhận 1 trong 3 giá trị SUV, Senda, Sport tương ứng với 3 nút con. Chúng ta hãy gọi lần lượt tập các điểm trong mỗi nút con này là $ S_u $, $ S_e $, $ S_p $.

Sắp xếp theo thuộc tính Loại hình Chúng tôi có 3 bàn nhỏ.

Loại SUV ($ S_u $)

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
4 1000cc SUV Màu xanh da trời Không Đúng
số 8 1000cc SUV màu bạc Không Đúng

Loại Sedan ($ S_e $)

IDEngineTypeColor4WDBạn muốn?
2 1000cc Sedan màu bạc Đúng Đúng
5 2000cc Sedan màu bạc Đúng Không
bảy 1000cc Sedan Màu xanh da trời Không Đúng

Khỏe mạnh ($ S_p $)

IDEngineTypeColor4WDBạn muốn?
3 2000cc thể thao Màu xanh da trời Không Không
6 2000cc thể thao Màu xanh da trời Đúng Đúng

Tương tự, chúng ta lần lượt tính toán entropy như sau:

$$ begin {align} H (S_u) & = & 0 crH (S_e) & = & – frac {2} {3} mathcal {log} _2 left ( frac {2} {3} right) – frac {1} {3} mathcal {log} _2 left ( frac {1} {3} right) about 0.918 crH (S_p) & = & – frac {1} {2 } mathcal {log} _2 left ( frac {1} {2} right) – frac {1} {2} mathcal {log} _2 left ( frac {1} {2} right) = 1 crH ({type}, S) & = & frac {3} {8} H (S_u) + frac {3} {8} H (S_e) + frac {2} {8} H ( S_p) khoảng 0,594 end {align} $$

Xem xét thuộc tính Màu

Thuộc tính này có thể nhận 1 trong 2 giá trị Silver, Blue tương ứng với 2 nút con. Hãy gọi tập hợp các điểm trong mỗi nút con này lần lượt là $ S_s $, $ S_b $.

Sắp xếp theo thuộc tính Màu sắc Chúng tôi có 2 bàn nhỏ.

Màu bạc ($ S_s $)

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
2 1000cc Sedan màu bạc Đúng Đúng
5 2000cc Sedan màu bạc Đúng Không
số 8 1000cc SUV màu bạc Không Đúng

Màu xanh lam ($ S_b $)

IDEngineTypeColor4WDBạn muốn?
3 2000cc thể thao Màu xanh da trời Không Không
4 1000cc SUV Màu xanh da trời Không Đúng
6 2000cc thể thao Màu xanh da trời Đúng Đúng
bảy 1000cc Sedan Màu xanh da trời Không Đúng

Dễ dàng nhận thấy, giá trị Bạc và Xanh có cùng tỷ lệ Có và Không, 3⁄4 và 1⁄4. Do đó, chúng tôi tính toán Entropy trung bình:

$$ begin {align} H ({color}, S) & = & – frac {3} {4} mathcal {log} _2 left ( frac {3} {4} right) – frac {1} {4} mathcal {log} _2 left ( frac {1} {4} right) khoảng 0,811 end {align} $$

Xem xét thuộc tính 4WD.

Thuộc tính này có thể nhận 1 trong 2 giá trị Yes, No tương ứng với 2 nút con. Hãy gọi tập hợp các điểm trong mỗi nút con này, lần lượt là $ S_y $, $ S_n $.

Sắp xếp theo thuộc tính 4×4 Chúng tôi có 2 bàn nhỏ.

4×4 Có ($ S_y $)

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
2 1000cc Sedan màu bạc Đúng Đúng
5 2000cc Sedan màu bạc Đúng Không
6 2000cc thể thao Màu xanh da trời Đúng Đúng

4×4 Không ($ S_n $)

IDEngineTypeColor4WDBạn muốn?
3 2000cc thể thao Màu xanh da trời Không Không
4 1000cc SUV Màu xanh da trời Không Đúng
bảy 1000cc Sedan Màu xanh da trời Không Đúng
số 8 1000cc SUV màu bạc Không Đúng

Tương tự với màu sắc, chúng tôi tính toán entropy trung bình:

$$ begin {align} H ({4wd}, S) & = & – frac {3} {4} mathcal {log} _2 left ( frac {3} {4} right) – frac {1} {4} mathcal {log} _2 left ( frac {1} {4} right) khoảng 0,811 end {align} $$

Chọn thuộc tính có entropy thấp nhất

Sau khi tính toán entropy trung bình của 4 thuộc tính, chúng tôi nhận được: $ H ({engine}, S) = 0,5 $$ H ({type}, S) khoảng 0,594 $$ H ({color}, S) khoảng 0,811 $ $ H ({4wd}, S) khoảng 0,811 $

Đặc tính Động cơ có giá trị entropy nhỏ nhất nên ta chọn là nút đánh giá đầu tiên. Với Engine 1000cc, tất cả dữ liệu là Có, vì vậy chúng ta nhận được nút Có trong nhánh 1000cc. Chúng tôi tiếp tục tính toán cho nhánh Động cơ 2000cc với dữ liệu nhỏ hơn. Chức vụ

IDEngineTypeColor4WDBạn muốn?
Đầu tiên 2000cc SUV màu bạc Đúng Đúng
3 2000cc thể thao Màu xanh da trời Không Không
5 2000cc Sedan màu bạc Đúng Không
6 2000cc thể thao Màu xanh da trời Đúng Đúng

Tương tự, chúng ta lần lượt tính toán entropy cho 3 thuộc tính: Loại, Màu, 4WD

Với thuộc tính Loại hình: $$ begin {align} H (S_u) & = & 0 crH (S_e) & = & 0 crH (S_p) & = & – frac {1} {2} mathcal {log} _2 left ( frac {1} {2} right) – frac {1} {2} mathcal {log} _2 left ( frac {1} {2} right) = 1 crH ({type}, S) & = & frac {1} {4} H (S_u) + frac {1} {4} H (S_e) + frac {2} {4} H (S_p) = 0.5 end {align} $$

Với thuộc tính Màu sắc: Vì 2 giá trị Bạc và Xanh lam có cùng tỷ lệ Có, Không là 1⁄2 và 1⁄2. $$ begin {align} H ({color}, S) & = & – frac {1} { 2} mathcal {log} _2 left ( frac {1} {2} right) – frac {1} {2} mathcal {log} _2 left ( frac {1} {2} right ) = 1 end {căn chỉnh} $$

Với thuộc tính 4×4: $$ begin {align} H (S_y) & = & – frac {2} {3} mathcal {log} _2 left ( frac {2} {3} right) – frac {1} {3} mathcal {log} _2 left ( frac {1} {3} right) about 0.918 crH (S_n) & = & 0 crH ({4wd}, S) & = & frac { 3} {4} H (S_y) + frac {1} {4} H (S_n) khoảng 0,688 end {căn chỉnh} $$

Vì vậy, chúng tôi chọn Loại hình là nút đánh giá tiếp theo.

Trong trường hợp Loại là SUV hoặc Sedan, chúng ta có ngay một nút lá vì chỉ có một kết quả duy nhất. Trong trường hợp Loại là Thể thao, vì thuộc tính Màu giống nhau cho tất cả dữ liệu, chúng tôi chọn nút đánh giá tiếp theo. 4×4.