Khóa luận Tự động tổng hợp và phân loại tin trong hệ thống trang tin điện tử

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Xuân Thành TỰ ĐỘNG TỔNG HỢP VÀ PHÂN LOẠI TIN TRONG HỆ THỐNG TRANG TIN ĐIỆN TỬ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Xuân Thành TỰ ĐỘNG TỔNG HỢP VÀ PHÂN LOẠI TIN TRONG HỆ THỐNG TRANG TIN ĐIỆN TỬ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Trí Thành HÀ NỘI - 2010 Lời cảm ơn Lời đầu tiên, tôi xin được bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo – TS. Nguyễn Trí Thành đã tận tình hướng dẫn, đôn đốc tôi trong suốt quá trình là khóa luận tốt nghiệp. Tôi xin được chân thành cảm ơn các thầy, cô và các cán bộ của trường Đại Học Công Nghệ đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu. Tôi xin gửi lời cảm ơn tới ThS Nguyễn Thanh Bình, ThS Lê Văn Thanh và tập thể các anh chị em của công ty iTim đã động viên, khích lệ, tạo điều kiện cho tôi trong suốt quá trình làm khóa luận. Tôi cũng xin gửi lời cảm ơn tới các bạn trong tập thể lớp K51CD và K51CHTTT đã ủng hộ và khuyến khích tôi trong suốt quá trình học tập tại trường. Cuối cùng, tôi muốn được gửi lời cảm ơn vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn! Sinh viên Lê Xuân Thành i Tóm tắt nội dung Trong hệ thống các website điện tử, các trang tin tức chiếm một vai trò hết sức quan trọng, giúp con người cập nhật những tin tức thời sự mới nhất thuận tiện mọi lúc mọi nơi. Theo Hiệp hội các nhà xuất bản trực tuyến (Online Publishers Association – OPA) thì phần lớn thời gian trên Internet con người dùng để đọc tin tức1. Như vậy, nhu cầu cập nhật tin tức của con người là rất lớn, và nếu người dùng chỉ phải vào một trang Web duy nhất để cập nhật được tất cả các tin tức thì sẽ tiện dụng hơn rất nhiều so với việc phải truy cập vào nhiều trang. Khóa luận này tập trung vào việc nghiên cứu và xây dựng một hệ thống tổng hợp tin tức, dựa trên bài toán trích xuất thông tin từ tài liệu Web và bài toán phân lớp văn bản. Khóa luận đưa ra mô hình gom tin tự động với tính mở rộng cao, trình bày các bước xây dựng một hệ thống tổng hợp tin tức. Khóa luận cũng đã tiến hành chạy các thực nghiệm và đánh giá kết quả. Kết quả đánh giá cho thấy chất lượng gom tin và phân loại là nhanh và đáng tin cậy. 1 ii Mục lục Tóm tắt nội dung .................................................................................................................i Mục lục ................................................................................................................................ii Bảng các ký hiệu viết tắt ...................................................................................................iv Danh sách các hình .............................................................................................................v Danh sách các bảng biểu ...................................................................................................vi Giới thiệu .............................................................................................................................1 Chương 1. Khái quát về các trang tin tức và các hệ thống tổng hợp tin tức của Việt Nam ........................................................................................................................3 1.1. Khái quát chung về các báo điện tử ........................................................................3 1.2. Khái quát chung về các hệ thống tổng hợp tin tức..................................................3 Chương 2. Cơ sở lý thuyết xây dựng mô hình hệ thống tổng hợp và phân loại tin tự động ........................................................................................................................8 2.1. Xây dựng crawler ....................................................................................................8 2.1.1. Khái niệm crawler...........................................................................................8 2.1.2. Xây dựng crawler .........................................................................................10 2.2. Xây dựng bộ trích chọn thông tin..........................................................................11 2.2.1. Trích chọn thông tin trên tài liệu Web..........................................................11 2.2.2. Xây dựng bộ trích chọn tài liệu Web............................................................11 2.3. Xây dựng bộ phân lớp ...........................................................................................12 2.3.1. Khái niệm phân lớp văn bản.........................................................................12 2.3.2. Áp dụng thuật toán phân lớp entropy cực đại xây dựng bộ phân lớp văn bản. ......................................................................................................................14 2.3.3. Phương pháp đánh giá hiệu suất phân lớp....................................................18 Chương 3. Xây dựng hệ thống tổng hợp và phân loại tin tự động ...........................21 3.1. Cơ sở thực tiễn.......................................................................................................21 3.2. Xây dựng mô hình hệ thống ..................................................................................24 3.2.1. Mô hình tổng quan........................................................................................25 3.2.2. Module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình .............................29 3.2.3. Module phân lớp...........................................................................................30 3.2.4. Module sinh file huấn luyện .........................................................................31 3.3. Khả năng mở rộng của hệ thống............................................................................32 iii Chương 4. Thực nghiệm và đánh giá kết quả.............................................................34 4.1. Môi trường phần cứng và phần mềm ....................................................................34 4.1.1. Môi trường phần cứng ..................................................................................34 4.1.2. Công cụ phần mềm .......................................................................................34 4.2. Cấu trúc Cơ sở dữ liệu...........................................................................................37 4.3. Đánh giá chất lượng tổng hợp tin..........................................................................39 4.4. Thực nghiệm và đánh giá hiệu suất phân loại tin tự động ....................................39 4.4.1. Xây dựng tập dữ liệu huấn luyện và kiểm tra mô hình ................................39 4.4.2. Thực nghiệm thứ nhất...................................................................................41 4.4.3. Thực nghiệm thứ hai.....................................................................................44 Kết luận .............................................................................................................................47 Tài liệu tham khảo ............................................................................................................49 iv Bảng các ký hiệu viết tắt Ký hiệu Diễn giải HTML HyperText Markup Language URL Uniform Resource Locator WWW World Wide Web CSDL Cở sở dữ liệu v Danh sách các hình Hình 1. Minh họa lỗi tổng hợp tin trang Baomoi.com…………………………………….5 Hình 2. Minh họa lỗi mất ảnh trang tintuc.xalo.vn………………………………………..7 Hình 3. Sơ đồ cơ bản của một crawler đơn luồng…………………………………………9 Hình 4. Lược đồ chung xây dựng bộ phân lớp văn bản………………………………….13 Hình 5a. Mô tả phần nội dung cần lấy trên trang tin 1…………………………………...21 Hình 5b. Mô tả phần nội dung cần lấy trên trang tin 2…………………………………...22 Hình 6. Mô hình cây DOM của 2 detail-pages…………………………………………...22 Hình 7a. Các đặc trưng cho phép trích chọn thông tin bài báo 1………………………...23 Hình 7b. Các đặc trưng cho phép trích chọn thông tin bài báo2…………………………24 Hình 8. Mô hình tổng quan của hệ thống tổng hợp và phân loại tin tức…………………25 Hình 9. Đặc điểm giúp loại tin thuộc lớp chưa quan tâm……………………….........…..28 Hình 10. Module chuẩn hóa dữ liệu huấn luyện/kiểm tra mô hình………………………29 Hình 11. Module phân lớp………………………………………………………………..31 Hình 12. Module sinh file huấn luyện……………………………………………………32 vi Danh sách các bảng biểu Bảng 1. Các nhóm tài liệu sau phân lớp………………………………………………….19 Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm………………………………..34 Bảng 3. Các công cụ phần mềm sử dụng trong thực nghiệm…………………………….34 Bảng 4. Mô tả chức năng các lớp trong các gói………………………………………….36 Bảng 5. Chi tiết CSDL……………………………………………………………….......38 Bảng 6. Các lớp tài liệu sử dụng trong thực nghiệm…………………………………….40 Bảng 7. Thống kê số lượng tài liệu dùng cho việc học mô hình…………………………41 Bảng 8. Thống kê số lượng tài liệu thực nghiệm 1 dùng kiểm tra mô hình……………...42 Bảng 9. Kết quả thực nghiệm 1…………………………………………………………..43 Bảng 10. Thống kê số lượng tài liệu thực nghiệm 2 dùng kiểm tra mô hình…………….44 Bảng 11. Kết quả thực nghiệm 2…………………………………………………………45 1 Giới thiệu Trong gần hai mươi năm trở lại đây, cùng với sự phát triển bùng nổ của Internet mà đặc biệt là World Wide Web (www) - hay còn gọi tắt là Web - mang lại cho con người rất nhiều lợi ích. Đồng thời với đó cũng là sự bùng nổ về thông tin, giúp con người dễ dàng cập nhật tin tức mới nhất, nhưng hệ quả sau đó là sự tiêu tốn rất nhiều thời gian, khi những thông tin cần đối với một người dùng thuộc một nội dung cụ thể lại nằm trên nhiều trang Web khác nhau. Ví dụ đối với một nhà đầu tư chứng khoán, thông tin họ quan tâm là các tin tức mới nhất về thị trường chứng khoán, về kết quả giao dịch ở các sàn chứng khoán, nhưng để có được điều này thường họ phải truy cập vào nhiều trang khác nhau để có đủ thông tin. Như vậy, nhu cầu đặt ra cần có một hệ thống tổng hợp tin tức nhanh nhất và được phân chia theo các mục, phân mục rõ ràng, giúp thuận tiện hơn cho nhu cầu thông tin của người dùng. Điều này giúp người dùng thuận tiên hơn cho việc tìm, cập nhật các thông tin mà mình quan tâm một cách thuận tiện nhất, tiết kiệm thời gian nhất. Điều này đặc biệt có ý nghĩa trong cuộc sống bận rộn hiện đại ngày nay. Để giải quyết được bài toán về hệ thống tổng hợp tin tức cần phải giải quyết được hai bài toán khác là trích xuất thông tin từ tài liệu Web và phân lớp tự động các văn bản Web – là hai bài toán được quan tâm ở rất nhiều các hội nghị lớn về khai phá dữ liệu và xử lý ngôn ngữ tự nhiên [6],[9],[10],[14]. Khóa luận xây dựng một tập luật cho phép tự động gom và trích xuất thông tin từ các trang tin tức của Việt Nam, tin tức được lấy về sẽ được gán nhãn tự động nhờ vào thuật toán phân lớp văn bản entropy cực đại (maximum entropy), và được ghi lại vào CSDL, phục vụ cho việc xuất bản tin. Khóa luận gồm có 4 chương được mô tả sơ bộ dưới đây: Chương 1: Khái quát về các trang tin tức và các hệ thống tổng hợp tin tức của Việt Nam. Giới thiệu về các trang báo điện tử (trang tin tức) và các hệ thống tổng hợp tin tức. Đánh giá ưu và nhược điểm của các hệ thống đó. Chương 2: Cơ sở lý thuyết xây dựng mô hình hệ thống tổng hợp và phân loại tin tự động. Giới thiệu về crawler, trích chọn thông tin từ tài liệu Web, phân lớp văn bản bằng phương pháp entropy cực đại. Đồng thời chương này cũng giới thiệu về phương pháp đánh giá hiệu suất của việc phân lớp văn bản thông độ hồi tưởng, độ chính xác và độ đo F1. 2 Chương 3: Xây dựng hệ thống tổng hợp và phân loại tin tự động. Nêu ra các cơ sở lý thực tiễn có thể áp dụng cho việc trích chọn thông tin đối với tài liệu Web. Đưa ra mô hình hệ thống, các module, cách thức tương tác giữa các module với nhau. Từ đó nêu lên được tính mở rộng cao của hệ thống. Chương 4: Thực nghiệm và đánh giá kết quả để đánh giá bài toán mô hình được xây dựng trong chương 3. Kết quả thực nghiệm cho thấy hiệu quả tốt của hệ thống tổng hợp và phân loại tin tự động của khóa luận. Phần kết luận tóm lược nội dung chính của khóa luận và nêu lên định hướng của khóa luận trong thời gian tới. 3 Chương 1. Khái quát về các trang tin tức và các hệ thống tổng hợp tin tức của Việt Nam 1.1. Khái quát chung về các báo điện tử Hiện nay, các website báo điện tử của Việt Nam chiếm một vai trò không thể thiếu trong việc cung cấp tới bạn đọc các nội dung thông tin chính trị, xã hội, thể thao, giải trí... mới nhất. Điều này được thể hiện qua việc hai trang tin tức lớn nhất của Việt Nam là vnexpress.net và dantri.com.vn liên tục nằm trong top 10 websites được truy cập nhiều nhất tại Việt Nam, theo xếp hạng của alexa.com. Mặc dù vậy các báo điện tử của Việt Nam hiện nay, việc phân lớp (phân loại) tin tức thường được làm thủ công bởi người viết báo hoặc người biên tập. Do vậy nhu cầu đặt ra là cần có một hệ thống phân lớp văn bản Tiếng Việt, cho phép gán nhãn cho các tài liệu một cách tự động. Khóa luận xin trình bày một phương pháp cho phép phân lớp các văn bản hay tài liệu Web vào các lớp, dựa vào mô hình được trả về sau quá trình huấn luyện, sẽ được trình bày kỹ hơn trong chương 2. 1.2. Khái quát chung về các hệ thống tổng hợp tin tức Khoảng hơn một năm trở lại đây, các hệ thống tổng hợp tin tức của Việt Nam phát triển rất mạnh. Sau đây khóa luận xin liệt kê ra một số hệ thống hiện đang được xem là thành công nhất, đều nằm trong top 40 websites được truy cập nhiều nhất Việt Nam theo xếp hạng của alexa.com.
Baomoi.com: Có thể nói baomoi.com là trang tổng hợp tin nổi bật nhất hiện nay với rất nhiều ưu điểm nổi trội so với các hệ thống tổng hợp báo khác: • Ưu điểm: - Baomoi.com được biết đến như là trang tổng hợp lấy tin từ nhiều nguồn nhất, từ các báo điện tử lớn tin tức tổng hợp trên đủ lĩnh vực cho đến các báo chỉ chuyên về một lĩnh vực (ví dụ: chỉ chuyên về ôtô-xe máy), hay đến cả các báo địa phương. - Baomoi.com còn được biết đến như là trang tổng hợp tin có crawler tốt nhất, tin tức sau khi xuất hiện trên trang gốc, chỉ sau một vài phút đã có tin tổng hợp trên baomoi.com. 4 - Hỗ trợ tìm kiếm tin tức • Nhược điểm: baomoi.com cho phép người đọc xem một tin chi tiết theo 2 cách, tuy nhiên cả 2 cách đều có những vấn đề không tốt: - Cách thứ nhất là xem trang gốc - website chứa bài báo quan tâm thông qua trang của baomoi.com. Như vậy có nghĩa là báo mới đứng vai trò trung gian, nhận dữ liệu từ webstie chứa bài báo và gửi nguyên vẹn đến cho người đọc. Cách làm này là cách phổ biến với hầu hết các tin của baomoi.com, cách này không tối ưu cho người sử, trong khi người sử dụng chỉ cần xem nội dung tin thì việc xem cả trang gốc như thế mang đến rất nhiều thông tin thừa như các ảnh, các flash quảng cáo, làm cho tốc độ xem tin bị chậm, đặc biệt đối với những tin có clip thì tốc độ xem clip là rất chậm hoặc có thể dẫn đến hiện tượng “đơ” trình duyệt. - Cách thứ hai, tin được lấy về và lưu trong CSDL của baomoi.com, sau đó khi có yêu cầu tin, thì tin sẽ được truy vấn để trả về kết quả ở trang chi tiết (detail-page), cách làm này ít phổ biến hơn cách thứ nhất. Cách làm này của baomoi.com xuất hiện các lỗi về trích xuất tin, đối với những bài viết có nhiều ảnh, thì ảnh sẽ bị đẩy hết xuống dưới cùng, sau phần kết thúc bài báo như trong Hình 1. 5 Hình 1. Minh họa lỗi tổng hợp tin trang Baomoi.com 6
tintuc.xalo.vn: • Ưu điểm: - Tốc độ lấy tin của tintuc.xalo.vn là rất nhanh, có thể nói về tốc độ thì tintuc.xalo.vn không hề thua kém baomoi.com. - Tintuc.xalo.vn cho phép người đọc có thể dễ dàng truy cập đến bài báo gốc nếu cần bằng một liên kết đặt phía dưới tiêu đề ở detail-page. • Nhược điểm: - Ở page-list khá nhiều tin của tintuc.xalo.vn gặp hiện tượng mất ảnh minh họa
tin247.com: Tốc độ lấy tin của tin247.com là khá chậm, tin tức sau khi xuất hiện ở trang gốc khoảng vài giờ mới được cập nhật trên trang tin của tin247.com. Như vậy thì nói chung không đáp ứng được nhu cầu cập nhật tin tức nhanh chóng như 2 trang tổng hợp trên. 7 Hình 2. Minh họa lỗi mất ảnh trang tintuc.xalo.vn 8 Chương 2. Cơ sở lý thuyết xây dựng mô hình hệ thống tổng hợp và phân loại tin tự động Ở chương này, khóa luận xin trình bày các bước xây dựng một hệ thống tổng hợp tin tức. Để có một hệ thống tổng hợp tin tức tốt hai điều phải quan tâm đầu tiên đó là xây dựng một crawler tốt, và tiếp theo là xây dựng cây phân lớp đạt hiệu quả cao. Chính vì thế khóa luận đã tiến hành tham khảo, đánh giá và lựa chọn phương pháp phân lớp hiệu quả để áp dụng cho hệ thống. Phương pháp entropy cực đại (Maximum Entropy) là phù hợp hơn cả [3],[16]. Trong các phương pháp phân lớp văn bản nổi tiếng nhất được biết đến như Naïve Bayes, SVM và entropy cực đại, Naïve Bayes là phương pháp lâu đời nhất và với độ chính xác không cao nhưng lại có tốc độ phân lớp là nhanh hơn entropy cực đại và SVM, ngược lại thì SVM lại là thuật toán hiện đại và được biết đến là phương pháp phân lớp văn bản có độ chính xác là cao nhất hiện nay nhưng tốc độ phân lớp thì chậm hơn so với Naïve Bayes và entropy cực đại. Đối với yếu tố phân lớp của một hệ thống tổng hợp tin tức thì cần phải cân bằng được cả hai yêu tố chất lượng phân lớp và tốc độ. Vậy khóa luận đi đến kết luận sẽ sử dụng phương pháp entropy cực đại cho việc phân lớp văn bản do entropy cực đại có thời gian thực thi không thua nhiều Naïve Bayes nhưng hiệu quả thì cũng rất tốt, không thua kém nhiều so với SVM [15],[16]. Khóa luận cũng trình bày phương pháp đánh giá hiệu quả của cây phân lớp dựa vào các độ đo là độ chính xác (P), độ hồi tưởng (R) và độ đo (F1). 2.1. Xây dựng crawler 2.1.1. Khái niệm crawler Kích thước quá lớn và bản chất thay đổi không ngừng của Web đặt ra một nhu cầu mang tính nguyên tắc là, cần phải cập nhật không ngừng tài nguyên cho các hệ thống trích chọn thông tin trên Web. Thành phần crawler đáp ứng được nhu cầu này bằng cách đi theo các siêu liên kết trên các trang Web để tải về một cách tự động nội dung các trang Web. Web crawler khai thác sơ đồ cấu trúc của Web để duyệt không gian Web bằng cách chuyển từ trang Web này sang trang Web khác. 9 Hình 3. Sơ đồ cơ bản của một crawler đơn luồng [12] Hình vẽ biểu diễn sơ đồ khối một crawler đơn luồng. Chương trình crawler yêu cầu một danh sách các URL chưa được thăm (frontier). Ban đầu frontier chứa các URL hạt nhân do người dùng hoặc chương trình khác cung cấp. Mỗi vòng lắp crawling bao gồm: lấy ra các URL tiếp theo cần được tải về từ frontier, nạp trang Web tương ứng với URL đó bằng giao thức HTTP, chuyển nội dung trang Web vừa được tải về cho phục vụ kho chứa trang Web. Quá trình crawling được kết theo theo hai tình huống: - Đạt được điều kiện dừng cho trước, chẳng hạn như số lượng các trang Web được tải về đã đáp ứng được yêu cầu đặt ra. - Danh sách các URL tại frontier rỗng, không còn trang Web yêu cầu crawler phải tải về. Lưu ý rằng, điều kiện frontier rỗng được tính với một độ trễ nào đó, bởi có [done] [no URL] Cr aw lin g Lo o p Initialize frontier with seed URLs start Check for termination [not done] Fetch page Parse page Add URLs to frontier [URL] Pitch URL from frontier end 10 một số trường hợp, bộ điều khiển crawling chưa chuyển kịp các dánh sách URL sẽ tới thăm. Hoạt động của thành phần crawler có thể được xem như một bài toán duyệt đồ thị. Toàn bộ thế giới được Web xem như một đồ thị lớn với các đỉnh là các trang Web và các cung là các siêu liên kết. Quá trình tải một trang Web và đi tới một trang Web mới tương tự như quá trình mở rộng một đỉnh trong bài toán tìm kiếm trên đồ thị [2]. 2.1.2. Xây dựng