Luận văn Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM LUẬN VĂN THẠC SỸ Hà Nội – 2007 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM Ngành: Công nghệ thông tin. Mã số: 1.01.10 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HÀ QUANG THỤY Hà Nội - 2007 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 1 - Những lời đầu tiên Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo, tiến sỹ Hà Quang Thụy - người đã tận tình hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời xin cảm ơn tất cả những người thân yêu trong gia đình tôi cùng toàn thể bạn bè, những người đã luôn giúp đỡ và động viên tôi mỗi khi vấp phải những khó khăn, bế tắc. Cuối cùng, xin chân thành cảm ơn đồng nghiệp của tôi tại Trung tâm CNTT, NHNo&PTNT VN những người đã đem đến cho tôi những lời khuyên vô cùng bổ ích để giúp tháo gỡ những khó khăn, vướng mắc trong quá trình làm luận văn. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 2 - LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 01 tháng 11 năm 2007 Nguyễn Thị Thu Hằng Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 3 - MỤC LỤC DANH MỤC CHỮ VIẾT TẮT ........................................................................................ 5 DANH MỤC HÌNH VẼ, BẢNG BIỂU ............................................................................ 6 MỞ ĐẦU .......................................................................................................................... 7 CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB ................................... 9 1.1. Khai phá dữ liệu Web ....................................................................................... 9 1.1.1. Giới thiệu về Khai phá dữ liệu .................................................................. 9 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin ........................................... 11 1.1.3. Đặc điểm của dữ liệu Web ...................................................................... 12 1.1.4. Các hướng tiếp cận khai phá dữ liệu Web .............................................. 13 1.1.5. Nhu cầu Phân cụm tài liệu Web .............................................................. 14 1.2. Mô hình tìm kiếm thông tin ............................................................................ 15 1.2.1. Giới thiệu ................................................................................................ 15 1.2.2. Quy trình tìm kiếm thông tin trong hệ thống .......................................... 15 1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm ........................................... 18 1.3. Kết luận chương 1 ........................................................................................... 19 CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB ................................................... 20 2.1. Một số nội dung cơ bản về thuật toán phân cụm tài liệu ................................ 20 2.2. Tiêu chuẩn đánh giá thuật toán phân cụm ...................................................... 22 2.3. Các đặc tính của các thuật toán phân cụm web .............................................. 24 2.3.1. Mô hình dữ liệu ....................................................................................... 24 2.3.2. Độ đo về sự tương tự .............................................................................. 27 2.3.3. Mô hình phân cụm .................................................................................. 29 2.4. Một số kỹ thuật Phân cụm Web điển hình ...................................................... 30 2.4.1. Phân cụm theo thứ bậc ............................................................................ 30 2.4.2. Phân cụm bằng cách phân mảnh ............................................................. 33 2.5. Các yêu cầu đối với các thuật toán phân cụm Web ........................................ 35 2.5.1. Tách các thông tin đặc trưng ................................................................... 35 2.5.2. Phân cụm chồng lặp ................................................................................ 36 2.5.3. Hiệu suất ................................................................................................. 36 2.5.4. Khả năng khử nhiễu ................................................................................ 36 2.5.5. Tính tăng ................................................................................................. 37 2.5.6. Việc biểu diễn kết quả ............................................................................ 37 2.6. Bài toán tách từ tự động tiếng Việt ................................................................. 37 2.6.1. Một số khó khăn trong phân cụm trang Web tiếng Việt ......................... 37 2.6.2. Tiếng và Từ trong tiếng Việt .................................................................. 39 2.6.3. Phương pháp tách từ tự động tiếng Việt fnTBL ..................................... 39 2.6.4. Phương pháp Longest Matching ............................................................. 43 2.6.5. Kết hợp giữa fnTBL và Longest Matching ............................................. 44 2.7. Kết luận chương 2 ........................................................................................... 44 CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT TOÁN CÂY PHÂN CỤM TÀI LIỆU ........................................................................................ 45 3.1. Giới thiệu về thuật toán phân cụm trang Web có tính tăng ............................ 45 3.2. Thuật toán phân cụm cây hậu tố ..................................................................... 46 3.2.1. Mô tả ....................................................................................................... 46 3.2.2. Thuật toán STC ....................................................................................... 47 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 4 - 3.3. Thuật toán phân cụm sử dụng cây phân cụm tài liệu ...................................... 51 3.3.1. Giới thiệu ................................................................................................ 51 3.3.2. Trích chọn đặc trưng và phân cụm tài liệu ............................................. 51 3.3.3. Cây phân cụm tài liệu –DC Tree ............................................................ 55 3.4. Kết luận chương 3 ........................................................................................... 60 CHƯƠNG 4 - PHẦN MỀM THỬ NGHIỆM VÀ KẾT QUẢ THỰC NGHIỆM ...... 61 4.1. Giới thiệu ........................................................................................................ 61 4.2. Thiết kế cơ sở dữ liệu ..................................................................................... 62 4.3. Chương trình thử nghiệm ................................................................................ 65 4.4. Kết quả thực nghiệm ....................................................................................... 66 4.5. Kết luận chương 4 ........................................................................................... 69 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 5 - DANH MỤC CHỮ VIẾT TẮT AHC: Phân cụm tích tụ theo thứ bậc (Agglomerative Hierarchical Clustering) CSDL: Cơ sở dữ liệu DF: tần suất xuất hiện tài liệu (Document Frequency) DC-tree: Cây phân cụm tài liệu (Document Clustering Tree) fnTBL: Học dựa trên sự biến đổi (Fast Transformation-based learning) FCM: Fuzzy C-means FCMdd: Fuzzy C-Medoids IR: Mô hình tìm kiếm thông tin (Information Retrieval) IDF: tần suất nghịch đảo tài liệu (inverse document frequency) KDD: Khai phá tri thức (Knowledge Discovery in Databases) STC: Phân cụm cây hậu tố (Suffix tree clustering) TF: tần suất xuất hiện (term frequency) UPGMA: (Unweighter Pair-Group Method using Arithmetic averages) Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 6 - DANH MỤC HÌNH VẼ, BẢNG BIỂU Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 7 - MỞ ĐẦU World Wide Web là một kho thông tin khổng lồ với tiềm năng được coi là không có giới hạn. Khai phá Web là vấn đề nghiên cứu thời sự trong thời gian gần đây, đã thu hút nhiều nhóm nhà khoa học trên thế giới tiến hành nghiên cứu, đề xuất các mô hình, phương pháp mới nhằm tạo ra các công cụ hiệu quả hỗ trợ người dùng trong việc tổng hợp thông tin và tìm kiếm tri thức từ tập hợp các trang Web khổng lồ trên Internet. Phân cụm tài liệu Web là một bài toán điển hình trong khai phá Web, nhằm phân hoạch tập văn bản thành các tập con có tính chất chung, trong đó bài toán phân cụm các trang Web là kết quả trả về từ máy tìm kiếm là rất hữu dụng [4-6, 8-15, 18, 19, 22, 24]. Như đã biết, tập hợp các trang Web đáp ứng một câu hỏi trả về từ máy tìm kiếm nói chung là rất lớn, vì vậy, thuật toán phân cụm văn bản ở đây cần có được một tính chất rất quan trọng là tính "tăng" theo nghĩa thuật toán phân cụm không phải thực hiện chỉ trên toàn bộ tập dữ liệu mà có thể được thực hiện theo cách từ bộ phận dữ liệu tới toàn bộ dữ liệu [4, 6, 11, 14, 15, 24]. Điều đó cho phép thuật toán tiến hành ngay trong giai đoạn máy tìm kiếm đưa các trang web kết quả về. Luận văn tập trung khảo sát các phương pháp phân cụm trong Web có tính chất tăng và thực hiện một số thử nghiệm tích hợp các kết quả nghiên cứu nói trên vào một phần mềm tải trang Web theo dạng máy tìm kiếm. Đồng thời, luận văn triển khai một số bước đầu tiên trong việc áp dụng phân cụm cho các trang Web tiếng Việt. Luận văn xây dựng một phần mềm thử nghiệm và tiến hành các thử nghiệm phân cụm Web tiếng Việt. Ngoài Phần Mở đầu, Phần Kết luận và các Phụ lục, nội dung luận văn được chia thành 4 chương chính: Chương 1 – Khái quát về khai phá dữ liệu Web. Chương này giới thiệu những nội dung cơ bản nhất, cung cấp một cái nhìn khái quát về Khai phá dữ liệu Web. Đồng thời, luận văn cũng mô tả sơ bộ một hệ thống thông tin tìm kiếm và nhu cầu phân cụm áp dụng cho hệ thống này. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 8 - Chương 2 – Thuật toán phân cụm Web. Chương này trình bày một cách khái quát về các thuật toán phân cụm Web, những đặc trưng và yêu cầu đối với các thuật toán phân cụm Web. Những yêu cầu và độ đo áp dụng cho các thuật toán phân cụm Web cũng được trình bày trong chương này. Một số kiến thức cơ bản về tiếng Việt cũng được giới thiệu ở đây. Chương 3 – Thuật toán phân cụm cây hậu tố và thuật toán cây phân cụm tài liệu. Chương này đi sâu vào phân tích các thuật toán phân cụm Web có tính chất tăng. Luận văn tập trung vào hai thuật toán phân cụm Web có tính “tăng” là thuật toán STC và thuật toán phân cụm có sử dụng cấu trúc cây DC (DC-tree). Chương 4 – Phần mềm thử nghiệm và kết quả thực nghiệm. Chương này trình bày kết quả thực nghiệm phân cụm Web theo phần mềm thử nghiệm trên cơ sở thuật toán phân cụm DC-tree. Chương trình cài đặt thử nghiệm được viết trên ngôn ngữ lập trình C# trên nền tảng .Net Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ liệu. Phần mềm đã hoạt động, cho kết quả phân cụm, tuy nhiên, do thời gian hạn chế nên luận văn chưa tiến hành đánh giá kết quả phân cụm một cách chính thống. Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. Luận văn đã đạt một số kết quả khả quan bước đầu trong việc nghiên cứu và triển khai các thuật toán phân cụm Web có tính chất tăng, tuy nhiên, luận văn không tránh khỏi những sai sót. Rất mong được sự đóng góp ý kiến, nhận xét để tác giả có thể hoàn thiện được kết quả nghiên cứu. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 9 - CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB 1.1. Khai phá dữ liệu Web 1.1.1. Giới thiệu về Khai phá dữ liệu Khái niệm Khai phá dữ liệu (Data Mining) Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu. Thuật ngữ Data Mining ám chỉ việc tìm một tập nhỏ có giá trị từ một lượng lớn các dữ liệu thô. Có sự phân biệt giữa khái niệm "Khai phá dữ liệu" với khái niệm "Phát hiện tri thức" (Knowledge Discovery in Databases - KDD) mà theo đó, khai phá dữ liệu chỉ là một bước trong quá trình KDD. Quá trình KDD gồm một số bước sau: • Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết • Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại • Lựa chọn dữ liệu: Các dữ liệu có liên quan đến quá trình phân tích được lựa chọn từ cơ sở dữ liệu • Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý • Khai phá dữ liệu: Là một trong những bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để lựa chọn ra những mẫu dữ liệu. • Ước lượng mẫu: Quá trình đánh giá kết quả thông qua một độ đo nào đó • Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan cho người dùng. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 10 - Hình 1. Các bước trong KDD Các hướng tiếp cận và các kỹ thuật trong khai phá dữ liệu Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau: • Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. • Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản. Ví dụ: “50% những người mua máy tính thì cũng mua máy in”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v. • Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Người ta còn gọi phân lớp là học có giám sát (học có thầy). • Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Người ta còn gọi phân cụm là học không giám sát (học không thầy). • Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 11 - Ứng dụng của khai phá dữ liệu Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được sự quan tâm của rất nhiều nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể liệt kê ra đây một số ứng dụng điển hình [7,16]: • Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support) • Điều trị y học (medical treatment) • Text mining & Web mining • Tin-sinh (bio-informatics) • Tài chính và thị trường chứng khoán (finance & stock market) • Bảo hiểm (insurance) • Nhận dạng (pattern recognition) • .v.v. 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng như số lượng của các trang Web trên Internet thì vấn đề tìm kiếm thông tin đối với người sử dụng lại ngày càng khó khăn. Có thể nói nhu cầu tìm kiếm thông tin trên môt cơ sở dữ liệu phi cấu trúc (bao gồm dữ liệu văn bản) đã được phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy với Internet, con người đã làm quen với các trang Web cùng với vô vàn các thông tin. Trong những năm gần đây, Intrnet đã trở thành một trong những kênh về khoa học, thông tin kinh tế, thương mại và quảng cáo. Một trong những lý do cho sự phát triển này là giá cả thấp cần tiêu tốn khi công khai một trang Web trên Internet. So sánh với những dịch vụ khác như mua bản hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web "đòi" chi phí rẻ hơn rất nhiều mà lại được cập nhật nhanh chóng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thể nói không gian Web như là cuốn từ điển Bách khoa toàn thư. Thông tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Có thể nói Internet như một xã hội ảo, nó bao gồm các Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 12 - thông tin về mọi mặt của đời sống kinh tế, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh,... Tuy nhiên cùng với sự đa dạng và số lượng lớn thông tin như vậy đã nảy sinh vấn đề quá tải thông tin. Người ta không thể tìm tự kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung giống với yêu cầu của người tìm kiếm. Các tiện ích này quản lý dữ liệu trang Web như các đối tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy, đó là Yahoo, Google, Alvista, ... Mặt khác, giả sử chúng ta có các trang Web về các vấn đề Tin học, Thể thao, Kinh tể-Xã hội và Xây dựng...Căn cứ vào nội dung của các tài liệu mà khách hàng xem hoặc download về, sau khi phân lớp các yêu cầu như thế của khách hàng, chúng ta sẽ biết được khách hàng hay tập trung vào nội dung gì trên trang Web của chúng ta, mà từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm. Ngược lai, về phía khách hàng, sau khi được phục vụ phù hợp yêu cầu, khách hàng sẽ hướng sự quan tâm tới hệ thống của chúng ta hơn. Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài toán thời sự và cần được phát triển nghiên cứu. 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 [25, 26]. 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á dữ liệu, Xử lý ngôn ngữ tự nhiên và Công nghệ Web: Khai phá web = Khai phá dữ liệu + Xử lý ngôn ngữ tự nhiên + World Wide Web. 1.1.3. Đặc điểm của dữ liệu Web * Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ Khai phá 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. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 13 - * 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.1.4. Các hướng tiếp cận khai phá dữ liệu Web Như đã phân tích về đặc điểm và nội dung các siêu văn bản ở trên, từ đó khai phá dữ liệu Web cũng sẽ tập trung vào các thành phần có trong trang Web. Đó chính là: 1. Khai phá nội dun