ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THANH HUYỀN

ỨNG DỤNG CÂY QUYẾT ĐỊNH TRONG
KHAI PHÁ DỮ LIỆU

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.05

LUẬN VĂN THẠC SỸ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. ĐOÀN VĂN BAN
HÀ NỘI – 2011 iii
MỤC LỤC

2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy 20
2.2.1. Tiêu chí chọn thuộc tính phân lớp 20
2.2.2. Thuật toán ID3 21
2.2.3. Ví dụ về thuật toán ID3 23
2.3. Thuật toán xây dựng cây quyết định dựa vào độ phụ thuộc của thuộc
tính 28 iv
2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô 28
2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô 28
2.3.3. Tiêu chí chọn thuộc tính để phân lớp 28
2.3.4. Thuật toán xây dựng cây quyết định ADTDA 29
2.3.5. Ví dụ 30
2.4. Thuật toán xây dựng cây quyết định dựa vào Entropy và độ phụ thuộc
của thuộc tính 33
2.4.1. Tiêu chí chọn thuộc tính để phân lớp 33
2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] ) 34
2.4.3. Ví dụ 35
2.5. Kết luận chương 2 39
Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ 40
3.1. Giới thiệu bài toán 40
3.2. Giới thiệu về cơ sở dữ liệu 40
3.3. Cài đặt ứng dụng 41
3.4. Kết quả và đánh giá thuật toán 42
3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data 42
3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data 44
3.4.3. Đánh giá thuật toán 44
3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu 45
3.5. Kết luận chương 3 46

Miền C-khẳng định của d
|DT| Tổng số các đối tượng trong DT
|U| Lực lượng của tập U
[U]
d
Phân hoạch của U sinh ra bởi quan hệ IND(d)

CÁC CHỮ VIẾT TẮT:
ADTDA Algorithm for Buiding Decision Tree Based on Dependency
of Attributes
FID3 Fixed Iterative Dichotomiser 3
ID3 Iterative Dichotomiser 3
IG Information Gain vi
DANH MỤC CÁC BẢNG

Bảng 1. Hệ thông tin đơn giản 10
Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk} 11
Bảng 3. Dữ liệu huấn luyện 23
Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data 41
Bảng 5. Độ chính xác của các thuật toán 45
vii
DANH MỤC CÁC HÌNH

Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình 7

bùng nổ thông tin. Các thông tin tổ chức theo phương thức sử dụng giấy trong
giao dịch đang dần được số hóa, do nhiều tính năng vượt trội mà phương thức
này mang lại như: có thể lưu trữ lâu dài, cập nhật, sửa đổi, tìm kiếm một cách
nhanh chóng. Đó là lý do khiến cho số lượng thông tin số hóa ngày nay đang
tăng dần theo cấp số nhân.
Hiện nay, không một lĩnh vực nào lại không cần đến sự hỗ trợ của công
nghệ thông tin và sự thành công của các lĩnh vực đó phụ thuộc rất nhiều vào
việc nắm bắt thông tin một cách nhạy bén, nhanh chóng và hữu ích. Với nhu cầu
như thế nếu chỉ sử dụng thao tác thủ công truyền thống thì độ chính xác không
cao và mất rất nhiều thời gian. Do vậy việc khai phá tri thức từ dữ liệu trong các
tập tài liệu lớn chứa đựng thông tin phục vụ nhu cầu nắm bắt thông tin có vai trò
hết sức to lớn. Việc khai phá tri thức đã có từ lâu nhưng sự bùng nổ của nó thì
mới chỉ xảy ra trong những năm gần đây. Các công cụ thu thập dữ liệu tự động
và các công nghệ cơ sở dữ liệu được phát triển dẫn đến vấn đề một lượng dữ liệu
khổng lồ được lưu trữ trong cơ sở dữ liệu và trong các kho thông tin của các tổ
chức, cá nhân Do đó việc khai phá tri thức từ dữ liệu là một trong những vấn
đề đã và đang nhận được nhiều sự quan tâm của các nhà nghiên cứu. Một vấn đề
quan trọng và phổ biến trong kỹ thuật khai phá dữ liệu là phân lớp, nó đã và
đang được ứng dụng rộng rãi trong thương mại, y tế, công nghiệp
Trong những năm trước đây, phương pháp phân lớp đã được đề xuất,
nhưng không có phương pháp tiếp cận phân loại nào là cao hơn và chính xác
hơn hẳn những phương pháp khác. Tuy nhiên với mỗi phương pháp có một lợi
thế và bất lợi riêng khi sử dụng. Một trong những công cụ khai phá tri thức hiệu
quả hiện nay là sử dụng cây quyết định để tìm ra các luật phân lớp.
Phân lớp sử dụng lý thuyết tập thô, được đề xuất bởi Zdzislaw Pawlak vào
năm 1982, và đã được nghiên cứu rộng rãi trong những năm gần đây. Lý thuyết
tập thô cung cấp cho nhiều nhà nghiên cứu và phân tích dữ liệu với nhiều kỹ
thuật trong khai phá dữ liệu như là các khái niệm đặc trưng bằng cách sử dụng
một số dữ kiện. Nhiều nhà nghiên cứu đã sử dụng lý thuyết tập thô trong các
ứng dụng như phân biệt thuộc tính, giảm số chiều, khám phá tri thức, và phân


3
Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ
LÝ THUYẾT TẬP THÔ
1.1. Giới thiệu về khai phá dữ liệu
1.1.1 Khám phá tri thức
Trong thời đại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ liệu
ngày càng phát triển nhanh chóng tạo điều kiện cho các đơn vị thu thập dữ liệu
nhiều hơn và tốt hơn. Đặc biệt trong lĩnh vực kinh doanh, các doanh nghiệp đã
nhận thức được tầm quan trọng cuả việc nắm bắt và xử lí thông tin. Nó hỗ trợ
các chủ doanh nghiệp trong việc đưa ra các chiến lược kinh doanh kịp thời mang
lại những lợi nhuận to lớn cho doanh nghiệp của mình. Tất cả lí do đó khiến cho
các cơ quan, đơn vị và các doanh nghiệp đã tạo ra một lượng dữ liệu khổng lồ cỡ
Gigabyte thậm chí là Terabyte cho riêng mình. Các kho dữ liệu ngày càng lớn và
tiềm ẩn nhiều thông tin có ích. Sự bùng nổ đó dẫn tới một yêu cầu cấp thiết là
phải có những kĩ thuật và công cụ mới để biến kho dữ liệu khổng lồ kia thành
những thông tin cô đọng và có ích. Khám phá tri thức từ dữ liệu (Knowledge
Discovery from Data - KDD) ra đời như một kết quả tất yếu đáp ứng các nhu
cầu đó.
Quá trình khám phá tri thức từ dữ liệu thông thường gồm các bước chính
sau [2]-[7]:
Bước 1: Xác định vấn đề và lựa chọn nguồn dữ liệu (Problem
Understanding anh Data Understanding)
Trong giai đoạn này các chuyên gia trong lĩnh vực cần phải thảo luận
với các chuyên gia tin học, để xác định được chúng ta mong muốn khám
phá những gì, thống nhất giải pháp cho quá trình khám phá dữ liệu (muốn
có các luật hay muốn phân lớp, phâm cụm dữ liệu…). Đây là một giai đoạn
quan trọng vì nếu xác định sai vấn đề thì toàn bộ quá trình phá sản, nó trở
nên vô ích.
Bước 2: Chuẩn bị dữ liệu (Data preparation)

Đây là bước tập hợp các dữ liệu được khai thác trong một cơ sở dữ liệu,
một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
Giai đoạn 2: Trích lọc dữ liệu (Selection) 5
Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu
chuẩn nào đó, ví dụ chọn tất cả những người có tuổi đời từ 25 – 35 và có trình
độ đại học.
Giai đoạn 3: Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing,
Pre-processing and Preparation)
Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một
bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải
trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. Vì vậy, dữ liệu thường
chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: tuổi =
673. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói
trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị.
Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm
sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm
trọng.
Giai đoạn 4: Chuyển đổi dữ liệu (Transformation)
Dữ liệu sẽ được chuyển đổi phù hợp với mục đích khai thác.
Giai đoạn 5: Phát hiện và trích mẫu dữ liệu (Pattern Extraction and
Discovery)
Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các
mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết
hợp hoặc các mô hình dữ liệu tuần tự,. v.v.
Giai đoạn 6: Đánh giá kết quả mẫu (Evaluation of Result)
Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các
mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất

1.3. Một số phương pháp khai phá dữ liệu thông dụng
Nhiệm vụ chính của khai phá dữ liệu là mô tả và dự đoán. Trong đó mô tả
nhằm biểu thị các đặc điểm chung của dữ liệu có trong CSDL, còn dự đoán
nhằm thực hiện, suy luận trên dữ liệu hiện có để đưa ra các kết luận của dự đoán
đó. Dưới đây giới thiệu 3 phương pháp thông dụng nhất là: phân cụm dữ liệu,
phân lớp dữ liệu và luật kết hợp.
1.3.1. Phân lớp (Classification)
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các
mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước:
Bước 1: Xây dựng mô hình
Trong bước này, một mô hình sẽ được xây dựng dựa trên việc phân tích
các mẫu dữ liệu sẵn có. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc 7
được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc
tính đó. Mỗi bộ giá trị được gọi chung là một mẫu (sample). Trong tập dữ liệu
này, mỗi mẫu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của
một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính quyết
định. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng
if-then, cây quyết định, công thức logic, hay mạng nơron. Quá trình này được
mô tả như trong hình 1

Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình
Bước 2: Sử dụng mô hình đã xây dựng để phân lớp dữ liệu
Trong bước này việc đầu tiên là phải làm là tính độ chính xác của mô
hình. Nếu độ chính xác là chấp nhận được mô hình sẽ được sử dụng để dự đoán
nhãn lớp cho các mẫu dữ liệu khác trong tương lai.
Độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra
được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác

Mục tiêu của phương pháp này là phát hiện và đưa ra mối liên hệ giữa các
giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật
kết hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2 bước:
 Bước 1: Tìm tất cả các tập mục phổ biến, một văn bản phổ biến được xác
định qua độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.
 Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải
thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.
1.4. Lý thuyết tập thô
Lý thuyết tập thô (rough set theory) lần đầu tiên được đề xuất bởi
Z.Pawlak vào những năm đầu thập niên 1980. Phương pháp này đóng vai trò hêt
sức quan trọng trong lĩnh vực trí tuệ nhân tạo và các ngành liên quan đến nhận
thức, đặc biệt là trong lĩnh vực học máy, thu nhận tri thức, phân tích quyết định,
phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên gia, các hệ hỗ trợ
quyết định, lập luận dựa trên quy nạp [1]-[8].
Các lĩnh vực ứng dụng trong tập thô bao gồm:
- Chẩn đoán y học (medical diagnosis)
- Nghiên cứu dược lý ((pharmacology)
- Dự đoán thị trường cổ phiếu và phân tích dữ liệu tài chính
- Kinh doanh tiền tệ (banking)
- Nghiên cứu thị trường
- Các hệ thu nhận và lưu trữ thông tin
- Nhận dạng mẫu, gồm nhận dạng tiếng nói và chữ viết tay
- Thiết kế hệ điều khiển ( control system design)
- Xử lý ảnh (image processing) 10
- Thiết kế logic số(digital logic design)
Sau đây chúng ta sẽ nghiên cứu các khái niệm cơ bản của lý thuyết tập thô.
Đây là những kiến thức quan trọng cho việc áp dụng tập thô để xây dựng cây

31-45
1-25
x
4

31-45
1-25
x
5

46-60
26-49
x
6

16-30
26-49
x
7

46-60
26-49

Bảng 1. Hệ thông tin đơn giản
1.4.2. Bảng quyết định
Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết
đinh, chúng ta xét một trường hợp đặc biệt của hệ thông tin được gọi là bảng
quyết định được định nghĩa như sau:
4

31-45
1-25
Yes
x
5

46-60
26-49
No
x
6

16-30
26-49
Yes
x
7

46-60
26-49
No

Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk}

Định nghĩa 1.3. Miền khẳng định
Cho bảng quyết định DT = {U,CD}. Tập POS
C
(D) =

và xử lý các dữ liệu trong đó có sự mập mờ, không phân biệt được. Trong một
hệ thông tin theo định nghĩa trên cũng có thể có những đối tượng không phân
biệt được.
Định nghĩa 6: Cho hệ thông tin S = (U, A). Với mỗi tập thuộc tính B  A
đều tạo ra tương ứng một quan hệ tương đương, kí hiệu IND(B) [1]-[8]:
IND(B) = {(x,x’)  U
2
|  a B, x(a) = x’(a) }
IND(B) được gọi là quan hệ B-không phân biệt được. Nếu (x,x’)  IND(B) thì
các đối tượng x và x’ là không thể phân biệt được với nhau qua tập thuộc tính B.
Với mọi đối tượng x  U, lớp tương đương của x trong quan hệ IND(B) được kí
hiệu bởi [x]
B
là tập tất cả các đối tượng có quan hệ IND(B) với x.
Quan hệ B- không phân biệt được phân hoạch tập đối tượng U thành các
lớp tương đương, kí hiệu là U/ IND(B) hay U/B, tức là U/B = {[x]
P
| x  U}.
Ví dụ 1.3. [8] Xét hệ thông tin cho trong Bảng 1
Xét thuộc tính B = {LEMS}, ta có phân hoạch của tập U sinh bởi quan hệ
tương đương IND(B) là:
U/B = {{x
1
}, {x
2
}, {x
3
, x
4
}, {x

},{ x
6
}}
Khi đó x
5
và x
6
là phân biệt được qua tập thuộc tính {Age, LEMS} vì
chúng không thuộc cùng lớp tương đương định bởi quan hệ IND(B).
1.4.4. Xấp xỉ tập hợp
Ta thấy ở bảng 2 khái niệm Walk không thể định nghĩa rõ ràng qua 2
thuộc tính điều kiện Age và LEMS vì có x
3
, x
4
thuộc cùng một lớp tương đương
tạo bởi 2 thuộc tính Age và LEMS nhưng lại có giá trị khác nhau tại thuộc tính 13
Walk. Vì vậy, nếu một đối tượng nào đó có (Age,LEMS) = (31-45, 1-25) thì ta
vẫn không thể biết chắc chắn giá trị của nó tại thuộc tính Walk là Yes hay No.
Vì vậy, ta thấy khái niệm Walk không được mô tả rõ ràng. Tuy nhiên, căn cứ
vào tập thuộc tính {Age, LEMS} ta vẫn có thể chỉ ra được chắc chắn một số đối
tượng có Walk là Yes, một số đối tượng có Walk là No, còn lại là các đối tượng
thuộc tính về biên của hai giá trị Yes và No, cụ thể:
 Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập
{{16-30, 50}, {16-30, 26-49}} thì có Walk là Yes.
 Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập
{{16-30, 0}, {46-60, 26-49}} thì có Walk là No.

tượng mà sử dụng các thuộc tính của B ta không thể xác định được chúng có
thuộc tập X hay không.
Tập U\
B
X được gọi là B-ngoài của tập X, gồm những đối tượng mà sử
dụng tập thuộc tính B ta biết chắc chắn chúng không thuộc tập X.
Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược
lại ta nói tập này là rõ.
Ví dụ 1.4. Xét hệ quyết định cho trong Bảng 2 14
Xét tập đối tượng X = {x U | x(Walk) = Yes} = {x
1
, x
4
, x
6
} và tập thuộc
tính B = {Age, LEMS}. Khi đó ta có [8]:
U/B ={{x
1
}, {x
2
}, {x
3
, x
4
}, {x
5

LEMS
1.5. Kết luận chương 1
+ Chương này đã giới thiệu tổng quan về khai phá dữ liệu, ứng dụng của
khai phá dữ liệu, và giới thiệu một số phương pháp khai phá dữ liệu thông dụng.
+ Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thống thông tin,
quan hệ không phân biệt được, các tập thô, bảng quyết định,… Và đồng thời
trình bày các ví dụ cụ thể để minh họa các khái niệm này.
15
Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY
DỰNG CÂY QUYẾT ĐỊNH
2.1. Tổng quan về cây quyết định
Cây quyết định là công cụ dùng để phân lớp các dữ liệu, nó có cấu trúc
cây. Mỗi cây quyết định là một sự tượng trưng cho một sự quyết định của một
lớp các dữ kiện nào đó. Mỗi nút trong cây là tên của một lớp hay một phép thử
thuộc tính cụ thể nào đó, phép thử này phân chia không gian trạng thái các dữ
kiện tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được
phân chia của phép thử là không gian con của các sự kiện, nó tương ứng với một
vấn đề con của sự phân lớp. Các cây quyết định được dùng để hỗ trợ quá trình ra
quyết định.
2.1.1. Định nghĩa
Cây quyết định là một cây mà mỗi nút của cây là:
- Nút lá hay còn gọi là nút trả lời biểu thị cho một lớp các trường hợp mà
nhãn của nó là tên của lớp.
- Nút không phải là nút lá hay còn gọi là nút trong, nút định phép kiểm tra
các thuộc tính, nhãn của nút này là tên của thuộc tính và có một nhánh nối nút này
đến các cây con ứng với mỗi kết quả có thể có phép thử. Nhãn của nhánh này là
các giá trị của thuộc tính đó. Nút trên cùng gọi là nút gốc.

Hình 6. Ví dụ về Cây quyết định

2.1.2. Thiết kế cây quyết định
2.1.2.1. Xử lý dữ liệu
Trong thế giới thực, nói chung dữ liệu thô chắc chắn có mức độ nhiễu.
Điều này có các nguyên nhân khác nhau như là dữ liệu lỗi, dữ liệu có đại lượng
không chính xác, Do đó, chúng ta thường tiền xử lý (nghĩa là, “làm sạch”) để
cực tiểu hoá hay huỷ bỏ tất cả dữ liệu thô bị nhiễu. Các giai đoạn tiền xử lý này
cũng có thể biến đổi dữ liệu thô hiển thị hữu ích hơn, như hệ thống thông tin.
Khi nhiều bước tiền xử lý ứng dụng hiệu quả, nó sẽ giúp cải tiến hiệu quả phân
lớp.
Các công việc cụ thể của tiền xử lý dữ liệu bao gồm những công việc như:
- Filtering Attributes: Chọn các thuộc tính phù hợp với mô hình.
- Filtering samples: Lọc các mẫu (instances, patterns) dữ liệu cho
mô hình.
- Transformation: Chuyển đổi dữ liệu cho phù hợp với các mô hình
như chuyển đổi dữ liệu từ numeric sang nomial
- Discretization (rời rạc hóa dữ liệu): Nếu bạn có dữ liệu liên tục
nhưng có một số thuật toán chỉ áp dụng cho các dữ liệu rời rạc
(như ID3, ADTDA,…) thì bạn phải thực hiện việc rời rạc hóa dữ
liệu.
mild
Humidity
high

Normal
low
Outlook
Temp
Overcast

+ Độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện theo
nghĩa lí thuyết tập thô của Zdzisław Pawlak [3]-[10]
Các tiêu chuẩn trên sẽ được trình bày trong các thuật toán xây dựng cây
quyết định ở các phần dưới đây.
2.1.2.4. Tiêu chuẩn dừng
Đây là phần quan trọng trong cấu trúc phân lớp của cây quyết định nhằm
chia một nút thành các nút con.
Chúng ta tập trung một số tiêu chuẩn dừng chung nhất được sử dụng trong
cây quyết định. Tiêu chuẩn dừng truyền thống sử dụng các tập kiểm tra. Chúng
ta kiểm tra cây quyết định trong suốt qúa trình xây dựng cây với tập kiểm tra và
dừng thuật toán khi xảy ra lỗi. Một phương pháp khác sử dụng giá trị ngưỡng
cho trước để dừng chia nút. Chúng ta có thể thay ngưỡng như là giảm nhiễu, số
các mẫu trong một nút, tỉ lệ các mẫu trong nút, hay chiều sâu của cây,
2.1.2.5. Tỉa cây
Trong giai đoạn tạo cây chúng ta có thể giới hạn việc phát triển của cây
bằng số bản tin tối thiểu tại mỗi nút, độ sâu tối đa của cây hay giá trị tối thiểu
của lượng thông tin thu thêm.
Sau giai đoạn tạo cây chúng ta có thể dùng phương pháp “Độ dài mô tả
ngắn nhất” (Minimum Description Length) hay giá trị tối thiểu của IG để tỉa cây 18
(chúng ta có thể chọn giá trị tối thiểu của IG trong giai đoạn tạo cây đủ nhỏ để
cho cây phát triển tương đối sâu, sau đó lại nâng giá trị này lên để tỉa cây).
2.1.3. Phương pháp tổng quát xây dựng cây quyết định
Quá trình xây dựng một cây quyết định cụ thể bắt đầu bằng một nút rỗng
bao gồm toàn bộ các đối tượng huấn luyện và làm như sau [3]:
1. Nếu tại nút hiện thời, tất cả các đối tượng huấn luyện đều thuộc vào
một lớp nào đó thì cho nút này thành nút lá có tên là nhãn lớp chung của các
đối tượng.