Đề tài nghiên cứu khoa học Nghiên cứu về thuật toán phân lớp sử dụng quá trình học máy bán giám sát, ứng dụng trong việc phân lớp trang Web

Nội dung text: Đề tài nghiên cứu khoa học Nghiên cứu về thuật toán phân lớp sử dụng quá trình học máy bán giám sát, ứng dụng trong việc phân lớp trang Web

1. TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CƠNG NGHỆ THƠNG TIN THUYẾT MINH ĐỀ TÀI NCKH CẤP TRƯỜNG ĐỀ TÀI NGHIÊN CỨU VỀ THUẬT TỐN PHÂN LỚP SỬ DỤNG QUÁ TRÌNH HỌC MÁY BÁN GIÁM SÁT, ỨNG DỤNG TRONG VIỆC PHÂN LỚP TRANG WEB Chủ nhiệm đề tài: ThS. Lê Hồng Dương Thành viên tham gia: ThS. Ngơ Quốc Vinh Hải Phịng, tháng 4/2016
2. MỤC LỤC MỞ ĐẦU 1 1. Tính cấp thiết của vấn đề nghiên cứu 1 2. Tổng quan về tình hình nghiên cứu thuộc lĩnh vực đề tài 1 3. Mục tiêu, đối tượng, phạm vi nghiên cứu 2 4. Phương pháp nghiên cứu, kết cấu của cơng trình nghiên cứu 3 5. Kết quả đạt được của đề tài 3 CHƯƠNG 1 TỔNG QUAN VỀ VIỆC PHÂN LỚP SỬ DỤNG PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT 4 1.1. Tổng quan về phân lớp dữ liệu. 4 1.1.1. Tổng quan về bài tốn phân lớp dữ liệu 4 1.1.2. Tổng quan về quá trình phân lớp dữ liệu 5 1.2. Tổng quan về phân lớp dữ liệu văn bản 6 1.2.1. Thực trạng của vấn đề. 6 1.2.2. Sử dụng mơ hình vector biểu diễn văn bản 7 1.2.3. Tổng quan về phương pháp phân lớp văn bản 11 1.2.4. Ứng dụng của việc phân lớp dữ liệu văn bản 12 1.2.5. Quá trình phân lớp dữ liệu văn bản: 12 1.2.6. Đánh giá máy phân lớp dữ liệu văn bản 14 1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp. 15 1.3. Các thuật tốn học máy ứng dụng trong phân lớp 15 1.3.1. Phương pháp học cĩ giám sát 15 1.3.2. Thuật tốn phân lớp dữ liệu theo phương pháp học bán giám sát 18 i
3. CHƯƠNG 2 BÀI TỐN PHÂN LỚP ÁP DỤNG SVM VÀ PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT SVM 21 2.1. Máy hỗ trợ vector – Support Vector Machine 21 2.1.1. Giới thiệu về thuật tốn SVM 22 2.1.2. Huấn luyện SVM 23 2.1.3. Ưu điểm của SVM trong phân lớp văn bản 24 2.2. Bán giám sát SVM và phân lớp trang Web 26 2.2.1. Giới thiệu về bán giám sát SVM 26 2.2.2. Phân lớp trang Web sử dụng bán giám sát SVM 27 CHƯƠNG 3 KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ 30 3.1. Giới thiệu về phần mềm SVMlin 30 3.2. Sử dụng phần mềm và kết quả đánh giá 31 KẾT LUẬN 34 TÀI LIỆU THAM KHẢO 35 ii
4. DANH SÁCH HÌNH ẢNH Số hình Tên hình Trang 1.1 Mơ hình tổng quan về bài tốn phân lớp 5 1.2 Ví dụ về việc biểu diễn văn bản bởi vector 8 đặc trưng 1.3 Sơ đồ biểu diễn quá trình phân lớp dữ liệu 13 văn bản 1.4 Mặt siêu phẳng h phân các điểm thành 2 lớp 18 + và - với khoảng cách biên lớn nhất. Các điểm gần mặt siêu phẳng h nhất là các vector hỗ trợ 1.5 Thuật tốn Self training 19 1.6 Thuật tốn Co training 20 iii
5. DANH SÁCH THUẬT NGỮ, CHỮ VIẾT TẮT Chữ viết tắt Trang SVM: Support Vector Machine 1 VC: Vapnik-Chervonenkis 21 S3VM: Semi Supervised Support Vector Machine 26 iv
6. MỞ ĐẦU 1. Tính cấp thiết của vấn đề nghiên cứu Với xu hướng phát triển hiện tại, khối lượng dữ liệu trong cuộc sống ngày càng lớn dẫn đến việc vai trị của phân lớp dữ liệu cũng ngày càng quan trọng hơn, đây cĩ thể được đánh giá là một trong các vấn đề bức thiết trong ngành xử lý dữ liệu văn bản. Một trong các yêu cầu thiết yếu cần được đưa ra là cải thiện hiệu suất của thuật tốn thực hiện việc phân lớp, gia tăng giá trị độ đo hồi tưởng, cũng như tính chính xác của phương pháp. Tuy nhiên trong thực tế, nguồn dữ liệu được thiết lập nhãn trước khơng phải lúc nào cũng được đáp ứng dẫn đến việc phải xây dựng các phương pháp phân lớp sử dụng tập dữ liệu chưa gán nhãn. Để cĩ thể thỏa mãn được cả hai yêu cầu trình bày phía trên phương pháp phân lớp bán giám sát tỏ ra tương đối hiệu quả. Các phương pháp phân lớp này tận dụng được các nguồn dữ liệu chưa được đánh nhãn rất phong phú và đồng thời cũng tận dụng được hiệu quả một số lượng nhỏ các dữ liệu đã được thiết lập nhãn sẵn. Một trong các phương pháp được sử dụng và đánh giá tương đối tốt trong thời gian qua để sử dụng trong các cơng việc nhận dạng hay phân loại là phương pháp SVM - bộ phân loại máy hỗ trợ vector (Support Vector Machine). Các nghiên cứu đã được cơng bố đã chứng minh về hiệu suất phân loại văn bản khá tốt của phương pháp SVM. 2. Tổng quan về tình hình nghiên cứu thuộc lĩnh vực đề tài Trong lĩnh vực khai phá dữ liệu, các phương pháp phân lớp văn bản đã dựa trên những phương pháp quyết định như quyết định Bayes, cây quyết định, K-người láng giềng gần nhất, . Những phương pháp này đã cho kết quả chấp nhận được và được sử dụng nhiều trong thực tế. Trong những năm gần đây, phương pháp phân lớp sử dụng quá trình học máy bán giám sát đang được quan tâm và sử dụng nhiều trong lĩnh vực nhận dạng, phân lớp. Nhận thấy được tính mới trong vấn đề này nên tác giả lựa chọn đề tài “Nghiên cứu về thuật tốn phân lớp sử dụng quá trình học máy bán giám sát, Trang 1
7. ứng dụng trong việc phân lớp trang Web” để sử dụng cho việc nghiên cứu của mình. 3. Mục tiêu, đối tượng, phạm vi nghiên cứu Những năm gần đây, thế giới chứng kiến sự phát triển bùng nổ của khoa học nĩi chung và lĩnh vực cơng nghệ thơng tin nĩi riêng. Chính điều này đã làm gia tăng các hình thức trao đổi thơng tin thơng qua hệ thống Internet một cách chĩng mặt, cĩ thể kể đến như thư viện điện tử, báo điện tử Vì lý do này mà lượng dữ liệu văn bản trên Internet cũng ngày càng tăng theo một cách đáng kể, kèm theo đĩ là tốc độ của thơng tin thay đổi cũng rất nhanh chĩng. Với lượng dữ liệu thơng tin càng càng lớn, một trong những yêu cầu bức thiết được lập ra là làm cách nào cĩ thể tổ chức và khai thác được các thơng tin một cách hiệu quả. Để giải quyết được các yêu cầu trên thì bài tốn phân lớp là một trong những giải pháp thích hợp nhất. Tuy nhiên trong thực tế, lượng thơng tin lại quá lớn để cĩ thể phân lớp một cách thủ cơng và các thực hiện phân lớp bằng các phương pháp đơn giản thủ cơng là điều khơng khả thi. Một chương trình máy tính thực hiện phân lớp các dữ liệu văn bản một cách tự động chính là chìa khĩa để giải quyết vấn đề này. Trong thực tế, các khĩ khăn mà chúng ta thường phải đối mặt khi xử lý các bài tốn phân lớp tự động là làm thế nào để cĩ thể tạo ra được một bộ phân lớp cĩ độ tin cậy cao khi số lượng dữ liệu được gán nhãn sẵn khơng cĩ sẵn. Các bộ dữ liệu được thiết lập nhãn sẵn này thường khơng cĩ nhiều vì để cĩ được chúng địi hỏi phải tốn nhiều cơng sức cũng như thời gian để xây dựng thiết lập nhãn. Điều này dẫn đến việc phải cĩ một phương pháp học khơng địi hỏi nhiều dữ liệu thiết lập nhãn sẵn và đồng thời tận dụng được hiệu quả các nguồn dữ liệu chưa thiết lập nhãn cĩ rất nhiều trong thực tế, phương pháp học được lựa chọn để nghiên cứu ở đây là phương pháp học bán giám sát. Thực chất phương pháp học bán giám sát cĩ thể được xem là cách học sử dụng dữ liệu chứa trong cả bộ dữ liệu chưa được thiết lập nhãn Trang 2
8. và bộ dữ liệu đã được thiết lập nhãn. Vì ưu điểm tiện lợi của phương pháp này nên nĩ được áp dụng khá rộng rãi. Vì lý do trên, nghiên cứu tập trung vào việc trình bày về bài tốn phân lớp dữ liệu sử dụng phương pháp học bán giám sát và việc áp dụng phương pháp học bán giám sát sử dụng máy hỗ trợ vector vào việc phân lớp dữ liệu trên các trang Web. Mục tiêu chính của đề tài bao gồm: + Nghiên cứu thuật tốn phân lớp sử dụng quá trình học máy bán giám sát. + Ứng dụng thuật tốn trong việc phân lớp trang Web. 4. Phương pháp nghiên cứu, kết cấu của cơng trình nghiên cứu Nghiên cứu định tính: Thực hiện tham khảo các bài báo khoa học liên quan đến các thuật tốn học máy và học máy bán giám sát cũng như tham khảo các cơng trình đã cơng bố về lĩnh vực này. Nghiên cứu định lượng: Cài đặt thuật tốn, ứng dụng trong việc phân lớp trang Web. Đánh giá kết quả đạt được đồng thời hiệu chỉnh thuật tốn và hệ thống để đạt được kết quả tốt nhất. Nghiên cứu được trình bày trong 3 chương. Cấu trúc cụ thể như sau: Chương 1: Tổng quan về việc phân lớp sử dụng phương pháp học bán giám sát Chương 2: Bài tốn phân lớp áp dụng SVM và phương pháp học bán giám sát SVM Chương 3: Kết quả thử nghiệm và đánh giá. 5. Kết quả đạt được của đề tài Kết quả đạt được của đề tài: là báo cáo về kết quả nghiên cứu thuật tốn phân lớp sử dụng quá trình học máy bán giám sát, và kết quả của việc ứng dụng thuật tốn trong việc phân lớp trang Web. Trang 3
9. Đối tượng phục vụ: kết quả của nghiên cứu sẽ là tài liệu phục vụ cho việc tham khảo và nghiên cứu của các đối tượng trong lĩnh vực Khai phá dữ liệu. CHƯƠNG 1 TỔNG QUAN VỀ VIỆC PHÂN LỚP SỬ DỤNG PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT 1.1. Tổng quan về phân lớp dữ liệu. 1.1.1. Tổng quan về bài tốn phân lớp dữ liệu Bài tốn phân lớp dữ liệu là quá trình phân lớp một đối tượng dữ liệu cụ thể vào một hoặc nhiều lớp dữ liệu đã xác định trước thơng qua một mơ hình phân lớp được xây dựng từ trước dựa trên một tập đối tượng dữ liệu thiết lập nhãn sẵn từ trước hay chúng ta vẫn thường gọi là tập huấn luyện. Quá trình phân lớp dữ liệu cịn cĩ thể được gọi với một tên khác là quá trình thiết lập nhãn cho các đối tượng dữ liệu. Nhiệm vụ chính của việc phân lớp dữ liệu là tạo ra mơ hình phân lớp để khi cĩ một đối tượng dữ liệu mới được đưa ra thì mơ hình phân lớp dữ liệu sẽ xếp đối tượng dữ liệu đĩ vào lớp nào hay cĩ thể coi là thiết lập nhãn cho đối tượng dữ liệu này. Trong thực tế phân lớp dữ liệu cĩ rất nhiều bài các bài tốn khác nhau như bài tốn phân lớp nhị phân, bài tốn phân lớp đa trị, . Bài tốn phân lớp nhị phân cịn được hiểu là phân lớp đối tượng dữ liệu vào một trong hai lớp cho trước khác nhau thơng qua việc xem xét đối tượng dữ liệu đĩ cĩ hay khơng cĩ các đặc tính phân loại được đặt ra theo quy ước của mơ hình phân lớp. Bài tốn phân lớp đa trị là bài tốn phân lớp mà trong đĩ mỗi đối tượng dữ liệu trong tập dữ liệu được gán nhãn cũng như các đối tượng dữ liệu chưa được gán nhãn sau khi được phân lớp cĩ thể được xếp vào hai lớp trở lên. Trang 4
10. Tiếp theo đây, nghiên cứu sẽ trình bày tổng quan về quá trình phân lớp dữ liệu và phương pháp phân lớp dữ liệu. 1.1.2. Tổng quan về quá trình phân lớp dữ liệu Hình 1.1 Mơ hình tổng quan về bài tốn phân lớp Như hình trên thể hiện quá trình phân lớp dữ liệu được thực hiện qua hai bước chính: Bước 1: Thiết lập mơ hình phân lớp: Mơ hình phân lớp được tạo nên dựa trên việc phân tích các đối tượng dữ liệu trong tập huấn luyện. Các lớp được gán nhãn của tập dữ liệu được gán nhãn này được xác định thủ cơng từ trước, vì vậy phương pháp học này cịn cĩ thể được gọi với tên khác là phương pháp học cĩ giám sát (supervised learning). Tại bước này, độ chính xác của mơ hình cần được tính đến. Nếu độ chính xác của mơ hình là chấp nhận được mơ hình phân lớp sẽ được dùng để xác định nhãn cho các đối tượng chưa được gán nhãn. Trong quá trình đánh giá mơ hình phân lớp, độ đo sẽ được sử dụng để đánh giá độ chất lượng của các tập phân lớp. Trong thực tế cĩ nhiều phương pháp phân lớp dữ liệu để giải quyết các bài tốn phân lớp tùy thuộc vào cách tạo ra mơ hình phân lớp. Cĩ thể kể đến một số phương pháp như Bayes, cây quyết định, SVM, K láng giềng gần nhất, Các Trang 5
11. phương pháp phân lớp phân biệt nhau thơng qua bộ| phân lớp. Bộ phân lớp cịn được gọi với tên gọi khác là thuật tốn phân lớp. Bước 2: Tiến hành phân lớp sử dụng mơ hình phân lớp tạo ở bước 1. Thuật tốn phân lớp cĩ thể coi là ánh xạ từ miền dữ liệu sẵn cĩ sang một miền giá trị cụ thể của nhãn lớp, dựa trên thuộc tính của các đối tượng dữ liệu. 1.2. Tổng quan về phân lớp dữ liệu văn bản 1.2.1. Thực trạng của vấn đề. Các phương thức giao dịch sử dụng giấy tờ trong thời đại hiện nay thì phương thức số dần đang thay thế các phương thức giao dịch truyền thống. Cụ thể việc số hố các giấy tờ cĩ thể hiểu như việc chuyển các dữ liệu dạng giấy tờ sang các định dạng số được lưu trữ trên máy tính hoặc truyền tải thơng qua mơi trường internet. Lượng dữ liệu văn bản được lưu trữ trực tuyến hiện nay đang gia tăng một cách chĩng mặt do cĩ nhiều ưu điểm như tiện dụng, gọn nhẹ và sự lưu trữ ổn định lâu dài, dễ dàng hiệu chỉnh cũng như truyền gửi. Song song với sự gia tăng số lượng văn bản thì nhu cầu khai thác tìm kiếm các dữ liệu văn bản cũng đang trở thành một nhu cầu thiết yếu trong thời điểm hiện tại. Trong cuộc sống hàng ngày, việc phân lớp các văn bản đa phần được thực hiện thủ cơng. Và dễ thấy được cách thức phân loại này tốn kém về mặt thời gian cũng như cơng sức của con người vì các văn bản rất lớn, để thực hiện phân lớp các văn bản theo cách thức này về lâu dài là một vấn đề khơng khả thi. Từ đĩ chúng ta cĩ thể nhận thấy việc phân lớp văn bản tự động là một vấn đề bức thiết cần phải được giải quyết. Câu hỏi được đặt ra ở đây là phân lớp văn bản là gì? Phân lớp văn bản cĩ thể được hiểu là việc phân lớp dữ liệu áp dụng đối với các dữ liệu văn bản, hay phân một văn bản vào một hay nhiều lớp văn bản thơng qua một mơ hình phân lớp được xây dựng dựa trên một tập hợp các văn bản thiết lập nhãn từ trước. Trang 6
12. Phân lớp dữ liệu văn bản hiện nay đang là một trong các lĩnh vực được quan tâm hàng đầu và hiện đã và đang được đầu tư nghiên cứu tương đối nhiều trong những năm gần đây trên khắp thế giới. 1.2.2. Sử dụng mơ hình vector biểu diễn văn bản Một trong những cách phổ biến được sử dụng để biểu diễn dữ liệu văn bản là phương pháp biểu diễn bằng mơ hình vector, mỗi văn bản sẽ được biểu diễn thơng qua một vector trọng số. Cụ thể phương pháp này sẽ coi mỗi một đối tượng dữ liệu văn bản Di được biểu diễn dưới dạng 푖 = (→, 푖), trong đĩ chỉ số i 푖 dùng để nhận diện văn bản này và → là vector đặc trưng biểu diễn cho văn bản 푖 Di . Cụ thể trong vector này: →=(wi1,wi2, ,win), với n là số luợng đặc trưng được 푖 trích chọn của văn bản, wij là trọng số của đặc trưng thứ j của văn bản Di, j∈{1,2, ,n}. Đối với việc chuyển đổi văn bản sang biểu diễn dưới dạng vector đặc trưng, thì vấn đề cần quan tâm là việc lựa chọn đặc trưng nào và bao nhiêu đặc trưng, phương thức chọn ra sao?  Các đặc trưng trong vector biểu diễn văn bản Số chiều của khơng gian vector đặc trưng biểu diễn văn bản thường lớn và phụ thuộc vào lượng thơng tin trong các văn bản. Các đặc trưng trong vector biểu diễn của văn bản thường độc lập nhau. Các đặc trưng rời rạc: vector đặc trưng di cĩ thể cĩ nhiều trọng số đặc trưng bằng 0 do cĩ nhiều đặc trưng khơng xuất hiện trong văn bản di, tuy vậy nếu đơn thuần chỉ dùng cách tiếp cận sử dụng bộ giá trị 0, 1 thì kết quả phân lớp sẽ bị hạn chế là do cĩ thể cĩ các đặc trưng khơng cĩ trong văn bản đang xét nhưng trong văn bản đang xét lại cĩ nội dung cĩ ý nghĩa tương đồng với đặc trưng bị bỏ qua này, do điều này chúng ta cĩ thể lựa chọn cách tiếp cận khác là khơng sử dụng bộ số 0, 1 mà sử dụng giá trị các giá trị thực để phần nào giảm bớt sự rời rạc trong vector đặc trưng biểu diễn văn bản. Trang 7
13. Đa số các văn bản cĩ thể được phân loại một cách tuyến tính bằng cách sử dụng các hàm tuyến tính. Theo đĩ, số chiều của vector là số lượng các từ xuất hiện trong ít nhất một mẫu dữ liệu đã được thiết lập nhãn. Trước khi thiết lập các trọng số đặc trưng cho các từ khố phân loại cần thực hiện loại trừ những từ dừng. Từ dừng ở đây được hiểu là các từ thường xuất hiện nhưng khơng đem lại lợi ích trong việc phân lớp dữ liệu văn bản chẳng hạn như “như vậy”, “tuy”, “là”, “và”, “thì”, “and”, “but”, “the”, “or”, . thường chúng ta cĩ thể nhận biết các từ dừng cĩ thể kể đến như các trạng từ hoặc liên từ hay giới từ. Chúng ta cĩ thể xem xét ví dụ sau về việc biểu diễn văn bản dưới dạng vector đặc trưng: Hình 1.2 Ví dụ về việc biểu diễn văn bản bởi vector đặc trưng  Biểu diễn dữ liệu văn bản dạng trang Web Về mặt bản chất các trang web thực chất là các siêu văn bản. Ngồi các thành phần dữ liệu văn bản và các thành phần dữ liệu media, trong các trang Web cịn chứa các thành phần đặc trưng như các Hyperlink, các tag định dạng Trang 8
14. HTML và các meta-data. Kết quả của phần lớn nghiên cứu chỉ ra cơng việc phân lớp Web được cung cấp thơng tin chủ yếu nhở các thành phần băn bản trong trang web và được gia tăng hiệu suất nhờ vào những thành phần khơng phải văn bản. Ở thời điểm hiện tại để biểu diễn một trang Web người ta cĩ thể sử dụng nhiều cách khác nhau, tùy theo mục đích chúng ta cĩ thể lựa chọn các cách thức biểu diễn riêng. Các bộ máy tìm kiếm của các hãng lớn như Google hay Yahoo đều sử dụng hệ thống từ khĩa mĩc nối thay vì lựa chọn cách biểu diễn sử dụng vector. Các hệ thống văn bản cũ trước đây thường thực hiện các cơng việc tìm kiếm, biểu diễn, phân lớp theo các phương pháp dựa trên việc xem trang Web như một văn bản thơng thường và biểu diễn văn bản đĩ bằng vector. Siêu liên kết được sử dụng kết nối các trang Web thể hiện được các mối liên hệ giữa nội dung giữa các trang, Từ đĩ chúng ta cĩ thể nâng cao hiệu suất của các cơng việc như phân lớp và tìm kiếm giúp khai thác được các ưu điểm của hyperlink trong các văn bản. Một số nghiên cứu gần đây đã chi ra cách nâng cao hiệu quả thơng qua phương pháp bổ sung thêm các từ khố bằng cách mở rộng thêm các từ khố mới trong các văn bản lân cận với siêu liên kết. Trong nghiên cứu này sẽ tập trung vào cách biểu diễn trang Web bằng cách sử dụng mơ hình vector. Sử dụng các thơng tin liên kết với mục đích cải thiện độ chính xác của cơng việc tìm kiếm và các cơng việc phân lớp các trang Web bằng cách bổ sung các thơng tin về các trang Web láng giềng vào vector đặc trưng biểu diễn cho trang đang được xét. Hiện nay tồn tại bốn cách chính để biểu diễn trang Web dưới dạng vector như sau: Cách thứ nhất Lưu trữ các từ khĩa cùng tần số xuất hiện từ khĩa đĩ trong trang Web được xét. Cách lưu trữ này bỏ qua tất các thơng tin khác như vị trí của từ khố trong Trang 9
15. trang đang xét cũng như thứ tự của các từ trong trang cùng các thơng tin khác như hyperlink. Cách biểu diễn này được cho là phương pháp hiệu quả nhất cho các trường hợp tài liệu đã liên kết độc lập với các nhãn của các lớp nhưng với một số trường hợp đặc biệt khác thì phương pháp lại khơng tận dụng được tính cân đối của tài liệu siêu liên kết. Cách thứ hai Mĩc nối trang được xét tới các trang láng giềng để tạo ra một super document thơng qua thơng tin liên kết của trang đĩ. Vector đặc trưng của văn bản gồm thơng tin về các từ xuất hiện trong trang trong các trang láng giềng của nĩ đi kèm với tần số cĩ mặt của các từ đĩ. Phương pháp này cũng giống như phương pháp trên bỏ qua các thơng tin liên quan đén vị trí xuất hiện và thứ tự xuất hiện của các từ khĩa. Điểm yếu của phương pháp này là gây phân tán nội dung của trang web đang quan tâm. Tuy vậy với trường hợp biểu diễn cho một tập các trang web tương đồng về nội dung chủ đề thì đây lại là phương pháp tương đối tốt. Tuy nhiên việc các trang web liên kết cùng chủ điểm hiện nay chưa thật sự phổ biến nên phương pháp này ít được lựa chọn. Cách thứ ba Phương pháp biểu diễn trang web dùng một vector cĩ cấu trúc gồm lớn hơn 2 thành phần. Mỗi thành phần trong vector biểu diễn một tập các trang lân cận với trang được xét. Số chiều của vector cố định nhưng mỗi thành phần của vector đĩ chỉ biểu diễn cho các từ khĩa xuất hiện trong một tập. Phương pháp này khắc phục được tình trạng các từ khĩa của trang láng giềng làm lỗng nội dung của trang web đang được xét. Nếu thơng tin mở rộng trang láng giềng thực sự hữu ích cho cơng việc phân lớp thì mơ hình học vẫn cĩ thể truy cập đến tồn bộ nội dung trong trang láng giềng đĩ để học. Cách thứ tư Trang 10
16. Phương pháp biểu diễn trang web thơng qua vector cĩ cấu trúc. Cụ thể các bước thực hiện xây dựng vector gồm các bước như sau: Bước 1: Gán d là bậc cao nhất của các trang trong tập được xét. Bước 2: Thiết lập vector với cấu trúc gồm d + 1 các phần: - Phần 1 biểu diễn chính cho trang Web đang xét. - Phần 2 đến phần thứ d+1 biểu diễn các trang láng giềng của trang được biểu diễn ở phần 1, mỗi trang láng giềng được biểu diễn ở 1 phần riêng rẽ. Từ đĩ thơng qua các cách biểu diễn trang web bằng vector như đã trình bày ở phía trên ta cĩ thể thấy rằng đa phần các phương pháp biểu diễn trang web bằng mơ hình vector sẽ kết hợp các thơng tin về web đĩ với các trang láng giềng để cĩ được hiệu suất phân lớp tốt hơn so với hiệu suất của phương pháp biểu diễn trang web bằng mơ hình vector lưu thơng tin về từ khĩa và số lần xuất hiện của nĩ chỉ trong trang web đang xét. 1.2.3. Tổng quan về phương pháp phân lớp văn bản Hiện nay, cĩ rất nhiều các phương pháp dùng để phân lớp văn bản như phương pháp Bayes, sử dụng cây quyết định, k láng giềng gần nhất hay SVM. Thuật tốn học máy thường được sử dụng để xây dựng mơ hình phân lớp văn bản một cách tự động. Ngồi ra chúng ta cịn cĩ thể kể đến các phương pháp đặc biệt hơn dùng để phân lớp trong một số lĩnh vực. Ví dụ khi mơ hình phân loại thấy xuất hiện một cụm từ trong văn bản thì hệ thống sẽ phân văn bản đĩ vào một lớp nào đĩ. Trong trường hợp các văn bản cĩ số đặc trưng hơn khơng nhiều như vậy thì chúng ta đưa ra các phương pháp phân lớp dựa vào nội dung trong văn bản độ phù hợp của văn bản đĩ với các văn bản trong tập huấn luyện. Trong mơ hình học máy được áp dụng, văn bản trong tập huấn luyện đã được gán nhãn trước và mơ hình phân loại cần phải tìm cách để trích chọn ra các đặc trưng của các văn bản thuộc mỗi lớp. Trang 11
17. 1.2.4. Ứng dụng của việc phân lớp dữ liệu văn bản Phân lớp dữ liệu văn bản cĩ vai trị vơ cùng quan trọng với cơng việc tìm kiếm dữ liệu văn bản. Thơng qua phân lớp văn bản chúng ta cĩ thể xác định ra được chủ để phân lớp dữ liệu muốn tìm kiếm. Ngồi ra chúng ta cĩ thể kể đến một ứng dụng nữa của việc phân lớp dữ liệu văn bản là việc ứng dụng để lọc văn bản hoặc một phần văn bản chứa những thơng tin cần tìm mà khơng làm mất hay ảnh hưởng tới tính phức tạp ngơn ngữ tự nhiên. Phân lớp dữ liệu văn bản cịn cĩ rất nhiều ứng dụng đa dạng khác trong thực tế, điển hình chúng ta cĩ thể kể đến những ứng dụng trích chọn thơng tin trên mạng Internet. Cĩ rất nhiều trang cĩ nội dung khơng lành mạnh hay phản động hoặc đăng những nội dung sau sự thật nhằm tăng lượng người xem, những nội dung này cĩ khả năng lẫn lộn vào kết quả trả về của các bộ máy tìm kiếm thơng tin trên mạng hoặc cĩ thể gây phiền tối cho những người dùng internet bằng các email rác. Từ đĩ chúng ta ngày càng thấy rõ sự cần thiết của việc ứng dụng việc phân lớp văn bản vào việc xây dựng các mơ hình lọc thơng tin trên mạng internet. Từ đĩ cĩ thể thấy rằng phân lớp văn bản đã và đang là một trong các cơng cụ khơng thể thiếu trong thời đại hiện nay, vì vậy phân lớp dữ liệu văn bản đang là một trong các vấn đề được quan tâm phát triển được hàng đầu với mục đích tạo ra những cơng cụ hữu ích cho thế giới nĩi chung và lĩnh vực cơng nghệ thơng tin nĩi riêng. 1.2.5. Quá trình phân lớp dữ liệu văn bản: Phân lớp dữ liệu văn bản cĩ thể chia làm 4 bước cơ bản sau: Trang 12
18. Sơ đồ dưới đây thể hiện bộ khung cho việc phân lớp dữ liệu văn bản, trong đĩ cĩ thể kể đến ba cơng đoạn chính: Cơng đoạn 1: Biểu diễn đối tượng văn bản dưới dạng cĩ cấu trúc, xây dựng tập dữ liệu được gán nhãn. Cơng đoạn 2: Dùng các kỹ thuật học máy để tiến hành huấn luyện trên các mẫu vừa được biểu diễn ở cơng đoạn 1. Thực chất cơng đoạn 1 tạo ra các vector đầu vào cho cơng đoạn 2. Cơng đoạn 3: Mở rộng các dữ liệu thêm vào được cung cấp bởi người dùng để cải thiện hiệu suất. Trang 13
19. Hình 1.3 Sơ đồ biểu diễn quá trình phân lớp dữ liệu văn bản 1.2.6. Đánh giá máy phân lớp dữ liệu văn bản Trong thực tế khơng cĩ một phương pháp phân lớp dữ liệu văn bản nào là tuyệt đối trong mọi hồn cảnh. Bất cứ một phương pháp phân loại nào cũng đều tồn tại độ sai số. Do đĩ chỉ ra độ đo để cĩ thể đánh giá chính xác được hiệu suất của mơ hình phân lớp sẽ giúp xác định được phương pháp nào là tốt hay khơng tốt. Cĩ thể đưa ra một số cơng thức chung để đánh giá hiệu suất của các mơ hình. Độ hồi tưởng và độ chính xác, độ và độ đo F1 được sử dụng khá phổ biến trong việc đánh giá độ chính xác của các mơ hình phân lớp. Để dễ hiểu hơn, chúng ta cĩ cơng thức: Trang 14
20. 1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp. Phân lớp dữ liệu văn bản hiện đang cĩ vai trị rất quan trọng trong sự phát triển của tồn thế giới, tùy vào độ phức tạp của từng loại văn bản khả năng thực thi của các mơ hình phân lớp sẽ khác nhau. Cĩ 3 yếu tố thiết yếu ảnh hưởng đến kết quả của việc phân lớp cĩ thể kể đến: Tập dữ liệu được thiết lập nhãn trước phải đủ lớn để huấn luyện cho mơ hình phân lớp. Cĩ được một tập dữ liệu chuẩn và đủ lớn sẽ giúp cho việc học của mơ hình được tốt hơn và đem lại kết quả phân lớp sau này chính xác hơn. Phương pháp tách từ khĩa trong văn bản ảnh hưởng tới quá trình biểu diễn văn bản bằng vector vì các phương pháp tách đơn giản thường sẽ gặp vấn đề với những ngơn ngữ khác nhau, do đĩ việc xây dựng phương pháp tách từ khĩa là một yếu tố thiết yếu. Phân lớp dữ liệu văn bản phải sử dụng thuật tốn hợp lý về thời gian xử lý gồm: thời gian để huấn luyện và thời gian thực hiện phân lớp, thêm nữa thuật tốn sẽ khơng phân lớp lại tồn bộ tập văn bản khi thêm vào đối tượng dữ liệu văn bản mới mà chỉ thực hiện phân lớp cho đối tượng văn bản mới, ngồi ra thuật tốn cần cĩ khả năng giảm nhiễu khi phân lớp dữ liệu văn bản. 1.3. Các thuật tốn học máy ứng dụng trong phân lớp 1.3.1. Phương pháp học cĩ giám sát 1.3.1.a. Tổng quan về bài tốn học cĩ giám sát Trang 15
21. Mục tiêu của bài tốn là để huấn luyện tạo nên một hàm ánh xạ từ tập X tới tập Y. Cụ thể nếu tập huấn luyện gồm các cặp (xi , yi ), với yi ∈Y là nhãn phân loại của mẫu xi∈X. Một thủ tục chuẩn là các cặp (xi, yi) được thử theo giả thiết độc lập trên khắp miền giá trị X × Y. 1.3.1.b. Giới thiệu về phương pháp học cĩ giám sát Giải quyết bài tốn học cĩ giám sát cần cĩ nhiều bước khác nhau: • Bước 1: Xác định thể loại của tập dữ liệu huấn luyện. • Bước 2: Tiến hành Thu thập tập dữ liệu huấn luyện. • Bước 3: Thiết lập cấu trúc biểu diễn các đặc trưng đầu vào. • Bước 4: Thiết lập cấu trúc của hàm chức năng cần huấn luyện và phương pháp học tương ứng. • Bước 4: Hồn thiện việc học. 1.3.1.c. Phương pháp học cĩ giám sát sử dụng thuật tốn k láng giềng gần nhất. Như đã trình bày phía trên, cĩ rất nhiều thuật tốn học cĩ giám sát trong Trang 16
22. thực tế, trong nghiên cứu này tơi sẽ giới thiệu một phương pháp học sử dụng thuật tốn k láng giếng gần nhất, một phương pháp học cĩ giám sát điển hình. Phương pháp này được đánh giá là một trong những phương pháp hàng đầu được áp dụng từ những ngày đầu trong nghiên cứu phân loại dữ liệu văn bản. Phương pháp này sử dụng ý tưởng là khi cần phân loại một đối tượng văn bản, thuật tốn sẽ tính khoảng cách (Euclide, Manhattan, Cosine, ) của tất cả đối tượng văn bản trong tập dữ liệu văn bản đã thiết lập nhãn đến đối tượng văn bản này để xác định k văn bản cĩ khoảng cách gần nhất, được gọi là k láng giềng gần nhất, sau đĩ đánh trọng số cho các chủ để bằng các khoảng cách này. Trọng số một chủ đề chính là tổng khoảng cách ở trên của các văn bản trong k văn bản gần nhất cùng chủ đề, chủ đề nào khơng xuất hiện trong k văn bản thì trọng số được thiết lập là 0. Các chủ đề tiếp đĩ sẽ được sắp xếp lại theo chiều giảm dần của trọng số. Các chủ đề trọng số cao sẽ được coi là nhãn của đối tượng dữ liệu văn bản cần phân loại. chủ đề cj đối với văn bản x được tính giá trị trọng số như sau : Trong đĩ: Giá trị y (di, c) thuộc vào miền {0,1}, với: y = 0: văn bản di khơng được gán nhãn chủ đề cj y = 1: văn bản di được gán nhãn chủ đề cj sim (x, d): độ tương đồng giữa văn bản x và văn bản d. Cĩ thể dùng cơng thức cosine để tính khoảng cách giữa 2 vector biểu diễn văn bản: Trang 17
23. bj là ngưỡng phân loại của nhãn cj giá trị này cĩ được sau quá trình huấn luyện. 1.3.1.d. Phương pháp học cĩ giám sát sử dụng Support vector machine (SVM) Máy hỗ trợ vector là phương pháp phân lớp đặc biệt hiệu quả trong giải quyết nhận dạng mẫu chỉ cĩ hai lớp sử dụng nguyên lý Giảm tiểu tối đa rủi ro cấu trúc. Thuật tốn cĩ ý tưởng chính là với một tập huấn luyện được biểu diễn trong khơng gian vector và mỗi đối tượng tài liệu được xem là 1 điểm, mục tiêu phương pháp là tìm ra một mặt siêu phẳng h chia các điểm trong khơng gian này thành hai lớp + và -. Khoảng cách từ điểm gần nhất tới mặt phẳng càng lớn thì việc phân loại càng chính xác. Hình 1.4 Mặt siêu phẳng h phân các điểm thành 2 lớp + và - với khoảng cách biên lớn nhất. Các điểm gần mặt siêu phẳng h nhất là các vector hỗ trợ 1.3.2. Thuật tốn phân lớp dữ liệu theo phương pháp học bán giám sát 1.3.2.a. Khái niệm Phương pháp học bán giám sát là một phương phương pháp học trong ngành học máy sử dụng đồng thời dữ liệu đã thiết lập nhãn và cả dữ liệu chưa xác định nhãn. Trong thực tế để cĩ được dữ liệu xác định nhãn địi hỏi nhiều thời gian và cơng sức nhưng ngược lại dữ liệu chưa gán nhãn lại cĩ tương đối Trang 18
24. sẵn trong thế giới hiện tại. Từ đây, ta cĩ thể thấy được phương pháp học bán giám sát cĩ thể giúp thực hiện các cơng việc với quy mơ lớn. Phương pháp học bán giám sát bao gồm dữ liệu huấn luyện và dữ liệu chưa xác định nhãn. Phương pháp này cĩ thể được dùng trong các cơng việc phân lớp hay phân nhĩm. Phương pháp học bán giám sát cĩ mục tiêu nhằm vào việc huấn luyện mơ hình phân lớp tốt hơn phương pháp học cĩ giám sát cùng trên tập dữ liệu xác định nhãn và chưa được xác định nhãn. 1.3.2.b. Tổng quan về một số phương pháp học bán giám sát Hiện nay học bán giám sát cĩ rất nhiều phương pháp được sử dụng cũng như được nghiên cứu và phát triển. Cĩ thể kể đến một số phương pháp phổ biến như: Nạve Bayes, self-training hay co-training và transductive support vector machine, Về cơ bản khơng thể xác định được chính xác phương pháp hiệu quả nhất trong các phương pháp này. Tiếp theo, chúng ta sẽ tìm hiểu tổng quan một số thuật tốn học bán giám sát thường gặp.  Self-training Self-training sử dụng một tập phân lớp ban đầu được cùng với một lượng nhỏ dữ liệu đã xác định nhãn. Tập phân lớp sẽ được dùng để thiết lập nhãn cho dữ liệu chưa xác định nhãn. Cĩ thể thấy rằng hầu hết các đối tượng dữ liệu chưa phân loại cĩ độ tin cậy cao, cũng như các nhãn dự đốn trước của chúng. Các dữ liệu này sau khi phân lớp sẽ được thêm vào tập huấn luyện. Mơ hình phân lớp sẽ được huấn luyện lại. Chú ý rằng việc tự học ở đấy chính là việc mơ hình phân lớp học trên chính các dữ liệu mà nĩ đã phân loại. Thuật tốn học Self-training cĩ thể được dùng trong việc xử lý các bài tốn của một số ngơn ngữ tự nhiên. Ngồi ra thuật tốn này cịn cĩ thể được dùng trong phân tách và dịch máy. Trang 19
25. Hình 1.5 Thuật tốn học self training  Co-training Thuật tốn học Co training là thuật tốn được dựa trên giả thiết rằng các đặc trưng cĩ thể được tách ra thành hai tập đặc trưng. Mỗi một tập đặc trưng lại cĩ khả năng huấn luyện một mơ hình phân lớp tốt. Hình 1.6 Thuật tốn học Co training Trang 20
26. CHƯƠNG 2 BÀI TỐN PHÂN LỚP ÁP DỤNG SVM VÀ PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT SVM Trong các nghiên cứu thời gian gần đây, phương pháp phân lớp dùng tập phân lớp vector hỗ trợ đang được nghiên cứu và áp dụng tương đối mạnh mẽ trong lĩnh vực phân lớp và nhận dạng. SVM là phương pháp được ra đời từ lý thuyết học thống kê do Vapnik và Chervonenkis nghiên cứu và phát triển. Đây là phương pháp cĩ nhiều tiềm năng phát triển về trong thực tiễn cũng như trong các nghiên cứu lý thuyết. Từ kết quả của những nghiên cứu gần đây cho thấy rằng SVM là phương pháp cĩ khả năng phân lớp khá tốt khơng chỉ đối với bài tốn phân lớp dữ liệu văn bản mà cịn trong nhiều ứng dụng như nhận dạng văn bản viết tay, phát hiện mặt người khung hình Khả năng phân lớp của phương pháp SVM được đánh giá là khá cao so với các phương pháp khác. 2.1. Máy hỗ trợ vector – Support Vector Machine SVM sử dụng thuật tốn học với mục tiêu tìm ra một mặt siêu phẳng làm nhỏ nhất cĩ thể độ phân lớp sai cho một đối tượng dữ liệu mới. Độ phân lớp sai của một mặt siêu phẳng được đặc trưng bởi khoảng cách từ điểm gần nhất tới siêu phẳng đấy. Đặc trưng thiết yếu thể hiện khả năng của mơ hình phân lớp chính là khả năng phân lớp những dữ liệu mới sau quá trình huấn luyện. Phương pháp huấn luyện sẽ được đánh giá là tốt nếu hiệu suất tổng quát hố của mơ hình phân lớp cao và ngược lại phương pháp huấn luyện sẽ được đánh giá là chưa tốt nếu hiệu suất tổng quát hĩa của mơ hình là thấp. Hiệu suất tổng quát hố ở đây phụ thuộc vào hai yếu tố là năng lực của máy học và sai số huấn luyện. Trong các tham số này thì sai số huấn luyện được hiểu là tỷ lệ sai lỗi của quá trình phân lớp trên tập dữ liệu huấn luyện. Cịn yếu tố thứ hai năng lực của máy học được xác định bằng kích thước VC (Vapnik-Chervonenkis). Đây được coi là một khái niệm quan trọng đối với một mơ hình phân lớp. Kích thước VC được tính bởi số điểm cực đại mơ hình phân lớp cĩ thể tách trong khơng gian đối tượng cần phân loại. Trang 21
27. 2.1.1. Giới thiệu về thuật tốn SVM Xét ví dụ về bài tốn phân tập dữ liệu mẫu thành 2 lớp: m {( x i, yi) i = 1, 2, , N, x i∈ R } Trong đĩ đối tượng dữ liệu mẫu ở đây chính là các vector đối tượng được phân lớp và lớp chúng ta sẽ chia thành lớp các mẫu dương và lớp các mẫu âm như trong hình 1.4: Lớp các mẫu dương là lớp các mẫu xi thuộc vào lĩnh vực được quan tâm và được thiết lập nhãn yi = 1. Lớp các mẫu âm là các mẫu xi khơng thuộc vào lĩnh vực được quan tâm và được thiết lập nhãn yi = - 1. Phương pháp về bản chất chính là một bài tốn tối ưu, mục tiêu của bài tốn này là tìm ra một khơng gian H và mặt siêu phẳng quyết định h trên H sao với sai số phân lớp là cực tiểu. Mơ hình phân lớp SVM ở đây thực chất chính là mặt siêu phẳng phân tách các mẫu dương và âm với độ chênh lệch là lớn nhất, độ chênh lệch ở đây được xác định bằng khoảng cách nhỏ nhất giữa các mẫu dương và các mẫu âm với mặt siêu phẳng. Phương trình của mặt siêu phẳng cĩ thể xác định như sau: C + w1 x1 + w2 x2 + + wn xn = 0 Hoặc chúng ta cĩ thể sử dụng cơng thức tương đương sau để biểu diễn cho phương trình của mặt siêu phẳng C + ∑w x = 0 (2.2) i i với i=1, ,n Trang 22
28. w = w1 + w2 + + wn là bộ hệ số siêu phẳng hay là vector trọng số của mặt siêu phẳng, C là độ dịch, Thay đổi w và C cĩ thể làm thay đổi hướng và khoảng cách từ gốc toạ độ đến mặt siêu phẳng. Tập phân lớp SVM được định nghĩa như sau: f(x) = sign(C + ∑wi xi) (2.3) sign(z) = +1 nếu z ≥0, sign(z) = -1 nếu z < 0. Khi f(x) = 1 thì xác định x thuộc về lĩnh vực được quan tâm, và ngược lại, nếu f(x) = -1 thì x khơng thuộc vào lĩnh vực cần quan tâm. Mơ hình học SVM cĩ thể được coi là một mơ hình học với các siêu phẳng phụ thuộc vào tham số vector trọng số w của mặt siêu phẳng và tham số độ dịch C. Mục tiêu của mơ hình học SVM là xác định được w và C để cĩ thể cực đại hố khoảng cách tối thiểu giữa các điểm dương và điểm âm với mặt siêu phẳng. Về cơ bản việc xây dựng mơ hình cần phải giải phương trình sau: để cĩ thể tìm ra được vector trọng số w và sai số của mỗi điểm trong tập huấn luyện để cĩ được phương trình tổng quát của mặt siêu phẳng: f(x1, x2, , xn) = C +∑ wi xi Với i = 1, , n. Trong đĩ n là tổng số các đối tượng dữ liệu dùng để huấn luyện. 2.1.2. Huấn luyện SVM Để huấn luyện máy hỗ trợ vector thực chất chúng ta sẽ tiến hành giải bài tốn quy hoạch tồn phương Support Vector Machine. Để giải bài tốn này chúng ta cĩ thể dùng các phương pháp số. Cụ thể các phương pháp này cần một Trang 23
29. ma trận kích thước bằng bình phương của số lượng mẫu dùng trong việc training. Điều này trong thực tế đơi khi khơng khả thi vì kích thước của tập dữ liệu dùng để training thường rất lớn (thậm chí cĩ thể đến hàng chục nghìn mẫu huấn luyện). Nhằm giải quyết vấn đề nêu trên người ta đã phát triển nhiều thuật tốn khác nhau dựa trên việc phân rã tập training thành những nhĩm dữ liệu. Lúc này bài tốn quy hoạch tồn phương sẽ được giải với kích thước nhỏ hơn. Sau đĩ, những thuật tốn này sẽ kiểm tra các điều kiện Karush KuhnTucker để tìm ra được phương án tối ưu nhất. Một vài phương pháp huấn luyện dựa vào tính chất: Nếu trong tập training của bài tốn quy hoạch tồn phương Support Vector Machine con (bài tốn nhỏ) cĩ ít nhất một mẫu vi phạm vào điều kiện Karush KuhnTucker, thì bài tốn này sau khi được giải, hàm mục tiêu sẽ tăng. Một loạt các bài tốn quy hoạch tồn phương Support Vector Machine con với ít một mẫu nào đĩ vi phạm các điều kiện Karush KuhnTucker được đảm bảo sẽ sự hội tụ đến phương án tối ưu. 2.1.3. Ưu điểm của SVM trong phân lớp văn bản Chúng ta cĩ thể thấy từ các thuật tốn phân lớp hai lớp như SVM đến các thuật tốn phân lớp đa lớp đều cĩ đặc điểm chung là yêu cầu văn bản phải được biểu diễn dưới dạng vector đặc trưng, tuy nhiên các thuật tốn khác đều phải sử dụng các uớc lượng tham số và ngưỡng tối ưu trong khi đĩ thuật tốn SVM cĩ thể tự tìm ra các tham số tối ưu này. Trong các phương pháp thì SVM là phương pháp sử dụng khơng gian vector đặc trưng lớn nhất (hơn 10.000 chiều) trong khi đĩ các phương pháp khác cĩ số chiều bé hơn nhiều (như Nạve Bayes là 2000, k-Nearest Neighbors là 2415 ). Trang 24
30. Trong cơng trình của mình năm 1999, Joachims đã so sánh SVM với Nạve Bayesian, k-Nearest Neighbour, Rocchio, và C4.5 và đến năm 2003, Joachims đã chứng minh rằng SVM làm việc rất tốt cùng với các đặc tính được đề cập trước đây của văn bản. Các kết quả cho thấy rằng SVM đưa ra độ chính xác phân lớp tốt nhất khi so sánh với các phương pháp khác. Theo Xiaojin Zhu thì trong các cơng trình nghiên cứu của nhiều tác giả (chẳng hạn như Kiritchenko và Matwin vào năm 2001, Hwanjo Yu và Han vào năm 2003, Lewis vào năm 2004) đã chỉ ra rằng thuật tốn SVM đem lại kết quả tốt nhất phân lớp văn bản. Kiritchenko và Matwin đã nghiên cứu và so sánh phương pháp SVM với kỹ thuật Nạve Bayesian, sau đĩ đã chứng minh được rằng SVM là phương pháp tốt nhất cho phân lớp thưđiện tử cũng như phân lớp văn bản. Hwanjo Yu và Han cho thấy rằng SVM hồn tồn được tiến hành tốt nhất so với các phương pháp phân lớp văn bản khác. Tất cả các tài liệu nghiên cứu hiện nay cho thấy rằng SVM đưa ra kết quả chính xác nhất trong khía cạnh phân lớp văn bản. Lewis đã nghiên cứu phân lớp văn bản và đã khám phá ra rằng kết quả của SVM là tốt nhất. Lewis đã đưa ra tập hợp nhỏ các tài liệu của phân lớp văn bản. Tác giả đã cố gắng cải tiến phương pháp RCV1 cho phân lớp văn bản và sử dụng phương pháp mới được ứng dụng cho một số kỹ thuật phân lớp văn bản khác nhau. SVM đã đưa ra kết quả tốt nhất khi đặt dựa vào k-người láng giềng gần nhất và kỹ thuật tập phân lớp RocchioStyle Prototype. Những phân tích của các tác giả trên đây cho thấy SVM cĩ nhiều điểm phù hợp cho việc ứng dụng phân lớp văn bản. Và trên thực tế, các thí nghiệm phân lớp văn bản tiếng Anh chỉ ra rằng SVM đạt độ chính xác phân lớp cao và tỏ ra xuất sắc hơn so với các phương pháp phân lớp văn bản khác. Vấn đề căn bản của học bán giám sát là chúng ta cĩ thể tận dụng dữ liệu chưa gán nhãn để cải tiến hiệu quả của độ chính xác trong khi phân lớp, điều này Trang 25
31. được đưa ra để so sánh với một tập phân lớp được thiết kề mà khơng tính đến dữ liệu chưa gán nhãn. Trong phần sau của chương này, nghiên cứu sẽ giới thiệu một phương thức cải tiến của SVM là bán giám sát SVM (semi-supervised support vector machine – S3VM). Bán giám sát SVM được đưa ra nhằm nâng SVM lên một mức cao hơn, trong khi SVM là một thuật tốn học cĩ giám sát, sử dụng dữ liệu đã gán nhãn thì bán giám sát SVM sử dụng cả dữ liệu gán nhãn (tập huấn luyện – training set) kết hợp với dữ liệu chưa gán nhãn (working set). 2.2. Bán giám sát SVM và phân lớp trang Web 2.2.1. Giới thiệu về bán giám sát SVM Chúng ta sẽ giới thiệu phương thức cải tiến của SVM là Bán giám sát SVM (Semi Supervised Support Vector Machine - S3VM). Cho một tập huấn luyện (training set) của dữliệu gán nhãn và cĩ sự tham gia của một tập các dữ liệu chưa gán nhãn (working set), S3VM xây dựng một máy hỗ trợ vector sử dụng cả training set và working set. Bài tốn truyền dẫn sẽ dựđốn giá trị của một hàm phân lớp tới các điểm đã cho trong working set. Trong khi SVM là một thuật tốn cĩ giám sát sử dụng dữ liệu đã gán nhãn, thì S3VM được xây dựng sử dụng hỗn hợp dữ liệu gán nhãn (training set) và dữ liệu chưa gán nhãn (working set). Mục đích là để gán các lớp nhãn tới working set một cách tốt nhất, sau đĩ sử dụng hỗn hợp dữ liệu huấn luyện đã gán nhãn và dữ liệu working set sau khi đã gán nhãn để phân lớp những dữ liệu mới. Nếu working set rỗng thì phương pháp này trở thành phương pháp chuẩn SVM để phân lớp. Nếu training set rỗng, sau đĩ phương pháp này sẽ trở thành hình thể học khơng giám sát. Học bán giám sát xảy ra khi cả training set và working set khơng rỗng. Để hiểu một cách rõ ràng cụ thể về S3VM, thì chúng ta cần hiểu về SVM đã được trình bày ở trên. Với thời gian và điều kiện khơng cho phép, trong khố Trang 26
32. luận này em chỉ cĩ thể tìm hiểu về thuật tốn S3VM là bài tốn phân lớp nhị phân. Cho trước một tập huấn luyện gồm những dữ liệu đã gán nhãn cùng với tập dữ liệu chưa gán nhãn working set bao gồm n dữ liệu. Mục đích là gán nhãn cho những dữ liệu chưa gán nhãn này. Với hai lớp đã cho trước gồm lớp dương (lớp +1) và lớp âm (lớp –1). Mỗi dữ liệu được xem như một điểm trong khơng gian vector. Mỗi điểm i thuộc tập dữ liệu huấn luyện cĩ một sai số là ηivà mỗi điểm j thuộc working set sẽ cĩ hai sai sốξj (sai số phân lớp với giả sử rằng j thuộc lớp +1) và zi (sai số phân lớp với giả sử rằng j thuộc lớp –1). S au khi đã tìm được ξi và zj, chúng ta sẽ cĩ được sai số nhỏ nhất của mỗi điểm j, Nếu ξi zj thì điểm j thuộc lớp âm. Quá trình này diễn ra trên tất cả các điểm thuộc working set, sau khi quá trình này đã hồn thành, tất cả các điểm chưa gán nhãn sẽđược gán nhãn. Tập dữ liệu chưa gán nhãn working set sau khi đã gán nhãn sẽđược đưa vào tập dữ liệu huấn luyện, tiếp theo đĩ sẽ sử dung thuật tốn SVM để học tạo ra SVM mới, SVM này chính là S3VM cĩ một siêu phẳng mới. Sau đĩ áp dụng siêu phẳng này để phân lớp các mẫu dữ liệu mới được đưa vào. 2.2.2. Phân lớp trang Web sử dụng bán giám sát SVM 2.2.2.a. Giới thiệu bài tốn phân lớp trang Web (Web Classification) Trang 27
33. Phân lớp trang Web là một trường hợp đặc biệt của phân lớp văn bản bởi sự hiện diện của các siêu liên kết trong trang Web, cấu trúc trang Web chặt chẽ, đầy đủ hơn, dẫn đến các tính năng hỗn hợp như là plain texts, các thẻ hypertext, hyperlinks . Internet với hơn 10 tỷ trang Web là một tập huấn luyện rất phong phú về mọi chủđề trong cuộc sống, hơn nữa với số lượng chủđề trên các Website là khơng nhiều thì việc sử dụng Internet như cơ sở huấn luyện rất phù hợp. Trong các trang Web, tuy độ chính xác khơng phải là tuyệt đối, nhưng ta cĩ thể thấy mỗi chủđề gồm cĩ nhiều từ chuyên mơn với tần suất xuất hiện rất cao, việc tận dụng tần số phụ thuộc của các từ này vào chủđề cĩ thểđem lại kết quả khả quan cho phân lớp. 2.2.2.b. Áp dụng S3VM vào phân lớp trang Web Cĩ thể thấy trang Web là siêu văn bản (hypertext) rất phổ dụng hiện nay. Nội dung của các trang Web thường được mơ tả ngắn gọn, súc tích, cĩ các siêu liên kết chỉđến các Web cĩ nội dung liên quan và cho phép các trang khác liên kết đến nĩ. Nhưđã nĩi trên, vì được xem như là các văn bản thơng thường nên trong quá trình phân lớp trang Web việc biểu diễn văn bản sử dụng mơ hình khơng gian vector. Việc biểu diễn và xử lý tài liệu Web cũng giống như biểu diễn và xử lý văn bản bằng mơ hình này. Tuy nhiên trong phân lớp Web thì việc khai thác thế mạnh của siêu liên kết trong văn bản là một vấn đềđáng quan tâm. Với việc sử dụng các siêu liên kết giữa các trang Web từđĩ cĩ thể lấy được các thơng tin về mối liên hệ giữa nội dung các trang, và dựa vào đĩ để nâng cao hiệu quả phân lớp và tìm kiếm. Để áp dụng vào phân lớp trang Web, thuật tốn S3VM xem mỗi trang Web là một vector f(d1, d2, , dn)được biểu diễn giống như văn bản. Áp dụng cơng thức (2.5) trong phương trình của siêu phẳng: Trang 28
34. f(x1, x2, , xn) = C +∑ wi xi Thay thế mỗi văn bản tương ứng với mỗi trang Web vào phương trình siêu phẳng này: f(d1, d2, ,dn) = C +∑ wi di (2.6) Với i=1, ,n. Nếu f(d) ≥ 0 thì trang Web thuộc lớp +1. Ngược lại nếu f(d) < 0 trang Web thuộc lớp –1. Cĩ thể thấy rằng quá trình áp dụng thuật tốn S3VM vào bài tốn phân lớp trang Web chính là việc thay thế vector trọng số biểu diễn trang Web đĩ vào phương trình siêu phẳng của S3VM, từđĩ tìm ra được nhãn lớp của các trang Web chưa gán nhãn. Như vậy, thực chất của quá trình phân lớp bán giám sát áp dụng đối với dữ liệu là các trang Web là tập dữ liệu huấn luyện là các trang Web cịn tập working set (dữ liệu chưa gán nhãn) là những trang Web được các trang Web đã cĩ nhãn trong tập huấn luyện trỏ tới. Trang 29
35. CHƯƠNG 3 KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ Trong nghiên cứu này, tác giả sử dụng phần mềm nguồn mở để tiến hành thực nghiệm phân lớp bán giám sát các tài liệu Web. Trong nội dung của chương sẽ giới thiệu giới thiệu về phần mềm nguồn mở SVMlin do Vikas Sindhwani cơng bố, trình bày quá trình khai thác phần mềm nhằm thực hiện bài tốn phân lớp và đánh giá. 3.1. Giới thiệu về phần mềm SVMlin SVMlin là gĩi phần mềm dành cho SVMs tuyến tính, nĩ thoả mãn bài tốn phân lớp một số lớn các mẫu dữ liệu và các đặc trưng. Là chương trình phần mềm được viết trên ngơn ngữ C++. Ngồi tập dữ liệu đã được gán nhãn, SVMlin cịn cĩ thể tận dụng tập dữ liệu chưa được gán nhãn trong quá trình học. Tập dữ liệu chưa được gán nhãn này thực sử hữu ích trong việc nâng cao độ chính xác của quá trình phân lớp khi mà số lượng dữ liệu được gán nhãn từ trước là rất ít. Hiện tại SVMlin đã thực hiện cài đặt các thuật tốn sau:  Thuật tốn học cĩ giám sát (chỉ sử dụng các dữ liệu đã gán nhãn) Thuật tốn phân lớp bình phương tối thiểu đã được chuẩn hĩa tuyến tính (Linear Regularized Least Squares Classification).  Thuật tốn học bán giám sát (cĩ thể sử dụng các dữ liệu chưa gán nhãn) Thuật tốn học tuyến tính SVM truyền dẫn sử dụng nhiều lần chuyển đổi (Multi-switch linear Transductive L2-SVMs) Theo Vikas Sindhwani, khi dùng SVMlin phân loại văn bản (tập dữ liệu RCV1v2/LYRL2004) với 804414 dữ liệu gán nhãn và 47326 đặc trưng, SVMlin mất ít hơn hai phút để huấn luyện SVM tuyến tính trong một máy Intel với tốc độ xử lý 3GHz và 2GB RAM. Nếu chỉ cho 1000 nhãn, nĩ cĩ thể sử dụng hàng trăm ngàn dữ liệu chưa gán nhãn để huấn luyện một SVM tuyến tính bán giám Trang 30
36. sát trong vịng khoảng 20 phút. Dữ liệu chưa gán nhãn rất hữu ích trong việc cải thiện quá trình phân lớp khi số lượng nhãn lớp khơng quá lớn. Download SVMlin: phiên bản mới nhất của SVMlin được tải tại trang Web: Cài đặt: - Thực hiện giải nén file cài đặt bằng các lệnh sau: unzip svmlin.zip tar –xvzf svmlin.tar.gz - Kết quả giải nén sẽ tạo ra thư mục svmlin-v1.0 gồm các File: Makefile, ssl.h, ssl.cpp và svmlin.cpp. - Gõ lệnh: make Sẽ tạo ra file thực thi svmlin Quá trình thực thi này được sử dụng để huấn luyện, kiểm tra và đánh giá quá trình thực hiện. 3.2. Sử dụng phần mềm và kết quả đánh giá  Các file dữ liệu Định dạng dữ liệu đầu vào cho SVMlin tương tự như định dạng của bộ cơng cụ SVM-Light/LIBSVM (điểm khác biệt duy nhất là khơng cĩ cột đầu tiên mơ tả nhãn của các dữ liệu) Mỗi một dịng mơ tả một mẫu dữ liệu và là danh sách các cặp gồm chỉ số đặc trưng : giá trị đặc trưng cho các đặc trưng cĩ giá trị khác khơng, được phân cách nhau bởi một ký tự trống. Mỗi hàng được kết thúc bằng một ký tự ‘\n’. : : : . Ta xét một ví dụ với ma trận dữ liệu với 4 dữ liệu và 5 đặc trưng như sau: Trang 31
37. 0 3 0 0 1 4 1 0 0 0 6 5 9 2 0 6 0 0 5 3. Được mơ tả trong file đầu vào là: 2:3 5:1 1:4 2:1 2:5 3:9 4:2 1:6 4:5 5:3 Nhãn của các dữ liệu huấn luyện được chứa trong một file riêng biệt, gọi là file mơ tả nhãn dữ liệu. Mỗi dịng của file chứa nhãn cho dữ liệu ở dịng tương ứng trong file mơ tả dữ liệu ở trên. Nhãn của dữ liệu cĩ thể nhận các giá trị sau: +1 (dữ liệu gán nhãn thuộc lớp dương) -1 (dữ liệu gán nhãn thuộc lớp âm) 0 (các dữ liệu chưa được gán nhãn)  Quá trình huấn luyện Gõ lệnh: svmlin [options] training_examples training_labels Trong đĩ: - training_examples.weights là File chứa dữ liệu huấn luyện - training_examples.outputs. File chứa kết quả mơ hình phân lớp  Kiểm tra (testing) Gõ lệnh: svmlin -f training_examples.weights test_examples_filename Trong đĩ: Trang 32
38. training_examples.weights: File chứa kết quả mơ hình phân lớp test_examples_filename: File chứa dữ liệu kiểm tra  Đánh giá Nếu nhãn của dữ liệu kiểm thử đã được biết trước, chúng ta sử dụng lệnh sau để tính ma trận thực thi của quá trình phân lớp: svmlin -f weights_filename test_examples_filename test_labels_filename  Dữ liệu dùng cho quá trình huấn luyện Dữ liệu huấn luyện được sử dụng bao gồm 1460 tài liệu (trongđĩ chỉ cĩ 50 tài liệu được gán nhãn) được lấy từ bộ dữ liệu chuẩn 20-newsgroups.  Kết quả phân lớp Với dữ liệu huấn luyện trên đây, SVMlin đạt độ chính xác là 92.8% khi lựa chọn chức năng multi-switch TSVM và đạt độ chính xác là 95.5% khi lựa chọn chức năng semi-supervised SVM. Điều này khẳng định tính hiệu quả của học bán giám sát SVM. Trang 33
39. KẾT LUẬN Kết quả của nghiên cứu đã chỉ ra được một số vấn đề về bài tốn phân lớp như: phương pháp phân lớp dữ liệu, phân lớp văn bản, sự áp dụng của thuật tốn học máy vào bài tốn phân lớp, trong đĩ tập trung trình bày về phương pháp học bán giám sát – phương pháp hiệu quả và được sử dụng phổ biến. Về phân lớp dữ liệu, nghiên cứu đã đưa ra bài tốn tổng quan và trình bày về phương pháp phân lớp dữ liệu tổng quát từ đĩ cĩ thể giúp người đọc hiểu về bài tốn phân lớp. Nghiên cứ cũng đã trình bày cơ bản về bài tốn phân lớp văn bản, cách một văn bản trong bài tốn phân lớp được biểu diễn, qua đĩ nêu lên các phương pháp phân lớp văn bản cơ bản hiện nay. Nghiên cứu đồng thời cũng đã tìm hiểu về việc sử dụng các thuật tốn học máy trong bài tốn phân lớp văn bản như: thuật tốn phân lớp sử dụng quá trình học cĩ giám sát và học bán giám sát. Kết quả của việc tìm hiểu đã nêu lên một số phương pháp học bán giám sát điển hình, trên cơ sở đĩ sẽ đi sâu tìm hiểu thuật tốn học bán giám sát SVM. Nghiên cứu cũng đã giới thiệu một cơng cụ cĩ tên là SVMlin, cách sử dụng phần mềm và kết quả chạy phần mềm do V. Sindhwani tiến hành trong năm 2007. Hướng nghiên cứu trong thời gian tới Như đã trình bày ở trên, trong nghiên cứu chưa thể tìm hiểu sâu, đặc biệt là tiến hành thực hiện phần mềm SVMlin đã khảo sát. Vì thế trong thời gian tới tơi sẽ tìm hiểu kỹ hơn về phần mềm để cĩ thể chủ động nắm vững việc thực hiện phần mềm, đặc biệt là các thuật tốn học bán giám sát nền tảng lý thuyết của phần mềm. Trang 34
40. TÀI LIỆU THAM KHẢO 1. Balaij Krishnapuuram, David Williams, Ya Xue,k Alex Hartemink, Lawrence Carin, Masrio A.T.Figueiredo (2005). On Semi-Supervised Classification. NIPS: 721-728, 2005. 2. Panu Erastox (2001). Support Vector Machines: Background and Practice. Academic Dissertation for the Degree of Licentiate of Philosophy. University of Helsinki, 2001. 3. T. Joachims (2003). Transductive learning via spectral graph partitioning. Proceeding of The Twentieth International Conference on Machine Learning (ICML2003): 290-297. Trang 35