TRƢỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN  BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI LIỆU TIẾNG VIỆT TRẦN THỊ THU THẢO VŨ THỊ CHINH BIÊN HÒA, THÁNG 11/2012 TRƢỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN  ĐỀ TÀI: XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI LIỆU TIẾNG VIỆT SVTH: TRẦN THỊ THU THẢO VŨ THỊ CHINH GVHD:ThS. TẠ NGUYỄN BIÊN HÒA, THÁNG 11/2012 LỜI NÓI ĐẦU Trong những năm gần đây, với sự phát triển mạnh mẽ của công nghệ thông tin và nhu cầu sử dụng Internet của con ngƣời đã làm tăng vọt lƣợng thông tin giao dịch trên Internet. Vì vậy mà số lƣợng văn bản điện tử tăng nhanh chóng mặt về số lƣợng và chủ đề đặc biệt là thƣ viện điện tử, tin tức điện tử trên mạng toàn cầu…. Với lƣợng thông tin đồ sộ nhƣ vậy, một yêu cầu lớn đặt ra là làm sao tổ chức và tìm kiếm thông tin một cách chính xác, có hiệu quả nhất. 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 trên. Nhƣng một thực tế cho thấy là khối lƣợng thông tin quá lớn, việc phân loại dữ liệu thủ công là điều vô cùng khó khăn. Hƣớng giải quyết cho việc này là xây dựng một chƣơng trình phân loại thông tin tự động bằng máy tính. Phân loại văn bản là một vấn đề quan trọng trong lĩnh vực xử lý ngôn ngữ. Nhiệm vụ của bài toán này là gán các tài liệu văn bản vào nhóm các chủ đề cho trƣớc. Đây là một bài toán rất thƣờng gặp trong thực tế điển hình nhƣ việc phân nhóm tin tức, phân nhóm các văn bản theo từng thể loại khác nhau. Tuy nhiên, chúng ta không thể cùng lúc đọc tất cả các tin tức, bài viết, bài báo hay các tài liệu để rồi phân loại chúng theo đúng mục đích của mình bởi vì số tài liệu lớn, nếu để đọc hết đƣợc tất cả thì sẽ mất rất nhiều thời gian. Đó là lý do cần có một hệ thống phân loại tài liệu tiếng Việt. Chúng em đã chọn thực hiện đề tài “Xây dựng hệ thống phân loại tài liệu tiếng Việt” nhằm tìm hiểu và thử nghiệm các phƣơng pháp phân loại văn bản áp dụng trên tiếng Việt. Trong luận văn này, chúng em cũng tìm hiểu một số cách phân loại tài liệu và thử nghiệm một phƣơng pháp phân loại áp dụng thuật toán Naïve Bayes để xây dựng chƣơng trình dựa trên tập dữ liệu huấn luyện từ đó hƣớng đến việc phân loại các bài báo khoa học trong lĩnh vực Công nghệ thông tin nhằm tiết kiệm thời gian và công sức cho các nhà tổ chức trong các hội thảo chuyên đề. Việc thực hiện đề tài phân loại tài liệu tiếng Việt của chúng em hy vọng sẽ đem đến một cách phân loại mới, nhanh chóng và hiệu quả hơn việc phân loại bằng thủ công nhƣ hiện nay. LỜI CẢM ƠN Chúng em xin bày tỏ lòng biết ơn sâu sắc nhất tới Thầy Tạ Nguyễn đã tận tụy hƣớng dẫn, động viên, giúp đỡ em trong suốt thời gian thực hiện đề tài. Chúng em xin chân thành cảm ơn quý Thầy Cô trong khoa Công nghệ thông tin đã truyền đạt những kiến thức quý báu và những kinh nghiệm quý báu cho chúng em trong những năm học vừa qua. Chúng con xin nói lên lòng biết ơn đối với Ông Bà, Cha Mẹ luôn là nguồn động viên, chăm sóc trên bƣớc đƣờng học vấn của chúng con. Xin chân thành cảm ơn các anh chị và bạn bè đã ủng hộ, giúp đỡ và động viên chúng em trong thời gian học tập và nghiên cứu. Mặc dù chúng em đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhƣng chắc chắn chúng em sẽ không tránh khỏi những thiếu sót trong quá trình thực hiện đề tài. Chúng em kính mong nhận đƣợc sự cảm thông và các ý kiến đóng góp của quý Thầy Cô và các bạn. Một lần nữa, xin chân thành cảm ơn. Sinh viên thực hiện, Trần Thị Thu Thảo & Vũ Thị Chinh 11/2012 Mục lục CHƢƠNG 1: TỔNG QUAN 1 1.1 Đặt vấn đề 1 1.2 Tổng quan tình hình nghiên cứu trong và ngoài nƣớc 1 1.2.1 Tổng quan thế giới 1 1.2.2 Tổng quan trong nƣớc 2 1.3 Mục tiêu của luận văn 4 1.4 Nội dung thực hiện 4 CHƢƠNG 2: CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN BẢN 6 2.1 Tổng quát về các phƣơng pháp phân loại văn bản 6 2.2 Mô tả bài toán phân loại văn bản 6 2.3 Các phƣơng pháp phân loại văn bản tiếng Anh 7 2.3.1 Support vector Machine (SVM) 7 2.3.2 Naïve Bayes (NB) 9 2.3.3 Biểu diễn văn bản 10 2.3.4 K–Nearest Neighbor (kNN) 12 2.3.5 Linear Least Square Fit (LLSF) 13 2.3.6 Neural Network (NNet) 14 2.3.7 Centroid- based vector 15 2.4 Kết luận chung về các phƣơng pháp phân loại văn bản tiếng Anh 16 2.5 Tách từ trong bài toán phân loại văn bản 17 2.5.1 Khó khăn vƣớng mắc 18 2.5.2 Các phƣơng pháp tách từ 19 CHƢƠNG 3: ỨNG DỤNG PHÂN LOẠI BÀI BÁO KHOA HỌC TRONG LĨNH VỰC CÔNG NGHỆ THÔNG TIN 24 3.1 Hiện trạng 24 3.2 Quy trình xử lý phân loại bài báo 25 3.2.1 Tách từ trong văn bản 26 3.2.2 Loại bỏ các từ tầm thƣờng 28 3.3 Trích chọn đặc trƣng văn bản 28 3.3.1 Các ý tƣởng cơ bản 28 3.3.2 Phƣơng pháp rút trích đặc trƣng 29 3.3.3 Phƣơng pháp đặc trƣng đề nghị sử dụng 30 3.4 Sử dụng thuật toán Naïve Bayes để phân loại văn bản 32 3.4.1 Lý do chọn Naïve Bayes 32 3.4.2 Ý tƣởng và công thức Naïve Bayes 32 3.4.3 Ƣớc lƣợng P(X|Y) 33 3.4.4 Ƣớc lƣợng P(Y) 34 3.4.5 Ƣớc lƣợng P(Y|X) 34 3.5 Ứng dụng Naïve Bayes vào bài toán phân loại 34 3.5.1 Ý tƣởng 34 3.5.1 Hƣớng dẫn cài đặt 35 CHƢƠNG 4: XÂY DỰNG CHƢƠNG TRÌNH 39 4.1 Xây dựng cơ sở dữ liệu 39 4.1.1 Từ điển tiếng việt 39 4.1.2 Mô tả thực thể 40 4.1 Xây dựng giao diện phân loại văn bản 47 4.1.1 Lƣu đồ phân loại văn bản 47 4.1.2 Thiết kế giao diện 48 4.1.3 Xây dựng các chức năng 49 CHƢƠNG 5: THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 54 5.1 Ví dụ về chƣơng trình phân loại văn bản 54 5.2 Đánh giá kết quả 58 5.2.1 Dữ liệu đầu vào 58 5.2.2 Kết quả thực nghiệm 59 5.2.3 Đánh giá kết quả 60 KẾT LUẬN 62 TÀI LIỆU THAM KHẢO Mục lục hình Hình 2.1 Phân chia dữ liệu huấn huyện 8 Hình 2.2 Biểu diễn văn bản 11 Hình 2.3 Hình Kiến trúc mô đun (Modular Architecture) 15 Hình 2.4 Xây dựng ôtômát âm tiết 19 Hình 2.5 Xây dựng ôtômát từ vựng 20 Hình 2.6 Một tình huống nhập nhằng trong phân tách từ 21 Hình 3.1 Mô hình phân loại tài liệu tự động 25 Hình 3.2 Chi tiết giai đoạn huấn luyện 31 Hình 3.3 Mô tả bƣớc xây dựng bộ phân lớp 35 Hình 4.1 Mô hình cơ sở dữ liệu 45 Hình 4.2 Lƣu đồ phân loại văn bản 47 Hình 4.3 Giao diện chính chƣơng trình 48 Hình 4.4 Huấn luyện văn bản 49 Hình 4.5 Phân loại văn bản 50 Hình 4.6 Thông tin chủ đề 51 Hình 4.7 Thông tin bài báo 52 Hình 5.1 Giao diện phân loại văn bản 54 Hình 5.2 Kết quả phân tách văn bản 55 Hình 5.3 Kết quả dựa vào công thức tính trọng số Tf*idf 56 Hình 5.4 Thống kê kết quả phân loại từ máy 57 Mục lục bảng Bảng 3.1 Bảng phân lớp 38 Bảng 4.1 Thuộc tính thực thể 39 Bảng 4.2 Bảng Chuyên ngành 40 Bảng 4.3 Bảng tài khoản 41 Bảng 4.4 Bảng từ điển 41 Bảng 4.5 Bảng từ phổ thông 42 Bảng 4.6 Bảng từ đƣợc tách 42 Bảng 4.7 Bảng từ chuyên ngành 43 Bảng 4.8 Bảng bài báo 43 Bảng 4.9 Bảng bài báo sau khi phân loại 44 Bảng 4.10 Bảng biến tạm 44 Bảng 4.11 Bảng mối quan hệ thực thể 46 Bảng 4.12 Bảng mối kết hợp của thực thể 46 Bảng 5.1 Bảng số liệu xử lý theo con ngƣời 58 Bảng 5.2 Bảng kết quả chƣơng trình phân loại văn bản tiếng Việt 59 Bảng 5.3 Tỷ lệ(%) phân loại văn bản 60 1 CHƢƠNG 1: TỔNG QUAN 1.1 Đặt vấn đề Trong thời đại bùng nổ công nghệ thông tin hiện nay, phƣơng thức sử dụng giấy tờ trong giao dịch đã dần đƣợc số hoá chuyển sang các dạng văn bản lƣu trữ trên máy tính hoặc truyền tải trên mạng. Bởi nhiều tính năng ƣu việt của tài liệu số nhƣ: cách lƣu trữ gọn nhẹ, thời gian lƣu trữ lâu dài, tiện dụng trong trao đổi đặc biệt là qua Internet, dễ dàng sửa đổi… nên ngày nay, số lƣợng văn bản số tăng lên một cách chóng mặt đặc biệt là trên world-wide-web. Cùng với sự gia tă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. Với số lƣợng văn bản đồ sộ thì việc phân loại văn bản tự động là một nhu cầu bức thiết. Tại sao phải phân loại văn bản tự động? Việc phân loại văn bản sẽ giúp chúng ta tìm kiếm thông tin dễ dàng và nhanh chóng hơn rất nhiều so với việc phải bới tung mọi thứ trong ổ đĩa lƣu trữ để tìm kiếm thông tin. Mặt khác, lƣợng thông tin ngày một tăng lên đáng kể, việc phân loại văn bản tự động sẽ giúp con ngƣời tiết kiệm đƣợc rất nhiều thời gian và công sức. Do vậy, các phƣơng pháp phân loại văn bản tự động đã ra đời để phục vụ cho nhu cầu chính đáng đó. 1.2 Tổng quan tình hình nghiên cứu trong và ngoài nƣớc Công tác phân loại luôn đƣợc các thƣ viện và cơ quan thông tin trên thế giới hết sức quan tâm. Phân loại tài liệu là một khâu công tác quan trọng giúp cho việc kiểm soát thƣ mục, góp phần thúc đẩy việc khai thác, trao đổi thông tin trong phạm vi quốc gia và quốc tế. Trên thế giới và một số thƣ viện lớn ở Việt Nam, phân loại đƣợc áp dụng sâu rộng trong việc tổ chức kho mở và tra cứu thông tin. 1.2.1 Tổng quan thế giới Theo Yang & Xiu, 1999, “việc phân loại văn bản tự động là việc gán các nhãn phân loại lên một văn bản mới dựa trên mức độ tƣơng tự của văn bản đó so với các văn 2 bản đã đƣợc gán nhãn trong tập huấn luyện”. Từ trƣớc đến nay, phân loại văn bản tự động trong tiếng Anh đã có rất nhiều công trình nghiên cứu và đạt đƣợc kết quả đáng khích lệ. Dựa trên các thống kê của Yang & Xiu (1999)[6] và nghiên cứu của chúng em, một số phƣơng pháp phân loại thông dụng hiện nay là: Support Vector Machine -Joachims, 1998[4], k-Nearest Neighbor -Yang, 1994, Linear Least Squares Fit -Yang and Chute, 1994[7] Neural Network -Wiener et al, 1995, Naïve Bayes -Baker and Mccallum, 2000, Centroid- based -Shankar and Karypis, 1998. Các phƣơng pháp trên đều dựa vào xác suất thống kê hoặc thông tin về trọng số của từ trong văn bản. Chi tiết về ý tƣởng và công thức tính toán của mỗi phƣơng pháp sẽ đƣợc chúng em trình bày ở chƣơng 2, mục 2.3. Mỗi phƣơng pháp phân loại văn bản đều có cách tính toán, áp dụng công thức khác nhau, tuy nhiên, nhìn một cách tổng quan thì các phƣơng pháp đó đều phải thực hiện một số bƣớc chung nhƣ sau: đầu tiên, mỗi phƣơng pháp sẽ dựa trên các thông tin về sự xuất hiện của từ trong văn bản (ví dụ tần số, số văn bản chứa từ…) để biểu diễn văn bản thành dạng vector. Sau đó, tuỳ từng phƣơng pháp mà ta sẽ áp dụng công thức và cách thức tính toán khác nhau để thực hiện việc phân loại. Đối với tiếng Anh, các kết quả trong lĩnh vực này rất khả quan, còn đối với tiếng Việt, các công trình nghiên cứu về phân loại văn bản gần đây đã có một số kết quả ban đầu nhƣng vẫn còn nhiều hạn chế. Nguyên nhân là ngay ở bƣớc đầu tiên, chúng ta đã gặp khó khăn trong việc xử lý văn bản để rút ra tần số xuất hiện của từ. Trong khi đó, để phân loại văn bản thì có thể nói bƣớc đầu tiên là quan trọng nhất bởi vì nếu ở bƣớc tách từ đã sai thì việc phân loại hầu nhƣ không thể thành công đƣợc. Phần trình bày tiếp theo sẽ cho chúng ta biết những thách thức đặt ra trong việc tách từ tiếng Việt, cũng nhƣ những ứng dụng thú vị của nó. 1.2.2 Tổng quan trong nƣớc Vấn đề phân loại văn bản tiếng Việt đƣợc nhiều cơ sở nghiên cứu trong cả nƣớc quan tâm trong những năm gần đây. Một số công trình nghiên cứu cũng đạt đƣợc những kết quả khả quan. Các hƣớng tiếp cận bài toán phân loại văn bản đã đƣợc nghiên cứu bao gồm: hƣớng tiếp cận bài toán phân loại bằng lý thuyết đồ thị[10], cách tiếp cận sử dụng [...]... vào việc xây dựng một chƣơng trình có thể phân loại các bài báo theo các chuyên ngành khác nhau đã đƣợc quy định từ trƣớc, các chuyên ngành này quy định dựa trên việc khảo sát một số hội thảo nhƣ: hội thảo Fair, Hội thảo @ Cần Thơ Bao gồm các chuyên ngành: - Các hệ thống tính toán đi động - Công nghệ đa phƣơng tiện - Công nghệ phần mềm - Cơ sở toán học của công nghệ thông tin - Hệ thống thông tin - Khoa... hợp .Xây dựng bộ từ điển các từ trong lĩnh vực Công nghệ thông tin kèm theo trọng số  Bƣớc 4: - Rút trích đặc trƣng ƣớc lƣợng xác suất theo phƣơng pháp Naïve Bayes vào chƣơng trình phân loại văn bản tiếng Việt  Bƣớc 5: - Thử nghiệm và thống kê kết quả xử lý khi hoàn thành chƣơng trình dựa trên tập dữ liệu kiểm thử đã đƣợc phân loại sẵn - Nhận xét và đánh giá 6 CHƢƠNG 2: CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN... văn bản khi thêm một số văn bản mới vào tập dữ liệu mà chỉ phân loại các văn bản mới mà thôi, khi đó thuật toán phải có khả năng giảm độ nhiễu ( noise ) khi phân loại văn bản 2.5 Tách từ trong bài toán phân loại văn bản Hiện nay các phƣơng pháp tách từ tiếng Việt đƣợc công bố vẫn chƣa nhiều và hƣớng tiếp cận chủ yếu là dựa vào tập huấn luyện và từ điển Việc tạo ra hệ thống dữ liệu đó không phải là một... Bayes ứng dụng vào xây dựng một chƣơng trình phân loại văn bản tiếng Việt, bƣớc đầu ứng dụng vào việc phân loại các bài báo khoa học điện tử thuộc lĩnh vực CNTT trong các hội thảo nhƣ: Hội thảo Fair, hội thảo @ Cần Thơ 1.4 Nội dung thực hiện  Bƣớc 1: - Tìm tập dữ liệu bao gồm tập kiểm thử chƣơng trình và tập máy học bao gồm các bài báo, luận văn thuộc chuyên ngành công nghệ thông tin trong đó: o Tập... thông tin thống kê rút trích trực tiếp từ Internet sử dụng các search engine thƣơng mại Thông tin rút trích bao gồm tần số của tài liệu và thông tin tƣơng quan n-gram Hƣớng tiếp cận lai áp dụng nhiều cách khác nhau để tận dụng ƣu điểm của các giải pháp.Tóm lại, các hƣớng tiếp cận để phân loại văn bản tiếng Việt dựa vào từ chỉ khả thi khi có bộ lexicon tốt và hay ngữ liệu huấn luyện đủ lớn và đáng tin. .. trích xuất thông tin thống kê từ Internet thông qua một công cụ tìm kiếm (ví dụ nhƣ Google) thay vì lấy từ tập dữ liệu nhƣ các phƣơng pháp trƣớc Để thực hiện bƣớc tách từ trong luận văn này chúng em dựa trên ý tƣởng của mô hình N-gram là chia văn bản ra thành nhiều chuỗi, mỗi chuỗi gồm hai, ba ký tự trở lên với tập dữ liệu xây dƣng thô và dữ liệu đã đƣợc phân loại sẵn 1.3 Mục tiêu của luận văn Tìm hiểu... truyền thông - Trí tuệ nhân tạo - Xử lý ngôn ngữ tự nhiên và tiếng nói Qua đó giảm bớt khối lƣợng công việc, rút ngắn thời gian phân loại của ban tổ chức hội thảo, đồng thời cũng tăng tính chính xác khách quan của việc phân loại vì dựa trên tập dữ liệu huấn luyện 3.2 Quy trình xử lý phân loại bài báo Để tiến hành phân loại văn bản nói chung, chúng ta sẽ thực hiện các bƣớc nhƣ sau: Hình 3.1 Mô hình phân loại. .. loại tài liệu tự động Bƣớc 1: Rút trích đặc trƣng văn bản và tính trọng số của từ Bƣớc 2: Áp dụng thuật toán phân loại văn bản Bƣớc này chúng ta sẽ đề xuất sử dụng thuật toán Navie Bayes để phân loại văn bản vì nhìn chung đây là một thuật toán phân loại tuyến tính thích hợp trong phân loại văn bản nhiều chủ đề NB có ƣu điểm là cài đặt đơn giản, tốc độ thực hiện thuật toán nhanh, dễ dàng cập nhật dữ liệu. .. với văn bản tiếng Việt cho trƣớc Các kết quả thực nghiệm cho thấy hƣớng tiếp cận này đạt đƣợc những kết quả khả quan trong việc tách từ và phân loại văn bản tiếng Việt với độ đo micro-averaging F1 đạt trên 90% Phƣơng pháp này hứa hẹn tiềm năng lớn cho việc xử lý các văn bản của các ngôn ngữ tƣơng tự tiếng Việt – vốn còn chƣa có các ngữ liệu đƣợc gán nhãn hay lexicon chuẩn 24 CHƢƠNG 3: ỨNG DỤNG PHÂN LOẠI... thử nghiệm độ chính xác của phƣơng pháp tách từ này trong khía cạnh phân loại văn bản 2.5.1 Khó khăn vƣớng mắc Vấn đề phân định từ loại tiếng Việt ở nƣớc ta khá phức tạp Tiếng Việt là loại hình phi hình thái nên việc phân biệt loại từ (danh từ, động từ, tính từ …) và ý nghĩa từ là rất khó, cho dù có sử dụng từ điển Việc tiền xử lý văn bản (tách từ, tách đoạn, tách câu…) sẽ thêm phức tạp với phần xử . có một hệ thống phân loại tài liệu tiếng Việt. Chúng em đã chọn thực hiện đề tài Xây dựng hệ thống phân loại tài liệu tiếng Việt nhằm tìm hiểu và thử nghiệm các phƣơng pháp phân loại văn bản. HÒA, THÁNG 11/2012 TRƢỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN  ĐỀ TÀI: XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI LIỆU TIẾNG VIỆT SVTH: TRẦN THỊ THU THẢO VŨ THỊ CHINH GVHD:ThS TRƢỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN  BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI LIỆU TIẾNG VIỆT TRẦN THỊ THU THẢO VŨ THỊ CHINH