..

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
----------------------------------------------

LUẬN VĂN THẠC SỸ KHOA HỌC

PHÂN LOẠI VĂN BẢN BẰNG PHƯƠNG PHÁP
SUPPORT VECTOR MACHINE

NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ:

LƯƠNG THỊ MINH HỒNG

Người hướng dẫn khoa học: TS. NGUYỄN LINH GIANG

HÀ NỘI 2006


^ 2 ]

MỤC LỤC
Danh mục các ký hiệu, các từ viết tắt ............................................................. 5
Danh mục các bảng.......................................................................................... 6
Danh mục các hình vẽ, đồ thị .......................................................................... 7
Mở đầu .............................................................................................................. 8
PHẦN I - CƠ SỞ LÝ THUYẾT ..................................................................... 12
CHƯƠNG 1. TÔNG QUAN VỀ KHAI PHÁ VĂN BẢN ..................... 13

1.1.

Một số khái niệm ............................................................................. 13

1.2.

Khai phá dữ liệu văn bản – Text Mining ..................................... 15

1.3.

Phân loại văn bản ............................................................................ 19

1.4.

Quy trình phân loại văn bản .......................................................... 20

1.4.1. Lưu trữ tài liệu ............................................................................... 20
1.4.2. Định dạng văn bản ......................................................................... 21
1.4.3. Cấu trúc hoá tài liệu ....................................................................... 22
1.4.4. Tách dữ liệu ................................................................................... 22
1.4.5. Giảm chiều ..................................................................................... 23
1.4.6. Mơ hình hố khơng gian vector ..................................................... 25
1.4.7. Giải thuật học máy ......................................................................... 26
1.4.8. Thiết lập cấu hình học máy............................................................ 26
1.4.9. Học tăng cường .............................................................................. 26
1.4.10. Hành vi giả thuyết ...................................................................... 27
CHƯƠNG 2. SUPPORT VECTOR MACHINE ................................... 28
2.1.

Động cơ ............................................................................................. 28


2.1.1. Học máy ......................................................................................... 28

Luận văn Thạc sỹ

Support Vector Machine


^ 3 ]

2.1.2. Lý thuyết học thống kê .................................................................. 30
2.2.

Nguyên lý tối thiểu hoá rủi ro cấu trúc ......................................... 33

2.3.

Máy học vector hỗ trợ - SVM......................................................... 35

2.3.1. SVM với các vấn đề tuyến tính...................................................... 37
2.3.2. Trường hợp phân tách khơng tuyến tính........................................ 39
2.4.

Một số phương pháp Kernel........................................................... 41

2.4.1. Polynomial - Phép toán đa thức ..................................................... 43
2.4.2. Gaussian RBF (Radial Basis Function) ......................................... 44
2.4.3. RBF mở rộng (Exponential Radial Basis Function)...................... 44
2.4.4. Perceptron đa tầng (multi-Label Perceptron –MLP) ..................... 44
2.5.


Một số vấn đề trong SVM............................................................... 45

2.5.1. Các hàm thiệt hại cho SVM ........................................................... 45
2.5.2. Các vấn đề đa lớp........................................................................... 45
2.5.3. Các vấn đề phân loại đa lớp – đa nhãn .......................................... 46
2.5.4. Tối ưu hoá các siêu phẳng phân tách ............................................. 46
CHƯƠNG 3: PHÂN LOẠI VĂN BẢN VỚI SVM ................................. 56
3.1.

Thực hiện phân loại văn bản với SVM.......................................... 56

3.2.

Ưu điểm khi sử dụng SVM phân loại văn bản ............................. 58

PHẦN II - THỬ NGHIỆM PHÂN LOẠI VĂN BẢN TRONG ORACLE
BẰNG PHƯƠNG PHÁP SVM ...................................................................... 59
CHƯƠNG 4. PHÂN LOẠI VĂN BẢN VỚI ORACLE TEXT ............ 60
4.1.

Khai phá văn bản với Oracle ......................................................... 60

4.2.

Phân loại văn bản trong Oracle Text ............................................ 62

4.2.1. Các ứng dụng phân loại trong Oracle Text.................................... 63

Luận văn Thạc sỹ


Support Vector Machine


^ 4 ]

4.2.2. Phân loại với SVM......................................................................... 65
4.2.3. Phương pháp đánh giá.................................................................... 80
CHƯƠNG 5. TIẾN HÀNH THỬ NGHIỆM .......................................... 82
5.1.

Chuẩn bị dữ liệu .............................................................................. 82

5.2.

Kiểm thử với Oracle 10g................................................................. 83

5.2.1. Thử nghiệm lần 1 ........................................................................... 83
5.2.2. Thử nghiệm lần 2 ........................................................................... 87
5.2.3. Thử nghiệm lần 3 .......................................................................... 88
5.2.4. Kết quả 3 lần thử nghiệm............................................................... 89
KẾT LUẬN ..................................................................................................... 92
TÀI LIỆU THAM KHẢO .............................................................................. 95
Phụ lục 1 ......................................................................................................... 97
TÓM TẮT LUẬN VĂN .................................................................................. 99

Luận văn Thạc sỹ

Support Vector Machine



^ 5 ]

Danh mục các ký hiệu, các từ viết tắt
Từ

Tiếng Anh

Tiếng Việt

CSDL

Database

Cơ sở dữ liệu

DF

Document Frequency

Tần xuất tài liệu

ERM

Empirical Risk Minimization

Tối thiểu hoá rủi ro theo kinh
nghiệm

IG


Information Gain

KDD

Knowledge Discovery in Database Khai phá tri thức trong CSDL

KNN

K Neighbourhood Nearest

K láng giêng gần nhất

ODM

Oracle Data Mining

Khai phá dữ liệu Oracle

SVM

Support Vector Machine

Máy học vector hỗ trợ

SRM

Structural Risk Minimization

Tối thiểu hoá rủi ro cấu trúc


VC

Vapnik-Chervonenkis

Chiều VC

Luận văn Thạc sỹ

Thu nhận thông tin

Support Vector Machine


^ 6 ]

Danh mục các bảng
Bảng 1.1. Bảng ngẫu nhiên cho phân loại cj và thuật ngữ fk. .................... 24
Bảng 4.1. Bảng các thuộc tính của SVM_CLASSIFIER ........................... 79
Bảng 5.1. Bảng dữ liệu thử nghiệm đã phân loại .................................... 82
Bảng 5.2. Bảng kết quả thử nghiệm lần 1 .............................................. 89
Bảng 5.3. Bảng kết quả thử nghiệm lần 2 .............................................. 90
Bảng 5.4. Bảng kết quả thử nghiệm lần 3 .............................................. 90
Bảng 5.5. Bảng tổng hợp kết quả thử nghiệm qua 3 lần ........................... 90

Luận văn Thạc sỹ

Support Vector Machine



^ 7 ]

Danh mục các hình vẽ, đồ thị
Hình 1.1. Các bước trong tiến trình KDD

14

Hình 1.2. Hoạt động của một bộ phân loại trên một tập tài liệu

19

Hình 2.1. Mơ hình hố các lỗi

30

Hình 2.2. Mơ tả VC Dimension

32

Hình 2.3. Mơ tả của phương trình 2.7.

34

Hình 2.4. Siêu phẳng phân tách tối ưu là một siêu phẳng phân tách dữ liệu
với margin lớn nhất

37

Hình 2.5. Sử dụng một hàm ánh xạ Φ vào khơng gian đặc trưng F có thể
được tìm thấy bằng cách sử dụng một siêu phẳng tuyến tính (bên phải).


42

Hình 2.6. Siêu phẳng phân tách tối ưu là một phân tách với lề cực đại

47

Hình 2.7. Không gian đặc trưng SV ánh xạ không gian nguồn vào một khơng
gian đặc trưng nhiều chiều và sau đó xây dựng một siêu phẳng tối ưu trong
không gian đặc trưng.

54

Hình 4.1 Cấu trúc cuả một ứng dụng phân loại văn bản

63

Hình 4.2. Mơ hình phân loại tổng quan trong Oracle

72

Hình 4.3. Quy trình đánh chỉ số văn bản

75

Luận văn Thạc sỹ

Support Vector Machine



^ 8 ]

Mở đầu
Phân loại văn bản là tiến trình xếp các tài liệu văn bản vào trong một
hoặc nhiều các phân loại hoặc lớp các tài liệu tương tự xác định trước. Sự
khác nhau trong các kết của của từng phân loại từ sự lựa chọn tập đặc trưng
tới sự kết hợp của tài liệu đã cho với một phân loại cho trước. Chủ trương của
nhận dạng phân loại văn bản xếp các tài liệu văn bản vào trong các phân loại
của các tài liệu với các yêu cầu cao hơn để thu nhận nhanh hơn các tài liệu đó
và cung cấp các lĩnh vực trong đó người dùng có thể khảo sát sâu hơn các tài
liệu tương tự. Trước đây, các hệ thống thu nhận thông tin sử dụng các biểu đồ
phân loại truyền thống trong khi hầu hết các giải thuật phân nhóm sử dụng mơ
hình khơng gian vector để hình thức hố các nhóm tài liệu.
Gần đây hơn, các nhà nghiên cứu đã thực hiện sử dụng các kỹ thuật học
máy để kết hợp tự động các tài liệu với các phân loại bằng cách đầu tiên sử
dụng một tập huấn luyện để thông qua bộ phân loại tới tập đặc trưng của tập
tài liệu đặc biệt. Quy trình học máy được khởi tạo bởi một một sự kiểm tra
các tài liệu mẫu để quyết định tập đặc trưng tối thiểu mà sinh ra các kết quả
phân loại mong muốn. Giai đoạn huấn luyện này có thể được kiểm sốt hoặc
khơng kiểm sốt. Trong cả hai trường hợp một tập các phân loại được định
nghĩa một quyền ưu tiên, khơng giống phân nhóm mà định nghĩa các phân
loại dựa trên đặc trưng của các tài liệu thực sự. Các kỹ thuật học khơng kiểm
sốt sử dụng các đặc trưng của các tài liệu huấn luyện để cho giải thuật quyết
định phân loại mỗi tài liệu thuộc vào. Các kỹ thuật học có kiểm sốt sử dụng
một tập các tài liệu huấn luyện mà đã được kết hợp trong một phân loại để
quyết định tập đặc trưng nào của các tài liệu sẽ tạo ra kết quả mong muốn.
Các kỹ thuật học máy, nếu thành công, cung cấp một ưu thế mới với các tập
tài liệu động thơng qua qua mơ hình khơng gian vector chuẩn, trong đó hướng

Luận văn Thạc sỹ


Support Vector Machine


^ 9 ]

dẫn của các tài liệu mới và các tập tài liệu mới sẽ không yêu cầu xây dựng lại
các ma trận vector tài liệu.
Với số lượng thông tin ngày càng tăng được sinh ra bởi các giao dịch
thương mại và các nhà nghiên cứu có một nhu cầu cho các giải thuật chính
xác và nhanh để phân tích dữ liệu. Các cải tiến trong kỹ thuật CSDL, thực
hiện tính tốn và trí tuệ nhân tạo đã xây dựng để phát triển phân tích dữ liệu
thơng minh. Dữ liệu thế giới thực thường được đặc tính hố bằng cách có các
số lớn các ví dụ, ví dụ hàng tỷ các giao dịch thẻ tín dụng ,…Quan hệ giữa các
biến dự đoán như ký hiệu vật lý và các khái niệm đích,… thường khơng tuyến
tính. Một kỹ thuật gần đây được phát triển để thu nhận các vấn đề đó là SVM.
SVM được phát triển như một công cụ thô để phân loại và hồi quy trong các
lĩnh vực phức tạp và đa dạng.
Các CSDL thương mại hiện đại càng phát triển đã làm tăng khả năng
phân tích. Kỹ thuật khai phá văn bản trở nên chủ yếu để phân tích khối lượng
lớn dữ liệu. Các kỹ thuật khai phá tài liệu hiện tại đã đưa ra các kết quả chính
xác cao và tổng q hố cho tập dữ liệu. Tuy nhiên, các kết quả thu được có
chất lượng cao yêu cầu mức độ chuyên nghiệp hơn của người dùng. SVM là
một giải thuật khai phá văn bản mạnh có thể giải quyết các vấn đề mà không
cần các phương pháp thống kê truyền thống. Tuy nhiên, vẫn còn một số giới
hạn về độ phức tạp phương pháp luận, khả năng linh hoạt, và cài đặt sản phẩm
SVM có chất lượng thấp. Luận văn này mô tả cách thực hiện của SVM nhằm
chính vào tính dễ sử dụng và khả năng linh hoạt trong khi vẫn duy trì tính
chính xác cao. SVM đã được hợp nhất vào CSDL Oracle và do đó có thể dễ
dàng khai phá văn bản trong CSDL với việc hỗ trợ dữ liệu trong CSDL hoặc

ngoài CSDL và thực hiện phân loại với bộ dữ liệu gồm nhiều phân loại và
mỗi tài liệu có thể thuộc một hoặc nhiều phân loại khác nhau.

Luận văn Thạc sỹ

Support Vector Machine


^ 10 ]

Với dữ liệu thông tin trong CSDL ngày càng lớn cùng với yêu cầu thực
tế của các ứng dụng phân loại văn bản là đa lớp và đa nhãn nên trong luận văn
này tác giả tập trung nghiên cứu về vấn đề phân loại văn bản bằng phương
pháp SVM và thử nghiệm với bộ dữ liệu gồm nhiều phân loại khác nhau bên
trong CSDL. Trong phần thực nghiệm, chúng tôi cũng thử nghiệm với các
văn bản được đưa vào trong CSDL Oracle, đồng thời thực hiện thử nghiệm
giải thuật SVM đã được hợp nhất trên Oracle với phiên bản mới nhất là
Oracle 10g Release 2 .
Nội dung của luận văn được chia thành 2 phần chính.
Phần 1: Cơ sở lý thuyết về các vấn đề được nêu trên. Phần này được
tổ chức với 3 chương. Chương 1 là giới thiệu tổng quan về Khai phá văn bản.
Chương 2 tác giả trình bày về quá trình hình thành SVM, nội dung giải thuật
SVM và một số vấn đề khi phân loại với SVM. Chương 3 trình bày về khái
niệm phân loại văn bản và lý do vì sao SVM lại được lựa chọn cho phân loại
văn bản
Phần 2: mô tả phương pháp luận về khai phá văn bản với Oracle, và
phương pháp để có thể thực hiện phân loại văn bản trong Oracle với giải
thuật SVM. Phần này được tổ chức thành 2 chương. Chương 4 trình bày
phương pháp luận về khai phá văn bản trong Oracle. Chương 5 báo cáo một
số kết quả thử nghiệm dữ liệu văn bản với giải thuật SVM trong CSDL Oracle

10g.
Ngoài ra, tại phần cuối cùng là: Kết luận và định hướng nghiên cứu và
phát triển của luận văn.

Luận văn Thạc sỹ

Support Vector Machine


^ 11 ]

Em xin chân thành cảm ơn TS.Nguyễn Linh Giang cùng các thày cô
giáo bộ môn đã trang bị kiến thức, giúp đỡ tận tình trong suốt quá trình học và
quá trình làm luận văn. Em cũng cảm ơn những người bạn lớp CH CNTT
2004-2006, các bạn đồng nghiệp, những người bạn thân và gia đình đã thường
xuyên động viên khích lệ và giúp đỡ em trong thời gian qua.

Luận văn Thạc sỹ

Support Vector Machine


^ 12 ]

PHẦN I - CƠ SỞ LÝ THUYẾT
Trong phần đầu tiên này, tác giả đưa ra một số khái niệm, quá trình hình
thành và các vấn đề khi phân loại thông thường khi áp dụng SVM:
- Khái niệm về khai phá văn bản
- Giới thiệu phương pháp SVM
- Các vấn đề gặp phải khi phân loại bằng phương pháp SVM

- Bài toán phân loại văn bản, cách sử dụng SVM trong bài toán phân
loại văn bản.

Luận văn Thạc sỹ

Support Vector Machine


^ 13 ]

CHƯƠNG 1. TÔNG QUAN VỀ KHAI PHÁ VĂN BẢN
Mục đích của chương này là giới thiệu một cách tóm tắt về vấn đề khai phá
dữ liệu văn bản, bài toán phân loại văn bản.
9 Khai phá dữ liệu văn bản là gì?
9 Các bước để xây dựng bài toán khai phá dữ liệu văn bản.
9 Bài toán phân loại văn bản
9 Khái niệm các bước cần thực hiện để phân loại văn bản

1.1. Một số khái niệm
Trước tiên, tác giả xin trình bày một số khái niệm cơ bản để hiểu rõ
được mối liên quan giữa dữ liệu, thơng tin và tri thức, và lý do vì sao lại cần
phải giải quyết các bài toán liên quan của lĩnh vực này.
• Dữ liệu được hiểu là một chuỗi các con số hoặc các đối tượng mà
chúng ta thu thập được hàng ngày. Ví dụ: dữ liệu là các file trong máy
tính, dữ liệu là các văn bản giấy tờ mà chúng ta xử lý hàng ngày, ...
• Thơng tin là dữ liệu đã được loại bỏ đi nhiễu, sự dư thừa và đã được
biểu diễn dưới dạng mà con người có thể nhận thức được. Ví dụ: thơng
tin về tình hình chiến sự tại IRAQ, thơng tin về nhiệt độ trong tháng.
• Tri thức được hiểu là các thơng tin đã được tích hợp lại, đã được nhận
thức, kiểm nghiệm, hay được đúc rút ra thành các quy luật có ý nghĩa

đối với con người. Ví dụ: từ thơng tin về nhiệt độ trong tháng, con
người có thể đưa ra được những dự báo thời tiết quan trọng,....
Như vậy, tri thức chính là các dữ liệu, thơng tin ở mức trừu tượng và
khái quát cao hơn, tri thức ở dạng cô đọng và dễ hiểu nhất đối với con người.
Rõ ràng trong kỷ nguyên công nghệ thông tin này thì con người chỉ muốn tìm
kiếm và lĩnh hội các tri thức, đó là cách nhanh nhất và hợp lý nhất, chứ không

Luận văn Thạc sỹ

Support Vector Machine


^ 14 ]

thể có đủ thời gian và khả năng để hiểu được các dữ liệu ở một dạng thô sơ
nào đó. Điều đó cũng cho thấy vai trị quan trọng của lớp các bài toán khai
phá dữ liệu và phát hiện tri thức. Phần tiếp theo tác giả trình bày về tiến trình
khai phá dữ liệu và phát hiện tri thức (KDD). Theo nhiều tài liệu khác nhau
thì tiến trình KDD nói chung đều bao gồm 5 bước cơ bản sau đây:
Bước 1. Tìm hiểu về lĩnh vực và các vấn đề có liên quan.
Bước 2. Thu thập và tiền xử lý dữ liệu. Đây là một bước cực kỳ quan trọng,
chiếm phần lớn thời gian và sức lực (70 ÷ 90%) trong cả tiến trình.
Nó cũng ảnh hưởng tới toàn bộ các kết quả thu được về sau của tiến
trình khai phá dữ liệu.
Bước 3. Khai phá dữ liệu, trích chọn ra các mẫu, các thơng tin có ý nghĩa.
Bước này gồm các phương thức để sản sinh ra các tri thức hữu ích.
Bước 4. Thể hiện và đánh giá các tri thức đã rút ra được ở bước 3.
Bước 5. Đưa các tri thức đã phát hiện được vào sử dụng trong thực tế.
Mơ hình KDD khơng phải là một mơ hình như kiểu mơ hình thác nước
(thực hiện xong bước 5 là kết thúc) mà trên thực tế nó có tính lặp lại, bước

sau phản hồi về cho bước trước đó, rồi thực hiện những sự điều chỉnh cần
thiết nhằm đưa đến một kết quả tốt nhất cho tồn bộ hệ thống.

Hình 1.1. Các bước trong tiến trình KDD

Luận văn Thạc sỹ

Support Vector Machine


^ 15 ]

Việc áp dụng tiến trình KDD có thể thực hiện trên nhiểu kiểu loại dữ
liệu khác nhau với các hình thức tổ chức lưu trữ khác nhau. Hiện nay, có rất
nhiều cách tổ chức dữ liệu khác nhau, cách phổ biến nhất và cũng là cách
truyền thống là cơ sở dữ liệu quan hệ, ngồi ra cịn có các cơ sở dữ liệu hướng
đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu hướng thời gian, và cơ sở
dữ liệu văn bản,…Đối với mỗi dạng cơ sở dữ liệu lại có các phương pháp xử
lý khác nhau và mục đích khai phá dữ liệu khác nhau tùy theo tính chất và đặc
thù của dữ liệu.
Các kỹ thuật được sử dụng có thể là các phương pháp truyền thống như
học máy (machine learning), nhận dạng (recognition), thống kê (statistics),
phân loại (classification),… và các kỹ thuật được phát triển bởi ngành nghiên
cứu trí tuệ nhân tạo như mạng nơ-ron nhân tạo (neural network), thuật toán di
truyền (genetic algorithm), quy nạp luật (rule reduction), cây quyết định
(decision tree),…
Phần tiếp theo tác giả đề cập các khái niệm cơ bản trong lĩnh vực Text
Mining, lĩnh vực mà đồ án tập trung giải quyết.

1.2. Khai phá dữ liệu văn bản – Text Mining

Trước khi đi sâu vào các bài toán liên quan tới khai phá dữ liệu văn
bản, tác giả trình bày một số khái niệm xung quanh bài tốn này.
• Thế nào là văn bản: đó là các tài liệu ở dạng khơng có cấu trúc hoặc
bán cấu trúc. Ví dụ như các các file dạng đi .txt, .doc.
• Khai phá dữ liệu văn bản là gì?
- Khai phá dữ liệu văn bản là việc trích ra, lấy ra các thơng tin có ích,
chưa được biết đến cịn tiềm ẩn trong các kho dữ liệu văn bản lớn.
- Khai phá dữ liệu văn bản là việc thu thập và phân tích dữ liệu bằng
các cơng cụ tự động hoặc bán tự động từ các nguồn tài liệu đã có
khác nhau để có được các tri thức mới, chưa được biết đến trước đó.

Luận văn Thạc sỹ

Support Vector Machine


^ 16 ]

- Khai phá văn bản là phát hiện ra các mô tả chung của các lớp đối
tượng, các từ khoá, các mối liên quan về mặt nội dung, sự phân loại
của các đối tượng văn bản, .v.v...
• Các bài toán hiện nay được quan tâm trong lĩnh vực TM:
a) Phát hiện xu hướng văn bản (Text Trend Detection):
Đây là bài toán phát hiện các xu hướng, các luật chưa được biết đến
trong các CSDL văn bản lớn. Ví dụ điển hình nhất của bài tốn này đó là tìm
ra các thơng tin xác định khả năng bị ung thư của một bệnh nhân từ cơ sở dữ
liệu bệnh án về ung thư đã được thu thập, hay đưa ra được các xu hướng mua
các mặt hàng của khách hàng khi họ đi siêu thị, v.v... Đây là bài tốn hay, có
ý nghĩa rất quan trọng và tất nhiên đó cũng là bài tốn khó nhất trong các bài
tốn thuộc về lĩnh vực khai phá dữ liệu văn bản.

b) Tìm kiếm văn bản (Text Retrieval):
Tìm kiếm văn bản là quá trình tìm các văn bản trong một kho dữ liệu
theo các yêu cầu của người dùng. Ở đây, các yêu cầu là các truy vấn và
thường được biểu diễn dưới dạng thuật ngữ hay biểu thức logic giữa các thuật
ngữ. Ví dụ: người dùng đưa vào truy vấn sau: "Manchester United" & "David
Beckham" & "Victoria". Ứng với truy vấn này, hệ thống sẽ tìm tất cả các tài
liệu về "Manchester United" có liên quan đến "David Beckham" và
"Victoria". Hiện nay, các hệ thống tìm kiếm mạnh và thơng dụng nhất như
Google cũng chỉ hiểu được các câu truy vấn có sử dụng phép tốn logic Và,
Hoặc như trên.
Kết quả đưa ra cho người sử dụng là danh sách các tài liệu được sắp
xếp giảm dần theo mức độ phù hợp với truy vấn đầu vào.
c) Phân loại văn bản (Text Categorization - Text Classification):
Theo cách truyền thống, việc phân loại văn bản có thể thực hiện một
cách thủ cơng: đọc từng văn bản một và gán nó vào nhóm phù hợp nhất. Rõ

Luận văn Thạc sỹ

Support Vector Machine


^ 17 ]

ràng đây là một công việc tốn nhiều thời gian, công sức nếu số lượng văn bản
cần phân loại lớn. Vì thế việc xây dựng các cơng cụ tự động phân loại các văn
bản là một việc cần thiết và có tính hữu ích cao.
d) Lập nhóm văn bản (Text Clustering):
Lập nhóm văn bản là bài tốn tự động lập ra các nhóm văn bản từ một
tập các văn bản có sẵn căn cứ vào sự tương tự về mặt nội dung giữa các văn
bản. Số lượng nhóm từ 1 đến K. Người sử dụng có thể chỉ định số nhóm cần

lập hoặc hệ thống tự động tính số nhóm sao cho phù hợp nhất. Nhờ việc phân
loại tự động, hệ thống sẽ gợi ý cho người dùng cách phân loại một tập các văn
bản có sẵn mơt cách hợp lý.
Đối với bài tốn này, khơng bao giờ có một kết quả thoả mãn hồn tồn
theo ý người dùng. Lý do chính là vì máy tính khơng thể hiểu được bản chất
của các văn bản đó và kết quả tất yếu là việc phân loại không thể làm người
sử dụng ln cảm thấy hài lịng. Chúng ta cũng phải thừa nhận rằng ngay cả
con người giải quyết bài tốn này cũng rất khác nhau, tuỳ theo sở thích và
quan niệm của người đó. Ví dụ, khi cho lập nhóm các từ: "bơi", "vận động
viên", "nghiên cứu" và "sinh viên". Người thứ nhất có thể lập thành 2 nhóm:
động từ (bơi, nghiên cứu) và danh từ (vận động viên, sinh viên), trong khi đó
người thứ hai lại lập thành 2 nhóm khác: thể thao (bơi, vận động viên) và học
tập (sinh viên, nghiên cứu). Vì vậy, việc xây dựng một hệ thống tự động lập
nhóm, phân loại đúng tuyệt đối là một việc phi thực tế.
e) Tóm tắt văn bản (Text Summarization):
Tóm tắt văn bản là bài tốn tìm ra thể hiện nội dung của một văn bản
thông qua một vài đoạn văn bản, hoặc thông qua các câu quan trọng nhất của
văn bản đó.
Ứng dụng điển hình của bài tốn này là trong tìm kiếm văn bản. Các
kho dữ liệu đều bao gồm vô số các tài liệu, kích thước tài liệu có thể nhỏ

Luận văn Thạc sỹ

Support Vector Machine


^ 18 ]

nhưng cũng có thể lên tới hàng trăm trang. Khi người dùng đưa vào một truy
vấn yêu cầu hệ thống tìm kiếm đưa ra những văn bản có liên quan, thì kết quả

thường là một danh sách dài có thể lên đến hàng trăm tài liệu. Làm thế nào để
có thể tìm được tài liệu người dùng quan tâm giữa một danh sách dài như thế,
tất nhiên chúng ta không đề cập đến việc đọc hết từng tài liệu để lấy ra những
tài liệu mình thấy là thích hợp nhất. Hệ thống tóm tắt văn bản sẽ làm cho việc
tìm kiếm giảm nhẹ đi rất nhiều bằng cách tự động tóm lược nội dung của tồn
bộ văn bản bởi một vài đoạn hoặc bởi những câu quan trọng nhất. Sau khi đọc
qua đoạn tóm lược này, người dùng có thể biết được đây có phải là những tài
liệu chứa thông tin mà họ quan tâm hay không.
Hầu hết các máy tìm kiếm hiện nay như Google, Altavista, ... đều có
chức năng này khi thể hiện kết quả của truy vấn.
f) Dẫn đường văn bản (Text Routing):
Bài toán dẫn đường văn bản; là sự tổ hợp giữa bài toán tìm kiếm văn
bản và phân loại văn bản. Giống như phân loại văn bản, bài toán dẫn đường
đưa các bài báo về các nhóm khác nhau. Tuy nhiên nó cũng giống bài tốn
tìm kiếm, mỗi nhóm văn bản được gán với các thơng tin cần thiết của một hay
nhiều nhóm người dùng. Mỗi người dùng có thể thay đổi thêm bớt các u
cầu của mình. Q trình phản hồi có thể được sử dụng để nâng cao chất lượng
tìm kiếm.
g) Trích chọn từ khố (Keyword Extraction):
Bài tốn trích chọn từ khố, thực hiện việc trích ra được các từ khố
quan trọng nhất của văn bản, thể hiện đặc thù về chun mơn của văn bản đó.
Phần tiếp theo tác giả trình bày chi tiết hơn về bài tốn phân loại văn
bản và phần tiếp sau và cũng là cuối cùng trong chương trình là quy trình
phân loại văn bản.

Luận văn Thạc sỹ

Support Vector Machine



^ 19 ]

1.3. Phân loại văn bản
Đề hiểu một cách đơn giản thì phân loại văn bản là việc gán các tài liệu
vào trong các phân loại dựa trên nội dung của chúng. Sử dụng học máy, mục
tiêu là để học các bộ phân loại từ các mẫu mà văn bản chưa thấy có thể được
tự động phân loại.
Về mặt hình thức, cho trước một tập các nhãn (các phân loại) C = {c1, .
. . , c|C|} và một tập các tài liệu chưa thấy trước đó D = {d1, d2, . . .}, một bộ
phân loại là một hàm K ánh xạ từ D tới tập của tất cả các tập con của C. Hình
1.2 biểu diễn một biểu đồ đơn giản của phân loại văn bản:

Hình 1.2. Hoạt động của một bộ phân loại trên một tập tài liệu
Trong một vài ứng dụng, các bộ phân loại chỉ gán một nhãn đơn tới
từng tài liệu, bởi vậy thường là một hàm ánh xạ trực tiếp từ D tới C. Thơng
thường một hàm trung gian rất hữu ích cho các phân loại theo vùng hoặc phân
loại mềm, ánh xạ từ D×C tới tập các số thực R gán một điểm tới từng phân
loại cj cho từng tài liệu di. Các phân loại tính điểm có thể được biểu diễn tới
một hệ chuyên gian nhân tạo theo thứ tự giảm, và con người sau đó có thể tạo
các quyết định cuối cùng trên thành phần loại của tài liệu. Hệ thống có thể tự
tạo một quyết định dựa trên một ngưỡng tới thành phần phân loại, biến đổi
vấn đề trở lại các phân loại cứng được biểu diễn trong hình 1.2.
Các cách tiếp cận hiện đại chuẩn để tạo các hàm phân loại mới là để
xây dựng chúng sử dụng các kỹ thuật học máy từ một tập các tài liệu huấn

Luận văn Thạc sỹ

Support Vector Machine



^ 20 ]

luyện Tr. Đây là một tập các tài liệu do người dùng cung cấp và được gán
nhãn trước mà cho phép một phân loại phân bổ tương tự với sự phân bổ của
D, và có các nối dụng cung cấp thông tin phần nào về các tài liệu sẽ được ánh
xạ tới các phân loại. Các giải thuật sau đó có thể được phát triển để tạo ra các
sự tổng quát hoá về quan hệ giữa nội dung tài liệu và phân loại tài liệu, mã
hoá các sự tổng qt hố đó trong hàm học K.

1.4. Quy trình phân loại văn bản
Để huấn luyện một bộ phân loại theo cách trên, người dùng phải bắt
đầu với một một huấn luyện, và được gọi là Tr. Đây là một tập tài liệu được
gán nhãn trước với các phân loại mà được xem là đúng hoàn toàn - chúng
được gán thủ cơng bởi một chun gia về lĩnh vực đó, một người biết rõ kiểu
tài liệu chứa trong các văn bản và biết làm thế nào để gán các phân loại tới
từng tài liệu dựa trên nội dung tài liệu
Phác thảo cơ bản về việc tạo các ứng dụng phân loại văn bản là khá đơn
giản: các tài liệu trong Tr được đưa tới hệ thống phân loại văn bản, hệ thống
xử lý nội dung các tài liệu và hàm phân loại xác định K được sinh ra có thể
được sử dụng để phân loại các tài liệu tương lai từ tập D. Trong một ứng
dụng, nhiều điểm của quy trình này cần được quản lý trong nhiều cách xác
định. Từ phần 1.4.1 tới 1.4.10 miêu tả các giai đoạn cuả quá trình này.
1.4.1.

Lưu trữ tài liệu
Trong một tổ chức mà cần một ứng dụng phân loại văn bản, các tài liệu

có thể có từ nhiều nguồn. Chúng có thể xuất phát từ các văn bản thuần tuý
(chỉ có các ký tự) hoặc các thông điệp thư điện tử đã định dạng, chúng có thể
là các trang web đã được xử lý và cịn thơ, chúng có thể là các bộ dữ liệu từ

một CSDL (phần 1.4.4), hoặc chúng không thể có một biểu diễn ngồi hệ

Luận văn Thạc sỹ

Support Vector Machine


^ 21 ]

thống phân loại văn bản. Bởi vậy quan trọng để nhận dạng khái niệm phương
tiện lưu trữ tài liệu và tiến hành chuyển đổi từ các phương tiện đó tới một
trung gian có thể truy cập tới hệ thống phân loại văn bản, là một phần quan
trọng của quy trình phân loại văn bản.
Hơn nữa, nhiều bộ dữ liệu phân loại văn bản là khá lớn. Theo định
dạng ban đầu của chúng, chúng có thể lớn hơn khối lượng bộ nhớ trên máy xử
lý. Đầu tiên, cần chuyển đổi các tài liệu tới các chuẩn lưu trữ đặc biệt (ví dụ,
trong một tập các file trên hệ thống file cục bộ) để hệ thống phân loại văn bản
có thể truy cập chúng có thể là khơng thể được hoặc khơng mong muốn vì các
lý do về thời gian, không gian hoặc dư thừa dữ liệu. Thứ hai, một kỹ thuật mà
có thể giải quyết quan trung gian lưu trữ âm của các tài liệu mà không không
tất cả các tài liệu vào trong bộ nhớ là có thể cần thiết trong một hệ thống phân
loại văn bản.
1.4.2.

Định dạng văn bản
Tuy hầu hết các phân loại văn bản xem xét một tài liệu là một văn bản

thuần tuý chuỗi dữ liệu, nhưng điều này là khó gặp trong một mơi trường ứng
dụng. Các tài liệu có thể được lưu trong nhiều định dạng tài liệu, bao gồm văn
bản thuần tuý (plain text), HyperText Markup Language (HTML), Adobe’s

Portable Document format (PDF), Extensible Markup Language (XML),
Microsoft Word (DOC), các thư điện tử mã hoá MIME, …. Dữ liệu bên trong
mỗi tài liệu cũng có thể được xem xét một phần định dạng của nó khi khối
lượng thơng tin trích dẫn hoặc các biến đổi khác cần được áp dụng tới dữ liệu
tài liệu để làm chúng có khả năng có thể truy cập được tới hệ thống phân loại
văn bản. Ví dụ, các chuỗi số trong một số tập tài liệu có thể là các thuật ngữ
đáng xem xét khi phân loại, nhưng ngược lại trong các bộ dữ liệu khác có thể
chỉ có dữ liệu nhiễu. Vì lý do tương tự như đã đề cập trong phần trước, có thể
mong muốn với một hệ thống phân loại văn bản giải quyết với các vấn đề trực

Luận văn Thạc sỹ

Support Vector Machine


^ 22 ]

tiếp, hoặc để cung cấp một kỹ thuật để mở rộng hệ thống để nhận dạng các
chuẩn mới, hoặc là chuyển đổi dữ liệu của tất cả các dữ liệu tới một chuẩn
nhận dạng bởi hệ thống.
1.4.3.

Cấu trúc hoá tài liệu
Một vấn đề khác với vấn đề chuẩn tài liệu mà cần quan tâm là vấn đề là

cấu trúc tài liệu. Trong thời đại hiện nay khi dữ liệu XML ngày càng tăng
trong trao đổi dữ liệu và định dạng lưu trữ, cấu trúc của một tài liệu, cách các
phần của một tài liệu liên quan tới nhau và xếp lồng nhau để tạo thành toàn bộ
tài liệu có thể là quan trọng để hiểu ý nghĩa của tài liệu.
Trong phân loại văn bản, một ít là tạo bởi cấu trúc văn bản, ngoại trừ

rằng một hệ thống phân loại văn bản có thể gán các trọng số quan trọng tới
các thuật ngữ trong một tài liệu theo các trọng số quan trọng được thiết lập
trước theo các phần trong các thuật ngữ đó được tìm thấy. Ví dụ, một thuật
ngữ tìm thấy trong một tiêu đề của một tài liệu có thể được xem xét 2 lần
quan trọng hơn một thuật ngữ tìm thấy trong nội dung. Tuy nhiên, khi nghiên
cứu vào sự phân loại của việc thực hiện các tài liệu có cấu trúc, có thể là một
lĩnh vực rất lớn để xem xét việc xây dựng các hệ thống phân loại văn bản.
1.4.4.

Tách dữ liệu
Để chuyển đổi văn bản của một tài liệu thành dữ liệu mà có thể được

phân tích bởi một giải thuật học máy, cần chia văn bản thành các đơn vị rời,
mỗi đơn vị tương ứng với một từ hoặc cụm từ trong văn bản. Việc này được
gọi là tách từ (tokenization). Trong phần thảo luận này, từ thuật ngữ ám chỉ
tới thực thể ngơn ngữ chính xác khi nó xuất hiện trong văn bản nguồn, token
là một chuỗi được trích ra bởi hệ thống phân loại văn bản. Việc phân đoạn dữ
liệu văn bản vào trong các khoanh (chunk) biểu diễn các từ riêng biệt có thể
giống với bài tốn khơng phức tạp, nhưng thực tế có nhiều biến đổi quy trình

Luận văn Thạc sỹ

Support Vector Machine


^ 23 ]

này sẽ được thực hiện. Việc phân tách các từ bằng khoảng trống (dấu cách,
tab,..) là không đủ vì chưa thực hiện với các dấu chấm hay các từ ghép, việc
tách từ này thường cần được tạo với một vài kiến trức về tập tài liệu D. Hơn

nữa, nhiều ngôn ngữ như tiếng Hàn hay tiếng Nhật không chứa các khoảng
trắng để chỉ ra sự phân tách giữa các từ. Quy trình tách từ có thể xố dữ liệu
có trong danh sách từ dừng (stop-list) định nghĩa trước đó. Từ dừng là các
thường xuất hiện trong lĩnh vực (như “the” hay “and” trong các văn bản tiếng
Anh) và được cho rằng chứ một ít hoặc khơng liên quan tới vấn đề thuộc
phân loại bằng tay.
Để đưa ra các vấn đề đó, một hệ thống phân loại văn bản cần cho phép
các biến đổi trong tiến trình phân loại văn bản. Việc này có thể bao gồm các
điều chỉnh một tập các tham số điều khiển hoặc một vài trường hợp người
phát triển ứng dụng có thể viết thêm mã điều khiển trong trong các trường
hợp xác định.
1.4.5.

Giảm chiều
Giống với nhiều lĩnh vực nghiên cứu xử lý ngôn nhữ, nhiều bộ phân

loại văn bản phải giải quyết vấn đề tính đa chiều cao. Số chiều của khơng gian
trong đó giải thuật học máy thực hiện có thể là lớn hơn nhiều tổng số các
thuật ngữ trong Tr.
Tính đa chiều cao có thể đưa ra hai vấn đề. Đầu tiên, một vài giải thuật
học máy có thể hiệu quả trên dữ liệu ít chiều, nhưng chúng yêu cầu nhiều thời
gian hoặc bộ nhớ hơn thực tế khi tính đa chiều của tập dữ liệu là cao. Thứ hai,
dữ liệu Tr trong khơng gian đa chiều lớn có thể là q rải rác, mà không đủ
các điểm dữ liệu khác 0 để tạo ra bất kỳ một biến đổi quy nạp nào trong quá
trình huấn luyện. Điều này đặc biệt đúng trong các ngơn ngữ hình thái học
cao như Phần Lan, trong đó một từ đơn có thể có hàng ngàn hoặc hàng triệu

Luận văn Thạc sỹ

Support Vector Machine



^ 24 ]

kiểu biến tố, và hầu hết các kiểu có thể chỉ thấy một lần trong tồn bộ Tr, làm
chúng hầu như khơng có ích trong q trình học quy nạp.
Một cách nhắm vào vấn đề tính đa chiều cao là áp dụng một giải thuật
chặn ngôn ngữ thành các thuật ngữ tìm thấy trong Tr và D. Các giải thuật đó
biến đổi các từ bằng cách xố các tiền tố và hậu tố. Một cách khác để giảm
tính đa chiều là trong một hệ thống phân loại áp dụng lựa chọn đặc trưng
và/hoặc trích chọn đặc trưng.
Có cj
Đúng

Sai

Có

Đúng

A

B

fk

Sai

C


D

Bảng 1.1. Bảng ngẫu nhiên cho phân loại cj và thuật ngữ fk.
(Số lượng A-D biểu diễn số tài liệu với thuộc tính cho trước)
Cả hai kỹ thuật biến đổi tồn bộ tập các thuật ngữ trong tài liệu vào một
tập đặc trưng nhỏ hơn với ít rải rác hơn, chọn các thuật ngữ “liên quan nhất”
sử dụng một vài tiêu chí thống kê. Ba trong số các tiêu chí lựa chọn đặc trưng
thường được sử dụng là tần xuất tài liệu (document frequency (DF)), χ2 , và
các độ đo thu nhận thông tin (information gain (IG)). DF(fk) đơn giản là số
các tài liệu của Tr trong đó số đặc trưng fk xuất hiện. χ2 được định nghĩa trong
phương trình (1.1). A, B, C, và D là các thuật ngữ trong bảng 1. χ2(fk, cj) có
giá trị 0 khi fk and cj độc lập, và là 1 khi chúng có liên quan với nhau.
χ 2 (fk ,c j )=

Luận văn Thạc sỹ

T r ( AD − CB )
( A + C )( B + D)( A + B)(C + D)
2

(1.1)

Support Vector Machine


^ 25 ]

Để tìm tồn bộ độ đo χ2(fk), các thuật ngữ χ2(fk, cj) có thể là trung bình
(được đánh trọng số là tần xuất của từng phân loại) hoặc giá trị tối đa với từng
phân loại có thể được nhận. IG được định nghĩa trong phương trình (1.2).

P(fk) và P( f k ) là các xác suất mà một tài liệu có thể chứa hoặc khơng chứa fk.

C f k và C f k là các tập phân loại của D chứa hoặc không chứa fk. H(x) là
hàm entropy chuẩn từ Lý thuyết thông tin.

IG ( f k ) = H (C ) − P( f k) H (C f k ) − P( f k ) H (C f )
k

1.4.6.

(1.2)

Mơ hình hố khơng gian vector
Như đã trình bày ở trên, tác giả đã đề xuất mỗi tài liệu có thể được xem

như một vector trong một khơng gian vector chung có số chiều được biểu diễn
là tập các đặc trưng duy nhất từ Tr. Ý tưởng này tạo thành các cơ sở cho một
vài kỹ thuật học máy, gồm có các bộ phân loại máy học vector hỗ trợ (SVM)
và k láng giềng gần nhất (KNN). Nó cũng cho phép các giải thuật xử lý vector
tuỳ ý trên dữ liệu văn bản tận dụng các kết quả phân loại. Một tập các giải
thuật thường được sử dụng cho mục đích thu nhận thơng tin là sơ đồ trọng số
thuật ngữ TF/IDF của Salton và Buckley, cho phép một vài cách khác nhau để
biểu diễn một tài liệu như một vector trong khơng gian vector chung. Các
thuật ngữ có thể được đánh trọng số bởi tần xuất của chúng trong tài liệu, tính
logarit các tần xuất đó hoặc bởi một biểu diễn minh họa có hay khơng có
thuật ngữ. Trọng số thuật ngữ cũng có thể được làm giảm bằng một yếu tố
biểu diễn sự xuất hiện của thuật ngữ trong các tài liệu khác, trên học thuyết
bất cứ thuật ngữ nào đưa ra trong hầu hết các tài liệu có sự liên quan giữa các
phân loại. Cuối cùng, độ dài tồn bộ của vector tài liệu có thể được giảm bớt
theo nhiều cách khác nhau.


Luận văn Thạc sỹ

Support Vector Machine