Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
PHÒNG ĐÀO TẠO SAU ĐẠI HỌC
BÀI THU HOẠCH MÔN HỌC
KHAI PHÁ DỮ LIỆU VÀ NHÀ KHO DỮ LIỆU
ĐỀ TÀI: NGHIÊN CỨU CÁC THUẬT TOÁN
PHÂN LỚP DỮ LIỆU TRÊN CÂY QUYẾT ĐỊNH
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 1
GVHD PGS.TS. ĐỖ PHÚC
HỌC VIÊN LƯƠNG VĂN NGUYÊN
NƠI SINH HÀ NAM
LỚP CAO HỌC, KHÓA 7
MSHV CH1102005
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
HÀ NỘI - 2012
LỜI CẢM ƠN

Em xin chân thành cảm ơn các Thầy Cô trong
Trường Đại học Công nghệ thông tin, đã tận tình giúp
đỡ chúng em học tập, nghiên cứu.
Em vô cùng biết ơn phó giáo sư tiến sỹ Đỗ Phúc
đã cho phép em tìm hiểu, nghiên cứu đề tài “Các thuật
toán phân lớp dữ liệu trên cây quyết định” và Thầy đã
dành nhiều thời gian, tận tình hướng dẫn em trên diễn
đàn môn học Khai phá dữ liệu và Nhà kho dữ liệu.
Học viên: Lương Văn Nguyên
MỤC LỤC
LỜI NÓI ĐẦU 4
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU TRONG DATA MINING 4
Phân lớp dữ liệu là gì? 4
Qúa trình phân lớp dữ liệu gồm 2 bước : 4

Độ đo sử dụng để xác định điểm chia tốt nhất: 32
4. Một số vấn đề với thuộc tính: 33
ỨNG DỤNG CÂY QUYẾT ĐỊNH TRONG CƠ SỞ DỮ LIỆU THỰC TÊ 46
III.KẾT LUẬN 52
TÀI LIỆU THAM KHẢO 52
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 3
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
LỜI NÓI ĐẦU
Ngày nay phân lớp dữ liệu (classification) là một trong những hướng nghiên
cứu chính
của
khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu
với nhiều thông tin ẩn con người
có
thể trích rút ra các quyết định nghiệp vụ thông
minh. Phân lớp và dự đoán là hai dạng của phân tích
dữ
liệu nhằm trích rút ra một
mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hướng dữ
liệu

tương
lai.
Phân lớp dự đoán giá trị của những nhãn xác định hay những giá trị
rời
rạc, có
nghĩa là phân lớp thao tác với những đối tượng dữ liệu mà có bộ giá trị là
biết
trước.
Trong khi đó, dự đoán lại xây dựng mô hình với các hàm nhận giá trị liên tục. Ví dụ mô

mại, nhà băng,
maketing, nghiên cứu thị trường, bảo hiểm, y tế, giáo dục Phần lớn các thuật toán
ra
đời trước đều sử dụng cơ chế dữ liệu cư trú trong bộ nhớ (memory resident),
thường thao tác
với

lượng
dữ liệu nhỏ. Một số thuật toán ra đời sau này đã sử dụng kỹ
thuật cư trú trên đĩa cải thiện đáng
kể
khả năng mở rộng của thuật toán với những
tập dữ liệu lớn lên tới hàng tỉ bản
ghi.
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU TRONG
DATA MINING
Phân lớp dữ liệu là gì?
Phân lớp dữ liệu là xếp đối tượng dữ liệu vào một trong các lớp đã được xác định
trước.
Qúa trình phân lớp dữ liệu gồm 2 bước :
Bước 1 (Learning)
Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các
khái
niệm
định trước. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc
đượ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 phần tử dữ liệu (data tuple), có thể là

Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu mới.
Trước
tiên
độ 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 đó. Kỹ
thuật này sử dụng một tập dữ liệu kiểm tra
với
các mẫu đã được gán nhãn lớp.
Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong
tập
dữ liệu đào
tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ lệ phần trăm các
các
mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế). Nếu
độ chính xác của
mô
hình được ước lượng dựa trên tập dữ liệu đào tạo thì kết quả
thu được là rất khả quan vì mô hình
luôn
có xu hướng “quá vừa” dữ liệu. Quá vừa
dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ
liệu
thực tế vì quá trình xây
dựng mô
hình phân lớp từ tập dữ liệu đào tạo có thể kết hợp từ các đặc điểm riêng
biệt của tập dữ liệu đó
Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập
dữ liệu đào tạo. Nếu độ

h1 8
S
p
o
r

t

s
H
ig

h4 0
S
p

o
r

t

s
H
ig

h5 0
F a m
i

ly


If age <31
Or car Type = Sport
Then Rist = Hight
Tranning Data
Classification algorithm
Classifier (model)
Classifier (model)
Test Datad
A g e
C a r
T y

p e

R

i
s k

2 0
C o m
b

i
H
ig

h1 8
S

M
in
iv a
nL

o w

3 0
C o m
b

i
H
ig

h3 2
F a m
i

ly
L o
w4 0
C o m
b

iL

o w

R is k

Một số ứng dụng phân lớp tiêu biểu:
- Tín dụng: phân lớp khách hàng…
- Tiếp thị: phân lớp nhu cầu mua hàng của khách hàng…
- Chẩn đoán y khoa: từ một số triệu chứng -> xác định bệnh…
- Phân tích hiệu quả điều trị: kiểm tra tính đúng đắn của luật phân lớp
Tiến trình phân lớp dữ liệu:
Tiến trình gồm hai bước:
- Xây dựng mô hình từ tập huấn luyện, mô hình được biểu diễn bởi các luật
phân lớp, các cây quyết định hoặc các công thức toán học.
- Sử dụng mô hình: kiểm tra tính đúng đắn của mô hình và dùng nó để phân
lớp dữ liệu mới.
Tiền xử lý dữ liệu để tiến hành phân lớp:
Bao gồm các công việc:
- Làm sạch dữ liệu: dữ liệu nhiễu, các giá trị trống…
- Phân tích sự liên quan giữa các dữ liệu để chọn đặc trưng
- Biến đổi dữ liệu về dạng dữ liệu rời rạc, số hóa dữ liệu
Các phương pháp phân lớp:
- Phân lớp bằng mạng Neural lan truyền ngược
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 6
Classifier (model)
Test Data
A g e
C a r
T y

p e

R

i

- Hướng tập mờ
Tiêu chuẩn để đánh giá các phương pháp phân lớp:
Đánh giá các phương pháp phân lớp dựa trên:
- Độ chính xác
- Tốc độ
- Bền vững
- Gia/giảm: phân lớp các tập dữ liệu có hàng triệu mẫu và hàng trăm thuộc tính
với tốc độ chấp nhận được.
- Có thể biểu diễn được
- Dễ làm
Độ chính xác trong phân lớp:
Dùng một trong các cách sau để ước lượng tỉ lệ sai:
- Phân hoạch: dành cho tập dữ liệu lớn
 Dùng hai tập dữ liệu độc lập: tập huấn luyện (2/3), tập kiểm tra (1/3)
- Kiểm tra chéo: dành cho tập dữ liệu vừa
 Chia tập dữ liệu thành k mẫu con
 Sử dụng (k – 1) mẫu con làm tập huấn luyện và một mẫu con làm tập kiểm tra,
kiểm tra chéo k thành phần.
- Bootstrapping: dành cho tập dữ liệu nhỏ
Xóa dần mỗi lần 1 phần tử của tập dữ liệu để kiểm tra.
CHƯƠNG 2: CÂY QUYẾT ĐỊNH ỨNG DỤNG TRONG PHÂN
LỚP DỮ LIỆU
I. TỔNG QUAN VỀ CÂY QUYẾT ĐỊNH:
1. Giới thiệu chung:
Cây quyết định (decision tree) là một phương pháp rất mạnh và phổ biến cho cả hai
nhiệm vụ của khai phá dữ liệu là phân loại và dự báo. Mặt khác, cây quyết định còn có thể
chuyển sang dạng biểu diễn tương đương dưới dạng tri thức là các luật If-Then.
Cây quyết định là cấu trúc biễu diễn dưới dạng cây. Trong đó, mỗi nút trong (internal
node) biễu diễn một thuộc tính, nhánh (branch) biễu diễn giá trị có thể có của thuộc tính,
mỗi lá (leaf node) biểu diễn các lớp quyết định và đỉnh trên cùng của cây gọi là gốc (root).

, , x x x
là các biến sẽ giúp ta thực hiện công việc đó.
2. Các kiểu cây quyết định:
Cây quyết định còn có hai tên khác:
o Cây hồi quy (Regression tree): ước lượng các hàm giá có giá trị là số thực
thay vì được sử dụng cho các nhiệm vụ phân loại. (ví dụ: ước tính giá một
ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện)
o Cây phân loại (Classification tree): nếu y là một biến phân loại như: giới
tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua).
Ví dụ:
Ta sẽ dùng một ví dụ để giải thích về cây quyết định:
David là quản lý của một câu lạc bộ đánh golf nổi tiếng. Anh ta đang có rắc rối chuyện
các thành viên đến hay không đến. Có ngày ai cũng muốn chơi golf nhưng số nhân viên câu
lạc bộ lại không đủ phục vụ. Có hôm, không hiểu vì lý do gì mà chẳng ai đến chơi, và câu lạc
bộ lại thừa nhân viên.
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 8
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Mục tiêu của David là tối ưu hóa số nhân viên phục vụ mỗi ngày bằng cách dựa theo
thông tin dự báo thời tiết để đoán xem khi nào người ta sẽ đến chơi golf. Để thực hiện điều
đó, anh cần hiểu được tại sao khách hàng quyết định chơi và tìm hiểu xem có cách giải thích
nào cho việc đó hay không.
Vậy là trong hai tuần, anh ta thu thập thông tin về:
Quang cảnh (outlook), nắng (sunny), nhiều mây (clouded) hoặc mưa (raining)). Nhiệt độ
(temperature), độ ẩm (humidity). Có gió mạnh (windy) hay không.
Và tất nhiên là số người đến chơi golf vào hôm đó. David thu được một bộ dữ liệu gồm
14 dòng và 5 cột.
Dữ liệu chơi golf
Các biến độc lập Biến phụ thuộc
Quang cảnh Nhiệt độ Độ ẩm Gió Chơi
Nắng Nóng Cao Nhẹ Không

nhân viên nghỉ vào những ngày trời nắng và ẩm, hoặc những ngày mưa gió. Vì hầu như sẽ
chẳng có ai chơi golf trong những ngày đó. Vào những hôm khác, khi nhiều người sẽ đến
chơi golf, anh ta có thể thuê thêm nhân viên thời vụ để phụ giúp công việc.
Lưu ý :
o Cây quyết định trên không có sự tham gia của thuộc tính “Nhiệt độ” trong
thành phần cây, các thuộc tính như vậy được gọi chung là các thuộc tính dư
thừa bởi vì các thuộc tính này không ảnh hưởng đến quá trình xây dựng mô
hình của cây.
o Các thuộc tính tham gia vào quá trình phân lớp thông thường có các giá trị
liên tục hay còn gọi là kiểu số (ordered or numeric values) hoặc kiểu rời rạc
hay còn gọi là kiểu dữ liệu phân loại (unordered or category values). Ví dụ
kiểu dữ liệu độ ẩm hay lương có thể biểu diễn bằng số thực là kiểu dữ liệu
liên tục, kiểu dữ liệu giới tính là kiểu dữ liệu rời rạc (có thể rời rạc hóa thuộc
tính giới tính một cách dễ dàng).
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 10
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Kết luận là cây quyết định giúp ta biến một biểu diễn dữ liệu phức tạp thành một cấu trúc
đơn giản hơn rất nhiều.
Ưu điểm cây quyết định:
So với các phương pháp khai phá dữ liệu khác, cây quyết định là phương pháp có một
số ưu điểm:
• Cây quyết định dễ hiểu. Người ta có thể hiểu mô hình cây quyết định sau khi
được giải thích ngắn.
• Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết.
Các kỹ thuật khác thường đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ
(dummy variable) và loại bỏ các giá trị rỗng.
• Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là
tên thể loại. Các kỹ thuật khác thường chuyên để phân tích các bộ dữ liệu chỉ
gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến
tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số.

Mưa Ấm áp Cao Nhẹ Có
Mưa Mát TB Nhẹ Có
Mưa Mát TB Mạnh Không
Âm u Mát TB Mạnh Có
Nắng Ấm áp Cao Nhẹ Không
Nắng Mát TB Nhẹ Có
Mưa Ấm áp TB Nhẹ Có
Nắng Ấm áp TB Mạnh Có
Âm u Ấm áp Cao Mạnh Có
Âm u Nóng TB Nhẹ Có
Mưa Ấm áp Cao Mạnh Không
III. PHƯƠNG PHÁP XÂY DỰNG CÂY QUYẾT ĐỊNH:
• Việc tạo cây quyết định bao gồm 2 giai đoạn : Tạo cây và tỉa cây .
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 12
Cao
Nhẹ
Âm u
Trung bình
Mạnh
Nắng
Mưa
Không
Không
Có
Có
Có
Quang cảnh
Độ ẩm
Gió
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc

Phân tách tốt
Phép
phân tách tốt
Phép phân tách kémPhép phân tách kém
DỮ LIỆU GỐC
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Thuật toán xây dựng cây quyết định hết sức thấu đáo. Chúng bắt đầu bằng việc
chọn mỗi biến đầu vào chưa được chọn và đo mức độ tăng độ tinh khiết trong các kết quả
ứng với mỗi biến. Sau đó một phép tách tốt nhất sẽ được sử dụng trong phép tách khởi đầu,
để tạo hai hay nhiều nút con. Nếu không phép phân tách nào có khả năng (có thể do có quá
ít bản ghi) hoặc do không có phép phân tách nào làm tăng độ tinh khiết thì thuật toán kết
thúc và nút đó trở thành nút lá.
Phép phân tách trên các biến đầu vào kiểu số: đối với sự phân tách nhị phân trên
một biến đầu vào, mỗi giá trị mà biến đó chứa đều có thể trở thành giá trị dự tuyển. Phép
phân tách nhị phân dựa trên biến đầu vào kiểu số có dạng X < N. Để cải thiện hiệu năng,
một số thuật toán không kiểm tra hết toàn bộ các giá trị của biến mà chỉ kiểm tra trên tập
mẫu giá trị của biến đó.
Phép phân tách trên các biến đầu vào định tính : thuật toán đơn giản nhất trong việc
phân tách trên một biến định tính là ứng với mỗi giá trị của biến đó, ta tạo một nhánh tương
ứng với một lớp được phân loại. Phương pháp này được sử dụng thực sự trong một số
phần mềm nhưng mang lại hiệu quả thấp. Một phương pháp phổ biến hơn đó là nhóm các
lớp mà dự đoán cùng kết quả với nhau. Cụ thể, nếu hai lớp của biến đầu vào có phân phối
đối với biến đích chỉ khác nhau trong một giới hạn cho phép thì hai lớp này có thể hợp nhất
với nhau.
Phép phân tách với sự có mặt của các giá trị bị thiếu: một trong những điểm hay
nhất của cây quyết định là nó có khả năng xử lý các giá trị bị thiếu bằng cách coi giá trị rỗng
(NULL) là một nhánh của nó. Phương pháp này được ưa thích hơn so với việc vứt các bản

• Lớp N: Chơi_tennis = “Không”
• Thông tin cần thiết để phân lớp một mẫu được cho là:
• Xét thuộc tính ‘Quang cảnh’ ta có :
○ ‘Quang cảnh’ = ‘Nắng’:
Info ([2,3]) = entropy (2/5, 3/5) = – 2/5log
2
(2/5) – 3/5log
2
(3/5) = 0.971
○ ‘Quang cảnh’ = ‘Âm u’:
Info ([4,0]) = entropy (1, 0) = – 1log
2
(1) – 0log
2
(0) = 0
Do không có log
2
(0) nên ta quy ước nó bằng 0
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 15
2 2
( , ) ( , ) log log
p n p p n n
Info p n Entropy
p n p n p n p n p n p n
= = − −
+ + + + + +
1
( ) ( , )
i i
i i

○ ‘Độ ẩm’ = ‘Cao’:
Info ([3,4]) = entropy (3/7, 4/7) = – 3/7log
2
(3/7) – 4/7log
2
(4/7) = 0.985
○ ‘Độ ẩm’ = ‘Trung bình’:
Info ([6,1]) = entropy (6/7, 1/7) = – 6/7log
2
(6/7) – 1/7log
2
(1/7) = 0.592
Entropy(Độ ẩm)= 7/14 Info(3,4) + 7/14 Info(6,1)
= 7/14* 0.985 + 7/14* 0.592 = 0.789
Gian(Độ ẩm) = Info(9,5) – Entropy(Độ ẩm)
= 0.940 – 0.798 = 0.151
Tương tự cho các thuộc tính còn lại ta có:
Rõ ràng ban đầu ta sẽ chọn thuộc tính ‘Quang cảnh’ để phân tách. Sau đó làm tương tự
ta sẽ được cây quyết định cuối cùng có dạng
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 16
5 4 5
( ) (2,3) (4,0) (3,2)
14 14 14
Entropy Quang canh Info Info Info
= + +
( ) (9,5) ( )Gain Quang canh Info Entropy Quang canh
= −
( ) 0.246
( ) 0.151
( ) 0.048

VÍ DỤ 1:
R
1
: If (Quang cảnh=Nắng) ∧ (Độ ẩm=Cao) Then Chơi=Không
R
2
: If (Quang cảnh=Nắng) ∧ (Độ ẩm=Trung bình) Then Chơi=Có
R
3
: If (Quang cảnh=Âm u) Then Chơi=Có
R
4
: If (Quang cảnh=Mưa) ∧ (Gió=Mạnh) Then Chơi=Không
R
5
: If (Quang cảnh=Mưa) ∧ (Gió=Nhẹ) Then Chơi=Có
CHƯƠNG 3: CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT
ĐỊNH
Phần lớn các thuật toán phân lớp dữ liệu dựa trên cây quyết định có mã như sau:
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 18
Không
Có CóKhông
Cao
Mạnh
Nhẹ
Quang cảnh
Độ ẩm
Gió
Nắng Mưa
TB

không. Giải thuật ID3 sẽ học cây quyết định từ tập hợp các ví dụ sau:
Tập dữ liệu này bao gồm 14 ví dụ. Mỗi ví dụ biểu diễn cho tình trạng thời tiết gồm
các thuộc tính quang cảnh, nhiệt độ, độ ẩm và gió; và đều có một thuộc tính phân loại ‘chơi
Tennis’ (có, không). ‘Không’ nghĩa là không đi chơi tennis ứng với thời tiết đó, ‘Có’ nghĩa là
ngược lại. Giá trị phân loại ở đây chỉ có hai loại (có, không), hay còn ta nói phân loại của tập
ví dụ của khái niệm này thành hai lớp (classes). Thuộc tính ‘Chơi tennis’ còn được gọi là
thuộc tính đích (target attribute).
Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính quang cảnh có ba giá
trị (âm u, mưa, nắng), nhiệt độ có ba giá trị (nóng, mát, ấm áp), độ ẩm có hai giá trị (cao, TB)
và gió có hai giá trị (mạnh, nhẹ). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn
bài toán.
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 19
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Từ tập dữ liệu rèn luyện này, giải thuật ID3 sẽ học một cây quyết định có khả năng
phân loại đúng đắn các ví dụ trong tập này, đồng thời hy vọng trong tương lai, nó cũng sẽ
phân loại đúng các ví dụ không nằm trong tập này.
Sau khi giải thuật đã quy nạp được cây quyết định, thì cây này sẽ được sử dụng để
phân loại tất cả các ví dụ hay thể hiện (instance) trong tương lai. Và cây quyết định sẽ không
thay đổi cho đến khi ta cho thực hiện lại giải thuật ID3 trên một tập dữ liệu rèn luyện khác.
Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân loại đúng
tất cả các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây quyết định khác nhau tùy
thuộc vào thứ tự của các kiểm tra trên thuộc tính.
Giải thuật ID3 xây dựng cây quyết định từ trên xuống
ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên xuống. Lưu ý rằng đối với bất kỳ
thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập
con tách rời, mà ở đó mọi ví dụ trong một phân vùng (partition) có một giá trị chung cho
thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của cây và dùng trắc
nghiệm này để phân vùng tập hợp các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy
một cây con cho từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân
vùng đều nằm trong cùng một lớp; lớp đó trở thành nút lá của cây.

xóa P ra khỏi tập_thuộc_tính;
với mỗi giá trị V của P
begin
tạo một nhánh của cây gán nhãn V;
Đặt vào phân_vùngV các ví dụ trong tập_ví_dụ có giá trị V tại
thuộc tính P;
Gọi induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết quả
vào nhánh V
end
end
end
 Các khả năng có thể có của các phân vùng (partition):
Trong quá trình xây dựng cây QĐ, phân vùng của một nhánh mới có thể có các dạng sau:
 Có các ví dụ thuộc các lớp khác nhau, chẳng hạn như có cả ví dụ âm và dương.
 Tất cả các ví dụ đều thuộc cùng một lớp, chẳng hạn như toàn âm hoặc toàn dương.
 Không còn ví dụ nào => giải thuật trả về mặc nhiên
 Không còn thuộc tính nào => nghĩa là dữ liệu bị nhiễu, khi đó giải thuật phải sử dụng
một luật nào đó để xử lý, chẳng hạn như luật đa số (lớp nào có nhiều ví dụ hơn sẽ
được dùng để gán nhãn cho nút lá trả về).
Từ các nhận xét này, ta thấy rằng để có một cây QĐ đơn giản, hay một cây có chiều cao
là thấp, ta nên chọn một thuộc tính sao cho tạo ra càng nhiều các phân vùng chỉ chứa các ví
dụ thuộc cùng một lớp càng tốt. Một phân vùng chỉ có ví dụ thuộc cùng một lớp, ta nói phân
vùng đó có tính thuần nhất. Vậy, để chọn thuộc tính kiểm tra có thể giảm thiểu chiều sâu của
cây QĐ, ta cần một phép đo để đo tính thuần nhất của các phân vùng, và chọn thuộc tính
kiểm tra tạo ra càng nhiều phân vùng thuần nhất càng tốt. ID3 sử dụng lý thuyết thông tin để
thực hiện điều này.
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 21
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất?
a. Entropy đo tính thuần nhất của tập ví dụ

p
+
- p
-
log
2
p
-
Một cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả sử là
có c giá trị phân loại thì công thức entropy tổng quát là:
Entropy(S) =
∑
=
−
C
i
ii
pp
1
2
log
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 22
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
b. Lượng thông tin thu được đo mức độ giảm entropy mong đợi
Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa
một phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lượng
thông tin thu được, nó đơn giản là lượng giảm entropy mong đợi gây ra bởi việc phân chia
các ví dụ theo thuộc tính này.
Một cách chính xác hơn, Gain(S,A) của thuộc tính A, trên tập S, được định nghĩa như sau:
)(

Nắng
Âm u Mưa
[2+, 3-] [4+, 0-] [3+, 2-]
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Gain(S, Quang cảnh) = Entropy(S) – (5/14)Entropy(S
Nắng
) – (4/14)Entropy(S
Âm u
) – (5/14)
Entropy(S
Mưa
) = 0.940 – (5/14)(5/14)(- (2/5)log
2
(2/5) – (3/5)log
2
(3/5)) - (4/14)(0) -
(5/14)(- (3/5)log
2
(3/5) – (2/5)log
2
(2/5)) = 0.246
Gain(S, Nhiệt độ) = Entropy(S) - (4/14)×Entropy(S
Nóng
) - (6/14)×Entropy(S
Ấm áp
) –
(4/14)×Entropy(S
Mát
)
= 0.940 – (4/14)(1) - (6/14)(- (4/6)log

(7/14)(- (6/7)log
2
(6/7) – (1/7)log
2
(1/7)) = 0.151
HV: Lương Văn Nguyên (CH1102005) – Cao học 07 Trang 24
Nhiệt độ
Nóng
Ấm áp Mát
[2+, 2-] [4+, 2-] [3+, 1-]
Gió
Mạnh Nhẹ
[3+, 3-] [6+, 2-]
Độ ẩm
Cao TB
[3+, 4-] [6+, 1-]
Nghiên cứu các thuật toán phân lớp dữ liệu trên cây quyết định GVHD: PGS.TS. Đỗ Phúc
Ta thấy Gain(S, Quang cảnh) là lớn nhất  lấy thuộc tính quang cảnh làm nút gốc
Sau khi lập được cấp đầu tiên của cây quyết định ta lại xét nhánh Nắng
Entropy(S
Nắng
) = - (3/5)log
2
(3/5) – (2/5)log
2
(2/5) = 0.971
Gain(S
Nắng
, Nhiệt độ) = Entropy(S
Nắng

Mát
Nắng
Quang cảnh
[0+, 2-] [1+, 1-] [1+, 0-]
Gió
Mạnh
Nắng
Quang cảnh
[1+, 1-] [1+, 2-]
Nhẹ