ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thuỳ Linh PHÂN LỚP TÀI LIỆU WEB
ĐỘC LẬP NGÔN NGỮ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin Cán bộ hướng dẫn: NCS. Phan Xuân Hiếu
Cán bộ đồng hướng dẫn: TS. Hà Quang Thuỵ

Xin chân thành cảm ơn!
Hà Nội, ngày 25 tháng 05 năm 2006
Sinh viên
Nguyễn Thị Thuỳ Linh i
TÓM TẮT NỘI DUNG
Phân lớp văn bản là một trong những bài toán cơ bản và quan trọng nhất của
lĩnh vực xử lý ngôn ngữ tự nhiên. Nó có ứng dụng rất nhiều trong các bài toán thực tế
ví dụ như: ứng dụng lọc nội dung văn bản (lọc thư rác, lọc trang web có nội dung phản
động, trang web có nội dung không lành mạnh,…), bài toán phân lớp văn bản sau tìm
kiếm,… Hiện nay có rất nhiều bộ phân lớp đạt được
độ chính xác cao (đều xấp xỉ
90%), tuy nhiên các bộ phân lớp này hầu hết chỉ áp dụng cho một ngôn ngữ cụ thể.
Thực tế cho thấy, đối với bài toán lọc nội dung trang Web thì một vấn đề đặt ra là phải
xử lý trên nhiều ngôn ngữ khác nhau. Một trong hướng nghiên cứu phân lớp văn bản
được quan tâm gần đây là phân lớp đa ngôn ngữ [7]. Khoá luận này nghiên cứu và đề
xuất một phương pháp phân lớp nộ
i dung Web độc lập ngôn ngữ. Phương pháp này
cho phép tích hợp thêm các ngôn ngữ mới vào bộ phân lớp và giải quyết vấn đề bùng
nổ đặc trưng thông qua hướng tiếp cận entropy cực đại và sử dụng chiến lược tối ưu
hoá hàm nhiều biến rất hiệu quả. Các kết quả thực nghiệm cho thấy hướng tiếp cận của
khoá luận rất khả quan, cụ thể, khi huấn luyện riêng bi
ệt trên từng ngôn ngữ đều nhận
được kết quả rất cao (Anh trên 98%, Việt trên 91%), còn khi có sự kết hợp của hai
ngôn ngữ kết quả đạt được cũng rất khả quan (Anh-Việt xấp xỉ 95%). Đặc biệt khi cho


1.2. Phân lớp văn bản độc lập ngôn ngữ .....................................................................4

1.2.1. Đặt vấn đề......................................................................................................4

1.2.2. Phân lớp văn bản độc lập ngôn ngữ ..............................................................5

1.2.3. Ý nghĩa và ứng dụng .....................................................................................5

CHƯƠNG 2. CÁC MÔ HÌNH VÀ THUẬT TOÁN PHÂN LỚP VĂN BẢN...............7

2.1. Giới thiệu.............................................................................................................7

2.2. Mô hình Maximum Entropy................................................................................7

2.2.1. Giới thiệu.......................................................................................................7

2.2.2. Xây dựng mô hình .........................................................................................9

2.3. Tổng kết chương.................................................................................................16

CHƯƠNG 3. PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGÔN NGỮ VỚI MÔ HÌNH
ENTROPY CỰC ĐẠI ...................................................................................................17

3.1 Giới thiệu............................................................................................................17

3.2. Bài toán phân lớp văn bản độc lập ngôn ngữ ....................................................17

3.2.1. Vấn đề nhập nhằng ngôn ngữ......................................................................17


3.6. Tổng kết chương................................................................................................27

CHƯƠNG 4. KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ .........................................28

4.1. Môi trường thử nghiệm ......................................................................................28

4.1.1. Môi trường phần cứng.................................................................................28

4.1.2. Công cụ phần mềm......................................................................................28

4.2. Dữ liệu kiểm thử.................................................................................................29

4.2.1. Tiền xử lý dữ liệu ........................................................................................29

4.2.2. Cây phân lớp................................................................................................30

4.3. Kết quả thử nghiệm ............................................................................................31

4.3.1. Quá trình huấn luyện ...................................................................................31

4.3.2. Lần lặp cho độ chính xác cao nhất ..............................................................34

4.3.3. Kết quả kiểm tra trên dữ liệu mới ...............................................................35

4.4. Tổng kết chương.................................................................................................36

KẾT LUẬN ...................................................................................................................37

PHỤ LỤC. DANH SÁCH STOP-WORD ....................................................................38



Bảng 6. Cây phân lớp thông tin.....................................................................................31

Bảng 7. Tập dữ liệu huấn luyện của cả 3 mô hình ........................................................31

Bảng 8. Độ chính xác 10 lần huấn luyện của tiếng Anh ...............................................32

Bảng 9. Độ chính xác 10 lần huấn luyện của tiếng Việt ...............................................32

Bảng 10. Độ chính xác 10 lần huấn luyện kết hợp Anh-Việt........................................32
vi
DANH MỤC HÌNH ẢNH
Hình 1. Tập ràng buộc C ...............................................................................................12

Hình 2. Mô tả các bước xây dựng bộ phân lớp .............................................................19

Hình 3. Trang tin tức tiếng Việt VnExpress.net............................................................29

Hình 4. Trang tin tức tiếng Anh BBC News .................................................................30

Hình 5. Độ chính xác của 3 bộ phân lớp trong 10 lần huấn luyện ................................33

Hình 6. Sự phụ thuộc độ chính xác theo bước lặp của cả 3 mô hình ............................34

Hình 7. Kết quả kiểm tra bộ dữ liệu độc lập Anh-Việt .................................................35
9 Chương 1: Giới thiệu tóm tắt bài toán phân lớp văn bản, đặt vấn đề và
phát biểu bài toán phân lớp văn bản độc lập ngôn ngữ.
9 Chương 2: Trình bày cụ thể hơn về bài toán phân lớp, đề cập đến các vấn
đề cơ bản của nguyên lý entropy cực đại theo hướng áp dụ
ng vào bài toán
phân lớp văn bản.
9 Chương 3: Phát biểu bài toán phân lớp văn bản độc lập ngôn ngữ, phân
tích các vấn đề cần giải quyết đối với bài toán và các bước xây dựng bộ

2
phân lớp trên cơ sở áp dụng mô hình entropy cực đại. Đưa ra một đề xuất
mới có thể áp dụng và các ứng dụng vừa và nhỏ.
9 Chương 4: Trình bày những kết quả đánh giá thử nghiệm của khoá luận
áp dụng cho bài toán cây phân lớp tin tức với hai ngôn ngữ Anh và Việt.
Cuối cùng là kết luận lại những điểm chính, những đóng góp chính của luận
văn, đồng th
ời chỉ ra những điểm cần khắc phục và vạch ra hướng cải tiến nhằm
hướng tới xây dựng một hệ ứng dụng thực trên môi trường Internet.

3
Chương 1
KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN
ĐỘC LẬP NGÔN NGỮ
Bài toán phân lớp độc lập ngôn ngữ là một bài toán con, phát triển trên nền
của bài toán phân lớp văn bản. Trước khi trình bày về bài toán chính, chương này trình
bày một cách sơ lược lịch sử cũng như ứng dụng của bài toán phân lớp văn bản.
1.1. Bài toán phân lớp văn bản
1.1.1. Tổng quan
Phân lớp văn bản được coi là quá trình phân loại một văn bản bất kì vào một
hay nhiều lớp cho trước. Theo phương pháp học máy (machine learning), quá trình này

kiếm, ứng dụng này rất hữu ích vì nó định vị nội dung thông tin cần tìm kiếm nhanh và
dễ dàng hơn.
Tóm lại, với tất cả ý ngh
ĩa thực tế trên, một lần nữa có thể khẳng định rằng
trong thời đại Internet được coi là một phần không thể thiếu trong cuộc sống, phân lớp
văn bản luôn là vấn đề đáng được quan tâm để có thể phát triển và xây dựng được
những công cụ ngày càng hữu dụng hơn.
1.2. Phân lớp văn bản độc lập ngôn ngữ
1.2.1. Đặt vấn đề
Nếu thường xuyên theo dõi các trang tin của các hãng tin lớn, chúng ta dễ
dàng nhận thấy chúng được thể hiện trên nhiều ngôn ngữ. Trên BBC hiện nay có tới
33 ngôn ngữ, CNN có 5 ngôn ngữ,… Hoặc khi chúng ta nhập câu truy vấn trong một
hệ thống tìm kiếm trực tuyến (Google, Yahoo) để tìm kiếm thông tin mà ta quan tâm,
kết quả trả về là một danh sách các địa chỉ trang web chứa từ khoá cần tìm và chúng
hiển thị dưới nhiều ngôn ngữ khác nhau. Như vậy có th
ể thấy rằng khá nhiều ngôn ngữ
đã được đưa lên Internet. Hiện nay theo thống kê [20] đã có tới 141 ngôn ngữ được mã
hoá và được sử dụng trên Internet, và theo xu thế này thì sẽ còn có nhiều hơn nữa các
ngôn ngữ được mã hoá và đưa vào sử dụng.
Trong giai đoạn nền kinh tế hội nhập này, không chỉ các hãng tin lớn mà cả
các tập đoàn xuyên quốc gia cũng xây dựng trang web của mình trên nhiều ngôn ngữ
khác nhau. Bên cạnh đó còn có các quốc gia muốn gi
ới thiệu về nền văn hoá, lịch sử
nước mình bằng việc xây dựng các trang web trên Internet nhằm giao lưu văn hoá và
thu hút khách du lịch.
Hơn thế nữa, hiện nay thư rác, các trang web thương mại, trang web phản
động, trang web có nội dung không lành mạnh,… ngày càng xuất hiện dưới nhiều hình
thức phong phú hơn. Chúng không chỉ được biểu diến một ngôn ngữ mà còn bởi đồng
thời nhiều ngôn ngữ nhằm đi qua bộ lọc thư rác, hay các b
ộ lọc nội dung của máy tìm

đưa ra cách giải quyết trong Chương 3.
Trong khoá luận này, chúng tôi sử dụng kĩ thuật học máy entropy cực đại để
xây dựng mô hình phân lớp . Entropy cực đại là một phương pháp cho phép khả năng
tích hợ
p mạnh nhiều đặc trưng, có thể là hàng nghìn hàng triệu đặc trưng. Qua thử
nghiệm đã cho thấy kết quả rất khả quan. Độ chính xác trong quá trình huấn luyện của
bộ phân lớp của hai ngôn ngữ Anh – Việt xấp xỉ 95%, trong khi bộ phân lớp của tiếng
Anh là 98% và của tiếng Việt là trên 91%.
1.2.3. Ý nghĩa và ứng dụng
Phân lớp tài liệu Web độc lập ngôn ngữ là bài toán có ý nghĩa và ứng dụng
thực tiễn cao. Nó cho phép áp d
ụng vào các bài toán như:

6
- Bài toán lọc nội dung: lọc thư rác, lọc web phản động, web không lành
mạnh,… Hiện nay, bất kì ai sử dụng email cũng đối mặt với nạn thư rác
được viết bằng đủ mọi thứ tiếng Anh, Pháp, Nga, Nhật, Hàn,… Chúng vào
hòm thư của chúng ta và gây nhiều phiền toái nên việc ngăn chặn chúng là
rất cần thiết. Bên cạnh đó, trên Internet hiện nay xuất hiện ngày càng nhiều
các trang Web không lành mạnh có ảnh hưởng xấu t
ới các em thiếu niên,
học sinh. Web không lành mạnh ở đây không chỉ có sex mà còn có thể có
nội dung về “chế tạo hoặc sử dụng vũ khí mang tính bạo lực” hay “web
hướng dẫn về tự tử tập thể” (như ở Nhật),… Bảo vệ các em thiếu niên
trước những thông tin không lành mạnh như vậy là điều rất cần thiết.
- Sử dụng làm bộ phân lớp cho các hãng tin, tổ chức xuyên qu
ốc gia, thậm
chí là các trang web giới thiệu về mình của các quốc gia trên toàn thế giới.
- Một ứng dụng cũng rất hữu ích là làm công cụ phân lớp cho các thư viện
sách lớn, thay thế cho công việc của một thủ thư. Ở đây, mô hình được xây

Vấn đề lớn nhất vớ
i bài toán phân lớp văn bản là ở chỗ tích hợp được các quan
sát từ dữ liệu mẫu vào mô hình càng nhiều càng tốt, và phải có thuật toán học tối ưu.
So với các mô hình khác, mô hình phân loại dựa trên nguyên lý entropy cực đại
có thế mạnh là khả năng học và nhớ đến hàng trăm nghìn đặc trưng, thậm chí hàng
triệu đặc trưng từ dữ liệu mẫu nhờ vào một chiến lược tối ưu hoá hàm nhiều bi
ến rất
hiệu quả. Khả năng này rất phù hợp với bài toán phân lớp văn bản và đặc biệt là bài
toán phân lớp văn bản độc lập ngôn ngữ khi mà lượng đặc trưng là rất lớn.
2.2. Mô hình Maximum Entropy
Mô hình entropy cực đại [4][11][12][14][15][16][17] là mô hình dựa trên xác
suất có điều kiện cho phép tích hợp các thuộc tính đa dạng từ dữ liệu mẫu nhằm hỗ trợ
quá trình phân lớp.
2.2.1. Giới thiệu
Trước khi trình bày về mô hình entropy cực đại, chúng ta cùng xem xét một ví
dụ đơn giản sau. Xét một quá trình ngẫu nhiên: gieo con súc sắc, đồng chất, cân đối.
Quan sát 1.000 lần thử, thống kê xác suất xuất hiện của từng mặt ta có nhận xét:

8

6
1
() 1
i
pi
=
=
∑
(1)
p(i) là xác suất xuất hiện của mặt có i chấm.

, các mặt 3, 5, 6 có xác suất xuất hiện là 0.
Tuy nhiên, lại một lần nữa ta thấy rằng, phân phối giống với phân phối thực nhất là:
( ) ( )
141/4pp= =

( ) ( ) ( ) ( )
23561/8pppp= ===

Dữ liệu trong thế giới thực là vô hạn, khó đoán nhận, ta mong muốn xây dựng
được một mô hình mà ước lượng được gần đúng với phân phối thực thông qua một tập
dữ liệu mẫu. Qua ví dụ vừa nêu trên chúng ta có nhận xét rằng: trong tập dữ liệu mẫu
mà ta có được, mô hình có phân phối đều nhất thì sẽ gần giống với phân phối thực
nhất. Vì vậy, vấn đề đặt ra là: làm th
ế nào để tìm được một mô hình như vậy? Phương
pháp entropy cực đại cho phép tìm ra được mô hình này.
Tư tưởng chủ đạo của nguyên lý entropy cực đại rất đơn giản: ta phải xác định
môt phân phối mô hình sao cho phân phối đó tuân theo mọi giả thiết đã quan sát từ

9
thực nghiệm, ngoài ra không cho thêm bất kì giả thiết nào khác. Điều này có nghĩa là
phân phối mô hình phải thoả mãn các ràng buộc quan sát từ thực nghiệm, và phải gần
nhất với phân phối đều.
Entropy là độ đo về tính đồng đều hay tính ko chắc chắn của một phân phối
xác suất. Một phân phối xác suất có entropy càng cao thì phân phối của nó càng đều.
Độ đo Entropy điều kiện của một phân phối xác suấ
t trên một chuối các trạng thái với
điều kiện biết từ một chuỗi dữ liệu quan sát được tính như sau:
() ( ) ( ) ( )
,
|log |

Txy xy= K
trong đó
{ }
1
,,
N
x xK
là tập
các thông tin ngữ cảnh đã được gán nhãn tương ứng là tập các lớp
{ }
1
,,
N
yyK
.
Với một cặp
()
,
ii
x y
, phân phối xác suất thực nghiệm của nó được tính bởi:
()
1
,
ii
px y
N
=
%
× số lần xuất hiện của

y Spam document_has san_pham_moi true
fxy
==
⎧
=
⎨
⎩

Gọi hàm f được biểu diễn như trên là hàm đặc trưng hay đặc trưng. Giá trị kì
vọng của f đối với phân phối thực nghiệm
(, )p xy
%
là giá trị thống kê được một cách
chính xác (trong ví dụ trên thì đó là: 0,8): số lần xuất hiện của f trong tập dữ liệu huấn
luyện. Nó được biểu diễn như sau:

( ) ( )
,
,,
pi i
xy
Ef pxy f xy=
∑
%
%
(4)
Bất kì thống kê nào sinh ra từ tập dữ liệu mẫu cũng có thể được biểu diễn một
hàm kì vọng của đặc trưng f theo quy tắc như trên.
Trong [16] cung cấp một cách có hệ thống cách xây dựng hàm đặc trưng.
Thông tin “thư có chứa cụm từ “sản phẩm mới”” được xây dựng thành một mệnh đề

⎧
=
⎨
⎩
nÕu vµ
ng−îc l¹i11
Hàm đặc trưng là hàm kiểm tra sự xuất hiện đồng thời của mệnh đề thông tin
ngữ cảnh và lớp được dự đoán.
Thống kê vừa nêu trong ví dụ ở phần trước là một thông tin quan trọng: xác
suất xuất hiện lên tới 80%. Trong quá trình quan sát tập dữ liệu, ta sẽ nhận được rất
nhiều thống kê hữu ích. Vì thế, nếu coi đó là một điều kiện mà mô hình ph
ải tuân theo
thì sẽ giúp mô hình dự đoán được lớp của văn bản một cách chính xác hơn. Biểu diễn
theo toán học, ta có phương trình như sau:

p ipi
Ef Ef=
%
(5)
Phương trình này được gọi là
ràng buộc
, gọi đầy đủ là phương trình ràng
buộc, trong đó:

( ) ( ) ( )
,
|,

%
), và ý nghĩa của việc ràng buộc mô hình của chúng ta tuân theo
những sự kiện đó (chính là
p ipi
Ef Ef=
%
).
2.2.2.3. Nguyên lý entropy cực đại
Giả sử quá trình thống kê từ tập dữ liệu huấn luyện sinh ra n đặc trưng
i
f
, mỗi
đặc trưng này sẽ xác định một ràng buộc. Gọi
P
là không gian của tất cả các phân phối
xác suất,
C
là tập con của
P
sẽ được mô tả như sau:
{ }
{ }
| 1,2,..,
pi pi
CpPEfEf i n≡∈ = ∈víi
%

Hình 1 mô tả 4 trường hợp tập
C
khi có các ràng buộc.

13
CC∩ =∅
), không có
Pp ∈
nào thoả
mãn cả hai ràng buộc đó.
(a)
(b)
(c)
(d)
P
P
P
C
1
C
1
C
2
C
1
C
3

Hình 1. Tập ràng buộc C
Nguyên lý entropy cực đại được phát biểu rằng: “Từ tập các phân bố xác suất
có thể được là
C
, sẽ tìm ra được một mô hình
*