ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

ỨNG DỤNG GIẢI THUẬT NAÏVE BAYES VÀO
BÀI TOÁN PHÂN LỚP VÀ TRÍCH XUẤT KEYPHRASE
CHO TÀI LIỆU HỌC TẬP CÔNG NGHỆ THÔNG TIN

GVHD : PGS.TS VŨ THANH NGUYÊN
HVTH : NGUYỄN VĂN TIẾN
MSHV: CH1301109
Lớp : CH-08 TP. Hồ Chí Minh – Tháng 3 Năm 2014
Nguyn Vn Tin CH1301109 Trang 2

MC LC
I. C S Lí THUYT V THUT TON BAYES V CC VN
LIấN QUAN. 3
1. Cỏc cụng thc xỏc sut 3
2. Cụng thc Bayes 4
3. Bi toỏn phõn lp 4
4. Thut toỏn Naùve Bayes 4
II. NG DNG NAẽVE BAYES V ONTOLOGY VO BI TON
PHN LP V TRCH XUT KEYPHRASE 5
1. t vn 5
2. Ni dung ti: 6
3. Phng phỏp xõy dng mụ hỡnh Naùve Bayes 6

 Công thức xác suất có điều kiện:
)(
)(
)(
)(
)(
)(
AP
ABP
A|BP
BP
ABP
B|AP



 Công thức nhân xác suất: P(AB)=P(A).P(B|A)=P(B).P(A|B)
 Công thức độc lập xác suất: A
1
, A
2
,…, A
n
độc lập với nhau  P(A
1
.A
2
.….A
n
)

n
}
 Một tập cố định các phân lớp C = {c
1,
c
2
, …, c
l
}
Đầu ra: Phân lớp c
i
mà mẫu X thuộc về.
4. Thuật toán Naïve Bayes
Quá trình học: cho một tập tài liệu huấn luyện S

;in examples with )|( estimate)|(
ˆ

),1 ;,,1( attributeeach of valueattributeevery For
;in examples with )( estimate)(
ˆ

of t valueeach targeFor
1
S
S
ijkjijkj
jjjk
ii
Lii

[)(
ˆ
)]|(
ˆ
)|(
ˆ
[
1
*
1
***
1







Nguyễn Văn Tiến – CH1301109 Trang 5 II. ỨNG DỤNG NAÏVE BAYES VÀ ONTOLOGY VÀO BÀI TOÁN
PHÂN LỚP VÀ TRÍCH XUẤT KEYPHRASE
1. Đặt vấn đề
Thế giới dưới sự ảnh hưởng mạnh mẽ này cũng dần dần chuyển sang một nền kinh
tế xã hội mà tri thức là nguồn lực chủ yếu. Với sự xuất hiện của Internet tốc độ cao, các

viên sẽ được xác định và các giá trị đặc trưng của từng cụm ứng viên sẽ được tính toán.
Mỗi cụm ứng viên sẽ được gán nhãn là cụm từ khóa hay không là cụm từ khóa
dựa vào những cụm từ khóa do tác giả chỉ định. Quá trình huấn luyện sẽ sinh ra một một
mô hình và mô hình này được dùng để dự đoán lớp cho các mẫu dữ liệu mới, sử dụng
các giá trị các đặc trưng đã được tính toán.

Nguyễn Văn Tiến – CH1301109 Trang 7 Hình 1: Quá trình huấn luyện – xây dựng mô hình máy học Naïve Bayes
ONTOLOGY
Cập nhật các ứng viên dưới sự giám sát của

Xây dựng mô
hình huấn
luyện Naïve
Bayes
Một tập các ứng viên
Đánh dấu các ứng viên có phải là
keyphrase hay không dựa vào tập
keyphrase kèm theo tài liệu
Xây dựng mô hình:
 Rời rạc hóa các đặc trưng.
 Tính toán lớp xác xuất.
 TÍnh xác suất P
YES
, P
NO
Nguyễn Văn Tiến – CH1301109 Trang 8

4. Các đặc trưng dùng để phân lớp dữ liệu
Để xây dựng được một mô hình hoàn chỉnh cho phương pháp trích xuất ta cần những
đặc trưng cơ bản sao cho từ những đặc trưng cơ bản đó chúng ta sẽ xây dựng được mô
hình máy học cho trích xuất.
Ở đây, chúng ta sẽ sử dụng các đặc trưng sau để xây dựng mô hình máy học:
a. TF, IDF, TFxIDF.
TF được gọi là tần số thuật ngữ, là tần số xuất hiện của một từ hoặc một cụm từ trong
một văn bản.
IDF là tần số nghịch của một từ trong một tập các văn bản.
TFxIDF là kết quả của hai số liệu thống kê tần số từ (thuật ngữ) TF và tần số nghịch
của một từ trong tập ngữ liệu IDF.
Giá trị TFxIDF là một thống kê phản ánh tầm quan trọng của một từ trong tài liệu
trong một tập ngữ liệu. Nó thường được sử dụng như một yếu tố quan trọng trong trích

D
idf t D
td


(3.2)
Trong đó:
 idf(t ,D): số tài liệu chứa từ hay cụm từ t trong tập tài liệu D.
 |D|: tổng số văn bản trong tập D.
 |{dD :td}|: số lượng văn bản chứa từ nhất định, với điều kiện t xuất
hiện trong văn bản d (hay: tf(t ,d)  0). Nếu từ đó không xuất hiện trong
tập mẫu nào trong tập thì mẫu số sẽ bằng 0 nên phép chia cho không
không hợp lệ, vì thế người ta thường thay bằng mẫu thức:
1 |{d D:t d}|  
(3.3)
Cơ số logarit trong công thức (2) không thay đổi giá trị của 1 từ mà chỉ thu
hẹp khoảng cách của từ đó. Vì thay đổi cơ số sẽ dẫn đến việc giá trị của các từ thay
đổi bởi một số nhất định và tỷ lệ giữa các trọng lượng với nhau sẽ không thay đổi.
Nói cách khác, thay đổi cơ số sẽ không ảnh hưởng đến tỷ lệ giữa các giá trị IDF.
Tuy nhiên, việc thay đổi khoảng giá trị sẽ giúp tỷ lệ giữa IDF vs TF tương đồng để
dùng cho công thức TFxIDF.
 TFxIDF:
tfidf(t, d, D) = tf(t, d) x idf(t, D) (3.4)

b. Vị trí xuất hiện đầu tiên, vị trí xuất hiện cuối cùng.
Vị trí xuất hiện đầu tiên và vị trí xuất hiện cuối cùng của một từ hay cụm từ là một
trong những đặc trưng không thể thiếu trong trích xuất keyphrase. Vị trí xuất hiện đầu
Nguyễn Văn Tiến – CH1301109 Trang 10

tiên và cuối cùng của một từ hay cụm từ cho ta biết được sự quan trọng của từ hay cụm

programming by demonstration
demonstration method
(3.7)
(3.8)
Nguyễn Văn Tiến – CH1301109 Trang 11

programming by demonstration
method

5. Xây dựng mô hình Naïve Bayes
Dựa vào quy trình trên (hình 1) chúng ta sẽ phân ra 2 giai đoạn để xây dựng mô hình
Máy học cho bài toán như sau:
a. Quá trình được chuyên gia/ người có kiến thức về lĩnh vực công nghệ thông tin:
Người có chuyên môn trong lĩnh vực Khoa học máy tính sẽ thu thập các bài
báo và các bài viết khoa học về ngành Khoa học máy tính.
Sau khi thu thập các bài báo về lĩnh vực này, ta phân các tài liệu này thành
hai tập khác nhau, một tập dùng để huấn luyện xây dựng mô hình, một tập dùng
để kiểm tra hiệu năng của mô hình vừa xây dựng. Đối với tập tài liệu dùng để
huấn luyện, ta thực hiện việc trích xuất bằng tay các keyphrase cho tài liệu, công
việc này được thực hiện bằng cách duyệt qua các phần chính của bài báo như:
title, abstract, keyword và các tiêu đề chính trong bài báo để chọn ra các keyphrase
cho tài liệu. Sau khi chọn được các keyphrase cho tài liệu ta tiến hành lưu các
keyphrase của từng tài liệu vào các tập tin có dạng <Tên tài liệu>.key được lưu
trong cùng một thư mục với tài liệu, tập tin có cấu trúc như sau:
<keyphrase>
<keyphrase>
……………
<keyphrase>

b. Quá trình do máy tính thực hiện và xây dựng mô hình.

Sau đó, ta thực hiện tính toán xác suất lớp cho từng đặc trưng, với mỗi đặc trưng
ta có 2 lớp là “Yes” và “No”, xác suất cho từng lớp của mỗi đặc trưng được tính bằng
cách lấy tổng số các ứng viên có cùng thuộc tính quyết định chia cho tổng các ứng viên
có cùng giá trị của đặc trưng sau khi đã rời rạc hóa. Ví dụ: theo mô hình trên xác suất
của đặc trưng TFxIDF có giá trị rời rạc hóa là 1 của phân lớp “Yes” có giá trị là 0.0056.
Cuối cùng ta tính toán các xác suất ưu tiên P
Yes
và P
No
, 2 xác suất ưu tiên này được tính
bằng công thức sau: P
Yes
=


trong đó, Y là tổng số các keyphrase được gán sẵn, N là
tổng số các ứng viên mà không phải là keyphrase, ta có công thức tính P
No
tương tự như
sau: P
No
=


. Như vậy ta đã có được một mô hình hoàn chỉnh cho việc trích xuất
keyphrase.
6. Trích xuất Keyphrase cho tài liệu.
Để rút trích các cụm từ khóa từ một tài liệu mới, chương trình xác định các cụm
ứng viên và các giá trị đặc trưng, sau đó áp dụng mô hình đã xây dựng trong quá trình
huấn luyện. Mô hình xác định xác suất mà mỗi ứng viên là một cụm từ khóa. Sau đó










Nguyễn Văn Tiến – CH1301109 Trang 14

Trong đó:
Y: số lượng các cụm là cụm từ khóa (do tác giả chỉ định)
N: số lượng các cụm ứng viên không phải là cụm từ khóa.
Theo đánh giá Laplace để tránh xác suất 0 thì ta thay thế Y = Y + 1, và N = N + 1.
Xác suất tổng thể mà cụm ứng viên là cụm từ khóa được tính như sau:
 







Sau khi tính toán giá trị xác suất p. Các ứng viên được sắp theo thứ tự (tăng hay
giảm dần) của giá trị p này.
Chúng ta sẽ dựa vào xác suất p này để trích xuất những keyphrase được xem như
các keyword của các bài báo hay văn bản về khoa học máy tính.
III. CÀI ĐẶT VÀ THỬ NGHIỆM
1. Chức năng cơ bản:


Hình 3: Trích xuất dữ liệu từ văn bản.

Hình 4: Kết quả xây dựng mô hình Naïve Bayes
Nguyễn Văn Tiến – CH1301109 Trang 17 b. Trích xuất dữ liệu:

Hình 5: Rút trích ứng viên của một văn bản
Nguyễn Văn Tiến – CH1301109 Trang 18 Hình 6: Rút trích tập keyphrase cho văn bản

4. Kết quả đạt được và đánh giá:
Phương pháp phân lớp Bayes được xem như là thuật toán cơ bản nhất trong các thuật
toán. Nó được xem như tiền đề cho các phương pháp mới sau này như mạng neural,
SVM,… dùng để phân lớp dữ liệu.
Mặc dù là phương pháp cũ nhưng phân lớp Bayes là một định hướng tiếp cận theo
hướng sử dụng xác suất thống kê để xây dựng mô hình máy học. Nó được ứng dụng rộng
rãi ở nhiều lĩnh vực như: công nghệ tri thức, xử lý ngôn ngữ tự nhiên….

Nguyễn Văn Tiến – CH1301109 Trang 19

IV. TÀI LIỆU THAM KHẢO
[1] Ian H. Witten, Gordon W. Paynter, Eibe Frank, Carl Gutwin and Craig G. Nevill-
Manning, KEA: Practical Automatic keyphrase Extraction, ACM New York, NY,
USA, 1999.
[2] Olena Medelyan, Automatic keyphrase Indexing with a Domain-Specific