Luận văn Nghiên cứu công nghệ khai phá dữ liệu văn bản, áp dụng cho các trang tin tức trên các thiết bị cầm tay (pdas & smartphones)

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ NGỌC ANH NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN, ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ CẦM TAY (PDAS & SMARTPHONES) LUẬN VĂN THẠC SỸ KHOA HỌC HÀ NỘI-2006 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ NGỌC ANH NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN, ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ CẦM TAY (PDAS & SMARTPHONES) NGÀNH CÔNG NGHỆ THÔNG TIN CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: 01.01.10 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HÀ QUANG THỤY HÀ NỘI-2006 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 2 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả nêu trong luận văn là trung thực và chưa từng được công bố trong các công trình khác. Tác giả luận văn Vũ Ngọc Anh Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 3 MỤC LỤC TÓM TẮT........................................................................................................... 5 CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT .................................................. 6 CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH................................................................ 7 CÁC HÌNH MINH HỌA.................................................................................... 8 MỞ ĐẦU ............................................................................................................ 9 CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ TRÊN THIẾT BỊ CẦM TAY ................................................................................................... 12 1.1. Báo điện tử và công nghệ Internet không dây........................................ 12 1.1.1. Báo điện tử - một thành tựu của Internet ........................................ 12 1.1.2. Sự phát triển của các thiết bị cầm tay ............................................. 13 1.1.3. Công nghệ kết nối internet không dây............................................ 14 1.2. Bài toán xây dựng kênh tin tức điện tử trên thiết bị cầm tay ................. 15 1.2.1. Mô tả bài toán ................................................................................. 15 1.2.2. Mô tả các chức năng cơ bản của hệ thống...................................... 16 1.3. Hướng tiếp cận giải quyết bài toán ........................................................ 16 Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT TIN.................................................................................................................... 18 2.1. Khái niệm “Chi phí chuyển đổi cây” ..................................................... 18 2.2. Thuật toán RTDM .................................................................................. 22 2.3. Áp dụng RTDM trích xuất tin tức tự động............................................. 29 2.3.1 Phân cụm trang ................................................................................ 31 2.3.2 Trích xuất mẫu chung ...................................................................... 32 2.3.3 Khớp dữ liệu .................................................................................... 35 2.3.4 Gán nhãn dữ liệu.............................................................................. 37 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 4 Chương III . PHÂN TÍCH THIẾT KẾ HỆ THỐNG........................................ 39 3.1.Giới thiệu................................................................................................. 39 3.2. Mô hình Use Case: ................................................................................. 40 3.2. Mô hình lớp ............................................................................................ 45 3.4. Danh sách các thực thể ........................................................................... 47 3.5. Mô hình thực thể liên kết ....................................................................... 48 Chương IV. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................ 49 4.1. Giới thiệu chung về hệ thống ................................................................. 49 4.2. Thực nghiệm và đánh giá kết quả .......................................................... 49 KẾT LUẬN....................................................................................................... 54 TÀI LIỆU THAM KHẢO ................................................................................ 55 PHỤ LỤC. MÔ TẢ CHI TIẾT CÁC THỰC THỂ ........................................... 58 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 5 TÓM TẮT Luận văn quan tâm nghiên cứu các giải pháp trích chọn thông tin trên Web nhằm xây dựng một hệ thống cung cấp tin tức trên các thiết bị cầm tay thông minh mà tin tức này được trích chọn từ các báo điện tử tiếng Việt. Luận văn sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi de Castro Reis và các đồng tác giả đề xuất [28], một thuật toán được đánh giá rất hiệu quả trong việc trích chọn tin tức tức tự động thông qua việc phân tích cấu trúc cây. Hiện nay RTDM được dùng như là thành phần lõi chính của hệ thống trích xuất tin tức có tên là AkwanClipping (Akwan Information Technologies, thuộc công ty Google tại Braxin) cung cấp tin tức hàng ngày của các tờ báo phổ biến nhất tại Braxin. Luận văn đã tiến hành chi tiết và hoàn thiện các phần nội dung không công bố của thuật toán RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung cấp tin điện tử trên các thiết bị cầm tay thông minh. Hệ thống thử nghiệm việc trích chọn tin tức trên các báo điện tử tiếng Việt phổ dụng hiện nay và đã cho kết quả đáng khích lệ. Chúng tôi đang tiến hành cải tiến tốc độ làm việc của hệ thống nhằm tiến tới đưa hệ thống vào hoạt động thực tế. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 6 CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT Từ viết tắt Giải nghĩa RTDM Restricted Top-Down Mapping PDA Personal digital assistant Data extraction Trích xuất dữ liệu Trees Cây biểu diễn cấu trúc trang HTML Edit distance Chi phí chuyển đổi giữa 2 cây (thay thế, chèn, xoá nút) PK Primary Key FK Foreign Key PF Primary & Foreign Key Tx Cây biểu diễn trang Web. Tx[i] Nút thứ i của cây Tx t[i] Cây con có nút gốc tại vị trí thứ i Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 7 CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH STT Ký hiệu Giải thích 1 Tiến trình thực hiện một nhiệm vụ nào đó trong hệ thống 2 Tác nhân của hệ thống, đóng vai trò tương tác với hệ thống trong quá trình thực hiện 3 Nguồn thông tin cung cấp cho hệ thống 4 Điều kiện kiểm tra và đưa ra các quyết định tương ứng với các kết quả nhận được 5 Miêu tả sự phụ thuộc lẫn nhau của các đối tượng Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 8 CÁC HÌNH MINH HỌA Hình 3 - Ví dụ về ánh xạ giữa 2 cây ................................................................. 20 Hình 4 – Ví dụ ánh xạ trên-xuống .................................................................... 21 Hình 5 – Một ví dụ về ánh xạ trên xuống hạn chế............................................ 23 Hình 6 - Một mẫu tin chi tiết Quốc tế trên trang tienphongonline.com.vn ...... 30 Hình 7: Các bước trích xuất tin tức [28]........................................................... 31 Hình 8 - Các bước hình thành ne-pattern từ các nhóm..................................... 37 Hình 9 : Gói các lớp quản lý các cây HTML.... Error! Bookmark not defined. Hình 10 : Gói các lớp phục vụ tính toán giá trị RTDM.................................... 46 Hình 11 : Gói các lớp quản lý các trang tin tức ................................................ 46 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 9 MỞ ĐẦU Sự phát triển của báo điện tử, một thành quả của Internet nói riêng và của Công nghệ thông tin nói chung, đã dẫn tới các thay đổi lớn đối với thói quen đọc báo. Internet với ưu thế về tốc độ và khả năng vươn xa cho phép độc giả có thể tiếp cận tin tức mọi lúc mọi nơi. Với sự tiến bộ không ngừng của công nghệ viễn thông, ngày nay thiết bị cầm tay thông minh ngày càng được phổ biến với giá cả ngày càng hạ và đã trở thành một công cụ đắc lực, bình dân và không thể thay thế. Tốc độ kết nối Internet không dây được cải thiện không chỉ về tốc độ mà cả về phạm vi phủ sóng, trong đó, thế hệ mạng không dây chuẩn WIMAX (IEEE 802.16) cho phép khoảng cách phủ sóng tới 50km và thông lượng tối đa tới 70Mbps. Tất cả những yếu tố trên đây đã trở thành tiền đề cho việc đáp ứng nhu cầu xem tin tức trên thiết bị cầm tay, một nhu cầu đã trở thành thiết yếu, hàng ngày, hàng giờ của mỗi người dùng cuối các thiết bị này. Tuy nhiên, việc đọc báo trên các thiết bị cầm tay còn nhiều bất tiện. Khung màn hình hạn chế của thiết bị cầm tay không cho phép hiển thị trang Web được thiết kế cho máy tính để bàn: font chữ thường bị lỗi khi xem tin tức trên thiết bị cầm tay, các thông tin quảng cáo và banner cũng được tải về cùng với tin tức làm giảm đáng kể tốc độ và gây tràn màn hình… Chính vì vậy, mục đích của luận văn này là xây dựng một hệ thống cho phép dễ dàng và thuận tiện xem tin tức tiếng Việt của báo điện tử bất kỳ trên thiết bị cầm tay thông minh. Luận văn sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi de Castro Reis và các đồng tác giả đề xuất [28], một thuật toán được đánh giá rất hiệu quả trong việc trích xuất tin tức tức tự động thông qua việc phân tích cấu trúc cây. Thuật toán RTDM được cải tiến trên thuật toán trích xuất thông tin Web đã có để áp dụng đặc thù riêng cho bài toán trích xuất tin tức. Qua thực nghiệm trên 35 trang tin tức, thuật toán RTDM cho kết quả trung bình 87.71% trích xuất tin tức thành công không cần có sự can thiệp của con người. Hiện tại, RTDM được sử dụng như là thành phần lõi chính của hệ thống trích xuất tin tức có tên là AkwanClipping (Akwan Information Technologies, Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 10 thuộc công ty Google tại Braxin) cung cấp tin tức hàng ngày của các tờ báo phổ biến nhất tại Braxin. Chúng tôi đã chi tiết và hoàn thiện các nội dung không công bố của thuật toán RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung cấp tin điện tử trên các thiết bị cầm tay thông minh. Hệ thống thử nghiệm đã trích chọn thông tin trên các báo điện tử tiếng Việt phổ dụng hiện nay. Chúng tôi đã tiến hành đánh giá hệ thống và các kết quả đánh giá cho thấy hệ thống là hữu dụng. Tuy nhiên, để đưa hệ thống vào hoạt động thực tiễn cần phải nghiên cứu tăng tốc độ hoạt động của nó. Nội dung của luận văn được tổ chức thành bốn chương được giới thiệu sơ bộ như dưới đây. Chương 1. Xây dựng kênh tin tức điện tử trên các thiết bị cầm tay giới thiệu sự phát triển nhanh chóng của báo điện tử và công nghệ kết nối Internet không dây, tiền đề cho việc ra đời của kênh cung cấp tin điện tử trên các thiết bị cầm tay. Mô tả bài toán và hướng tiếp cận giải quyết bài toán xây dựng kênh tin điện tử từ các báo điện tử tiếng Việt trên các thiết bị cầm tay cũng được trình bày. Bài toán xây dựng kênh tin tức điện tử trên các thiết bị cầm tay được giải quyết trên cơ sở phân cụm các trang Web trong site báo điện tử theo đó nội dung tin tức cần trích chọn được lấy từ vùng nội dung thông tin trong cấu trúc các trang Web của site đó. Chương 2. Thuật toán RTDM và ứng dụng trong trích xuất tin trình bày vấn đề đánh giá tính tương đồng của các trang Web thông qua khái niệm chi phí chuyển đổi cây đối với kiến trúc cây mô tả các trang Web. Sau khi phân cụm, lớp tương ứng với mỗi cụm được gán nhãn để tạo dựng mô hình phân lớp cho các trang Web mới và trích chọn tin tức. Luận văn đề xuất một phiên bản chi tiết của thuật toán để thi hành hệ thống trích chọn tin tức trên các báo điện tử. Với phiên bản này, vấn đề thi hành hệ thống trở nên dễ dàng hơn. Chương 3 giới thiệu quá trình phân tích và thiết kế hệ thống theo tiếp cận hướng đối tượng. Các mô hình tương ứng được trình bày ở đây. Chương 4. trình bày hệ thống thực nghiệm với một số nhận xét đánh giá kết quả thực nghiệm. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 11 Phần Kết luận tóm tắt các kết quả chính yếu nhất của luận văn. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 12 CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ TRÊN THIẾT BỊ CẦM TAY 1.1. Báo điện tử và công nghệ Internet không dây 1.1.1. Báo điện tử - một thành tựu của Internet Đọc báo chí, xem tin tức là một nhu cầu không thể thiếu của mỗi người trong xã hội thông tin, không phân biệt lứa tuổi. Các loại báo chí được phát hành đa dạng về nội dung, hình thức phù hợp với nhu cầu riêng biệt của từng độc giả. Hiện nay, với sự phát triển lớn mạnh của internet kéo theo sự bùng nổ thông tin, thông qua các trang báo điện tử. Chỉ với một thao tác tìm kiếm đơn giản, ta cũng có thể tìm được hàng trăm đến hàng ngàn trang báo đủ chủng loại. Chẳng hạn ta sử dụng công cụ tìm kiếm của Google để tìm theo từ khoá "Báo điện tử" và những trang từ Việt nam, hàng loạt các trang tin tức được liệt kê như vietnamnet.vn, vnexpress.net, dantri.com.vn, tuoitre.com.vn… Theo thống kê của google.com.vn thì có đến 755.000 kết quả tìm được, tất nhiên trong số đó rất nhiều các kết quả là trùng nhau, nhưng con số đó cũng đủ để nói lên sự phát triển lớn mạnh về số lượng của các trang tin tức điện tử tại Việt Nam hiện nay. Một ưu điểm lớn của các tin tức trên các trang báo điện tử đó là tính thời sự, cập nhật rất cao. Đối với các tin tức trên báo in giấy, có khi ta phải đợi đến ngày hôm sau mới được xem. Nhanh nhất như báo "Thể thao Việt nam", cũng phải đến 5h sáng hôm sau mới có thể đăng thông tin về các trận đấu trong buổi đêm ngày hôm đó. Ngược lại, đối với các báo điện tử, thông tin có thể được cập nhật gần như lập tức khi có sự kiện. Theo thống kê trên diễn đàn nghiệp vụ báo chí Việt Nam vào tháng 11 năm 20041, hiện có khoảng 2 triệu người Việt Nam truy cập Internet, và không ít hơn số đó là độc giả của các tờ báo điện tử như VietNamNet, VnExpress, TuoitreOnline, Lao động điện tử... Do ưu thế về phương tiện công nghệ mà báo điện tử ngày càng thu hút được nhiều độc giả. Ở Mỹ, nếu tính theo số lượng độc giả thì báo giấy đang ngày càng bị thất thế so với báo điện tử. Một nghiên cứu hồi tháng 3-2005 của Hiệp 1 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 13 Hội Báo In Hoa Kỳ (NNA) cho thấy với các tờ báo lớn và được tín nhiệm nhất ở nước Mỹ như New York Times, Washington Post, số người đọc báo qua mạng đã vượt trội số người đọc báo in (New York Times: 12,8 triệu/5 triệu; Washington Post: 7.8 triệu/1.8 triệu, Los Angeles Times: 4.3 triệu/2.4 triệu)1,2. Cũng vì sự phát triển bùng nổ như vậy nên việc đọc thông tin trên báo điện tử một cách hiệu quả cũng không phải là dễ dàng. Hiện tượng người đọc báo điện tử khó kiểm soát tin và nội dung tin đã đọc đã trở thành thực tế. Cần thiết xây dựng phương tiện hỗ trợ người dùng giải quyết hiện tượng nói trên. 1.1.2. Sự phát triển của các thiết bị cầm tay Ngày nay, với sự phát triển vượt bậc của khoa học công nghệ, các sản phẩm cầm tay đã thực sự đem lại rất nhiều hiệu quả lao động cho con người. Các thiết bị có thể kể đến ở đây là các điện thoại thông minh (smart phone), máy tính bỏ túi (pocket pc). Cùng với sự phát triển công nghệ, các thiết bị này đã được hỗ trợ khả năng lướt Web không dây với tốc độ ngày càng cải thiện. Do đó, đây cũng là một kênh tiếp cận thông tin, tin tức điện tử thuận tiện nhanh chóng, gọn nhẹ mọi lúc mọi nơi. Hơn thế nữa, do nhu cầu công việc của con người cộng với giá cả cũng hợp lý nên các thiết bị này cũng ngày càng được dùng phổ biến hơn (nhiều nhất vẫn là trong các doanh nghiệp). Những thuận 2 Hình 1. Tin tức điện tử trên các thiết bị cầm tay Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 14 lợi này là cơ sở dẫn tới nhu cầu xem tin tức điện tử trên các thiết bị cầm tay ngày một phát triển3. 1.1.3. Công nghệ kết nối internet không dây Song song với sự phát triển của các thiết bị cầm tay, công nghệ kết nối không dây cũng phát triển ngày càng mạnh mà mới đây nhất là chuẩn Wimax - 802.16e với khả năng kết nối với tốc độ 20Mbps trong phạm vi 3km và có thể tiến xa hơn. Wimax hay còn gọi là chuẩn 802.16, mới được công nhận vào tháng 1/2003, cung cấp khả năng truy cập băng rộng không dây giữa người sử dụng và điểm kết nối bằng các băng tần từ 2 đến 11 GHz, có thể kết nối mà không cần điều kiện tầm nhìn thẳng. Hiện tại, chuẩn này đã được kết nối thử nghiệm tại khoảng trên 100 điểm trên toàn thế giới. Công nghệ này đặc biệt phù hợp với việc phổ cập Internet băng rộng tại nhiều miền sâu, vùng xa. Trên thế giới hiện có khoảng 100 cuộc thử nghiệm công nghệ WiMAX đang được tiến hành. Sự quan tâm của các chính phủ và các nhà cung cấp dịch vụ về triển khai công nghệ WiMAX là bằng chứng rõ ràng cho thấy công nghệ này rất thiết thực, người dùng cuối sẽ được tận hưởng những giá trị sử dụng cao từ dịch vụ băng rộng không dây và khả năng di động không giới hạn. Hiện nay, công nghệ WiMAX đang được sử dụng làm công nghệ không dây cố định cho truy cập băng rộng đầu cuối trong năm 2005 và sẽ tiến tới di động hoàn toàn trong những năm tới4 Chưa cần đến khả năng kết nối tốc độ cao, các dịch vụ truy cập internet di động cũng sẽ được hình thành tại VN trong thời gian tới với tốc độ chấp nhận được 156Kbps đối với các thiết bị di động. Dịch vụ băng rộng di động của EVN Telecom sử dụng công nghệ CDMA 2000-1X, tần số 450 Mhz, cho phép người sử dụng kết nối Internet trực tiếp trên máy điện thoại hoặc thông qua máy tính cá nhân với tốc độ 156 Kbps đối với mạng 1X tại bất cứ nơi nào có phủ sóng5. 3 4 5 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 15 1.2. Bài toán xây dựng kênh tin tức điện tử trên thiết bị cầm tay 1.2.1. Mô tả bài toán Mục tiêu của luận văn là nghiên cứu các công nghệ khai phá dữ liệu văn bản, áp dụng cho việc xây dựng một kênh tin tức điện tử hỗ trợ cho những người sử dụng có thể đọc tin tức trên thiết bị cầm tay (PDA). Hệ thống này sẽ trích lọc, thu gọn các trang báo cồng kềnh thành các trang tin gọn nhẹ, dễ đọc với sự loại bỏ các thông tin dư thừa, các banner quảng cáo, thu nhỏ các hình ảnh sao cho phù hợp với màn hình hạn chế của các thiết bị cầm tay (Hình 1). Hình 2 mô tả sơ đồ của hệ thống kênh tin tức điện tử cho các thiết bị cầm tay. Hệ thống được tích hợp vào phục vụ truy nhập Web của các thiết bị cầm tay, cung cấp dịch vụ đọc tin tức PDA. Mỗi khi người dùng cuối sử dụng dịch vụ này, hệ thống căn cứ vào các khuôn mẫu đã được nhận biết về mỗi báo điện tử để trích chọn chỉ nội dung tin tức cần thiết cho người dùng. Cách làm như vậy rất thích hợp với việc khai thác tin tức từ các thiết bị cầm tay. Hình 2. Sơ đồ hệ thống Kênh tin tức cho các thiết bị cầm tay Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 16 1.2.2. Mô tả các chức năng cơ bản của hệ thống Hệ thống cần thực hiện được các chức năng cơ bản là xác định các tin - mục tin trên các báo điện tử, xử lý trang tin và định dạng hiển thị tin trên các thiết bị cầm tay. Dưới đây là một số yêu cầu cơ bản của các chức năng này. a) Chức năng xác định các tin - mục tin trên các báo điện tử - Yêu cầu: xác định được các mục tin của các trang báo điện tử, trong các trang chi tiết, hệ thống phải xác định được các vùng tin cần trích xuất, vùng tin có thể loại bỏ. Các vùng tin tức sau khi trích xuất sẽ được định dạng lại cho phép