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
^ ]
Luận văn Thạc sỹ
2
Support Vector Machine
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
99 trang |
Chia sẻ: huyen82 | Lượt xem: 3588 | Lượt tải: 4
Tóm tắt tài liệu Phân loại văn bản bằng phương pháp Support vector machine, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 hoá 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ỹ
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
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ỹ
4
Support Vector Machine
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ỹ
5
Support Vector Machine
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 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 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ỹ
7
Support Vector Machine
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 hoá 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ỹ
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ộ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 soát hoặc
không kiểm soá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
soá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 soá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ỹ
9
Support Vector Machine
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 toá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 hoá 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 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à
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ỹ
11
Support Vector Machine
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ỹ
12
Support Vector Machine
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ỹ
13
Support Vector Machine
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ỹ
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
^ ]
Luận văn Thạc sỹ
15
Support Vector Machine
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ệ, ngoà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 toá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 đuô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ỹ
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à
"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 toá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ỹ
17
Support Vector Machine
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 toá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 toán này, không bao giờ có một kết quả thoả mãn hoàn toà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 luôn 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 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.
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 toá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 yêu
cầu của mình. Quá 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ừ khoá (Keyword Extraction):
Bài toán trích chọn từ khoá, thực hiện việc trích ra được các từ khoá
quan trọng nhất của văn bản, thể hiện đặc thù về chuyên 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 toá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ỹ
19
Support Vector Machine
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ỹ
20
Support Vector Machine
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 quát hoá đó 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 chuyên 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 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
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ỹ
22
Support Vector Machine
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 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
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à quá 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ỹ
24
Support Vector Machine
kiểu biến tố, và hầu hết các kiểu có thể chỉ thấy một lần trong toàn bộ Tr, 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 Tr 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ó cj
Đúng Sai
Đúng A B Có
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 toà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
2
DCBADBCA
CBADTcf
r
jk ++++
−=χ (1.1)
^ ]
Luận văn Thạc sỹ
25
Support Vector Machine
Để tìm toà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à )( kfP 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.
kf
C và
kf
C 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.
)()()()()()(
kk fkfkk
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ừ 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 toà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ỹ
26
Support Vector Machine
1.4.7. Giải thuật học máy
Nhiều giải thuật học máy khác nhau đã được nghiên cứu trong lĩnh vực
nghiên cứu phân loại văn bản và các giải thuật mới hoặc sự biến đổi trên hệ
thống hiện tại vẫn tiếp tục đang được phát triển. Hơn nữa, lựa chọn giải thuật
có thể phụ thuộc vào các giải thuật - ứng dụng khác không chỉ trong khả năng
thực hiện chính xác trên các tập dữ liệu khác nhau, nhưng cũng trong các
nguồn chung có thể yêu cầu chọn một giải thuật để hợp nhất vào trong một
framework. Trong một hệ thống phân loại văn bản, cần cho phép chọn theo
một vài giải thuật chuẩn và thống nhất các giải thuật đã được phát triển bởi
các nhà nghiên cứu.
1.4.8. Thiết lập cấu hình học máy
Thậm chí trong một giải thuật học máy cũng có thể có một vài tham số
có ảnh hưởng tới quy trình huấn luyện và phân loại. Ví dụ, giải thuật k láng
giềng gần nhất có một tham số điều chỉnh k và một giải thuật SVM cho phép
một vài biến về kiểu kernel sử dụng và hầu hết các giải thuật cho vào một vài
kiểu điều khiển việc cân bằng precision và recall với nhau. Để thu nhận sự
thực hiện tương ứng với một bài toán đã cho, những người ừng dụng cần các
cách đơn gian tới các tham số đó. Thực tế, vấn đề này không chỉ duy nhât với
thành phần học máy của phân loại văn bản. Một vài hướng đã thảo luận trước
đó của bài toán phân loại văn bản như chọn lựa chọn đặc trưng, giảm chiều và
biến đổi không gian vector có thể được điều khiển bởi các tham số mà người
kiểm soát có thể muốn thay đổi. Tính nhất quán trong việc điều khiển các
tham số của hệ thống có thể là một thành phần quan trọng trong thiết kế.
1.4.9. Học tăng cường
Một vài ứng dụng phân loại văn bản có thể được mong muốn kết hợp
lại với người dùng về có các quyết định phân loại của hệ thống có thể là đúng
hoặc không đúng. Việc này có thể cho phép với một số nhỏ các tập huấn
^ ]
Luận văn Thạc sỹ
27
Support Vector Machine
luyện ban đầu Tr hoặc với việc phân loại trên các khái niệm mà có thể thay
đổi theo thời gian. Quá trình này được gọi là học trực tuyến hay hoặc tăng
cường. Tuy nhiên, việc học tăng cường là không thể với tất cả các phương
pháp học máy, một vài giải thuật (mạng nơron) không thể hợp nhất với dấu
hiệu mới vào trong mô hình của chúng mà không thực hiện lại quy trình huấn
luyện. Với các giải thuật mà có thể được hỗ trợ, việc sử dụng học tăng cường
có thể được xem là quan trọng trong việc xây dựng một ứng dụng phân loại
văn bản.
1.4.10. Hành vi giả thuyết
Hầu hết các phương pháp phân loại văn bản chuẩn cho rằng mục tiêu
của phân loại văn bản là gán từng tài liệu tới một hoặc nhiều phân loại, ngược
lại được coi như một phân loại nhị phân. Tất nhiên, các vấn đề thế giới thực
thường bao gồm các bản thể (cây phân loại phân cấp) gồm hơn 2 phân loại và
thành viên có không là duy nhất. Tình huống này không biểu diễn một không
kết nối lý thuyết giữa nghiên cứu và thực tế vì mỗi vấn đề đa phân loại có thể
được đưa ra lại như một chuỗi các vấn đề nhị phân. Hầu hết các nhà xây dựng
ứng dụng, sẽ không muốn đưa lại các vấn đề của họ vì nó yêu cầu thêm các
công việc và có thể mơ hồ về ứng dụng cần phát triển.
^ ]
Luận văn Thạc sỹ
28
Support Vector Machine
CHƯƠNG 2. SUPPORT VECTOR MACHINE
Chương này tác giả sẽ đề cập tới quá trình hình thành và một số vấn
đền của SVM:
- Nội dung của phương pháp SVM
- Một số vấn đề khi phân loại SVM: vấn đề đa nhãn, vấn đề đa lớp -
đa nhãn. Các thức giải quyết các vấn đề không thể phân tách tuyến
tính
- Các phương pháp để tìm được siêu phẳng tối ưu.
2.1. Động cơ
2.1.1. Học máy
Hiện nay, có nhiều tập dữ liệu số lớn tồn tại trong các cơ quan, doanh
nghiệp trong các CSDL như thông tin sinh học, bộ văn bản, bài hát được số
hoá, thông tin WEB và thậm chí một vài kênh truyền hình cũng được số hoá.
Khi một số lượng lớn các dữ liệu trở nên lớn và khả năng tính toán của CPU
được cải thiện, thì việc hy vọng vào việc sử dụng các thông tin một cách có
hiệu quả và việc lưu trữ các thông tin dư thừa sẽ ngày càng cao. Tuy nhiên,
với dữ liệu ngày càng lớn thì độ phức tạp của các bài toán phần mềm ngày
càng lớn và xuất hiện tư tưởng có chăng một giải thuật học có thể làm việc
với lĩnh vực đã cho được biểu diễn bởi một tập dữ liệu huấn luyện và khai
thác nó bất cứ khi nào tri thức được mở rộng. Lĩnh vực khoa học máy tính
miêu tả lớp các giải thuật này được gọi là học máy (Machine Learning).
Lịch sử của các kỹ thuật học máy bắt đầu từ giữa thập kỷ 1950 khi
Frank Rosenblatt, một nhà tâm lý học, đưa ra Perceptron. Ý tưởng đã được
công khai trên giấy vào tháng 2 năm 1958. Khoảng cùng thời gian, Widrow
^ ]
Luận văn Thạc sỹ
29
Support Vector Machine
và Hoff phát triển một thủ tục học có kiểm soát, bình phương trung bình nhỏ
nhất. Widrow cũng đã phát triển một thành phần nơron tương tự như
Perceptron là Adaptive Linear Neuron. Sự kiện quan trọng tiếp theo trong
lịch sử các mạng nơron là công việc của Novikoff trên tỷ lệ hội tụ của các
nơron nhân tạo. Một thế hệ hiện đại của các hệ thống học máy đã được phát
triển sau một học thuyết đã phát triển gần đây bởi một nhà toán học từ Liên
xô cũ, Vladimir N. Vapnik. Sự thành công của mô hình mới cũng được thúc
đẩy bởi tính linh hoạt đưa hàm số tương tự mẫu định nghĩa trước của người
dùng vào, nó có thể đưa ưu điểm của tính rải rác của giải pháp các vấn đề dựa
trên các tập dữ liệu lớn, nó có thể điều khiển các không gian đặc trưng lớn, nó
xác định một hàm suy xét uyển chuyển (hoặc tính gần đúng) và vấn đề số hoá
hợp lý. Lý thuyết học thống kê đã đưa ra một động lực to lớn với học máy.
Lớp các vấn đề mà chúng ta xem xét là các vấn đề phân loại nhị phân, phân
loại đa lớp đa nhãn. Trong tài liệu này tác giả đã tìm hiểu một số tài liệu dựa
trên một vài phương pháp xây dựng các hàm số kernel trên dữ liệu có cấu
trúc.
Các thuật toán học máy chủ yếu tập trung vào 2 vấn đề đó là phân lớp
và phân đoạn dữ liệu và được chia làm 2 nhóm chính :
a. Học có giám sát (supervised learning): Là phương pháp từ một bộ dữ liệu
huấn luyện, bộ dữ liệu đã biết kết quả phân nhóm.
b. Học không có giám sát (unsupervised learning) : cũng tương tự như học có
giám sát, sự khác biệt là không có bộ dữ liệu huấn luyện, và thường là không
biết trước số lớp.
Lĩnh vực học máy gần đây đã được nghiên cứu qua việc sử dụng một
tài liệu học thuyết thống kê đã thu được một sự quan tâm đáng kể. Học thuyết
học thống kê (V.N. Vapnik, 1979) bắt đầu phát triển năm 1960 khi được đưa
^ ]
Luận văn Thạc sỹ
30
Support Vector Machine
ra rằng các phương pháp cổ điển cho các bài toán ước lượng hàm số chiều
thấp không có khả năng theo tính phức tạp của các trường hợp đa chiều cao.
Phần tiếp theo tác giả trình bày sơ qua về lý thuyết học thống kê.
2.1.2. Lý thuyết học thống kê
Hình 2.1. Mô hình hoá các lỗi
Mục tiêu trong mô hình hoá là để chọn một mô hình từ không gian giả
thiết, mà là gần nhất (với độ đo một vài lỗi) với hàm cơ sở trong không gian
đích. Các lỗi trong quá trình này xảy ra từ 2 trường hợp:
Approximation Error- Lỗi xấp xỉ: là một kết quả không gian giả thuyết nhỏ
hơn không gian đích, và do đó hàm cơ sở có thể nằm ngoài không gian giả
thuyết. Một sự lựa chọn không tốt mô hình không gian sẽ dẫn tới một lỗi xấp
xỉ lớn và được quy tới trong mô hình lỗi.
Estimation Error - Lỗi ước lượng là lỗi bởi thủ tục học với các kết quả trọng
một sự lựa chọn ký thuật mô hình không tối ưu từ không gian giả thuyết.
Các lỗi đó gắn với nhau tạo ra lỗi tổng quát hoá. Tóm lại chúng ta sẽ
tìm hàm f, tối thiểu hoá lỗi:
^ ]
Luận văn Thạc sỹ
31
Support Vector Machine
[ ] ( )( ) ( )dxdyyxPxfyLfR
YX
,,∫ ×= (2.1)
Tuy nhiên, P(x, y) không được biết. Nó có thể tìm thấy một xấp xỉ theo
nguyên tắc tối thiểu hoá lỗi theo kinh nghiệm (ERM)
[ ] ( )( )∑
=
=
l
i
ii
emp xfyLl
fR
1
,1 (2.2)
với các tối thiểu hoá lỗi theo kinh nghiệm
( ) [ ]fRxf empHfln n∈= minargˆ , (2.3)
Sự tối thiểu hoá lỗi theo kinh nghiệm tạo khả năng chỉ nếu,
[ ] [ ]fRfRempl =∞→lim (2.4)
Là đúng từ luật của các số lớn. Tuy nhiên, nó cũng phải thoả mãn,
[ ] [ ]fRfR
nn Hf
empHfl ∈∈∞∈ = minminlim (2.5)
mà chỉ có giá trị khi Hn là đủ ‘nhỏ’. Điều kiện này có cảm giác kém hơn và
yêu cầu các số tối thiểu cũng hội tụ. Giới hạn sau chứa với xác suất 1 - δ,
[ ] [ ]
l
h
lh
RfR emp
⎟⎠
⎞⎜⎝
⎛−⎟⎠
⎞⎜⎝
⎛ +
+≤ 4
ln12ln δ
(2.6)
Đặc biệt, biểu thức này với rủi ro mong muốn độc lập với khả năng
phân bổ lỗi
VC dimension - Chiều VC
VC dimension là một giá trị vô hướng mà đo các khả năng của một tập
các hàm.
^ ]
Luận văn Thạc sỹ
32
Support Vector Machine
Hình 2.2. Mô tả VC Dimension
Định nghĩa (Vapnik–Chervonenkis). VC dimension của một tập các hàm là p
nếu và chỉ nếu có tồn tại một tập các điểm {xi}pi=1 mà các điểm đó có thể
được phân biệt trong tất cả 2p cấu hình có thể, và không có tập {xi}qi=1 tồn tại
với q > p thoả mãn thuộc tính này.
Hình 2.2 miêu tả làm thể nào 3 điểm đó trong mặt phẳng có thể được
đảo lộn bởi một tập các hàm chỉ thị tuyến tính trong khi 4 điểm thì không.
Trong trường hợp này VC dimension bằng với số các tham số free (tự do),
nhưng nhìn chung đó không là tính huống, ví dụ hàm Asin(bx) có một VC
dimension vô hạn. Tập các hàm chỉ thị tuyến tính trong không gian n chiều
có một VC dimension bằng n + 1.
Một định nghĩa tương đương của VC dimension là độ lớn của tập huấn
luyện lớn nhất mà có thể được tìm thấy mà lớp hàm có thể làm phá huỷ tập
huấn luyện.
Xem xét các siêu phẳng sau trong Rd sau:
Định lý: cho trước một tập n> 1 điểm trong Rd. Chọn một trong các điểm đó
làm gốc, sau đó n điểm có thể bị phá vỡ bởi các các siêu phẳng có hướng nếu
và chỉ nếu các vector vị trí của các các điểm còn lại là độc lập tuyến tính.
Trong một kết quả trực tiếp của kết quả này, dễ thấy là VC dimension
của tập các siêu phẳng có hướng trong Rd là d + 1.
^ ]
Luận văn Thạc sỹ
33
Support Vector Machine
2.2. Nguyên lý tối thiểu hoá rủi ro cấu trúc
Khái niệm VC dimension thúc đẩy một phương pháp mới về suy luận
quy nạp. Cung cấp các giả thiết lớp S với một cấu trúc bằng cách định nghĩa
trong các lớp con liên tiếp
S1 ⊂ S2 ⊂ ... ⊂ Sn với Sk = {fα(z): α ∈Ωk}
là chiều VC hk của mỗi lớp con Sk là hữu hạn và thoả mãn h1 ≤ h2 ≤ …≤ hp
(tăng độ phức tạp qua cấu trúc). Kết quả VC chính độc lập với sự phân bố
nguồn là giới hạn:
⎟⎟⎠
⎞
⎜⎜⎝
⎛ −+=
nd
nRR
k
n
empn
ηφαα log,)()( 1) (2.7)
đúng với xác suất ít nhất (1- η)
Nguyên tắc hướng dẫn giải thuật này được gọi là tối thiểu hoá rủi ro
cấu trúc (Structural Risk Minimization (SRM))..
Bởi vậy, để thu được giới hạn nhỏ nhất trên lỗi thử nghiệm là tối thiểu
hoá số các lỗi huấn luyện, tập hàm với chiều VC nhỏ nhất có thể được sử
dụng. Hai yêu cầu là mâu thuẫn vì theo thứ tự tối thiểu hoá số lỗi huấn luyện
một hàm phân loại có thể được lấy ra từ một tập lớn các hàm số, hơn là một
tập ít với chiều VC nhỏ. Giải pháp đảm bảo nhất được tìm thấy với một sự
thoả hiệp giữa độ chính xác của tính gần đúng trên dữ liệu theo kinh nghiệm
và khả năng của máy được sử dụng tối thiểu hoá số lỗi (Hình 2.3).
Khái niệm khả năng là một cái gì đó liên quan việc quyết định các điều
kiện cần và đủ cho tính nhất quán của các bài toán học và tỷ trọng hội tụ của
các bài toán học. Một thành tựu quan trọng của học thuyết này là sự khai phá
khả năng tổng quát hoá của máy học phụ thuộc vào khả năng của tập các hàm
thực hiện bởi máy học, khác với số các tham số tự do.
Với số lượng dữ liệu huấn luyện, một giải pháp hiệu quả của các bài
toán học dựa trên độ lớn mẫu nhỏ, một giải pháp tốt là để giải quyết trực tiếp
^ ]
Luận văn Thạc sỹ
34
Support Vector Machine
bài toán, tránh giải quyết một vấn đề chung hơn như một bước trung gian. Có
thể là thông tin hiện có là đủ cho một giải pháp trực tiếp nhưng là đủ để giải
quyết một vấn đề trung gian chung hơn.
Hình 2.3. Mô tả của phương trình 2.7.
Hàm số giảm biểu diễn lỗi huấn luyện (rủi ro theo kinh nghiệm), trong
khi hàm tăng là giới hạn trên trên độ phức tạp (phụ thuộc vào lỗi đúng). Với
một độ phức tạp cho trước của lớp hàm, sự tin cậy của rủi ro mong muốn có
thể được quyết định. Mục tiêu là để tìm một trao đổi tối ưu giữa lỗi theo kinh
nghiệm và độ phức tạp, chọn từ các tập S1,…, Sn, hàm số học với VC
dimension tối ưu h*, với độ phức tạp tối ưu.
Ứng dụng của các khái niệm đó tìm không gian để phát triển trong các
chiêu bài khác nhau của các bài toán học. Học có kiểm soát, ví dụ, là bài toán
của việc học một hàm đã cho một vài dữ liệu và trợ giúp một nguồn các kết
quả mẫu. Trong mô hình học không kiểm soát chỉ không gian nguồn χ là cho
trước, không gian ra Y là chưa có. Các ứng dụng khác là ước lượng các hàm
số giá trị thức, xấp xỉ hàm, ước lượng hồi quy và xử lý tín hiệu.
Học thuyết trên là cần thiết để đưa ra một nền móng thô cho việc đặc
tính hoá phương pháp hoạt động hiện đại để giải quyết các bài toán học máy.
^ ]
Luận văn Thạc sỹ
35
Support Vector Machine
2.3. Máy học vector hỗ trợ - SVM
Cách tiếp cận thường này dùng để tối thiểu hoá giới hạn rủi ro là chọn
một lớp giả thiết cố định. Việc này cố định chiều VC và do đó khoảng cách
tin cậy được đo bởi Φ() toán hạng trong phương trình 2.7 của giới hạn. Khi đó
sự tối thiểu hoá của rủi ro theo kinh nghiệm (lỗi huấn luyện) dẫn tới một giới
hạn trên bên trên rủi ro mong muốn.
Phương pháp này nảy sinh một khó khăn khi lớp được chọn quá phức
tạp (chiều VC quá lớn). Trong trường hợp này khoảng cách tin cậy sẽ lớn và
giới hạn trên quá lỏng. Ngược lại, nếu lớp được chọn là quá đơn giản (chiều
VCquá thấp) rủi ro theo kinh nghiệm sẽ lớn và giới hạn sẽ tồi tệ nữa.
Một giải pháp để thiết kế lại màu cho mỗi độ lớn khác nhau của dữ liệu
huấn luyện và có lựa chọn một độ phức tạp đúng một tiên nghiệm (a priori)
để khắc phục các hạn chế trên. Một kỹ thuật khác sẽ là cố định rủi ro theo
kinh nghiệm nhỏ (hoặc bằng 0) và sau đó tích cực tối thiểu hoá khoảng cách
tin cậy của giới hạn (phương trình 2.7). Việc này yêu cầu một máy học trong
đó kiểm soát độ phức tạp được xây dựng bên trong Support Vector Machines,
(SVM) là một ví dụ của giải thuật học mà thực hiện theo cách tiếp cận này.
Giải pháp của một bài toán phân loại có thể được diễn đạt với một siêu phẳng:
f(x) = m • x + b
với m là một vector tham số và dấu f(x) là giá trị dự đoán cho từng x cho
trước. Một siêu phẳng có thể được diễn đạt cũng với một sự kết hợp tuyến
tính các mẫu. Thực tế, cho L = {(x1,y1),…, (xn,yn)} là một tập các mẫu phức
tạp và các giá trị đích liên quan, thì:
⎥⎦
⎤⎢⎣
⎡ += ∑
=
n
i
iii bxxKysignxf
1
),()( α
^ ]
Luận văn Thạc sỹ
36
Support Vector Machine
là một bộ phân loại ánh xạ tạm có trọng số. Hàm K: Rd × Rd → R định nghĩa
một độ đo khoảng cách giữa hai thành phần bất kỳ của không gian nguồn.
Khoảng cách suy ra bởi hàm kernel có thể được viết như sau:
d(x,y) = K(x,x) – 2K(x,y) +K(x,y)
Vector xi là các mẫu được sử dụng để ánh xạ các trường hợp tương lai
và αi là các hệ số điều khiển đánh trọng số giữa các mẫu. Chúng tôi giả sử
hầu hết tất cả các hệ số sẽ là 0. các hệ số khác 0 xác định mẫu nào là quan
trọng. Các mẫu đó được gọi là các vector hỗ trợ (support vectors).
Một cách hiểu nguyên tắc phân loại (classification rule) mà SVM thực
hiện là: đầu tiên biến đổi các điểm dữ liệu tới một không gian đặc trưng đa
chiều trong đó không gian đầu vào được sắp xếp với một ánh xạ không tuyến
tính. Khi đó, một sự phân tách của dữ liệu ánh xạ với một siêu phẳng là có
thể. Do vậy, chúng ta có thể quyết định quyết định nào là tối ưu để đưa vào,
theo SRM bằng các xem xét tình huống siêu phẳng.
Mặt khác, chiều VC của tập các siêu phẳng với các vector trọng số giới
hạn ||m||2 ≤ A là số tối thiểu của d + 1 và [C2A2] +1 với C là bán kính của
đường tròn nhỏ nhất giới hạn dữ liệu huấn luyện. Bởi vậy siêu phẳng tối ưu là
một siêu phẳng phân tách dữ liệu và có chiều VC nhỏ nhất, như là vector
trọng số nhỏ nhất.
Bằng cách chỉ chọn theo các siêu phẳng mà phân tách dữ liệu (như vậy,
với một Remp(α) = 0 cố định), chúng ta thu thập một sự thực hiện kiểu suy
luận rủi ro có cấu trúc. Khi các hạn chế này được biến đổi ngược lại vào trong
không gian nguồn của các điểm dữ liệu, nó xuất hiện các giá trị tối ưu của m
và b được đưa ra bởi giải pháp của một bài toán tối ưu toàn phương lồi.
^ ]
Luận văn Thạc sỹ
37
Support Vector Machine
2.3.1. SVM với các vấn đề tuyến tính
Một SVM là một siêu phẳng phân tách các mẫu âm với các mẫu dương
với một khoảng cách giữa các lớp tối đa được gọi là lề giới hạn (margin)
(Hình 2.4)
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
Bài toán có thể được chuyển thành một bài toán tối ưu. Như chúng tôi
đã dự đoán trước, siêu phẳng SVM có để được biểu diễn:
f(x) = m • x + b
do đó:
f(xi) ≥ 1 với yi = +1
f(xi) ≤ 1 với yi = -1
khi:
yif(xi) ≥ 1 ∀i ∈ 1,..,n (2.8)
và lề (margin) của nó phải là lớn nhất. Có thể chỉ ra rằng lề là 2/||m||. Bởi vậy,
bằng cách tối thiểu hoá số lượng ½(m . m) đã đảm bảo tính tối ưu của siêu
phẳng đáp án. Bởi vậy, bài toán kết quả là:
2
2
1min mP m≡
^ ]
Luận văn Thạc sỹ
38
Support Vector Machine
đối với: yi(m • xi +b) ≥ 1 ∀i ∈ 1,..,n
với: m ∈ Rd, b ∈ R
Nếu chúng ta chuyển thành công thức Lagrangian:
))'(1(
2
1max
1
2 bxmymL ii
n
i
i +−+= ∑
=
αα (2.9)
với αi ≥ 0, i ∈ 1,..,n
Bài toán bội (dual problem) có thể được chuyển hoá áp dụng các điều
kiện tối ưu hoá Karush-Kuhn-Tucker trên công thức Lagrangian (công thức
2.9):
∑∑ =⇒=−=∂∂ i iiiiii i xymxymm
L αα 0 (2.10)
0==∂
∂ ∑
i
ii yb
L α (2.11)
Thay thế 2.9, 2.10 vào 2.11, thu được:
jijii
ji
i
i
i xxyyL ααα ∑∑ −=
,2
1
và bài toán bội là:
jijjiji ii i
xxyy αααα ∑∑ − ,21max
{ }ni
y
i
ii i
,...,1,0
0
∈≥
=∑
α
α
(2.12)
Chú ý rằng dữ liệu huấn luyện xuất hiện chỉ trong kiểu các tính trong
giữa các vector. Đặc tính này sẽ chứng minh là hữu ích khi SVM được áp
dụng tới các tập huấn luyện phân tách không tuyến tính. Cho α* là giải pháp
^ ]
Luận văn Thạc sỹ
39
Support Vector Machine
tối ưu của 2.11. Giá trị tối ưu của b có thể cuối cùng xem xét αi* >0 và các
điều kiện KKT thêm vào:
0))'(1(* =+− bxmy iiiα (2.13)
Giải pháp siêu phẳng được quyết định bởi các điểm xi huấn luyện nằm
trên các siêu phẳng song song đặt tại một khoảng cách bằng với lề
*),()(
1
* bxxKyxf ii
nSV
i
i += ∑
=
α (2.14)
Các điểm đó được gọi là các vector hỗ trợ (support vectors).
2.3.2. Trường hợp phân tách không tuyến tính
Giải thuật trên, nếu áp dụng tới một tập huấn luyện phân tách không
tuyến tính, sẽ không tìm được bất kỳ giải pháp nào hợp lý. Bởi vậy cần mở
rộng mô hình tới trường hợp không thể phân tách, các ràng buộc có thể được
thả lỏng (công thức 2.8) nhưng chỉ khi cần. Việc này có thể được thực hiện
bằng đưa vào các biến dương không chặt ξi với ∀i ∈ {1,..,n} với các ràng
buộc:
f(xi) ≥ 1- ξi với yi = +1
f(xi) ≤ 1+ ξi với yi = -1
với ξi ≥ 0 ∀i
Bởi vậy, với một lỗi xảy ra, ξi tương ứng phải vượt quá 1 đơn vị
(unity), bởi vậy ∑iξi là một giới hạn trên số các lỗi huấn luyện. Bởi vậy một
cách tự nhiên để gán một giá trị thêm với các lỗi là để thay đổi hàm mục tiệu
được tối thiểu hoá từ:
2
2
1 m thành ∑+
i
iCm ξ22
1
^ ]
Luận văn Thạc sỹ
40
Support Vector Machine
với C là một tham số được chọn bởi người dùng; một C lớn tương ứng để gán
một bất lợi lớn tới lỗi, trong khi một C nhỏ có nghĩa là các lỗi ít hơn. Có thể
chỉ ra rằng bài toán bội tương ứng là:
jijijji ii i
xxyyL ⋅−= ∑∑ αααα ,21max (2.15)
đối với (2.16)
∀i∈ 1,..., n 0 ≤ αi ≤ C
ii i y∑α
Nếu giải pháp của vấn đề này là không đủ để đạt được một sự thực hiện
tổng quát hoá tốt (lớp các siêu phẳng là quá kém để phân tách các mẫu huấn
luyện), thì có một phương pháp mà có thể được sử dụng để thiết lập một sự
tổng quát hoá tốt theo một cách đơn giản. Đầu tiên chú ý rằng chỉ có cách
trong đó các mẫu huấn luyện xuất hiện trong bài toán học (2.15) là theo kiểu
của các tích trong xi⋅xj. Bây giờ, giả sử đầu tiên chúng ta ánh xạ dữ liệu tới
một vài không gian Euclit khác (có thể số chiều vô hạn), sử dụng một ánh xạ
mà chúng ta gọi φ:
φ: Rd → H
Khi đó giải thuật huấn luyện có thể được áp dụng vào trong H sử dụng
các hàm từ φ(xi)⋅φ(xj). Khi bài toán được diễn đạt chỉ trong các toán hạng của
các tích trong như là các giải pháp tốt. Một vấn đề với các mẫu trong một
không gian đặc trưng H khác có thể được giải quyết xác định một tích trong
thực hiện trong H. Một tích trong có thể cũng được gọi là một hàm nhân
kernel function. Bởi vậy, để giải quyết một bài toán SVM định nghĩa rõ ràng
ánh xạ φ là không cần thiết.
^ ]
Luận văn Thạc sỹ
41
Support Vector Machine
2.4. Một số phương pháp Kernel
Trong những năm gần đây, một vài máy học kernel, như Kernel
Principal Component Analysis, Kernel Fisher Discriminant và Support Vector
Machines đã được đưa ra. Các cách tiếp cận đó đã nhận được một sự quan
tâm đặc biệt vì chúng được dùng với các vấn đề phân loại và hồi quy, và, gần
đây, khả năng của chúng được khai thác với các vấn đề học không kiểm soát.
Chúng tôi sẽ đưa ra các khái niệm cơ bản của học thuyết học và giới thiệu ý
tưởng về không gian đặc trưng cơ bản (kernel feature space) áp dụng tới vấn
đề học có kiểm soát. Trong phần dưới nhắc lại với một vấn đề ánh xạ không
tuyến tính:
φ: Rd → F
x a φ (x)
dữ liệu x1,…, xn ∈ Rd được ánh xạ vào trong một không gian đặc trưng F với
một số chiều có khả năng nhiều hơn. Cho trước một ví dụ của một bài toán
học, nó có thể chuyển nó vào không không gian F thay vì Rd, ví dụ,
(φ(x1), y1),..., (φ(xn), yn) ∈ F × Y
sự biểu diễn ánh xạ này có thể được sử dụng để tìm dễ dàng một phân loại của
dữ liệu.
Tính đa chiều là làm tăng sự khó khăn trong bài toán đánh giá với số
chiều d của không gian, theo nguyên tắc, sẽ tăng theo hàm mũ với số mẫu của
các đặc tính của không gian. Việc này bao gồm một bài toán trên việc ánh xạ
bài toán tới một không gian đặc trưng đa chiều cao cho các mục đích học.
Tuy nhiên, học thuyết học thống kê đã chỉ ra rằng học trong F có thể đơn giản
hơn nếu sử dụng độ phức tạp thấp hơn (như bộ phân loại tuyến tính), được
phát biểu rằng, với các mục đích học, nó liên quan hơn với độ phức tạp của
^ ]
Luận văn Thạc sỹ
42
Support Vector Machine
lớp hàm số mà tăng số chiều của không gian đặc trưng. Xem xét một tình
huống 2 chiều khi các mặt quyết định không tuyến tính cần để phân tách các
lớp, trong một không gian đặc trưng của đơn thức thứ hai:
φ: R2 → R3
(x1, x2) a (z1, z2, z3) : = (x 21 , 2 x1x2, x 22 ).
Do đó, trong R3, một siêu phẳng tuyến tính có thể phân tách chính xác
các tình huống, xem Hình 2.5 về minh hoạ của ý tưởng này.
Ở đây việc tính toán một tích trong vô hướng giữa 2 vector không gian
đặc trưng có thể công thức ho._. tham số đã
được định nghĩa trước trong lexer. Các tham số gồm các định nghĩa về các ký
^ ]
Luận văn Thạc sỹ
77
Support Vector Machine
từ mà phân tách các tokens như dấu cách, và để chuyển đổi văn bản tới chữ
hoa hoặc để đó trong chế độ hỗn hợp.
Indexing Engine – Đánh chỉ số
Indexing engine tạo một index đảo mà ánh xạ các chuỗi vào tài liệu mà
chứa chúng. Trong truờng hợp này Oracle Text sử dụng từ dừng (stoplist) đã
xác định để loại từ các từ dừng khỏi index. Oracle Text cũng sử dụng các
tham số xác định trước trong danh sách các WORDLIST, dùng để hệ thống
biết làm thế nào để tạo một index tiền tố hoặc index chuỗi con, nếu có thể.
4.2.2.4. Thiết lập tham số huấn luyện với SVM trong Oracle
SVM_CLASSIFIER là một đối tượng mới cho bộ phân loại thực hiện
phân loại SVM. Với các bộ phân loại hiện nay, RULE_CLASSIFIER, xây
dựng các cât quyết định và người dung đưa vào bảng nguyên tắc các câu truy
vấn có thể kiểm soát được. SVM_CLASSIFIER thì thực hiện một mô hình
thống kê phức tạp với các nguyên tắc mà người dùng không thể đọc được.
Tuy nhiên phương pháp sử dụng SVM_CLASSIFIER cũng gần giống với
RULE_CLASSIFIER.
Để sử dụng SVM_CLASSIFIER, đầu tiên tạo một tham chiếu tới bộ phân loại
EXEC ctx_ddl.create_preference('mysvm',’SVM_CLASSIFIER ');
Người dùng có thể thiết lập các thuộc tính để làm thay đổi việc huấn luyện,
các tham số dùng với SVM_CLASSIFIER chúng tôi sẽ liệt kê phía dưới.
Tiếp theo, chúng ta thực hiện huấn luyện với một API huấn luyện đơn giản:
PROCEDURE Train (
index_name in varchar2, -- tên của chỉ số đã tạo trong bước 3
docid in varchar2, -- tên của cột docID
cattab in varchar2, -- tên của bảng phân loại sẵn tạo trong bước 2
catdocid in varchar2, -- tên cột docID trong bảng phân loại
^ ]
Luận văn Thạc sỹ
78
Support Vector Machine
catid in varchar2, -- tên của cột mã phân loại trong bảng phân loại
restab in varchar2, -- tên bảng kết quả
preference in varchar2 -- tên tham chiếu tới bộ phân loại tạo ở bước
trên );
Ví dụ:
EXEC ctx_cls.train
('myindex', 'did', 'cat_tab', 'did', 'cid', 'svmtab', 'mysvm');
Giống như bộ phân loại RULE, bộ phân loại SVM tạo ra một bảng các
nguyên tắc. Tuy nhiêu cấu trúc của bảng nguyên tắc khác với bộ phân loại:
create table svmtab (cat_id number, type number, rule blob);
Mặc dù các nguyên tắc là BLOB không kiểm soát được, người dùng
vẫn có thể tạo một chỉ số CTXRULE trên bảng nguyên tắc để phân chia các
tài liệu. Tuy nhiên người dùng phải cung cấp các tham chiếu tới bộ phân loại
trong kh tạo chỉ số CTXRULE:
CREATE INDEX svmx on svmtab(rule)
indextype is ctxsys.ctxrule parameters ('classifier mysvm');
Tên thuộc tính Kiểu
dữ liệu
Giá trị
mặc
định
Giá trị
thấp
nhất
Giá trị
cao
nhất
Ghi chú
MAX_DOCTERMS Integer 50 10 8192 Xác định số tối đa
các từ biểu diễn
một tài liệu
MAX_FEATURES Integer 3,000 1 100,000 Xác định tối đá số
các đặc trưng
THEME_ON Boolean FALSE NULL NULL TRUE: để sử dụng
thêm như các đặc
^ ]
Luận văn Thạc sỹ
79
Support Vector Machine
trưng. Phân loại
với các themes yêu
cầu đã có trong
một cơ sở tri thức.
Một cơ sở tri thức
có thể có thế được
cài đặt hoặc chưa
với Oracle Text.
TOKEN_ON Boolean TRUE NULL NULL TRUE: sử dụng các
token lặp như các
đặc trưng
STEM_ON Boolean FALSE NULL NULL TRUE: sử dụng các
token lấy gốc như
các đặc trưng. Chỉ
làm việc khi tuning
INDEX_STEM
trên lexer.
MEMORY_SIZE Integer 500 10 4000 Xác định độ lớn bộ
nhớ tương đối (tính
theo MB).
SECTION_WEIGHT Integer 2 0 100 Xác định các bộ
nhân xuất hiện để
thêm một thuật ngữ
vào một trường
như một thuật ngữ
thông thường.
Bảng 4.1. Bảng các thuộc tính của SVM_CLASSIFIER
^ ]
Luận văn Thạc sỹ
80
Support Vector Machine
4.2.3. Phương pháp đánh giá
Các giải thuật cần được kiểm thử để đánh giá độ chính xác về sự dự đoán
của chúng; khi kiểm thử chúng ta sử dụng dụng dữ liệu với các kết quả đã biết
trước và so sánh với các giá trị được dự đoán của giải thuật. Các kết quả kiểm
thử được tính toán theo các độ đo. Các ứng dụng của Oracle thường kiểm tra
kết quả phân loại với các độ đo:
- Confusion matrix (Ma trận giá trị)
- Lift (bậc thang)
Trong thử nghiệm này tác giả sử dụng độ đo Confusion matrix.
Một mô hình thu được qua quá trình khai phá dữ liệu sử dụng các kỹ thuật
học – suy luận khác nhau có thể được đánh giá sử dụng các tham số chuẩn
như một độ đo hiệu suất thực hiện của nó. Giá trị này biểu thị một giá trị gần
đúng của tỷ lệ lỗi đúng, một tham số được định nghĩa trong lý thuyết học
thống kê. Tỷ lệ lỗi được tính sử dụng một tập dữ liệu kiểm thử thu được qua
một trong các kỹ thuật lấy mẫu lại được áp dụng. Hơn nữa để đo tính chính
xác theo tỷ lệ lỗi, các mô hình khai phá dữ liệu có thể được so sánh với tốc
độ, độ tinh chỉnh dữ liệu, tính co giãn, và tính biểu thị và tất cả các thám số đó
có thể có một ảnh hưởng tới sự thẩm định và xác thực của mô hình. Trong
luận văn này, tác giả sử dụng tham số tỷ lệ lỗi với bài toán phân loại dữ liệu;
tương tự như các cách tiếp cận và phân phân tích có thể cho với các bài toán
khai phá dữ liệu khác. Sự tính toán tỷ lệ lỗi dựa trên việc đếm số lỗi trong quá
trình kiểm thử. Các lỗi với bài toán phân loại, đơn giản định nghĩa trên sự
phân loại sai. Nếu tât cả các lỗi đều quan trọng như nhau, một tỷ lệ lỗi R là số
lỗi E chia số số mẫu S trong tập kiểm tra.
R = E / S
^ ]
Luận văn Thạc sỹ
81
Support Vector Machine
Độ chính xác A của một một mô hình là một phần của tập dữ liệu kiểm
được phân loại chính xác và được tính như sau:
A= 1- R = (S - E) / S
Với các bài toán phân loại chuẩn, có thể có m2 –m kiểu lỗi, với m là số
phân loại. nếu phân loại 2 lớp, có thể có 2 kiểu lỗi
1. Nếu giá trị thực là T, nhưng phân loại là F: có các lỗi âm và
2. Nếu giá trị thực là F, nhưng được phân loại là T: có các lỗi dương
Nếu có hơn 2 lớp, các kiểu lỗi có thể được tổng hợp trong một ma trận các giá
trị (confusion matrix). Với số phân loại là m=3, có 6 kiểu lỗi (m2 − m = 32 − 3
= 6)
Confusion Matrix
Confusion Matrix cung cấp tính chính xác mô hình và các loại lỗi của
mô hình khi ghi điểm dữ liệu. Đó là kết quả của nhiệm vụ kiểm thử với mô
hình phân lớp. Các chỉ số hàng ứng với giá trị thực sự và được dùng xây dựng
mô hình, chỉ số cột tương ứng với các giá trị dự đoán được áp dụng mô hình.
Dự đoán
Thực Mua Không mua
Mua 516 25
Không mua 10 725
Ma trận trên thể hiện mô hình dự đoán đúng 516 khách hàng mua và
725 khách hàng không mua. Mô hình dự đoán sai 10 người mua - thực sự
không mua, sai 25 người không mua thực sự có mua. Tỷ lệ dự đoán đúng là
1241/1276; sai là 35/1276.
^ ]
Luận văn Thạc sỹ
82
Support Vector Machine
CHƯƠNG 5. TIẾN HÀNH THỬ NGHIỆM
5.1. Chuẩn bị dữ liệu
Bộ dữ liệu Reuters-21578 được hoàn thiện bởi David Lewis và được
lựa chọn bắt nguồn từ tập đoàn Carnegie từ mạng lưới Reuter năm 1997.
Chúng tôi sử dụng các phân chia Apte, gồm 9603 tài liệu huấn luyện và 3299
tài liệu kiểm thử. Có thể có 135 phân loại, nhưng chỉ 90 trong số chúng là
xuất hiện trong cả tập huấn luyện và tài liệu test. Bộ dữ liệu này có bộ từ vựng
hạn chế: tập huấn luyện chỉ chứa 27658 thuật ngữ tách biệt. Bài toán phân
loại là gán các bài báo tới tâp các chủ đề. Với nhiều phân loại có sự tương
ứng trực tiếp giữa các từ và bản thân chúng.
Trong phần thử nghiệm này, tôi đã sử dụng kiểm thử dữ liệu với 5 phân
loại có số lượng tài liệu huấn luyện và kiểm thử lớn nhất.
Phân loại Số tài liệu
huấn luyện
Số tài liệu
kiểm thử
Earn 2877 1087
Acq 1650 719
money_fx 538 179
Grain 433 149
Crude 389 189
Bảng 5.1. Bảng dữ liệu thử nghiệm đã phân loại
Ban đầu dữ liệu nằm ngoài các file văn bản lưu trữ ở các thư mục
của hệ điều hành, tác giả đã xây dựng một thủ tục để đưa các dữ liệu này
vào trong CSDL Oracle. Dữ liệu của 5 phân loại lớn nhất này được lưu
trong các bảng:
^ ]
Luận văn Thạc sỹ
83
Support Vector Machine
Training_Top5: lưu dữ liệu huấn luyện
Test_Top5: lưu dữ liệu kiểm thử đã được phân loại sẵn để có thể đo độ
chính xác của tài liệu
5.2. Kiểm thử với Oracle 10g
Như trên đã đề cập, kết quả phân loại văn bản Oracle chỉ có thể thay đổi
bằng 2 cách: chuẩn bị dữ liệu và thay đổi các tham số huấn luyện văn bản;
trong các tham số huấn luyện với thuật toán SVM trong Oracle Text, để thay
đổi kernel function, sử dụng thuộc tính MAX_FEATURE đối với kiểu huấn
luyện là SVM_PREFERENCES:
- Nếu MAX_FEATURE <=100: hàm tuyến tính
- Nếu MAX_FEATURE >100: hàm Gaussian
Việc thiết lập cấu hình này là tối ưu, do Oracle đã tính toán tối ưu để tìm ra
siêu phẳng phù hợp. Trong luận văn này tác giả thực nghiệm với 3 lần với
cùng một bộ dữ liệu nhưng với các tham số khác nhau:
- Lần 1: MAX_FEATURES=100, sử dụng danh sách từ dừng mặc định
của Oracle gồm 114 từ dừng
- Lần 2: tăng số đặc trưng MAX_FEATURES=1000 và giữ nguyên
danh sách từ dừng như lần 1
- Lần 3: giữ nguyên số đặc trưng như lần 2, MAX_FEATURES=1000 và
sử dụng một danh sách từ dừng với số từ dừng là 509 từ dừng tiếng
Anh
5.2.1. Thử nghiệm lần 1
Các bước thực hiện trong lần thử nghiệm 1 với MAX_FEATURE=100
Bước 1: Tạo bảng huấn luyên và đưa dữ liệu vào bảng:
CREATE TABLE Training_5 (
^ ]
Luận văn Thạc sỹ
84
Support Vector Machine
ID NUMBER Primary key,
Doc_Text CLOB);
INSERT INTO Training_5 (ID, Doc_Text)
SELECT TO_NUMBER(a.Doc_ID), a.Docs
FROM Training_Top5 a
WHERE ID=
(SELECT ID FROM Training_Top5 b
WHERE b.Doc_ID = a.Doc_ID and rownum=1);
kết quả có 5837 dòng trong bảng Training_5
Bước 2: Tạo bảng và đưa dữ liệu huấn luyện đã được phân loại sẵn
CREATE TABLE Category_Training (
Doc_ID NUMBER,
Cat_ID NUMBER,
Cat_Name VARCHAR2(100),
PRIMARY KEY (Cat_id, Doc_ID));
INSERT INTO Category_Training (Doc_ID , Cat_ID, Cat_Name)
SELECT TO_NUMBER(Doc_ID),Cat_ID, Cat_Came
FROM Training_Top5;
kết quả có 5887 dòng dữ liệu trong bảng Category_Training
Bước 3: Tạo chỉ số CONTEXT trên bảng huấn luyện. Oracle Text hỗ trợ
kiểu phân loại với SVM thì phải thực hiện đánh chỉ số với tham số cho chỉ
số là NONPOPULATE
CREATE INDEX Reuter_5_Index ON Training_5(Doc_Text)
INDEXTYPE IS CTXSYS.CONTEXT
PARAMETERS(‘NONPOPULATE’);
^ ]
Luận văn Thạc sỹ
85
Support Vector Machine
Bước 4: Thiết lập kiểu tham chiếu tới giải thuật SVM và thay đổi các
tham số thực hiện tương ứng. Việc thiết lập này sẽ được sử dụng trong thủ
tục huấn luyện Oracle hỗ trợ
EXEC CTX_DDL.CREATE_PREFERENCE(
‘Reuter_5_Classifier’,
'SVM_CLASSIFIER');
EXEC CTX_DDL.SET_ATTRIBUTE
('Reuter_5_Classifier',
'MAX_FEATURES','100');
Bước 5: Tạo bảng để lưu nguyên tắc (rule) của từng phân loại. Bảng này
được sinh ra trong quá trình huấn luyện.
CREATE TABLE Result_5_Table (
Cat_ID NUMBER,
Type NUMBER(3) NOT NULL,
Rule BLOB);
Bước 6: Tiến hành huấn luyện dữ liệu với các bảng đã chuẩn bị dữ liệu và
các tham số đã được thiết lập
EXEC CTX_CLS.TRAIN (
'Reuter_5_Index',
'ID',
'Category_Training',
'Doc_ID',
'Cat_ID',
'Result_5_Table',
'Reuter_5_Classifier');
Bước 7: Tạo chỉ số CTXRULE trên bảng lưu nguyên tắc phân loại được
sinh ra trong quá trình phân loại
^ ]
Luận văn Thạc sỹ
86
Support Vector Machine
EXEC CTX_DDL.CREATE_PREFERENCE(
'Reuter_5_Filter',
'NULL_FILTER');
CREATE INDEX Restabx_Docs ON Result_5_Table(Rule)
INDEXTYPE IS CTXSYS.CTXRULE
PARAMETER ('FILTER Reuter_5_Filter
CLASSIFIER Reuter_5_Classifier');
Bước 8: Thực hiện kiểm thử dữ liệu với bảng nguyên tắc đã được
sinh ra sau quá trình huấn luyện
- Tạo bảng và đưa nội dung các tài liệu không giống nhau để chuẩn
bị kiểm thử mô hình đã được huấn luyện ở trên.
CREATE TABLE Testing_5 AS
SELECT TO_NUMBER(Doc_ID) Doc_ID, Docs
FROM Test_Top5 a WHERE ID =
(SELECT ID FROM Test_Top5 b
WHERE b.Doc_ID = a.Doc_ID and rownum=1);
Kết quả trong bảng Testing_5 có 2310 tài liệu khác nhau để kiểm
thử.
- Thực hiện thử nghiệm phân loại các ứng với các nguyên tắc theo phân
loại đã được huấn luyện ở trên bằng cách sử dụng toán tử MATCHES
CREATE TABLE Test_5 AS
SELECT Result_5_Table.Cat_ID,
MATCH_SCORE(1) Score,
Testing_5.Doc_ID
FROM Result_5_Table, Testing_5
WHERE
^ ]
Luận văn Thạc sỹ
87
Support Vector Machine
MATCHES(Result_5_Rable.Rule,
Testing_5.Docs,1) > 0;
kết quả trong bảng Test_5 có 8461 dòng, với mỗi tài liệu cần phân loại có
thể có thể có trong nhiều phân loại khác nhau. Việc một tài liệu có nhiều
phân loại khác nhau như vậy là do khi tính điểm tương tự giữa các tài liệu
kiểm với các nguyên tắc phân loại, tác giả đã lấy tất cả chỉ cần có điểm lớn
0 có nghĩa là có sự tương ứng về đặc trưng.
- Để loại bớt các phân loại thừa, trong số các phân loại của một tài liệu
tác giả chỉ lấy tài liệu có điểm cao nhất
CREATE TABLE Highest_Score AS
SELECT DISTINCT a.Doc_ID, a.Cat_ID, a.Score
FROM Test_5 a,
(SELECT Doc_ID, MAX(Score) Score
FROM Test_5 GROUP BY Doc_ID ) b
WHERE a.Doc_ID = b.Doc_ID and a.Score =b.Score;
kết quả trong bảng Highest_Score có 2313 dòng và ít nhất một tài liệu
trong tập kiểm thử sẽ nằm trong 1 phân loại, trong bảng này có 3 cặp tài
liệu – phân loại (1 tài liệu thuộc 2 phân loại) có điểm bằng nhau.
5.2.2. Thử nghiệm lần 2
Các bước thực hiện trong lần thử nghiệm 2 với MAX_FEATURE
=1000 tương tự như tất cả bước trong lần kiểm thử 1 nhưng tại bước 4, ta
thiết lập tham số có mô hình phân loại
EXEC CTX_DDL.CREATE_PREFERENCE(
‘Reuter_5_Classifier’,
'SVM_CLASSIFIER');
EXEC CTX_DDL.SET_ATTRIBUTE
('Reuter_5_Classifier',
^ ]
Luận văn Thạc sỹ
88
Support Vector Machine
'MAX_FEATURES','1000');
--chỉ thực hiện thay đổi với chữ màu xanh
Kết quả dữ liệu trong các bảng:
- Các bảng Training_5, Category_Training , Testing_5 và Testing_Top5
đều giống nhau trong tất cả các lần thử nghiệm do sử dụng chung một
tập dữ liệu huấn luyện và kiểm thử.
- Bảng Test_5 có 11436 dòng, bảng Highest_Score có 2314 (có 4 cặp tài
liệu - phân loại có điểm bằng nhau)
5.2.3. Thử nghiệm lần 3
Thực hiện thử nghiệm với MAX_FEATURE =1000 và sử dụng một
bảng từ dừng tiếng Anh khác với 509 từ dừng (Phụ lục 1). Bước đầu tiên là
đưa bảng danh sách từ dừng tiếng Anh mới vào vào trong bảng từ dừng của
Oracle, sử dụng một số thủ tục dựng sẵn để dưa danh sách từ dừng vào trong
CSDL.
Các bước thực hiện tương tự các bước giống lần 2 nhưng tại bước 3, sử
dụng danh sách từ dừng trong việc đánh chỉ số cho nội dung văn bản, như
sau:
CREATE INDEX Reuter_5_Index ON Training_5(Doc_Text)
INDEXTYPE IS CTXSYS.CONTEXT
PARAMETERS(‘STOPLIST SVM.English_Stoplist1 NONPOPULATE’);
- Tiếp theo tại bước 7, chúng ta cũng thêm đối số về danh sách từ dừng
mới với bảng lưu các nguyên tắc phân loại.
CREATE INDEX Restabx_Docs ON Result_5_Table(Rule)
INDEXTYPE IS CTXSYS.CTXRULE
PARAMETER (' STOPLIST SVM.English_Stoplist1
FILTER Reuter_5_Filter
^ ]
Luận văn Thạc sỹ
89
Support Vector Machine
CLASSIFIER Reuter_5_Classifier');
- Kết quả của các bảng dữ liệu phân loại kiểm thử như sau:
Bảng Test_5 có 11438 dòng, bảng Highest_Score có 2311 (chỉ có 1
cặp tài liệu - phân loại có điểm bằng nhau)
5.2.4. Kết quả 3 lần thử nghiệm
Tất cả các kết quả thử nghiệm đều lấy từ các phân loại có điểm cao
nhất với mỗi tài liệu trong tập kiểm thử của cả 3 lần thử nghiệm.
Lần 1: MAX_FEATURE =100
Earn Acq Money_fx Grain Crude Tổng số
Earn 1071 12 0 1 3 1087
Acq 34 653 6 14 14 721
Money_fx 2 24 132 19 2 179
Grain 7 11 10 116 4 148
Crude 4 15 2 9 162 192
Tổng số 1118 715 150 159 185 2327
Bảng 5.2. Bảng kết quả thử nghiệm lần 1
Từ bảng trên tính được:
Số lỗi là E = 193, tổng số mẫu: 2327
Vậy tỷ lệ lỗi: R = E / S = 193/2327 = 0.083
Độ chính xác A: A= 1- R = (S - E) / S =0.917
Lần 2: Max feature =1000 (tăng số đặc trưng)
Earn Acq Money_fx Grain Crude Tổng số
Earn 1076 10 0 0 1 1087
Acq 18 692 1 1 9 721
Money_fx 1 4 174 0 1 180
Grain 3 3 1 142 1 150
^ ]
Luận văn Thạc sỹ
90
Support Vector Machine
Crude 2 5 1 0 181 189
Tổng số 1100 714 177 143 193 2327
Bảng 5.3. Bảng kết quả thử nghiệm lần 2
Số lỗi E = 62, tổng số mẫu: 2327
Vậy tỷ lệ lỗi: R = E / S = 193/2327 = 0.029
Độ chính xác A: A= 1- R = (S - E) / S =0.971
Lần 3: dùng bảng từ dừng với: 509 và MAX_FEATURE=1000
Earn Acq Money_fx Grain Crude Tổng số
Earn 1074 11 1 0 1 1087
Acq 15 696 1 1 7 720
Money_fx 1 3 175 0 0 179
Grain 2 1 3 142 1 149
Crude 3 6 2 0 178 189
Tổng số 1095 717 182 143 187 2324
Bảng 5.4. Bảng kết quả thử nghiệm lần 3
Số lỗi E = 56, tổng số mẫu: 2324
Vậy tỷ lệ lỗi: R = E / S = 193/2327 = 0.024
Độ chính xác A: A= 1- R = (S - E) / S =0.976
Tổng hợp: Đưa kết quả vào một bảng ta có:
Tham số
Số đặc trưng Từ dừng
Tỷ lệ lỗi Chính xác
100 114 0.083 0.917
1000 114 0.029 0.971
1000 509 0.024 0.976
Bảng 5.5. Bảng tổng hợp kết quả thử nghiệm qua 3 lần
^ ]
Luận văn Thạc sỹ
91
Support Vector Machine
Một số nhận xét về phương pháp SVM trong Oracle:
SVM trong Oracle sử dụng phương pháp phân tích thống kê văn bản
tập các tài liệu và các tương quan của chúng với các nhóm theo nội dung.
Ưu điểm:
- Không cần cung cấp các nguyên tắc phân loại hoặc các tài liệu mẫu
trong 1 tập huấn luyện
- Trợ giúp việc phát hiện các mẫu và tính tương tự nội dung trong tập tài
liệu mà các tài liệu có thể bị bỏ sót
- Thực tế, có thể sử dụng phân loại không kiểm soát khi không có một ý
tưởng về các nguyên tắc hoặc phân loại. Một kịch bản có thể là sử
dụng phân loại học không kiểm soát để cung cấp các tập phân loại ban
đầu và sau đó sử dụng trong phân loại có kiểm soát.
Nhược điểm:
- Phân nhóm có thể có kết quả trong các nhóm không mong muốn khi
hành động phân nhóm không được định nghĩa, nhưng dựa trên một giải
thuật bên trong
- Không thấy các nguyên tắc để tạo các phân loại
- Hành động phân loại là cần nhiều CPU và ít nhất là bằng thời gian đánh
chỉ số.
^ ]
Luận văn Thạc sỹ
92
Support Vector Machine
KẾT LUẬN
Trong luận văn chúng tôi đã trình bày các khái niệm và các bước cơ
bản để xây dựng được hệ thống phân loại văn bản. Chúng tôi cũng đâ tập
trung tìm hiểu sâu hơn một phương pháp phân loại mà được các nhà chuyên
môn đánh giá cao là Support Vector Machines. Chúng tôi đã tìm hiểu về cơ
sở lý thuyết, nội dung cách tiếp cận, các vấn đề về phân tách tuyến tính,
không tuyến tính khi sử dụng SVM. Cách tiếp cận SVM trong phân loại đang
được rất quan tâm vì độ chính xác cũng như cách giải quyết với các vấn đề đa
lớp, đa nhãn khi phân loại.
Các cách tiếp cận với phân loại văn bản thường có suy nghĩ là các văn
bản là các file văn bản như Mircosoft Word hay các trang điện tử, nhưng đó
chỉ là một phần thông tin trong thời kỳ mà dữ liệu có ở mọi nơi, và một nơi
lưu trữ rất văn bản và các dữ liệu phi cấu trúc được lưu trong các CSDL về
một lĩnh vực nào đó. Hãng CSDL hàng đầu hiện nay, Oracle, đã thực hiện hỗ
trợ phân loại văn bản bằng phương pháp SVM đối với các văn bản được lưu
dưới dạng file hệ thống, đường dẫn liên kết tới các trang WEB hay chính nội
dung các văn bản đã được lưu trong CSDL. Các văn bản được lưu trong
CSDL Oracle trong các trường có kiểu dữ liệu là CLOB, BLOB hoặc
VARCHAR. Với việc sử dụng SVM trong Oracle, người dùng có thể thực
hiện phân loại với một tài liệu có thể thuộc nhiều hơn một phân loại và một
phân loạicũng có thể có nhiều tài liệu; đây chính là vấn đề đa lớp – đa nhãn
chúng tôi đã đề cập ở trên.
Luận văn mới chỉ dừng lại ở phần lý thuyết và thực hiện thử nghiệm
với phân loại tiếng Anh trong CSDL. Dữ liệu thực nghiệm chúng tôi đã sử
dụng bộ dữ liệu Reuter-21578 với cách phân loại của Mode Aprit với chuyên
dùng để kiểm thử các phương pháp phân loại và đo chính xác của chúng. Bộ
^ ]
Luận văn Thạc sỹ
93
Support Vector Machine
dữ liệu này gồm 9603 tài liệu huấn luyện và 3299 tài liệu kiểm thử được chia
sẵn vào 90 phân loại cho trước. Và để dễ theo dõi kết quả kiểm thử, chúng tôi
sử dụng 5 bộ phân loại có số dữ liệu huấn luyện và kiểm thử lớn nhất để kiểm
thử kết quả. Chúng tôi đã thử nghiệm 5 phân loại này với các cách thiết lập
tham số khác nhau trong Oracle. Qua thử nghiệm chúng tôi đã thu được các
kết quả khả quan với phương pháp phân loại SVM đã được tích hợp trong
Oracle 10g. (tham khảo chương 5, mục 5.2.4 để xem các kết quả của 3 lần
thực nghiệm phân loại.
Các kết quả đã đạt được trong luận văn:
9 Trình bày tổng quan về khai phá văn bản, các bước thực hiện phân loại
văn bản.
9 Tìm hiểu cơ sở lý thuyết của phương pháp SVM, nêu ra các vấn đề về
phân tách đa lớp đa nhãn, phân tích các ưu điểm của phương pháp phân
loại văn bản SVM.
9 Tìm hiểu cách thực hiện phân loại bằng phương pháp bên trong Oracle
10g với các văn bản được đưa trong CSDL Oracle với các bộ dữ liệu đa
lớp và đa nhãn.
9 Thực hiện thử nghiệm trên Oracle và đánh giá kết quả sau 3 lần thử
nghiệm.
Các định hướng phát triển tiếp theo của luận văn:
9 Tìm hiểu, nghiên cứu khai thác rộng và sâu hơn các tri thức về lý
thuyết khai phá văn bản đặc biệt là lĩnh vực KDD để có thể vận dụng
vào thực tiễn chính xác hơn.
9 Thử nghiệm và đánh giá kỹ hơn với các dữ liệu thuộc các lĩnh vực khác
nhau.
^ ]
Luận văn Thạc sỹ
94
Support Vector Machine
9 Tìm hiểu thêm về các phương pháp đánh giá kết quả khác để đưa ra
đánh giá khách quan trong việc sử dụng các phương pháp phân loại
văn bản.
9 Kết hợp với các chuyên gia ngôn ngữ tiếng Việt, đồng thời tìm hiểu
thêm về các cách thức phân loại với ngôn ngữ tự nhiên khác tiếng Anh
để có thể áp dụng phân loại văn bản bằng phương pháp SVM trong
CSDL Oracle một cách hiệu quả hơn, đặc biệt là với các văn bản tiếng
Việt của chúng ta.
^ ]
Luận văn Thạc sỹ
95
Support Vector Machine
TÀI LIỆU THAM KHẢO
Tiếng Việt
1. Nguyễn Linh Giang, Nguyễn Mạnh Hiền (2004), Phân loại văn bản
tiếng Việt với bộ phân loại vector hỗ trợ, Bài báo khoa học, Hà nội.
2. Nguyễn Thị Kim Ngân (2004), Phân loại văn bản tiếng Việt bằng
phương pháp Support Vector Machines, Luận văn thạc sĩ khoa học Công
nghệ thông tin, trường Đại học Bách Khoa Hà nội, Hà nội.
Tiếng Anh
3. Filippo Portera (4/2005), Loss Functions and Structured Domains for
Support Vector Machines, Technique Report UBLCS-2005-08,
Departement of Computer Science University of Bologna, Bologna
(Italy).
4. Oracle (6/2005), Oracle® Text Application Developer's Guide 10g
Release 2(10.2), Technique paper.
5. Oracle (6/2005), Oracle® Text Reference 10g Release 2(10.2),
Technique paper.
6. Oracle (6/2005), Oracle® Data mining Concepts 10g Release 2(10.2),
Technique paper.
7. Brian C. Lovell and Christian J Walder, Support Vector Machines for
Business Applications, The University of Queensland and Max Planck
Institute, Tübingen.
8. Thorsten Joachims, Text Categorization with Support Vector Machines:
Learning with Many Relevant Features, University at Dortmund
Informatik LS8, Baroper Str. 301 44221 Dortmund, Germany.
9. Kurt Maly, Mohammad Zubair, Hesham Anan, An Automated
Classification System and Associated Digital Library Services,
^ ]
Luận văn Thạc sỹ
96
Support Vector Machine
Department of Computer Science, Old Dominion University, Norfolk,
VA 23529, USA.
10. Boriana L. Milenova, SVM in Oracle Database 10g: Removing the
Barriers to Widespread Adoption of Support Vector Machines, Data
Mining Technologies Oracle .
11. Steve R. Gunn (10 May 1998), Support Vector Machines for
Classification and Regression, Technical Report, Faculty of Engineering,
Science and Mathematics School of Electronics and Computer Science,
University of Southamton, English.
12. Oracle, Oracle Text 9.2.0 Technical Feature Review,
13. Oracle, Oracle Text 10g Technical Overview,
ml.
14. Ken Williams (March 18, 2003), A Framework for Text Categorization,
Master of Engineering (Research),School of Electrical and Information
Engineering The University of Sydney, Australia.
15. Vladimir N. Vapnik (1999), The Nature of Statistical Learning Theory
Second Edition, Springer.
16. Mehmed Kantardzic (2003), Data Mining: Concepts, Models, Methods,
and Algorithms, John Wiley & Sons.
Dữ liệu thử nghiệm
17. C.J. van Rijsbergen, Some Examples of Stoplist, SMART, English
Stoplist
18. Aptè split, Aptè split 90 categories, Reuters-21578 collection Aptè split.
^ ]
Luận văn Thạc sỹ
97
Support Vector Machine
Phụ lục 1
DANH SÁCH TỪ DỪNG TIẾNG ANH
cannot given least p thank
a's cant gives less particular thanks
able cause go lest particularly thanx
about causes goes let per that
above certain going let's perhaps that's
according certainly gone like placed thats
accordingly changes got liked please the
across clearly gotten likely plus their
actually co greetings little possible theirs
after com h look presumably them
afterwards come had looking probably themselves
again comes hadn't looks provides then
against concerning happens ltd q thence
ain't consequently hardly m que there
all consider has mainly quite there's
allow considering hasn't many qv thereafter
allows contain have may r thereby
almost containing haven't maybe rather therefore
alone contains having me rd therein
along corresponding he mean re theres
already could he's meanwhile really thereupon
also couldn't hello merely reasonably these
although course help might regarding they
always currently hence more regardless they'd
am d her moreover regards they'll
among definitely here most relatively they're
amongst described here's mostly respectively they've
an despite hereafter much right think
and did hereby must ssaid third
another didn't herein my same this
any different hereupon myself saw thorough
anybody do hers n say thoroughly
anyhow does herself name saying those
anyone doesn't hi namely says though
anything doing himhimself nd second three
anyway don't his near secondly through
anyways done hither nearly see throughout
anywhere down hopefully necessary seeing thru
apart downwards how need seem thus
appear during howbeit needs seemed to
appreciate e however neither seeming together
^ ]
Luận văn Thạc sỹ
98
Support Vector Machine
appropriate each i never seems too
are edu i'd nevertheless seen took
aren't eg i'll new self toward
around eight i'm next selves towards
as either i've nineno sensible tried
aside else ie nobody sent tries
ask elsewhere if non serious truly
asking enough ignored none seriously try
associated entirely immediate noone seven trying
at especially in nor several twice
available et inasmuch normally shall two
away etc inc not she u
awfully even indeed nothing should un
b ever indicate novel shouldn't under
be every indicated now since unfortunately
became everybody indicates nowhere six unless
because everyone inner o so unlikely
become everything insofar obviously some until
becomes everywhere instead of somebody unto
becoming ex into off somehow up
been exactly inward often someone upon
before example is oh something us
beforehand except isn't ok sometime use
behind f it okay sometimes used
being far it'd old somewhat useful
believe few it'll on somewhere uses
below fifth it's once soon using
beside first its one sorry usually
besides five itself ones specified uucp
best followed j only specify v
better following just onto specifying value
between follows k or still various
beyond for keep other sub very
both former keeps others such via
brief formerly kept otherwise sup viz
but forth know ought sure vs
by four knows our t w
c from known ours t's want
c'mon further l ourselves take wants
c's furthermore last out taken was
came g lately outside tell wasn't
can get later over tends way
can't gets latter overall th we
getting latterly own than we'd
we'll
^ ]
Luận văn Thạc sỹ
99
Support Vector Machine
TÓM TẮT LUẬN VĂN
Mục tiêu chính của luận văn là tìm hiểu lĩnh vực khai phá văn bản,
trong đó tập trung nghiên cứu lý thuyết và thử nghiệm trên bộ dữ liệu có sẵn
các ứng dụng phân loại văn bản bằng phương pháp Support Vector Machines.
Trong phần lý thuyết, tác giả đã giới thiệu tổng quan về khai phá văn
bản, các dạng bài toán trong lĩnh vực khai phá văn bản trong hai phần đầu của
chương 1, và đề cập tới khai phá tri thức trong CSDL. Trong hai phần cuối
của chương 1, tác giả trình bày cụ thể về lý thuyết của bài toán phân loại văn
bản và các bước thực hiện để phân loại văn bản. Chương 2 thể hiện nội dung
lý thuyết của phương pháp SVM, cách thực hiện SVM với các trường hợp
phân tách tuyến tính và không tuyến tích; chương 2 cũng giới thiệu một số
hàm kernel hiện nay đang được sử dụng đồng thời cũng nêu ra các vấn đề khi
thực hiện phân tách dữ liệu bằng phương pháp SVM với vấn đề về đa lớp, đa
nhãn và luận văn cũng chỉ ra làm thể nào để có thể tìm được siêu phẳng tối
ưu. Phần phân loại văn bản với phương pháp SVM và lý do vì sao SVM được
đánh giá cao trong phân loại văn bản được trình bày trong Chương 3.
Trong phần thực nghiệm, tác giả đã lựa chọn Oracle 10g phiên bản 2
là môi trường thử nghiệm và Oracle Text là công cụ để thực hiện. Yếu tố để
tác giả lựa chọn Oracle Text để thực hiện thử nghiệm là dữ liệu huấn luyện và
kiểm thử có thể ở trong CSDL hoặc bên ngoài CSDL, có thể là phi cấu trúc
hoặc có cấu trúc. Dữ liệu thử nghiệm được lựa chọn thử nghiệm là bộ dữ liệu
Reuter-21578, gồm 90 phân loại được dựng sẵn. Chương 4, tác giả tập trung
tìm hiểu và trình bày mô hình hoạt động để thực hiện phân loại văn bản bằng
phương pháp SVM trong Oracle, và phần cuối cùng Chương 5 là kết quả của
3 lần thử nghiệm với các đối số khác nhau và những kết luận đánh giá về cách
thực hiện của SVM trong Oracle.
Từ khoá: khai phá văn bản, phân loại văn bản, SVM, Oracle Text, CSDL.
._.
Các file đính kèm theo tài liệu này:
- LA3258.pdf