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Ử KHỐ 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Ử KHỐ 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 tốn trích xuất thơng tin từ tài liệu Web và bài tố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 tố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 khốn, thơng tin họ quan tâm là các tin tức mới nhất về thị trường chứng khốn, về kết quả giao dịch ở các sàn chứng khố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 tốn về hệ thống tổng hợp tin tức cần phải giải quyết được hai bài tố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 tố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 tố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 tố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ư Nạve Bayes, SVM và entropy cực đại, Nạ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 tố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 Nạ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 Nạ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 tốn duyệt đồ thị. Tồ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 tốn tìm kiếm trên đồ thị [2]. 2.1.2. Xây dựng crawler Đối với một trang Web X, muốn tổng hợp được những tin tức mới nhất của nĩ, trước tiên cần gieo cho frontier một hạt giống là URL trang Home (hoặc trang Portal) của Web X đĩ. Ví dụ đối với vnexpress.net thì trang Home cĩ URL là: Dùng giao thức HTTP để tải về mã html - gọi là Y - của URL hạt giống. Mã html Y chứa rất nhiều các URL, trong đĩ chỉ một bộ phận nhỏ URL là siêu liên kết đến các detail-page của một tin bài cụ thể là cĩ giá trị, cịn phần lớn các URL cĩ trong Y đều là liên kết khơng liên quan, chủ yếu là các liên kết quảng cáo... Nếu đưa tất cả các siêu liên kết này vào frontier thì sẽ là khơng tối ưu, do frontier phải duyệt qua các URL khơng chứa nội dung thơng tin, như vậy sẽ ảnh hưởng đến tốc độ cập nhật tin mới của hệ thống, cĩ thể gặp phải trường hợp như tin247.com ở trên. Để lấy được các URL chứa nội dung thơng tin cần thiết (phù hợp), khĩa luận đưa ra một tập mẫu cho phép nhận dạng thẻ HTML chứa siêu liên kết tới detail-page. Ví dụ đối với báo vnexpress.net, từ mã html của trang Home cĩ thể dễ dàng nhận biết được các tin cĩ nội dung thơng tin được chứa trong các thẻ HTML với tên class như là link-topnews, folder-topnews, other-foldernews, link-othernews hay link-title. Tập dữ liệu đặc trưng này giúp dễ dàng nhận diện và lấy ra các siêu liên kết chứa nội dung thơng tin đưa vào frontier. Để lấy được các tin mới một cách nhanh nhất, crawler dừng quá trình thêm vào URL vào frontier sau chỉ một lần duyệt frontier hạt giống. Sau khi tồn bộ URL thuộc frontier được xử lý hết, crawler được tạm dừng (delay) trong một khoảng thời gian xác định trước khi lặp lại quá trình. 11 Việc xây dựng crawler cũng chính là xây dựng luật lấy URL từ tập các đặc trưng. 2.2. Xây dựng bộ trích chọn thơng tin 2.2.1. Trích chọn thơng tin trên tài liệu Web Web là dữ liệu điển hình trong dữ liệu bán cấu trúc. Trích xuất thơng tin Web đĩ là vấn đề trích xuất các thành phần thơng tin mục tiêu từ những trang Web. Một chương trình hay một luật trích xuất thường được gọi là một wrapper [4]. Bài tốn trích xuất thơng tin cho dữ liệu bán cấu trúc là rất hữu dụng bởi vì nĩ cho phép thu thập và tích hợp dữ liệu từ nhiều nguồn để cung cấp cho những dịch vụ giá trị gia tăng như : thu được những thơng tin Web một cách tùy ý, meta-search, hay các hệ thống tổng hợp tin tức. Ngày càng nhiều các cơng ty, các tổ chức phổ cập các thơng tin ở trên Web, thì khả năng trích xuất dữ liệu từ các trang Web đĩ ngày càng trở nên quan trọng. Bài tốn này đã được bắt đầu nghiên cứu vào giữa những năm của thập niên 1990 bởi nhiều cơng ty và các nhà nghiên cứu [4]. Thơng tin bán cấu trúc trên Web rất đa dạng và phụ thuộc vào cách lưu trữ và trình bày của từng webstie cụ thể Trích trọng trơng tin, dữ liệu từ những tài liệu Web bán cấu trúc là một vấn đề rất quan trọng trong trích chọn dữ liệu nĩi chung. Các Website thường được trình bày theo nhiều cách rất đa dạng, sử dụng nhiều định dạng về bảng biểu, màu sắc, font chữ, hình ảnh,... nhằm tạo ra sự bắt mắt, thoải mái cho bạn đọc. Đặc điểm của các thơng tin, dữ liệu tồn tại ở dạng bán cấu trúc là ngồi những từ khĩa (ngơn ngữ tự nhiên) thì cịn những cứ liệu (evidence) khác như bảng biểu, danh sách, kích thước font chữ, màu sắc, định dạng, các thẻ HTML... giúp quá trình trích chọn dễ dàng khả thi hơn. Các phương pháp trích chọn thơng tin dạng bán cấu trúc cũng thường phải tận dụng được hết các căn cứ này. 2.2.2. Xây dựng bộ trích chọn tài liệu Web Đối với một trang tổng hợp tin tức, việc trích chọn tài liệu cần phải lấy ra được các phần nội dung sau: - Phần bắt đầu và kết thúc bài báo từ đĩ trích rút ra các nội dung kế tiếp. 12 - Tiêu đề bài báo - Tĩm tắt - Ảnh minh họa - Phần thân bài báo Tương tự với việc trích rút ra các URL để đưa vào frontier như phần crawler (2.1.2). Xậy dựng bộ trích chọn tài liệu cũng là việc tạo ra một tập gồm các đặc trưng, cho phép nhận biết để trích rút được các nội dung cần thiết như trình bày ở trên. Chính tập các đặc trưng này, kết hợp với URL hạt giống và tập các đặc trưng nhận biết URL chứa nội dung thơng tin (được trình bày trong phần 2.1.2) tạo nên một tập dữ liệu đầu vào, cho phép crawling, trích chọn ra nội dung thơng tin của một trang Web bất kì. 2.3. Xây dựng bộ phân lớp 2.3.1. Khái niệm phân lớp văn bản Phân lớp là một trong những mối quan tầm nhiều nhất của con người trong quá trình làm việc với một tập hợp đối tượng. Điều này giúp con người cĩ thể tiến hành việc sắp xếp, tìm kiếm các đối tượng, một cách thuận lợi. Khi biểu diễn đối tượng vào hệ thống thơng tin, tính chất lớp vốn cĩ của đối tượng trong thực tế thường được biểu diễn bằng một thuộc tính “lớp” riêng biệt. Chẳng hạn, trong hệ thống thơng tin quản lý tư liệu thuộc thư viện, thuộc tính về loại tư liệu cĩ miền giá trị là tập tên chuyên nghành của tư liệu, gồm các giá trị như “Tin học”, “Vật lý”,... Trước đây các cơng việc gán các giá trị của thuộc tính lớp thường được làm một cách thủ cơng. Nhưng hiên nay, với sự bùng nổ của thơng tin và các loại dữ liệu, việc đánh thuộc tính lớp một cách thủ cơng là rất khĩ khăn, cĩ thể nĩi là khơng thể. Do vậy, cácphương pháp phân lớp tự động, trong đĩ cĩ phân lớp văn bản là rất cần thiết và là một trong những chủ đề chính của khai phá dữ liệu. Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán tên các chủ đề (tên lớp/nhãn lớp) đã được xác định cho trước vào các văn bản dựa trên nội dung của nĩ. Phân lớp văn bản là cơng việc được sự dụng để hỗ trợ trong quá trình tìm kiếm thơng tin (Information Retrieval), chiết lọc thơng tin (Information Extraction), lọc văn bản hoặc tự động dẫn đường cho các văn bản tới những chủ đề xác định trước. 13 Hình 4. Lược đồ chung xây dựng bộ phân lớp văn bản Hình 4 biểu diễn một lược đồ chung cho hệ thống phân lớp văn bản, trong đĩ bao gồm ba thành phần chính: thành phần đầu tiên là biểu diễn văn bản, tức là chuyển các dữ liệu văn bản thành một dạng cĩ cấu trúc nào đĩ. Thành phần thứ hai là học quy nạp – sử dụng các kỹ thuật học máy để phân lớp văn bản vừa biểu diễn. Thành phần thứ ba là tri thức ngồi – bổ sung các kiến thức thêm vào do người dung cung cấp để làm tăng độ chính xác trong biểu diễn văn bản hay trong quá trình học máy. Trong nhiều trường hợp, các phương pháp học hệ thống phân lớp cĩ thể bỏ qua thành phần thứ ba này. Thành phần thứ hai được coi là trung tâm của một hệ thống phân lớp văn bản. Trong thành phần này, cĩ nhiều phương pháp học máy được áp dụng như mơ hình học Bayes, cây quyết định, phương pháp k láng giềng gần nhất, SVM, entropy cực đại (maximum entropy),... là phù hợp [2]. Dữ liệu văn bản Tri thức ngồi Học quy nạp Các cơng cụ phân lớp Biểu diễn ban đầu Biểu diễn ban Biểu diễn cuối Làm giảm số chiều hoặc lựa chọn thuộc tính (1) 14 2.3.2. Áp dụng thuật tốn phân lớp entropy cực đại xây dựng bộ phân lớp văn bản Rất nhiều bài tốn trong lĩnh vực xử lý ngơn ngữ tự nhiên (NLP) cĩ thể được xem xét dưới dạng các bài tốn phân lớp với việc ước lượng xác suất cĩ điều kiện ( ),p a b của “lớp” a (class) xuất hiện trong “ngữ cảnh” b (context) hay nĩi cách khác là ước lượng xác suất xuất hiện của a với điều kiện b. Ngữ cảnh thường bao gồm các từ và việc chọn ngữ cảnh phụ thuộc theo từng bài tốn cụ thể. Ngữ cảnh b cĩ thể là một từ đơn lẻ, cũng cĩ thể chứa một số từ xung quanh hoặc các từ cùng với các nhãn cú pháp tương ứng. Một lượng văn bản lớn sẽ cung cấp rất nhiều thơng tin về sự xuất hiện đồng thời của các lớp a và ngữ cảnh b, nhưng lượng văn bản đĩ chắc chắn sẽ khơng đủ để chỉ ra một cách chính xác xác suất ( ),p a b của mọi cặp ( ),a b vì các từ trong b thường nằm rải rác. Do đĩ cần phải tìm một phương pháp ước lượng (cĩ thể tin tưởng được) mơ hình xác suất cĩ điều kiện ( ),p a b sử dụng các cứ liệu về sự xuất hiện đồng thời của lớp a và ngữ cảnh b. Mơ hình xác suất entropy cực đại cung cấp một cách đơn giản để kết hợp các cứ liệu ngữ cảnh khác nhau để ước lượng xác suất của một số lớp ngơn ngữ xuất hiện cùng với một số ngữ cảnh ngơn ngữ. 2.3.2.1. Biểu diễn các đặc trưng Theo [1],[7] các đặc trưng (feature) được biểu diễn bằng các mệnh đề biểu diễn thơng tin ngữ cảnh (context predicate). Nếu A là tập các lớp thực hiện phân lớp và B là tập các ngữ cảnh mà quan sát được, thì mệnh đề biểu diễn thơng tin ngữ cảnh là một hàm được mơ tả như sau: : { , }cp B true false→ Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc khơng xuất hiện của các thơng tin hữu ích trong một số ngữ cảnh b B∈ . Tập các mệnh đề biểu diễn thơng tin ngữ cảnh được sử dụng rất nhiều trong các bài tốn tuy nhiên với mỗi bài tốn thì người thực nghiệm phải cung cấp một tập thơng tin ngữ cảnh riêng. Các mệnh đề biểu diễn thơng tin ngữ cảnh được sử dụng trong các đặc trưng – đĩ là một hàm cĩ dạng như sau: : {0,1}f A B× → 15 Và được mơ tả dưới dạng: ( ) ( ) , ' 1 ' and , 0cp a if a a cp b truef a b other  = = =   Hàm này kiểm tra sự xuất hiện đồng thời của lớp dự đốn a' với mệnh đề biểu diễn thơng tin ngữ cảnh cp. Ví dụ nếu trong bài tốn xuất hiện: - a' là lớp “THETHAO”, b là văn bản hiện tại. - cp = [ văn bản hiện tại chứa cụm từ “bĩng_đá” ]. thì hàm đặc điểm này sẽ trả về giá trị 1 nếu như lớp dự đốn a là “THETHAO”. 2.3.2.2. Cách tiếp cận theo ngữ liệu Cho rằng tồn tại một tập dữ liệu huấn luyện 1 1{( , ),..., ( , )}N NT a b a b= trong đĩ một tập hợp lớn các ngữ cảnh 1{ , , }Nb b… được gắn nhãn tương ứng trong tập hợp các lớp 1{ , , }Na a… , sau đĩ tiến hành học cho mơ hình phân lớp entropy cực đại trên tập dữ liệu huấn luyện đĩ. Ý tưởng tập dữ liệu huấn luyện bao gồm các cặp, mỗi cặp là một véc-tơ giá trị logic cùng với một lớp tương ứng rất phổ biến và được sử dụng với rất nhiều các thuật tốn được mơ tả trong các tài liệu về học máy.
Học với ước lượng likelihood cực đại trên mơ hình mũ Để kết hợp các cứ liệu ta cĩ thể đánh trọng số cho các đặc trưng bằng cách sử dụng một mơ hình log-linear hay mơ hình mũ: ( ) ( ) ( ), 1 1 , i k f a b i i p a b Z b λ = = ∏ (1) ( ) ( ), 1 i k f a b i a i Z b λ = =∑∏ trong đĩ k là số lượng các đặc trưng và ( )Z b là biểu thức chuẩn hĩa để đảm bảo điều kiện ( | ) 1 a p a b =∑ . Mỗi tham số iλ tương ứng với một đặc điểm if và cĩ thể được hiểu là “trọng số” của đặc điểm tương ứng ( iλ > 0). Khi đĩ xác suất ( ),p a b là kết quả được chuẩn hố của các đặc trưng cĩ ý nghĩa với cặp ( ),a b , tức là với các đặc điểm if mà 16 ( , ) 1if a b = . Các trọng số 1{ , , }kλ λ… của phân phối xác suất *p là phân phối xác suất phù hợp nhất với tập dữ liệu huấn luyện cĩ thể xác định thơng qua một kĩ thuật phổ biến của ước lượng likelihood cực đại: ( , ) 1 1{ | ( | ) }( ) i k f a b i i Q p p a b Z b λ = = = ∏ , ( ) ( , ) log ( , ) a b L p p a b p a b=∑ * arg max ( ) q Q p L q ∈ = trong đĩ Q là tập hợp các mơ hình của dạng log-linear, ( | )p a b là xác suất thực nghiệm trên tập T, ( )L p là log-likelihood cĩ điều kiện của tập dữ liệu huấn luyện T (được chuẩn hố bởi số lượng sự kiện huấn luyện) và *p là phân phối xác suất tối ưu phụ thuộc theo tiêu chuẩn likelihood cực đại.
Học dưới mơ hình entropy cực đại Trong khi cĩ rất nhiều cách để kết hợp các cứ liệu dưới dạng nào đĩ của một mơ hình phân phối xác suất, dạng (1) cĩ tính tích cực riêng dưới hình mẫu entropy cực đại. Nguyên lý entropy cực đại trong [17] chỉ ra rằng mơ hình xác suất tốt nhất cho dữ liệu là mơ hình làm cực đại giá trị entropy trong số các mơ hình phân phối xác suất thoả mãn các cứ liệu. 2.3.2.3. Mơ hình entropy cực đại cĩ điều kiện Trong hình mẫu được dùng để giải quyết bài tốn đặt ra, cĩ k đặc trưng và khi cho trước một lớp a A∈ cùng với một ngữ cảnh b B∈ thì cơng việc là phải tìm một ước lượng cho xác suất cĩ điều kiện ( ),p a b . Trong các hình mẫu entropy cực đại cĩ điều kiện được sử dụng trong các nghiên cứu [5],[8],[11],[13],[16],[18], lời giải tối ưu *p là phân phối “khơng chắc chắn nhất” (entropy đạt cực đại) thoả mãn k ràng buộc trên các kì vọng của các đặc điểm: * arg max ( ) p P p H p ∈ = , ( ) ( , ) log ( , ) a b H p p a b p a b=∑ 17 { | , {1... }}p i ipP p E f E f i k= = = , ( , ) ( , )i ip a b E f p a b f a b=∑ , ( ) ( , ) ( , )p i i a b E f p b p a b f a b=∑ Ở đây ( )H p kí hiệu cho entropy cĩ điều kiện được tính trung bình trên tập huấn luyện, khác với entropy kết hợp, và xác suất biên của b sử dụng ở đây là xác suất thực nghiệm ( )p b , khác với xác suất mơ hình ( )p b . p iE f là kì vọng của mơ hình p của if , nĩ sử dụng ( )p b làm một xác suất biên. Tương tự như vậy ipE f là kì vọng thực nghiệm của p của if . ( , )p a b kí hiệu cho xác suất thực nghiệm của ( ),a b trong một số mẫu huấn luyện nhất định. Và cuối cùng P kí hiệu cho tập các mơ hình xác suất thoả mãn các cứ liệu quan sát được. 2.3.2.4. Mối quan hệ với likelihood cực đại Thơng thường hình mẫu likelihood cực đại và entropy cực đại là hai cách tiếp cận khác nhau trong mơ hình hố thống kê, nhưng chúng cĩ cùng câu trả lời trong trường hợp này. Cĩ thể thấy rằng việc ước lượng tham số của likelihood cực đại cho mơ hình của dạng (1) tương đương với việc ước lượng tham số của entropy cực đại trên tập các mơ hình thoả mãn. Điều đĩ cĩ nghĩa là: * arg max ( ) arg max ( ) q Q p P p L q H p ∈ ∈ = = Điều này được mơ tả trong [3] sử dụng lý thuyết thừa số nhân lagrange và trong [11] với các đối số lý thuyết thơng tin (đối với trường hợp *p là một mơ hình kết hợp). Dưới tiêu chuẩn likelihood cực đại, *p sẽ phù hợp với dữ liệu ở mức gần nhất cĩ thể, trong khi đĩ dưới tiêu chuẩn entropy cực đại, *p sẽ khơng giả định bất kì điều gì vượt quá những trơng tin trong các ràng buộc tuyến tính định nghĩa ra P. Trong [18] trình bày các chứng minh cho thấy rằng điều kiện * arg max ( ) q Q p L q ∈ = là tương đương với điều kiện * arg max ( ) p P p H p ∈ = . Điều này rất quan trọng để thấy rằng dạng (1) khơng phải là đưa ra 18 một cách khơng cĩ căn cứ, lời giải cho entropy cực đại * arg max ( ) p P p H p ∈ = phải cĩ dạng này. Sự tương đương này đã cung cấp một phương pháp mới cho phép ước lượng tham số cho các mơ hình dựa trên nguyên lý entropy cực đại bằng cách sử dụng các phép ước lượng tham số cho likelihood cực đại. 2.3.2.5. Các thuật tốn ước lượng tham số Cho tập huấn luyện 1 1{( , ),..., ( , )}N NT a b a b= . Phân phối mũ: ( ) ( ) ( ), 1 1| i k f a b i i p a b Z b λ = = ∏ trong đĩ 1{ ... }kλ λ λ= là tập trọng số, ( ) ( ), 1 i k f a b i a i Z b λ = =∑∏ là thừa số chuẩn hố. Huấn luyện mơ hình entropy cực đại chính là ước lượng tập trọng số 1{ ... }kλ λ λ= để cho phân phối ở trên đạt entropy cao nhất. Các thuật tốn phổ biến được sử dụng bao gồm: Thuật tốn GIS – Generalized Iterative Scaling – được đưa ra trong [8]; Thuật tốn IIS – Improved Iterative Scaling – được đưa ra trong [11] là thuật tốn ước lượng tham số của mơ hình mũ do các thành viên trong nhĩm nghiên cứu tại IBM’s T. J. Watson Research Center đưa ra vào những năm đầu của thập kỉ 90; Thuật tốn L-BFGS – Limited memory BFGS – là phương pháp giới hạn bộ nhớ cho phương pháp quasi-Newton. 2.3.3. Phương pháp đánh giá hiệu suất phân lớp Việc đánh giá độ phân lớp dựa trên việc áp dụng mơ hình đối với các dữ liệu thuộc tập dữ liệu kiểm tra testD , sử dụng mơ hình cho từng trường hợp dữ liệu ở testD mà kết quả ra là lớp c dự báo cho từng dữ liệu. Hai độ đo được dùng phổ biến để đánh giá chất lượng của thuật tốn phân lớp là độ hồi tưởng (recall) R và đọ chính xác (precision) P. Ngồi ra, một số độ đo kết hợp được xây dựng từ các độ đo này cũng được sử dụng, trong đĩ điển hình nhất là độ đo F1. Phần dưới đây trình bày các tính tốn chi tiết giá trị của các độ đo hồi tưởng và độ chính xác trong bài tốn phân lớp văn bản. 19 Xét trường hợp lực lượng của tập C các lớp trong bài tốn lớn hơn hai (|C| > 2) với lưu ý rằng, trường hợp tập C chỉ gồm cĩ hai lớp là đơn giản. Đối với lớp c, cho thực hiện mơ hình phân lớp vừa được xác định với các dữ liệu thuộc testD nhận được các đại lượng cTP , cTN , cFP , cFN như bảng dưới đây: Giá trị thực tế Lớp c Thuộc lớp c Khơng thuộc lớp c Thuộc lớp c cTP cTN Giá trị qua bộ phân lớp Khơng thuộc lớp c cFP cFN Diễn giải bằng lời cho từng giá trị trong bảng: - cTP (true positives): số lượng ví dụ dương (tài liệu thực sự thuộc lớp c) được thuật tốn phân lớp gán cho giá trị đúng thuộc lớp c. - cTN (true negatives): số lượng ví dụ âm (tài liệu thực sự khơng thuộc c) nhưng lại được thuật tốn phân lớp gán cho giá trị đúng thuộc lớp c. - cFP (false positives): số lượng ví dụ dương được thuật tốn phân lớp gán cho giá trị sai là khơng thuộc lớp c. - cFN (false negatives): số lượng ví dụ âm được thuật tốn phân lớp gán cho giá trị sai là khơng thuộc lớp c. Khi đĩ, với mỗi lớp c, giá trị các độ đo cR và cP được tính như sau: c c c c TPR TP FP = + và c c c c TPP TP TN = + Với bài tốn phân lớp nhị phân, các độ đo nĩi trên cho một lớp trong hai lớp là đủ để đánh giá chất lượng bộ phân lớp, tuy nhiên, trong trường hợp bài tốn phân lớp K lớp, các Bảng 1. Các nhĩm tài liệu sau phân lớp 20 độ đo trung bình được sử dụng bao gồm trung bình mịn (microaveraging) và trung bình thơ (macroaveaging). Độ hồi tưởng trung bình thơ (macroaveraging recall): 1 1 KM c c R R K = = ∑ và độ chính xác trung bình thơ (macroaveaging precision): 1 1 KM c c P P K = = ∑ Độ hồi tưởng trung bình mịn (microaveraging recall): 1 1 ( ) K c M c K c c c TP P TP FP = = = + ∑ ∑ và độ chính xác trung bình mịn (microaveraging precision): 1 1 ( ) K c M c K c c c TP P TP TN = = = + ∑ ∑ Các độ đo trung bình mịn được coi là các độ đo tốt hơn để đánh giá chất lượng thuật tốn phân lớp đa lớp tài liệu [2]. 21 Chương 3. Xây dựng hệ thống tổng hợp và phân loại tin tự động Việc xây dụng hệ thống tổng hợp và phân loại tin tự động là vấn đề quan trọng nhất của khĩa luận. Ở chương này, khĩa luận sẽ trình bày các bước xây dựng mơ hình hệ thống trên cơ sở lý thuyết được trình bày trong chương 2. 3.1. Cơ sở thực tiễn Hiện nay, các trang Web đều được xây dựng bởi các ngơn ngữ lập trình Web như PHP, ASP.NET,... Nĩ cho phép sinh ra siêu văn bản một cách tự động. Khi một tin tức được đăng tải trên một báo điện tử, thì nĩ tuân theo định dạng HTML nhất định được sinh ra tự động. Điều này cĩ nghĩa là, khi biết mẫu để trích xuất một tin trong một khuơn mẫu, thì cũng cĩ thể trích xuất được tin ở trang cĩ cùng khuơn mẫu đĩ. Ví dụ: Ở trang tin vnexpress.net, hai bài báo ở hình 5a và 5b là hai tin bài trong hai mục báo khác nhau Hình 5a. Mơ tả phần nội dung cần lấy trên trang tin 1 22 Hình 5b. Mơ tả phần nội dung cần lấy trên trang tin 2 Mặc dù detail-pages của chúng khác nhau nhưng chúng cĩ cùng một câu DOM => cĩ nghĩa là cĩ cùng một khuơn mẫu. Hình 6. Mơ hình cây DOM của 2 detail-pages HTML TABLE TD DIV TD BODY BODY TR TR Nội dung bài báo Quảng cáo 23 2 detail-pages này cĩ cùng một cây DOM, nhưng khĩa luận khơng sử dụng trích chọn thơng tin dựa trên mơ hình cây DOM mà sử dụng đặc trưng mẫu để tìm ra các nội dung thơng tin cần thiết. Các đặc trưng này được thể hiện như trong hình 7a và 7b. Hình 7a. Các đặc trưng cho phép trích chọn thơng tin bài báo 1 24 Hình 7b. Các đặc trưng cho phép trích chọn thơng tin bài báo 2 Từ mẫu tìm được, dễ dàng nhận ra phần nội dung thơng tin cần thiết, điều đĩ khiến việc trích chọn ra nội dung thơng tin cần thiết là hết sức đơn giản. 3.2. Xây dựng mơ hình hệ thống Trên cơ sở thực tiễn và mơ hình lý thuyết đã phân tích ở chương 2, tiếp theo khĩa luận sẽ trình bày mơ hình hĩa hệ thống tổng hợp và phân loại tin tức. Các module cấu thành sẽ cho thấy tính mở của hệ thống, cho phép dễ dàng mở rộng khi cần. 25 3.2.1. Mơ hình tổng quan 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 Mơ tả bài tốn Đầu vào: File cấu hình hệ thống xnews.conf Đầu ra: Các tin tức đã được phân tích và tách thành các phần bao gồm: tiêu đề, tĩm tắt, ảnh minh họa, nội dung... ghi vào CSDL. File cấu hình xnews.conf chứa tập các URLs hạt giống, tương ứng với mỗi URL hạt giống là một loạt các mẫu, cho phép trích xuất thơng tin như mong đợi. Định dạng xnews.conf được trình bày như sau: Dịng 1: Chứa số nguyên dương N, với N là số nguồn sẽ sử dụng để tổng hợp tin tức. 8 dịng tiếp theo được trình bày theo định dạng cố định và lặp lại N lần 26 1. URL hạt giống 2. Dấu hiệu nhận biết link con cần lấy 3. Bắt đầu phần nội dung 4. Kết thúc phần nội dung 5. Tiêu đề bài báo 6. Đoạn tĩm tắt nội dung chính 7. Tác giả bài báo 8. Dịng trống Đối với cụm 8 dịng này thì: 7 dịng đầu tiên chứa thơng tin về một Web tin tức, nĩ cho phép crawl, trích xuất tất cả các tin bài cần lấy của Web tin tức đĩ. Dịng thứ 8 được để trống. Ví dụ đối với báo vnexpress.net để cĩ thể lấy được đầy đủ các tin bài cần thiết, khĩa luận xây dựng một bộ gồm các mẫu như sau: ~ ~class="link-topnews"~class="folder-topnews fl"~class="other-folder fl"~<a class="link-othernews"~<a class="link-title"~ ~class="content"~ ~style="margin-top:5px;margin-bottom:5px;"~ ~class=Title~ ~~ ~ormal align=right~ Mỗi một dịng được bắt đầu và kết thúc bởi dấu “~”, đồng thời dấu “~” cũng được sử dụng để làm phân cách cho các mẫu trên cùng một dịng. Đường đi của mơ hình hệ thống 27 Trước hết, “module sinh file huấn luyện” được chạy để sinh ra file huấn luyện, cũng là dữ liệu vào, thành phần chính của “module phân lớp”. Tiếp theo, chương trình đọc file cấu hình xnews.conf để thu được các URLs hạt giống và các mẫu đi cùng với nĩ như được trình bày ở trên. Tạo một yêu cầu (request) HTTP để lấy về mã HTML của trang tin Home tương ứng với URL hạt giống. Đọc và trích xuất ra các siêu liên kết cĩ trong mã HTML này dựa vào mẫu “Dấu hiệu nhận biết link con cần lấy” để thu được danh sách URLs. Truy vấn đến CSDL để kiểm tra các URLs thuộc danh sách này xem đã được thăm chưa, từ đĩ đưa ra được danh sách các URLs chưa thăm. Ở đây, khĩa luận sử dụng lưu trữ trong CSDL bảng băm MD5 của URL thay cho việc lưu trữ trực tiếp URL, đồng thời sử dụng mã MD5 làm khĩa chính của bảng tương ứng trong CSDL (sẽ được trình bày chi tiết hơn trong chương 4). Đối với mỗi URL trong danh sách URLs chưa thăm, lặp lại việc gửi yêu cầu HTTP để thu được mã HTML tương ứng. Sử dụng cơng cụ UnicodeConverter để chuẩn hĩa Unicode mã HTML lấy về, và sau đĩ tiến hành trích xuất thơng tin nhờ vào tập mẫu của file cấu hình xnews.conf. Thơng tin trích xuất được, được đưa vào dữ liệu “các thơng tin đầy đủ về bài báo” bao gồm bảng băm MD5 của URL, URL, tiêu đề bài báo, phần tĩm tắt nội dung, link ảnh minh họa, và phần nội dung bài báo, đồng thời cung cấp “tồn bộ nội dung bài báo” (từ phần bắt đầu đến kết thúc của bài báo đĩ trong mã HTML) cho “module chuẩn hĩa dữ liệu huấn luyện/kiểm tra mơ hình”. Qua bước này, chương trình thu được xâu đã được chuẩn hĩa, làm dữ liệu vào cho “module phân lớp”, qua module thu được nhãn tương ứng của bài báo. Cung cấp nhãn này cho “các thơng tin đầy đủ về bài báo” và cuối cùng là tiến hành ghi các thơng tin này vào CSDL. Xử lý các văn bản khơng thuộc các lớp quan tâm Trên thực tế, xảy ra trường hợp tập các lớp mà bài tốn phân lớp của chương trình quan tâm tới khơng bao quát hết các trường hợp văn bản, tin tức của hệ thống trang tin điện tử. Một phương pháp giải quyết với vấn đề này, là xây dựng thêm một phân lớp, là phân lớp “khác”. Tất cả các văn bản khơng thuộc các phân lớp văn bản thơng thường sẽ được xếp vào phân lớp “khác”. Để giải quyết vấn đề theo cách đơn giản hơn, khĩa luận đã áp dụng một số phương pháp để loại bỏ các trường hợp này từ danh sách URLs dựa vào đặc điểm URL và một số yếu tố khác. Làm như vậy cũng đồng thời tiết kiệm được cơng sức phải xử lý (từ lấy mã HTML, chuẩn hĩa, phân lớp,…) một lượng các văn bản khơng thuộc lớp nào gĩp phần tăng tốc độ chung cho tồn hệ thống. 28 Ví dụ 1: Trên trang báo điện tử vnexpress.net cĩ phân lớp “Tâm sự” là phân lớp khơng thuộc nhĩm được quan tâm của nội dung khĩa luận. Một số URL bài viết thuộc lớp này: - - Dễ dàng nhận thấy đặc điểm chung URL của các bài viết thuộc lớp này. Như vậy với báo điện tử vnexpress.net để loại các bài viết thuộc lớp “Tâm sự” đơn giản chỉ cần loại các URL cĩ chứa xâu “vnexpress.net/GL/Ban-doc-viet/Tam-su/”. Ví dụ 2: Trong trường hợp của báo phapluattp.vn. Xuất hiện các bài báo thuộc lớp “Đơ thị” là phân lớp chưa được khĩa luận quan tâm tới. Dựa vào đặc điểm này, các bài báo thuộc lớp “Đơ thị” cũng sẽ dễ dàng bị loại trước khi chương trình thực hiện trích xuất các nội dung thơng tin cần thiết. Hình 9. Đặc điểm giúp loại tin thuộc lớp chưa quan tâm 29 Kiểm sốt các trang trùng nhau Một vấn đề khơng kém phần quan trọng trong nội dung tổng hợp tin tức là kiểm sốt các bài báo cĩ cùng nội dung. Đối với hệ thống trang tin điện tử của Việt Nam, nhiều trang báo thực hiện việc tổng hợp từ các báo khác bằng phương pháp thủ cơng, và đi kèm với đĩ cĩ một số vấn đề cần được xử lý như sau: - Tiêu đề của tin tức cĩ thể được thay đổi. - Phần tĩm tắt cĩ thể được thêm bớt. - Ảnh minh họa cĩ thể bị thay đổi. - Nội dung cĩ thể được thêm bớt ít nhiều. Để xử lý trường hợp này phương pháp thường được sử dụng là Jaccard Index (chỉ số Jaccard) – cịn được gọi là hệ số tương tự Jaccard, là một số thống kê được sử dụng để so sánh sự giống nhau và đa dạng của các bộ mẫu. Nhưng do cĩ nhiều hạn chế về mặt thời gian, nên vấn đề này sẽ là định hướng phát triển trong tương lai. 3.2.2. Module chuẩn hĩa dữ liệu huấn luyện/kiểm tra mơ hình Hình 10. Module chuẩn hĩa dữ liệu huấn luyện/kiểm tra mơ hình 30 Mơ tả bài tốn Đầu vào: Xâu dữ liệu nội dung bài báo và file danh sách từ dừng1 Đầu ra: Xâu dữ liệu đã được gán nhãn “Xâu dữ liệu nội dung bài báo” là phần nội dung từ bắt đầu đến kết thúc bài báo dưới mã HTML đã được chuẩn hĩa Unicode (là phần dữ liệu được trích xuất từ mã HTML của bài báo tương ứng). Đường đi của mơ hình hệ thống Từ xâu dữ liệu vào, xĩa bỏ các thẻ HTML để thu được tài liệu dạng văn bản phi cấu trúc thơng thường. Sử dụng cơng cụ vnTokenizer phân tích dữ liệu thu được ra dạng từ đơn, từ ghép. Xĩa bỏ các ký tự đặc biệt như dấu chấm, dấu phẩy, chấm phẩy, hai chấm, ba chấm,… thu được xâu dữ liệu chỉ bao gồm các từ đơn từ ghép ngồi ra khơng cịn ký hiệu đặc biệt hay nào khác. Loại bỏ từ dừng ở xâu thu được bằng phương pháp khớp biểu thức chính quy. Từ file danh sách từ dừng sinh ra một mẫu biểu thức chính quy, cho phép khớp tất cả các từ dừng cĩ trong danh sách. Sau khi loại bỏ từ dừng, chuẩn hĩa xâu thu được, xĩa bỏ các dấu trống đầu và cuối, thay tất cả các ký tự trống (ký tự tab, cuối dịng) bằng dấu khoảng cách, giữa hai từ bất kỳ chỉ giữ một dấu khoảng cách duy nhất. Thu được xâu đã được chuẩn hĩa, thực hiện gán nhãn và trả ra xâu đã được gán nhãn. Ở đây, đối với mơ hình huấn luyện, nhãn của dữ liệu đã được biết trước, thực hiện gán nhãn trên xâu đã được chuẩn hĩa. Cịn với mơ hình kiểm tra, nhãn ở đây được gán theo dạng câu hỏi (dấu chấm hỏi “?”). 3.2.3. Module phân lớp Mơ tả bài tốn Đầu vào: File huấn luyện và xâu cần phân lớp đã được chuẩn hĩa Đầu ra: Xâu được phân lớp và gán nhãn File huấn luyện được tạo bởi “module sinh file huấn luyện” và xâu cần được phân lớp được sinh bởi “module chuẩn hĩa dữ liệu huấn luyện/kiểm tra mơ hình”. Đường đi của mơ hình hệ thống 1 31 Từ file huấn luyện, sử dụng cơng cụ maxent cho việc học mơ hình. Sau quá trình học, mơ hình thu được được sử dụng để kiểm tra mơ hình trên “xâu vào đã được chuẩn hĩa” (sử dụng cơng cụ maxent) thu được xâu được gán nhãn. 3.2.4. Module sinh file huấn luyện Mơ tả bài tốn Đầu vào: Tập dữ liệu huấn luyện Đầu ra: File huấn luyện Tập dữ liệu huấn luyện được lấy từ báo vnexpress.net riêng biệt theo 10 phân lớp bao gồm: - XAHOI - THEGIOI - KINHDOANH Hình 11. Module phân lớp 32 - VANHOA - THETHAO - PHAPLUAT - ĐOISONG - KHOAHOC - VITINH - XE Mỗi phân lớp sử dụng 1.000 bài báo cho việc học mơ hình. Như vậy file huấn luyện sẽ bao gồm nội dung được lấy từ 10.000 bài báo đã biết trước nhãn. Đường đi của module Đọc tập dữ liệu huấn luyện để thu được xâu, làm dữ liệu đầu vào cho “module chuẩn hĩa dữ liệu huấn luyện/kiểm tra mơ hình” thu được xâu đã được gán nhãn ghi lại thành file huấn luyện. 3.3. Khả năng mở rộng của hệ thống Theo mơ hình hệ thống của chương trình thể hiện tính module hĩa cao. Các module làm việc ăn khớp với nhau, mỗi module đều cĩ một chức năng rõ ràng và tương đối độc Hình 12. Module sinh file huấn luyện 33 lập với các module cịn lại, các module chỉ tương tác với nhau theo dạng đầu vào của module này là đầu ra của module khác làm cho chương trình dễ dàng kiểm sốt được lỗi phát sinh nếu cĩ. Đồng thời việc nâng cấp tồn bộ hệ thống lấy tin cũng chỉ ảnh hưởng đến từng module riêng biệt chứ khơng tác động tới tất cả các module trong hệ thống. Ví dụ hệ thống cần được nâng cấp về số phân lớp, để mở rộng quy mơ ra những lĩnh vực chưa được quan tâm trước đĩ, hệ thống chỉ cần nâng cấp làm việc với “module sinh file huấn luyện” để cĩ thể phân lớp các văn bản thuộc các lớp mới đĩ. 34 Chương 4. Thực nghiệm và đánh giá kết quả Ở chương này, khĩa luận sẽ trình bày thực nghiệm và kết quả để đánh giá chất lượng của hệ thống tổng hợp và phân loại tin tự động, khĩa luận sẽ đưa ra hai nội dung đánh giá là chất lượng tổng hợp tin và hiệu suất của việc phân loại tin tự động. 4.1. Mơi trường phần cứng và phần mềm 4.1.1. Mơi trường phần cứng Thành phần Thơng số CPU Intel Core 2 Duo T7600 2.0GHz RAM 3GB OS Ubuntu 9.04 Bộ nhớ ngồi 120GB 4.1.2. Cơng cụ phần mềm STT Tên phần mềm Giấy phép Nguồn 1 Netbean 6.5 GPL Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm Bảng 3. Các cơng cụ phần mềm sử dụng trong thực nghiệm 35 2 mysql 5.0.75- 0ubuntu10.3 GPL 3 OpenJDK 1.6.0_0 GPL 4 mysql-connector- java-5.1.12-bin.jar GPL 5 maxent-2.5.2.jar GPL 6 vn.hus.nlp.tokenizer- 4.1.1.jar GPL php 7 UnicodeConverter.jar v2.0 GPL Sử dụng các cơng cụ phần mềm trên khĩa luận đã xây dựng chương trình tự động tổng hợp và phân loại tin trong hệ thống trang tin điện tử. Cấu trúc của chương trình gồm cĩ 3 gĩi (packages) chính như sau:
J_Lib: Cung cấp các chức năng cần thiết ở mức thư viện cung cấp các chức năng tiện dụng nhất và cĩ mức độ độc lập tương đối với các packages khác.
J_NLP: Cung cấp các chức năng tách từ tiếng Việt (sử dụng vnTokenizer) và học cũng như kiểm tra mơ hình với phân lớp văn bản entropy cực đại (sử dụng maxent)
xnews: Sử dụng J_Lib và J_NLP để lấy tin, xử lý trích xuất, chuẩn hĩa, phân lớp, ghi nội dung tin tức vào CSDL, làm và đánh giá các thực nghiệm... Chi tiết các lớp của 3 gĩi này được trình bày như bảng bên dưới: 36 Packages Classes Chức năng J_GET Tạo yêu cầu (request) GET để lấy về mã HTML của một URL J_Img Tải ảnh, phân loại và nén ảnh J_RmTag Xĩa các thẻ HTML để thu được bài báo ở dạng văn bản thơng thường J_SQL Kết nối với CSDL (sử dụng mysql- connector-java-5.1.12-bin.jar) J_Lib J_Utilities Sinh mã md5 của một xâu và các tiện tích trên file CreateModel Sinh mơ hình từ tập dữ liệu huấn luyện (sử dụng maxent) Predict Kiểm tra mơ hình, gán nhãn cho dữ liệu kiểm tra (sử dụng maxent) J_NLP J_Tokenizer Sử dụng biểu thức chính quy để chuẩn hĩa xấu, loại ký tự đặc biệt, loại bỏ từ dừng, tách từ đơn, từ ghép (sử dụng vnTokenizer) Crawler Điều khiển lấy tin, trích xuất nội dung, chuẩn hĩa, phân lớp, vào ra trên CSDL,... (sử dụng UnicodeConverter.jar) xnews Lab Tạo dữ liệu học, kiểm tra mơ hình từ tập dữ liệu thơ Bảng 4. Mơ tả chức năng các lớp trong các gĩi 37 4.2. Cấu trúc Cơ sở dữ liệu Cơ sở dữ liệu của chương trình được thiết kế cho việc tối ưu hĩa tốc độ truy vấn, khi số lượng tin tức được lưu là rất lớn. CSDL của chương trình được thiết kế gồm 3 bảng t_store01, t_store02 và t_store03 cụ thể như sau:
Bảng t_store01: Cho biết các tin theo ngày và theo thể loại được phép hiển thị. Ứng với mỗi một ngày, bảng t_store01 sinh ra thêm 10 hàng tương ứng với 10 phân lớp của tin tức, lưu trữ thơng tin về các bài báo trong ngày theo 10 phân lớp tương ứng.
Bảng t_store02: Lưu trữ tất cả các thơng tin chi tiết của một bài báo cụ thể.
Bảng t_store03: Được thiết kế các trường, các chức năng giống với t_store01, chỉ cĩ một điểm khác duy nhất, ngược lại với t_store01 cho biết các tin được phép hiển thị, thì t_store03 lại cho biết các tin khơng được phép hiển thị. Bảng t_store03 nhằm phục vụ cho việc lưu trữ các bài báo được xĩa bằng tay trong trường hợp tin bài khơng phù hợp. Tất cả các tin khi được lấy về, sẽ được mặc định ghi vào bảng t_store01 và bảng t_store02. Bảng t_store03 sẽ được sử dụng đến bởi chức năng của người biên tập báo. Dù là một hệ thống lấy tin tức tự động, nhưng việc hệ thống cần cĩ một người biên tập báo là điều hồn tồn hợp lý. Người biên tập sẽ cĩ nhiệm vụ theo dõi và chuẩn xác lại các thơng tin, ví dụ khi hệ thống được mở rộng nguồn cập nhật tin, hệ thống tự động lấy về một số bài báo cĩ nội dung liên quan đến các vấn đề “nhạy cảm” về chính trị, người biên tập cĩ nhiệm vụ đánh giá mức độ “nhạy cảm” của vấn đề và đưa ra quyết định cĩ giữ bài báo hay khơng. Nếu bài báo cần được xĩa, nĩ sẽ được chuyển từ bảng t_store01 sang t_store03 - nơi chỉ chứa các tin đã bị xĩa (trên thực tế là bị ẩn) và trường vis của bảng t_store02 cũng thay đổi tương ứng. Ngồi ra t_store03 được tạo ra cịn nhằm để cho phép khơi phục lại tin đã xĩa nếu thấy cần thiết. Để phục vụ việc tối ưu hĩa truy vấn, khĩa luận thực hiện đánh chỉ mục (index) trên các bảng của CSDL tương ứng với các khĩa chính của bảng đĩ: - data_type trên t_store01 và t_store03. - u5 trên t_store02. 38 Bảng Trường/ Khĩa Kiểu dữ liệu Mơ tả date_type (p) int Date là ngày theo kiểu int được viết dưới định dạng YYYYMMDD viết liền type, để chia ra tin tức theo 10 phân lớp trong ngày. nums int Số bài đến thời điểm hiện tại trong ngày ứng với mỗi một mục tin date_type. t_store01 lu5 text Danh sách bảng băm MD5 của nums tin tương ứng của mỗi mục tin trong ngày. Hai mã MD5 liên tiếp phân cách nhau bởi xâu “t_#”. Mỗi mã MD5 cho phép truy vấn tin theo u5 của t_store02. u5 (p) char(32) u5 gồm 32 ký tự là bảng băm MD5 của URL bài báo gốc. u5 được sử dụng làm khĩa chính của bảng, đồng thời được đánh chỉ mục (index) cho phép tối ưu hĩa truy vấn. Ngồi tập tất cả các u5 trong t_store02 cũng đại diện cho tất cả các URL đã thăm, như vậy nĩ cho phép kiểm tra URL chưa thăm. vis char(1) vis được ấn định 1 trong 2 trạng thái 0 hoặc 1. Mặc định vis bằng 1 cĩ nghĩa là bài báo đĩ được phép hiển thị. Ngược lại khi vis bằng 0 thì bài báo đĩ khơng được phép hiển thị. t_store02 type int type là số cĩ 2 chữ số 00, 01, …, 09 tương ứng với 10 phân lớp tin tức của hệ thống. Bảng 5. Chi tiết CSDL 39 infors text Thơng tin tổng hợp về một bài báo bao gồm các nội dung thơng tin: ngày tháng định dạng YYYYMMDDHHmm bài báo được lấy về, URL bài báo gốc, tiêu đề bài báo, tĩm tắt, link ảnh minh họa. Các thơng tin được ngăn cách nhau bởi ký hiệu “t_#”. view mediumtext Chứa tồn bộ phần nội dung thơng tin bài báo, từ sau phần tĩm tắt đến kết thúc. t_store03 Hồn tồn tương tự với t_store01 về thành phần. 4.3. Đánh giá chất lượng tổng hợp tin Sau một thời gian thử nghiệm, quan sát và đánh giá, khĩa luận đi tới một số kết luận về chất lượng tổng hợp tin của hệ thống:
Tốc độ lấy tin mới nhanh và ổn định. Chương trình đặt một độ trễ (delay) là 2 phút cho hai lần (lặp) lấy tin liên tiếp. Kết quả quan sát cho thấy, khi tin mới xuất hiện trên hệ thống nguồn, thì sau đĩ 1 đến 2 phút, tin tức sẽ được tự động cập nhật vào hệ thống.
Chất lượng tin lấy về với độ chính xác cao, hiện khĩa luận chưa phát hiện việc trích rút sai nội dung tin tức như tiêu đều, tĩm tắt, ảnh, nội dung… Khĩa luận sẽ tiếp tục theo dõi và đánh giá trong thời gian tới. 4.4. Thực nghiệm và đánh giá hiệu suất phân loại tin tự động 4.4.1. Xây dựng tập dữ liệu huấn luyện và kiểm tra mơ hình Để chuẩn bị dữ liệu huấn luyện và kiểm tra mơ hình khĩa luận thực hiện phân lớp bằng tay dựa vào các mục tin (category) của Website báo điện tử nguồn. Đối với mỗi một phân lớp, sau khi được phân bằng tay, khĩa luận tạo một số đoạn mã chương trình bằng Java thực hiện việc lấy các tin tức cũ hơn của mục tin (phân lớp) đĩ theo ngày tháng. 40 STT Tên phân lớp VnExpress Mơ tả 1 XAHOI Xã hội Giáo dục, lối sống, du lịch,… 2 THEGIOI Thế giới Tình hình thế giới, chủ yếu là tình hình chính trị. 3 KINHDOANH Kinh doanh Kinh doanh, tình hình kinh tế, thị trường chứng khốn,… 4 VANHOA Văn hố Âm nhạc, thời trang, điện ảnh, nghệ sĩ, mỹ thuật,… 5 THETHAO Thế giới Tình hình thế giới, chủ yếu là tình hình chính trị. 6 PHAPLUAT Pháp luật Vụ án, vụ việc, các văn bản luật mới. 7 DOISONG Đời sống Tâm sự, gia đình, tình cảm, nội trợ, nhà ở, ẩm thực,… 8 KHOAHOC Khoa học Khoa học nĩi chung, khơng liên quan đến lớp Cơng nghệ. 9 VITINH Vi tính Cơng nghệ thơng tin và truyền thơng. 10 XE Ơtơ-Xe máy Phương tiện đi lại. Dữ liệu dùng cho việc huấn luyện mơ hình là các bài báo được lấy từ trang báo điện tử vnexpress.net, với số lượng các phân lớp như sau: Bảng 6. Các lớp tài liệu sử dụng trong thực nghiệm 41 STT Phân lớp Số lượng văn bản 1 XAHOI 1000 2 THEGIOI 1000 3 KINHDOANH 1000 4 VANHOA 1000 5 THETHAO 1000 6 PHAPLUAT 1000 7 DOISONG 1000 8 KHOAHOC 1000 9 VITINH 1000 10 XE 1000 Tổng số 10000 Ở đây, khĩa luận xin đưa ra 2 thực nghiệm kiểm tra chất lượng phân loại tin tự động. 4.4.2. Thực nghiệm thứ nhất Mơ tả thực nghiệm Thực nghiệm nhằm đánh giá chất lượng phân loại tin tự động đối với dữ liệu test cũng được lấy từ báo điện tử vnexpress.net. Bảng 7. Thống kê số lượng tài liệu dùng cho việc học mơ hình 42 Đầu vào: Mơ hình đã qua huấn luyện của hệ thống, và các dữ liệu lấy từ vnexpress.net ở dạng thơ. Đầu ra: Bảng đánh giá kết quả độ chính xác theo các chỉ số bao gồm: độ hồi tưởng (R), độ chính xác (P) và độ đo F1. Tập dữ liệu được dùng cho việc kiểm tra mơ hình được mơ tả trong bảng STT Phân lớp Số lượng văn bản 1 XAHOI 100 2 THEGIOI 100 3 KINHDOANH 100 4 VANHOA 100 5 THETHAO 100 6 PHAPLUAT 100 7 DOISONG 100 8 KHOAHOC 100 9 VITINH 100 10 XE 100 Tổng số 1000 Kết quả thực nghiệm 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 43 Nhãn Độ chính xác (%) Độ hồi tưởng (%) F1 (%) XAHOI 92.93 92.00 92.46 THEGIOI 98.96 95.00 96.94 KINHDOANH 90.74 98.00 94.23 VANHOA 95.24 100.00 97.55 THETHAO 98.99 98.00 98.49 PHAPLUAT 94.23 98.00 96.08 DOISONG 93.20 96.00 94.58 KHOAHOC 97.92 94.00 95.92 VITINH 100.00 93.00 96.37 XE 98.97 96.00 97.46 Trung bình thơ 96.11 96.00 96.01 Trung bình mịn 96.00 96.00 96.00 Nhận xét: - Kết quả thực nghiệm cho thấy kết quả phân lớp tự động được thực hiện với dữ liệu test mơ hình của báo điện tử vnexpress.net là rất tốt. Tất cả các trường hợp độ đo F1 đều chính xác hơn 92%. Trung bình mịn của độ chính xác và độ hồi tưởng đều đạt 96%. - Đối với đặc trưng của tin tức. Một bài báo cĩ thể thuộc cùng lúc nhiều phân lớp. Ví dụ, một bài báo với nội dung nĩi về “tình trạng mĩc túi diễn ra tại các bến xe bus ở Hà Nội” tin tức này hồn tồn cĩ thể xếp vào phân lớp PHAPLUAT Bảng 9. Kết quả thực nghiệm 1 44 xong cũng đồng thời cĩ thể xếp vào phân lớp XAHOI. Chính bản chất đa lớp cĩ thể cĩ của một tin tức cụ thể cĩ thể dẫn đến kết quả phân lớp bị sai. 4.4.3. Thực nghiệm thứ hai Mơ tả thực nghiệm Thực nghiệm nhằm đánh giá chất lượng phân loại tin tự động đối với dữ liệu test lấy từ các báo khác bao gồm: dantri.com.vn, baodatviet.vn và tuoitre.vn. STT Phân lớp Số lượng văn bản 1 XAHOI 50 2 THEGIOI 50 3 KINHDOANH 50 4 VANHOA 50 5 THETHAO 50 6 PHAPLUAT 50 7 DOISONG 50 8 KHOAHOC 50 9 VITINH 50 10 XE 50 Tổng số 500 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 45 Đầu vào: Mơ hình đã qua huấn luyện của hệ thống, và các dữ liệu lấy từ 3 nguồn tin dantri.com.vn, baodatviet.vn và tuoitre.vn ở dạng thơ. Đầu ra: Bảng đánh giá kết quả độ chính xác theo các chỉ số bao gồm: độ hồi tưởng (R), độ chính xác (P) và độ đo F1. Tập dữ liệu được dùng cho việc kiểm tra mơ hình được mơ tả trong bảng 10. Kết quả thực nghiệm Nhãn Độ chính xác (%) Độ hồi tưởng (%) F1 (%) XAHOI 34.85 46.00 39.66 THEGIOI 83.02 88.00 85.44 KINHDOANH 79.63 86.00 82.69 VANHOA 66.67 80.00 72.73 THETHAO 94.23 98.00 96.08 PHAPLUAT 89.58 86.00 87.75 DOISONG 69.23 54.00 60.67 KHOAHOC 76.67 46.00 57.50 VITINH 83.93 94.00 88.86 XE 100 84.00 91.30 Trung bình thơ 77.78 76.20 76.25 Trung bình mịn 76.20 76.20 76.20 Bảng 11. Kết quả thực nghiệm 2 46 Nhận xét: - Kết quả thực nghiệm 2 trong bảng 11 cho biết trong tổng số lượng văn bản được phân lớp, thì cĩ khoảng 76% văn bản được phân lớp đúng theo cách phân lớp của báo dùng để test. - Bảng 9 và bảng 11 cho thấy cĩ sự khác biệt lớn về độ chính xác của thực nghiệm 2 so với thực nghiệm 1. Sở dĩ cĩ sự khác nhau như vậy, là do trong thực nghiệm 2, khĩa luận tiến hành kiểm tra với các báo điện tử khác với báo được sử dụng để học mơ hình, các báo khác nhau này cĩ cây phân lớp khơng tương đồng nhau, do đĩ dẫn đến việc phân lớp đúng theo báo học mơ hình là vnexpress.net thì cĩ thể khơng đúng với báo kiểm tra tuoitre.vn. Ví dụ: tin “Phá án buơn ma túy biên giới, 3 cơng an bị thương”1 theo cây phân lớp của tuoitre.vn được xếp vào lớp XAHOI, nhưng với một tin cĩ nội dung hồn tồn tương tự “3 cảnh sát bị thương khi truy bắt nhĩm buơn ma túy”2 thì vnexpress.net lại xếp tin này vào phân lớp PHAPLUAT. 1 an buon-ma-tuy-bien-gioi-3-cong-an-bi-thuong.html 2 47 Kết luận Kết quả đạt được của khĩa luận Từ việc nghiên cứu về các bài tốn của hệ thống tổng hợp và phân loại tin tự động, khĩa luận đã trình bày phương pháp tổng hợp và phân loại tin tức từ các trang báo điện tử khác nhau. Qua những kết quả thực nghiệm cho thấy tính hiệu quả của phương pháp này. Về mặt nội dung, khĩa luận đã đạt được những kết quả như sau: - Giới thiệu các hệ thống tổng hợp tin hiện cĩ của Việt Nam, ưu và nhược điểm. - Nghiên cứu cơ sở lý thuyết về trích chọn thơng tin tài liệu Web, giới hiệu mơ hình phân lớp văn bản entropy cực đại. Chỉ ra thế mạnh của phương pháp này trong phân lớp văn bản phù hợp với nội dung phân lớp tin tức. Giới thiệu các đại lượng sử dụng cho việc đánh giá kết quả phân lớp. - Thơng qua mơ hình lý thuyết nghiên cứu được về trích chọn tài liệu Web và phân lớp văn bản, khĩa luận đã tiến hành xây dựng mơ hình hệ thống tổng hợp và phân loại tin tự động. - Trên cơ sở mơ hình cĩ được, khĩa luận đã cài đặt được chương trình chính là hệ thống tổng hợp và phân loại tin tự động bằng ngơn ngữ Java sử dụng mơi trường Netbean. - Đánh giá chất lượng tổng hợp và hiệu suất phân loại tin của hệ thống, từ đĩ cho thấy chất lượng tổng hợp và hiệu suất phân loại đều rất tốt. Mặc dù vậy, do hạn chế về thời gian và kiến thức khĩa luận vẫn cịn hạn chế sau: - Khĩa luận chưa xây dựng được giao diện người dùng cho hệ thống. - Chưa đưa ra được phương pháp xử lý thỏa đáng đối với trường hợp một bài báo thuộc nhiều hơn một phân lớp. - Chưa kiểm sốt một cách tồn diện đối với trường hợp các bài báo cĩ nội dung trùng nhau. Định hướng tương lai Trong tương lai, khĩa luận sẽ tiếp tục nghiên cứu về các vấn đề sau: 48 - Phân lớp một bài báo cĩ thể thuộc vào nhiều lớp sử dụng phân lớp mờ Fuzzy. - Kiểm sốt trường hợp các bài báo cĩ nội dung trùng nhau sử dụng chỉ số Jaccard. - Đồng thời khĩa luận cũng cố gắng để sớm cơng bố hệ thống để phục vụ người sử dụng. 49 Tài liệu tham khảo [1]. Nguyen Viet Cuong, Nguyen Thi Thuy Linh, Phan Xuan Hieu and Ha Quang Thuy (2005). “A Maximum Entropy Model for Vietnamese Web Content Classification”. Proceedings of the 8th National Conference on Information Technology of Vietnam: pages 174-189, Vietnam. (in Vietnamese). [2]. Hà Quang Thụy, Phan Xuân Hiếu, Đồn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú. Giáo trình khai phá dữ liệu Web. Nxb GDVN, 2009, tr. 153-166, tr. 220-233. [3]. Berger, A., Della Pietra, S., and Della Pietra, V. A maximum entropy approach to natural language processing. Computational Linguistics, volume 22, number 1, 1996, pages 39-71. [4]. Bing Liu, Web Data Mining Exploring Hyperlinks, Contents, and Usage Data, ,December, 2006. [5]. Chieu, H. L. and Ng, H. T. A Maximum Entropy Approach to Information Extraction from Semi-Structured and Free Text. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), 2002, pages 786-791. [6]. Crescenzi V., Mecca G., and Merialdo P. Roadrunner: Towards Automatic Data Extraction from Large Web Sites.In Proc. of Very Large Data Bases (VLDB’01), pages 109–118, 2001. [7]. Cuong Nguyen Viet, Nguyen Thi Thuy Linh, Ha Quang Thuy and Phan Xuan Hieu (2006). “A Maximum Entropy Model for Text Classification”. Proceedings of International Conference on Internet Information Retrieval 2006 (IRC 2006), pages 143- 149, Korea. [8]. Darroch, J. and Ratcliff, D. Generalized iterative scaling for log-linear models. Annals Mathematical Statistics, volume 43, number 5, 1972, pages 1470–1480. [9]. Debnath S., Mitra P., and Giles C. L. Automatic extraction of informative blocks from webpages. In Proc. SAC, pages 1722-1726, 2005. [10]. Debnath S., Mitra P., Pal N., and Giles C. L. Automatic Identification of Informative , IEEE Trans. Knowl. Data Eng. 17 , 2005. 50 [11]. Della Pietra, S., Della Pietra, V. and Lafferty, J. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 19, number 4, 1997, pages 380–393. [12]. Gautam Pant, Parmini Srinivasan, and Filipo Menczer (2004). Crawling the Web. Web Dynamic 2004: pg. 153-178. [13]. Jaynes, E. R. (1957). Information Theory and Statistical Mechanics. Physic Review, volume 106, 1957, pages 620-630. [14]. Kushmerick WIEN N. Wrapper Induction for Information Extraction. Ph.D Thesis. Dept. of Computer Science, University of Washington, TR UW-CSE-11-04- 1997. [15]. NGAI Grace, WU Deka, CARPUAT Marine, WANG Chi-Shing, WANG Chi- Yung. Semantic Role Labeling with Boosting, SVMs, Maximum Entropy, SNOW, and Decision Lists. [16]. Nigam, K., Lafferty, J. and McCallum, A. Using maximum entropy for text classification. IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999, pages 61-67. [17]. Nigam K., McCallum, A., Thrun S. and Mitchell, T. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning, volume 39, number 2/3, 2000, pages 103-134. [18]. Ratnaparkhi, A. A simple introduction to maximum entropy models for natural language processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997.