Tìm hiểu SVM và ứng dụng thuật toán

Ngày đăng: 14/12/2013, 00:21

Đồ án tốt nghiệp đại học TRƯỜNG ĐẠI HỌC VINH KHOA CÔNG NGHỆ THÔNG TIN ————————– ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC ĐỀ TÀI: TÌM HIỂU SVM ỨNG DỤNG THUẬT TOÁN SVM VÀO PHÂN LỚP TRANG WEB Sinh viên thực hiện : Nguyễn Văn Thông Mã sinh viên : 0851077270 Lớp : 49K-Công nghệ thông tin Thầy giáo chỉ dẫn: ThS. Trần Thị Kim Oanh Nghệ An, tháng 12 năm 2012 Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 1 Đồ án tốt nghiệp đại học LỜI CẢM ƠN Trước nhất, em xin bộc bạch lòng mang ơn chân tình sâu sắc nhất tới Gia sư ThS.Trần Thị Kim Oanh đã tận tình chỉ dẫn, khuyến khích, trợ giúp em trong suốt công cuộc thực hiện chủ đề. Em xin gửi lời cảm ơn sâu sắc tới quý Thầy Cô trong Khoa Công Nghệ Thông Tin đã truyền đạt học thức quý báu cho em trong những năm học vừa qua. Em xin gửi lời cảm ơn các anh chị trong nhóm seminar về khai hoang dữ liệu đã đon đả chỉ bảo trong công cuộc em làm khoá luận. Con xin nói lên lòng mang ơn so với Ông Bà, Bố Mẹ luôn là nguồn chăm chút, khuyến khích trên mỗi bước đường học thức của con. Xin chân tình cảm ơn các Anh Chị Đồng bọn, nhất là các member trong lớp 49K-Tin đã ủng hộ, trợ giúp khuyến khích tôi trong suốt thời gian học hành bốn năm trên giảng đường đại học thực hiện chủ đề. Dù rằng đã phấn đấu giải quyết luận văn trong phạm vi khả năng cho phép nhưng chắc cú sẽ không tránh khỏi những thiếu sót. Em kính mong thu được sự thông cảm tận tình chỉ bảo của quý Thầy Cô các Bạn. Em xin chân tình cảm ơn! Nghệ An, tháng 12 năm 2012 Sinh viên Nguyễn Văn Thông Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 2 Đồ án tốt nghiệp đại học MỞ ĐẦU Trong những năm gần đây, sự tiến triển vượt bậc của CNTT đã làm tăng số lượng mua bán thông tin trên mạng Mạng internet một cách đáng kể nhất là thư viện điện tử, tin tức điện tử… Thành ra mà số lượng văn bản hiện ra trên mạng Mạng internet cũng tăng với một vận tốc chóng mặt, vận tốc biến đổi thông tin là rất nhanh chóng chóng. Với số lượng thông tin khổng lồ như thế, một yêu cầu lớn đề ra là làm sao tổ chức tìm kiếm thông tin, dữ liệu có hiệu quả nhất. Bài toán phân lớp là một trong những bí quyết hợp lý cho yêu cầu trên. Nhưng một thực tiễn là khối lượng thông tin quá lớn, việc phân lớp dữ liệu thủ công là điều chẳng thể. Hướng khắc phục là một chương trình laptop auto phân lớp các thông tin dữ liệu trên. Không những thế, khi giải quyết các bài toán phân lớp auto thì gặp phải một số khốn khó là để xây dựng được bộ phân lớp có độ tin cậy cao đòi hỏi cần có một lượng lớn các mẫu dữ liệu đào tạo tức là các văn bản đã được gán nhãn lớp tương ứng. Các dữ liệu đào tạo này thường rất hiếm đắt vì đòi hỏi thời gian công sức của nhân loại. Cho nên phải có một phương thức học không cần nhiều dữ liệu gán nhãn có khả năng tận dụng được các nguồn dữ liệu chưa gán nhãn rất đa dạng như hiện tại, phương thức học này là học bán giám sát. Học bán giám sát chính là cách học sử dụng thông tin chứa trong cả dữ liệu chưa gán nhãn tập đào tạo, phương thức học này được sử dụng rất thông dụng vì tính tiện dụng của nó. Chính vì như vậy, đồ án “phân lớp bán giám sát ứng dụng thuật toán SVN vào phân lớp trang web” chăm chú vào tìm hiểu bài toán phân lớp sử dụng công cuộc học bán giám sát, việc áp dụng thuật toán bán giám sát máy trợ giúp vector (Support Vector Machine – SVM) vào phân lớp trang Website. Nội dung của đồ án được trình bày bao gồm 3 chương. Tổ chức cấu tạo như sau: • Chương 1 Khái quát về phân lớp bán giám sát. Phần đầu trình bày tổng quan về bài toán phân lớp dữ liệu, phân lớp văn bản, một số nét sơ bộ về học có giám sát. Phần cuối của chương giới thiệu các nội dung căn bản về phương thức học bán giám sát, trong đó đã giới thiệu một số thuật toán học bán giám sát điển hình. • Chương 2 Sử dụng SVM bán giám sát SVM vào bài toán phân lớp. Khóa luận trình bày những bước hoạt động căn bản nhất của thuật toán SVM, sau đó tìm hiểu thuật toán học bán giám sát SVM, một tôn tạo của SVM được trình bày trong [11]. Khoá luận trình bày một số áp dụng học bán giám sát vào bài toán phân lớp trang Website trong phần cuối cùng của chương. Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 3 Đồ án tốt nghiệp đại học • Chương 3 Hệ thống thực nghiệm phân loại trang Website nhận xét. Trình bày kết quả tìm hiểu của ?. Sindhwani về software nguồn mở SVMlin [14, 15, 18] mà do chính Author đề nghị thông báo. Các tìm hiểu này cho thấy software SVMlin phân lớp bán giám sát văn bản cho độ đúng đắn cao. Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 4 Đồ án tốt nghiệp đại học MỤC LỤC MỤC LỤC 5 Chương 1: TỔNG QUAN VỀ PHÂN LỚP BÁN GIÁM SÁT 8 1.1. Phân lớp dữ liệu .8 1.1.1. Bài toán phân lớp dữ liệu 8 1.1.2. Tiến trình phân lớp dữ liệu .9 1.2. Phân lớp văn bản .10 1.2.1. Đặt vấn đề .10 1.2.2. Mô hình vector trình diễn văn bản 10 1.2.3. Mẹo phân lớp văn bản 15 1.2.4. Ứng dụng của phân lớp văn bản .16 1.2.5. Các bước trong công cuộc phân lớp văn bản 16 1.2.6. Nhận xét mô hình phân lớp 18 1.2.7. Các yếu tố trọng yếu ảnh hưởng đến phân lớp văn bản .19 1.3. Một số thuật toán học máy phân lớp .20 1.3.1. Học có giám sát 20 1.3.2. Thuật toán phân lớp sử dụng công cuộc học bán giám sát .23 Chương 2: SỬ DỤNG SVM BÁN GIÁM SÁT SVM VÀO BÀI TOÁN PHÂN LỚP. 28 2.1. SVM – Support Vector Machine 28 2.1.1. Thuật toán SVM 29 2.1.2. Đào tạo SVM 30 2.1.3. Các ưu điểm của SVM trong phân lớp văn bản 31 2.2. Bán giám sát SVM phân lớp trang Website 32 2.2.1. Giới thiệu về bán giám sát SVM .32 2.2.2. Phân lớp trang Website sử dụng bán giám sát SVM .34 Chương 3: THỬ NGHIỆM HỌC BÁN GIÁM SÁT PHÂN LỚP TRANG WEB .36 3.1. Giới thiệu software SVMlin .36 3.1.1. Thuật toán học có giám sát (chỉ sử dụng các dữ liệu đã gán nhãn) 36 Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 5 Đồ án tốt nghiệp đại học 3.1.2. Bán giám sát (có thể sử dụng các dữ liệu chưa gán nhãn tương đối tốt) .36 3.2 Download SVMlin 37 3.3 Thiết lập: 37 3.4. Sử dụng software kết quả nhận xét .37 KẾT LUẬN .40 TÀI LIỆU THAM KHẢO 41 Ι. Tiếng Việt .41 II. Tiếng Anh 41 Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 6 Đồ án tốt nghiệp đại học Tóm lược nội dung Hiện tại, với một lượng lớn dữ liệu thì việc phân lớp dữ liệu đóng vai trò rất trọng yếu, là một trong những bài toán nan giải trong ngành nghề xủ lý dữ liệu văn bản. một yêu cầu căn bản được đề ra là cần tăng tính hiệu quả của thuật toán phân lớp, chuyên sâu giá trị của các độ đo tưởng niệm, đúng đắn của thuật toán. Mặt khác nguồn tài nguyên về chẳng hạn học có nhãn không phải luôn được đáp ứng, chính vì như thế phải có các thuật toán phân lớp sử dụng các chẳng hạn chưa có nhãn. Phân lớp bán giám sát đáp ứng được 2 yêu cầu nói trên. Các thuật toán phân lớp bán giám sát tận dụng các nguồn dữ liệu chưa gán nhãn rất đa dạng có trong tự nhiên kết phù hợp với một số dữ liệu đã được gán nhãn cho sẵn. Trong những năm gần đây, phương thức sử dụng bộ phân loại máy trợ giúp vector (Support Vector Machine – SVM ) được quan tâm sử dụng nhiều trong ngành nghề phân loại nhận dạng.từ các công trình khoa học thông báo cho thấy phương thức SVM có khả năng phân loại khá tốt so với bài toán phân loại văn bản cũng như trong nhiều ứng dụng khác. Trong đồ án này em thăm dò thuật toán học bán giám sát SVM trình bày các nội dung về software SVMlin do ?. Sindhwani đề nghị [18]. Trong năm 2006-2007, ?. Sindhwani đã dùng SVMlin tiến hành phân lớp văn bản từ nguồn 20-Newsgroups cho các kết quả tốt [14,15]. Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 7 Đồ án tốt nghiệp đại học Chương 1: TỔNG QUAN VỀ PHÂN LỚP BÁN GIÁM SÁT 1.1. Phân lớp dữ liệu 1.1.1. Bài toán phân lớp dữ liệu Là công cuộc phân lớp một đối tượng dữ liệu vào một hay nhiều lớp cho trước nhờ một mô hình phân lớp mà mô hình này được xây dựng dựa vào một tập hợp các đối tượng dữ liệu đã được gán nhãn từ trước gọi là tập dữ liệu học (tập đào tạo) [1-3]. Tiến trình phân lớp còn gọi là công cuộc gán nhãn cho các đối tượng dữ liệu. Như thế, trách nhiệm của bài toán phân lớp dữ liệu là cần xây dựng mô hình (bộ) phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc lớp nào. Có nhiều bài toán phân lớp dữ liệu, như phân lớp nhị phân, phân lớp đa lớp, phân lớp đa trị,…. Phân lớp nhị phân là công cuộc tiến hành việc phân lớp dữ liệu vào một trong hai lớp khác nhau dựa theo việc dữ liệu đó có hay không một số đặc điểm theo quy định của bộ phân lớp. Phân lớp đa lớp là công cuộc phân lớp với số lượng lớp to hơn hai. Như thế, tập hợp dữ liệu trong miền cân nhắc được phân tách thành nhiều lớp chứ không đơn thuần chỉ là hai lớp như trong bài toán phân lớp nhị phân. Về bản chất, bài toán phân lớp nhị phân là trường hợp riêng của bài toán phân lớp đa lớp. Trong phân lớp đa trị, mỗi đối tượng dữ liệu trong tập đào tạo cũng như các đối tượng mới sau khoảng thời gian được phân lớp có thể thuộc vào từ hai lớp trở lên. Chẳng hạn như website về việc bùng nổ bệnh cúm gia cầm, thủy cầm tại một số tính phía Bắc vừa thuộc về ngành nghề y tế liên quan đến lây bệnh sang người nhưng cũng thuộc về ngành nghề kinh tế liên quan đến nghề chăn nuôi… Trong những trường hợp như thế, việc xếp đặt một ebook vào nhiều hơn một lớp là phù phù hợp với yêu cầu thực tiễn. Sau đây tất cả chúng ta sẽ tìm hiểu tổng quan về công cuộc phân lớp dữ liệu sơ bộ về phương thức phân lớp dữ liệu. Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 8 Đồ án tốt nghiệp đại học 1.1.2. Tiến trình phân lớp dữ liệu Hình 1.1: Bài toán phân lớp Tiến trình phân lớp dữ liệu thường gồm hai bước: xây dựng mô hình (tạo bộ phân lớp) sử dụng mô hình đó để phân lớp dữ liệu. • Bước 1: một mô hình sẽ được xây dựng dựa vào việc nghiên cứu các đối tượng dữ liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này còn gọi là tập dữ liệu đào tạo (training data set). Các nhãn lớp của tập dữ liệu đào tạo được xác nhận bởi nhân loại trước khi xây dựng mô hình, chính vì vậy phương thức này còn gọi là học có giám sát (supervised learning). Trong ở giai đoạn này, tất cả chúng ta còn phải tính độ đúng đắn của mô hình, mà cần phải sử dụng một tập dữ liệu kiểm soát (check data set). Nếu độ đúng đắn là chấp thuận được (tức là cao), mô hình sẽ được sử dụng để xác nhận nhãn lớp cho các dữ liệu khác mới trong tương lai. Trong việc check mô hình, sử dụng các độ đo để nhận xét chất lượng của tập phân lớp, này là độ tưởng niệm, độ đúng đắn, độ đo F1 . Nội dung cụ thể về các độ đo này được trình bày trong mục (1.2.6). Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 9 Đồ án tốt nghiệp đại học Tồn tại nhiều phương thức phân lớp dữ liệu để khắc phục bài toán phân lớp tùy theo vào phương pháp xây dựng mô hình phân lớp như phương thức Bayes, phương thức cây quyết định, phương thức k-người láng giềng gần nhất, phương thức máy trợ giúp vector Các phương thức phân lớp khác nhau chủ chốt về mô hình phân lớp. Mô hình phân lớp còn gọi là thuật toán phân lớp. • Bước 2: sử dụng mô hình đã được xây dựng ở bước 1 để phân lớp dữ liệu mới. Như thế, thuật toán phân lớp là một ánh xạ từ miền dữ liệu đã có sang một miền giá trị rõ ràng của tính chất lớp, dựa theo giá trị các tính chất của dữ liệu. 1.2. Phân lớp văn bản 1.2.1. Đặt vấn đề Ngày nay cách thức sử dụng giấy tờ trong giao dịch đã dần được số hoá chuyển sang các dạng chữ lưu trữ bằng máy tính hoặc truyền tải trên mạng. Bởi nhiều chức năng ưu việt của ebook số như cách lưu trữ gọn nhẹ, thời gian lưu trữ bền lâu, tiện dụng trong thỏa thuận nhất là qua Mạng internet, đơn giản sửa đổi… nên càng ngày, số lượng văn bản số tăng trưởng một cách mau lẹ nhất là trên World Wide Website. Cùng với sự tăng trưởng về số lượng văn bản, nhu cầu tìm kiếm văn bản cũng tăng theo. Trong đời thường, phân lớp các văn bản được tiến hành một cách thủ công, nghĩa là tất cả chúng ta thực hiện công việc đọc từng văn bản một, cân nhắc sau này là gán nó vào một lớp rõ ràng nào đó. Phương pháp này sẽ tốn rất là nhiều thời gian công sức của nhân loại vì các văn bản là vô vàn, để gán mỗi văn bản vào một lớp đã nghĩ rằng một vấn đề chẳng thể vì thế không khả thi. Với số lượng văn bản khổng lồ thì việc phân lớp văn bản auto là một nhu cầu bức thiết. Vậy phân lớp văn bản là gì? Phân lớp văn bản (Text Categorization) là việc phân lớp áp dụng so với dữ liệu văn bản, tức là phân lớp một văn bản vào một hay nhiều lớp văn bản nhờ một mô hình phân lớp; mô hình này được xây dựng dựa vào một tập hợp các văn bản đã được gán nhãn từ trước. Phân lớp văn bản là một ngành nghề được Note nhất đã được tìm hiểu trong những năm gần đây. 1.2.2. Mô hình vector trình diễn văn bản Như đã trình bày ở phần trên, bước trước hết trong qui trình phân lớp văn bản là thao tác chuyển văn bản đang được miêu tả dưới dạng chuỗi các từ thành một mô hình khác, sao cho phù phù hợp với các thuật toán phân lớp. Thông thường người ta thường trình diễn văn bản bằng mô hình vector, mỗi văn bản được trình diễn bằng 1 vector trọng số. sáng tạo của Nguyễn Văn Thông – lớp 49K – Khoa Công nghệ thông tin Page 10

Xem Thêm  Tài liệu API jQuery - jquery loại bỏ phần tử theo lớp

– Tham khảo thêm –

Tham khảo thêm: Tìm hiểu SVM và ứng dụng thuật toán , Tìm hiểu SVM và ứng dụng thuật toán

Viết một bình luận