Decision tree là gì

Decision tree là 1 trong những mô hình supervised learning, có thể được vận dụng vào cả nhì bài xích toán classification cùng regression. Mỗi một nút ít trong (internal node) khớp ứng với một biến; mặt đường nối thân nó với nút nhỏ của chính nó thể hiện một quý giá rõ ràng đến biến hóa đó. Mỗi nút ít lá thay mặt đại diện cho cực hiếm dự đoán thù của biến hóa kim chỉ nam, mang lại trước những giá trị của những biến đổi được màn biểu diễn bởi lối đi trường đoản cú nút gốc cho tới nút ít lá đó. Kỹ thuật học tập thiết bị sử dụng trong cây ra quyết định được Hotline là học bằng cây quyết định, tốt chỉ gọi với cái brand name ngắn thêm gọn gàng là cây ra quyết định.

Bạn đang xem: Decision tree là gì

1. Entropy

Giả sử ta tất cả phát triển thành tự dưng tránh rốc X:

Có không gian chủng loại là x1, x2, ..., xm với xác suấtP(X = x1) = p1, P(X = x2) = p2, ..., P(X = xm) = pmSố bit vừa phải nhỏ dại nhất nhằm truyền một đơn vị tài liệu theo phân phối hận P(X):
*

H(X) là entropy của X (0 2m)Xem xét m = 2, trong ngôi trường hòa hợp X là tinc khiết nhất, có nghĩa là một trong các nhì pi bằng 0 cùng cực hiếm tê bằng 1, khi đó H(X) = 0. khi X là vẩn đục nhất tức cả nhì Tỷ Lệ mang cực hiếm pi = 0.5, hàm entropy đạt giá trị cao nhất.

*

Vậy cùng với m > 2,hàm entropy đạt quý giá nhỏ dại tốt nhất trường hợp gồm một giá trị pi = 1 (tức những quý giá pi sót lại với giá trị 0), đạt giá trị lớn số 1 nếu toàn bộ pi đều nhau.Giá trị entropy:

Lớn: Phân păn năn P(X) ngay gần với dạng phân phối hận đồng bộ (unikhung distribution)Nhỏ: Phân phối hận P(X) xa dạng phân phối đồng nhấtNhững quý giá này khiến cho nó được áp dụng trong bài toán đo độ vẩn đục của một pháp phân loại trong ID3 (Hôm bữa bình chọn nói không nên phần này
*

Ví dụ:

*

Ta có:

*

Vậy nên:H(Y|X) = 0.5 x 1 + 0.25 x 0 + 0.25 x 0 = 0.5

Information Gain IG(Y|X)

IG(Y|X) là số lượng bit vừa đủ có thể tiết kiệm khi truyền Y cơ mà hai đầu gửi với nhận sẽ biết X.Tức là: IG(Y|X) = H(Y) - H(Y|X)

Ví dụ: H(Y) = 1 H(Y|X) = 0.5IG(Y|X) = 1 - 0.5 = 0.5

2. Iterative sầu Dichotomiser 3 (ID3)

Input:

Tập tài liệu huấn luyện và đào tạo DTập những lớp C = c1, c2, ..., cn là nằm trong tính đích.Attributes = F tập toàn bộ những nằm trong tính điều kiện

ID3

Tạo nốt gốc (root) cho cây.

Nếu toàn bộ những đối tượng người tiêu dùng x nằm trong D tất cả cùng một lớp ông xã, trả về nốt cội Root với nhãn ck.

Nếu không thể trực thuộc tính ĐK nào (Attributes = rỗng), trả về nốt gốc Root cùng với nhãn ck làm sao xuất hiện thêm nhiều tốt nhất trong D.

Nếu ko thì:

4.1. Chọn trực thuộc tính Fi ở trong Attributes là thuộc tính phân lớp tốt nhất có thể (với thuận toán thù ID3 là nằm trong tính phân lớp rất tốt là trực thuộc tính gồm độ lợi biết tin Khủng nhất) mang lại tập D làm nốt nơi bắt đầu.

4.2. Đối với từng giá trị vij của Fi4.2.1. Thêm một nhánh bên dưới nốt root khớp ứng với Fi = vij.4.2.2. D(vij) là tập những đối tượng thuộc D bao gồm Fi= vij4.2.3. Nếu D(vij) = trống rỗng, thêm một nốt lá (leaf node) bên dưới nhánh này cùng với nhãn ông chồng làm sao kia thông dụng tuyệt nhất vào D. trái lại dưới nhánh này thêm 1 cây nhỏ ID3(D(vij), C, Attributes - Fi)

Trả về nốt cội Root.

Xem thêm: Chi Tiết Địa Điểm Khu E Hutech Ở Đâu 2021, Xe Buýt Đi Qua Trạm Hutech

Ví dụ

*

Information Gain theo từng nằm trong tính.

*

Dựng cây cùng với nốt là nằm trong tính Age.

*

Tiếp tục tính Information Gain cho đầy đủ thuộc tính còn lại:

*

Tiếp tục dựng cây:

*

3. Thuật toán C4.5

C4.5 là thuật tân oán cải tiến so với ID3:

Sử dụng Gain Ratio (cụ vị Information Gain) để lựa chọn trực thuộc tính phân loại trong quá trình dựng cây.Xử lý xuất sắc cả nhị dạng thuộc tính: tách rốc, liên tụcXử lý dữ liệu không không hề thiếu (thiếu thốn một vài quý hiếm tại một trong những thuộc tính).C4.5 chất nhận được những thuộc tính - cực hiếm bị thiếu thốn hoàn toàn có thể cố bởi vết hỏi (?)Những quý giá bị thiếu thốn không được xem xét lúc tính toán Information Gain và Gain RadioCắt tỉa cây sau khi xây dựng: Loại bỏ hồ hết nhánh cây ko đích thực chân thành và ý nghĩa (vắt bằng nốt lá).

Ý nghĩa của Gain Ratio (GR)

*

Spliting entropy của trực thuộc tính Fi, cam kết hiệu SE(Fi):

*

khi kia, Gain Ratio cam kết hiệu GRD(C|Fi)

*

Giá trị Information Gain và Gain Ratio

*

Tiêu chí Information Gain thường "ưu tiên" chọn phần đa nằm trong tính có rất nhiều giá trị (miền xác minh lớn)Spliting entropy, SED(Fi) đã mập khi thuộc tính Fi có không ít cực hiếm. Điều này giúp:2.1. Làm bớt Gain Ratio của trực thuộc tính có nhiều quý hiếm.2.2 Làm tăng Gain Ratio của nằm trong tính bao gồm không nhiều cực hiếm.Ý nghĩa khác:Giảm sự việc "thừa khớp"

4. Kết luận

Ưu điểm

Mô hình dễ hiểu cùng dễ dàng phân tích và lý giải.Cần không nhiều tài liệu để huẩn luyện.cũng có thể xử trí xuất sắc cùng với dữ liệu dạng số (tách rốc và liên tục) cùng tài liệu hạng mục.Mô những thiết kế White box ví dụ.Xây dựng nhanh.Phân lớp nkhô nóng.

Nhược điểm

Không bảo đảm gây ra được cây tối ưu.cũng có thể overfitting (tạo nên hầu hết cây quá khớp với dữ liệu huấn luyện hay quá phức tạp).Thường ưu tiên trực thuộc tính có rất nhiều cực hiếm (khắc phục và hạn chế bởi các sử dụng Gain Ratio).

Xem thêm: Nghĩa Của Từ Kim Ngạch Tiếng Anh Là Gì, Kim Ngạch Xuất Khẩu Tiếng Anh Là Gì

5. Ứng dụng

Xử lý tốt tài liệu dạng bảng biếu với số thuộc tính không quá to.Không cân xứng Lúc con số ở trong tính nở rộ (như tài liệu vnạp năng lượng bạn dạng, hình ảnh, âm tkhô cứng, đoạn Clip, ...).

Bài viết tham khảo bài giảng của thầy Phan Xuân hiếu - Giảng viên ngôi trường đại học Công Nghệ


Chuyên mục: Hỏi Đáp