Đồ án Tìm hiểu về support vector machine cho bài toán phân lớp quan điểm - Phạm Văn Sơn

Nội dung text: Đồ án Tìm hiểu về support vector machine cho bài toán phân lớp quan điểm - Phạm Văn Sơn

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHỊNG o0o TÌM HIỂU VỀ SUPPORT VECTOR MACHINE CHO BÀI TỐN PHÂN LỚP QUAN ĐIỂM ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng Nghệ Thơng Tin Sinh viên thực hiện: Phạm Văn Sơn Giáo viên hƣớng dẫn: Ths. Nguyễn Thị Xuân Hƣơng Mã số sinh viên: 120704 HẢI PHỊNG 12/2012 0
2. MỤC LỤC MỤC LỤC 1 LỜI CẢM ƠN 3 MỞ ĐẦU 4 CHƢƠNG 1: TÌM HIỂU VỀ SUPPORT VECTOR MACHINE 6 1.1 PHÁT BIỂU BÀI TỐN 6 1.1.1 Trình bày tĩm tắt về phân lớp dữ liệu 8 1.1.2 Tại sao lại sử dụng thuật tốn SVM trong phân lớp dữ liệu 9 1.2 THUẬT TỐN SVM 10 1.2.1 Giới thiệu 10 1.2.2 Định nghĩa 10 1.2.3 Ý tƣởng của phƣơng pháp 10 1.2.4 Nội dung phƣơng pháp 11 1.2.4.1 Cơ sở lý thuyết 11 1.2.4.2 Bài tốn phân 2 lớp với SVM 12 1.2.4.3 Bài tốn nhiều phân lớp với SVM 13 1.2.4.4 Các bƣớc chính của phƣơng pháp SVM 14 CHƢƠNG 2: BÀI TỐN PHÂN LỚP QUAN ĐIỂM 15 2.1 SỰ KIỆN (Facts) VÀ QUAN ĐIỂM (Opinions) 15 2.2 NHU CẦU VỀ THƠNG TIN QUAN ĐIỂM VÀ NHẬN XÉT 15 2.3 MÁY TÌM KIỂM QUAN ĐIỂM / NHẬN XÉT 17 1
3. 2.4 LỊCH SỬ CỦA PHÂN TÍCH QUAN ĐIỂM VÀ KHAI THÁC QUAN ĐIỂM 18 2.5 XU HƢỚNG NGHIÊN CỨU GẦN ĐÂY 19 2.5.1 Xác định cụm từ, quan điểm 19 2.5.2 Sử dụng tính từ và phĩ từ 20 2.5.3 Sử dụng các động từ 21 2.5.4 Xác định chiều hƣớng, cụm từ, quan điểm 22 2.6 NHIỆM VỤ CỦA PHÂN TÍCH QUAN ĐIỂM 22 2.7 BÀI TỐN PHÂN LỚP QUAN ĐIỂM 22 2.7.1 Phân cực quan điểm và mức độ phân cực 23 2.7.2 Nhiệm vụ của bài tốn phân lớp quan điểm 24 2.7.3 Xây dựng mơ hình phân lớp để phân loại tài liệu 25 CHƢƠNG III: CHƢƠNG TRÌNH THỰC NGHIỆM 26 3.1 DỮ LIỆU THỬ NGHIỆM 26 3.2 CƠNG CỤ SỬ DỤNG 26 3.2.1 Cơng cụ sinh SRIML 26 3.2.2 Ngơn ngữ lập trình java 27 3.2.3 Cơng cụ phân lớp dữ liệu SVMLight 28 3.3 Kết quả thực nghiệm 29 KẾT LUẬN 34 TÀI LIỆU THAM KHẢO 35 2
4. LỜI CẢM ƠN Trƣớc hết, em xin chân thành cảm ơn Trƣờng Đại học Dân Lập Hải Phịng. Các Thầy, Cơ trong Khoa Cơng nghệ Thơng tin đã tạo điều kiện thuận lợi cho em trong suốt quá trình học tập và làm luận văn tốt nghiệp Em xin bày tỏ lịng biết ơn sâu sắc của mình đối với Cơ Nguyễn Thị Xuân Hƣơng, ngƣời đã tận tình hƣớng dẫn em thực hiện luận văn tốt nghiệp này. Cơ đã định hƣớng cho luận văn, đã giúp sinh viên cĩ một mơi trƣờng học thuật để cĩ thể trao đổi ý tƣởng, kiến thức đã thu thập đƣợc qua đọc sách, tạp chí, tài liệu, qua tìm hiểu các bài giảng, cũng nhƣ qua mạng Inernet, đặc biệt Cơ đã cho phép sinh viên đƣợc tiếp cận với kho tài liệu tƣơng đối đầy đủ, cĩ tính cập nhật cao mà cơ đã dày cơng sƣu tầm Em xin cảm ơn các Thầy, Cơ đã quan tâm gĩp ý và nhận xét quý báu cho bản đồ án của em. Xin cảm ơn các bạn đã chia sẻ và gĩp ý cho tơi trong quá trình hồn thành luận văn Hải Phịng, ngày tháng năm . Sinh viên Phạm Văn Sơn 3
5. MỞ ĐẦU Trong thời đại hiện nay, sự phát triển nhƣ vũ bão của cơng nghệ thơng tin (CNTT) đã kéo theo sự phát triển của nhiều lĩnh vực khác. Cĩ thể nĩi, CNTT đang làm thay đổi hình hài của nền kinh tế thế giới, giúp nhân loại bƣớc những bƣớc vững chắc đầu tiên trên con đƣờng của kinh tế tri thức, thƣơng mại điện tử Ngày nay, con ngƣời khơng cịn phải vất vả nhọc nhằn trong cơng việc thu thập dƣ liệu vì đã cĩ trợ thủ đắc lực là hệ thống máy tính và mạng truyền số liệu triển khai ở quy mơ tồn cầu. Tuy nhiên, sự phát triển vƣợt bậc của CNTT đã làm tăng số lƣợng giao dịch thơng tin trên mạng Internet một cách đáng kể, đặc biệt là thƣ điện tử, tin tức điện tử, Theo số liệu thống kê từ Brođer et ai (2008) thì cứ sau khoảng 6 đến 10 tháng lƣợng thơng tin đĩ lại tảng gấp đơi, bên cạnh đĩ tốc độ thay đổi thơng tin cũng cực kỳ nhanh. Hoạt động của các lĩnh vực cũng đặt ra phải xử lý một khối lƣợng thơng tin đồ sộ. Một yêu cầu lớn đặt ra đối với chứng ta là làm sao tổ chức, tìm kiếm thơng tin một cách hiệu quả nhất và phân loại thơng tin là một trong những giải pháp hợp lý cho yêu cầu này. Nhƣng vối một khối lƣợng thơng tin quá lớn và địi hỏi phải xử lý nhanh thì việc phân loại thủ cơng là điều khơng tƣởng. Hƣớng giải quyết là xây dựng các giải pháp cho phép thuật tốn hĩa và chƣơng trình hĩa trên máy tính để cĩ thể tự động phân loại các thơng tin trên. Trong đề tài tốt nghiệp đại học Trƣờng Đại Học Dân Lập Hải Phịng, em thực hiện đề tài “TÌM HIỂU VỀ SUPPORT VECTOR MACHINES CHO BÀI TỐN PHÂN LỚP QUAN ĐIỂM” . Lý do chọn đề tài Vấn đề phân lớp và dự đốn là khâu rất quan trọng trong học máy và trong khai phá dữ liệu, phát hiện trí thức. Kỹ thuật Support Vector Machines (SVM) đƣợc đánh giá là cơng cụ mạnh và tinh vi nhất hiện nay cho những bài tốn phân lớp phi tuyến. Nhiều những ứng dụng đã và đang đƣợc xây dựng dựa trên kỹ thuật SVM rất hiệu quả. 4
6. Mục đích, đối tượng và phạm vi nghiên cứu Trong khuơn khổ luận văn sẽ nghiên cứu phần bài tốn phân lớp quan điểm, cơ sở lý thuyết của phƣơng pháp SVM và các vấn đề liên quan. Phân tích những giải pháp cho phép mở rộng và cải tiến để nâng cao hiệu quả ứng dụng của SVM. Đƣa kỹ thuật mờ vào SVM cho phép phân chia khơng gian dữ liệu một cách tốt hơn, nhằm loại bỏ những vùng khơng đƣợc phân lớp bằng SVM thơng thƣờng. Trình bày hƣớng áp dụng kỹ thuật SVM cũng nhƣ những cải tiến, mở rộng của nĩ vào giải quyết một số các bài tốn ứng dụng trong thực tiễn. Trình bày tổng quan về bài tốn phân lớp quan điểm và cụ thể là bài tốn phân lớp phân cực để phân chia các tài liệu chứa quan điểm là tích cực hay tiêu cực. Tìm hiểu dữ liệu quan điểm và viết chƣơng trình thử nghiệm phân lớp phan cực tài liệu sử dụng SVM. Ý nghĩa khoa học và thực tiễn SVM là một phƣơng pháp phân lớp hiện đại và hiệu quả, nắm chắc phƣơng pháp này sẽ tạo nền tảng giúp chúng ta trong việc phát triển các giải pháp phân loại và dự đốn , xây dựng đƣợc những ứng dụng quan trọng trong thực tế. Ứng dụng phân lớp SVM cho bài tốn phân lớp quan điểm là bài tốn đã và đang đƣợc nghiên cứu và phát triển rộng rãi và cĩ ý nghĩa cả về học thuật lẫn ứng dụng thực tế. Nội dung cơ bản của luận văn bao gồm Chương 2: Tìm hiểu về Support Vector Machine Chương 2: Bài tốn phân lớp quan điểm Chương 3: Chương trình thực nghiệm Phần Kết Luận Phần tài liệu tham khảo 5
7. CHƢƠNG 1: TÌM HIỂU VỀ SUPPORT VECTOR MACHINE 1.1 PHÁT BIỂU BÀI TỐN Support Vector Machines (SVM) là kỹ thuật mới đối với việc phân lớp dữ liệu, là phƣơng pháp học sử dụng khơng gian giả thuyết các hàm tuyến tính trên khơng gian đặc trƣng nhiều chiều, dựa trên lý thuyết tối ƣu và lý thuyết thống kê. Trong kỹ thuật SVM khơng gian dữ liệu nhập ban đầu sẽ đƣợc ánh xạ vào khơng gian đặc trƣng và trong khơng gian đặc trƣng này mặt siêu phẳng phân chia tối ƣu sẽ đƣợc xác định. Ta cĩ tập S gồm e các mẫu học e S = {(x1,y1), (x2,y2), (x3,y3) ( xe,ye)} (X x Y) n với một vectơ đầu vào n chiều xi ∈ R thuộc lớp I hoặc lớp II (tƣơng ứng nhãn y i =1 đối với lớp I và y i =-1 đối với lớp II). Một tập mẫu học đƣợc gọi là tầm thƣờng nếu tất cả các nhãn là bằng nhau. Đối với các dữ liệu phân chia tuyển tính, chúng ta cĩ thể xác định đƣợc siêu phẳng f(x) mà nĩ cĩ thể chia tập dữ liệu. Khí đĩ, với mỗi siêu phẳng nhận đƣợc ta cĩ: f(x)≥ 0 nếu đầu vào x thuộc lớp dƣơng, và f(x)< 0 nếu x thuộc lớp âm n f(x) = w.x +b = wxii+ b j 1 yi f(xi) = yi (w.xi + b) ≥ 0 , i=1, .,l trong đĩ w là vector pháp tuyến n chiều và b là giá trị ngƣỡng Vector pháp tuyến w xác định chiều của siêu phẳng f(x), cịn giá trị ngƣỡng b xác định khoảng cách giữa siêu phẳng và gốc. . 6
8. Hình 2. 1: Phân tách theo siêu phẳng (w,b) trong khơng gian 2 chiều của tập mẫu Siêu phẳng cĩ khoảng cách với dữ liệu gần nhất là lớn nhất (tức cĩ biên lớn nhất) đƣợc gọi là siêu phẳng tối ƣu Hình 2. 2: Siêu phẳng tối ưu Mục đích đặt ra ở đây là tìm đƣợc một ngƣỡng (w,b) phân chia tập mẫu vào các lớp cĩ nhãn 1 (lớp I) và -1 (lớp II) nêu ở trên với khoảng cách là lớn nhất 7
9. 1.1.1 Trình bày tĩm tắt về phân lớp dữ liệu - Phân lớp dữ liệu là một kỹ thuật trong khai phá dữ liệu đƣợc sử dụng rộng rãi nhất và đƣợc nghiên cứu mở rộng hiện nay. - Mục đích: Để dự đốn những nhãn phân lớp cho các bộ dữ liệu hoặc mẫu mới. Đầu vào: Một tập các mẫu dữ liệu huấn luyện,với một nhãn phân lớp cho mỗi mẫu dữ liệu Đầu ra: Bộ phân lớp dựa trên tập huấn luyện,hoặc những nhãn phân lớp Phân lớp dữ liệu dựa trên tập huấn luyện và các giá trị trong một thuộc tính phân lớp và dùng nĩ để xác định lớp cho dữ liệu mới Kỹ thuật phân lớp dữ liệu đƣợc tiến hành bao gồm 2 bƣớc: Bước 1: Xây dựng mơ hình từ tập huấn luyện Bước 2: Sử dụng mơ hình – kiểm tra tính đúng đắn của mơ hình và dùng nĩ để phân lớp dữ liệu mới. Bước 1. Xây dựng mơ hình - Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc. - Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn lớp - Tập các bộ/mẫu dữ liệu huấn luyện - tập huấn luyện - đƣợc dùng để xây dựng mơ hình. - Mơ hình đƣợc biểu diễn bởi các luật phân lớp,các cây quyết định hoặc các cơng thức tốn học. Hình 2.3: Ví dụ xây dựng mơ hình 8
10. Bước 2: Sử dụng mơ hình - Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp - Đánh giá độ chính xác của mơ hình Lớp biết trƣớc của một mẫu/bộ dữ liệu đem kiểm tra đƣợc so sánh với kết quả thu đƣợc từ mơ hình. Tỉ lệ chính xác bằng phần trăm các mẫu/bộ dữ liệu đƣợc phân lớp đúng bởi mơ hình trong số các lần kiểm tra Hình 2.4: Sử dụng mơ hình 1.1.2 Tại sao lại sử dụng thuật tốn SVM trong phân lớp dữ liệu  SVM rất hiệu quả để giải quyết bài tốn dữ liệu cĩ số chiều lớn (ảnh của dữ liệu biểu diễn gene, protein, tế bào)  SVM giải quyết vấn đề overfitting rất tốt (dữ liệu cĩ nhiễu và tách dời nhĩm hoặc dữ liệu huấn luyện quá ít)  Là phƣơng pháp phân lớp nhanh  Cĩ hiệu suất tổng hợp tốt và hiệu suất tính tốn cao 9
11. 1.2 THUẬT TỐN SVM 1.2.1 Giới thiệu Bài tốn phân lớp (Classification) và dự đốn (Prediction) là hai bài tốn cơ bản và cĩ rất nhiều ứng dụng trong tất cả các lĩnh vực nhƣ: học máy, nhận dạng, trí tuệ nhân tạo, .v.v . Trong khĩa luận này, chúng em sẽ đi sâu nghiên cứu phƣơng pháp Support Vector Machines (SVM), một phƣơng pháp rất hiệu quả hiện nay. Phƣơng pháp SVM đƣợc coi là cơng cụ mạnh cho những bài tốn phân lớp phi tuyến tính đƣợc các tác giả Vapnik và Chervonenkis phát triển mạnh mẽ năm 1995. Phƣơng pháp này thực hiện phân lớp dựa trên nguyên lý Cực tiểu hĩa Rủi ro cĩ Cấu trúc SRM (Structural Risk Minimization), đƣợc xem là một trong các phƣơng pháp phân lớp giám sát khơng tham số tinh vi nhất cho đến nay. Các hàm cơng cụ đa dạng của SVM cho phép tạo khơng gian chuyên đổi để xây dựng mặt phẳng phân lớp 1.2.2 Định nghĩa Là phƣơng pháp dựa trên nền tảng của lý thuyết thống kê nên cĩ một nền tảng tốn học chặt chẽ để đảm bảo rằng kết quả tìm đƣợc là chính xác Là thuật tốn học giám sát (supervied learning) đƣợc sử dụng cho phân lớp dữ liệu. Là 1 phƣơng pháp thử nghiệm, đƣa ra 1 trong những phƣơng pháp mạnh và chính xác nhất trong số các thuật tốn nổi tiếng về phân lớp dữ liệu SVM là một phƣơng pháp cĩ tính tổng quát cao nên cĩ thể đƣợc áp dụng cho nhiều loại bài tốn nhận dạng và phân loại 1.2.3 Ý tƣởng của phƣơng pháp Cho trƣớc một tập huấn luyện, đƣợc biểu diễn trong khơng gian vector, trong đĩ mỗi tài liệu là một điểm, phƣơng pháp này tìm ra một siêu phẳng quyết định tốt nhất cĩ thể chia các điểm trên khơng gian này thành hai lớp riêng biệt tƣơng ứng là lớp + và lớp -. Chất lƣợng của siêu phẳng này đƣợc quyết định bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khi đĩ, khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt, đồng thời việc phân loại càng chính xác. 10
12. Mục đích của phƣơng pháp SVM là tìm đƣợc khoảng cách biên lớn nhất, điều này đƣợc minh họa nhƣ sau: Hình 2. 5: Siêu phẳng phân chia dữ liệu học thành 2 lớp + và - với khoảng cách biên lớn nhất. Các điểm gần nhất (điểm được khoanh trịn) là các Support Vector. 1.2.4 Nội dung phƣơng pháp 1.2.4.1 Cơ sở lý thuyết SVM thực chất là một bài tốn tối ƣu, mục tiêu của thuật tốn này là tìm đƣợc một khơng gian F và siêu phẳng quyết định f trên F sao cho sai số phân loại là thấp nhất. n Cho tập mẫu (x1, y1), (x2, y2), (xf, y f )} với xi ∈ R , thuộc vào hai lớp nhãn: yi ∈ {-1,1} là nhãn lớp tƣơng ứng của các xi (-1 biểu thị lớp I, 1 biểu thị lớp II). Ta cĩ, phƣơng trình siêu phẳng chứa vectơ xi trong khơng gian: xi .w + b = 0 +1, Xi . W + b > 0 Đặt f(Xi) = sign (Xi . W + b) = -1, Xi . W + b < 0 11
13. Nhƣ vậy, f(Xi) biểu diễn sự phân lớp của Xi vào hai lớp nhƣ đã nêu. Ta nĩi yi= +1 nếu Xi € lớp I và yi = -1 nếu Xi € lớp II . Khi đĩ, để cĩ siêu phẳng f ta sẽ phải giải bài tốn sau:  Tìm min w với W thỏa mãn điều kiện sau: yi(sin (Xi.W + b)) ≥ 1 với i € 1,n Bài tốn SVM cĩ thể giải bằng kỹ thuật sử dụng tốn tử Lagrange để biến đổi về thành dạng đẳng thức. Một đặc điểm thú vị của SVM là mặt phẳng quyết định chỉ phụ thuộc các Support Vector và nĩ cĩ khoảng cách đến mặt phẳng quyết định là 1/ . Cho dù các điểm khác bị xĩa đi thì thuật tốn vẫn cho kết quả giống nhƣ ban đầu. Đây chính là điểm nổi bật của phƣơng pháp SVM so với các phƣơng pháp khác vì tất cả các dữ liệu trong tập huấn luyện đều đƣợc đùng để tối ƣu hĩa kết quả. TĨM LẠI: trong trƣờng hợp nhị phân phân tách tuyến tính, việc phân lớp đƣợc thực hiện qua hàm quyết định f(x) = sign( + b), hàm này thu đƣợc bằng việc thay đổi vectơ chuẩn w, đây là vectơ để cực đại hĩa viền chức năng Việc mở rộng SVM để phân đa lớp hiện nay vẫn đang đƣợc đầu tƣ nghiên cứu. Cĩ một phƣơng pháp tiếp cận để giải quyết vấn để này là xây dựng và kết hợp nhiều bộ phân lớp nhị phân SVM (Chẳng hạn: trong quá trình luyện với SVM, bài tốn phân m lớp cĩ thể đƣợc biến đổi thành bài tốn phân 2*m lớp, khi đĩ trong mỗi hai lớp, hàm quyết định sẽ đƣợc xác định cho khả năng tổng quát hĩa tối đa). Trong phƣơng pháp này cĩ thể đề cập tới hai cách là một-đổi-một, một-đối-tất cả 1.2.4.2 Bài tốn phân 2 lớp với SVM Bài tốn đặt ra là: Xác định hàm phân lớp để phân lớp các mẫu trong tƣơng lai, nghĩa là với một mẫu dữ liệu mới xi thì cần phải xác định xi đƣợc phân vào lớp +1 hay lớp -1 Để xác định hàm phân lớp dựa trên phƣơng pháp SVM, ta sẽ tiến hành tìm hai siêu phẳng song song sao cho khoảng cách y giữa chúng là lớn nhất cĩ thể để phân tách hai lớp này ra làm hai phía. Hàm phân tách tƣơng ứng với phƣơng trình siêu phẳng nằm giữa hai siêu phẳng tìm đƣợc 12
14. Hình 2. 6: Minh họa bài tốn 2 phân lớp bằng phƣơng pháp SVM Các điểm mà nằm trên hai siêu phẳng phân tách được gọi là các Support Vector. Các điểm này sẽ quyết định đến hàm phân tách dữ liệu 1.2.4.3 Bài tốn nhiều phân lớp với SVM Để phân nhiều lớp thì kỹ thuật SVM nguyên thủy sẽ chia khơng gian dữ liệu thành 2 phần và quá trình này lặp lại nhiều lần. Khi đĩ hàm quyết định phân dữ liệu vào lớp thứ i của tập n , 2-Iớp sẽ là: i fi(x) = w ix + bi Những phần tử x là support vector sẽ thỏa điều kiện +1 nếu thuộc lớp i fi (x) = -1 nếu thuộc phần cịn lại Nhƣ vậy, bài tốn phân nhiều lớp sử dụng phƣơng pháp SVM hồn tồn cĩ thể thực hiện giống nhƣ bài tốn hai lớp. Bằng cách sử dụng chiến lƣợc "một- đối- một”(one - against - one). Giả sử bài tốn cần phân loại cĩ k lớp (k > 2), chiến lƣợc "một-đối-một”sẽ tiến hành k(k-l)/2 lần phân lớp nhị phân sử dụng phƣơng pháp SVM. Mỗi lớp sẽ tiến hành phân tách với k-1 lớp cịn lại để xác định k-1 hàm phân tách dựa vào bài tốn phân hai lớp bằng phƣơng pháp SVM. 13
15. 1.2.4.4 Các bước chính của phương pháp SVM Phƣơng pháp SVM yêu cầu dữ liệu đƣợc diễn tả nhƣ các vector của các số thực. Nhƣ vậy nếu đầu vào chƣa phải là số thì ta cần phải tìm cách chuyển chúng về dạng số của SVM Tiền xử lý dữ liệu: Thực hiện biến đổi dữ liệu phù hợp cho quá trình tính tốn, tránh các số quá lớn mơ tả các thuộc tính. Thƣờng nên co giãn (scaling) dữ liệu để chuyển về đoạn [-1, 1] hoặc [0, 1]. Chọn hàm hạt nhân: Lựa chọn hàm hạt nhân phù hợp tƣơng ứng cho từng bài tốn cụ thể để đạt đƣợc độ chính xác cao trong quá trình phân lớp. Thực hiện việc kiểm tra chéo để xác định các thám số cho ứng đụng. Điều này cũng quyết định đến tính chính xác của quá trình phân lớp. Sử dụng các tham số cho việc huấn luyện với tập mẫu. Trong quá trình huấn luyện sẽ sử dụng thuật tốn tối ƣu hĩa khoảng cách giữa các siêu phẳng trong quá trình phân lớp, xác định hàm phân lớp trong khơng gian đặc trƣng nhờ việc ánh xạ dữ liệu vào khơng gian đặc trƣng bằng cách mơ tả hạt nhân, giải quyết cho cả hai trƣờng hợp dữ liệu là phân tách và khơng phân tách tuyến tính trong khơng gian đặc trƣng. Kiểm thử tập dữ liệu Test 14
16. 2 CHƢƠNG 2: BÀI TỐN PHÂN LỚP QUAN ĐIỂM 2.1 SỰ KIỆN (Facts) VÀ QUAN ĐIỂM (Opinions) ả : Sự kiện là những biểu hiện khách quan về ực thể, các sự kiện và các thuộc tính của họ VD: “ ” ểu hiện chủ quan mơ tả tình cảm, đánh giá hay cảm xúc của con ngƣời đối với các thực thể, sự kiệ ủ . VD: “ ơ tơ , và dễ sử dụng” 2.2 NHU CẦU VỀ THƠNG TIN QUAN ĐIỂM VÀ NHẬN XÉT “Những gì ngƣời khác nghĩ” đã luơn luơn là một phần quan trọ c ới thiệu một thợ cơ khí tự động hoặc yêu cầu tài liệu tham khảo thƣ liên quan đến xin việc từ các đồng nghiệp, hoặc tƣ vấ ủa những ngƣờ , khơn ộng lớn. Và ngƣợc lạ Internet. Theo nhƣ hai cuộc khảo sát của hơn 2000 ngƣời Mỹ trƣởng thành mỗi: 81% ngƣời dùng Internet (hoặc 60% ngƣời Mỹ) đã thực hiệ ực tuyến về một sản phẩm ít nhất một lần 20% (15% của tất cả các ngƣời Mỹ) làm nhƣ vậy trong một ngày. Trong số các độc giả đánh giá trực tuyến của nhà hàng, khách sạn, dịch vụ khác nhau (ví dụ nhƣ, các cơ quan du lịch hoặc bác sĩ), giữa 73% và 87% báo cáo đánh giá đã cĩ một ảnh hƣởng đáng kể mua hàng của họ. Ngƣời tiêu dùng sẵn sàng trả từ 20% đến 99% một mụ 5 sao cao hơn so với 15
17. một mục đánh giá 4 sao. 32% đã cung cấp một đánh giá về một sản phẩm, dịch vụ thơng qua một hệ thống xếp hạng trực tuyến, trong đĩ cĩ 18% của cơng dân trực tuyến cao cấp, cĩ đăng một bình luận trực tuyến hoặc xem xét về một sản phẩm hay dịch vụ. hàng hĩa và dịch vụ khơng phải là động cơ duy nhất hoặc thể hiệ trực tuyế . Ví dụ, trong một cuộc khảo sát hơn 2500 ngƣời Mỹ trƣởng thành, Rainie và Horrigan nghiên cứu 31% ngƣời Mỹ - trên 60 triệu ngƣời - 2006 ngƣờ , là những ngƣời thu thập thơng tin về cuộc bầu cử năm 2006 trực tuyến và trao đổ thơng qua email. Trong số này: 28% nĩi rằng cho các hoạt động trực tuyế để ợc quan điểm từ bên trong cộng đồng của họ, và 34% cho biết một lý do chính là để ợc quan điểm từ bên ngồi cộng đồng của họ. 27% ực tuyến cho hoặc xếp hạng của ; 28% cho biết rằng hầu hết các trang web mà họ sử dụng chia sẻ quan điểm, nhƣng 29% nĩi rằng các trang web thách thức quan điểm của họ, chỉ ra rằng nhiều ngƣời khơng chỉ đơn giản là tìm kiếm xác nhận 8% đăng trực tuyến bình luận chính trị riêng của họ. . Theo Horrigan rằng trong khi đa số ngƣời sử dụng internet của Mỹ kinh nghiệm tích cực trong trực tuyến, 58% cho rằng thơng tin trực tuyến , khĩ hiểu . Vì vậ . 16
18. ự quan tâm mà ngƣời dùng cá nhân trong các ý kiến trực tuyến về sản phẩm và dịch vụ, ảnh hƣở . Với sự bùng nổ của nền tảng Web 2.0 , diễn đàn thảo luận, peer- to-peer mạng, và các loại khác nhau củ chƣa từng cĩ và quyền chia sẻ kinh nghiệm và ý kiến của riêng họ ực hay tiêu cực. Khi các cơng ty lớn đang ngày càng nhận ra, những tiếng nĩi của ngƣời tiêu dùng cĩ thể vận dụng rất lớn ảnh hƣởng trong việc hình thành ý kiến của ngƣời tiêu dùng trung thành v thƣơng hiệu của họ, quyết định mua,và vận động cho chính thƣơng hiệu của họ Cơng ty cĩ thể đáp ứng với nhữ ời tiêu dùng mà họ tạo ra thơng qua ện truyền thơng xã hội và phân tích . Tuy nhiên, các nhà phân tích ngành cơng nghiệp lƣu ý rằng việc tận dụng các phƣơng tiện truyền thơng mới cho mục đích hình ảnh sản phẩm địi hỏi c cơng nghệ mới. Các nhà tiếp thị luơn luơn cần giám sát các phƣơng tiện truyền thơng cho thơng tin liên quan đến thƣơng hiệu của mình, cho dù đĩ là đối với các hoạt động quan hệ cơng chúng, vi phạm gian lận, hoặc tình báo cạnh tranh. Nhƣng phân mảnh các phƣơng tiện truyề thay đổi hành vi của ngƣời tiêu dùng đã truyền thống. Technorati ƣớc tính rằng 75.000 blog mới đƣợc tạo ra mỗi ngày, cùng với 1,2 triệu bài viết mỗi ngày ều ý kiến ngƣời tiêu dùng thảo luận về sản phẩm và dịch vụ. Vì vậ cá nhân hệ thống cĩ khả năng tự động phân tích của ngƣời tiêu dùng 2.3 MÁY TÌM KIỂM QUAN ĐIỂM / NHẬN XÉT Tạo hệ thống cĩ thể xử lý thơng tin chủ quan một cách hiệu quả địi hỏi phải khắc phục một số thách thứ ột ứng dụng sẽ điền vào thơng tin quan trọng và phổ biến cần thiế ạn chế sự chú ý vào blog tìm kiếm hoặc xem xét các loại tổng quát hơn của tìm kiếm đã đƣợc mơ tả ở trên. 17
19. Sự phát triển củ ế ến hồn chỉnh cĩ thể liên quan đến việc tấn cơng lẫn nhau trong những vấn đề sau đây. Khi ứng dụng đƣợc tích hợp vào mộ ếm, sau đĩ cần phải xác đị ờ . Điều này cĩ thể khơng là một vấn đề : “review” “reviews” “opinion” , hoặc ứng dụ ấp một ời dùng để họ cĩ thể Bên cạ ấn đề vẫn cịn mở ịnh những tài liệu tại chỗ liên quan đến một truy vấn định hƣớ ột thách thức trong việc thiết lậ ồng thời hoặ ần của tài liệu chứa tài liệ . Khi đã cĩ các tài liệ c tiêu, ngƣời ta vẫn cịn phải đối mặt với vấn đề xác đị ổng thể /hoặc ý kiến cụ thể ệt hoặc các khía cạnh củ hoặc các chủ đề trong câu hỏi, khi cần thiết. Cuối cùng, hệ thống cần phả ợc trong một số trang tĩm tắt hợp lý. 2.4 LỊCH SỬ CỦA PHÂN TÍCH QUAN ĐIỂM VÀ KHAI THÁC QUAN ĐIỂM (sentiment analysis (opinion mining) gần đây đã thu hút đƣợc sự quan tâm rộ ấ ộng nhận thức về các vấn đề nghiên cứu và cơ hộ . 18
20. :  Sự gia tăng của các phƣơng pháp học máy, xử lý ngơn ngữ tự nhiên và khơi phục thơng tin.  Sự sẵn cĩ củ ữ liệ ật tốn họ ủa Internet, cụ thể ự phát triể . Thực hiện những thách thức trí tuệ, thƣơng mại và các ứng dụ . ử lý một tập hợp các kết quả tìm kiếm cho mộ ất định, sinh ra một danh sách các thuộc tính sản phẩm (chất lƣợ ổng hợ ). “ ” ụm từ song song của " ”ở những khía cạnh nhất định (Das và Chen Tong, 2001). ”và ”biểu thị cùng một lĩnh vực nghiên cứu 2.5 XU HƢỚNG NGHIÊN CỨU GẦN ĐÂY ểm đã trở thành chủ đề nĩng giữa các nhà nghiên cứu xử lý ngơn ngữ tự nhiên và trích chọ ều các bài báo đƣợc xuất bản và những ứng dụng khác nhau cĩ sử dụng hệ thống đánh giá quan điểm đƣợc phát triển và đƣa vào trong hoạt động thƣơng mạ :  ừ, cụm từ chỉ quan điểm  Xác định quan điể . 2.5.1 Xác định cụm từ, quan điểm Những từ, cụm từ chỉ quan điểm là những từ ngữ đƣợc sử dụng để diễn tả cảm xúc, ý kiến ngƣời viết, những quan điểm chủ quan đĩ dựa trên những vấn đề mà anh ta hay cơ ta đang tranh luận. Việc rút ra những từ, cụm từ chỉ quan điểm là giai đoạn đầu tiên trong hệ thống đánh giá quan điểm, vì những từ, cụm từ này là những chìa khĩa cho cơng việc nhận biết và phân loại tài liệu sau đĩ. 19
21. Ứng dụng dựa trên hệ thống đánh giá quan điểm hiện nay tập trung vào các từ chỉ nội dung câu: danh từ, động từ, tính từ và phĩ từ. Phần lớn cơng việc sử dụng từ loại để rút chúng ra (Hu và Liu, 2004 , Turney, 2002). Việc gán nhãn từ loại cũng đƣợc sử dụng trong cơng việc này, điều này cĩ thể giúp cho việc nhận biết xu hƣớng quan điểm trong giai đoạn tiếp theo. Những kĩ thuật phân tích ngơn ngữ tự nhiên khác nhƣ xĩa: stopwords, stemming cũng đƣợc sử dụng trong giai đoạn tiền xử lý để rút ra từ, cụm từ chỉ quan điểm 2.5.2 Sử dụng tính từ và phĩ từ Những hệ thống hiện tại dùng để nhận biết những từ chỉ quan điểm hay xu hƣớng quan điểm tập trung chủ yếu vào các tính từ và phĩ từ vì chúng đƣợc xem là sự biểu lộ rõ ràng nhất của tính chủ quan ( Hatzivassiloglou and McKeown, 1997, Wiebe and Bruce, 1999 ). Hu và Liu (2004) áp dụng việc gán nhãn từ loại và kĩ thuật xử lý ngơn ngữ tự nhiên nhằm rút ra những tính từ cũng nhƣ những từ chỉ quan điể : . Định nghĩa một câu mà chứa một hay nhiều dấu hiệu sản phẩm và từ chỉ quan điểm đƣợc xem là một câu chỉ quan điểm. . ỗi câu trong dữ liệu chỉ quan điểm, rút ra tất cả những tính từ đƣợc coi là những từ chỉ quan điểm. . Kết quả thực nghiệm việc rút ra những câu đánh giá quan điểm cĩ độ chính xác (precision) khoảng 64.2% và recall là 69.3%. . Sử dụng WordNet (Fellbaum, 1998) để xác định các tính từ đƣợc rút ra mang chiều hƣớng tích cực (positive) hay tiêu cực (negative). Trong WordNet, các tính từ đƣợc tổ chức thành các cụm từ lƣỡng cực, nửa cụm thứ hai phần đầu là từ trái nghĩa của cụm thứ nhất. Mỗi nửa cụm là phần đầu của tập từ đồng nghĩa chính, tiếp theo là tập từ đồng nghĩa kèm theo, đại diện cho ngữ nghĩa tƣơng tự nhƣ những tính từ quan trọng. Ngƣợc với cách tiếp cận dựa trên từ điển, họ sử dụng định hƣớng quan điểm của những từ đồng nghĩa và từ trái nghĩa để dự đốn định hƣớng của các tính từ. Họ bắt đầu với một danh sách khởi đầu gồm 30 tính từ thơng dụng đƣợc chọn thủ cơng (bằng tay). Sau đĩ sử dụng WordNet để 20
22. dự đốn định hƣớng của tất cả các tính từ trong danh sách từ quan điểm đƣợc rút ra bằng cách tìm kiếm qua cụm lƣỡng cực để tìm ra liệu các từ đồng nghĩa hay trái nghĩa cĩ trong danh sách khởi đầu hay khơng. Khi định hƣớng của tính từ đƣợc dự đốn, nĩ sẽ đƣợc bổ sung vào danh sách khởi đầu và cĩ thể đƣợc sử dụng để xác định định hƣớng của các tính từ khác. Trong phƣơng pháp này, danh sách khởi đầu sẽ dần tăng lên khi sự định hƣớng của các tính từ đƣợc nhận dạng, và khi nĩ ngừng gia tăng, tức qui mơ của danh sách khởi đầu trùng với qui mơ của danh sách từ chỉ quan điểm, thì tất cả định hƣớng của các tính từ đã đƣợc nhận biết và quá trình này kết thúc. Những từ quan điểm thƣờng tập trung chủ yế ạ ừ và phĩ từ vì vậy càng nhận dạng chính xác đƣợc nhiều hai loại từ này hệ thống càng cĩ độ chính xác cao 2.5.3 Sử dụng các động từ Các tính từ và phĩ từ đĩng một vai trị quan trọng trong việc phân tích quan điểm và là các loại từ cĩ lợi thế trong việc nhận biết định hƣớng và rút ra các từ chỉ quan điểm trong các nghiên cứu hiện nay. Tuy nhiên, các loại từ khác, ví dụ nhƣ động từ cũng đƣợc sử dụng để diễn tả cảm xúc hay ý kiến trong các bài viết. Nasukawa và Yi (2003) xem xét rằng bên cạnh các tính từ và phĩ từ, thì các động từ cũng cĩ thể diễn tả quan điểm trong hệ thống đánh giá quan điểm của họ. Họ phân loại các động từ cĩ liên quan đến quan điểm thành 2 loại. Loại thứ nhất trực tiếp thể hiện quan điểm tích cực hay tiêu cực, theo lý giải của họ thì “beat” trong “X beats Y” . Loại thứ hai khơng thể hiện quan điểm trực tiếp nhƣng dẫn đến những quan điểm , giống nhƣ “is” trong “X is good” . Họ sử dụ ựa trên mơ hình Markov (HMM) (Manning and Schutze, 1999) và phân tích cú pháp nơng dựa trên luật (Neff et al., 2003) cho bƣớc tiền xử lý. Sau đĩ họ phân tích tính phụ thuộc về mặt cú pháp giữa các cụm từ và tìm kiếm các cụm từ cĩ một từ chỉ quan điểm mà nĩ bổ nghĩa hoặc đƣợc bổ nghĩa bởi một thuật ngữ chủ thể 21
23. 2.5.4 Xác định chiều hƣớng, cụm từ, quan điểm Trong phân tích quan điểm, xu hƣớng của những từ, cụm từ trực tiếp thể hiện quan điểm, cảm xúc của ngƣời viết bài. Phƣơng pháp chính để nhận biết xu hƣớng quan điểm của những từ, cụm từ chỉ cảm nghĩ là dựa trên thống kê hoặc dựa trên từ vựng 2.6 NHIỆM VỤ CỦA PHÂN TÍCH QUAN ĐIỂM Phân tích quan điể nhiên. Cĩ hai hƣớ : (Sentiment Classification (Sentiment Extraction) : bao gồm 3 nhiệm vụ chính là: - . - positive, negative ) - 2.7 BÀI TỐN PHÂN LỚP QUAN ĐIỂM Phân lớp là quá trình "nhĩm” các đối tƣợng "giống” nhau vào "một lớp” dựa trên các đặc trƣng dữ liệu của chúng. Tuy nhiên, phân lớp là một hoạt động tiềm ẩn trong tƣ duy con ngƣời khi nhận dạng thế giới thực, đĩng vai trị quan trọng làm cơ sở đƣa ra các dự báo, các quyết định. Phân lớp và cách mơ tả các lớp giúp cho tri thức đƣợc định dạng và lƣu trữ trong đĩ Khi nghiên cứu một đối tƣợng, hiện tƣợng, chúng ta chỉ cĩ thể dựa vào một số hữu hạn các đặc trƣng của chúng. Nĩi cách khác, ta chỉ xem xét biểu diễn của đối tƣợng, hiện tƣợng trong một khơng gian hữu hạn chiều, mỗi chiểu ứng với một đặc trƣng đƣợc lựa chọn. Khi đĩ, phân lớp dữ liệu trở thành phân hoạch tập dữ liệu thành các tập con theo một tiêu chuẩn nhận dạng đƣợc. Nhiệm vụ : - - . 22
24. Phân lớp câu/tài liệu chứa quan điể ực(positive) hay tiêu cực (negative (neutral). Theo Bo Pang và Lillian Lee (2002) phân lớp câu/tài liệu chỉ quan điểm khơng cĩ sự nhận biết của mỗi từ/ cụm từ chỉ quan điểm. Họ sử dụng học máy cĩ giám sát để phân loại những nhận xét về phim ảnh. Khơng cần phải phân lớp các từ hay cụm từ chỉ quan điểm, họ rút ra những đặc điểm khác nhau của các quan điểm và sử dụng thuật tốn Nạve Bayes (NB), Maximum Entropy (ME) và Support Vector Machine (SVM) để phân lớp quan điểm. Phƣơng pháp này đạt độ chính xác từ 78, 7% đến 82, 9%. Input: . Output: (polarity) về tiếp cận ngữ ). Phân lớp tài liệu theo hƣớng quan điểm thật sự là vấn đề thách thức và khĩ khăn trong lĩnh vự xử lý ngơn ngữ đĩ chính là bản chất phức tạp của ngơn ngữ của con ngƣời, đặc biệt là sự đa nghĩa và nhập nhằng nghĩa của ngơn ngữ. Sự nhập nhằng này rõ ràng sẽ ảnh hƣởng đến độ chính xác bộ phân lớp của chúng ta một mức độ nhất định. Một khía cạnh thách thức của vấn đề này dƣờng nhƣ là phân biệt nĩ với việc phân loại chủ đề theo truyền thống đĩ là trong khi những chủ đề này đƣợc nhận dạng bởi những từ khĩa đứng một mình, quan điểm cĩ thể diễn tả một cách tinh tế hơn. Ví dụ câu sau: “Làm thế nào để ai đĩ cĩ thể ngồi xem hết bộ phim này ?”khơng chứa ý cĩ nghĩa duy nhất mà rõ ràng là nghĩa tiêu cực. Theo đĩ, quan điểm dƣờng nhƣ địi hỏi sự hiểu biết nhiều hơn, tinh tế hơn 2.7.1 Phân cực quan điểm và mức độ phân cực - : positive/negative/neutral - : Like/ dislike/ So so - p/ thumbs down - :like to win/ unlike to win Liberal/conservative - / bad new. 23
25. : / . : “This laptop is great”. ” => . VD: “The stock prise rose” ” ” Rating inference (ordinal regression : 5 sao. , : positive, negative, neutral positive negative. neutral ). Theo neutral negative negative 10%. 2.7.2 Nhiệm vụ của bài tốn phân lớp quan điểm Bài tốn phân lớp quan điểm đƣợc biết đến nhƣ là bài tốn phân lớp tài liệu với mục tiêu là phân loại các tài liệu theo định hƣớng quan điểm. Đã cĩ rất nhiều tiếp cận khác nhau đƣợc nghiên cứu để giải quyết cho loại bài tốn này. Để thực hiện, về cơ bản cĩ thể chia thành hai nhiệm vụ chính nhƣ sau: - Trích các đặc trưng nhằm khai thác các thơng tin chỉ quan điểm để phục vụ mục đích phân loại tài liệu theo định hướng ngữ nghĩa. - Xây dựng mơ hình để phân lớp các tài liệu. 24
26. 2.7.3 Xây dựng mơ hình phân lớp để phân loại tài liệu Trong phân tích quan điểm, xu hƣớng của những từ, cụm từ trực tiếp thể hiện quan điểm, cảm xúc của ngƣời viết bài. Phƣơng pháp chính để nhận biết xu hƣớng quan điểm của những từ, cụm từ chỉ cảm nghĩ là dựa trên thống kê hoặc dựa trên từ vựng. Với nhiệm vụ phân lớp các tài liệu, đã cĩ rất nhiều các phƣơng pháp học máy thống kê đƣợc sử dụng cho mục đích này, nhƣ là: Naive Bayes, phân loại Maximum Entropy, học máy giám sát SVM, cây quyết định, Thuật tốn gồm 4 bước: Bước 1: Xác định các n-gram, các đặc trưng được lọc qua tồn bộ tập dữ liệu. Bước 2: Tính tốn tần số xuất hiện của các n-gram tích cực, tiêu cực và tính trọng số của các n-gram. Bước 3: Chọn n-gram thỏa mãn ngưỡng và cĩ trọng số cao cũng như loại bỏ các bigram khơng cĩ ý nghĩa cho việc phân loại. Bước 4: Tính tốn độ chính xác của quá trình huấn luyện của bộ phân lớp 25
27. 3 CHƢƠNG III: CHƢƠNG TRÌNH THỰC NGHIỆM 3.1 DỮ LIỆU THỬ NGHIỆM Trong đồ án này, chúng tơi sử dụng dữ liệu từ những bài viết về đánh giá bộ phim gồm 700 nhận xét tích cực và 700 nhận xét tiêu cực. Dữ liệu này đƣợc cung cấp bởi tác giả Lillian Lee ( review-data/) Các dữ liệu này đã dƣợc loại bỏ các chỉ số đánh giá và rút ra thơng tin trong nguyên văn từ các tài liệu gốc định dạng HTML, xử lý các dấu chấm câu nhƣ các mục của từ vựng riêng biệt. Chúng tơi tập trung vào những đặc trƣng dựa trên những từ đơn và cặp 2 từ . 3.2 CƠNG CỤ SỬ DỤNG 3.2.1 Cơng cụ sinh SRIML SRILM là bộ cơng cụ để xây dựng và áp dụng các mơ hình ngơn ngữ thống kê , chủ yếu là để sử dụng trong nhận dạng tiếng nĩi, gắn thẻ thống kê và phân khúc, và dịch máy thống kê. Bộ cơng cụ này đƣợc phát triển bởi “Phịng thí nghiệm và nghiên cứu cơng nghệ giọng nĩi SRI” từ năm 1995, cĩ thể chạy trên nền tảng Linux cũng nhƣ Windows. SRILM bao gồm các thành phần sau: Một tập hợp các thƣ viện C++ giúp cài đặt mơ hình ngơn ngữ, hỗ trợ cấu trúc dữ liệu và các chức năng tiện ích nhỏ. Một tập hợp các chƣơng trình thực thi thực hiện nhiệm vụ xây dựng mơ hình ngơn ngữ, đào tạo và thử nghiệm mơ hình ngơn ngữ trên dữ liệu, gắn thẻ hoặc phân chia văn bản, Bộ cơng cụ SRILM cĩ rất nhiều chƣơng trình con, để xây dựng mơ hình ngơn ngữ ta sử dụng chƣơng trình Ngram 26
28. Chƣơng trình Ngram thống kê tần số xuất hiện của các cụm Ngram. Kết quả của việc thống kê đƣợc ghi lại vào một tệp hoặc sử dụng chúng để xây dựng mơ hình ngơn ngữ. Kết quả của việc thống kê đƣợc ghi lại theo định dạng sau: ngram –count –ordern -interpolate -text -lm Trong đĩ: order n: thiết lập độ dài lớn nhất của các cụm Ngram sẽ thống kê bằng n. Giá trị mặc định nếu khơng thiết lập tham số này là n = 3 interpolaten: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tính tốn tần số của các cụm Ngram cĩ độ dài là n bằng cách nội suy từ các cụm Ngram cĩ độ dài nhỏ hơn. text : File dữ liệu cần thống kê tần số các cụm Ngram. Tệp văn bản này cĩ thể chứa mỗi câu trên một dịng. Kí hiệu kết thúc và bắt đầu dịng mới sẽ đƣợc tự động thêm vào nếu trong tệp đầu vào chƣa cĩ. Các dịng trống trong tệp này cũng bị loại bỏ. lm : xây dựng mơ hình ngơn ngữ truy hồi từ các tần số vừa thống kê, sau đĩ ghi lại vào tệp fileketqua theo định dạng ở trên. 3.2.2 Ngơn ngữ lập trình java Java là một ngơn ngữ lập trình dạng lập trình hƣớng đối tƣợng (OOP). Khác với phần lớn ngơn ngữ lập trình thơng thƣờng, thay vì biên dịch mã nguồn thành mã máy hoặc thơng dịch mã nguồn khi chạy, Java đƣợc thiết kế để biên dịch mã nguồn thành bytecode, bytecode sau đĩ sẽ đƣợc mơi trƣờng thực thi (runtime environment) chạy. Bằng cách này, Java thƣờng chạy nhanh hơn những ngơn ngữ lập trình thơng dịch khác nhƣ Python, Perl, PHP, Cú pháp Java đƣợc vay mƣợn nhiều từ C & C++ nhƣng cĩ cú pháp hƣớng đối tƣợng đơn giản hơn và ít tính năng xử lý cấp thấp hơn. 27
29. Một số đặc điểm nổi bật của java - Máy ảo java - Thơng dịch - Độc lập nền - Hƣớng đối tƣợng Đa nhiệm, đa luồng 3.2.3 Cơng cụ phân lớp dữ liệu SVMLight SVM- đƣợc phát triển bởi Joachims Thorste nh sau: Các tính năng chính của chƣơng trình - Tối ƣu hĩa thuật tốn nhanh - Giải quyết nhanh các vấn đề phân loại và hồi quy đối với các kết quả đầu ra đa biến - Hỗ trợ các phƣơng pháp nhận dạng mẫu SVM-light bao gồm các thành phần chính: - SVMTlearn - SVMTagger - SVMTeval . - SVMClassicfy: kiểm thử kết quả Thực hiện: : svm-learn [-option] train_file model_file 28
30. : train_file . - Tên train_file . - . model_file: . . - . - ủ ố . - ). 3.3 Kết quả thực nghiệm Các bƣớc thực hiện Bước 1: sử dụng cơng cụ N-gram để sinh ra các file dữ liệu chứa các N-gram của tài liệu chứa quan điểm. Ở đây, chúng tơi sử dụng uni-gram (1-gram) và Bi- gram (2-gram). Bước 2: Từ tập dữ liệu này, trƣớc khi đƣợc sử dụng để huấn luyện và kiểm thử cần qua một số bƣớc lọc bỏ các đặc trƣng khơng tốt. Bƣớc thứ nhất, lọc bỏ các từ vơ nghĩa (stop word), và các ký tự đặc biệt nhƣ {! , ? , / , @ . # , “, } Bƣớc tiếp theo là lọc bỏ các đặc trƣng theo tần số. Những đặc trƣng cĩ tần số xuất hiện trong dữ liệu huấn luyện thấp hơn một giá trị nào đĩ (đối với unigram sẽ là nhỏ hơn 3 và bigram là nhỏ hơn 7) sẽ bị loại bỏ. Bƣớc cuối cùng đƣợc thực hiện sau khi đã gán các trọng số cho từng đặc trƣng. 29
31. Bước 3: Gán nhãn cho mỗi N-gram trong tập dữ liệu huấn luyện để lấy thơng tin phân loại: các nhận xét chứa quan điểm tích cực đƣợc gán nhãn 1, các nhận xét chứa quan điểm tiêu cực đƣợc gán nhãn -1. chọn Để thực hiện phân lớp tài liệu quan điểm, chúng tơi chia tập dữ liệu thành hai tập con là tập huấn luyện (train) và tập kiểm thử (test) Tập huấn luyện gồm cĩ 550 nhận xét tích cực và 550 nhận xét tiêu cực. Tập kiểm thử (test) gồm cĩ 150 nhận xét tích cực và 150 nhận xét tiêu cực. Kết quả thực hiện phân lớp Support Vector Machine với các đặc trƣng Uni- gram và Bigram nhƣ sau: Đặc trƣng Uni-gram Bi-gram Độ chính xác (Precision) 91,38 % 56,49% Độ phản hồi (Recall) 91,54% 58% Chƣơng trình trích đặc trƣng n-gram và tạo dữ liệu cho phân lớp SVM để phân lớp các bình luận là tích cực hay tiêu cực. 30
32. 3. 1: Giao diện chính của chƣơng trình 3.2: Mở file dữ liệu đầu vào 31
33. 3.3: Hiển thị dữ liệu dùng để chạy Get Pos Data 3.4: Dữ liệu cho phân lớp SVM 32
34. 3.5: Hình ảnh khi chạy Lệnh SVM trong mơi trƣờng DOS 33
35. 4 KẾT LUẬN Luận văn hƣớng tới mục tiêu phân lớp dữ liệu đạt độ chính xác cao, tuy đã xem xét đƣợc tất cả các mục tiêu nhƣ trong phần giới thiệu nhƣng do thời gian cĩ hạn, nên một số vấn đề vẫn chƣa hồn chỉnh. Tuy nhiên, luận văn cũng đạt đƣợc một số kết quả: . Nghiên cứu và trình bày cơ sở của lý thuyết của phƣơng pháp học máy. Trình bày phƣơng pháp SVM. Đây là một phƣơng pháp phân lớp hiệu quả đƣợc nghiên cứu nhiều nhất trong thời gian qua. Phân tích những giải pháp cho phép mở rộng và cải tiến để nâng cao hiệu quả ứng dụng của SVM: Cài đặt đƣợc một số cơng cụ giúp đỡ cho việc xây dựng mơ hình ngơn ngữ nhƣ: chuẩn hĩa văn bản, tách từ bằng ngơn ngữ Java. Cài đặt đƣợc chƣơng trình để trích đặc trƣng và tạo dữ liệu cho phân lớp SVM. Tìm kiếm và sử dụng bộ dữ liệu phân lớp tài liệu chứa quan điểm. Cài đặt và chạy thành cơng bộ mã nguồn mở Srilm trên mơi trƣờng Linux Sử dụng bộ cơng cụ mã nguồn mở SRILM để xây dựng mơ hình ngơn ngữ cho dữ liệu đầu vào. Do thời gian cĩ hạn, nên hiện tại luận văn mới chỉ nghiên cứu đƣợc trích đặc trƣng n-gram từ các bình luận và sử dụng phân lớp SVM để phân lớp các bình luận là tích cực hay tiêu cực. Trong thời gian tới, tơi sẽ tiếp tục nghiên cứu trích các đặc trƣng khác cho bài tốn này và các phƣơng pháp phân lớp thống kê khác. 34
36. 5 TÀI LIỆU THAM KHẢO 1. Ths. Nguyễn Thị Xuân Hƣơng và Ths. Lê Thụy về “phân tích quan điểm và một số hƣớng tiếp cận” . Hội nghị khoa học lần thứ nhất, 2012, trƣờng ĐHDL Hải Phịng 2. Nghiên cứu thuật tốn phân lớp nhị phân và ứng dụng cho bào tốn Protein Folding – Nguyễn Quang Phƣớc – Trƣờng Đại học Khoa học tự nhiên TPHCM 3. Bo Pang and Lillian Lee và Shivakumar Vaithyanathan. Thumbs up Sentiment Classification using Machine Learning Techniques. 4. 5. 6. 7. 8. 35