Các thành phần của web mining và các phương pháp luận

MỤC LỤC MỞ ĐẦU ............................................................................................................... 3 Mục đích thực tập chuyên ngành ............................................................... 3 Giới thiệu về đề tài thực tập chuyên ngành ............................................... 3 Yêu cầu của đề tài ..................................................................................... 4 CHƯƠNG I TỔNG QUAN VỀ WEB MINING...................................................... 5 Giới thiệu chung ......................................................................................... 5 Web mining ................................................................................................ 6 Tổng quan ........................................................................................... 6 Các thành phần của web mining và các phương pháp luận ............... 7 a. Khám phá thông tin (IR) ................................................................. 8 b. Trích rút, lựa chọn và tiền xử lý thông tin ....................................... 9 c. Tổng quát hoá ................................................................................. 10 d. Phân tích ........................................................................................ 10 3. Web content mining và Web structure mining ............................................ 11 Web content mining ............................................................................. 11 Web structure mining ........................................................................... 13 4. Web text mining .......................................................................................... 14 Text Classification ............................................................................... 14 Text Clustering .................................................................................... 14 Association analysis ........................................................................... 15 Trend Prediction .................................................................................. 15 CHƯƠNG II KHAI PHÁ DỮ LIỆU ....................................................................... 16 Tổng quan về khai phá dữ liệu .................................................................. 16 Khái niệm ............................................................................................ 16 Các bước của quá trình khai phá dữ liệu ............................................ 16 2. Nhiệm vụ chính của khai phá dữ liệu ........................................................ 18 3. Các phương pháp khai phá dữ liệu ........................................................... 19 4. Một số bài toán chính đối với nghiên cứu về khai phá dữ liệu .................. 21 CHƯƠNG III VĂN BẢN VÀ XỬ LÝ VĂN BẢN .................................................... 22 Khái niệm .................................................................................................... 22 Phương pháp biểu diễn văn bản bằng mô hình không gian vector ............ 23 Mô hình Boolean ................................................................................. 23 Mô hình Tần suất ................................................................................ 23 a. Phương pháp dựa trên tần số thuật ngữ (TF – Term Frequency).. 23 b. Phương pháp dựa trên nghịch đảo tần số văn bản (IDF - Inverse Document Frequency) ........................................................... 24 c. Phương pháp TF x IDF ................................................................. 24 2.3 Phương pháp xử lý vector thưa ......................................................... 25 Các bài toán xử lý văn bản không có cấu trúc ........................................... 26 Bài toán phân loại văn bản ................................................................. 26 3.1.1 Giới thiệu .................................................................................. 26 Các phương pháp phân loại văn bản ...................................... 26 a. Decision Tree ...................................................................... 29 b. k-Nearest Neighbor ............................................................. 34 Bài toán lập nhóm văn bản ................................................................. 36 3.2.1 Giới thiệu .................................................................................. 36 Các phương pháp lập nhóm văn bản ...................................... 37 a. Thuật toán phân câp Bayesian............................................ 37 b. Thuật toán ghép nhóm theo độ tương tự............................. 39 c. Thuật toán K-means ........................................................... 40 CHƯƠNG IV XÂY DỰNG THỬ NGHIỆM ỨNG DỤNG WEB CLUSTERING...... 43 Bài toán đặt ra ............................................................................................ 43 Phương hướng giải quyết .......................................................................... 43 Web Crawler ........................................................................................ 43 a. Giới thiệu ........................................................................................ 43 b. Thứ tự Crawl các URLs .................................................................. 44 c. Một số vấn đề cần chú ý cho Web Crawler .................................... 44 d. Thuật toán sử dụng cho Web Crawler ............................................ 45 Áp dụng các thuật toán lập nhóm cho bộ dữ liệu thu được ................. 46 2.2.1 Các bước thực hiện để biểu diễn vector văn bản ...................... 46 a. Tách từ .................................................................................. 46 b. Loại bỏ Stopwords ................................................................. 47 c. Stemming ............................................................................... 47 d. Sắp xếp các keyword ............................................................. 47 e. Xây dựng bag-of-words ......................................................... 47 f. Biểu diễn từng file văn bản thành các vector .......................... 48 Áp dụng các thuật toán lập nhóm ............................................. 54 TÀI LIỆU THAM KHẢO ......................................................................................... 55 MỞ ĐẦU Mục đích thực tập chuyên ngành Sau 2 năm học chuyên ngành, chúng em đã được tiếp thu khá nhiều kiến thức nền tảng nhờ các thầy cô trong khoa Công nghệ thông tin (CNTT), tuy nhiên chúng em vẫn chưa thực sự đi sâu vào tiếp cận các công nghệ mới, các vấn đề trong ngành CNTT chi tiết và cụ thể. Vì vậy đợt thực tập chuyên ngành này là một dịp để chúng em có thể tìm hiểu một vấn đề cụ thể trong ngành CNTT. Đây cũng là bước mở đầu và cũng là bước tiếp cận để chúng em tiếp tục chuyển sang học giai đoạn chuyên ngành hẹp Công nghệ phần mềm. Giới thiệu về đề tài thực tập chuyên ngành Từ một thập kỷ trở lại đây, chúng ta đã được chứng kiến sự phát triển như vũ bão của những nguồn thông tin sẵn có trên World Wide Web (WWW). Ngày nay, các trình duyệt Web cho phép chúng ta dễ dàng truy nhập vào vô số nguồn dữ liệu văn bản và multimedia. Với hơn một tỷ trang web, việc đánh chỉ số bởi các search engine và tìm kiếm những thông tin cần thiết không còn là một việc dễ dàng. Lượng thông tin dồi dào to lớn đã làm nảy sinh nhu cầu phát triển các kỹ thuật khai phá tự động trên WWW, hay còn được gọi bởi một thuật ngữ là “Web mining”. Để có được những công cụ web thông minh, hạn chế sự can thiệp của con người, chúng ta cần phải tích hợp hay nhúng trí tuệ nhân tạo (artificial intelligence) vào các công cụ này. Sự cần thiết tạo ra các hệ thống thông minh phía server và phía client nhằm khai thác một cách có hiệu quả các tri thức trên Internet hay từ các trang Web cụ thể đã thu hút sự chú ý của những nhà nghiên cứu từ nhiều lĩnh vực khác nhau như truy hồi thông tin (information retrieval), khai phá tri thức (knowledge discovery), máy học (machine learning) và trí tuệ nhân tạo (AI). Tuy nhiên, bài toán phát triển các công cụ tự động để tìm kiếm, trích rút, lọc, hay lượng giá thông tin mà người sử dụng mong muốn từ dữ liệu web vốn không được gán nhãn lại phân tán, hỗn tạp vẫn còn đang trong giai đoạn trứng nước. Trong một tháng thực tập chuyên ngành ngắn ngủi, em chưa có đủ thời gian để tìm hiểu một cách sâu sắc về Web mining mà mới chỉ dừng lại ở giới thiệu tổng quan và cài đặt một ứng dụng nhằm minh hoạ các thuật toán đã tìm hiểu. Mong thầy và các bạn cho em những ý kiến quý báu để em có thể tiếp tục phát triển, hoàn thiện hơn đề tài này. Yêu cầu của đề tài Tìm hiểu chung về Web mining Tìm hiểu Web Text mining Xây dựng ứng dụng cho phép thu thập thông tin từ trên mạng Internet. Sau đó, áp dụng các thuật toán lập nhóm cho bộ dữ liệu vừa thu được. CHƯƠNG I TỔNG QUAN VỀ WEB MINING Với một khối lượng thông tin trực tuyến khổng lồ, World Wide Web đã trở thành một lĩnh vực phong phú, dồi dào cho các nghiên cứu về data mining. Có thể nói, những nghiên cứu về Web mining là sự tổng hợp của nhiều lĩnh vực nghiên cứu khác nhau như database, thu hồi thông tin (information retrieval), trí tuệ nhân tạo (AI), đặc biệt là sự góp mặt của máy học (machine learning) và xử lý ngôn ngữ tự nhiên. Tuy vậy, hãy còn có rất nhiều những nhầm lẫn, những mập mờ khi đem so sánh những kết quả nghiên cứu từ các quan điểm khác nhau. Giới thiệu chung Ngày nay, World Wide Web là một môi trường tương tác phổ dụng, được dùng để phổ cập thông tin. Những người sử dụng thông tin, khi tương tác với Web, thường gặp phải những vấn đề sau: a. Tìm kiếm những thông tin thích hợp : Con người sử dụng trình duyệt và các dịch vụ tìm kiếm khi họ muốn có được những thông tin đặc biệt nào đó trên Web. Muốn sử dụng dịch vụ tìm kiếm, người sử dụng chỉ cần đưa ra những câu truy vấn đơn giản. Dường như ngay lập tức, kết quả tìm kiếm được hiển thị thành danh sách các trang được sắp xếp dựa trên độ tương đồng với câu truy vấn. Tuy nhiên, các công cụ tìm kiếm ngày nay vẫn còn gặp phải một số những vấn đề nổi cộm. Thứ nhất, độ chính xác thấp do sự không thích hợp của nhiều kết quả tìm kiếm. Thứ hai, khả năng triệu hồi (recall) thấp do không đủ khả năng đánh chỉ số cho tất cả các thông tin có sẵn trên Web. b. Tạo tri thức mới từ những thông tin có sẵn trên Web : Có thể coi bài toán này là một bài toán con của bài toán trên. Trong khi bài toán trên xử lý các câu truy vấn (retrieval oriented) thì bài toán này lại xử lý dữ liệu, trong đó ta giả sử đã có sẵn một tập dữ liệu Web, cần phải trích ra những tri thức tiềm ẩn có ích từ tập dữ liệu này. c. Sự cá nhân hoá thông tin : Khi tương tác với Web, mỗi người lại có một cách biểu diễn thông tin riêng, tuỳ thuộc vào sở thích của họ. d. Nghiên cứu về người tiêu dùng và những người sử dụng riêng : Đây là bài toán giải quyết cho bài toán c ở trên. Bài toán này sẽ cho biết khách hàng làm gì và muốn gì. 2. Web mining 2.1 Tổng quan Web mining thực chất là việc sử dụng các kỹ thuật của Data mining nhằm tự động khai phá, trích dẫn thông tin từ các tài liệu và các dịch vụ Web. Hiện nay, nó đang là một lĩnh vực nghiên cứu rộng lớn, thu hút sự chú ý của nhiều lĩnh vực nghiên cứu khác nhau do sự phát triển ghê gớm của các nguồn thông tin trên Web cũng như thương mại điện tử. Web mining được phân thành những nhiệm vụ nhỏ sau: Tìm kiếm các nguồn tài nguyên : truy hồi các tài liệu Web mong muốn. Đây là quá trình truy hồi dữ liệu trực tuyến hoặc không trực tuyến từ các nguồn văn bản sẵn có trên Web. Các nguồn thông tin này có thể là các bản tin điện tử, các bức điện tín, nội dung văn bản từ các tài liệu HTML, thu được bằng cách loại bỏ các HTML tag… Lựa chọn và tiền xử lý thông tin : tự động lựa chọn và tiền xử lý các thông tin vừa nhận được từ các nguồn tài nguyên Web. Những chuyển đổi này có thể là loại bỏ các stop words, stemming… hoặc tiền xử lý để có những biểu diễn thích hợp, hay chuyển đổi sang mô hình quan hệ, dạng logic 1 (first order logic form). Tổng quát hoá : Tự động khai phá ra các mẫu tổng quát từ các Web site riêng biệt hoặc từ một nhóm các Web site. Để tổng quát hoá ra các mẫu, người ta thường sử dụng các kỹ thuật machine learning hoặc data mining. Trong quá trình khai phá thông tin và tri thức, con người đóng một vai trò cực kỳ quan trọng bởi Web là một môi trường tương tác. Phân tích hiệu lực và (hoặc) giải thích các mẫu vừa khai phá được. Nói một cách ngắn gọn, Web mining là một kỹ thuật dùng để khai phá và phân tích thông tin có ích từ dữ liệu Web. Web có hai loại dữ liệu chính: Web content data Web structure data Tương ứng với mỗi loại dữ liệu cần khai thác, người ta cũng chia ra các kỹ thuật Web mining thành : Web content mining Web structure mining Hình 1. Phân loại Web mining Web structure mining có thể được chia nhỏ thành: Khai phá cấu trúc ngoài (External Structure mining) : tập trung khai phá siêu liên kết giữa các trang Web. Khai phá cấu trúc trong (Internal Structure mining) : khai phá cấu trúc nội tại của trang Web. URL mining. Web content mining được chia thành: Text mining: bao gồm text file, HTML, document... Multimedia mining. Mặc dầu khai phá các dữ liệu multimedia có rất nhiều điều thú vị, hấp dẫn, nhưng text mining lại có một vai trò cực kỳ quan trọng, bởi lẽ hiện nay, văn bản là phương tiện thông tin chủ yếu trên Web. 2.2 Các thành phần của Web mining và các phương pháp luận Như đã nói ở trên Web mining có thể được chia thành bốn nhiệm vụ nhỏ: Khám phá thông tin (Information Retrieval hay Resource Discovery) Trích dẫn, lựa chọn và tiền xử lý thông tin (Information Selection/Extraction and preprocessing) Tổng quát hoá (Generalization) Analysis Khám phá thông tin (IR) Khám phá thông tin là giải quyết bài toán tự động nhận về tất cả các tài liệu liên quan, đồng thời hạn chế tối đa các tài liệu không có ích. Quá trình IR thường bao gồm biểu diễn tài liệu (document representation), đánh chỉ số (indexing) và tìm kiếm tài liệu. Về cơ bản, chỉ mục là nơi ghi lại các thuật ngữ. Mỗi khi cần tìm tài liệu liên qua đến thuật ngữ nào, ta sẽ tra cứu trong chỉ mục để biết được tất cả các tài liệu có chứa thuật ngữ này. Tuy nhiên, đánh chỉ mục các trang Web lại khá phức tạp. Với một số lượng khổng lồ các trang web có tính chất động và thường xuyên được cập nhật, các kỹ thuật đánh chỉ số dường như là điều không thể. Hiện nay, có bốn phương pháp đánh chỉ số cho các tài liệu trên web: manual indexing automatic indexing intelligent or agent - based indexing metadata - based indexing Search engine là chương trình được viết để truy vấn và nhận về các thông tin được lưu trữ trong các cơ sở dữ liệu (hoàn toàn có cấu trúc), các trang HTML (nửa cấu trúc) hay các văn bản text có trên web. Kiến trúc của một hệ IR Processor Documents Feedback Output Queries Input Với đầu vào là các tài liệu và truy vấn của người dùng, khối xử lý (processor) sẽ cho kết quả về các tài liệu thoả mãn truy vấn. Các kết quả này đôi khi được sử dụng làm thông tin phản hồi cho hệ IR nhằm có được các kết qủa tốt hơn trong các tình huống tương tự sau này. b. Trích rút, lựa chọn và tiền xử lý thông tin Khi các tài liệu được nhận về, nhiệm vụ tiếp theo là phải trích rút được tri thức và những thông tin yêu cầu khác mà không cần đến sự tương tác của con người. Trích rút thông tin (IE) có nhiệm vụ xác định các đoạn đặc trưng cấu thành nên nội dung ngữ nghĩa hạt nhân của tài liệu. Cho đến nay, các phương pháp IE đều ít nhiều liên quan đến việc viết các wrapper để ánh xạ các tài liệu sang một vài mô hình dữ liệu. Các hệ thống tích hợp thông tin hiện nay thường thao tác bằng cách dịch các site khác nhau thành các nguồn tri thức rồi trích rút thông tin từ chúng. Một phương pháp khác để trích rút thông tin từ các siêu văn bản (hypertext) là coi mỗi trang như một tập các câu hỏi chuẩn. Bài toán đặt ra là cần phải xác định được các đoạn văn bản trả lời cho một số câu hỏi xác định nào đó. Nói một cách khác, các khe hở sẽ được điền đầy bằng các đoạn văn bản trong tài liệu. Như vậy, mục tiêu của IE là trích rút những tri thức mới từ những tài liệu nhận được bằng cách lợi dụng cấu trúc của tài liệu và sự biểu diễn tài liệu trong khi các chuyên gia IR lại coi tài liệu là một tập các từ (bag of words) mà không hề chú ý tới cấu trúc của tài liệu. Vấn đề trở ngại chính đối với IE chính là kích thước và tính chất động của web. Vì vậy, các hệ thống IE thường chỉ trích rút thông tin từ một số site cụ thể và tập trung vào một số vùng xác định mà thôi. Để có thể trích rút được bất cứ loại tri thức nào từ các CSDL có kích thước trung bình, chúng ta cần có một hệ thống tiền xử lý mạnh mẽ. Khi người sử dụng yêu cầu một trang web, rất nhiều loại file khác nhau như hình ảnh, âm thanh, video, cgi, html được truy cập. Kết quả là, server log chứa rất nhiều mục dư thừa hoặc không thích hợp cho nhiệm vụ khai phá. Chính vì vậy, chúng cần phải được loại bỏ bằng quá trình tiền xử lý. Một trong những kỹ thuật tiền xử lý mà IE hay sử dụng là latent semantic indexing (LSI), nhằm biến đổi các vector tài liệu ban đầu sang không gian có số chiều nhỏ hơn bằng cách phân tích sự tương quan của các thuật ngữ trong tập các tài liệu. Một số kỹ thuật tiền xử lý khác nữa là “stop words”, “stemming”, cho phép giảm kích thước các đặc trưng đầu vào. c. Tổng quát hoá Trong giai đoạn này, các kỹ thuật máy học và nhận dạng mẫu thường được sử dụng để trích rút thông tin. Hầu hết các hệ thống máy học được triển khai trên web thường học nhu cầu của người sử dụng hơn là bản thân web. Khó khăn chính khi học về web là vấn đề gán nhãn. Dữ liệu trên web quả thực vô cùng phong phú, xong lại không được gán nhãn. Trong khi đó, rất nhiều kỹ thuật khai phá dữ liệu lại yêu cầu các mẫu đầu vào phải được gán nhãn dương (positive) hoặc âm (negative) tương ứng với một số khái niệm nào đó. Ví dụ, giả sử chúng ta có một tập lớn các trang web được gán nhãn dương hoặc âm của khái niệm homepage. Khi đó, việc tạo ra một trình phân loại để dự đoán một trang web có là homepage hay không sẽ rất dễ dàng. Nhưng thật không may, các trang web lại không được gán nhãn. Các kỹ thuật như lẫy mẫu không chắc chắn có thể giảm bớt lượng dữ liệu không được gán nhãn, nhưng lại không thể khử được bài toán này. Một cách tiếp cận để giải quyết bài toán gán nhãn là dựa trên cơ sở web có nhiều tập các tài liệu liên kết. Các kỹ thuật lập nhóm không yêu cầu đầu vào phải được gán nhãn, đồng thời chúng đã và đang được ứng dụng hết sức thành công cho tập lớn các tài liệu. Hơn nữa, Web chính là một mảnh đất màu mỡ phì nhiêu cho các nghiên cứu lập nhóm tài liệu. Khai phá các luật kết hợp (association rule mining) là một phần của giai đoạn này. Về cơ bản, luật kết hợp là những biểu thức có dạng X Þ Y trong đó X và Y là tập các mục (item). X Þ Y có nghĩa là bất cứ khi nào một giao tác T có chứa X thì T cũng có thể chứa Y. Xác suất hay độ tin cậy của luật được định nghĩa là phần trăm các giao tác có chứa Y khi đã chứa X trên tổng số các giao tác có chứa X. d. Phân tích (analysis) Phân tích là bài toán hướng dữ liệu với giả thiết đã có sẵn đầy đủ dữ liệu. Từ đó, những thông tin hữu ích tiềm ẩn có thể được trích rút và được phân tích. Con người đóng một vai trò cực kỳ quan trọng trong quá trình khai phá tri thức bởi web là một môi trường tương tác. Điều này đặc biệt quan trọng cho sự phê chuẩn và giải thích các mẫu được khai phá bởi khi các mẫu được khai phá, những người phân tích cần phải sử dụng những công cụ thích hợp để hiểu, trực quan hoá và giải thích các mẫu. 3. Web content mining và Web structure mining Web content mining Web content mining là quá trình khai phá những thông tin có ích từ nội dung / dữ liệu / tài liệu / dịch vụ web. Tài liệu Web có thể chứa một số loại dữ liệu sau: văn bản, hình ảnh, âm thanh, video, siêu dữ liệu và siêu liên kết. Một số là nửa cấu trúc như tài liệu HTML, hoặc là những dữ liệu có cấu trúc hơn như dữ liệu trong bảng các CSDL sinh ra từ các trang HTML. Tuy