Tài liệu Xây dựng ứng dụng tự động trích rút thông tin tỉnh quảng ngãi

i MỤC LỤC TÓM TẮT LUẬN VĂN DANH MỤC CÁC CHỮ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ MỞ ĐẦU............. ............................................................................................. 1 Chương 1 – CƠ SỞ LÝ THUYẾT ................................................................. 3 1.1. Tổng quan về khai phá dữ liệu ................................................................ 3 1.1.1. Giới thiệu ...................................................................................... 3 1.1.2. Các dạng dữ liệu ........................................................................... 5 1.1.3. Các bài toán thông dụng trong khai phá dữ liệu ........................... 8 1.1.4. Ứng dụng của khai phá dữ liệu ..................................................... 8 1.2. Khai phá dữ liệu Web .............................................................................. 9 1.2.1. Khái niệm ...................................................................................... 9 1.2.2. Đặc điểm của khai phá Web ....................................................... 10 1.2.3. Phân loại khai phá Web .............................................................. 11 1.2.4. Hướng khai phá Web của luận văn ............................................. 12 1.3. Thu thập thông tin trên Web.................................................................. 12 1.3.1. Giới thiệu tổng quan về thu thập thông tin trên Web ................. 12 1.3.2. Quá trình thu thập thông tin trên Web ........................................ 12 1.3.3. Các kỹ thuật Crawling và Indexing ............................................ 14 1.4. Công cụ hỗ trợ trích rút thông tin .......................................................... 16 1.4.1. Tổng quan XPath ........................................................................ 16 1.4.2. Cú pháp và ngữ nghĩa ................................................................. 17 1.5. Khảo sát một số ứng dụng tổng hợp tin tự động ................................... 22 1.5.1. news.skydoor.net ........................................................................ 22 1.5.2. news.google.com.vn ................................................................... 23 1.5.3. www.baomoi.com ....................................................................... 23 1.6. Kết chương ............................................................................................ 24 ii Chương 2 - GIẢI PHÁP HỆ THỐNG TRÍCH RÚT THÔNG TIN TỰ ĐỘNG ........................................................................................ 25 2.1. Đặt vấn đề .............................................................................................. 25 2.2. Mô tả bài toán ........................................................................................ 25 2.3. Giải pháp hệ thống trích rút thông tin tự động ...................................... 26 2.4. Thành phần tự động lấy dữ liệu ............................................................. 27 2.5. Thành phần bóc tách dữ liệu ................................................................. 32 2.5.1. Tổng quan về xử lý, bóc tách nội dung trang web ..................... 32 2.5.2. Các phương pháp xử lý, bóc tách nội dung trang web ............... 33 2.5.3. Đề xuất phương pháp bóc tách dữ liệu của luận văn .................. 38 2.6. Thiết kế chức năng quản lý ................................................................... 41 2.6.1. Chức năng quản trị, xuất bản thông tin....................................... 41 2.6.2. Chức năng người dùng................................................................ 43 2.7. Kết chương ............................................................................................ 44 Chương 3 – XÂY DỰNG VÀ THỬ NGHIỆM HỆ THỐNG .................... 45 3.1. Thiết kế cơ sở dữ liệu ............................................................................ 45 3.1.1. Mô hình quan hệ cơ sở dữ liệu ................................................... 45 3.1.2. Thiết kế cơ sở dữ liệu ................................................................. 46 3.2. Công cụ và môi trường lập trình ........................................................... 49 3.3. Thử nghiệm hệ thống............................................................................. 49 3.3.1. Kết quả từ trang baomoi.com ..................................................... 51 3.3.2. Kết quả từ trang news.skydoor.net/ ............................................ 54 3.4. Đánh giá kết quả .................................................................................... 56 3.4.1. Số liệu thống kê kết quả thử nghiệm .......................................... 56 3.4.2. Đánh giá kết quả thử nghiệm hệ thống ....................................... 56 3.5. Kết chương ............................................................................................ 56 KẾT LUẬN DANH MỤC TÀI LIỆU THAM KHẢO QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao) PHỤ LỤC iii XÂY DỰNG ỨNG DỤNG TỰ ĐỘNG TRÍCH RÚT THÔNG TIN TỈNH QUẢNG NGÃI Học viên: Trần Duy Linh. Chuyên ngành: Khoa học máy tính Mã số: 60.48.01. Khóa: 31. Trường Đại học Bách khoa - ĐHĐN Tóm tắt - Hiện nay, ở nước ta báo điện tử phát triển khá mạnh mẽ; bên cạnh đó các Bộ, ngành trung ương và các tỉnh thành trên cả nước đều có Cổng thông tin điện tử để cung cấp thông tin cho tổ chức và người dân một cách nhanh chóng, kịp thời. Tuy nhiên với sự phát triển ấy đã làm cho công tác quản lý Nhà nước về báo điện tử gặp nhiều khó khăn đối với cơ quan quản lý báo chí tại địa phương. - Xuất phát từ yêu cầu trên, đề tài: “Xây dựng ứng dụng tự động trích rút thông tin tỉnh Quảng Ngãi” thực hiện việc trích rút thông tin tự động trên các trang thông tin điện tử có bài viết liên quan về tỉnh Quảng Ngãi, nhằm cung cấp thông tin đến các cấp chính quyền địa phương để nắm bắt thông tin và có hướng giải quyết kịp thời những vấn đề nóng. Đề tài đã tập trung nghiên cứu lý thuyết về khai phá dữ liệu Web, các giải pháp, kỹ thuật trích rút thông tin tự động từ Web từ đó xây dựng ứng dụng và thử nghiệm hệ thống. - Kết quả thử nghiệm cho thấy Hệ thống đã trích rút được các thông tin có liên quan về tỉnh Quảng Ngãi trên báo điện tử một cách chính xác khi cấu hình các kênh tin trong hệ thống. Với kết quả đạt được, trong thời gian đến nếu có thời gian và điều kiện sẽ tiếp tục phát triển hoàn thiện để đưa ứng dụng vào sử dụng tại đơn vị. Từ khóa - tự động trích rút thông tin; khai thác thông tin tự động; trích rút trang web; trích rút thông tin Quảng Ngãi. BUILDING AN APPLICATION AUTOMATICALLY EXTRACTING INFORMATION IN QUANG NGAI PROVINCE Abstract - Nowsaday, e-journals have been developing quite significantly in our home country; in addition, ministries, central agencies and provinces across the country all have Web portals to quickly provide accurate information to organizations and citizens. However, that rapiddevelopment has also confronted local journalism management agencies with many difficulties in ensuring that online newspapers are complying with the state legislations on journalism. - Due to that fact, the project of "building an application automaticallyextracting information in Quang Ngai Province" is aimed atautomatically extracting information from various websites with all online articles related to Quang Ngai Province in order to keepthe local authorities updated to the latest issues and as a result, they will be able to provide quick responses or solutions if needed. The projecthas been based on the theory of Web data mining, solutions and techniques to automaticallyextract information from Websitesso as to develop and test the application. - The test results show that the system has successfully extracted information from diffirentonline newspapers when configuring the news channels in the system. Due to the above results, if time and conditions are met, it is hoped that the application will continue to be developed and then, appliedin the next time. Key words - Automatically extract information; Automatical Information Extraction, Extract website; Extract information Quang Ngai. iv DANH MỤC CÁC CHỮ VIẾT TẮT STT Chữ viết tắt Giải thích 1 DOM 2 HTML 3 URL 4 WWW World Wide Web: Hệ thống trang web trên Internet 5 CSDL Cơ sở dữ liệu 6 RSS 7 XML 8 XHTML Document Object Model: Mô hình đối tượng tài liệu HyperText Markup Language: Ngôn ngữ đánh dấu siêu văn bản Uniform Resource Locator: Tham chiếu đến (địa chỉ) tài nguyên trên Internet Really Simple Syndication: là một tiêu chuẩn định dạng tài liệu dựa trên XML eXtensible Markup Language: gọi là ngôn ngữ đánh dấu mở rộng Extensible HyperText Markup Language: Ngôn ngữ đánh dấu siêu văn bản mở rộng v DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 1.1 Một số cú pháp của XPath 19 3.1 Bảng dữ liệu tin tức 46 3.2 Bảng dữ liệu chuyên mục (nhóm tin) 46 3.3 Bảng dữ liệu nguồn tin 47 3.4 Bảng dữ liệu người dùng 47 3.5 Bảng dữ liệu thành viên 48 3.6 Bảng dữ liệu vai trò 48 3.7 Bảng dữ liệu phân quyền 49 3.8 Bảng dữ liệu thứ tự bài báo 49 3.9 Cấu hình và yêu cầu của các máy thử nghiệm 50 3.10 3.11 3.12 Kết quả trích rút thông tin trên trang baomoi.com Kết quả trích rút thông tin trên trang news.skydoor.net Kết quả thử nghiệm hệ thống trên các website khác nhau 52 54 56 vi DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Phân loại khai phá Web 11 1.2 Các bước thu thập thông tin trên trang web 14 2.1 Mô hình hệ thống trích rút thông tin tự động 27 2.2 Thuật toán thu thập dữ liệu từ các URL cho trước 28 2.3 Thuật toán tìm kiếm ưu tiên theo chiều rộng 30 2.4 Thuật toán tìm kiếm ưu tiên theo chiều sâu 31 2.5 2.6 2.7 Nội dung thông tin cần được xử lý phục vụ mục đích bài toán Kết quả loại bỏ thẻ HTML Kết quả bóc tách nội dung chính bằng cách so sánh khung mẫu 33 34 36 2.8 Cây DOM đơn giản minh họa cho đoạn mã HTML 39 2.9 Thuật toán bóc tách dữ liệu 40 2.10 Thuật toán quản trị, xuất bản thông tin 42 2.11 Thuật toán chức năng người dùng 43 3.1 Mô hình quan hệ cơ sở dữ liệu 45 1 MỞ ĐẦU 1. Lý do lựa chọn đề tài Hiện nay, ở nước ta báo điện tử phát triển khá mạnh mẽ, các Bộ, ngành trung ương và các tỉnh thành trên cả nước đều có Cổng thông tin điện tử để cung cấp thông tin cho tổ chức và người dân một cách nhanh chóng, kịp thời. Báo điện tử ra đời sau những loại hình báo chí khác nhưng đã nhanh chóng phát triển về số lượng cũng như chất lượng; tuy nhiên sự phát triển ấy đã làm cho công tác quản lý Nhà nước về báo chí gặp nhiều khó khăn. Ví dụ như nhiều báo điện tử chạy theo xu hướng giật gân, câu khách, xa rời tôn chỉ, mục đích, đối tượng, thông tin thiếu chuẩn xác. Báo điện tử giúp cho mọi người trên khắp thế giới tiếp cận tin tức nhanh chóng không phụ thuộc vào không gian và thời gian. Chính vì vậy, để công tác quản lý Nhà nước về báo chí ở tỉnh Quảng Ngãi hiệu quả, kịp thời chấn chỉnh những sai phạm, đồng thời cung cấp nhanh thông tin nội dung phản ánh của các tổ chức, cá nhân về văn hóa, kinh tế, chính trị... đến các cấp chính quyền địa phương cần xây dựng một ứng dụng thu thập thông tin tự động trên Web phản ánh về tỉnh Quảng Ngãi. Công tác quản lý báo chí hiện nay tại địa phương được Bộ Thông tin và Truyền thông, UBND tỉnh giao Sở Thông tin và Truyền thông thực hiện. Định kỳ 1 tháng Sở Thông tin và Truyền thông tổ chức họp báo 1 lần và 3 tháng Chủ tịch UBND tỉnh tổ chức họp báo 1 lần để đánh giá tình hình báo chí phản ánh về tỉnh Quảng Ngãi trên cơ sở đó chỉ đạo các cấp, ngành rà soát trả lời hoặc giải quyết trên cơ sở thông tin báo chí đề cập. Sở Thông tin và Truyền thông tổng hợp bằng hình thức tìm kiếm đọc các báo rồi chọn lọc ra các nội dung mà báo chí phản ánh, đề nghị đến các cấp chính quyền của tỉnh, từ đó báo cáo UBND tỉnh chỉ đạo các cơ quan liên quan giải quyết. Để hỗ trợ công tác tự động thu thập, trích rút thông tin trên Web phục vụ nhu cầu trên và được sự đồng ý hướng dẫn của Thầy PGS.TS Nguyễn Thanh Bình tôi chọn đề tài: "Xây dựng ứng dụng tự động trích rút thông tin tỉnh Quảng Ngãi" trên các báo điện tử viết về tỉnh Quảng Ngãi. 2. Mục đích nghiên cứu Nghiên cứu nắm vững và vận dụng tốt kỹ thuật khai phá dữ liệu Web, nghiên cứu các giải pháp trích rút thông tin từ Web, từ đó xây dựng ứng dụng 2 trích rút thông tin tự động trên báo điện tử viết về tỉnh Quảng Ngãi phục vụ công tác quản lý báo chí tại địa phương. 3. Đối tượng nghiên cứu Trong khuôn khổ của luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn nghiên cứu các vấn đề sau: - Nghiên cứu kỹ thuật khai phá dữ liệu Web. - Nghiên cứu giải pháp, kỹ thuật trích rút thông tin tự động từ Web. - Tìm hiểu công tác quản lý báo chí hiện nay theo Luật báo chí. - Tìm hiểu các ngôn ngữ lập trình Web và cơ sở dữ liệu. 4. Phương pháp nghiên cứu của đề tài Về lý thuyết, tập trung tìm hiểu lý thuyết về khai phá dữ liệu Web; tìm hiểu cơ chế hoạt động của các hệ thống tìm kiếm, thu thập thông tin; ứng dụng các công cụ để xây dựng hệ thống thu thập thông tin như: RSS, Xpath... Về nghiên cứu thực nghiệm, dựa trên lý thuyết đã nghiên cứu, tiến hành xây dựng hệ thống thu thập thông tin từ các kênh tin cấu hình trước; thử nghiệm trên máy tính có kết nối Internet để kiểm thử một số mô đun. 5. Ý nghĩa khoa học và thực tiễn của đề tài - Ý nghĩa khoa học: + Nắm vững và vận dụng tốt kỹ thuật khai phá dữ liệu Web. + Nắm vững và vận dụng tốt giải pháp trích rút thông tin tự động. + Ứng dụng kết quả nghiên cứu vào thực tiễn. - Ý nghĩa thực tiễn: Ứng dụng kết quả nghiên cứu vào việc hỗ trợ quản lý thông tin báo chí tại địa phương. Ngoài ra, hệ thống còn cung cấp thông tin tổng hợp nhanh chóng những nội dung phản ánh về văn hóa, kinh tế, chính trị...trên địa bàn tỉnh Quảng Ngãi đến các cấp lãnh đạo của tỉnh. 6. Cấu trúc của luận văn Luận văn được tổ chức thành 3 chương chính: - Chương 1: Trình bày những nghiên cứu lý thuyết về khai phá dữ liệu, thu thập thông tin từ Internet. - Chương 2: Trình bày giải pháp trích rút thông tin. - Chương 3: Trình bày cài đặt và thử nghiệm chương trình. 3 Chương 1 – CƠ SỞ LÝ THUYẾT Trong chương này trình bày một số khái niệm, định nghĩa liên quan đến khai phá dữ liệu; các mô hình, các giai đoạn của quá trình khai phá dữ liệu; các dạng dữ liệu liên quan; các bài toán thông dụng và phạm vi ứng dụng của khai phá dữ liệu. Tiếp theo là giới thiệu về các quá trình thu thập thông tin, các kỹ thuật thu thập thông tin trên Web. Cuối cùng là giới thiệu một số phần mềm tổng hợp thông tin tự động hiện nay. 1.1. Tổng quan về khai phá dữ liệu 1.1.1. Giới thiệu Trong thời đại ngày nay, với sự phát triển vượt bậc của công nghệ thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hằng ngày. Từ khối dữ liệu này, các kỹ thuật trong khai phá dữ liệu và học máy có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. Tom Mitchell [4] đã đưa ra định nghĩa của khai phá dữ liệu như sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những quy tắc và cải thiện những quyết định trong tương lai”. Với một cách tiếp cận ứng dụng hơn, Fayyad [5] đã phát biểu: “Khai phá dữ liệu, thường được xem là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng các quy luật, ràng buộc, quy tắc trong cơ sở dữ liệu”. Tóm lại, khai phá dữ liệu [1] là một bước trong quá trình phát hiện tri thức trong cơ sở dữ liệu, thi hành một thuật toán khai phá dữ liệu để tìm ra các mẫu từ dữ liệu theo khuôn dạng thích hợp. Mô hình khai phá dữ liệu bao gồm 5 giai đoạn chính: - Tìm hiểu nghiệp vụ và dữ liệu. - Chuẩn bị dữ liệu. - Mô hình hoá dữ liệu. - Hậu xử lý và đánh giá mô hình. - Triển khai tri thức. 4 Quá trình này có thể được lặp lại nhiều lần hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình khai phá dữ liệu là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực khai phá dữ liệu. Trong giai đoạn đầu tiên, tìm hiểu nghiệp vụ dữ liệu, nhà tư vấn nghiên cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm các tri thức cấu trúc về hệ thống và tri thức, các nguồn dữ liệu hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực thể dữ liệu. Việc nghiên cứu này được thực hiện qua việc tiếp xúc giữa nhà tư vấn và người dùng. Khác với phương pháp giải quyết vấn đề truyền thống khi bài toán được xác định chính xác ở bước đầu tiên, nhà tư vấn tìm hiểu các yêu cầu sơ khởi của người dùng và đề nghị các bài toán tiềm năng có thể giải quyết với nguồn dữ liệu hiện hữu. Tập các bài toán tiềm năng được tinh chỉnh và làm hẹp lại trong các giai đoạn sau. Các nguồn và đặc tả dữ liệu có liên quan đến tập các bài toán tiềm năng cũng được xác định. Giai đoạn chuẩn bị dữ liệu sử dụng các kỹ thuật tiền xử lý làm biến đổi và cải thiện chất lượng dữ liệu để thích hợp với những yêu cầu của các giải thuật học. Phần lớn các giải thuật khai phá dữ liệu hiện nay chỉ làm việc trên một tập dữ liệu đơn và phẳng, do đó dữ liệu phải được trích xuất và biến đổi từ các dạng cơ sơ dữ liệu phân bố, quan hệ hay hướng đối tượng sang dạng cơ sở dữ liệu quan hệ đơn giản với một bảng dữ liệu. Các giải thuật tiền xử lý tiêu biểu bao gồm: (a) Xử lý dữ liệu bị thiếu/mất: các dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp. (b) Khử sự trùng lặp: các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ đi. Kỹ thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. (c) Giảm nhiễu: nhiễu và các đối tượng tách rời (outlier) khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. (d) Chuẩn hóa: miền giá trị của dữ liệu sẽ được chuẩn hóa. (e) Rời rạc hóa: các dữ liệu số sẽ được biến đổi ra các giá trị rời rạc. (f) Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có. (g) Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt. 5 Các bài toán được giải quyết trong giai đoạn mô hình hóa dữ liệu. Các giải thuật học sử dụng các dữ liệu đã được tiền xử lý trong giai đoạn hai để tìm kiếm các quy tắc ẩn và chưa biết. Công việc quan trọng nhất trong giai đoạn này là lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Các bài toán được phân loại vào một trong những nhóm bài toán chính trong khai phá dữ liệu dựa trên đặc tả của chúng. Các mô hình kết quả của giai đoạn ba sẽ được hậu xử lý và đánh giá trong giai đoạn (d). Dựa trên các đánh giá của người dùng sau khi kiểm tra trên các tập thử, các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần. Chỉ các mô hình đạt được mức yêu cầu cơ bản của người dùng mới đưa ra triển khai trong thực tế. Trong giai đoạn này, các kết quả được biến đổi từ dạng học thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng. Trong giai đoạn cuối, triển khai tri thức, các mô hình được đưa vào những hệ thống thông tin thực tế dưới dạng các module hỗ trợ việc đưa ra quyết định. Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình khai phá dữ liệu là rất quan trọng cho việc nghiên cứu trong khai phá dữ liệu. Một giải thuật trong khai phá dữ liệu không thể được phát triển độc lập, không quan tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục tiêu cụ thể. Do đó, sự hiểu biết bối cảnh vận dụng là rất cần thiết. Thêm vào đó, các kỹ thuật được sử dụng trong các giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật sử dụng trong các giai đoạn tiếp theo. 1.1.2. Các dạng dữ liệu 1.1.2.1. Full text Dữ liệu dạng Full text là một dạng dữ liệu phi cấu trúc với thông tin chỉ gồm các tài liệu dạng văn bản. Mỗi tài liệu chứa thông tin về một vấn đề nào đó thể hiện qua nội dung của tất cả các từ cấu thành tài liệu đó. Ý nghĩa của mỗi từ trong tài liệu không cố định mà tùy thuộc vào từng ngữ cảnh khác nhau sẽ mang ý nghĩa khác nhau. Các từ trong tài liệu được liên kết với nhau theo một ngôn ngữ nào đó. Trong các dữ liệu hiện nay thì văn bản là một trong những dữ liệu phổ biến nhất, nó có mặt khắp mọi nơi và chúng ta thường xuyên bắt gặp. Do đó các bài toán về xử lý văn bản đã được đặt ra khá lâu và hiện nay vẫn là một trong 6 những vấn đề quan trọng trong khai phá dữ liệu văn bản. Có những bài toán đáng chú ý như tìm kiếm văn bản, phân loại văn bản, phân cụm văn bản hoặc dẫn đường văn bản. Cơ sở dữ liệu Full text là một dạng cơ sở dữ liệu phi cấu trúc mà dữ liệu bao gồm các tài liệu và thuộc tính của tài liệu. Cơ sở dữ liệu Full text thường được tổ chức như một tổ hợp của hai thành phần: một cơ sở dữ liệu có cấu trúc thông thường (chứa đặc điểm của các tài liệu) và các tài liệu. 1.1.2.2. Hypertext Theo từ điển của Đại Học Oxford (Oxford English Dictionary Additions Series) thì Hypertext được định nghĩa như sau: Đó là loại văn bản không phải đọc theo dạng liên tục đơn, nó có thể được đọc theo các thứ tự khác nhau, đặc biệt là văn bản và ảnh đồ họa (Graphic) là các dạng có mối liên kết với nhau theo cách mà người đọc có thể không cần đọc một cách liên tục. Ví dụ khi đọc một cuốn sách người đọc không phải đọc lần lượt từng trang từ đầu đến cuối mà có thể nhảy cóc đến các đoạn sau để tham khảo về các vấn đề họ quan tâm. Như vậy, văn bản Hypertext bao gồm dạng chữ viết không liên tục, chúng được phân nhánh và cho phép người đọc có thể chọn cách đọc theo ý muốn của mình. Hiểu theo nghĩa thông thường thì Hypertext là một tập các trang chữ viết được kết nối với nhau bởi các liên kết và cho phép người đọc có thể đọc theo các cách khác nhau. Như ta đã làm quen nhiều với các trang định dạng HTML, trong các trang có những liên kết trỏ tới từng phần khác nhau của trang đó hoặc trỏ tới trang khác và người đọc sẽ đọc văn bản dựa vào những liên kết đó. Bên cạnh đó, Hypertext cũng là một dạng văn bản đặc biệt nên cũng có thể bao gồm các chữ viết liên tục (là dạng phổ biến nhất của chữ viết). Do không bị hạn chế bởi tính liên tục trong Hypertext, chúng ta có thể tạo ra các dạng trình bày mới, do đó tài liệu sẽ phản ánh tốt hơn nội dung muốn diễn đạt. Hơn nữa người đọc có thể chọn cho mình một cách đọc phù hợp chẳng hạn như đi sâu vào một vấn đề mà họ quan tâm. Sáng kiến tạo ra một tập các văn bản cùng với các con trỏ tới các văn bản khác để liên kết một tập các văn bản có mối quan hệ với nhau là một cách thực sự hay và hữu ích để tổ chức thông tin. Với người viết, cách này cho phép họ có thể thoải mái loại bỏ những băn khoăn về thứ tự 7 trình bày mà có thể tổ chức vấn đề thành những phần nhỏ rồi sử dụng kết nối để chỉ ra mối liên hệ giữa các phần nhỏ đó với nhau. Với người đọc, cách này cho phép họ có thể đi tắt trên mạng thông tin và quyết định phần thông tin nào có liên quan đến vấn đề mà họ quan tâm để tiếp tục tìm hiểu. So sánh với cách đọc tuyến tính tức là đọc lần lượt thì Hypertext đã cung cấp cho chúng ta một giao diện để có thể tiếp xúc với nội dung thông tin hiệu quả hơn rất nhiều. Theo khía cạnh của các thuật toán học máy thì Hypertext đã cung cấp cho chúng ta cơ hội nhìn ra ngoài phạm vi một tài liệu để đánh giá nó, nghĩa là có tính cả đến các tài liệu có liên kết với nó. Tất nhiên không phải tất cả các tài liệu có liên kết đến nó đều có ích cho việc đánh giá, đặc biệt là khi các siêu liên kết có thể chỉ đến nhiều loại các tài liệu khác nhau. Có hai khái niệm về Hypertext cần quan tâm: Hypertext Document (tài liệu siêu văn bản): là một tài liệu văn bản đơn trong hệ thống siêu văn bản. Nếu tưởng tượng hệ thống siêu văn bản là một đồ thị thì các tài liệu tương ứng các nút. Hypertext Link (liên kết siêu văn bản): là một tham chiếu để nối một tài liệu Hypertext này với một tài liệu Hypertext khác. Các siêu liên kết đóng vai trò quan trọng như những đường nối trong đồ thị nói trên. Hypertext là loại dữ liệu phổ biến hiện nay và cũng là loại dữ liệu có nhu cầu tìm kiếm rất lớn. Nó là dữ liệu phổ biến trên mạng thông tin Internet, cơ sở dữ liệu Hypertext với văn bản dạng “nửa cấu trúc” do xuất hiện thêm các “thẻ ”: Thẻ cấu trúc (tiêu đề, mở đầu, nội dung), thẻ nhấn trình bày chữ (đậm, nghiêng,..). Nhờ các thẻ này mà chúng ta có thêm một tiêu chuẩn (so với tài liệu Full text) để có thể tìm kiếm và phân loại chúng. Dựa vào các thẻ đã quy định trước, chúng ta có thể phân thành các độ ưu tiên khác nhau cho các từ khóa nếu chúng xuất hiện ở những vị trí khác nhau. Ví dụ khi tìm kiếm các tài liệu có nội dung liên quan đến “Quảng Ngãi ” thì chúng ta đưa từ khóa tìm kiếm là “Quảng Ngãi” và các tài liệu có từ khóa “Quảng Ngãi” đứng ở tiêu đề thì sẽ gần với yêu cầu tìm kiếm hơn. 8 1.1.3. Các bài toán thông dụng trong khai phá dữ liệu 1.1.3.1. Phân lớp (Classification) Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ lọc ra bộ phân loại (classifier) dùng để phân các dữ liệu mới vào một trong những lớp (còn gọi là loại) đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu phân loại. 1.1.3.2. Dự đoán (Prediction) Với mô hình học tương tự như bài toán phân loại, lớp bài toán dự đoán (Prediction) sẽ lọc ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán. Bài toán tiêu biểu trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh. 1.1.3.3. Tìm luật liên kết (Association Rule) Các giải thuật tìm luật liên kết (Association Rule) là tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị. 1.1.3.4. Phân cụm (Clustering) Các kỹ thuật phân cụm (Clustering) sẽ nhóm các đối tượng dữ liệu có tính chất giống nhau vào cùng một nhóm. Có nhiều cách tiếp cận với những mục tiêu khác nhau trong phân loại. Các kỹ thuật trong bài toán này thường được vận dụng trong vấn đề phân hoạch dữ liệu tiếp thị hay khảo sát sơ bộ các dữ liệu. 1.1.4. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tùy theo bản chất của từng lĩnh vực, việc vận dụng khai phá dữ liệu có những cách tiếp cận khác nhau. Khai phá dữ liệu cũng được vận dụng hiệu quả để giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao như tìm kiếm mỏ dầu từ ảnh viễn thám, xác định các vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất… Các bài toán này đã được giải quyết từ khá lâu bằng các kỹ thuật nhận dạng hay xác suất nhưng được giải quyết với yêu cầu cao hơn bởi các kỹ thuật của khai phá dữ liệu. Phân nhóm 9 và dự đoán là những công cụ rất cần thiết cho việc quy hoạch và phát triển các hệ thống quản lý và sản xuất trong thực tế. Các kỹ thuật khai phá dữ liệu đã được áp dụng thành công trong việc dự đoán tải sử dụng điện năng cho các công ty cung cấp điện, lưu lượng viễn thông cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm các khách hàng tiềm năng… Ngoài ra, khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như phát hiện tội phạm hay tăng cường an ninh xã hội. Việc vận dụng thành công đã mang lại những hiệu quả thiết thực cho các hoạt động diễn ra hàng ngày trong đời sống. 1.2. Khai phá dữ liệu Web Ngày nay, World Wide Web đã trở thành một kho tài nguyên dữ liệu khổng lồ về mọi lĩnh vực; kho tài nguyên dữ liệu này không ngừng tăng trưởng với tốc độ cao. Kho tài nguyên dữ liệu Web tiềm ẩn nhiều thông tin quý giá với hoạt động của cộng đồng nói chung và từng cá thể nói riêng với những mục đích khai thác khác nhau. Các hệ thống khai phá dữ liệu Web đã trở thành các công cụ làm cho tài nguyên Web thực sự phát huy hiệu quả tới cộng đồng và tới mỗi cá thể trong cộng đồng. Hoạt động nghiên cứu và triển khai về khai phá dữ liệu Web không ngừng được tăng trưởng. Khai phá dữ liệu Web đã trở thành một trong những nội dung được nhiều quan tâm nhất tại ACM SIGKDD (Conference on Knowledge Discovery and Data Mining) và các hội nghị khoa học quốc tế lớn khác. 1.2.1. Khái niệm Như vậy chúng ta có thể hiểu rằng, khai phá Web như là việc trích chọn ra các thành phần được quan tâm hay được đánh giá là có ích cùng các thông tin tiềm năng từ các tài nguyên hoặc các hoạt động liên quan tới World Wide Web. Một cách trực quan có thể quan niệm khai phá Web là sự kết hợp giữa khai phá văn bản với công nghệ Web. Hiện tại, phần nội dung điển hình nhất trong trang web là văn bản. Vì vậy, khai phá văn bản Web là một thành phần cơ bản của khai phá Web. Tuy nhiên, 10 với sự tiến bộ không ngừng của công nghệ Internet, nhu cầu về khai phá dữ liệu đối với các dữ liệu đa phương tiện khác như hình vẽ, tiếng nói, âm nhạc, phim,… đã không ngừng được phát triển cả về chiều rộng lẫn chiều sâu. 1.2.2. Đặc điểm của khai phá Web Các đặc điểm dưới đây cho thấy một số khó khăn thách thức cũng như thuận lợi đối với khai phá Web. 1.2.2.1. Khó khăn trong khai phá Web - Web dường như quá lớn để tổ chức thành một kho dữ liệu. - Độ phức tạp của trang web lớn hơn rất nhiều so với những tài liệu văn bản truyền thống khác. - Web là một nguồn tài nguyên thông tin có độ thay đổi cao. - Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng. - Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích. 1.2.2.2. Thuận lợi Do đặc điểm của Web, việc khai phá Web có một số thuận lợi sau: - Trang web được cấu trúc theo quy định của ngôn ngữ định dạng, chứa các thẻ thi hành cấu trúc các nội dung của trang web đó. Chính vì lý do đó, trang web được xem như là một loại dữ liệu bán cấu trúc. Tính bán cấu trúc của trang web tạo cho khai phá Web có được một số thuận lợi nhất định khi so sánh với khai phá văn bản. - Web chứa nội dung và có cả liên kết trỏ từ trang này đến trang khác. Các thông tin liên kết trang cung cấp một lượng thông tin giàu có về mối liên quan, chất lượng và cấu trúc của nội dung trang web. - Một máy chủ Web thường đăng ký một bản ghi đầu vào (web log entry) cho mọi lần truy cập trang web. Thực hiện phân tích các hồ sơ truy cập này có thể rút ra được những thống kê về xu hướng truy cập Web, cấu trúc Web và nhiều thông tin hữu ích khác. 11 1.2.3. Phân loại khai phá Web Người ta thường phân khai phá Web thành ba lĩnh vực chính: khai phá nội dung Web (Web content mining), khai phá cấu trúc Web (web structure mining) và khai phá sử dụng Web (web usage mining). KHAI PHÁ WEB Khai phá nội dung Web Khai phá nội dung trang web Khai phá cấu trúc Web Tối ưu kết quả trả về Khai phá sử dụng Web Khai phá các mẫu truy cập Phân tích các xu hướng cá nhân Hình 1.1. Phân loại khai phá Web 1.2.3.1. Khai phá nội dung Web (web content mining) Khai phá nội dung Web gồm hai phần: - Khai phá nội dung trang web: chỉ sử dụng các từ trong văn bản mà không tính đến các liên kết giữa các văn bản. Đây chính là khai phá dữ liệu văn bản (văn bản mining). - Tối ưu kết quả trả về từ các công cụ tìm kếm: sau khi đã tìm ra những trang web thoả mãn yêu cầu người dùng, cần phải sắp xếp kết quả theo thứ tự độ gần nhau với nội dung cần tìm kiếm. Đây cũng chính là khai phá nội dung trang web. 1.2.3.2. Khai phá cấu trúc Web (web structure mining) Khai phá cấu trúc Web là các quá trình xử lý, nhằm rút ra các tri thức từ cách tổ chức và liên kết giữa các tham chiếu của các trang web. Mỗi một trang có thể được liên kết đến nhiều trang. Các siêu liên kết thay đổi chứa đựng ngữ nghĩa chủ đề của trang. Một siêu liên kết trỏ tới một trang web khác có thể được xem như là một chứng thực của trang web đó. Do đó, nó rất có ích trong việc sử dụng những thông tin ngữ nghĩa để lấy được thông tin quan trọng thông qua phân tích liên kết giữa các trang web. 12 Mục tiêu của khai phá cấu trúc Web là để phát hiện thông tin cấu trúc về Web. Nếu như khai phá nội dung Web chủ yếu tập trung vào cấu trúc bên trong tài liệu thì khai phá cấu trúc Web cố gắng để phát hiện cấu trúc liên kết của các siêu liên kết ở mức trong của tài liệu. Dựa trên mô hình hình học của các siêu liên kết, khai phá cấu trúc Web sẽ phân loại các trang web, tạo ra thông tin như độ tương tự và mối quan hệ giữa các website khác nhau. 1.2.3.3. Khai phá sử dụng Web (web usage mining) - Phân tích các mẫu truy cập (general access partern tracking): Phân tích các Web log để khám phá ra các mẫu truy cập của người dùng trong trang web. - Phân tích các xu hướng cá nhân (customize usage tracking): Phân tích các mẩu truy cập của người dùng tại mỗi thời điểm để biết xu hướng truy cập trang web của từng đối tượng người dùng tại mỗi thời điểm khác nhau. 1.2.4. Hướng khai phá Web của luận văn Luận văn tập trung chủ yếu vào khai phá nội dung Web với mục đích khai thác kho dữ liệu Web của các nhà cung cấp nội dung (web publisher). Luận văn tiến hành các giai đoạn nghiên cứu và triển khai ứng dụng thử nghiệm trích rút tự động và xử lý bóc tách thành phần chính nội dung của trang web theo yêu cầu xác định trước. 1.3. Thu thập thông tin trên Web 1.3.1. Giới thiệu tổng quan về thu thập thông tin trên Web Thu thập thông tin (Information Retrieval - IR) trên Web là tập trung vào việc khám phá một cách tự động nguồn thông tin có giá trị trực tuyến. Nội dung Web có thể được tiếp cận theo 2 cách khác nhau: Tìm kiếm thông tin và khai phá dữ liệu trong cơ sở dữ liệu lớn. Có nhiều hình thức về thu thập, rút trích nội dung, thông tin trang web đã được nghiên cứu và phát triển. Chúng ta có một loạt khái niệm như Robot, Search, Web Crawler, Data Wrapper, Web Spider, Web Clipping, Semantic Web, Web Scraping ... 1.3.2. Quá trình thu thập thông tin trên Web Nắm bắt những đặc tính của người dùng Web là việc rất quan trọng đối với người thiết kế website. Thông qua việc khai phá lịch sử các mẫu truy xuất của người dùng Web, không chỉ thông tin về Web được sử dụng như thế nào mà 13 còn nhiều đặc tính khác như các hành vi của người dùng có thể được xác định. Sự điều hướng đường dẫn người dùng Web mang lại giá trị thông tin về mức độ quan tâm của người dùng đến các website đó. - Các kỹ thuật được sử dụng trong quá trình thu thập thông tin trên Web: + Luật kết hợp: Để tìm ra những Web thường được truy cập cùng nhau của người dùng, những lựa chọn cùng nhau của khách hàng trong thương mại điện tử. + Kỹ thuật phân cụm: Phân cụm người dùng dựa trên các mẫu duyệt để tìm ra sự liên quan giữa người dùng Web và các hành vi của họ. - Quá trình tìm kiếm và phân cụm tài liệu: Về cơ bản, quá trình phân cụm kết quả tìm kiếm sẽ diễn ra theo các bước: + Tìm kiếm trang web từ các website thoả mãn nội dung truy vấn. + Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL tương ứng. + Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang web thành các cụm, sao cho các trang trong cụm "tương tự" về nội dung với nhau hơn các trang ngoài cụm. - Tìm kiếm dữ liệu trên Web: Nhiệm vụ chủ yếu của giai đoạn này là dựa vào tập từ khoá tìm kiếm để tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt, URL... tương ứng với các trang đó. - Tiền xử lý dữ liệu: Quá trình làm sạch dữ liệu và chuyển dịch các tài liệu thành các dạng biểu diễn dữ liệu thích hợp. - Chuẩn hoá văn bản: Đây là giai đoạn chuyển hoá văn bản thô về dạng văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuận tiện, chính xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả xử lý. - Xoá bỏ từ dừng: Trong văn bản có những từ mang ít thông tin quan trọng trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất hiện với tần số lớn nhưng không quan trọng trong quá trình xử lý đều được loại bỏ. Theo một số nghiên cứu gần đây cho thấy việc loại bỏ các từ dừng có thể giảm bớt được khoảng 20 - 30% tổng số từ trong văn bản. 14 - Kết hợp các từ có cùng gốc: Hầu hết trong các ngôn ngữ đều có rất nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự nhau, do đó để giảm bớt số chiều trong biểu diễn văn bản, ta sẽ kết hợp với các từ có cùng gốc thành một từ. Ví dụ trong tiếng Anh từ user, users, used, using có cùng từ gốc và sẽ được quy về use. - Xây dựng từ điển: Việc xây dựng từ điển là một công việc rất quan trọng trong quá trình vector hoá văn bản, từ điển sẽ gồm các từ, cụm từ riêng biệt trong toàn bộ tập dữ liệu. Từ điển sẽ gồm một bảng các từ, chỉ số của nó trong từ điển và được sắp xếp theo thứ tự. - Tách từ, số hoá văn bản và biểu diễn tài liệu: tách từ là công việc hết sức quan trọng trong việc biểu diễn văn bản. Quá trình tách từ, vector hoá tài liệu là quá trình tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong từ điển. - Phân cụm tài liệu: Sau khi đã tìm kiếm, trích rút dữ liệu, tiền xử lý và biểu diễn văn bản chúng ta sử dụng kỹ thuật phân cụm để phân cụm tài liệu. Hình 1.2. Các bước thu thập thông tin trên trang web 1.3.3. Các kỹ thuật Crawling và Indexing Một Web thu thập thông tin là một chương trình máy tính có thể “duyệt web” một cách tự động và theo một phương thức nào đó được xác định trước [1]. Vì là một chương trình nên quá trình “duyệt web” của các Web thu thập thông tin không hoàn toàn giống với quá trình duyệt web của con người (Web thu thập thông tin phải sử dụng các phương thức dựa trên HTTP trực tiếp chứ