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
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ỹ
3
Support Vector Machine
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
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 Thu nhận thông tin
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ỹ
6
Support Vector Machine
Danh mục các bảng
Bảng 1.1. Bảng ngẫu nhiên cho phân loại c
j
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ỹ
8
Support Vector Machine
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 hoá 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ộ
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 quá hoá 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ỹ
10
Support Vector Machine
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à
^ ]
Luận văn Thạc sỹ
12
Support Vector MachinePHẦ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
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ỹ
14
Support Vector Machine
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 toàn bộ hệ thống.
Hình 1.1. Các bước trong tiến trình KDD
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ỹ
16
Support Vector Machine
- 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 toá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 toán hay, có
ý nghĩa rất quan trọng và tất nhiên đó cũng là bài toán khó nhất trong các bài
toá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à
con người giải quyết bài toá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 toá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 toá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ỹ
18
Support Vector Machine
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 toà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.
. . , c
|C|
} và một tập các tài liệu chưa thấy trước đó D = {d
1
, d
2
, . . .}, 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 c
j
cho từng tài liệu d
i
. 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ỹ
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 ngoài hệ
^ ]
Luận văn Thạc sỹ
21
Support Vector Machine
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
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 toá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ỹ
23
Support Vector Machine
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
ể xoá 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
, làm
chúng hầu như không có ích trong quá 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 T
r
và D. Các giải thuật đó
biến đổi các từ bằng cách xoá 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ó c
j
Đúng Sai
Đúng
A B
Có
f
k
Sai
C D
Bảng 1.1. Bảng ngẫu nhiên cho phân loại c
j
và thuật ngữ f
k
.
(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 toàn bộ tập các thuật ngữ trong tài liệu vào một
()
(
)
))()()((
,
2
2
DCBADBCA
CBADT
cf
r
jk
++++
−
=
χ
(1.1)
^ ]
Luận văn Thạc sỹ
25
Support Vector Machine
Để tìm toàn bộ độ đo
χ
2
(f
k
), các thuật ngữ
χ
2
(f
kfkk
CHfPCHfPCHfIG −−=
(1.2)
1.4.6. Mô hình hoá 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ừ T
r
. Ý 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 toàn bộ của vector tài liệu có thể được giảm bớt
theo nhiều cách khác nha
u.
Copyright: Tài liệu đại học ©