TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
MÔN HỆ CHUYÊN GIA
ĐỀ TÀI: TÍCH HỢP GÓI MÃ NGUỒN MỞ TÁCH TỪ
TỰ ĐỘNG VÀ ÁP DỤNG VÀO BÀI TOÁN PHÂN LOẠI
VĂN BẢN THEO NAVIE BAYS
Giảng viên hướng dẫn: NGUYỄN THỊ THU HÀ
Sinh viên thực hiện:
TRẦN VĂN ĐẠI
NGUYỄN VĂN LINH
VŨ VĂN TUẤN
Hà Nội, 06-2013
MỤC LỤC
2
DANH MỤC BẢNG
3
DANH MỤC TỪ VIẾT TẮT
Ký hiệu Diễn giải
WWW World Wide Web
VLSP Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lí tiếng nói và
văn bản tiếng Việt - Đề tài thuộc Chương trình Khoa học Công nghệ cấp
Nhà nước KC01/06-10
CRFs
Conditional Random Fields
VTB Viet Tree Bank
JRE Java Runtime Environment
XML eXtensible Markup Language - Ngôn ngữ Đánh dấu Mở rộng
RSS Rich Site Summary (RSS 0.91), RDF Site Summary (RSS 0.9 and 1.0),
Really Simple Syndication (RSS 2.0.0)
UTF-8 8-bit Unicode Transformation Format - Định dạng chuyển đổi Unicode

trong suốt thời gian học tập vừa qua. Nhờ có sự chỉ dạy tận tình của cô Nguyễn Thị
Thu Hà trực tiếp hướng dẫn giảng dạy, cùng sự đào tạo của các thầy cô bộ môn khác
trong thời gian qua giúp chúng em hoàn thành bài báo cáo này. Do đây là lần đầu tiên
triển khai một hệ thống có tính thực tiễn cao, nên quá trình triển khai có thể còn nhiều
sai sót. Mong các thầy cô đóng góp ý kiến giúp chúng em hiểu rõ hơn về bài toán.
Một lần nữa chúng em xin chân thành cảm ơn các thầy cô!
5
CHƯƠNG 1. BÀI TOÁN PHÂN LOẠI VĂN BẢN
1.1. Giới thiệu
Ngày nay, sự bùng nổ thông tin do bị tác động bởi sự xuất hiện của các siêu
phương tiện và World Wide Web (WWW) đã làm cho không gian dữ liệu gia tăng
thường xuyên, điều này tạo ra một thách thức cho các hệ thống truy vấn thông tin sao
cho có hiệu quả. Một trong những khó khăn mà các hệ thống thông tin thường phải
gặp đó là tần suất cập nhật của các thông tin quá lớn. 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ư là 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. Do đó số lượng văn bản số hóa ngày nay đang tăng dần theo cấp số nhân, cùng
với sự gia tăng của số lượng văn bản, nhu cầu tìm kiếm văn bản cũng tăng theo, khi đó
phân loại văn bản tự động là một yêu cầu cấp thiết được đặt ra. Phân loại văn bản giúp
sẽ giúp chúng ta tìm kiếm thông tin một cách nhanh chóng hơn thay vì phải tìm lần
lượt trong từng văn bản, hơn nữa khi mà số lượng văn bản đang gia tăng một cách
nhanh chóng thì thao tác tìm lần lượt trong từng văn bản sẽ mất rất nhiều thời gian,
công sức và là một công việc nhàm chán và không khả thi. Chính vì thế nhu cầu phân
loại văn bản tự động là thực sự cần thiết.
Có rất nhiều công trình nghiên cứu về phân loại văn bản và đã có được những
kết quả đáng khích lệ, như là: Support Vector Machine, K–Nearest Neighbor, Linear
Least Squares Fit, Neural Network, Naïve Bayes, Centroid Base… Điểm chung của
các phương pháp này đều dựa vào xác suất thống kê hoặc dựa vào trọng số của các từ,
cụm từ trong văn bản. Trong mỗi phương pháp đều có cách tính toán khác nhau, tuy
nhiên các phương pháp này đều phải thực hiện một số bước chung như: đầu tiên mỗi

toán) để chọn ra một họ các tham số tối ưu cho bộ phân loại.
Hình 1.1: Mô hình giai đoạn huấn luyện
Đầu vào: ngữ liệu huấn luyện và thuật toán huấn luyện
Đầu ra: mô hình phân lớp (bộ phân lớp – classifier)
Các bước trong giai đoạn huấn luyện:
7
Hình 1.2: Các bước trong giai đoạn huấn luyện
Trong đó :
Ngữ liệu huấn luyện: kho ngữ liệu thu thập từ nhiều nguồn khác nhau.
Tiền xử lý: chuyển đổi tài liệu trong kho ngữ liệu thành một hình thức phù hợp
để phân loại.
Vector hoá: mã hoá văn bản bởi một mô hình trọng số
Trích chọn đặc trưng: loại bỏ những từ (đặc trưng) không mang thông tin khỏi tài
liệu nhằm nâng cao hiệu suất phân loại và giảm độ phức tạp của thuật toán huấn luyện.
Thuật toán huấn luyện: Thủ tục huấn luyện bộ phân lớp để tìm ra họ các tham số
tối ưu.
Đánh giá: bước đánh giá hiệu suất (chất lượng) của bộ phân lớp
- Giai đoạn phân lớp
Sau khi đã hoàn thành giai đoạn huấn luyện, mô hình phân lớp sẽ được áp dụng
cho các văn bản mới cần phân loại.
Hình 1.3: Mô hình giai đoạn phân lớp
Các bước trong giai đoạn phân lớp:
8
Hình 1.4: Các bước trong giai đoạn phân lớp
1.4. Mục đích và phạm vi nghiên cứu
Mục đích:
+ Tìm hiểu thuật toán Navie Bayes và phạm vi ứng dụng của nó trong phân
loại văn bản.
+ Nắm rõ hơn về cơ chế học tập và huấn luyện máy học.
+ Xây dựng một chương trình có khả năng phân loại văn bản sau khi tìm

trường dữ liệu Access, SQL, việc liên kết dữ liệu có thể thực hiện bằng nhiều cách.
2.1.3. Bộ code mã nguồn mở xử lý văn bản
Để có thể có được kết quả huấn luyện và phân loại tốt các văn bản (phân loại
chính xác), chúng ta cần có một hệ từ vựng chuẩn. Việc tách các từ và gán nhãn từ loại
cho các cụm từ này trên thực tế là rất khó khăn và đòi hỏi sử dụng đến nhiều thuật toán
10
khác nhau do vậy việc xây dựng một modul như vậy là không khả thi. Thay vào đó
chúng ta có thể tích hợp các hệ thông nghiên cứu khác vào hệ thống giúp cho việc xây
dựng chương trình nhanh chóng và thuận tiện hơn.
Năm 2010, nhánh đề tài "Xử lí văn bản tiếng Việt" là một phần của đề tài
KC01.01/06-10 "Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lí tiếng nói và
văn bản tiếng Việt". Đây là đề tài liên kết giữa các nhóm nghiên cứu xử lí tiếng Việt
đến từ các trường đại học, viện nghiên cứu trong nước và quốc tế. Các sản phẩm được
trình diễn bao gồm:
- SP7.2: Từ điển tiếng Việt dùng cho xử lí ngôn ngữ tự nhiên
Thực hiện: Vũ Xuân Lương, Hồ Tú Bảo, Nguyễn Thị Minh Huyền
- SP7.3: Kho ngữ liệu câu tiếng Việt có chú giải
Thực hiện: Nguyễn Phương Thái, Vũ Xuân Lương, Nguyễn Thị Minh Huyền
- SP7.4: Hai kho ngữ liệu câu Anh-Việt phổ quát-chuyên ngành
Thực hiện: Hồ Bảo Quốc, Cao Hoàng Trụ
- SP8.2: Hệ phân đoạn từ tiếng Việt
Thực hiện: Nguyễn Thị Minh Huyền, Hồ Bảo Quốc
- SP8.3: Hệ phân loại từ tiếng Việt
Thực hiện: Phan Xuân Hiếu, Lê Minh Hoàng
- SP8.4: Hệ phân cụm từ tiếng Việt
Thực hiện: Nguyễn Lê Minh, Cao Hoàng Trụ
- SP8.5: Hệ phân tích câu tiếng Việt
Thực hiện: Lê Thanh Hương, Nguyễn Phương Thái
Trong chương trình của chúng ta cần tách được các danh từ để đưa vào CSDL
nên chúng ta sử dụng hệ tách từ tiếng Việt và hệ gán nhãn từ loại tiếng Việt nằn trong

Một trong những nhiệm vụ đầu tiền trong việc xử lý phân loại văn bản là chọn
được một mô hình biểu diễn văn bản thích hợp. Một văn bản ở dạng thô (dạng chuỗi)
cần được chuyển sang một mô hình khác để tạo thuận lợi cho việc biểu diễn và tính
toán. Tuỳ thuộc vào từng thuật toán phân loại khác nhau mà chúng ta có mô hình biểu
diễn riêng. Một trong những mô hình đơn giản và thường được sử dụng trong nhiệm
vụ này là mô hình không gian vector. Một văn bản trong nhiệm vụ này được biểu diễn
theo dạng , với là một vector n chiều để đo lường giá trị của phần tử văn bản.
2.2.3. Mô hình không gian vector
Mô hình không gian vector là một trong những mô hình được sử dụng rộng rãi
nhất cho việc tìm kiếm (truy hồi) thông tin. Nguyên nhân chính là bởi vì sự đơn giản
của nó.
Trong mô hình này, các văn bản được thể hiện trong một không gian có số chiều
lớn, trong đó mỗi chiều của không gian tương ứng với một từ trong văn bản. Phương
pháp này có thể biểu diễn một cách hình tượng như sau: mỗi văn bản D được biểu diễn
dưới dạng (vector đặc trưng cho văn bản D). Trong đó, =( x
1
, x
2
, … , x
n
), và n là số
12
lượng đặc trưng hay số chiều của vector văn bản, x
i
là trọng số của đặc trưng thứ i (với
1≤ i ≤n).
Như vậy, nếu trong kho ngữ liệu của quá trình huấn luyện nhiều văn bản, ta kí
hiệu D
j
, là văn bản thứ j trong tập ngữ liệu, và vector

trong văn bản d
j
), document frequency (df
i
số
văn bản có chứa từ w
i
), collection frequency ( cf
i
số lần suất hiện của từ w
i
trong cả tập
ngữ liệu). Trong đó, df
i
≤ cf
i
và ∑
j
tf
ij
=cf
i
.
Thông tin được nắm bắt bởi term frequency là sự nổi bật của thông tin (hay từ)
trong một văn bản. Term frequency càng cao (số lần xuất hiện càng nhiều trong văn
bản) thì đó là từ miêu tả tốt cho nội dung văn bản. Giá trị thứ hai, document frequency,
có thể giải thích như là một bộ chỉ định nội dung thông tin. Một từ được tập trung ngữ
nghĩa thường xảy ra nhiều lần trong một văn bản nếu nó cũng xuất hiện trong tất cả
các văn bản khác. Nhưng từ không được tập trung ngữ nghĩa trải đều đồng nhất trong
tất cả các văn bản.

các link RSS(Really Simple Syndication).
Có thể sử lý với các loại văn bản .txt hoặc .doc
- Về quản lý từ vựng:
Việc lấy từ vựng phải được lấy tự động do ngữ liệu từ vựng là rất lớn, từ cựng
lấy về phải là các danh từ và hạn chế thấp nhất các từ gây nhiễu hoặc không chính xác
14
Sử dụng tách từ tự động từ các văn bản được bóc tách về thông qua hệ mã nguồn
mở tách từ tiếng Việt và gán nhãn từ vựng tiếng Việt.
- Về quản lý các lĩnh vực:
Xây dựng giao diện quản lý được các thông tin trong từng lĩnh vực đặc biệt là
chọn thư mục chứa để có thể lấy văn bản về phục vụ cho việc huấn luyện sau này.
• Về mặt chức năng:
Chương trình phải xây dựng và hoàn thiện được hai chức năng quan trọng nhất là
huấn luyện và phân lọai văn bản. Việc phân loại văn bản với độ chính xác cao và đưa
ra thông báo cho người dùng.
3.2. Thiết kế
3.2.1. Kiến trúc chung
Chương trình được xây dựng theo mô hình 3 lớp.
- Về tổng quan chương trình được xây dựng có các trang chức năng sau:
+ Về mặt quản lý:
Trang quản lý văn bản nhằm quản lý các văn bản và thông tin liên quan.
Trang quản lý từ vựng nhằm quản lý các từ vựng phục vụ cho việc phân loại
Trang quản lý lĩnh vực nhằm quản lý các lĩnh vực được phân loại
Trang lấy tin tự động và tách từ tự động đưa vào CSDL.
Các trang quản lý mã hóa, quản lý huấn luyện, quản lý chi tiết huấn luyện, quản
lý link RSS… nhằm lưu và quản lý các thông tin trong mỗi lần huấn luyện.
+ Về chức năng:
Trang Huấn luyện nhằm huấn luyện và quản lý các văn bản huấn luyện
Trang phân loại nhằm phân loại văn bản.
3.2.2. Thuật toán sử dụng

1
,x
2
,…x
n
độc lập xác suất đôi một với nhau.
Theo định lý Bayes :
(3.2)
Theo tính chất độc lập điều kiện :
(3.3)
Khi đó, luật phân lớp cho các tài liệu mới X
new
={x
1
, x
2
, … , x
n
} là:
(3.4)
Trong đó :
- P(C
i
): được tính dựa trên tần suất xuất hiện tài liệu trong tập huấn luyện.
- P(x
k
|C): được tính từ những tập thuộc tính đã được tính trong quá trình
huấn luyện.
• Thuật toán
Các bước thực hiện thuật toán Naïve Bayes:

No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool
Norm
al
Weak Yes
D6 Rain Cool
Norm
al
Stron
g
No
D7 Overcast Cool
Norm
al
Weak Yes
D8 Sunny Mild High Weak No
D9 Sunny Cold
Norm
al
Weak Yes
D10 Rain Mild
Norm
al
Stron
g
Yes
D11 Sunny Mild
Norm

P(C
2
) = P(“no”) = 5/14
Tính xác suất P(x
k
|C
i
)
- Với thuộc tính Outlook: có các giá trị sunny, overcast, rain
P(sunny|yes) = 2/9
P(sunny|no) = 3/5
P(overcast|yes) = 4/9
P(overcast|no) = 0/5
P(rain|yes) = 3/9
P(rain|no) = 2/5
17
- Với thuộc tính Temp: có các giá trị Hot, Cold, Mild
P(hot|yes) = 2/9
P(hot|no) = 2/5
P(cold|yes) = 3/9
P(cold|no) = 1/5
P(mild|yes) = 4/9
P(mild|no) = 2/5
- Với thuộc tính Humidity: có các giá trị Normal,High
P(normal|yes) = 6/9
P(normal|no) = 1/5
P(high|yes) = 3/9
P(high|no) = 4/5
- Với thuộc tính Wind: có các giá trị Weak, Strong
P(weak|yes) = 6/9

- Từ tập huấn luyện, ta rút trích tập từ vựng (các đặc trưng)
- Tính xác suất P(C
i
) và P(x
k
|C
i
)
(3.5)
docs
i
: số tài liệu của tập huấn luyện thuộc lớp c
i
.
total#documents: số tài liệu có trong tập huấn luyện.
(3.6)
Hoặc
(3.7)
(làm mịn với luật Laplace)
- n: tổng số từ đôi một khác nhau của lớp c
i
.
- n
k
: tổng số từ x
k
trong tập từ vựng trong lớp C
i
.
- |Text

i
)
- Lớp C
1
= “Comp”: Tổng = 208
P(var|Comp) = (10+11+8)/208 = 29/208
P(bit|Comp) = (28+25+22)/208 = 75/208
P(chip |Comp) = (45+22+30)/208 = 97/208
P(log|Comp) = (2+4+1)/208 = 7/208
- Lớp C2 = “Math”: Tổng = 388
P(var|Math) = (42+33+28)/208 = 103/388
P(bit| Math) = (22+40+32)/208 = 97/388
P(chip| Math) = (7+8+9)/208 = 24/388
P(log| Math) = (56+48+60)/208 = 164/388
• Bước phân lớp: cho văn bản có vector đặc trưng sau
Doc
new
= (23,40,15,50)
Xác định lớp cho văn bản mới ?
Tính các xác xuất :
Xác suất Doc
new
thuộc Math:
P(Math)*[P(var|Math)*23*P(bit|Math)*40*P(chip|Math)*15*P(log|Math)*50]=598.62
Xác suất Doc
new
thuộc Comp:
P(Comp)*[P(var|Comp)*23*P(bit|Comp)*40*P(chip|Comp)*15*P(log|
Comp)*50]=272.22
• Kết quả:

linhvuc nvarchar 100 N Lĩnh vực
link ntext N Nơi chứa
Bảng 3.5: Bảng Lĩnh Vực
• Bảng Huấn Luyện
Lưu trữ các thông tin về các lần huấn luyện để có thể đánh giá và so sánh được
tính hiệu quả của thuật toán. Các thông tin gồm có:
Cột Kiểu DL Size NULL Diễn giải
id int N Lần huấn luyện
ngayhl datetime N Thời gian huấn luyện
tongvb int N Tổng số văn bản đưa vào hl
Bảng 3.6: Bảng Huấn Luyện
• Bảng Chi Tiết Huấn Luyện
Lưu trữ các thông tin chi tiết về lần huấn luyện, các lĩnh vực được huấn luyện
trong lần huấn luyện. Các thông tin lưu trữ bao gồm:
Cột Kiểu DL Size NULL Diễn giải
id int N Mã chi tiết luân luyện
idhl int N Lần huấn luyện
idlv int N Lĩnh vực
sovb int N Số văn bản
tilevb float N Tỉ lệ văn bản
tongtu int N Tổng số từ
Bảng 3.7: Bảng Chi Tiết Huấn Luyện
• Bảng Thống Kê
Thống kê tổng số từ của các lĩnh vực trong các lần huấn luyện. Thông tin bao
gồm:
Cột Kiểu DL Size NULL Diễn giải
id int N Mã thống kê
idhl int N Lần huấn luyện
idtu int N Mã từ
sotu int N Số từ

- Trang quản lý mã hóa
- Trang quản lý huấn luyện
- Trang quản lý chi tiết huấn luyện
- Trang quản lý RSS
- Trang bóc tách văn bản và lấy từ tự động
Các form chức năng:
23
- Trang phân loại văn bản
- Trang huấn luyện
3.3. Tích hợp hệ phân tích từ vựng và gán nhãn từ loại tiếng Việt
3.3.1. Hệ phân tích từ vựng tiếng Việt
Chương trình tách từ vnTokenizer, version 4.1.1.
• Tổng quan
Chương trình vnTokenizer được sử dụng để tách từ các văn bản tiếng Việt (mã
hóa bằng bảng mã Unicode UTF-8).
Chương trình chạy dưới dạng dòng lệnh:
- vnTokenizer.sh nếu chạy trên các hệ điều hành Linux/Unix/Mac OS
- vnTokenizer.bat nếu chạy trên các hệ điều hành MS Windows
Yêu cầu: Máy cần cài JRE (Java Runtime Environment) phiên bản 1.6. JRE có
thể tải về từ địa chỉ website Java của Sun Microsystems: />• Dữ liệu
Trong một lần chạy vnTokenizer có thể tách từ một tệp hoặc đồng thời nhiều tệp
nằm trong cùng một thư mục.
• Tách từ một tệp:
Dữ liệu cần cung cấp cho chương trình gồm 1 tệp văn bản tiếng Việt, dạng thô.
Kết quả: Một tệp văn bản kết quả tách từ được ghi dưới định dạng đơn giản hoặc
định dạng XML, tùy theo lựa chọn của người sử dụng.
• Tách từ nhiều tệp nằm trong một thư mục:
Dữ liệu cần cung cấp gồm một thư mục chứa các tệp văn bản thô cần tách từ (thư
mục input) và một thư mục trống (thư mục output) để chứa kết quả tách từ.
Mặc định, chương trình sẽ tự động quét toàn bộ thư mục input và lọc ra tất cả các

+) -e: chỉ định phần mở rộng của các tệp cần tách.
Ví dụ:
a) vnTokenizer.sh -i samples/input -o samples/output
Thực hiện tách từ tất cả các tệp samples/input/*.txt, ghi kết quả ra thư mục
samples/output.
b) vnTokenizer.sh -i samples/input -o samples/output -e .xyz
25