S dng thut toỏn Cõy quyt nh v Naùve Bayes trong phõn lp d liu
I HC QUC GIA TP. H CH MINH
TRNG I HC CễNG NGH THễNG TIN
BI THU HOCH MễN
MY HC V NG DNG
TI:
S DNG THUT TON
CY QUYT NH V NAẽVE BAYES TRONG
PHN LP D LIU
GVHD : PGS.TS. V Thanh Nguyờn
SVTH : Bựi Lờ Thun
MSSV : CH1301062
Lp : Cao hc khúa 8
Thỏng 03/2014
CH1301062 Trang 1
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
NHẬN XÉT CỦA GIẢNG VIÊN
Một số lợi ích của máy học:
- Các thông tin ngày càng nhiều, hàng ngày ta phải xử lý rất nhiều thông tin
đến từ nhiều nguồn khác nhau. Máy học có thể giúp xứ lý và dự báo các thông tin đó
bằng cách tạo ra các luất sản xuất từ dữ liệu thu thập.
- Ở những nơi không có chuyên gia, máy học có thể giúp tạo ra được các quyết
định từ các dữ liệu có được.
- Các thuật toán máy học có thể giúp xử lý khi dữ liệu không đầy đủ, không
chính xác.
- Máy học giúp thiết kế hệ thống huấn luyện tự động (mạng nơrôn nhân tạo) và
giải mã mối liên hệ giữa các tri thức được lưu trữ trong mạng từ dữ liệu.
Hiện nay, khối lượng thông tin ở các cơ sở dữ liệu, Internet … đã vượt giới hạn
rất nhiều, xét về khả năng nhận thức của con người, do vậy, giải quyết vấn đề tách rút
CH1301062 Trang 4
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
từ khối lượng khổng lồ đó lượng thông tin thực sự cần thiết cho ứng dụng cụ thể, đã
trở nên tuyệt đối cần thiết. Trong số các nhiệm vụ phân tích thông tin có nhiệm vụ
nhận biết mẫu, dự báo, phân tích trí tuệ đối với các dữ liệu (khai thác dữ liệu - Data
Mining) hỗ trợ việc đề ra quyết định, tạo dựng và bổ sung tri thức.
Với những yếu tố trên, ứng dụng máy học trong khai thác dữ liệu thực sự đã trở
thành một ngành nghiên cứu mang lại rất nhiều lợi ích thực tiễn. Nội dung của bài tiểu
luận này tập trung vào việc tìm hiểu phân lớp dữ liệu với các thuật toán phổ biến hiện
nay là cây quyết định và Naïve Bayes.
Em xin gửi lời cám ơn sâu sắc đến PGS.TS. Vũ Thanh Nguyên đã tận tình
giảng dạy, truyền đạt kiến thức, giúp em hiểu hơn về các ứng dụng của máy học, từ đó
tạo cho em định hướng để thực hiện bài thu hoạch này. Tuy nhiên do thời gian nghiên
cứu có hạn nên bài thu hoạch này không thể tránh khỏi những thiếu sót nhất định, em
rất mong nhận được sự góp ý của thầy để có thể hoàn thiện bài thu hoạch một cách tốt
nhất.
CH1301062 Trang 5
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu

CH1301062 Trang 6
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
1.2Phân loại
Các thuật toán máy học được chia làm 3 loại: học giám sát, học không giám sát
và học nửa giám sát
1.2.1Học có giám sát(Supervised Learning)
Đây là cách học từ những mẫu dữ liệu mà ở đó các kỹ thuật máy học giúp hệ
thống xây dựng cách xác định những lớp dữ liệu. Hệ thống phải tìm một sự mô tả cho
từng lớp (đặc tính của mẫu dữ liệu).
Người ta có thể sử dụng các luật phân loại hình thành trong quá trình học và
phân lớp để có thể sử dụng dự báo các lớp dữ liệu sau này.
Thuật toán học có giám sát gồm tập dữ liệu huấn luyện M cặp:
S = {(x
i
, c
j
)| i=1,…,M; j=1,…,C}
Các cặp huấn luyện này được gọi là mẫu, với
x
i
là vector n-chiều còn gọi là vector đặc trưng,
c
j
là lớp thứ j đã biết trước.
Thuật toán máy học giám sát tìm kiếm không gian của những giả thuyết có thể,
gọi là H. Đối với một hay nhiều giả thuyết, mà ước lượng tốt nhất hàm không được
biết chính xác f : x

c.
Tùy thuộc vào mức độ của thuật toán học giám sát, người ta có những mô hình

đóng vai trò thuộc tính lớp, mà chúng ta đang tiên đoán.
Kết quả sẽ là n tiêu chí phân lớp (n bộ phân lớp), với hy vọng là ít nhất một
trong n bộ phân lớp đó là đúng.
1.2.3Học nửa giám sát.
Học nửa giám sát là các thuật toán học tích hợp từ học giám sát và học không
giám sát. Việc học nửa giám sát tận dụng những ưu điểm của việc học giám sát và học
không giám sát và loại bỏ những khuyết điểm thường gặp trên hai kiểu học này.
CH1301062 Trang 8
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
CHƯƠNG II : PHÂN LỚP DỮ LIỆU
2.1Giới thiệu
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 dự
đoángiátrịcủanhữngnhãnxácđịnh(categoricallabel)haynhữnggiátrịrờirạc (discrete
value), 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 những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà nghiên
cứu trong nhiều lĩnh vực khác nhau như học máy (machine learning), hệ chuyên gia
(expert system), thống kê (statistics) Công nghệ này cũng ứng dụng trong nhiều lĩnh
vực khác nhau như: thương 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.
2.2 Quy trình phân lớp
Quá trình phân lớp dữ liệu gồm hai bước
2.2.1 Bước thứ nhất (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

liệu là tìm ra được một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao và có
khả năng mở rộng được. Trong đó khả năng mở rộng được của thuật toán được đặc
biệt trú trọng và phát triển
Có thể liệt kê ra đây các kỹ thuật phân lớp :
- Phương pháp dựa trên cây quyết định
- Phương pháp dựa trên luật
- Phương pháp Naïve Bayes
- Mạng Neural.
- SVM (hỗ trợ các máy tính vector).
- Tập thô
CH1301062 Trang 10
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
CHƯƠNG III : PHƯƠNG PHÁP PHÂN LỚP DỰA TRÊN CÂY
QUYẾT ĐỊNH
3.1 Định nghĩa
Cây quyết định là một cấu trúc phân cấp của các nút và các nhánh. Có 3 loại
nút trên cây:
+ Nút gốc.
+ Nút nội bộ: mang tên thuộc tính của Cơ sở dữ liệu.
+ Nút lá: mang tên lớp C
i
.
Ngoài ra, ta có nhánh: mang giá trị thuộc tính.
3.2 Các bước xây dựng cây quyết định
Gồm 2 bước để thực hiện xây dựng cây quyết định
- Bước 1: Thiết lập cây quyết định, bắt đầu từ gốc, kiểm tra các giá trị của
thuộc tính và phân chia các mẫu đệ qui
- Bước 2: Tỉa bớt cây, xác định và loại bỏ bớt các nhánh không ổn định hoặc cá
biệt.
CH1301062 Trang 11

+ p
i
là xác suất để một mẫu bất kỳ của D thuộc về lớp C
i
- Thông tin kỳ vọng để phân lớp một mẫu trong D là
Info (D) =
- Thuộc tính A có các giá trị : {a
1
, a
2
, …, a
v
}
CH1301062 Trang 12
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
- Dùng thuộc tính A để phân chia tập huấn luyện D thành v tập con {D
1
, D
2
, …,
D
V
}
- Thông tin cần thiết để phân chia D theo thuộc tính A
Info
A
(D) =
- Độ lợi thông tin (information gain) dựa trên phân chia theo thuộc tính A
Gain (A) = Info(D) – Info
A

…,D
v
}
gini
A
(D) =
- Tại mỗi cấp, chúng ta chọn thuộc tính có chỉ mục Gini nhỏ nhất để phân chia
tập dữ liệu.
3.5Bài toán ứng dụng
Cho tập dữ liệu huấn luyện
ID Bood Type Give birth Can fly Live in water Class
1 Warm Yes No No Mammals
2 Cold No No No Reptiles
CH1301062 Trang 13
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
3 Cold No No Yes Fishes
4 Warm Yes No Yes Mammals
5 Cold No No Some Amphibians
6 Cold No No No Reptiles
7 Warm Yes Yes No Mammals
8 Warm No Yes No Birds
9 Warm Yes No No Mammals
10 Cold Yes No Yes Fishes
11 Cold No No Some Reptiles
12 Warm No No Some Birds
13 Warm Yes No No Mammals
14 Cold No No Yes Fishes
15 Cold No No Some Amphibians
16 Cold No No No Reptiles
17 Warm No No No Mammals

(7/20) – (4/20)log
2
(4/20) – (3/20)log
2
(3/20) –
(4/20)log
2
(4/20)
= 2.201
Tính độ lợi thông tin cho các thuộc tính:
 Info
Boot Type
= (11/20)I
(7,0,0,0,4)
+ (9/20)I
(0,4,3,2,0)
= 1.208
 Gain (bood Type) = 2.201 – 1.208 = 0.993
 Info
give birth
= (7/20)I
(6,0,1,0,0)
+ (13/20)I
(0,4,3,2,0)
= 1.612
 Gain (give birth) = 2.201 – 1.612= 0.589
 Info
can fly
= (4/20)I
(1,0,0,0,3)

2
= “birds”, |D
1
| = 7, |D
2
| = 4
Info (D) = (-7/11) log
2
(7/11) – (4/11)log
2
(4/11) = 0.946
 Info
give birth
= (6/11)I
(6,0)
+ (5/11)I
(1,4)
= 0.328
 Gain (bood Type) = 0.946 – 0.328 = 0.618
 Info
can fly
= (4/11)I
(1,3)
+ (7/11)I
(6,1)
= 0.672
 Gain (can fly) = 0.946 – 0.6727 = 0.274
 Info
live in water
= (2/1)I

2
| = 3, |
D
3
| = 2
Info (D) = (-4/9) ) log
2
(4/9) – (3/9)log
2
(3/9) – (2/9)log
2
(2/9)= 1.530
 Info
give birth
(D)= (1/9)I
(0, 1, 0)
+ (8/9)I
(4, 2, 2)
= 1.333
 Gain (bood Type) = 1.530 – 1.333 = 0.197
 Info
can fly
(D)= 0 + (9/9)I
(4,3,2)
= 1.530
 Gain (can fly) = 0
 Info
live in water
(D)= (3/9)I
(0,3,0)

= “birds”
|D| = 5, |D
1
| = 1, |D
2
| = 4
Info(D) = -(1/5)log
2
(1/5) – (4/5) log
2
(4/5) = 0.722
 Info
can fly
= (3/5)I
Yes(0,3)
+ (2/5)I
No(1,1)
= 0.4
 Gain (can fly) = 0.722 – 0.4 = 0.322
 Info
live in water
= (1/5)I
Some(0,1)
+ (4/5)I
No(1,3)
= 0.649
 Gain (live in water) = 0.722 – 0.649 = 0.073
Chọn “Can Fly” làm thuộc tính phân loại cho bảng 1.2
CH1301062 Trang 17
Warm

No
Birds
Live in water
Birds
Some No
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
 Cây quyết định thu được
3.5.3 Tập luật
Có 6 luật
+ R1: If bood type = “warm” , give birth = “Yes”, Then Class = “mammals”
+ R2: If bood type = “warm” , give birth = “No”, can fly = “Yes” Then Class
= “Birds”
CH1301062 Trang 18
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
+ R3: If bood type = “warm” , give birth = “No”, can fly = “No”, live in water
= “Some” Then Class = “Birds”
+ R4: If bood type = “warm” give birth = “No”, can fly = “No”, live in water =
“No” Then Class = “Mammals”
+ R5: If bood type = “cold” , live in water = “Yes” Then Class = “Fishes”
+ R6: If bood type = “cold” , live in water = “No” Then Class = “Reptile”
3.6. Nhận xét
4.6.1. Ưu điểm
- Dễ dàng xây dựng cây
- Phân lớp mẫu mới nhanh
- Dễ dàng diển giải cho các cây có kích thước nhỏ
- Độ chính xác chấp nhận được so với các kỹ thuật phân lớp khác trên nhiều tập
DL đơn
4.6.2. Nhược điểm
- Khó giải quyết được những vấn đề có dữ liệu phụ thuộc thời gian liên tục - dễ
xảy ra lỗi khi có quá nhiều lớp chi phí tính toán để xây dựng mô hình cây quyết định

new
. X
new
được gán vào lớp có xác suất lớn nhất theo công thức
CH1301062 Trang 20
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
4.3 Làm trơn Laplace
Để tránh trường hợp giá trị P(X
k
|C
i
) = 0 do không có mẫu nào trong DL huấn kuyện
thỏa mãn tử số, ta làm trơn bằng cách thêm một số mẫu ảo.
Khi đó:
Làm trơn theo Laplace
Với m – số lớp và r là số giá trị rời rạc của thuộc tính
4.4 Bài toán ứng dụng
Cho tập dữ liệu huấn luyện
ID Outlook Temerature Humidity Windy Play
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcase Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Overcase Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes

new
= <Outlook = sunny, Temp = cool, Humidity = high, Windy = strong>
Các giá trị cần tính
P(C1)*P(X|C1) = P (C1) * P(Sunny|y) * P (Cool|y)*P(High|y)*P(Strong|y) = 0.005
P(C2)*P(X|C2) = P (C2) * P(Sunny|y) * P (Cool|y)*P(High|y)*P(Strong|y) = 0.021
Vậy X
new
thuộc lớp C2 (“No”)
CH1301062 Trang 22
Sử dụng thuật toán Cây quyết định và Naïve Bayes trong phân lớp dữ liệu
4.4.3 Làm trơn Laplace
Bước 1: Ước lượng P(C
i
) với C
1
= “Yes”, C
2
= “No” và P(x
k
|C
i
) theo công thức
Laplace.
Outlook
P(Sunny|y) = 3/12 P(Sunny|n) = 4/8
P(Overcast|y) = 5/12 P(Overcase|n) = 1/8
P(Rain|y) = 4/12 P(Rain|n) = 3/8
Temperature
P(Hot|y) = 3/12 P(Hot|n) = 3/8
P(Mild|y) = 5/12 P(Mild|n) = 3/8

4. />5. Naïve Bayes Classifier Slide - Ke Chen, Extended by Longin Jan Latecki
5. C. Apte and S. Weiss. Data mining with decision treesand decision rules. Future
Generation ComputerSystems, 13, 1997.
CH1301062 Trang 24