Phân lớp tài liệu web độc lập ngôn ngữ

iii
3.4.1. Các độ đo 24

3.4.2. Áp dụng phương pháp ước lượng chéo trên k tập con 25

3.5. Xây dựng bộ phân lớp trên cây phân lớp thông minh 25

3.5.1. Bản chất bài toán 26

3.5.2. Phân lớp cho văn bản mới 26

3.5.3. Thảo luận 27

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

TÀI LIỆU THAM KHẢO 41



iv
BẢNG KÍ HIỆU VIẾT TẮT
Kí hiệu Diễn giải
GIS Generalized Interative Scaling
HTML Hyper Text Markup Language
IDF Inverse Document Frequency
IIS Improved Iterative Scaling
kNN K Nearest Neighbours
L-BFGS Limited-memory Broyden-Fletcher-Goldfarb-Shannon
MaxEnt Maximum Entropy
NCR Numeric Character References
TF Term Frequency
UTF Unicode Transformation Formats


v
DANH MỤC BẢNG SỐ LIỆU
Bảng 1. Cây phân lớp thông minh tổng quát 26

Bảng 2. Bảng ví dụ cho cây phân lớp thông minh 26

Bảng 3. Cấu hình hệ thống chạy thử nghiệm 28

Bảng 4. Danh sách phần mềm sử dụng để thử nghiệm 28

Bảng 5. Danh sách công cụ sử dụng để thử nghiệm 29

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




1
MỞ ĐẦU
Hiện nay, nhờ khả năng cho phép mã hoá được phần lớn các ngôn ngữ thông
dụng trên toàn thế giới của bảng mã Unicode, khoảng cách giữa các quốc gia, dân tộc
do hạn chế về ngôn ngữ gây ra đang dần được xoá đi. Theo thống kê [20] hiện nay đã
có 141 ngôn ngữ được sử dụng trên Internet và xu hướng tất yếu là sẽ ngày càng xuất
hiện thêm nhiều ngôn ngữ trên Internet. Bộ phân lớp văn bản đã có hiện nay mới chỉ
dừng ở mức phân lớp cho các văn bản cùng trên một ngôn ngữ. Nếu với 141 ngôn ngữ
chúng ta xây dựng 141 bộ phân lớp thì quả thật tốn kém. Hơn thế nữa các trang web
thương mại, web có nội dung không lành mạnh hiện nay thể hiện và ẩn náu dưới nhiều
hình thức đa dạng (nhiều ngôn ngữ cùng xuất hiện trong một trang web) với mục đích
đi qua bộ lọc trong máy tìm kiếm, chúng gây rất nhiều phiền toái cho ngườ
i dùng. Vì
vậy, bài toán phân lớp văn bản độc lập ngôn ngữ được đặt ra nhằm mục đích xây dựng
một bộ phân lớp duy nhất cho nhiều ngôn ngữ.
Ý thức được vấn đề đó, khóa luận này tập trung xây dựng một bộ phân lớp tài
liệu web độc lập ngôn ngữ dựa trên việc áp dụng nguyên lý entropy cực đại. Đây là
phương pháp có khả năng tích hợp mạnh hàng nghìn hàng triệu đặc trư
ng quan trọng.
Qua kết quả thực nghiệm, với tập dữ liệu lên tới 12.000 trang Web bao gồm hai ngôn
ngữ Anh và Việt, kết quả cho thấy rất khả quan.
Mục tiêu mà khoá luận hướng tới:
9 Xây dựng bộ phân lớp duy nhất cho nhiều ngôn ngữ dựa trên mô hình
entropy cực đại.
9 Không cần sử dụng một bộ phân nhận dạng ngôn ngữ nào khác.
9 Thử nghiệm và đánh giá, và vạch ra h
ướng phát triển tiếp theo.
Cấu trúc của luận văn được tổ chức như sau:
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
gồm hai bước. Ở bước thứ nhất, một mô hình phân lớp (classfication model) được xây
dựng dựa trên tri thức kinh nghiệm. Ở đây, tri thức kinh nghiệm chính là một tập dữ
liệu huấn luyện (training dataset) được cung cấp bởi con người bao gồm một tập văn
b
ản và phân lớp tương ứng của chúng. Bước này còn gọi là bước xây dựng huấn luyện
(training process) hay ước lượng mô hình phân lớp. Ở bước thứ hai, mô hình phân lớp
xây dựng ở bước đầu sẽ được sử dụng để phân lớp cho những văn bản (chưa được
phân loại) trong tương lai. Bước đầu tiên được xem như là việc học có giám sát mà
chúng ta có thể sử dụng rất nhiều các kĩ thuậ
t học máy đã có như: Naïve Bayes, k láng
giếng gần nhất (kNN), cây quyết định (Decision Tree),… Mục tiêu của bài toán phân
lớp là nhằm xây dựng mô hình có khả năng gán nhãn cho một văn bản bất kì với độ
chính xác cao nhất có thể.
Nhu cầu có một bộ phân lớp hiệu quả đã xuất hiện ngay từ thủa ban đầu của
thời kì bùng nổ thông tin trên Internet. Vì thế bài toán phân lớp văn bản không phải là
một khái niệm mới mẻ. Tuy nhiên, hi
ện nay càng ngày hệ thống máy tính có khả năng
xử lý càng mạnh, lượng thông tin trên Internet biến đổi không ngừng cả về chất lượng
và số lượng. Nên bài toán phân lớp văn bản vẫn luôn là một vấn đề thời sự [7].
Đồng hành với lịch sử đó cho đến nay đã có rất nhiều các công cụ, bộ phân lớp
ra đời, có thể là bộ phân lớp với từng ứng dụng cụ thể, hay b
ộ phân lớp cho một bài
toán nhưng áp dụng những kĩ thuật học máy khác nhau.
Ứng dụng lớn nhất của bài toán phân lớp văn bản là áp dụng vào bài toán phân
loại hay lọc nội dung. Trong bài toán lọc nội dung: một văn bản được phân loại vào

4
nhóm: có ích hoặc không có ích. Sau đó lấy tất cả những văn bản thuộc nhóm có ích,
nhóm còn lại bị loại bỏ. Các ứng dụng cụ thể như: lọc thư rác, lọc trang web phản
động,… Một ứng dụng khác của bài toán phân lớp là xây dựng bộ phân lớp sau tìm
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
kiếm. Vì thế, việc xây dựng bộ phân lớp văn bản tự động cho nhiều ngôn ngữ là rất
cần thiết.

5
Chúng ta có thể xây dựng một bộ phân lớp như vậy bằng cách sử dụng một bộ
nhận dạng ngôn ngữ cho văn bản rồi mới tiến hành phân lớp. Đây là một phương pháp
hay, tuy nhiên khó khăn gặp khi phân lớp các tài liệu có nhiều ngôn ngữ xuất hiện
đồng thời. Hướng đến việc xây dựng công cụ áp dụng cho các ứng dụng vừa và nhỏ,
trong khoá luận này, chúng tôi đề xuất tiế
p cận cho bài toán phân lớp văn bản trên
nhiều ngôn ngữ theo hướng không phụ thuộc ngôn ngữ (độc lập) sử dụng mô hình
entropy cực đại.
1.2.2. Phân lớp văn bản độc lập ngôn ngữ
Phân lớp văn bản độc lập ngôn ngữ là một bài toán phân lớp văn bản, cho
phép sắp xếp một văn bản vào một lớp bất kì mà không cần quan tâm đến ngôn ngữ
trên văn bản đó. Đi
ều đó cũng có nghĩa là các văn bản trên những ngôn ngữ khác nhau
được coi là bình đẳng. Ý nghĩa của chữ “độc lập” là như vậy.
Trong [7], Fuchen đề xuất ý tưởng sử dụng mô hình ngôn ngữ N-gram giải
quyết các bài toán xử lý ngôn ngữ tự nhiên độc lập ngôn ngữ. Mô hình N-gram là một
mô hình thống kê thuần tuý, nếu xét trên một tập dữ liệu lớn thì nó sẽ gặp phải vấn đề
bùng nổ đặc trưng, là mộ
t trong thách thức với bài toán phân xử lý ngôn ngữ tự nhiên
độc lập ngôn ngữ nói chung và bài toán phân lớp văn bản độc lập ngôn ngữ nói riêng.
Bản chất các ngôn ngữ trong tự nhiên tồn tại sự nhập nhằng: Có nhiều từ
mượn, từ dùng chung giữa các ngôn ngữ với nhau. Sự nhập nhằng này rõ ràng sẽ ảnh
hưởng đến độ chính xác bộ phân lớp của chúng ta một mức độ nhất định. Bên cạnh đó,
m
ột vấn đề cốt lõi cần phải giải quyết khi muốn xây dựng bộ phân lớp cho văn bản độc
lập ngôn ngữ là sự bùng nổ đặc trưng. Cả hai vấn đề này sẽ được phân tích và được
đư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
dựng bằng cách đọc các tóm tắt trên mỗi quyển sách và sau đó tiến hành
phân lớp. Xếp mỗi quyển sách vào một trong cách lĩnh vực: Toán học, Vật
lý, Hoá họ
c, Văn học,… một cách chính xác; khi đó người thủ thư sẽ dễ
dàng sắp xếp các quyển sách vào các khu vực với lĩnh vực tương ứng mà
không phải đọc và phân tích tóm tắt của quyển sách.
- Hiện nay, chúng tôi đang đề xuất ứng dụng nghiên cứu của khoá luận vào
dự án “Nghiên cứu, phát triển hệ thống lọc nội dung hỗ trợ quản lý và đảm
bảo an toàn – an ninh thông tin trên mạng Internet”.
Tuy nhiên, cần phải khẳng định lại rằng, ứng dụng lớn nhất của bài toán phân
lớp văn bản độc lập ngôn ngữ là ứng dụng lọc thư rác, web phản động,… Ngoài ra với
tuỳ những đặc điểm của các ứng dụng khác mà ta xây dựng bộ phân lớp cho phù hợp.

Xem chi tiết: Phân lớp tài liệu web độc lập ngôn ngữ