ĐỒ ÁN MÔ HÌNH CÂY QUYẾT ĐỊNH DECISION TREE (Hồ Sơn Lâm)

Cây quyết định (decision tree) là một trong những hình thức mô tả dữ liệu trực quan nhất, dễ hiểu nhất đối với người dùng. Cấu trúc của một cây quyết định bao gồm các nút và các nhánh. Nút dưới cùng được gọi là nút lá, trong mô hình phân lớp dữ liệu chính là các giá trị của các nhãn lớp (gọi tắt là nhãn). Các nút khác nút lá được gọi là các nút con, đây còn là các thuộc tính của tập dữ liệu, hiển nhiên các thuộc tính này phải khác thuộc tính phân lớp. Mỗi một nhánh của cây xuất phát từ một nút p nào đó ứng với một phép so sánh dựa trên miền giá trị của nút đó. Nút đầu tiên được gọi là nút gốc của cây. Xem xét một ví dụ về một cây quyết định như sau[1]:

NỘI DUNG:

1. Gii thiu ( Minh Tun) .................................................................................. 4

1.1 Mô hình cây quyết định ......................................................................................... 4

1.2 Chiến lược cơ bản để xây dựng cây quyết định .................................................... 5

1.3 Thuận lợi và hạn chế của mô hình cây quyết định ................................................ 6

2. Các tiêu chun to cây quyt

nh ( Minh Tun) ........................................... 8

2.1 Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria): ......................................... 8

2.1.1 Impurity-based Criteria: .................................................................................. 8

2.1.2 Normalized impurity based criteria: ............................................................. 13

2.1.3 Binary criteria ................................................................................................ 13

2.2 Tiêu chuẩn tách đa chiều: .................................................................................... 14

2.3 Tiêu chuẩn dừng (Stopping Criteria): ................................................................... 14

3. Mt s thu

t toán (Trn Th

Tuyt Vân) ...........................................................15

3.1 Thuật toán CLS ..................................................................................................... 15

3.2 Thuật toán ID3 ..................................................................................................... 18

3.3 Thuật toán C4.5 .................................................................................................... 22

3.4 Một số cài tiến của thuật toán C4.5 so với thuật toán ID3.................................. 23

3.4.1 Chọn độ đo Gain Ratio .................................................................................. 23

3.4.2 Xử lý các thuộc tính có kiểu giá trị liên tục ................................................... 24

3.4.3 Làm việc với thuộc tính thiếu giá trị .............................................................. 26

3.4.4 Xử lý các thuộc tính có giá trị chi phí ............................................................ 28

3.5 Thuật toán SPRINT ............................................................................................... 29

3.5.1 SPRINT sử dụng độ đo Gini-index ................................................................. 30

3.5.2 Cấu trúc dữ liệu trong SPRINT ....................................................................... 30

3.5.3 Danh sách thuộc tính .................................................................................... 31

3.5.4 Thực thi sự phân chia .................................................................................... 34

4. Vn Overfitting và các gii pháp gim Overfitting (H Sơn Lâm) ..............37

Decision Tree 3

4.1 Quá khớp dữ liệu (Overfitting) ............................................................................ 37

4.1.1 Định nghĩa: .................................................................................................... 37

4.1.2 Nguyên nhân quá khớp dữ liệu ..................................................................... 38

4.2 Phương pháp tránh quá khớp dữ liệu ................................................................. 39

4.2.1 Cắt tỉa để giảm lỗi (Reduced error pruning) ................................................. 40

4.2.2 Luật hậu cắt tỉa (Rule Post-Pruning) ............................................................. 46

5. Cây quyt

nh m rng (Bùi Tun Phng) ......................................................48

5.1 Oblivious Decision Trees ......................................... Error! Bookmark not defined.

5.2 Fuzzy decision trees ................................................ Error! Bookmark not defined.

5.3 Decision Trees Inducers for Large Datasets ............ Error! Bookmark not defined.

5.4 Incremental Induction: ........................................... Error! Bookmark not defined.

6. Demo (Phan Hoàn V) ......................................................................................53

Tài liệu tham khảo

LINK DOWNLOAD

NỘI DUNG: