Tài liệu Phân lớp văn bản nhờ máy véc tơ hỗ trợ với hàm string kernel

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG .. ĐẶNG ĐÌNH TUYẾN PHÂN LỚP VĂN BẢN NHỜ MÁY VÉC – TƠ HỖ TRỢ VỚI HÀM STRING KERNEL Chuyên ngành: Khoa học máy tính LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS.TS.Nguyễn Tân Ân THÁI NGUYÊN - 2016 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học Công nghệ Thông tin và Truyền thông Thái Nguyên. Tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn khoa học: PGS.TS Nguyễn Tân Ân đã tận tình hướng dẫn, giúp đỡ và tạo mọi điều kiện để tác giả thực hiện luận văn này. Tác giả cũng xin chân thành cảm ơn tập thể các thầy cô giáo trong khoa CNTT, phòng quản lý sau đại học Trường Đại học Công nghệ Thông tin và Truyên thông Thái Nguyên đã tạo mọi điều kiện giúp đỡ cho tác giả nghiên cứu, học tập và hoàn thành luận văn. Xin cảm ơn gia đình, bạn bè, đồng nghiệp đã tạo điều kiện thuận lợi về tinh thần và vật chất cho tác giả hoàn thành luận văn này. Xin cảm ơn tất cả! Thái Nguyên, tháng 6 năm 2016 Tác giả luận văn Đặng Đình Tuyến Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii LỜI CAM ĐOAN Tôi là Đặng Đình Tuyến, học viên cao học K13, chuyên ngành Khoa học máy tính, khoá 2014-2016. Tôi xin cam đoan luận văn thạc sĩ “Phân lớp văn bản nhờ Máy Véc-tơ hỗ trợ (SVM) với hàm string kernel” là công trình nghiên cứu của riêng tôi cùng với sự hướng dẫn của PGS.TS Nguyễn Tân Ân. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo của luận văn. Trong luận văn, không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Thái Nguyên, tháng 6 năm 2016 Tác giả Đặng Đình Tuyến Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iv MỤC LỤC LỜI CẢM ƠN .............................................................................................................. i LỜI CAM ĐOAN................................................................................................... iii MỤC LỤC .................................................................................................................. iv DANH MỤC HÌNH ẢNH ......................................................................................... vi DANH MỤC BẢNG BIỂU ......................................................................................vii CHƯƠNG 1: BÀI TOÁN PHÂN LỚP ....................................................................... 1 1.1. Nội dung bài toán phân lớp .................................................................................. 1 1.2. Các phương pháp phân lớp ................................................................................... 2 1.2.1. Phương pháp Naïve Bayes (NB) ...................................................................2 1.2.2. Phương pháp K–Nearest Neighbor (kNN) ....................................................3 1.2.3. Neural Network (NNet) .................................................................................5 1.2.4. Centroid- based vector ...................................................................................6 1.3. Máy véc-tơ hỗ trợ (Support Vector Machine SVM) ............................................ 7 1.3.1. Bài toán phân loại SVM ................................................................................7 1.3.2. Ý tưởng của SVM ..........................................................................................8 1.3.3. Phương pháp tìm α*, b. ................................................................................16 1.3.4. SVM đối với bài toán nhiều lớp ..................................................................21 1.3. Kết luận .............................................................................................................. 24 CHƯƠNG 2: NHỮNG KIẾN THỨC CƠ SỞ .......................................................... 25 2.1. Hàm Kernel ........................................................................................................ 25 2.1.1. Không gian gốc, không gian đặc trưng ........................................................25 2.1.2. Định nghĩa kernel ........................................................................................26 2.1.3. Một số ví dụ về Ф và k(,) .............................................................................26 2.1.4. Một số hàm kernel .......................................................................................28 2.1.5. Định lý .........................................................................................................30 2.1.6. Kernel là độ đo giống nhau giữa hai đối tượng ..........................................31 2.1.7. Kernel trick ..................................................................................................32 2.1.8. Xây dựng các kernel ...................................................................................32 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn v 2.1.9. Nhân hóa một số phương pháp phân lớp ....................................................34 2.2. String kernel ....................................................................................................... 39 2.2.1. Kernel dựa trên mô hình k_gram .................................................................39 2.2.2. Kernel dựa trên trọng số của các xâu ...........................................................41 2.2.3. Tính string kernel dùng quy hoạch động .....................................................43 2.2.4. Kernel dựa trên độ giống nhau giữa hai xâu................................................44 2.2.5. Một số đặc trưng của Tiếng Việt. ................................................................45 2.3. Kết luận .............................................................................................................. 48 CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM THUẬT TOÁN SVM CHO BÀI TOÁN TÌM KIẾM VĂN BẢN ............................................................................................. 49 3.1. Mô tả bài toán ..................................................................................................... 49 3.2. Phân tích, cài đặt thuật toán ............................................................................... 49 3.2.1. Thuật toán huấn luyện để tìm từ khóa .........................................................49 3.2.2. Thuật toán sử dụng từ khóa tìm kiếm văn bản ............................................57 3.3. Kết luận .............................................................................................................. 61 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................................ 62 TÀI LIỆU THAM KHẢO ......................................................................................... 63 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vi DANH MỤC HÌNH ẢNH Hình 1.1: Kiến trúc mô đun (Modular Architecture). Các kết quả của từng mạng con sẽ là giá trị đầu vào cho mạng siêu chủ đề và được nhân lại với nhau để dự đoán chủ đề cuối cùng. .........................................................................................................6 Hình 1.2: Các trường hợp của siêu mặt h phân chia tập dữ liệu D trong SVM. .........8 Hình 1.3: Siêu mặt phân chia tập mẫu huấn luyện với 2 lớp là lớp + 1 hình vuông và lớp – 1 hình tròn. .........................................................................................................9 Hình 1.4: Siêu phẳng tuyến tính phân chia dữ liệu, m là khoảng cách giữa hai lề ...10 Hình 1.5: Nguyên lý cơ bản của phương pháp một-chọi-phần còn lại cho ba lớp ...22 Hình 1.6: Nguyên lý cơ bản của phương pháp phân chia môt-chọi-một ..................22 Hình 1.7: Biểu diến phương pháp END để phân chia ba trạng thái của bài toán dự đoán trong phân lớp...................................................................................................24 Hình 2.1: Mỗi điểm dữ liệu được ánh xạ bằng một hàm không tuyến tính Ф từ không gian dữ liệu X vào không gian đặc trưng F. Trong đó Ф(x) và Ф(o) là các véc-tơ đặc trưng của các điểm dữ liệu gốc x và o .....................................................26 Hình 2.2: Ánh xạ dữ liệu từ không gian đầu vào R2 sang không gian dữ liệu R3 .....27 Hình 2.3: Kernel đa thức bậc hai ánh xạ từ không gian hai chiều vào không gian đặc trưng 3 chiều..............................................................................................................29 Hình 2.4: Dữ liệu được tách thành hai lớp trong không gian ban đầu ......................31 Hình 3.1: Trang web Du lịch Khát vọng Việt ...........................................................50 Hình 3.2: Trang web taxinoibaiphuonglong.com .....................................................52 Hình 3.3: Trang web vietnamtourism.com ...............................................................55 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vii DANH MỤC BẢNG BIỂU Bảng 3.1: Bảng thống kê các từ đặc trưng từ Đoạn mẫu 1 .......................................50 Bảng 3.2: Tính toán tần xuất và trọng số của các từ (theo định nghĩa từ tiếng Việt).....51 Bảng 3.3: Bảng thống kê các từ đặc trưng từ Đoạn mẫu 2. ......................................52 Bảng 3.4: Tính toán tần xuất và trọng số của các từ (theo định nghĩa từ tiếng Việt).....54 Bảng 3.5: Bảng thống kê các từ đặc trưng từ Đoạn mẫu 3. ......................................55 Bảng 3.6: Tính toán tần xuất và trọng số của các từ (theo định nghĩa từ tiếng Việt).....56 Bảng 3.7: Bảng tổng hợp...........................................................................................56 Bảng 3.8: Số lần xuất hiện của các từ trong các văn bản huấn luyện .......................59 Bảng 3.9: Bảng phân nhóm với nhãn là “Vịnh Hạ Long” ........................................59 Bảng 3.10: Bảng phân nhóm với nhãn là “Di sản” ...................................................60 Bảng 3.11: Bảng phân nhóm với nhãn là “đảo”........................................................60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 CHƯƠNG 1: BÀI TOÁN PHÂN LỚP 1.1. Nội dung bài toán phân lớp Phân lớp (classification) là một tiến trình xử lý nhằm xếp các mẫu dữ liệu hay các đối tượng vào một trong các lớp đã được định nghĩa trước. Các mẫu dữ liệu hay các đối tượng được xếp về các lớp dựa vào giá trị của các thuộc tính (attributes) cho một mẫu dữ liệu hay đối tượng. Sau khi đã xếp tất cả các đối tượng đã biết trước vào các lớp tương ứng, lúc này mỗi lớp được đặc trưng bởi tập các thuộc tính của các đối tượng chứa trong lớp đó. Ví dụ: phân lớp văn bản, tế bào để xác định tế bào ung thư. Phân lớp còn được gọi là phân lớp có giám sát (supervised classification), là một trong những lĩnh vực phổ biến nhất của học máy (machine learning) và khai thác dữ liệu (data mining). Nó giải quyết việc xác định những quy tắc giữa số lượng biến số độc lập và kết quả đạt được hay một biến số xác định phụ thuộc trong tập dữ liệu được đưa ra. Tổng quát, đưa ra một tập mẫu học x ,x i1 i2  ,..., xik , yi , i=1,….,N, nhiệm vụ là phải ước lượng được một bộ phân lớp hay một mô hình xấp xỉ một hàm y = f(x) chưa biết mà phân lớp chính xác cho bất kỳ mẫu nào thuộc tập các mẫu học. Có nhiều cách để biểu diễn một mô hình phân lớp và có rất nhiều thuật toán giải quyết nó. Các thuật toán phân lớp tiêu biểu bao gồm như mạng neural, cây quyết định, suy luận quy nạp, mạng Beyesian, Support Vector Machine…. Tất cả các cách tiếp cập này xây dựng những mô hình đều có khả năng phân lớp cho một mẫu mới chưa biết dựa vào những mẫu tương tự đã được học. Bài toán phân lớp có thể xử lý thông tin được thu thập từ mọi lĩnh vực hoạt động của con người và thế giới tự nhiên được biểu diễn dưới dạng các bảng. Bảng này bao gồm các đối tượng và các thuộc tính. Các phần tử trong bảng là các giá trị xác định các thuộc tính (attributes hay features) của các đối tượng. Trong đó số cột chính là số thuộc tính của các đối tượng, mỗi cột là một thuộc tính và số dòng chính là số đối tượng chứa trong dữ liệu này. Mọi dữ liệu được biểu diễn dưới các dạng khác có thể được chuyển thành dạng bảng như trên để thực hiện quá trình phân lớp. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 1.2. Các phương pháp phân lớp 1.2.1. Phương pháp Naïve Bayes (NB) NB là phương pháp phân loại dựa vào xác suất được sử dụng rộng rãi trong lĩnh vực máy học (Mitchell trình bày năm 1996, Joachims trình bày năm 1997 và Jason năm 2001) được sử dụng lần đầu tiên trong lĩnh vực phân loại bởi Maron vào năm 1961, sau đó trở nên phổ biến dùng trong nhiều lĩnh vực như trong các công cụ tìm kiếm (được mô tả năm 1970 bởi Rijsbergen), các bộ lọc mail (mô tả năm 1998 bởi Sahami)... * Ý tưởng Ý tưởng cơ bản của cách tiếp cận Naïve Bayes là sử dụng xác suất có điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của một văn bản cần phân loại. Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện của tất cả các từ trong văn bản đều độc lập với nhau. Với giả định này NB không sử dụng sự phụ thuộc của nhiều từ vào một chủ đề, không sử dụng việc kết hợp các từ để đưa ra phán đoán chủ đề và do đó việc tính toán NB chạy nhanh hơn các phương pháp khác với độ phức tạp theo hàm số mũ. * Công thức Mục đích chính là tính được xác suất Pr(Cj,d′), xác suất để văn bản d′ nằm trong lớp Cj. Theo luật Bayes, văn bản d′ sẽ được gán vào lớp Cj nào có xác suất Pr(Cj, d′) cao nhất. Công thức sau dùng để tính Pr(Cj,d′) (do Joachims đề xuất năm 1997) H BAYES    d' d' '  Pr(C j ).  Pr(w i | C j )   Pr(C j ).  Pr(w i | C j ) IF (w,d ) i 1 i 1   arg max   arg max  d' d' ' '  C j C C j C  ' '  ' ' IF ( w , d ) Pr( C ).  Pr(w | C ) Pr( C ).  Pr(w | C ) i i    i 1 i 1  C 'C   C 'C Với:  (TF,d’) là số lần xuất hiện của từ wi trong văn bản d′  |d′| là số lượng các từ trong văn bản d′  wi là một từ trong không gian đặc trưng F với số chiều là |F| Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn       3 Pr(Cj) được tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp Pr(C j )  || C j || || C ||  || C j ||  || C ' || tương ứng với tập dữ liệu huấn luyện. C 'C  Pr(wi|Cj) được tính sử dụng phép ước lượng Laplace ( do Naplik trình bày năm 1982) Pr(w i | C j )  1  TF (w i , C j ) | F |   TF (w ' , C j ) w '| F | Ngoài ra còn có các phương pháp NB khác có thể kể ra như sau ML Naive Bayes, MAP Naive Bayes, Expected Naive Bayes, Bayesian Naive Bayes (Jason mô tả năm 2001). Naive Bayes là một công cụ rất hiệu quả trong một số trường hợp. Kết quả có thể rất tồi nếu dữ liệu huấn luyện nghèo nàn và các tham số dự đoán (như không gian đặc trưng) có chất lượng kém. Nhìn chung đây là một thuật toán phân loại tuyến tính thích hợp trong phân loại văn bản nhiều chủ đề. NB có ưu điểm là cài đặt đơn giản, tốc độ nhanh, dễ dàng cập nhật dữ liệu huấn luyện mới và có tính độc lập cao với tập huấn luyện, có thể sử dụng kết hợp nhiều tập huấn luyện khác nhau. Tuy nhiên NB ngoài giả định tính độc lập giữa các từ còn phải cần đến một ngưỡng tối ưu để cho kết quả khả quan. Nhằm mục đích cải thiện hiệu năng của NB, các phương pháp như multiclass- boosting, ECOC (do Berger trình bày năm 1999 và Ghani mô tả lại năm 2000) có thể được dùng kết hợp. 1.2.2. Phương pháp K–Nearest Neighbor (kNN) Đây là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên thống kê đã được nghiên cứu trong nhận dạng mẫu hơn bốn thập kỷ qua (theo tài liệu của Dasarathy năm 1991). kNN được đánh giá là một trong những phương pháp tốt nhất (áp dụng trên tập dữ liệu Reuters phiên bản 21450), được sử dụng từ những thời kỳ đầu của việc phân loại văn bản (được trình bày bởi Marsand năm 1992, Yang năm 1994, Iwayama năm 1995) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 * Ý tưởng Khi cần phân loại một 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 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ả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của các 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 0. Sau đó các chủ đề sẽ đượ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. * Công thức  Trọng số của chủ đề cj đối với văn bản x :         w  x , c j    sim  x , di  . y  di , c j   b j       Trong đó:    y  di , c j   {0,1} với y – 0: văn bản d i không thuộc về chủ đề cj, y = 1: văn bản    d i thuộc về chủ đề cj.      sin  x , di  : độ giống nhau giữa văn bản cần phân loại x và văn bản d i . Có thể        sử dụng độ đo cosine để tính sin  x , di  Bj là ngưỡng phân loại của chủ đề cj được tự động học sử dụng một tập văn bản hợp lệ được chọn ra từ tập huấn luyện. Để chọn được tham số k tốt nhất cho việc phân loại, thuật toán phải được chạy thử nghiệm trên nhiều giá trị k khác nhau, giá trị k càng lớn thì thuật toán càng ổn định và sai sót càng thấp ( theo Yang trình bày năm 1997). Giá trị tốt nhất được sử dụng trên hai bộ dữ liệu Reuter và Oshumed là k=45. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 1.2.3. Neural Network (NNet) Nnet được nghiên cứu mạnh trong hướng trí tuệ nhân tạo. Wiener là người đã sử dụng Nnet để phân loại văn bản, sử dụng 2 hướng tiếp cận : kiến trúc phẳng (không sử dụng lớp ẩn) và mạng nơron 3 lớp (bao gồm một lớp ẩn)(theo Wiener trình bày năm 1995) Cả hai hệ thống trên đều sử dụng một mạng nơron riêng rẽ cho từng chủ đề, NNet học cách ánh xạ phi tuyến tính những yếu tố đầu vào như từ, hay mô hình vector của một văn bản vào một chủ đề cụ thể. Khuyết điểm của phương pháp NNet là tiêu tốn nhiều thời gian dành cho việc huấn luyện mạng nơron. * Ý 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 interatedreweighted least squares là thuật toán truyền thống trong hồi quy (logistic regression). Kiến trúc mô dun (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. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 Hình 1.1: Kiến trúc mô đun (Modular Architecture). Các kết quả của từng mạng con sẽ là giá trị đầu vào cho mạng siêu chủ đề và được nhân lại với nhau để dự đoán chủ đề cuối cùng. * Công thức Trong công trình của Wiener et al (1995) dựa theo khung của mô hình hồi quy, liên quan từ đặc trưng đầu vào cho đến kết quả gán chủ đề tương ứng được học từ tập dữ liệu. Do vậy, để phân tích một cách tuyến tính, tác giả dùng hàm sigmoid sau làm hàm truyền trong mạng neural:  1 n 1 e Trong đó, η = βπ x là sự kết hợp của những đặc trưng đầu vào và p phải thỏa điều kiện p (0,1). 1.2.4. Centroid- based vector Là một phương pháp phân loại đơn giản, dễ cài đặt và tốc độ nhanh do có độ phức tạp tuyến tính O(n) ( được Han trình bày năm 2000) * Ý tưởng Mỗi lớp trong dữ liệu luyện sẽ được biểu diễn bởi một vector trọng tâm. Việc xác định lớp của một văn bản thử bất kì sẽ thông qua viêc tìm vector trọng tâm nào gần với vector biểu diễn văn bản thử nhất. Lớp của văn bản thử chính là lớp mà vector trọng tâm đại diện. Khoảng cách được tính theo độ đo cosine.  C i 1 i  d j ei Số hóa bởi Trung tâm Học liệu – ĐHTN  dj http://www.lrc.tnu.edu.vn 7 * Công thức Công thức tính vector trọng tâm của lớp i   Độ đo khoảng cách giữa vector x và Ci   x .Ci    cos  x , Ci       x  Ci Trong đó :  x là vector văn bản cần phân loại {i} là tập hợp các văn bản thuộc chủ đề Ci          Chủ đề của x là Cx thoả cos  x , Ci  arg max  cos  x, Ci        1.3. Máy véc-tơ hỗ trợ (Support Vector Machine SVM) 1.3.1. Bài toán phân loại SVM Máy véc-tơ hỗ trợ có thể được hiểu là kỹ thuật giải quyết bài toán sau:” Giả sử chúng ta có tập dữ liệu D gồm 2 loại đối tượng là O1 và O2 trong không gian Rn, hãy tìm một siêu mặt h chia tập D thành 2 phần rời nhau và khi chúng ta có một đối tượng mới b chúng ta phải trả lời được b thuộc loại O1 hay O2, nếu b thuộc O1 thì được gán nhãn là 1, ngược lại b được gán nhãn là -1?”. Siêu mặt h mà chúng ta cần tìm gồm có các trường hợp sau: Siêu phẳng h là (b) Siêu phẳng h là đường (c) Siêu phẳng h là đường cong được ánh xạ vào đường thẳng cong không gian mới thành (a) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 đường thẳng Hình 1.2: Các trường hợp của siêu mặt h phân chia tập dữ liệu D trong SVM. Giả sử chúng ta tìm được cách biểu diễn dữ liệu của bài toán thành dạng có thể áp dụng được vào bài toán SVM, dữ liệu huấn luyện của SVM là tập các dãy đã được gán nhãn trước D   x1 , y1  ,  x2 , y2  ,... xn , yn  . Trong đó: xi là véc-tơ dữ liệu biểu diễn các dãy di( xi Rn). yi { +1, -1}. Cặp (xi,yi) được hiểu là vé-tơ xi ( hay dãy di) được gán nhãn là yi Như vậy, bài toán SVM được phát biểu như sau: Tập huấn luyện Input D   x1 , y1  ,  x2 , y2  ,... xn , yn  Output xi  R n , yi  1, 1 Tìm hàm quyết định f: RN→ {± 1} để dự đoán nhãn y khi đã biết véc-tơ x, trong đó x không nằm trong tập huấn luyện 1.3.2. Ý tưởng của SVM Nếu coi mỗi dãy di được biểu diễn tương ứng với một điểm dữ liệu trong không gian Rn. Thì ý tưởng của SVM là “ tìm một mặt hình học ( siêu mặt f(x) tốt nhất trong không gian n - chiều để phân chia dữ liệu sao cho tất cả các điểm x+ được gán nhãn 1 thuộc về phía dương của siêu mặt (f(x) > 0), các điểm x- được gán nhãn -1 thuộc về phía âm của siêu mặt (f(x) < 0). Với bài toán phân loại SVM, một siêu mặt phân chia dữ liệu được gọi là tốt nhất, nếu khoảng cách từ điểm dữ liệu gần nhất đến siêu mặt là gần nhất. Khi đó, việc xác định một dãy xk D có thuộc phân loại c hay không, tương ứng với việc xét dấu của f(xk), nếu f(xk) > 0 thì xk c, nếu f(xk) ≤ 0 thì xk Số hóa bởi Trung tâm Học liệu – ĐHTN c. http://www.lrc.tnu.edu.vn 9 Hình 1.3: Siêu mặt phân chia tập mẫu huấn luyện với 2 lớp là lớp + 1 hình vuông và lớp – 1 hình tròn. Trong hình 1.3: - Hình tô đậm là siêu mặt tốt nhất. - Các điểm được bao bởi hình chữ nhật là những điểm gần nhất - Các đường nét đứt mà các véc-tơ nằm trên đó được gọi là lề Để giải quyết bài toán phân hai lớp trên ta phải tìm siêu mặt tách 2 lớp. Khi siêu mặt là siêu phẳng thì hàm f có dạng là f(x) = w.x + b sẽ phân loại tốt nhất trên dữ liệu mới. Có ba trường hợp xảy ra đối với tập dữ liệu D là: Tập D là tuyến tính có thể tách được, tập D là tuyến tính không tách được, tập D không tuyến tính. Tương ứng chúng ta có ba trường hợp để giải quyết bài toán SVM.  Tập dữ liệu D có thể phân chia tuyến tính mà không có nhiễu ( nghĩa là tất cả các nhãn được gán nhãn 1 thuộc về phía dương của siêu phẳng, tất cả các nhãn được gán nhãn -1 thuộc về phía âm của siêu phẳng). Khi đó, chúng ta tìm được một siêu phẳng tuyến tính có dạng f(x)= w.x + b (1.1) để phân chia tập dữ liệu thành hai phần như sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 10 m= w Class 2 WTx + b = 1 Class WTx + b = 0 1 WTx + b = - 1 Hình 1.4: Siêu phẳng tuyến tính phân chia dữ liệu, m là khoảng cách giữa hai lề Với mỗi xi ta luôn có T   w xi  b  0 f  xi    T   w xi  b  0 Trong đó: - w -b Nếu yi = 1 Nếu yi = -1 Rn là véc-tơ trọng số R là hệ số tự do - w.x là tích vô hướng của hai véc-tơ w và x. Sao cho với tập dữ liệu kiểm tra x = { x1, x2,…,xn}, lấy yi {-1,1} là nhãn của xi, ta có hàm quyết định: 1 f  xi   sign  w T x  b    1 Nếu yi = 1 (x,y) D (1.2) Nếu yi = -1 Giả sử siêu phẳng phân chia dữ liệu với các ràng buộc: min| w.xi+b|= Số hóa bởi Trung tâm Học liệu – ĐHTN với I = 1…l http://www.lrc.tnu.edu.vn (1.3) 11 Hay yi[ w.xi+b] ≥ Trong đó: với ≥ 0, i= 1…l (1.4) R là một biến mà chúng ta cần xác định. Bây giờ vấn đề đặt ra là cần xác định số w và b, như thế nào để siêu phẳng tìm được là tốt nhất? Siêu phẳng tốt nhất là siêu phẳng có khoảng cách từ điểm dữ liệu huấn luyện gần nhất đến siêu phẳng là xa nhất. Mà khoảng cách từ một điểm dữ liệu xi đến siêu phẳng là: D  w, b, xi   | w.xi  b | |w| | w.xi  b | là giá trị tuyệt đối của biểu thức (1.5) ,|w| là độ dài Ơ-cơ-lít của véc- tơ w. Giả sử h( w,b) là tổng của 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 thì: h  w, b   min xi , yi 1 d  w, b; xi   min xi , yi 1 d  w, b; xi  w.xi  b  min xi , yi 1 1 w 2  w   min xi , yi 1 w  min xi , yi 1 w.xi  b w w.xi  b  min xi , yi 1 w.xi  b |  (1.6) Như vậy, siêu phẳng tối ưu là siêu phẳng có h(w,b)= 2 /||w|| lớn nhất, tương đương với ||w|| là nhỏ nhất và là lớn nhất. Tóm lại, việc tìm siêu phẳng tốt nhất tương đương với việc giải bài toán tối ưu minФw, (w)= || w||2 –vp Với ràng buộc: yi  w.xi  b   với Với v là một tham số của (1.7), v ≥ 0 và I = 1….l [0,1] Hàm La-gơ-răng của bài toán tối ưu trên là: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn (1.7) 12 l L(w,b, ) = || w||2 - v   y  wx - i i 1 Ở đây,   1 , 2 ,...,l  và i ≥ 0 ( i= 1,…,l), i  b      (1.8) ≥ 0 là các hệ số của Lagrange multiplier. Ta có bài toán Lagrangian tương ứng với bài toán tối ưu (1.7) với các ràng buộc (1.4) là: 1 min w,   w, b,   w 2 l 2 v   i  yi  wx i  b       Với ràng buộc αi ≥ 0, i= 1,…,l i 1 và δ ≥ 0 Nghiệm của bài toán tối ưu (1.21) với ràng buộc (1.18) chính là điểm yên ngựa của hàm Lagrangian (1.7). Theo định lý Kuhn-Tucker, giá trị tối thiểu của (1.22) trên b, w và ρ đạt được khi: l L  0    i yi  0 b i 1 l L  0  w    i yi xi b i 1 l L  0  i  v   b i 1 Xét điều kiện l  i 1 i (1.9)  v   , chúng ta thấy rằng theo điều kiện bổ sung trong hệ điều kiện của định lý Kuhn-Tucker, δρ = 0, do đó ρ > 0 suy ra δ = 0. Như vậy, trong trường hợp ρ > 0 chúng ta có thể thay điều kiện này bằng điều kiện l  i 1 i v Từ nhận xét trên và thay (1.9) vào (1.8) ta có bài toán Lagragian đối ngẫu: max LD     1 l  2 i 1 l   j 1 i j yi y j xi x j Với các ràng buộc: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn (1.10) 13 α≥0 i = 1,…l l  i 1 i (1.11) l  i 1 yi  0 i v Giả sử α* là nghiệm của (1.10) với các ràng buộc (1.11) thì:  *  arg min 1 l  2 i 1 l   i j 1 j yi y j xi x j (1.12) Khi đó các hệ số của siêu phẳng tối ưu là: w*  b*  1 l * i yi xi 2 j 1 1  2s rr 0 l  * i i y ( xi xr ) (1.13) i Trong đó: xr là support vecto thỏa mãn  r*  0 , s là tổng số các véc-tơ hỗ trợ của siêu phẳng tối ưu. Từ (1.13) ta thấy chỉ những  r*  0 mới có ý nghĩa trong việc xây dựng véc-tơ w. Mà theo điều kiện bổ sung trong hệ điều kiện của định lý Kuhn-Tucker, i*  yi  w.xi  b      0 thì  r*  0 tương đương với yi(w.xi+b)-ρ= 0. Như vậy, điểm xi được gọi là support vector cũng chính là điểm có  r*  0 . Bây giờ, để phân loại một tài liệu x ta chỉ cần xét dấu của hàm f(x)  l *  f  x   sgn  i yi (x i x)  b*   i 1  (1.14)  Tập dữ liệu huấn luyện D có thể phân chia được tuyến tính nhưng có nhiễu ( Hình 1.9). Trong trường hợp này, hầu hết các điểm trong tập dữ liệu được phân chia bởi siêu phẳng tuyến tính. Tuy nhiên, có một số ít điểm bị nhiễu ( là điểm có nhãn dương nhưng thuộc về phía âm của siêu phẳng). Trong trường hợp này, chúng ta thay ràng buộc (1.4) bằng ràng buộc sau> Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn