Baocao

Trường Đại học Nha Trang Khoa Công nghệ Thông tin

PHAN THÚC BÌNH

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

ĐỒ ÁN TỐT NGHIỆP

Nha Trang, 1/2007

Trường Đại học Nha Trang Khoa Công nghệ Thông tin

PHAN THÚC BÌNH

43D1571

PHÂN LOẠI VĂN BẢN BẰNG PHƯƠNG PHÁP SUPPORT VECTOR MACHINES ĐỒ ÁN TỐT NGHIỆP

GIÁO VIÊN HƯỚNG DẪN

ThS. Huỳnh Văn Đức

LỜI CẢM ƠN Đầu tiên, xin gởi lời cảm ơn chân thành đến Thầy Huỳnh Văn Đức, người đã tận tình hướng dẫn, động viên, giúp đỡ em trong suốt thời gian thực hiện đề tài. Trong thời gian làm việc với thầy em không những học hỏi được nhiều kiến thức bổ ích mà còn học được tinh thần và thái độ làm việc nghiêm túc cũng như những kiến thức về cuộc sống rất quý báu của Thầy. Em xin gởi lời cảm ơn đến tất cả các Thầy Cô trong khoa Công nghệ Thông tin, những người đã dạy dỗ, truyền đạt cho em nhiều kiến thức trong suốt những năm học vừa qua. Xin gởi lời cảm ơn chân thành đến gia đình, ba mẹ và bè bạn vì đã luôn là nguồn động viên to lớn, giúp đỡ, chia sẽ những khó khăn, vui buồn cùng tôi trong suốt thời gian qua. Mặc dù đã cố gắng hoàn thiện đồ án với tất cả sự nỗ lực của bản thân, nhưng chắc chắn không thể tránh khỏi những thiếu sót. Em kính mong nhận được sự thông cảm và chỉ bảo của quý Thầy Cô và các bạn.

Nha Trang, 1/2007 Phan Thúc Bình

MỤC LỤC Trang MỤC LỤC................................................................................................... ........ii DANH MỤC HÌNH........................................................................ ...................iv NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN...................................... ..........v 1 Chương I: TỔNG QUAN.......................................................................................................................7 1.1 Vai trò của bài toán phân loại :.........................................................................................................7 1.1.1 Khái niệm phân lớp (Categorization):........................................................................................7 1.1.2 Các khái niệm :...........................................................................................................................8 1.2 Các cách tiếp cận :.............................................................................................................................8 1.2.1 Phương pháp k người láng giềng gần nhất (k-NN Algorithm):..................................................8 1.2.1.1 Ý tưởng:..............................................................................................................................8 1.2.1.2 Thuận lợi:...........................................................................................................................9 1.2.1.3 Bất tiện...............................................................................................................................9 1.2.2 Phương pháp Cây quyết định (Decision Tree Algorithm):.......................................................10 1.2.2.1 Ý tưởng:............................................................................................................................10 1.2.2.2 Thuận lợi:.........................................................................................................................10 1.2.2.3 Bất tiện:............................................................................................................................10 1.2.3 Phương pháp Naïve Bayes:.......................................................................................................11 1.2.3.1 Ý tưởng :...........................................................................................................................11 1.2.3.2 Thuận lợi :........................................................................................................................11 1.2.3.3 Bất tiện :...........................................................................................................................11 1.2.4 Phương pháp mạng Nơron (Neural Network):.........................................................................12 1.2.4.1 Ý tưởng:............................................................................................................................12 1.2.5 Phương pháp máy vectơ hỗ trợ (SVM Algorithm ):.................................................................12 1.2.5.1 Thuận lợi:.........................................................................................................................12 1.2.5.2 Bất tiện :...........................................................................................................................13 1.3 Tiếp cận SVM (Support Vector Machines):......................................................................................13 1.3.1 Giới thiệu..................................................................................................................................13 1.4 Giới thiệu SMO (Sequential Minimal Optimization)........................................................................14 1.5 Mục tiêu của đề tài...........................................................................................................................15 1.5.1 Tìm hiểu SMO :........................................................................................................................15 1.5.2 Cài đặt thí nghiệm phân loại văn bản.......................................................................................15 2 Chương 2 : CƠ SỞ LÝ THUYẾT.........................................................................................................16 2.1 Bài toán tối ưu của SVM..................................................................................................................16 2.1.1 Mô hình phân tách tuyến tính:..................................................................................................16 2.1.1.1 Tìm siêu phẳng với dữ liệu không nhiễu:.........................................................................16 2.1.1.2 Tìm siêu phẳng tách với dữ liệu mẫu có nhiễu:...............................................................19 2.1.2 Mô hình tách phi tuyến.............................................................................................................21 2.1.3 Vai trò hàm kernel.....................................................................................................................22 2.1.4 Điều kiện cần và đủ (The Karush-Kuhn-Tucker Conditions) :................................................23 2.1.5 Rủi ro cấu trúc (Structural Risk):.............................................................................................24 2.1.6 Ứng dụng SVM:......................................................................................................................26 2.2 Tiếp cận SMO :.................................................................................................................................26 2.2.1 Bài toán con và cách giải :........................................................................................................27 2.2.2 Heuristics chọn các nhân tử Lagrange :....................................................................................28

SVTH: Phan Thúc Bình

i

2.2.3 Phương pháp tính giới hạn b tại mỗi bước:..............................................................................31 2.2.4 Vấn đề hội tụ:...........................................................................................................................31 2.3 Bài toán phân loại văn bản :............................................................................................................31 2.3.1 Định nghĩa:...............................................................................................................................31 2.3.2 Các kiểu phân loại :..................................................................................................................31 2.3.2.1 Phân loại văn bản đơn nhãn và đa nhãn...........................................................................31 2.3.2.2 Phân loại văn bản phụ thuộc lớp/loại văn bản so với phụ thuộc tài liệu..........................32 2.3.2.3 Phân loại văn bản “cứng” so với “mềm”..........................................................................32 2.3.3 Ứng dụng của phân loại văn bản :............................................................................................33 2.3.4 Quá trình phân loại văn bản :...................................................................................................33 2.3.4.1 Tiền xử lý văn bản :..........................................................................................................33 2.3.4.2 Tạo ra chỉ mục :................................................................................................................34 2.3.4.3 Chọn lựa đặc trưng :.........................................................................................................36 2.3.4.4 Xây dựng thuật toán phân lớp : .......................................................................................39 2.3.4.5 Kết quả, đánh giá độ chính xác :......................................................................................40 3 PHẦN III : THIẾT KẾ - CÀI ĐẶT......................................................................................................41 3.1 Thuật toán SMO : ............................................................................................................................41 3.1.1 Sơ đồ lớp :................................................................................................................................41 3.1.2 Cài đặt......................................................................................................................................41 3.1.2.1 Lớp mainSVM.................................................................................................................41 3.1.2.2 Lớp linearSvm.................................................................................................................41 3.1.2.3 Lớp noneLinearSvm.........................................................................................................42 3.2 Module phân loại văn bản :.............................................................................................................42 3.2.1 Sơ đồ lớp :...............................................................................................................................44 3.2.2 Cài đặt :....................................................................................................................................44 3.2.2.1 Lớp Doc2Vector...............................................................................................................44 3.2.2.2 Lớp proClassify :..............................................................................................................44 3.2.2.3 Lớp preProcess................................................................................................................44 3.3 Giao diện chương trình :..................................................................................................................45

SVTH: Phan Thúc Bình

ii

DANH MỤC HÌNH Hình 1: Ví dụ về biên không tốt ............................................................................................................................ .... 8 Hình 2:Ví dụ về biên tối ưu ............................................................................................................................ .... 8 Hình 3: Minh họa Support Vectors ............................................................................................................................ .... 13 Hình 4: Tập huấn luyện có nhiễu ............................................................................................................................ .... 14 Hình 5: Chuyển không gian ban đầu vào không gian đặc trưng ............................................................................................................................ .... 15 Hình 6: Chiều VC ............................................................................................................................ .... 18 Hình 7: Qui trình giải bài toán con ............................................................................................................................ .... 21 Hình 8: Tìm i vi phạm cặp ràng buộc đối ngẫu ............................................................................................................................ .... 23 Hình 9: Tìm j qui phạm cặp ràng buộc đôi ngẫu ............................................................................................................................ .... 24 Hình 10: Quá trình phân loại văn bản ............................................................................................................................ .... 27 Hình 11: Biểu diễn văn bản sang vectơ SVTH: Phan Thúc Bình

iii

............................................................................................................................ .... 28 Hình 12: Sơ đồ lớp cài đặt SMO ............................................................................................................................ .... 35 Hình 13: Mô hình thuật toán học và phân loại. ............................................................................................................................ .... 37 Hình 14: Sơ đồ lớp module phân loại văn bản ............................................................................................................................ .... 38 Hình 15: Phân loại từng văn bản ............................................................................................................................ .... 39 Hình 16: Phân loại cả thư mục ............................................................................................................................ .... 39 Hình 17: Minh họa thuật toán SMO ............................................................................................................................ .... 40

SVTH: Phan Thúc Bình

iv

KÍ HIỆU VÀ VIẾT TẮT SVM: Support Vector Machines. SMO: Sequential Minimal Optimation QP: Quadratic Programming KKT: Karush-Kuhn-Tucker VC : Vapnik Chervonenkis TF : Term Frequency. TFIDF : Term Frequency Inverse Document Frequency OC: Orthogonal Centroid. OCFS: Orthogonal Centroid Feature Selection

SVTH: Phan Thúc Bình

v

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SVTH: Phan Thúc Bình

vi

Phân loại văn bản bằng phương pháp Support Vector Machines

1 CHƯƠNG I: TỔNG QUAN

1.1 Vai trò của bài toán phân loại : Ngày nay, với sự phát triển vượt bậc của công nghệ thông tin, với những tính năng ưu việt của máy tính như lưu trữ nhanh, an toàn, gọn nhẹ, dễ truyền tải...Thì phương thức sử dụng giấy tờ trong giao dịch dần chuyển sang các dạng văn bản số. Cùng với sự phát triển như vậy, số lượng văn bản ngày càng nhiều thì nhu cầu phân loại là rất cần thiết. Có rất nhiều lĩnh vực ứng dụng về phân loại văn bản, ví dụ như phân loại tài liệu, lọc văn bản, lướt Internet để truy lục thông tin, và ngăn chặn thư rác. Để đạt được lợi ích từ phân loại văn bản trong những lĩnh vực này, hệ thống phân loại phải sử dụng phân loại tự động với giá cả thấp nhất và dễ dàng cho các phương pháp phân loại cổ điển. Việc phân loại tự động sẽ giúp chúng ta dễ dàng và nhanh chóng tìm kiếm thông tin, giúp chúng ta tiết kiệm được thời gian và hiệu quả công việc sẽ cao hơn. Vì lí do này, những hệ thống nói trên chấp nhận cách tiếp cận học thông qua máy. Với cách tiếp cận này sẽ tạo ra hệ thống phân loại tự động có sự trợ giúp khi cung cấp ngữ liệu huấn luyện vào trong hệ thống và làm cho hệ thống “học” cách phân loại văn bản thông qua các ngữ liệu đó. 1.1.1 Khái niệm phân lớp (Categorization): Phân lớp là một tiến trình trong đó các đối tượng và sự việc được nhận ra, được phân biệt và hiểu được. Sự phân lớp hàm ý rằng các đối tượng được nhóm thành các bộ phân loại, thường thì phục vụ cho một vài mục đích đặc biệt. Nói một cách cơ bản, một bộ phân loại mô tả mối quan hệ giữa các chủ thể và đối tượng tri thức. Có rất nhiều cách tiếp cận phân lớp, nhưng nói chung có 2 cách cơ bản nhất: • Phân lớp học có giám sát (supervised learning). Ví dụ: Phân loại văn bản (Text Classification). • Phân lớp học không có giám sát (unsupervised learning). Ví dụ: Phân cụm văn bản (Text Clustering).

SVTH: Phan Thúc Bình

7

Phân loại văn bản bằng phương pháp Support Vector Machines 1.1.2 Các khái niệm : - Phân loại văn bản (Text Categorization): Cho một số lớp văn bản đã được xác định trước (tập huấn luyện), nhiệm vụ của phân loại văn bản là: gán các văn bản vào một (hay một số) lớp văn bản thích hợp dựa vào nội dung của văn bản. - Phân cụm văn bản (Text Clustering): Cho một số văn bản, nhiệm vụ của phân cụm văn bản là chia các văn bản này thành các cụm thích hợp căn cứ vào sự tương tự về mặt nội dung giữa các văn bản.

1.2 Các cách tiếp cận : Có rất nhiều phương pháp phân loại được đề xuất ,mỗi phương pháp phân loại văn bản đều có cách tính toán khác nhau. Sự khác nhau cơ bản của các phương pháp này là ở thuật toán học quy nạp. Tuy nhiên, nhìn một cách tổng quan thì các phương pháp đó đều phải thực hiện một số bước chung như sau: đầu tiên, mỗi phương pháp sẽ dựa trên các thông tin về sự xuất hiện của từ trong văn bản (ví dụ tần số, số văn bản chứa từ…) để biểu diễn văn bản thành dạng vector; sau đó, tuỳ từng phương pháp mà ta sẽ áp dụng công thức và phương thức tính toán khác nhau để thực hiện việc phân loại. Sau đây là một số cách tiếp cận mà theo thực nghiệm thì có hiệu quả phân loại cao cũng như những thuận lợi và bất tiện của mỗi cách. 1.2.1 Phương pháp k người láng giềng gần nhất (k-NN Algorithm): 1.2.1.1 Ý tưởng: Là phương pháp nổi tiếng về hướng tiếp cận dựa trên xác suất thống kê. Khi cần phân loại văn bản mới thuật toán sẽ tính khoảng cách (khoảng cách Euclide, Cosine...) của tất cả các văn bản trong tập huấn luyện đến văn bản mới này để tìm ra k văn bản gần nhất (gọi là k “láng giềng”) sau đó dùng các khoảng cách này đánh trọng số cho tất cả các chủ đề. Trọng số của một chủ đề chính là tổng tất cả các khoảng cách ở trên của văn bản trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng giềng sẽ có trọng số bằng không. Sau đó các chủ đề được sắp xếp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân loại. SVTH: Phan Thúc Bình

8

Phân loại văn bản bằng phương pháp Support Vector Machines 1.2.1.2 Thuận lợi: Có một vài thuận lợi khi thực thi giải pháp này. Giải thuật này được xem như giải thuật tốt nhất để bắt đầu việc phân loại văn bản và là một giải thuật mạnh. Một trong những thuận lợi của giai thuật này chính là sự rõ ràng và dễ dàng, đơn giản và dễ thực hiện. Được dựa trên phương pháp trực tuyến với cách xử lý một số hỗn hợp các tài liệu được thiết lập với các phụ lục kèm chỉ số và việc tìm kiếm các phụ lục có các tài liệu nhập vào được xem như điều kiện chia sẻ để thiết lập cho các tài liệu khác. Đặc biệt, giải thuật này còn kiểm tra các tài liệu kề các tài liệu mới, và cần vài thông số để làm việc này, nói cách khác giải thuật này hầu như không giới hạn. Dựa vào các nhân tố này, giải thuật này hoàn toàn hiệu quả thông qua thực nghiệm và dễ dàng áp dụng. Một thuận lợi khác là giải thuật này có nhiều hơn các kí tự cục bộ, bởi vì khi giải thuật này thử phân loại một tài liệu nhập vào, lập tức kiểm tra điều kiện trong tài liệu để tìm ra các điều kiện tương tự trong các tài liệu kề đó. Việc kiểm tra điều kiện gần kề đầu tiên là dễ dàng và hiệu quả hơn. Một lợi ích nữa của k-NN là giải thuật này có thể được vận dụng để cải tiến hơn. Nói cách khác, giải thuật này nhanh chóng chỉnh sửa và phù hợp với các trường hợp khác. Ví dụ, giải thuật có thể được áp dụng cho bất kỳ khoảng cách đo lường nào khi nhập vào và các tài liệu huấn luyện vì khoảng cách của các tài liệu nhập vào có thể được giảm đi để cải tiến hiệu quả của giải thuật, do vậy k-NN có thể được áp dụng cho tài liệu với bất kì khoảng cách nào trong tài liệu đào tạo. Cũng vì thế mà hầu hết thời gian huấn luyện đòi hỏi cho phân loại văn bản trong giải thuật k-NN; giải thuật này được đánh giá là kỹ thuật chi phí trong các kỹ thuật. cuối cùng, k-NN là giải thuật mạnh có thể giám sát các nguồn tiềm năng lỗi. 1.2.1.3 Bất tiện Rất khó có thể tìm ra k tối ưu. Hơn nữa với trường hợp văn bản có nhiễu thì việc phân loại là không tốt

SVTH: Phan Thúc Bình

9

Phân loại văn bản bằng phương pháp Support Vector Machines 1.2.2 Phương pháp Cây quyết định (Decision Tree Algorithm): 1.2.2.1 Ý tưởng: Bộ phân lớp cây quyết định là một dạng cây mà mỗi nút được gán nhãn là một đặc trưng, mỗi nhánh là giá trị trọng số xuất hiện của đặc trưng trong văn bản cần phân lớp, và mỗi lá là nhãn của phân lớp tài liệu. Việc phân lớp của một tài liệu dj sẽ được duyệt đệ quy theo trọng số của những đặc trưng có xuất hiện trong văn bản dj. Thuật toán lặp đệ quy đến khi đạt đến nút lá và nhãn của dj chính là nhãn của nút lá tìm được. Thông thường việc phân lớp văn bản nhị phân sẽ tương thích với việc dùng cây nhị phân. 1.2.2.2 Thuận lợi: - Dễ hiểu, dễ cài đặt. - Có thể chấp nhận trường hợp tập dữ liệu huấn luyện có nhiễu, và cho hiệu quả phân loại tương đối cao. 1.2.2.3 Bất tiện: Việc sử dụng giải thuật cây quyết định liên quan đến một số hạn chế quan trọng, dựa vào trạng thái nguyên thủy của thuật toán mà chia các vùng tài liệu được đưa vào các tập hợp con. Trước tiên, giải thuật này chia những tập tài liệu tùy thuộc vào đặc trưng (một bộ phận từ ) mọi lúc, bằng cách sử dụng các đặc trưng rõ ràng mọi lúc. Dựa vào các nhân tố này, giải thuật này sẽ bị sai nếu một lỗi bị nhìn thấy tại bất cứ mức độ nào, bởi vì cây con bên dưới cấp bậc sẽ bị sai. Do đó, giải thuật cây quyết định không mạnh và nó dường như mạo hiểm để quyết định những nhánh phân loại. Một vấn đề khác là không có bảo vệ phù hợp giống như Support Vector Machines, vì vậy chúng có thể loại trừ các đặc trưng. Điều này có nghĩa là chúng không thể chấp nhận một văn bản với số lượng lớn đặc trưng như SVM, vì có quá nhiều đặc trưng tạo nên tràn phù hợp và làm cho khả năng học kém hơn. Một trở ngại khác là thời gian huấn luyện phân loại cao bởi vì giải thuật này cần so sánh tất cả những nhánh con có thể, nên mất nhiều thời gian để chia và duyệt các đặc trưng.

SVTH: Phan Thúc Bình

10

Phân loại văn bản bằng phương pháp Support Vector Machines 1.2.3 Phương pháp Naïve Bayes: 1.2.3.1 Ý tưởng : Ý tưởng cơ bản của phương pháp xác suất Bayes là dựa vào xác suất có điều kiện của từ hay đặc trưng xuất hiện trong văn bản với chủ đề để dự đoán chủ đề của văn bản đang xét. Điểm quan trọng cơ bản của phương pháp này là các giả định độc lập: - Các từ hay đặc trưng của văn bản xuất hiện là độc lập với nhau. - Vị trí của các từ hay các đặc trưng là độc lập và có vai trò như nhau. Giả sử ta có: - n chủ đề (lớp) đã được định nghĩa c1 , c2 , , cn - Tài liệu mới cần được phân loại d j Để tiến hành phân loại tài liệu d j , chúng ta cần phải tính được tần suất xuất hiện của các lớp ci (i = 1,2,..., n) trong tài liệu d j . Sau khi tính được xác suất của văn bản đối với các chủ đề, theo luật Bayes, văn bản sẽ được phân lớp vào chủ đề ci nào có xác suất cao nhất. 1.2.3.2 Thuận lợi : Là phương pháp đơn giản, cài đặt không phức tạp, tốc độ nhanh, với tập huấn luyện lớn thì cho kết quả vẫn tương đối chính xác. 1.2.3.3 Bất tiện : Giải thuật Naïve Bayes cũng có những điểm yếu riêng mặc dù được xem là trình diễn tốt hơn giải thuật Cây quyết định. Một trong những trở ngại là dựa trên luật gọi là các điều kiện độc lập. Có thể bị vi phạm bởi các trường hợp trong thực tế, bởi vì Naïve Bayes thừa nhận các đặc trưng trong văn bản độc lập riêng rẻ và được biểu diễn một cách nghèo nàn khi những đặc trưng này có mối liên hệ với nhau. Hơn nữa, luật này không tạo được sự thường xuyên cho việc xuất hiện các đặc trưng. Một bất lợi khác nữa là giải thuật sử dụng nhiều tính toán và vì vậy thời gian bị chi phối.

SVTH: Phan Thúc Bình

11

Phân loại văn bản bằng phương pháp Support Vector Machines 1.2.4 Phương pháp mạng Nơron (Neural Network): 1.2.4.1 Ý tưởng: Mô hình mạng neural gồm có ba thành phần chính như sau: kiến trúc (architecture), hàm chi phí (cost function), và thuật toán tìm kiếm (search algorithm). Kiến trúc định nghĩa dạng chức năng (functional form) liên quan giá trị nhập (inputs) đến giá trị xuất (outputs). Kiến trúc phẳng ( flat architecture ) : Mạng phân loại đơn giản nhất ( còn gọi là mạng logic) có một đơn vị xuất là kích hoạt kết quả (logistic activation) và không có lớp ẩn, kết quả trả về ở dạng hàm (functional form) tương đương với mô hình hồi quy logic. Thuật toán tìm kiếm chia nhỏ mô hình mạng để thích hợp với việc điều chỉnh mô hình ứng với tập huấn luyện. Ví dụ, chúng ta có thể học trọng số trong mạng kết quả (logistic network) bằng cách sử dụng không gian trọng số giảm dần (gradient descent in weight space) hoặc sử dụng thuật toán interated-reweighted least squares là thuật toán truyền thống trong hồi quy (logistic regression). Kiến trúc môđun(modular architecture ): Việc sử dụng một hay nhiều lớp ẩn của những hàm kích hoạt phi tuyến tính cho phép mạng thiết lập các mối quan hệ giữa những biến nhập và biến xuất. Mỗi lớp ẩn học để biểu diễn lại dữ liệu đầu vào bằng cách khám phá ra những đặc trưng ở mức cao hơn từ sự kết hợp đặc trưng ở mức trước. 1.2.5 Phương pháp máy vectơ hỗ trợ (SVM Algorithm ): 1.2.5.1 Thuận lợi: Giải thuật Support Vector Machines là giải thuật dễ dàng trong sử dụng và mạnh, hầu như không có lỗi và trình diễn tốt nhất trong thử nghiệm. Ưu điểm đầu tiên là giải thuật này có giải pháp cẩn thận trong việc chon lựa các đặc trưng. Đặc trưng của văn bản là sự khác biệt trong các bộ phận từ xuất hiện trong văn bản. Văn bản được xem như một vectơ bao gồm các bộ phận, tùy thuộc vào định nghĩa của giải thuật. Trong SVM, hầu hết các đặc trưng được xem như có liên quan và hữu dụng trong phân loại văn bản ngay cả khi đó là những đặc trưng với ít khả năng rõ ràng nhất cũng được sử dụng để thử hệ thống

SVTH: Phan Thúc Bình

12

Phân loại văn bản bằng phương pháp Support Vector Machines phân loại, với những trình diễn tốt hơn cho các phân loại ngẫu nhiên. Vì lí do này SVM xem việc chọn đặc trưng như bộ phận thu nhỏ thực thi và sử dụng nó khá ít để ngăn chặn mất thông tin khi phân loại văn bản điểm. Hệ thống phân loại thực thi SVM nối kết nhiều đặc trưng để loại trừ chúng và sau đó “học” sự phân loại bằng cách dùng nhiều đặc trưng liên quan. Thứ hai, số lượng các đặc trưng (kích thước không gian đặc trưng) của văn bản được phân loại không ảnh hưởng đến khả năng của hệ thống sử dụng SVM. Nói cách khác, giải thuật SVM có thể xử lý với bất kỳ văn bản nào trong khi đang huấn luyện dù cho số lượng đặc trưng chứa trong nó lớn. Thứ ba là giải thuật được xây dựng trên ý tưởng cực tiểu rủi ro cấu trúc. Nguồn gốc của SVM dựa trên sự chắc chắn về lỗi chính xác, có thể phân loại ngẫu nhiên các mẫu văn bản được chọn mà lỗi được giữ sao cho nhỏ nhất. Vì vậy, giải thuật SVM giúp giảm thiểu biên trên các lỗi chính xác và làm cho hệ thống tin cậy hơn. Cuối cùng, một phần nhỏ các nhãn trong tập dữ liệu huấn luyện được giao cho SVM để huấn luyện hệ thống cho các tham. SVM có thể kiểm tra các tập mẫu mà trước đây không thể. 1.2.5.2 Bất tiện : - Để đạt kết quả phân loại tốt cần chọn hàm kernel phù hợp. - Yêu cầu phải lặp đi lặp lại quá trình huấn luyện đối với bài toán nhiều lớp.

1.3 Tiếp cận SVM (Support Vector Machines): 1.3.1 Giới thiệu Phương pháp Support Vector Machines được Vladimir Vapnik đưa ra vào năm 1995 để giải quyết vấn đề nhận dạng mẫu hai lớp sử dụng nguyên tắc cực tiểu hóa rủi ro cấu trúc (Structural Risk Minimization). Đây là phương pháp tiếp cận phân loại văn bản rất hiệu quả. Cho trước một tập huấn luyện biểu diễn trong không gian vector mỗi tài liệu là một vector được biểu diễn là một điểm, phương pháp SVM sẽ tìm ra một siêu phẳng h quyết định tốt nhất để chia các điểm trong không gian thành hai lớp riêng biệt . Chất lượng của siêu phẳng này được quyết định bởi khoảng cách (gọi là biên) SVTH: Phan Thúc Bình

13

Phân loại văn bản bằng phương pháp Support Vector Machines của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt và việc phân loại càng chính xác. Mục đích của SVM là tìm được khoảng cách biên lớn nhất và lỗi tách sai là bé nhất. Lớp 2

Lớp 2

Lớp 1

Lớp 1

Hình 1: Ví dụ về biên không tốt.

h(x) =

Lớp 2

m Lớp 1

Hình 2: Ví dụ về biên tối ưu. Từ đó bài toán đặt ra là tìm mặt phẳng tách

h( x) = wT x + b . Đây

cũng là bài toán chính của SVM. Ta sẽ phân tích và giải quyết bài toán này ở phần sau.

1.4 Giới thiệu SMO (Sequential Minimal Optimization) SMO là thuật toán đơn giản có thể giải quyết nhanh bài toán qui hoạch toàn phương của SVM (Quadratic Programming) mà không cần sử dụng ma trận lưu trữ. SMO phân rã bài toán qui hoạch toàn phương thành dãy các bài toán con, sử

SVTH: Phan Thúc Bình

14

Phân loại văn bản bằng phương pháp Support Vector Machines dụng định lý Osuna để đảm bảo sự hội tụ. Đây là một trong những phương pháp tốt nhất hiện nay có thể giải quyết rất tốt bài toán SVM nói trên. Không giống như các phương thức khác, SMO chọn cách giải quyết tối ưu hóa vấn đề nhỏ nhất có thể tại mỗi bước. Ở mỗi bước SMO chọn hai số nhân Lagrange để cùng tối ưu, tìm những giá trị tối ưu cho các số nhân này và cập nhật SVM tương ứng với giá trị tối ưu mới. Sự thuận tiện của SMO trong thực tế là việc xử lý hai số nhân Lagrange được thực hiện theo phép phân tích. Hơn nữa SMO không phụ thuộc vào ma trận lưu trữ thêm tại tất cả các bước. Ba thành phần của SMO: -

Phương pháp giải tích để xử lý hai số nhân Lagrange

-

Heuristic để chọn số nhân tối ưu

-

Phương pháp để tính b tại mỗi bước.

1.5 Mục tiêu của đề tài 1.5.1 Tìm hiểu SMO : Trong khuôn khổ đồ án này, em sẽ tìm hiểu lý thuyết phương pháp SVM và thực hiện giải bài toán này bằng phương pháp SMO. 1.5.2 Cài đặt thí nghiệm phân loại văn bản. Để kiểm nghiệm lại kết quả của phương pháp SVM và cách giải SVM bằng SMO, em sẽ cài đặt chương trình phân loại văn bản tự động.

SVTH: Phan Thúc Bình

15

Phân loại văn bản bằng phương pháp Support Vector Machines

2 CHƯƠNG 2 : CƠ SỞ LÝ THUYẾT 2.1 Bài toán tối ưu của SVM 2.1.1 Mô hình phân tách tuyến tính: Giả sử có hàm tuyến tính gọi là hàm phân tách:

h( x ) = w T x + b h(x) > 0 , ∀x ∈ X + với  h( x) < 0, ∀x ∈ X −

 X + = {x i | y i = 1} trong đó  −  X = { y i | y i = −1}

w: vector trọng số (weight vector) b: trọng số ngưỡng (threshold weight) 2.1.1.1 Tìm siêu phẳng với dữ liệu không nhiễu: Bài toán đặt ra la tìm ra siêu phẳng h(x) (tức là tìm w , b) tách không lỗi với khoảng cách từ mẫu huấn luyện đến siêu phẳng là cực đại. Định nghĩa W: Độ rộng cột của siêu phẳng tách (W): Là tổng khoảng cách từ điểm dữ liệu gần nhất của lớp +1 đến siêu phẳng và khoảng cách từ điểm dữ liệu gần nhất của lớp –1 đến siêu phẳng. W được tính như sau:

wT x + b wT x + b m+ m− W = min+ − max− = − x∈X x∈X || w || || w || || w || || w || Nhận xét: W không phụ thuộc vào b, nên ta có thể chọn b sao cho m + = − m − = m . W không phụ thuộc độ lớn w, chọn b và w sao cho m = 1 . Như vậy ta có W =

2m 2 = || w || || w ||

SVTH: Phan Thúc Bình

16

Phân loại văn bản bằng phương pháp Support Vector Machines Từ đó bài toán trên được đưa về bài toán quy hoạch toàn phương sau:

1 2  w → min Tìm b, w sao cho  2  y i wT x i + b ≥ 1, i = 1,..., n 

(

)

Để giải quyết bài toán này người ta đưa ra hàm Lagrange:

L=

1 2 w − α T ( y ( w T + b) − 1) 2

Điều kiện Kuhn Tucker (cần và đủ)

L'w = w − X ( yα ) = 0 L'b = α T y = 0 L'α = − y ( wT x + b) + 1 ≤ 0, α ≥ 0 L'α α = 0 Với X = ( x , x ,...), yα = ( y1α 1 , y 2α 2 ,..., y n α n ) 1

Ta có

2

w 2 = ( yα ) T X T X ( yα ) ⇔ w 2 = α T Dα

với

 D = Y T X T XY  Y = diag ( y )

1 2

αT ( y ( wT + b) −1) ≥ 0 ⇒ w 2 +αT Dα +αT e ⇔

1 2 1 w ≥ − α T Dα + α T e 2 2

Vậy bài toán đối ngẫu tương đương là:

1 − α T Dα + α T e → max 2 α T y = 0  α ≥ 0 Khi đó

w = Xα

, X = (x) ,

b = y i − wT x i SVTH: Phan Thúc Bình

x = yx

tại α i > 0 17

Phân loại văn bản bằng phương pháp Support Vector Machines

Và hàm quyết định

uˆ = sign( wT x + b)

Ví dụ: 0 −1   X =  0  1

 0 1  , Y = (1,−1) ⇒ X =  1 0  0 D = X X =   −1 T

h

− 1 1 0  =  0   0 1

1  0  0 1

1 2 1 2 α 1 + α 2 − α 1 − α 2 → min 2 2 Bài toán đối ngẫu: α = α  1 2  α j ≥ 0 Giải bài toán trên ta được:

α1 = α 2 = 1

0 w = Xα =  1

− 11  − 1   =   0 1  1 

0 b = y 1 − wT x i = 1 − (1 1)   = 0 1  W = Với

2 2 = = 2 w 2

x( x1 , x 2 ) ⇒ uˆ = ((−1) x1 + (1) x2 )

Định nghĩa: Các vector ứng với

αi > 0

là các vectơ hỗ trợ. Các vectơ hỗ

trợ có khoảng cách tới siêu phẳng là bé nhất. Từ ví dụ trên ta có nhận xét:

w = ∑α j y j x j Với xj là các support vector. Khi tập mẫu tăng, kích thước bài toán lớn lên theo (mỗi mẫu là một ràng buộc). Như vậy độ phức tạp tính toán là không thể chấp nhận được. Để giải

SVTH: Phan Thúc Bình

18

Phân loại văn bản bằng phương pháp Support Vector Machines quyết vấn đề này ta sẽ xây dựng các thuật toán huấn luyện, và vai trò của các vectơ hỗ trợ là rất quan trọng. Điểm thú vị của SVM là mặt phẳng quyết định phụ thuộc vào các vectơ hỗ trợ có khoảng cách đến mặt phẳng quyết định là

1  . Khi các điểm khác xoá || w ||

hết đi thì thuật toán vẫn có kết quả giống như ban đầu. Đó là đặc điểm khác so với các phương pháp khác vì tất cả dữ liệu trong tập huấn luyện đều được dùng để tối ưu hoá kết quả. Support Vectors

Hình 3: Minh họa Support Vectors 2.1.1.2 Tìm siêu phẳng tách với dữ liệu mẫu có nhiễu: Tập dữ liệu huấn luyện có thể phân chia tuyến tính nhưng có nhiễu. Chúng ta phải tìm mặt phẳng tách sao cho nó có độ rộng lớn nhất và số lỗi tách là bé nhất.

SVTH: Phan Thúc Bình

19

Phân loại văn bản bằng phương pháp Support Vector Machines

h z1

Lớp 2 z2 z3

m Lớp 1

Hình 4: Tập huấn luyện có nhiễu Đặt z là sai số phân loại, ta có:

z i = 1 − y i ( w T + b)

Với những phân loại sai :

Với những phân loại đúng : z i = 0 ≥ 1 − y i ( w T + b) Chọn các điều khiển đơn giản, ta có

1 2 T  2 w + Cz 1 → min   i T i y w x + b + z ≥ 1 z ≥ 0   

(

)

Từ đó ta có bài toán đối ngẫu sau :

1 T α Dα − α T 1 → min 2 yTα = 0  0 ≤ α ≤ C Đây là dạng mô hình SVM tổng quát giải quyết đồng thời hai mục tiêu: độ rộng lớn nhất và lỗi tách là bé nhất.

SVTH: Phan Thúc Bình

20

Phân loại văn bản bằng phương pháp Support Vector Machines 2.1.2 Mô hình tách phi tuyến Trong nhiều trường hợp dữ liệu vào không thể phân chia tuyến tính. Do đó chúng ta cần ánh xạ tập vector dữ liệu vào không gian đặc trưng có số chiều cao hơn nhiều so với không gian ban đầu, bằng cách sử dụng hàm :

Φ : Rn → Rm Φ ( x)

x

Φ (.) Hình 5: Chuyển không gian ban đầu vào không gian đặc trưng Chúng ta cần phải chuyển không gian ban đầu vào không gian đặc trưng vì những thao tác trên tách tuyến tính trên không gian đặc trưng cũng tương đương với thao tác tách phi tuyến trên không gian đầu vào ban đầu. Hơn nữa quá trình phân tách sẽ dễ dàng hơn khi ta chọn một phép chuyển thích hợp. Việc tính toán trên không gian đặc trưng sẽ tốn nhiều thời gian hơn bởi lẽ trong không gian này số chiều lớn (thường thì số chiều này không xác định được). Để giải quyết vấn đề này ta cần sử dụng đến hàm Kernel. Từ bài toán tối ưu SVM ban đầu ta chuyển về bài toán tách trên không gian mới là:

1 2 w + Cz T 1 → min 2  y ( w T Φ ( x i ) + b) + z ≥ 1  z ≥ 0 Khi đó luật quyết định là :

x

Φ

SVTH: Phan Thúc Bình

r

uˆ Φ(x)

uˆ

l ∈ { − 1, 1}

21

Phân loại văn bản bằng phương pháp Support Vector Machines Và hàm quyết định của ta có dạng như sau :

(

l = sign w Φ ( x) + b T

)

wT = ∑ α i Φ ( x i )

với

i

Từ đó ta có bài toán đối ngẫu

1 T α Dα − α T 1 → min 2  yTα = 0  0 ≤ α ≤ C

(

( ) ( )y)

Với D = d ij = y Φ x , Φ x

(

i

i

j

j

)

( ) ( ) ⇒ D = ( y K(x , y )y )

K x i , y j = Φ x i Φ x j : gọi là hàm kernel i

i

j

j

Giả sử α j > 0 là nghiệm của bài toán đối ngẫu, ta có :

b = y j − ∑αi y i K ( x i , x j ) i

(

)

uˆ = ∑ α i y i K x i , x + b i

2.1.3 Vai trò hàm kernel Kernel là những hàm trả về giá trị tích trong giữa các ảnh của các điểm dữ liệu trong một vài không gian. Việc lựa chọn K cũng chính là chọn Φ . Các hàm kernel có thể được tính toán hiệu quả ngay cả trên không gian có rất nhiều chiều. Hàm Kernel đóng một vai trò quan trọng trong bài toán phân loại sử dụng phương pháp SVM, nó tạo ra ma trận kernel tóm tắt tất cả dữ liệu. Trong thực tế, kernel đa thức với số bậc thấp hoặc kernel Gauss với độ rộng hợp lý thì khởi tạo tốt cho hầu hết các ứng dụng. Đối với phân loại văn bản thì sử dụng kernel đường thẳng là tốt nhất vì số chiều đặc trưng của hàm này đã đủ lớn. Một số hàm Kernel cơ bản : + Linear Kernel :

SVTH: Phan Thúc Bình

K ( x, y ) = ( x T y ) d 22

Phân loại văn bản bằng phương pháp Support Vector Machines + Polynomial Kernel : K ( x, y ) = ( x T y + 1) d + Radial Basis Function Kernel : K ( x, y ) = exp(−

x−y

2

2δ 2

)

+ Sigmoid Kernel : K ( x, y ) = tanh(κx T y + θ ) 2.1.4 Điều kiện cần và đủ (The Karush-Kuhn-Tucker Conditions) : Từ bài toán tối ưu tối ban đầu ta có được các phương trình sau:

α i ( yi ( wT xi − b ) + zi − 1) = 0 µ i zi = 0

(1) ( 2)

Phụ thuộc vào giá trị α i ta có các trường hợp sau:  Nếu α i = 0 thì

µ i = C − α i = C > 0 ⇒ zi = 0

(

)

Vì vậy: yi w xi − b − 1 ≥ 0 T

 Nếu 0 < α i < C thì từ phương trình (1) ta có:

(

)

y i wT xi − b + zi − 1 = 0 Mà

µ i = C − α i > 0 ⇒ zi = 0

(

)

Vì vậy: y i w x i − b − 1 = 0 T

(

)

T  Nếu α i = C thì từ phương trình (1) ta có: y i w xi − b + zi − 1 = 0

Mà µi = C − α i = 0 , ta có zi ≥ 0

(

)

Vì vậy y i w x i − b − 1 ≤ 0 Đặt

(

)

T

u i = y i w T x i − b − 1 ta viết lại u i :

(

)

(

)

u i = y i wT xi − b − y i2 = y i wT xi − b − y i = y i E i Với

E i = wT xi − b − y i = u i − y i

SVTH: Phan Thúc Bình

23

Phân loại văn bản bằng phương pháp Support Vector Machines Điều kiện KKT được tóm tắt lại như sau :

α i = 0 ⇒ ui ≥ 0   0 < α i < C ⇒ ui ≈ 0  α i = C ⇒ ui ≤ 0  2.1.5 Rủi ro cấu trúc (Structural Risk):  Số chiều VC (Vapnik Chervonenkis dimension): Xét các hàm f(x) : R→{+1,-1}, có 2n cách để gán nhãn cho n điểm. Nếu với mỗi một cách gán nhãn ta đều có thể tìm thấy một thành phần của tập hợp {f(x)} mà nhận dạng chính xác cách gán nhãn này. Khi đó tập hợp của n điểm được nói là bị phá vỡ bởi tập hợp các hàm {f(x)}. Chiều VC của {f(x)} là số lớn nhất của các điểm dữ liệu mà có thể bị phá vỡ bởi nó. Chiều VC của các siêu phẳng trong không gian Rn là thường là n+1

Hinh 6 : Chiều VC

 Rủi ro của bài toán học phân loại có giám sát X ∈ R n ; Y ∈ { − 1,+1} , S = x1 , y1 , , xn , yn

{(

SVTH: Phan Thúc Bình

)

(

)}

24

Phân loại văn bản bằng phương pháp Support Vector Machines

Hàm

f s là ánh xạ từ tập X vào tập Y

fs : x

fs : Χ → Υ , Thì hàm rủi ro toàn cục của

R( f s ) = ∫

X ×Y

Trong đó:

y

f s (x) là

c( f s ( x), y ) P( x, y ) dxdy

P(x, y) = P(x).P(y | x).

c: là hàm thiệt hại (loss function),đo sự sai lệch của

f s ( x ) so với y.

 Rủi ro thực nghiệm Cho S = { ( x1 , y1 ) , , ( xn , yn )} , c là hàm thiệt hại của

f s (x)

f s (x) trên tập dữ liệu huấn luyện S được

Rủi ro thực nghiệm của hàm tính như sau:

Remp ( f s ) =

1 l ∑ c( f s ( xi ), yi ) l i =1

 Nguyên tắc tối thiểu rủi ro cấu trúc Tìm được một hàm

fs

để có thể tối thiểu giới hạn trên của rủi ro toàn cục.

Giới hạn trên của rủi ro toàn cục là:  2l  δ  h ln + 1 − ln  h  4 R ( f S ) ≤ Remp ( f S ) + l

Trong đó

h: là chiều VC của

fs

l: là số mẫu của tập huấn luyện S 1-δ : là giá trị của xác suất liên kết P(x,y) Để tối thiểu rủi ro toàn cục, người ta làm như sau: - Đầu tiên, chọn các hàm mà có rủi ro thực nghiệm là nhỏ nhất, tập các hàm này kí hiệu là Femp min . - Sau đó, chọn trong tập các hàm

SVTH: Phan Thúc Bình

Femp min hàm nào có chiều VC là nhỏ nhất. 25

Phân loại văn bản bằng phương pháp Support Vector Machines Bổ đề [Vapnik, 1982] Giả sử tập không gian giả thiết là tập các siêu phẳng có dạng

f s ( x ) = w.x + b . Nếu tất cả các véc tơ mẫu xi được bao trong hình cầu có bán kính R, và thỏa w.xi + b ≥ 1 . Đặt ║x║=A, khi đó chiều VC h của tập các siêu phẳng

[

]

fs

được giới hạn bởi:

d ≤ min ( R 2 A2 , n ) + 1 2.1.6 Ứng dụng SVM:  Phân loại văn bản (Text Categorization).  Tìm khuôn mặt (Face Detection).  Nhận dạng chữ viết tay (Hand Written Digit Recognition).  Nhận dạng khuôn mặt (Face Recognition).  Nhận dạng tiếng nói. …

2.2 Tiếp cận SMO : Từ bài toán tối đối ngẫu :

1 g ( α ) = α T Dα − α T 1 → min 2 yTα = 0  0 ≤ α ≤ C Chúng ta có giải bằng nhiều cách: giải trực tiếp bài toán đối ngẫu, phân rã vấn đề, hoặc bằng phương pháp SMO... Giải bài toán trên bằng phương pháp SMO : Để giải bài toán trên SMO sẽ chia bài toán thành các bài toán con. Ở mỗi bước sẽ giải bài toán con với những điều kiện tối ưu và sau đó xây dựng bài toán con mới. Điểm đặc biệt khi giải bằng phương pháp SMO là tốc độ nhanh, kết quả chính xác vì bài toán con chỉ có hai biến và sử dụng heuristic ở mỗi bước nên rất có hiệu quả.

SVTH: Phan Thúc Bình

26

Phân loại văn bản bằng phương pháp Support Vector Machines 2.2.1 Bài toán con và cách giải : Đầu tiên SMO chọn ra một tập con (với SMO tập con chỉ có hai ví dụ), xác định các vectơ hỗ trợ rồi kiểm tra tính tối ưu. Chỉ cần một vài vectơ là đủ để xác định cấu trúc của SVM.. Qui trình giải bài toán con như sau :

Tính α với η > 0

Tính α với η = 0

Kiểm tra

α

Cập nhật

α và b

Hình 7 : Qui trình giải bài toán con Khi hai ví dụ được chọn là cùng lớp:

s = 1 1 2 λ η + λ ( d1 − d 2 )α → min λ = u = −u 2  1 2 và  − α 1 ≤ λ ≤ C − α 1  L = max(−α 1 , α 2 − C )   R = min(C − α1 , α 2 ) α 2 − C ≤ λ ≤ α 2 Khi hai ví dụ được chọn là khác lớp:

 s = −1 1 2 λ η + λ [ ( d1 + d 2 )α − 2] → min λ = u = u 2  1 2 và  − α 1 ≤ λ ≤ C − α 1  L = max(−α 1 ,−α 2 )   R = min ( C − α1 , C − α 2 ) − α 2 ≤ λ ≤ C − α 2 Tiếp theo ta tính η : η

SVTH: Phan Thúc Bình

= d ii − 2 sd ij + d jj

27

Phân loại văn bản bằng phương pháp Support Vector Machines

Với η > 0 thì

λ* =

sy j e j − yi ei

η

λ = R nếu λ* > R  Ta chọn λ như sau: λ = L nếu λ* < L λ = λ* còn lại 

λ = R λ = L

Với η = 0 thì 

Cuối cùng ta tính các

nếu syjej – yiei >0 ngược lại

α (các nhân tử Lagrange) như sau : α1 = λ α2 = s * λ

* Lưu ý : Các αi được chọn phải đảm bảo làm cho g (α ) giảm thực sự tại mỗi bước. 2.2.2 Heuristics chọn các nhân tử Lagrange : Với điều kiện SMO tối ưu, tại mỗi bước các nhân tử Lagrange có sự thay đổi và có ít nhất một nhân tử Lagrange vi phạm điều kiện KKT thì sau mỗi bước hàm mục tiêu sẽ giảm theo theo định lý Osuna. Độ hội tụ vì thế mà được đảm bảo. Để tăng tốc độ hội tụ, SMO sử dụng heuristics để chọn hai nhân tử cùng tối ưu. Có hai heuristics chọn các nhân tử Lagrange khác nhau: một cho nhân tử Lagrange thứ nhất và một cho nhân tử thứ hai. - Heuristic chọn nhân tử Lagange thứ nhất: + Một vòng lặp bên ngoài đầu tiên sẽ lặp trên toàn bộ tập huấn luyện tìm ra mẫu vi phạm điều kiện KKT (1). + Sau đó duyệt qua toàn bộ tập huấn luyện và chọn ra các mẫu mà nhân tử Lagrange khác 0 và khác C (tức là các mẫu không nằm trên biên) các mẫu này lại được kiểm tra xem có vi phạm điều kiện KKT không, các mẫu vi phạm có thể được chọn để tối ưu. Ở bước ngày lặp lại quá trình

SVTH: Phan Thúc Bình

28

Phân loại văn bản bằng phương pháp Support Vector Machines duyệt qua các mẫu không nằm trên biên cho tới khi không còn mẫu nào vi phạm điều kiện KKT với sai số

ε

(2).

+ Tiếp theo SMO sẽ quay lại từ đầu, thực hiện lặp trên toàn bộ tập huấn luyện thực hiện luân phiên (1), (2) cho đến khi không còn mẫu nào vi phạm điều kiện KKT với sai số

ε , sau đó thuật toán kết thúc.

Ở heuristic chọn đầu tiên này phần lớn thời gian tập trung vào tìm những mẫu vi phạm điều kiện KKT mà những mẫu này thường tập trung ở tập con không nằm trên biên. Theo thuật toán SMO thực hiện thì những mẫu nào nằm trên biên sẽ ở biên, còn những mẫu nào không nằm trên biên sẽ được di chuyển thành mẫu khác để đạt được tối ưu. Vì vậy, thuật toán SMO lặp trên tập con không nằm trên biên cho tới khi tập con này tự phù hợp. Sau đó SMO sẽ tìm bất kì một mẫu nào trên biên vi phạm KKT để tối ưu với tập con không nằm trên biên. Điều kiện KKT được kiểm tra với sai số

ε , thường thì ε

được thiết lập

khoảng 10-3.

 Tìm i vi phạm cặp ràng buộc đối ngẫu • Ưu tiên 0 < α j < C

Lặp trên toàn bộ các mẫu

Lặp trên toàn bộ với 0 < α i < C

Hinh 8: Tìm i vi phạm cặp ràng buộc đối ngẫu - Heuristic chọn nhân tử Lagange thứ hai: Như vậy nhân tử Lagrange thứ nhất đã được chọn, SMO chọn nhân tử Lagrange sao cho sắp sỉ E1 − E2 là lớn nhất. Các giá tri E của mỗi mẫu không nằm trên biên trong tập huấn luyện sẽ được lưu lại sau đó chọn giá trị lỗi mà làm cho trị tuyệt đối trên lớn nhất. Nếu E1 dương thì SMO chọn mẫu với E2 nhỏ nhất, ngược lại nếu E1 âm thì SMO chọn mẫu có E2 lớn nhất.

SVTH: Phan Thúc Bình

29

Phân loại văn bản bằng phương pháp Support Vector Machines Trong số ít trường hợp, SMO không thể make positive progress bằng cách sử dụng giải thuật môt tả như trên. Ví dụ, positive progress không thể được tạo nếu các ví dụ huấn luyện thứ nhất và thứ hai chia sẻ các vector nhập vào xác định x nhằm tạo ra hàm đối tượng để trở thành nhận dạng chung.Trong trường hợp này, SMO sử dụng một hệ thống cấp bậc của giải thuật chọn lựa nhân tử thứ hai cho đến khi nó tìm thấy một cặp nhân tử Lagrange có thể tạo ra positive progress. Positive progress có để được quyết định bởi việc tạo ra một kích thước bước không trên tối ưu nối của hai nhân tử Lagrange. Hệ thống cấp bậc của giải thuật chọn lựa nhân tử thứ hai bao gồm những điều sau đây: Nếu heuristic trên không tạo ra được positive progress thì SMO bắt đầu làm đi làm lại thông qua những ví dụ không giới hạn, tìm kiếm một ví dụ thứ hai có thể tạo nên positive progress thì SMO lặp trên những mẫu không nằm trên biên và tìm kiếm mẫu thứ hai mà có thể make positive progress. Nếu không tìm được phần tử không nằm trên biên nào make positive progress thì SMO bắt đầu lặp trên toàn bộ tập huấn luyện cho tới khi một mẫu được tìm thấy để make positive progress. Cả hai quá trình lặp trên những mẫu không nằm trên biên và lặp trên toàn bộ tập huấn luyện có thể bắt đầu tại những vị trí ngẫu nhiên. Trong trường hợp xấu không có mẫu thứ hai nào thỏa mãn thì mẫu thứ nhất được dừng lại và SMO tiếp tục với việc lựa chọn một mẫu thứ nhất khác.

0 <αj
Cực đại ∆



Tìm j vi phạm cặp ràng buộc đối ngẫu

• Ưu tiên 0 < α j < C • Trong đó ưu tiên

∆ = ei − e j lớn nhất

0 <αj
α j còn lại Từ j0 còn lại

Hình 9: Tìm j qui phạm cặp ràng buộc đôi ngẫu

SVTH: Phan Thúc Bình

30

Phân loại văn bản bằng phương pháp Support Vector Machines 2.2.3 Phương pháp tính giới hạn b tại mỗi bước: Giới hạn b được tính lại sau mỗi bước, vì thế mà điều kiện KKT được thực thi cho cả hai mẫu. Giá trị giới hạn b1, b2 được tính như sau:

    new.clipped − α1 ) K ( x1 , x2 ) + y2 (α 2 − α 2 ) K ( x1 , x2 ) + b     new new.clipped b2 = E2 + y1 (α1 − α1 ) K ( x1 , x2 ) + y2 (α 2 − α 2 ) K ( x2 , x2 ) + b b1 = E1 + y1 (α1

Với điều kiện là α 1 Nếu α1

new

,α 2

new

new

new

,α 2

new

phải không nằm trên biên. Khi đó b= b1= b2

nằm trên biên và

L ≠ H thì giới hạn b sẽ nằm giữa b1 và b2

2.2.4 Vấn đề hội tụ: Tốc độ hội tụ của thuật toán sẽ nhanh hơn nếu ta nới lỏng các ràng buộc, tức là nới lỏng các sai số

ε . Sai số ε

cho phép thường khoảng 10-3.

Thuật toán SMO (và các thuật toán SVM khác) sẽ không hội tụ nhanh nếu yêu cầu kết quả đầu ra có độ chính xác quá cao. - Độ phức tạp của thuật toán là: O(n).

2.3 Bài toán phân loại văn bản : 2.3.1 Định nghĩa: Phân loại tự động văn bản là việc gán nhãn phân loại lên một văn bản mới dựa trên mức độ tương tự của văn bản đó so với các văn bản đã được gán nhãn trong tập huấn luyện. 2.3.2 Các kiểu phân loại : 2.3.2.1 Phân loại văn bản đơn nhãn và đa nhãn Ràng buộc khác biệt ở đây có lẽ bị phụ thuộc vào nhiệm vụ phân loại (TC task) vào ứng dụng cụ thể . Chúng ta có thể lấy ví dụ như sau: cho trước 1 số nguyên k (hoặc lớn hơn k hoặc nhỏ hơn k), k thành phần của tập C (tập các loại) được gán cho mỗi tài liệu d j ∈ D . - Trường hợp chỉ có chính xác 1 phân lớp (category) được gán cho tài liệu d j ∈ D được gọi là phân loại nhãn đơn (single-label, nonoverlapping category).

SVTH: Phan Thúc Bình

31

Phân loại văn bản bằng phương pháp Support Vector Machines - Trường hợp có 1 số lượng nhãn (từ 0 cho đến C ) được gán cho tài liệu d j ∈ D được gọi là phân loại đa nhãn (multi-label, overlapping category).

- Trường hợp đặc biệt của phân loại nhãn đơn là phân loại nhị phân trong đó mỗi tài liệu d j ∈ D có thể được gán cho bộ phân loại ci hay không thuộc bộ phân loại ci. Trên quan điểm lý thuyết, trường hợp phân loại đơn nhãn (nhị phân) tổng quát hơn trường hợp đa nhãn. 1 thuật toán (algorithm) cho phân lớp đơn nhãn cũng có thể áp dụng cho phân lớp đa nhãn, chỉ đơn giản là chúng ta biến đổi vấn đề phân lớp đa nhãn trên tập {c1 ,, C } nhãn thành C vấn đề phân lớp đơn nhãn độc lập với nhau. Tuy nhiên, điều ngược lại là không đúng, 1 thuật toán cho phân lớp đa nhãn không thể áp dụng cho phân lớp đơn nhãn (cũng như phân lớp nhị phân). 2.3.2.2 Phân loại văn bản phụ thuộc lớp/loại văn bản so với phụ thuộc tài liệu Có rất nhiều cách khác nhau để sử dụng bộ phân loại văn bản (text classifier). Cho trước tài liệu d j ∈ D , chúng ta muốn tìm tất cả các lớp ci ∈ C mà tài liệu thuộc vào, cách này được gọi là phân loại dựa vào tài liệu (documentpivoted categorization-DPC). Ngược lại, nếu cho trước ci ∈ C , chúng ta muốn tìm tất cả các tài liệu d j ∈ D mà thuộc vào nó, cách này được gọi là phân loại dựa vào lớp (loại) văn bản (category-pivoted categorization-CPC). Sự khác biệt này thể hiện rõ ở thực tế hơn là ở khái niệm trừu tượng. Trên thực tế DPC được dùng nhiều hơn CPC. 2.3.2.3 Phân loại văn bản “cứng” so với “mềm” Trong khi việc tự động hoàn toàn của quá trình phân lớp cần 1 quyết định T hay F cho mỗi cặp (di,cj) thì việc tự động từng phần của tiến trình có lẽ lại cần những nhu cầu khác nhau. - Phân loại văn bản “cứng” (hard TC) tức là cung cấp 1 giá trị trong {T,F} cho biết di có hay không có nằm trong cj. Điều này rất hữu ích cho các ứng dụng phân lớp tự động (autonomous).

SVTH: Phan Thúc Bình

32

Phân loại văn bản bằng phương pháp Support Vector Machines - Phân loại văn bản mềm (soft TC) tức là cung cấp 1 giá trị trong [0,1] cho biết mức độ tin cậy của hệ thống khi quyết định sự phụ thuộc của dj vào trong cj. Điều này lại phù hợp hơn với các ứng dụng phân lớp tương tác (interactive). 2.3.3 Ứng dụng của phân loại văn bản : - Tổ chức các trang web thành hệ thống cấp bậc. - Phân vùng để trích rút thông tin. - Phân loại email thành các danh mục khác nhau (spam hay không spam). - Tìm ra mối quan tâm của người sử dụng. - Tóm tắt thông tin. - Phân loại thông tin. 2.3.4 Quá trình phân loại văn bản :

Văn bản cần phân loại

Tiền xử lý

Tạo chỉ mục

Kết quả

Thuật toán phân loại

Chọn đặc trưng

Hình 10: Quá trình phân loại văn bản

2.3.4.1 Tiền xử lý văn bản : Đây là quá trình làm sạch văn bản bằng. Chuyển văn bản nhập vào thành các dạng biểu diển phù hợp cho công tác phân lớp. Ví dụ : Nếu file đưa vào ở dạng *.html thì ta sẽ xóa bỏ các tag HTML hoặc các tag khác. Ở giai đoạn này các đặc trưng liên quan sẽ được rút trích lại từ các tài liệu nhập vào. Tất cả các từ được trong tài liệu được xem là các đặc trưng khả thi. Sau đó các từ này sẽ được qua một bước lọc bỏ các đặc trưng không mang thông SVTH: Phan Thúc Bình

33

Phân loại văn bản bằng phương pháp Support Vector Machines tin hữu ích. Các từ chức năng hay các phụ từ hư từ (Ví dụ : "dẫu sao", "của" , "sao cơ"...) sẽ được lược bỏ để giảm số lượng đặc trưng vốn đã rất lớn của văn bản đồng thời tăng hiệu năng của quá trình phân loại sau này. 2.3.4.2 Tạo ra chỉ mục : Tạo ra chỉ mục bằng việc sắp xếp lại các trọng số của từ. Đây là giai đọan biểu diễn văn bản thành vector đặc trưng hay còn gọi là quá trình trọng số hóa đặc trưng. Xem mỗi văn bản di tương ứng là một vectơ đặc trưng d i ( TF ( w1 ), TF ( w2 ),..., TF ( wn ) ) trong không gian các từ

W n ( wi

tương ứng là

một từ, một đặc trưng và cũng chính là một chiều trong không gian).

Hình 11 : Biểu diễn văn bản sang vectơ Cho tập đặc trưng F = { f1 , f 2 ,..., f D } tập các lớp C = { c1 , c 2 ,..., c n } , một đặc trưng f ∈ F và tài liệu d sẽ được trọng số hóa theo các công thức sau :  TF (Term Frequency): Dựa vào tần suất xuất hiện của đặc trưng. Ví dụ: TF(f,d) là số lần xuất hiện của đặc trưng f trong tài liệu d.  TF_IDF (Term Frequency Inverse Document Frequency): Dựa vào tần suất nghịch đảo văn bản, được tính theo công thức sau:

SVTH: Phan Thúc Bình

34

Phân loại văn bản bằng phương pháp Support Vector Machines

 D   IDF ( f ) = log  DF ( f )  

 D   TF _ IDF ( f , d ) = TF ( f , d ) * IDF ( f ) = TF ( fd ) * log   DF ( f )  Trong đó: D : là số văn bản trong tập huấn luyện.

DF ( f ) : số văn bản chứa đặc trưng f. TF ( f , d ) : tần số xuất hiện của đặc trưng f trong văn bản d.

TF _ IDF ( f , d ) : trọng số của đặc trưng f trong văn bản d.  logTF_IDF

ω fd =

Với

l df × log

D df r

 l D  l × log ∑ r df r r∈F 

  

2

0 neu tf fd = 0 d l = + f  log( tf fd + 1) neu tf fd ≠ 0 + ω fd : trọng số của đặc trưng f trong văn bản d

Ngoài ra còn có : TF_IWF , TF_CHI, TF_CRF… Các đặc trưng của văn bản khi biểu diễn dưới dạng vector : - Số chiều không gian đặc trưng thường rất lớn (trên 10000). - Có các đặc trưng độc lập nhau, sự kết hợp các đặc trưng này thường không có ý nghĩa trong phân loại. - Đặc trưng rời rạc : vector d i có rất nhiều giá trị 0 do có nhiều đặc trưng không xuất hiện trong văn bản d i - Hầu hết các văn bản có thể được phân chia một cách tuyến tính bằng các hàm tuyến tính. SVTH: Phan Thúc Bình

35

Phân loại văn bản bằng phương pháp Support Vector Machines 2.3.4.3 Chọn lựa đặc trưng : Thực chất của quá trình này là giảm số chiều của vector đặc trưng bằng cách bỏ đi những thành phần đặc trưng không quan trọng. Quá trình này rất quan trọng vì một văn bản gồm rất nhiều từ nên khi biểu diễn sang vector thì nó sẽ vector có số chiều rất lớn, trong đó thành phần dư thừa cũng rất nhiều. Vì vậy ta áp dụng các phương pháp lựa chọn đặc trưng để giảm số chiều của vector đặc trưng mà không mất đi độ chính xác. Cho kho ngữ liệu, một cách toán học nó được biểu diễn bởi một ma trận d x nX, trong đó d là số lượng các hạng hay các đặc trưng, n là số lượng các tài liệu trong kho ngữ liệu. Mỗi tài liệu là một véctơ cột xi , i=1,2,..,n. X T là ma trận chuyển vị của X ∈ R dxn . Vấn đề giảm số chiều thực chất là tìm ánh xạ

f : R d → R p với p là chiều của dữ liệu sau khi được giảm, p sẽ rất nhỏ so với p d d. Như vật tài liệu xi ∈ R sẽ được đổi thành yi = f ( xi ) ∈ R .

Theo phương pháp rút trích đặc trưng thì vấn đề giảm chiều là tìm ma trận T p chuyển đổi tối ưu W ∈ R dxp để mà y i = f ( xi ) = W xi ∈ R .

Mặt khác theo các phương pháp chọn lựa đặc trưng, mục đích của việc giảm

(

chiều là tìm tập đặc trưng ki i=1,2,...,p sao cho y i = f ( xi ) = xik1 , xik 2 ,..., xikp

)

T

.

Các phương pháp lựa chọn đặc trưng cơ bản như : 1, Mutual Information (MI) Thước đo độ tương tự đo sự xuất hiện đồng thời hay không đồng thời của một từ t trong nhãn c được tính như sau:

MI ( t , c ) = log

⇔ MI ( t , c ) ≈ log

pr (t , c ) pr (t ). pr (c)

A* N ( A + C )( A + B )

A: là số lần t và c xuất hiện đồng thời B: là số lần t xuắt hiện mà không xuất hiện c C: là số lần c xuất hiện mà không xuất hiện t

SVTH: Phan Thúc Bình

36

Phân loại văn bản bằng phương pháp Support Vector Machines N: là tổng số văn bản 2, Chi-Square

(

) (

) ( ( )

)

| Tr | [ P( t k , ci ).P t k , c i − P t k , c i .P t k , ci ]2 χ (t k , ci ) = P ( t k ) .P t k .P ( c i ) .P c i 2

( )

Trong đó: |Tr| : tổng số tài liệu đang xét.

(

)

P t k , c i : xác suất khi chọn ngẫu nhiên tài liệu x, đặc trưng t k sẽ

không xuất hiện trong x, và x không thuộc về phân lớp ci .

( ) P (t , c ) : xác suất khi chọn ngẫu nhiên tài liệu x, đặc trưng t

P t k , c i : xác suất xuất hiện tk với điều kiện không thuộc lớp ci k

i

k

sẽ

không xuất hiện trong x, và x thuộc về phân lớp ci . P( t k , ci ) : xác suất khi chọn ngẫu nhiên tài liệu x, đặc trưng tk sẽ

xuất hiện trong x, và x thuộc về phân lớp ci . P (t k ) : xác suất xảy ra đặt trưng t k P ( ci ) : xác suất xảy ra phân lớp ci

3, Odds ratio

OR(t k , ci ) =

P(t k | ci ).(1 − P(t k | ci )) (1 − P(t k | ci ).P(t k | ci ))

4, Information gain

IG (t k , ci ) =

∑ ∑

P( t , c ). log

c∈{ci , c i } t∈{t k ,t k }

P( t , c ) P( t ).P( c )

5, GSS coefficient

(

) (

_ _  GSS (t k , ci ) = P( t k , ci ).P t k , c i  − P t k , c i .P t k , ci  

)

6, OCFS SVTH: Phan Thúc Bình

37

Phân loại văn bản bằng phương pháp Support Vector Machines Đây là phương pháp một trong các phương pháp lựa chọn đặc trưng tốt nhất hiện nay. Phương pháp OCFS dựa trên nền tảng là giải thuật Orthogonal Centroid (OC). Để hiểu rõ hơn về phương pháp OCFS, chúng ta hãy tìm hiểu sơ qua về giải thuật OC. Thuật toán OC Thuật toán OC được đề nghị gần đây được xem như là một thuật toán rút trích đặc trưng có giám sát. Nó tận dụng phép biến đổi trực giao trên trọng tâm . Thuật toán này đã được chứng minh là rất hiệu quả với các vấn đề phân lớp véctơ dữ liệu dưới dạng văn bản (text data) và nó dựa trên phép tính toán không gian véctơ trong đại số tuyến tính . Thuật toán này cũng có mục tiêu là tìm ra được ma trận biến đổi W ∈ R dxp , tiêu chuẩn J(W) được tính như sau :

arg max J (W ) = arg max trace(W T S bW ) với giả thuyết W T W = I c

Và Sb = ∑ j =1

nj n

(m

j

− m )( m j − m )

T

Trong đó :  mj là vector trung bình được tính theo công thức  nj là kích thước của lớp j  m là véc tơ trung bình của tất cả các tài liệu, được tính theo công thức sau:

1 n 1 c m = ∑ xi = ∑ n j m j n i =1 n j =1 Thuật toán OCFS Trong các thành phần công thức được định nghĩa như trong phần OC, chỉ khác là ma trận là ma trận nhị phân mà mỗi cột chỉ có một phần tử khác 0, ta định nghĩa tập là tập các chỉ mục của đặc trưng, mặt khác ta có: ~

~

~

~

trace(W S b W ) = ∑i = `W i S b W i =∑i =1 ∑ j = ` p

T

p

c

nj

(m n

ki

j

− m ki

)

2

Như vậy thực chất của OCFS là tìm tập K để làm cực đại

SVTH: Phan Thúc Bình

38

Phân loại văn bản bằng phương pháp Support Vector Machines

nj

∑ ∑ n (m p

i =1

c

ki

j =`

− m ki

j

)

2

Các bước tiến hành thuật toán OCFS : - Bước 1: Tính centroid mi, i=1,2,…,c của mỗi lớp cho dữ liệu huấn luyện. - Bước 2: Tính centroid m của tất cả các mẫu huấn luyện - Bước 3: Tính điểm cho từng đặc trưng i theo công thức

s (i ) = ∑

nj n

(m

i

j

−m

i

)

2

- Bước 4: Lấy k đặc trưng có điểm cao nhất. Chọn lựa đặc trưng: Giả sử các đặc trưng được tính và được sắp xếp như sau:

p

s (k1 ) ≥ s (k2 )... ≥ s (kd ) . Hàm E(p) được tính như sau:

E ( p) =

∑ s(k ) j =1 d

∑ s (k ) i =1

những p được chọn phải thỏa mãn p = arg min E ( p ) sao cho

j

,

i

E ( p ) ≥ T , ví

dụ T = 80%. Đánh giá độ phức tạp: Độ phức tạp của thuật toán OCFS là O(cd). Được đánh giá là tốt hơn các thuật toán trước bởi thời gian thực hiện hiện ngắn hơn (thời gian chủ yếu của thuật toán dùng để tính điểm các đặc trưng) và dễ cài đặt hơn. 2.3.4.4 Xây dựng thuật toán phân lớp : Có rất nhiều phương pháp để thực hiện phân lớp mang lại hiệu quả cao như : Support Vector Machines, k-Nearest Neighbour, Neural Network, Naive Bayes. Trong đồ án này phương pháp Support Vector Machines (SVM) được chọn để thực hiện quá trình phân lớp. SVM được xem là một trong những phương pháp phân loại văn bản tốt nhất hiện nay. Bởi lẽ SVM phù hợp với bài toán phân loại văn bản vì nó có khả năng đáp ứng các yêu cầu như:  Không gian đầu vào có số chiều rất lớn. SVTH: Phan Thúc Bình

39

Phân loại văn bản bằng phương pháp Support Vector Machines  Các vector văn bản là thưa.  Các đặc trưng rời rạc, ít liên hệ lẫn nhau. 2.3.4.5 Kết quả, đánh giá độ chính xác : Để đánh giá hiệu quả phân loại văn bản người ta dùng các chỉ số độ thu recall và độ chính xác precision.

Recall = a / (a + c) Precision = a / (a + b) •

a: số lượng văn bản được gán nhãn đúng cho một lớp.

•

b: số lượng văn bản được gán nhãn không đúng cho một lớp.

•

c: số lượng văn bản không đúng được lọai bỏ từ một lớp.

 Giá trị recall cho ta biết tỉ lệ văn bản đúng được nhận ra .  Precision cho ta biết tỉ lệ văn bản đúng trong số các văn bản máy nhận biết.

SVTH: Phan Thúc Bình

40

Phân loại văn bản bằng phương pháp Support Vector Machines

3 PHẦN III : THIẾT KẾ - CÀI ĐẶT 3.1 Thuật toán SMO : 3.1.1 Sơ đồ lớp : mainSVM

linearSvm

noneLinearSvm

Hinh 12: Sơ đồ lớp cài đặt SMO 3.1.2 Cài đặt 3.1.2.1 Lớp mainSVM  Chức năng : Chức năng chính là thực hiện giải thuật SMO để giải bài toán SVM ở trên. Gồm các bước như : chia bài toán con, giải bài toán con, các heuristic tìm các nhân tử Lagrane. Trong lớp này có chứa các hàm ảo để các lớp khác kế thừa trong các trường hợp phân tách tuyến tính và phi tuyến.  Cài đặt : // Phương thức chính, tìm phần tử vi phạm điều kiện KKT thứ nhất public virtual void mainSMO() // Tìm phần tử vi phạm điều kiện KKT thứ hai private bool FindJ(int i1) // Giải phương trình tính các giá trị α và b private bool TakeStep(int i1, int i2)

3.1.2.2 Lớp linearSvm  Chức năng : SVTH: Phan Thúc Bình

41

Phân loại văn bản bằng phương pháp Support Vector Machines Thừa kế lớp mainSVM thực hiện phân tách tuyến tính.

 Cài đặt : // Cập nhật các giá trị của ma trận W protected override void updateW(int i1, int i2, int y1, int y2, float a1, float a2, float alph1, float alph2) 3.1.2.3 Lớp noneLinearSvm  Chức năng : Thừa kế lớp mainSVM thực hiện phân tách tuyến tính

 Cài đặt : // Các hàm kernel phục vụ cho phân tách phi tuyến protected override float Kernel(float[] vector1, float[] vector2)

3.2 Module phân loại văn bản :  Qui trình huấn luyện và kiểm nghiệm SVTH: Phan Thúc Bình

42

Phân loại văn bản bằng phương pháp Support Vector Machines

Ngữ liệu huấn luyện

Tiền xử lý

Biểu diễn văn bản thành vector

Chọn lựa và rút trích đặc trưng

Xây dựng bộ phân lớp

Dữ liệu phân lớp

Bộ phân lớp văn bản

Chủ đề văn bản

Văn bản cần gán nhãn

Hình 13: Mô hình thuật toán học và phân loại.

SVTH: Phan Thúc Bình

43

Phân loại văn bản bằng phương pháp Support Vector Machines 3.2.1 Sơ đồ lớp :

Doc2Vector

proClassify

Hình 14 : Sơ đồ lớp moudule phân loại văn bản 3.2.2 Cài đặt : 3.2.2.1 Lớp Doc2Vector  Chức năng : Biểu diễn văn bản đầu vào thành vectơ trọng số. Gồm các chức năng như : chuyển văn bản thành các đặc trưng.  Cài đặt: // Tính trọng số của các đặc trưng. public void doc2vector(List<string> lw) 3.2.2.2 Lớp proClassify :  Chức năng : Thực hiện huấn luyện và kiểm nghiệm.  Cài đặt: // Kiểm nghiệm một văn bản. public float classify(string str) 3.2.2.3 Lớp preProcess  Chức năng : Thực hiện chức năng tiền xử lý văn bản. Gồm các thao tác như loại bỏ dấu câu, loại bỏ từ vô nghĩa.  Cài đặt: // Loại bỏ từ vô nghĩa. public List<string> rmStopwordString(string str) // Loại bỏ dấu câu public string rmPunctuation(string st) SVTH: Phan Thúc Bình

44

Phân loại văn bản bằng phương pháp Support Vector Machines

3.3 Giao diện chương trình : Phân loại một văn bản : Chọn đường dẫn văn bản hoặc gõ trực tiếp nội dung vào.

Hình 15: Phân loại từng văn bản

SVTH: Phan Thúc Bình

45

Phân loại văn bản bằng phương pháp Support Vector Machines Phân loại một thư mục chứa nhiều văn bản

Hình 16 : Phân loại cả thư mục

SVTH: Phan Thúc Bình

46

Phân loại văn bản bằng phương pháp Support Vector Machines Minh họa thuật toán SMO

Hình 17: Minh họa thuật toán SMO Các lớp giao diện : mainTC : Lớp giao diện màn hình chính. frmClassify : Lóp giao diện màn hình phân loại một văn bản frmClassifyAll : Lóp giao diện màn hình phân loại cả thư mục. frmSVM : Lóp giao diện màn hình thuật toán SMO.

SVTH: Phan Thúc Bình

47

Phân loại văn bản bằng phương pháp Support Vector Machines

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. Kết luận : Sau thời gian nghiên cứu và thực hiện đề tài, em đã có thêm hiểu biết về phương pháp SVM cũng như cách giải nó bằng SMO. Trong đề tài này, em đã cài đặt được thuật toán SMO với độ chính xác khá cao. Đề tài cũng đã phân loại được văn bản nhưng mới chỉ dừng ở hai chủ đề minh họa là tin học, thể thao và chỉ ở những file có định dạng là *.txt, *.html. 2. Hướng phát triển : Ứng dụng phân loại văn bản ở đề tài này chỉ mới dừng lại ở mục đích kiểm nghiệm thuật toán SMO và số chủ đề chỉ có hai. Vì để có được một chương trình phân loại văn bản tự động (nhất là phân loại văn bản tiếng Việt) hoàn chỉnh thì cần phải hoàn thiện thêm rất nhiều vấn đề : -

Cần cải thiện bài toán tách từ vì độ chính xác của bài toán tách từ quyết định hiệu suất phân loại của cả bài toán

-

Bổ sung thêm nhiều chủ đề.

SVTH: Phan Thúc Bình

48

Phân loại văn bản bằng phương pháp Support Vector Machines

TÀI LIỆU THAM KHẢO [1] Dr. Tie-Yan Liu - SVM and Its Applications to Text Classification. [2] S.S.Keerthi, S.K. Shevade, C. Bhattacharyya, K.R.K Murthy - Improvements to Platt’s SMO Algorithm for SVM Classifier Design. [3] John C. Platt - SMO : A Fast Algorithm for Training SVM. [4] Jun Yan, Ning Liu, Benyu Zhang, Shuicheng Yan,Zheng Chen, Qiansheng Cheng, Weiguo Fan, Wei-Ying Ma - OCFS: Optimal Orthogonal Centroid Feature Selection for Text Categorization. [5] Hoàng Công Duy Vũ, Nguyễn Lê Nguyên – Luận văn Tìm kiếm văn bản theo chủ đề. [6] Seminar về Support Vector Machines do thầy Huỳnh Văn Đức tổ chức tại Đại học Kinh tế TP.HCM

SVTH: Phan Thúc Bình

49