Tài liệu Xử lý văn bản tiếng việt theo mô hình tập thô dung sai

TrÇn quang 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 c«ng nghÖ th«ng tin ngµnh : c«ng nghÖ th«ng tin Xö lý v¨n b¶n tiÕng viÖt Theo m« h×nh tËp th« dung sai TrÇn quang 2007 - 2009 Hµ Néi 2010 Hµ Néi 2010 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai 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 Xö Lý V¡N B¶N TIÕNG VIÖT THEO M¤ H×NH TËP TH¤ DUNG SAI ngµnh : c«ng nghÖ TH¤NG TIN m∙ sè:23.04.3898 TRÇN QUANG Người hướng dẫn khoa học : PGS. TS. NguyÔn ngäc b×nh Hµ Néi 2010 Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 1/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai LỜI CAM ĐOAN Tôi – Trần Quang – cam đoan Luận văn này là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn của PGS.TS.Nguyễn Ngọc Bình. Các kết quả nêu trong Luận văn là trung thực, không phải là sao chép toàn văn của bất kỳ công trình nào khác. Hà Nội, ngày tháng năm Tác giả Luận văn Trần Quang Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 2/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai MỤC LỤC DANH MỤC CÁC THUẬT NGỮ..................................................................................................................... 5 DANH MỤC CÁC BẢNG.................................................................................................................................. 6 DANH MỤC CÁC HÌNH................................................................................................................................... 7 LỜI NÓI ĐẦU ..................................................................................................................................................... 8 Chương 1 Tổng quan về khai phá dữ liệu........................................................................................................ 9 1.1. Khai phá dữ liệu – Data Mining............................................................................................................... 9 1.2. Tiền xử lý dữ liệu.................................................................................................................................... 12 1.3. Phân lớp và dự báo – Classification and Prediction .............................................................................. 12 1.3.1. Giới thiệu ........................................................................................................................................ 12 1.3.2. Support Vector Machines............................................................................................................... 15 1.3.2.1. SVMs với dữ liệu khả tách tuyến tính (linearly separable).....................................................................16 1.3.2.2. SVMs với dữ liệu không khả tách tuyến tính (linearly inseparable) ......................................................20 1.4. Phân nhóm dữ liệu .................................................................................................................................. 22 1.4.1. Giới thiệu ........................................................................................................................................ 22 1.4.2. Phân loại các phương pháp Clustering ......................................................................................... 24 1.4.3. Một số phương pháp Clustering .................................................................................................... 27 1.5. Các ứng dụng và xu hướng trong khai phá dữ liệu................................................................................ 31 Chương 2 Tập thô và ứng dụng....................................................................................................................... 34 2.1. Lý thuyết tập thô..................................................................................................................................... 34 2.1.1. Hệ thông tin .................................................................................................................................... 35 2.1.2. Quan hệ bất khả phân .................................................................................................................... 37 2.1.3. Xấp xỉ tập hợp ................................................................................................................................ 38 2.1.4. Thành viên thô – Rough Membership ............................................................................................ 42 2.1.5. Phụ thuộc giữa các thuộc tính ....................................................................................................... 43 2.1.6. Rút gọn thuộc tính .......................................................................................................................... 44 2.1.7. Ma trận phân biệt được và hàm phân biệt được ........................................................................... 50 2.1.8. Sự quan trọng của các thuộc tính và các rút gọn xấp xỉ ............................................................... 53 2.2. Các ứng dụng của tập thô ....................................................................................................................... 56 2.3. Mô hình tập thô dung sai ........................................................................................................................ 57 Chương 3 Một số kỹ thuật trong khai phá dữ liệu văn bản......................................................................... 60 3.1. Các mô hình biểu diễn văn bản .............................................................................................................. 60 3.1.1. Mô hình không gian vector – Vector Space Model ....................................................................... 60 3.1.1.1. Document Indexing..................................................................................................................................61 3.1.1.2. Feature Weighting....................................................................................................................................63 3.1.1.3. Similarity Coefficients .............................................................................................................................64 3.1.2. Mô hình tập mờ - Fuzzy Set Model ................................................................................................ 65 3.1.2.1. Lý thuyết tập mờ ......................................................................................................................................65 3.1.2.2. Biểu diễn văn bản dựa trên khái niệm mờ ...............................................................................................66 3.1.3. Mô hình xác suất – Probabilistic Model........................................................................................ 68 3.2. Công thức xác định hiệu năng xử lý văn bản......................................................................................... 71 3.3. Phân nhóm văn bản – Text Clustering ................................................................................................... 72 3.3.1. Giới thiệu ........................................................................................................................................ 72 3.3.2. Các ứng dụng của lập nhóm văn bản ............................................................................................ 73 3.4. Phân loại văn bản – Text Classification................................................................................................. 73 3.4.1. Giới thiệu bài toán phân loại văn bản ........................................................................................... 73 3.4.1.1. Tổng quan phân loại văn bản...................................................................................................................73 3.4.1.2. Nền tảng học máy trong bài toán phân loại văn bản ...............................................................................74 3.4.2. Một số phương pháp phân loại văn bản ........................................................................................ 76 3.4.2.1. Decision Tree ...........................................................................................................................................76 3.4.2.2. K - Nearnest Neighbor .............................................................................................................................76 Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 3/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai 3.4.2.3. Naïve Bayes .............................................................................................................................................78 3.4.2.4. Support Vector Machines ........................................................................................................................80 3.5. Tóm tắt văn bản – Text Summarization................................................................................................. 81 3.6. Phát hiện xu hướng văn bản – Text Trend Detection ............................................................................ 81 3.7. Tìm kiếm văn bản – Text Retrieval........................................................................................................ 81 Chương 4 Mô hình tập thô dung sai trong xử lý cơ sở dữ liệu văn bản ..................................................... 83 4.1. Bộ khung của hệ thống khai phá dữ liệu văn bản dựa trên mô hình TRSM ......................................... 83 4.2. Xử lý văn bản tiếng Anh......................................................................................................................... 85 4.2.1. Mô hình tập thô dung sai trong biểu diễn văn bản........................................................................ 85 4.2.2. Nonhierarchical Document Clustering dựa trên mô hình tập thô dung sai ................................. 87 4.2.2.1. Giải thuật ..................................................................................................................................................87 4.2.2.2. Biểu diễn cluster – cluster representation................................................................................................88 4.2.2.3. Độ tương tự giữa các tài liệu và giữa các biểu diễn cluster ....................................................................90 4.2.3. Hierarchical Document Clustering dựa trên mô hình tập thô dung sai ....................................... 91 4.3. Xử lý văn bản tiếng Việt......................................................................................................................... 92 4.3.1. Một số vấn đề chung trong xử lý văn bản Tiếng Việt .................................................................... 92 4.3.1.1. Một số đặc trưng của Tiếng Việt .............................................................................................................92 4.3.1.2. Các bước tiền xử lý văn bản ....................................................................................................................94 4.3.1.3. Một số phương pháp tách thuật ngữ trong văn bản Tiếng Việt ..............................................................95 4.3.1.4. Một số kỹ thuật giảm chiều văn bản........................................................................................................98 4.3.1.4.1. Loại bỏ từ dừng ...............................................................................................................................98 4.3.1.4.2. Lựa chọn tập đặc trưng cho không gian văn bản............................................................................99 4.3.2. Áp dụng mô hình TRSM để xử lý vấn đề đồng nghĩa, trái nghĩa trong Tiếng Việt..................... 100 4.3.2.1. Đặt vấn đề ..............................................................................................................................................100 4.3.2.2. Đặc trưng tần suất của các thuật ngữ và các lân cận ............................................................................101 4.3.2.3. Cài đặt thử nghiệm .................................................................................................................................102 Chương 5 Kết luận và hướng phát triển ...................................................................................................... 110 TÀI LIỆU THAM KHẢO.............................................................................................................................. 114 TÓM TẮT LUẬN VĂN.................................................................................................................................. 116 ABSTRACT OF THESIS............................................................................................................................... 117 Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 4/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai DANH MỤC CÁC THUẬT NGỮ STT Từ viết tắt Thuật ngữ Tiếng Anh 1 DM Data Mining Khai phá dữ liệu 2 DT Decision Tree Cây quyết định 3 EM Expectation Maximization Một phương pháp clustering 4 ERSM Equivalence Rough Sets Model Mô hình tập thô tương đương 5 IDF Inverse Document Frequency Mô hình nghịch đảo tần số văn bản 6 KDD 7 KE 8 K-NN 9 ML 10 Knowledge Discovery Thuật ngữ Tiếng Việt in Databases Khai phá tri thức trong cơ sở dữ liệu Keyword Extraction Bài toán trích trọn từ khoá K- Nearest Neighbour K láng giềng gần nhất Machine Learning Học máy MMH Maximum Marginal Hyperplane Siêu phẳng lề cực đại 11 RSM Rough Sets Model Mô hình tập thô 12 SVMs Support Vector Machines Máy vector hỗ trợ 13 TF Term Frequency Mô hình tần số thuật ngữ 14 TRSM Tolerance Rough Sets Model Mô hình tập thô dung sai 15 TSR Term Space Reduction Giảm không gian thuật ngữ 16 VSM Vector Space Model Mô hình không gian vector Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 5/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai DANH MỤC CÁC BẢNG Bảng 2.1: ví dụ về hệ thông tin............................................................................................36 Bảng 2.2: Walk – ví dụ về bảng quyết định.........................................................................36 Bảng 2.3: Ví dụ bảng thông tin có thuộc tính dư thừa.........................................................44 Bảng 2.4: Bảng dữ liệu thu được bằng cách loại bỏ cột thuộc tính Muscle-pain ................47 Bảng 2.5: Bảng dữ liệu thu được bằng cách loại bỏ cột thuộc tính Headache ....................48 Bảng 2.6: đơn giản hóa Bảng 2.4.........................................................................................49 Bảng 2.7: Đơn giản hóa bảng 2.5 .......................................................................................49 Bảng 3.1: Ví dụ phân loại theo số đông...............................................................................77 Bảng 3.2: Ví dụ lỗi khi phân loại theo số đông. ..................................................................78 Bảng 4.1: Một số hàm tính giá trị ước lượng thông tin của thuật ngữ...............................100 Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 6/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai DANH MỤC CÁC HÌNH Hình 1.1: Data mining – tìm kiếm tri thức trong dữ liệu .......................................................9 Hình 1.2: Data mining là một bước trong quá trình phát hiện tri thức ................................10 Hình 1.3: Dữ liệu 2-D khả tách tuyến tính..........................................................................16 Hình 1.4: Ví dụ về siêu phẳng cùng với lề tương ứng.........................................................17 Hình 1.5: Support vectors ....................................................................................................18 Hình 1.6: Dữ liệu không khả tách tuyến tính.......................................................................20 Hình 1.7: Clustering dựa trên giải thuật k-means ................................................................28 Hình 1.8: Mỗi cluster được biểu diễn bởi một phân bố xác suất .........................................29 Hình 2.1: Minh họa tập xấp xỉ trên, xấp xỉ dưới..................................................................39 Hình 2.2: Xấp xỉ tập đối tượng bằng các thuộc tính điều kiện Age và LEMS ....................40 Hình 2.3: Lớp các từ phủ lên nhau ......................................................................................58 Hình 3.1: Ma trận tài liệu-thuật ngữ ....................................................................................62 Hình 3.2: Minh họa cách tính precision và recall ................................................................71 Hình 3.3: Minh hoạ giải thuật KNN láng giềng gần nhất với K = 5. ..................................77 Hình 4.1: Bộ khung hệ thống khai phá dữ liệu dựa trên mô hình TRSM............................83 Hình 4.2: Giải thuật hierarchical agglomerative clustering dựa trên mô hình TRSM.........91 Hình 4.5: Ví dụ tình huống nhập nhằng trong đồ thị phân tách câu....................................97 Hình 4.6: Các bước của chương trình................................................................................103 Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 7/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai LỜI NÓI ĐẦU Hàng ngày chúng ta tiếp xúc với rất nhiều các loại dữ liệu khác nhau: âm thanh, hình ảnh, các dữ liệu số, các dữ liệu lưu dưới dạng các tài liệu… Các dữ liệu ít nhiều đều ẩn chứa bên trong một phần tri thức nào đó mà ta chưa biết. Khi các dữ liệu trở nên nhiều hơn mà ta không thể kiểm soát nó dưới dạng liệt kê ra được thì trong đó sẽ ẩn chứa một lượng tri thức lớn và cần có các phương pháp để tự động nhận biết ra các quy luật, các tri thức đang ẩn chứa để phục vụ cho lợi ích của chúng ta. Khai phá dữ liệu là bài toán tìm ra tri thức ẩn chứa bên trong một tập dữ liệu lớn và đã có nhiều phương pháp, nhiều hướng tiếp cận khác nhau cho bài toán này, chẳng hạn sử dụng lý thuyết tập thô, lý thuyết tập mờ, lý thuyết xác suất, học máy… Trong luận văn này tác giả sẽ sử dụng hướng tiếp cận mô hình tập thô dung sai cho bài toán khai phá dữ liệu văn bản nhằm giải quyết vấn đề đồng nghĩa, trái nghĩa trong văn bản tiếng Việt. Trong quá trình nghiên cứu, tác giả nhận thấy hướng tiếp cận này có rất nhiều ứng dụng thiết thực khác cũng như một số vấn đề lý thuyết liên quan khác. Tuy nhiên, do hạn chế về mặt thời gian, tác giả chỉ nêu ra các ứng dụng, các bài toán liên quan đó như là những hướng phát triển khả thi mà thôi. Về mặt bố cục, luận văn gồm năm chương với nội dung chính như sau: Chương 1: Trình bày tổng quan về lĩnh vực phát hiện tri thức và khai phá dữ liệu cũng như các bài toán, các phương pháp điển hình thường được sử dụng. Các ứng dụng và xu hướng trong lĩnh vực này. Chương 2: Trình bày về lý thuyết tập thô và các ứng dụng của nó, đặc biệt là trong lĩnh vực khai phá dữ liệu đã trình bày ở chương 1. Mô hình tập thô dung sai (TRSM) cũng được trình bày ở đây, mô hình biểu diễn văn bản này sẽ được sử dụng trong Chương 4. Chương 3: Trình bày một số kỹ thuật trong xử lý văn bản và các mô hình biểu diễn văn bản. Các bài toán, các phương pháp được trình bày tổng quan trong chương 1 sẽ được sử dụng ở đây với dữ liệu cụ thể là dữ liệu văn bản. Chương 4: Mô hình tập thô dung sai trong xử lý cơ sở dữ liệu văn bản nói chung và văn bản tiếng Việt nói riêng. Áp dụng thực tế để xử lý vấn đề đông nghĩa, trái nghĩa trong tiếng Việt. Chương 5: Trình bày các kết luận, các hạn chế của luận văn và đề xuất các hướng phát triển trong tương lai. Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 8/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai Chương 1 Tổng quan về khai phá dữ liệu Nội dung chính sẽ trình bày: • Các khái niệm cơ bản trong khai phá dữ liệu. • Một số kỹ thuật trong khai phá dữ liệu. • Các ứng dụng và xu hướng trong khai phá dữ liệu. 1.1. Khai phá dữ liệu – Data Mining Khai phá dữ liệu[1] là quá trình trích rút các thông tin ẩn chứa trong các kho dữ liệu lớn, đôi khi còn được gọi là khai phá tri thức từ dữ liệu (knowledge mining from data). Có nhiều thuật ngữ khác có nghĩa tương đồng hoặc khác biệt đôi chút với thuật ngữ Data Mining, chẳng hạn knowledge mining from data, knowledge extraction, data/pattern analysis, data archaeology, data dredging. Hình 1.1: Data mining – tìm kiếm tri thức trong dữ liệu Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 9/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai Nhiều người đã xem Data mining là đồng nghĩa với thuật ngữ tương đối phổ biến Knowledge Discovery from Data – KDD, đó là một bước quan trọng trong toàn bộ quy trình phát hiện tri thức, quy trình này bao gồm các bước như sau: Hình 1.2: Data mining là một bước trong quá trình phát hiện tri thức 1. Làm sạch dữ liệu (Data cleaning): loại bỏ nhiễu và các dữ liệu không đồng nhất 2. Tích hợp dữ liệu (Data integration): tích hợp dữ liệu từ các nguồn khác nhau Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 10/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai 3. Lựa chọn dữ liệu (Data selection): các dữ liệu liên quan tới nhiệm vụ phân tích được thu thập từ cơ sở dữ liệu 4. Chuyển đổi dữ liệu (Data transformation): dữ liệu được chuyển đổi hoặc hợp nhất thành các dạng phù hợp với quá trình khai phá, chẳng hạn bằng cách thực hiện các thao tác tổng kết hoặc tụ tập 5. Khai phá dữ liệu (Data mining): là một quá trình cốt lõi trong đó các phương pháp thông minh được áp dụng để trích rút các mẫu dữ liệu 6. Ước lượng mẫu (Pattern evaluation): xác minh tính chân thực của các mẫu biểu diễn tri thức dựa vào một số phương pháp tiêu chuẩn 7. Biểu diễn tri thức (Knowledge presentation): các kỹ thuật liên quan đến trực quan hóa và biểu diễn tri thức được áp dụng để trình diễn tri thức khai phá được cho người dùng nhận biết. Hai mục tiêu chính trong lĩnh vực khai phá dữ liệu đó là mô tả và dự báo. Mô tả nhằm tìm ra các thông tin để mô tả dữ liệu mà người dùng có thể hiểu được, để thực hiện mục tiêu này thường có các bài toán liên quan như lập nhóm, phát hiện luật kết hợp… Còn Dự báo là đoán nhận về xu hướng trong tương lai của dữ liệu dựa trên các dữ liệu đang có, để thực hiện mục tiêu này thường có các bài toán liên quan như bài toán hồi quy, phân loại, phát hiện độ lệch. Để quá trình khai phá dữ liệu được diễn ra thuận lợi, dữ liệu cần được tổ chức theo một cách thức nào đó và áp dụng các phương pháp phù hợp với mỗi cách tổ chức này và phù hợp với bản chất, đặc thù của dữ liệu; thường có nhiều cách tổ chức dữ liệu khác nhau nhưng phổ biến nhất là sử dụng cơ sở dữ liệu quan hệ, ngoài ra còn có cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu toàn văn, cơ sở dữ liệu hướng thời gian thực… Khai phá dữ liệu có thể được tiếp cận theo nhiều hướng khác nhau, mỗi bài toán trong lĩnh vực này sẽ có phương pháp luận để giải quyết nó, phương pháp luận quyết định quan điểm và cách thức chúng ta nhìn nhận và giải quyết vấn đề. Các Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 11/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai hướng tiếp cận lĩnh vực này có thể là: học máy (machine learning), thống kê (statistics), trí tuệ nhân tạo… 1.2. Tiền xử lý dữ liệu Các cơ sở dữ liệu lớn thường gặp phải vấn đề về nhiễu (noisy) chứa trong dữ liệu hoặc dữ liệu bị thiếu (missing) hoặc thiếu nhất quán (inconsistent), điều này ảnh hưởng nghiêm trọng đến các kết quả thu được trong quá trình khai phá dữ liệu. Tiền xử lý dữ liệu nhằm giải quyết vấn đề này. Vậy bằng cách nào có thể để tiền xử lý dữ liệu nhằm nâng cao chất lượng dữ liệu và thu được các kết quả tốt hơn cho quá trình khai phá cũng như nâng cao hiệu suất và dễ dàng hơn cho quá trình này? Có rất nhiều kỹ thuật để tiền xử lý dữ liệu: Data cleaning có thể được áp dụng để loại bỏ nhiễu và khắc phục vấn đề thiếu đồng nhất trong dữ liệu. Data integration để hợp nhất các dữ liệu từ nhiều nguồn khác nhau vào trong một kho chứa dữ liệu cố kết. Data transformations, chẳng hạn đó là sự chuẩn hóa dữ liệu, có thể được áp dụng để nâng cao độ chính xác cũng như tính hiệu quả của các giải thuật, đưa đến các độ đo về khoảng cách. Data reduction có thể dùng để giảm thiểu kích thước của dữ liệu bằng cách kết hợp hoặc loại bỏ các thuộc tính dư thừa. Các kỹ thuật này không loại trừ lần nhau, chúng có thể làm việc chung với nhau. Trong khai phá dữ liệu văn bản nói riêng, tiền xử lý dữ liệu là một quá trình chiếm tương đối nhiều tài nguyên. Để xử lý được dữ liệu dạng này cần phải có quá trình tiền xử lý để đưa nó về dạng có cấu trúc, sau đó áp dụng các giải thuật khai phá trên các cấu trúc đã đạt được. Vấn đề tách từ, loại bỏ các từ dừng (stop words), lấy gốc của từ (stemming), biểu diễn văn bản theo một mô hình nào đó… thường được biết đến bên trong quá trình này. 1.3. Phân lớp và dự báo – Classification and Prediction 1.3.1. Giới thiệu Là 2 dạng phân tích dữ liệu dùng để trích xuất các mô hình mô tả các lớp dữ liệu quan trọng (đối với classifiction) hoặc tiên đoán xu hướng của dữ liệu trong Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 12/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai tương lai (đối với prediction)[1]. Các phân tích này giúp ta có được hiểu biết tốt hơn về cơ sở dữ liệu lớn. Trong khi classification hướng đến việc đưa ra các nhãn xác định (rời rạc, không có thứ tự) thì prediction thường định ra các hàm liên tục. Có rất nhiều phương pháp phân loại cũng như dự báo đã được đưa ra bởi các nhà nghiên cứu trong các lĩnh vực học máy (machine learning), phát hiện mẫu (pattern recognition) và thống kê (statistic). Phần lớn các giải thuật đưa ra ở đây là thường trú trong bộ nhớ, thường sử dụng dữ liệu với kích thước bé; các nghiên cứu gần đây về khai phá dữ liệu dựa trên các kết quả trước đó để phát triển các phương pháp phân loại và dự báo phù hợp với việc xử lý dữ liệu lớn lưu trên đĩa cứng. Phân lớp dữ liệu là một quá trình gồm 2 bước: ở bước thứ nhất, một bộ phân loại được xây dựng mô tả một tập các khái niệm hoặc các lớp dữ liệu đã được định nghĩa trước và được gọi là bước học (learning step) hay pha huấn luyện (training phase); ở đây một giải thuật phân lớp xây dựng nên một bộ phân loại bằng việc phân tích hoặc học từ một training set (tập huấn luyện) được tạo nên từ các phần tử dữ liệu và gắn liền với các nhãn của chúng. Một phần tử X được biểu diễn bởi một vector thuộc tính trong không gian n chiều, có dạng X = (x1, x2,…, xn) biểu diễn n độ đo tạo nên phần tử này từ n thuộc tính của cơ sở dữ liệu, tương ứng là A1, A2, … , An. Mỗi phần tử X được giả định thuộc về một lớp đã được định nghĩa trước thông qua các thuộc tính khác của cơ sở dữ liệu gọi là thuộc tính nhãn các lớp (class label attribute), các thuộc tính này là rời rạc, không có thứ tự và biễu diễn cho một mục hay một lớp nào đó. Bởi vì nhãn của các phần tử huấn luyện đã được biết nên bước này còn được gọi là học có giám sát (supervised learning), nó trái ngược với phương pháp học không giám sát (unsupervised learning) (hoặc clustering) trong đó nhãn của mỗi phần tử huấn luyện là không được biết trước và số lượng các lớp cần được học cũng không được biết. Bước thứ nhất của quá trình phân lớp có thể được xem như là việc học một ánh xạ (một hàm) y = f(X) mà có thể dự đoán được nhãn y của đối tượng X cho trước. Theo cách nhìn này, ta mong muốn học một ánh xạ mà phân tách các lớp dữ Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 13/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai liệu. Thông thường, ánh xạ này được biểu diễn dưới dạng các luật phân lớp, cây quyết định (decision trees) hoặc bằng các mô tả hình thức toán học. Bước thứ 2 của quá trình phân lớp là xác định mức độ chính xác của việc phân lớp. Trước hết cần đánh giá trước độ chính xác của bộ phân lớp, nếu sử dụng tập huấn luyện để đo độ chính xác của bộ phân lớp thì giá trị này tương đối lạc quan vì bộ phân lớp thường có khuynh hướng overfit dữ liệu; bên cạnh đó tập dữ liệu khiểm thử (test set) được sử dụng, tập này được tạo ra từ các phần tử liên quan đến nhãn của các lớp, các phần tử này được lựa chọn một cách ngẫu nhiên từ tập dữ liệu thông thường và độc lập với các phần tử huấn luyện và không tham gia vào quá trình tạo lập bộ phân loại. Độ chính xác của một bộ phân loại dựa trên một tập dữ liệu kiểm thử nào đó là phần trăm các phần tử của tập kiểm thử được phân loại đúng bởi bộ phân loại. Nhãn của lớp liên kết với mỗi phần tử để test được so sánh với lớp dự báo trước của bộ phân loại đã được học áp dụng cho phần tử đó. Có nhiều phương pháp để tính độ chính xác của phân loại, chẳng hạn Holdout Method, Random Subsampling, Crossvalidation, Boostrap. Phương pháp Holdout sẽ phân hoạch ngẫu nhiên tập ban đầu thành 2 tập độc lập: Training set và test set; thông thường 2/3 dữ liệu được định vị trong training set, 1/3 còn lại nằm trong test set. Training set sử dụng để thu được mô hình mà độ chính xác của nó được đánh giá bởi test set. Sự đánh giá này không được tốt vì chỉ một phần dữ liệu ban đầu được sử dụng để tìm ra mô hình. Random subsampling là một biến thể của Holdout bằng cách thực hiện holdout k lần và lấy độ chính xác tổng thể bằng độ chính xác trung bình của mỗi lần lặp đó. Crossvalidation sẽ phân chia tập dữ liệu ban đầu thành k phần bằng nhau và thực hiện k bước lặp, ở mỗi bước lặp test data là 1 trong k phần bằng nhau đó, k-1 phần còn lại được dùng để học; độ chính xác được tính bằng toàn bộ phần tử được phân lớp chính xác sau k vòng lặp chia cho tổng số phần tử của tập ban đầu. Nếu độ chính xác của bộ phân loại là chấp nhận được thì nó sẽ được dùng để phân lớp cho các dữ liệu trong tương lai mà nhãn của nó là chưa được biết trước. Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 14/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai Cả phân lớp và dự báo đều giống nhau ở chỗ chúng đều là quá trình gồm 2 bước như đã nói ở trên, tuy nhiên đối với dự báo thì khái niệm thuộc tính nhãn của các lớp (class label attribute) không tồn tại vì thuộc tính mà giá trị của nó cần dự đoán là một giá trị liên tục (có thứ tự) hơn là giá trị rời rạc (không có thứ tự). Dự báo có thể được xem như là một ánh xạ y = f(X) với X là thông tin đầu vào (một phần tử, một thể hiện của tập dữ liệu) và y là đầu ra với giá trị là liên tục, như vậy, ta mong muốn học một ánh xạ liên hệ giữa X và y. 1.3.2. Support Vector Machines Có rất nhiều kỹ thuật có thể áp dụng trong bài toán phân lớp và dự báo, chẳng hạn có thể dùng cây quyết định (decision tree), Bayesian, K-NN, giải thuật di truyền… Ở đây ta giới thiệu một phương pháp hiện được dùng rất phổ biến hiện nay đó là Support Vector Machines (SVMs). SVMs là một phương pháp mới có thể dùng để phân loại dữ liệu tuyến tính hoặc phi tuyến, thực chất nó là một giải thuật làm việc như sau[1]. SVM sử dụng một ánh xạ phi tuyến (nonlinear mapping) để biến đổi dữ liệu huấn luyện ban đầu vào một không gian có số chiều cao hơn. Trong không gian mới này, nó tìm kiếm siêu phẳng phân tách tối ưu tuyến tính (linear optimal separating hyperplane) – đó là một vùng biên quyết định (decision boundary) phân tách các đối tượng của một lớp khỏi các lớp khác. Với một ánh xạ phi tuyến phù hợp vào một không gian mới tương ứng có số chiều lớn hơn thì dữ liệu thuộc về 2 lớp luôn luôn có thể được phân tách bởi một siêu phẳng. SVM tìm kiếm siêu phẳng này bằng cách sử dụng các support vector – thực chất là các đối tượng huấn luyện – và tìm kiếm lề (margin) được tạo ra bởi các support vector đó. SVMs có thể sử dụng cho cả classification lẫn prediction và được áp dụng rất rộng rãi vào nhiều lĩnh vực, chẳng hạn nhận dạng ký số viết tay, nhận dạng giọng nói, phân loại văn bản… Sau đây ta sẽ giới thiệu SVMs cho 2 trường hợp: dữ liệu là khả tách tuyến tính và không khả tách. Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 15/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai 1.3.2.1. SVMs với dữ liệu khả tách tuyến tính (linearly separable) Xét trường hợp đơn giản ta có 2 lớp phân tách tuyến tính với nhau: Tập dữ liệu ban đầu D được cho dưới dạng (X1, y1), (X2, y2),…, (X|D|, y|D|) trong đó Xi là các đối tượng huấn luyện với nhãn yi với yi ∈ {+1, -1}. Hình 1.3: Dữ liệu 2-D khả tách tuyến tính Xét ví dụ như hình trên, dữ liệu có 2 thuộc tính A1, A2 và khả tách tuyến tính vì ta có thể vẽ 1 đường thẳng để phân tách hoàn toàn các đối tượng thuộc nhóm +1 với các đối tượng thuộc nhóm – 1, có vô số các đường thẳng như thế có thể được vẽ; tuy nhiên ta mong muốn tìm ra đường thẳng nào tối ưu nhất để lỗi phân loại là bé nhất. Với dữ liệu là 3-D ta mong muốn tìm ra 1 mặt phẳng phân tách tối ưu, đối với dữ liệu n chiều ta mong muốn tìm ra 1 siêu phẳng tối ưu. Ta sẽ dùng thuật ngữ “siêu phẳng” – hyperplane – để chỉ đến vùng biên quyết định mà không quan tâm đến số chiều (số thuộc tính) của dữ liệu. Vậy bằng cách nào để tìm ra siêu phẳng tối ưu? SVMs giải quyết bài toán này bằng cách tìm kiếm siêu phẳng lề cực đại (maximum marginal hyperpalne). Hình 1.4 cho thấy 2 trường hợp siêu phẳng phân tách và lề tương ứng với chúng. Cả 2 siêu phẳng đều phân loại một cách đúng đắn dữ liệu ban đầu, tuy nhiên siêu phẳng với lề lớn hơn sẽ cho kết quả phân loại tốt hơn với các dữ Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 16/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai liệu sẽ có trong tương lai. Chính vì vậy, SVMs sẽ tìm kiếm siêu phẳng với lề lớn nhất (MMH – maximum marginal hyperplane) . Một siêu phẳng phân tách có phương trình là: W .X + b = 0 Hình 1.4: Ví dụ về siêu phẳng cùng với lề tương ứng Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 17/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai Với W là vector trọng số, W = {w1, w2,…, wn}, n là số thuộc tính, b là một giá trị vô hướng. Đối với ví dụ ở trên, X = {x1, x2} ta có thể biểu diễn phương trình của siêu phẳng phân tách như sau: w0 + w1x1 + w2x2 = 0 Bất cứ đối tượng nào nằm về phía trên siêu phẳng sẽ có: w0 + w1x1 + w2x2 > 0 và nằm về dưới siêu phẳng sẽ có: w0 + w1x1 + w2x2 < 0 Các trọng số có thể được hiệu chỉnh sao cho các siêu phẳng định ra các mặt của lề có thể được viết là: Bất cứ đối tượng nào nằm trong H1 sẽ thuộc về lớp +1, nằm trong H2 sẽ thuộc về lớp -1. Ta có thể biểu diễn bằng một công thức duy nhất sau đây cho H1 và H2: yi ( w0 + w1 x1 + w2 x2 ) ≥ 1, ∀i (*) Bất cứ đối tượng huấn luyện nào thỏa mãn bất đẳng thức trên được gọi là các support vector. Hình 1.5: Support vectors Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 18/117 Xử lý văn bản tiếng Việt theo mô hình tập thô dung sai ở hình vẽ trên, các support vector là các phần tử với đường viền tròn bao ngoài. Về bản chất thì các support vector là các phần tử khó phân loại nhất và chứa những thông tin quan trọng nhất để phân loại. Vậy tìm kiếm MMH và các support vector như thế nào? Ta có thể viết lại biểu thức (*) ở trên dưới dạng các ràng buộc của một bài toán quy hoạch toàn phương lồi (convex quadratic optimization problem), sử dụng các hệ số Lagrangian và giải quyết bài toán bằng điều kiện Karush-KuhnTucker (KKT). Ở đây, ta sẽ không đi sâu vào giải quyết bài toán này như thế nào, chi tiết có thể tham khảo thêm trong các tài liệu chuyên ngành về toán học. Như vậy giải quyết bài toán quy hoặc toàn phương là sẽ tìm ra các support vector với lề cực đại và như vậy ta đã có một máy vector hỗ trợ đã được huấn luyện. MMH là một vùng bao tuyến tính giữa các lớp, vì vậy SVM tương ứng có thể được sử dụng để phân loại một cách tuyến tính dữ liệu phân tách được. Sau khi đã có một support vector machine, ta có thể sử dụng nó để phân lớp dữ liệu. Dựa vào các hệ số Lagrangian, MMH có thể được viết lại như sau: Trong đó yi là nhãn lớp của vector Xi, XT là tập các phần tử để test; α i và b0 là các giá trị của tham số tối ưu có được nhờ giải quyết bài toán quy hoạch toàn phương; l là số lượng các support vector. Trong trường hợp dữ liệu khả tách tuyến tính, support vectors là tập con của tập các phần tử thực sự để huấn luyện. Với một phần tử kiểm tra, XT ta lắp nó vào công thức ở trên và kiểm tra dấu của kết quả. Nếu dấu là dương thì phần tử thuộc về phần dương của siêu phẳng, ngược lại nó thuộc về phần âm của siêu phẳng. Trong biểu thức kiểm tra dấu ở trên phải tính tích vô hướng giữa support vector Xi với dữ liệu kiểm thử XT, điều này sẽ có lợi cho việc tìm kiếm MMH và support vectors trong trương hợp dữ liệu không khả tách tuyến tính sẽ được đề cập đến ngay sau đây. Học viên thực hiện: Trần Quang – Lớp CH CNTT 2007-2009 19/117