phân loại văn bản bằng phương pháp support vector machine

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 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.