TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
‘KHÒATOÁN’
TRẦN THỊ HÀ
PHÂN LỚP NAI VE BAYES VÀ
ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI
HỌC • • • •
Chuyên ngành: ứng dụng
Người hướng dẫn khoa học
TRẦN TUẤN VINH
HÀ NỘI – 2014
Phân lớp naive Bayes và ứng dụng
________•__________
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành và sự biết ơn sâu sắc
tới thày Trần Tuấn Vinh đã tận tình hướng dẫn tôi ừong suốt quá trình
thực hiện khóa luận này.
Tôi xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo đã giảng
dạy tôi trong suốt 4 năm học qua, đã cho tôi những kiến thức quý báu
để tôi có thể vững bước trên con đường đi của mình.
Trong quá trình góp nhặt kiến thức các thày cô bạn bè là những
người đã cùng tôi sát cánh trong suốt thời gian tôi học tập và nghiên
cứu dưới mái trường Đại học Sư phạm Hà Nội 2.
Trong những nỗ lực đó, không thể không kể đến công lao to lớn
không gì có thể đền đáp được của cha mẹ những người đã sinh thành,
dưỡng dục tôi nên người, luôn nhắc nhở động viên tôi hoàn thành tốt
nhiệm vụ.
Hà Nội, tháng 5 năm 2014 Sinh viên
Trần Thị Hà
Phân lớp naive Bayes và ứng dụng
LỜI CAM ĐOAN

Chương I LÝ THUYẾT CHUNG
[1]
1.1. Biến cố ngẫu nhiên
1.1.1. Hiện tượng ngẫu nhiên
Người ta chia các hiện tượng xảy ra trong cuộc sống hàng ngày làm hai loại:
Tất nhiên và ngẫu nhiên.
- Những hiện tượng mà khi thực hiện ừong một điều kiện sẽ cho ra kết quả
như nhau được gọi là H I Ệ N T Ư Ợ N G T Ấ T N H I Ê N .
- Những hiện tượng mà cho dù khi được thực hiện ở ừong cùng một điều kiện
vẫn có thể cho ra các kết quả khác nhau được gọi là những H I Ệ N T Ư Ợ N G
N G Ẫ U N H I Ê N .
- Hiện tượng ngẫu nhiên chính là đối tượng khảo sát của lí thuyết xác suất.
1.1.2. Phép thử và biến cố
- Để quan sát các hiện tượng ngẫu nhiên, người ta cho các hiện tượng này
xuất hiện nhiều lần. Việc thực hiện một quan sát về một hiện tượng ngẫu
nhiên nào đó, để xem hiện tượng này có xảy ra hay không được gọi là một
phép thử.
- Khi thực hiện một phép thử, ta không thể dự đoán được kết quả xảy ra. Tuy
nhiên ta có thể liệt kê được tất cả các kết quả có thể xảy ra.
- Tập họp tất cả các kết quả có thể xảy ra của một phép thử được gọi là không
gian mẫu của phép thử kí hiệu Q. Biến cố không thể xảy ra được gọi
là biến cố rỗng kí hiệu Ộ .
- Biến cố ngẫu nhiên là biến cố có thể xảy ra hoặc không xảy ra khi thực hiện
phép thử.
- Biến cố sơ cấp là biến cố không thể phân tích được nữa.
Phân lớp naive Bayes và ứng dụng
6
1.1.3. Quan hêgiüa câc bien cô
- Quan hê kéo theo: Bien cô A dugc goi là kéo theo bien cô B khi và chî khi A
xày ra thi B xây ra. Ki hiêu: A Œ B

8
2. P(^) = 0
3. P { Q) = l
4. Nêu A Œ B thï P(A)<P ( B )
1.3. Công thirc tinh xac suât
1.3.1. Công thü'c công xac suât
Xét phép mot thü, ta cô càc công thüc công xac suât sau:
- Nêu A và B là hai bién cô tùy ÿ: P ( A ufi) = P ( A ) + P ( B ) - P ( A B )
- Nêu A và B là hai bien cô xung khac thi P ( A ^ J B ) = P ( A ) +
P ( B ) Nêu ho {Ai} (i=l,2, ,,n) xung khac tùng dôi thi
P(A
l
vA
2
u uA
n
) = P(A
l
) + P(A
2
) + + P(A
n
)
Chu ÿ: P(A) = 1-P(À),P(A) = P(AB) + P(ÀB)
1.3.2. Xac suât cô dieu kiên
1.3. 2 . 1 . D I N H N G H I A : Cho bien cô B vôi P { B ) > 0.
Xac suât cüa A khi biêt B xây ra là:
P(AI*) = ^
P(B)
Khi biêt B xây ra, xac suât cüa A IB ti le vai A . B , vây:

i
)
ẻ =1
1.4. Cụng thỹc
Bayes Dinh ly
Bayes
Binh li Bayes cho phộp tinh xc suõt xõy ra cỹa mot su kiờn ngõu nhiờn A khi
biờt su kiờn lien quan B dõ xõy ra. Xc suõt ny dugc ki hiờu l P { A I B ) v doc
l xc suõt cỹa A nờu cụ B. Bai luỗmg ny duỗrc goi l xc suõt cụ dieu kiờn hay
xc suõt hõu nghiờm vi nụ duỗrc rut ra tự giõ tri dugc cho cỹa B hoac phu thuục
vo giõ tri dụ.
Theo dinh li Bayes, xõc suõt xõy ra A khi biờt B sở phu thuục vo 3
r r
/V J /\
yeu to:
Xõc suõt xõy ra A cỹa riờng nụ, khụng quan tõm dộn B, ki
hiờu l P(A) v doc l xõc suõt cỹa A, dõy dugc goi l xõc
suõt tien nghiờm, nụ l tien nghiờm theo nghùa rang nụ khụng
quan tõm dờn bõt ki thụng tin no vờ B.
Phõn lp naive Bayes v ng dng
1
0
- Xâc suât xây ra B cüa riêng nô, không quan tâm dén A, ki hiêu là P { B ) và
doc là “xâc suât cüa B”. Dai luçmg này côn duoc goi là hang sô chuân hôa,
vi nô luôn giông nhau, không phu thuôc vào su kiên A dang muôn biêt.
- Xâc suât xày ra B khi biêt A xày ra, ki hiêu là P ( B I À ) và doc là “xâc
suât cüa B vôi dieu kiên A”. Nô là mot xâc suât hâu nghiêm và P { B ) là
mot xâc suât tien nghiêm cüa B. Dai luçmg này duoc goi là khâ nang xày ra
B khi biêt A da xày ra. Chu y không nhâm lân giüa khâ nang xày ra A khi
biêt B và xâc suât xày ra B khi biêt A.

xâc suât tien nghiêm.
Vi du suy luân Bayes âom giân
Bânh quy tù hôp nào?
Dê minh hoa, giâ su cô hai hôp dung dây bânh quy. Hôp thü nhât cô 10 chiêc
bânh quy sôcôla và 30 chiêc bânh quy bo. Hôp thü hai dung môi loai bânh 20
chiêc. Bé Khoai chon ngâu nhiên mot hôp, rôi nhat dai mot chiêc bânh. Ta cô thé
giâ thiét rang bé Khoai côn rât nhô nên không phân biêt hôp này hôp kia và bé
thich tât câ câc loai bânh keo nên bânh loai nào vai bé cüng vây. Và chiéc bânh mà
Phân lớp naive Bayes và ứng dụng
1
1
bé Khoai chon là mot chiéc bânh quy ba. Vây khâ nâng Khoai nhat chiêc bânh dô
tir trong hôp thù nhât là bao nhiêu?
Mot câch truc quan, cô vé rô rang là câu trâ loi phâi Ion hon 1/2, do trong hôp
1 cô nhiêu bânh quy ba han. Câu trâ loi chinh xâc duac tinh theo dinh lÿ Bayes. Giâ
sü H \ tuang ùng vai hôp 1 và H
2
tuang üng vai hôp 2. Ta biêt rang dôi vai bé
Khoai, hai hôp là nhu nhau, do dô, P { H
X
) = P ( H
2
) , và tông cüa chüng phâi
bang 1, do dô câ hai dèu bang 0.5. Dû lieu D là quan sât vê chiêc bânh quy ba. Tù
nôi dung cüa hai hôp bânh, ta biêt rang P I D L H , ) = 30/40 = 0.75 và P ( D \ H
2
)
= 20/40 = 0.5. Khi dô, công thüc Bayes cho ra kêt quâ:
«S. 10) =__________J-TO-ftP
1

1
2
Kĩ thuật phân lớp dữ liệu trong khai phá dữ liệu là một trong những vấn đề
nghiên cứu mở rộng hiện nay; tập trung chủ yếu vào thống kê, học máy và mạng
nơron. Kĩ thuật phân lớp được đánh giá là một kĩ thuật khai phá dữ liệu được sử
dụng rộng rãi nhất với nhiều mở rộng. Sự kết hợp của kỹ thuật phân lớp và cơ sở
dữ liệu là một lĩnh vực hứa hẹn bởi vì đáp ứng được một vấn đề hết sức quan trọng
của ứng dụng cơ sở dữ liệu đó là tính uyển chuyển cao.
2.2. Giới thiệu phân lớp naive Bayes
2.2.1. Định nghĩa
Phân lớp naive Bayes là một phương pháp phân lớp đơn giản dựa trên các ứng
dụng định lí Bayes với giả định độc lập bền vững. Một thuật ngữ mô tả chi tiết cho
những mô hình xác suất sẽ là “mô hình đặc trưng không phụ thuộc”.
Theo thuật ngữ đơn giản, một phân lớp naive Bayes giả định rằng sự có mặt
(hay không có mặt) của một đặc trưng của một lớp là không liên quan đến sự hiện
diện (hay thiếu vắng) của bất kì các đặc trưng.
Ví dụ: Một trái cây có thể được coi là một quả táo nếu có màu đỏ chung
quanh và đường kính khoảng 10 cm. Mặc dù các đặc trưng này phụ thuộc vào sự
tồn tại của các đặc trưng khác, phân lớp naive Bayes xem xét tất cả các đặc tính
độc lập góp phần vào khái niệm trái cây này là quả táo.
Tùy thuộc vào tính chính xác bản chất của mô hình xác suất,
phân lớp naive Bayes có thể được tạo ra rất hiệu quả trong
học máy. Trong nhiều ứng dụng thực tế, tham số ước lượng cho
các mô hình naive Bayes sử dụng các phương pháp maximum
likelihood (ước lượng hợp lí cực đại), nói cách khác,
với phương pháp này một ứng dụng dựa ừên mô hình naive Bayes thì sẽ
không phải sử dụng xác suất Bayes cũng như phương pháp Bayes.
Mặc dù với giả định đơn giản hơn nhưng dễ nhận thấy rằng phân lớp naive
Bayes thường hoạt động khá tốt trong nhiều tình huống phức tạp. Vào năm 2004
phân tích các vấn đề của phân lớp Bayes đã cho thấy rằng có một số giả thuyết giải

)
Trong thực hành, chỉ cần quan tâm tới tử số của phân số, khi mà mẫu số không
phu thuôc vào C và càc già tri cüa càc däc tnmg cüa F i dà cho nên mâu sô là häng.
Tü sô tuong duang voi mô hinh xàc suât:
p(Ç\F
l
, ,F
n
)
Tü sô cô thê duoc viêt lai nhu sau, su dung dinh nghïa cüa xâc suât cô dièu
kiên:
P
(C I F
l
, ,F
n
)
= P(C)-P(F
i
, ,F
n
)
= piQ.piF, I C).p(F
2
, ,F
n
I C,Fj)
= piQ.piF, I C).p(F
2
I C,F

I C}P(F
2
1 C,F
1
}p{F31 C,F
lt
F
2
y.p(F
M
I C
t
F
lt
F
2t
F
3t

t
F^)
Bây gio giâ dinh “naive” cô dieu kiên dôc lâp: Giâ dinh rang môi dac trung Fj
cô dièu kiên dôc lâp vai tât câ câc dac trung Fj vai j # i. Dièu này cô nghïa là:
p(F
l
\C,F
J
) = p(F
l
\C)

2.2.3. ước lượng tham số
Tất cả các mô hình tham số (lớp tiền nghiệm và hàm phân phối xác suất đặc
trưng) có thể được xấp xỉ với những tàn số tương đối trong tập huấn luyện.
Maximum likelihood là ước lượng của xác suất. Một lớp tiền nghiệm có thể được
tính bằng cách giả sử các lớp có xác suất ngang nhau. Prior = 1/số lớp hoặc tính
bằng cách ước lượng cho lớp xác suất từ tập huấn luyện (tiền nghiệm cho một lớp
đã đưa ra = số mẫu trong lớp/tổng số mẫu). Để ước lượng các tham số cho hàm
phân phối đặc trưng hoặc mô hình sinh ra không phải tham số cho những đặc trưng
từ tập huấn luyện.
[4]
Nếu tham số đang giải quyết những dữ liệu liên tục, một giả
thuyết đặc trưng đó là tiếp tục kết họp những giá ừị với mỗi lớp được phân phối
theo phân phối Gaussian.
Ví dụ: Giả sử tập huấn luyện chứa liên tiếp một thuộc tính X. Đầu tiên chúng ta
phân đoạn dữ liệu bởi các lớp sau đó tính toán số trung bình và phương sai của X
trong mỗi lớp. Đe J U
C
là giá trị trung bình của X kết họp với
lớp c và ĐỂ <7
C
2
là phương sai của giá trị X KẾT họp với lớp c thì
xác suất của một vài giá trị ĐÃ cho trong một lớp, P ( X = V I C )
có thể tính bằng cách đặt V vào phương trình cho bởi hàm phân
phối được tham số hóa bởi M C và cr
c
2
.
Phân lớp naive Bayes và ứng dụng
Phương pháp chung khác để xử lí tiếp các giá trị là sử dụng các giá trị rời rạc.

1
7
là mạnh đủ để bỏ qua các thiếu sót nghiêm trọng của nó ừong những mô hình xác
suất naive.
2.2.6. Phương pháp phân lớp Bay es
Lý thuyết Bayes cung cấp một tiếp cận theo xác suất để suy diễn. Nó dựa trên
giả thuyết rằng số lượng của khuynh hướng bị chi phối bởi phân bố xác suất và
quyết định tối ưu có thể được tạo bởi sự suy luận về những xác suất đi liền với dữ
liệu được quan sát. Đây là vấn đề quan ừọng của học máy bởi vì nó cung cấp một
tiếp cận định lượng cho việc xem xét cẩn thận bằng chứng hỗ trợ những giả thuyết
thay đổi.
Học theo xác suất: Tính các xác suất rõ ràng cho các giả thuyết, một ừong
những hướng thiết thực cho một số vấn đề thuộc loại học.
Tính tăng dàn: Mỗi ví dụ huấn luyện có thể tăng hoặc giảm dần khả năng
đúng của một giả thuyết. Kiến thức trước có thể kết họp với dữ liệu được quan sát.
Tiên đoán xác suất: Tiên đoán nhiều không gian giả thuyết, được đo bởi xác
suất của nó.
Tiêu chuẩn: Thậm chí khi phương thức Bayes khó tính toán, chúng cũng cung
cấp một tiêu chuẩn tốt nhất cho việc tạo quyết định tối ưu so với những phương
pháp khác.
2.2.7. Giới thiệu thuật toán naive Bayes
Naive Bayes (NB) là phương pháp phân loại dựa vào xác suất được sử dụng
rộng rãi ừong lĩnh vực học máy [Mitchell, 1996] [Joachims, 1997] [Jason, 2001],
được sử dụng làn đàu tiên ừong lĩnh vực phân loại bởi Maron vào năm 1961
[Maron, 1961] sau đó ừở nên phổ biến dùng trong nhiều lĩnh vực như trong các
công cụ tìm kiếm [Rijsbergen et al, 1970], các bộ lọc email [Sahamietal, 1998]
2.2.8. Phân lớp naỉve Bayes
Bộ phân lớp naive Bayes hay bộ phân lớp Bayes đơn giản (simple Bayes
classifier) hoạt động như sau:
Phân lớp naive Bayes và ứng dụng

P ( X ) là giống nhau với mọi lớp nên ta không cần tính. Do đó ta chỉ càn
tìm giá tn lớn nhất của P ( X 1C,)* P ( C Ị ).
\
D
i \
Chú ý răng P ( C Ị ) được ước lượng băng công thức P { C Ị ) = -j^j-, trong đó
Dị là tập các phàn tử dữ liệu thuộc vào lớp Cị. Nếu xác suất tiền nghiệm P{Cị )
cũng không xác định được thì ta coi chúng bằng nhau P{C
l
) = p(c
2
) = = p(c
m
),
khi đó ta chỉ cần tìm giá ừị P ( X I C Ị ) lớn nhất.
4. Khi số lượng các thuộc tính mô tả dữ liệu là lớn thì chi phí tính toán P { X I
C Ị ) là rất lớn, do đó để làm giảm độ phức tạp, giải thuật naive Bayes giả
thiết các thuộc tính là độc lập nhau hay không có sự phụ thuộc nào giữa các
thuộc tính. Khi đó ta có thể tính:
P ( X IC,)=P(^ IC
(
) (3)
%1
Chúng ta có thể ước lượng P(jCj ICJ),P(JC
2
IC
2
),P(xilCi), , P(jc
n
IC

ị {x-mf
g(x,m,ơ)= r—e

2 ơ ỉ

(4)
ơyLĨĨ
Và xác suất P { X
K
I c, ) được tính bằng công thức :
P{x
k
\c
i
) = g{x
k
,ụ
k
ci
,ơ
k
c
) (5)
Trong đó
M
C ’
Ơ
C là giá tậ ừung bình (mean) và độ lệch chuẩn (standard
deviation) của thuộc tính Ả
K

12 Middle-aged Medium No Exellent Yes
13 Middle-aged High Yes Fair Yes
14 Senior Medium No Exellent No
Giả sử khách hàng X có các giá trị thuộc tính là:
X=(age=youth,mcome=medium,student=yes,creditjating=fair)
Bây giờ ta cần xác định xem khách hàng X có thuộc lớp Cyes (mua máy
tính) hay không, ta tính toán như sau:
P(Cyes)=9/l4=0.643 ; P(C
no
)=5/14=0.357;
Trước khi tính xác suất P(XIQ), ta tính các xác suất thành phần:
P(age=youthlC
yes
)=2/9=0.222
P(age=youthlC
no
)=3/5=0.6
Phân lớp naive Bayes và ứng dụng
2
1
P(income=mediumlC
yes
)=4/9=0.444
P(income=mediumlC
no
)=2/5=0.4
P(student=yeslC
yes
)=6/9=0.667
P(student=yeslC

Nhiệt độ Độ ẩm Gió Chơi
tennis
1 Nắng Nóng Cao Yếu Không
2 Nắng Nóng Cao Mạnh Không
3 Âmu Nóng Cao Yếu Có
4 Mưa Bình thường Cao Yếu Có
5 Mưa Mát mẻ Bình thường Yếu Có
6 Mưa Mát mẻ Bình thường Mạnh Không
7 Âmu Mát mẻ Bình thường Mạnh Có
Phân lớp naive Bayes và ứng dụng
2
2
8 Nắng Bình thường Cao Yếu Không
9 Nắng Mát mẻ Bình thường Yếu Có
10 Mưa Bình thường Bình thường Yếu Có
11 Nắng Bình thường Bình thường Mạnh Có
12 Âmu Bình thường Cao Mạnh Có
Tập dữ liệu x= {ngoài trời là nắng, gió là mạnh}
Cyes là biến cố anh ta chơi tennis (bất kể nắng gió ra sao)
C
no
là biến cố anh ta không chơi tennis (bất kể nắng gió ra sao)
P(X) là xác suất ngoài ừời là nắng và gió là mạnh.
P(XICyes): Xác suất ngoài ừời là nắng và gió là mạnh nếu biết rằng anh
ta có chơi tennis.
P(C
yes
IX): Xác suất rằng anh ta chơi tennis nếu biết rằng ngoài trời là
nắng và gió là mạnh.
Bây giờ cần xác định xem anh ta có chơi tennis không nếu biết rằng ngoài

nhất, do đó thuật toán Bayes sẽ kết luận là anh ta không chơi tennis.
Trong quá trình tính toán công thức (3), ta có thể gặp trường họp
P ( X
K
I C
(
) = 0. Ví dụ trường hợp thuộc tính A
K
là giá trị rời rạc thì giá trị
£)*
P { X
K
I C Ị ) được tính theo công thức P { X
K
I C Ị ) = Ị^-Ị-
5
khi D Ị =0 ứiì
P ( X
K
I C Ị ) = 0. Điều này có nghĩa là P { X
K
I C Ị ) ứieo công ứiức (3) sẽ có giá
trị là 0. Để tránh trường họp này xảy ra, ta có thể sử dụng công thức ước lượng
Laplace , công thức Laplace có rất nhiều dạng tùy thuộc vào các bài toán khác
nhau, trong trường hợp cụ thể này ta có thể sử dụng công thức:
/ Ï
L + D
I X
P ( X
K

vào lớp văn bản c
k
được tính toán như sau:
Tài liệu di sẽ được gán cho loại văn bản nào có xác suất hậu nghiệm cao
nhất nên được biểu diễn bằng công thức:
Class of dị = argmax{p(c
fc
14.)} = arg max
ừong đó N là tổng số tài liệu.
Tóm lại phân loại văn bản sử dụng thuật toán naive Bayes có thể diễn đạt
một cách ngắn gọn như sau:
Với mỗi văn bản D (document) người ta sẽ tính cho mỗi loại một xác suất
mà tài liệu D có thể thuộc vào lớp tài liệu đó bằng việc sử dụng luật Bayes:
P{ c

k

)* P( d

i

I c

k

)
(
1
)