Tài liệu WEB MINING với giải thuật SOM và ứng dụng cho máy tìm kiếm VINAHOO

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯ PHƯƠNG HẠNH WEB MINING với giải thuật SOM và ứng dụng cho máy tìm kiếm VINAHOO luËn v¨n th¹c sÜ CÔNG NGHỆ THÔNG TIN Hµ néi - 2005 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯ PHƯƠNG HẠNH WEB MINING với giải thuật SOM và ứng dụng cho máy tìm kiếm VINAHOO Mã số : 1.01.10 luËn v¨n th¹c sÜ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: TS. Hà Quang Thuỵ Hµ néi - 2005 Formatted: Dutch (Netherlands) Mở đầu .............................................................................................................. 53 Formatted: Dutch (Netherlands) Lời cảm ơn ........................................................................................................ 75 Các từ viết tắt .................................................................................................... 86 Chƣơng 1. 1.1 Phân cụm dữ liệu Text và Web ................................................... 97 Khai phá dữ liệu Text và các mô hình biểu diễn dữ liệu…………….. 97 1.1.1 Khai phá dữ liệu Text ................................................................. 97 1.1.2 Các mô hình biểu diễn dữ liệu text ............................................. 97 1.2 1.1.2.1 Mô hình không gian véc tơ ................................................ 108 1.1.2.2 Đánh chỉ mục theo ngữ nghĩa tiềm tàng............................ 119 1.1.2.3 Phép chiếu ngẫu nhiên ....................................................... 119 1.1.2.4 Phân cụm từ khoá .............................................................. 119 Phân cụm dữ liệu trong khai phá WEB……………………………... 1210 1.2.1 Bài toán phân cụm trang Web................................................. 1210 1.2.2 Sơ bộ về ứng dụng thuật toán SOM trong phân cụm Web ..... 1614 Chƣơng 2. Phƣơng pháp WEBSOM và bộ công cụ SOM Toolbox ......... 1816 2.1 Mạng nơ ron………………………………………………………… 1816 2.1.1 Mạng nơ ron sinh học. ............................................................ 1816 2.1.2 Mạng nơ ron nhân tạo ............................................................. 1917 2.2 2.1.2.1 Cấu tạo mạng nơ ron nhân tạo ......................................... 1917 2.1.2.2 Mô hình nơ ron. ............................................................... 1917 Thuật toán SOM……………………………………………………. 2220 2.3 Phƣơng pháp WEBSOM…………………………………………… 2725 2.3.1 Mã hóa tài liệu ........................................................................ 3028 2.3.2 Xây dựng bản đồ (document map) ......................................... 3129 2.3.2.1 Xây dựng bản đồ dựa trên phần bản đồ nhỏ hơn đã đƣợc hình thành trƣớc đó. .......................................................................... 3129 Formatted: Dutch (Netherlands) 1 Formatted: Dutch (Netherlands) 2.3.2.2 2.4 Các thao tác hoàn thiện, làm mịn trên bản đồ ................. 3230 Công cụ SOM Toolbox…………………………………………….. 3432 2.4.1 Định dạng dữ liệu.................................................................... 3432 2.4.2 Xây dựng các tập dữ liệu ........................................................ 3533 2.4.3 Tiền xử lý dữ liệu .................................................................... 3937 2.4.4 Khởi tạo và huấn luyện ........................................................... 3937 2.4.5 Biểu diễn và phân tích ............................................................ 4038 Chƣơng 3. Ứng dụng phƣơng pháp WEBSOM trong bài toán phân cụm trang Web….. ................................................................................................ 4240 3.1 Thử nghiệm thi hành WEBSOM phân cụm trang Web…………….. 4240 3.1.1 Cấu trúc cơ sở dữ liệu trong máy tìm kiếm Vinahoo ............. 4240 3.1.2 Cấu trúc một số bảng chính trong cơ sở dữ liệu MySQL của Vinahoo ………………………………………………………………….42 40 3.1.3 Cấu trúc một số file nhị phân trong cơ sở dữ liệu của Vinahoo 4644 3.1.3.1 Cấu trúc các file nhị phân trong thƣ mục xxw: ............... 4644 3.1.3.2 Cấu trúc các file nhị phân trong thƣ mục Deltas. ............ 4745 3.1.4 Tiến hành thử nghiệm ............................................................. 4846 3.1.5 Đánh giá kết quả thực nghiệm ................................................ 5149 3.2 kiếm Đề xuất giải pháp ứng dụng phƣơng pháp WEBSOM trong máy tìm Vinahoo……………………………………………………………… 5351 KẾT LUẬN ................................................................................................... 5553 Tài liệu tham khảo......................................................................................... 5754 Mở đầu ................................................................................................................ 3 Lời cảm ơn .......................................................................................................... 5 Các từ viết tắt ...................................................................................................... 6 Formatted: Dutch (Netherlands) 2 Formatted: Dutch (Netherlands) Chƣơng 1. 1.1 Phân cụm dữ liệu Text và Web ..................................................... 7 Khai phá dữ liệu Text và các mô hình biểu diễn dữ liệu. 7 1.1.1 Khai phá dữ liệu Text. .................................................................. 7 1.1.2 Các mô hình biểu diễn dữ liệu text. .............................................. 7 1.2 1.1.2.1 Mô hình không gian véc tơ. ................................................... 8 1.1.2.2 Đánh chỉ mục theo ngữ nghĩa tiềm tàng. ............................... 9 1.1.2.3 Phép chiếu ngẫu nhiên ........................................................... 9 1.1.2.4 Phân cụm từ khoá .................................................................. 9 Phân cụm dữ liệu trong khai phá WEB 10 1.2.1 Bài toán phân cụm trang Web..................................................... 10 1.2.2 Sơ bộ về ứng dụng thuật toán SOM trong phân cụm Web. ........ 14 Chƣơng 2. Phƣơng pháp WEBSOM và bộ công cụ SOM Toolbox ............. 16 2.1 Mạng nơ ron. 16 2.1.1 Mạng nơ ron sinh học. ................................................................ 16 2.1.2 Mạng nơ ron nhân tạo. ................................................................ 17 2.1.2.1 Cấu tạo mạng nơ ron nhân tạo. ............................................ 17 2.1.2.2 Mô hình nơ ron. ................................................................... 17 2.2 Thuật toán SOM. 20 2.3 Phƣơng pháp WEBSOM 25 2.3.1 Mã hóa tài liệu ............................................................................ 28 2.3.2 Xây dựng bản đồ (document map) ............................................. 29 2.3.2.1 Xây dựng bản đồ dựa trên phần bản đồ nhỏ hơn đã đƣợc hình thành trƣớc đó. .............................................................................. 29 2.3.2.2 2.4 Các thao tác hoàn thiện, làm mịn trên bản đồ ..................... 30 Công cụ SOM Toolbox 32 2.4.1 Định dạng dữ liệu........................................................................ 32 2.4.2 Xây dựng các tập dữ liệu ............................................................ 33 2.4.3 Tiền xử lý dữ liệu ........................................................................ 37 2.4.4 Khởi tạo và huấn luyện ............................................................... 37 2.4.5 Biểu diễn và phân tích ................................................................ 38 Formatted: Dutch (Netherlands) 3 Formatted: Dutch (Netherlands) Chƣơng 3. Ứng dụng phƣơng pháp WEBSOM trong bài toán phân cụm trang Web. 40 3.1 Cấu trúc cơ sở dữ liệu trong máy tìm kiếm Vinahoo 3.1.1 40 Cấu trúc một số bảng chính trong cơ sở dữ liệu MySQL của Vinahoo 40 3.1.2 3.2 Cấu trúc một số file nhị phân trong cơ sở dữ liệu của Vinahoo . 44 3.1.2.1 Cấu trúc các file nhị phân trong thƣ mục xxw: ................... 44 3.1.2.2 Cấu trúc các file nhị phân trong thƣ mục Deltas. ................ 45 Cơ chế thực thi quá trình crawler trong module index của máy tìm kiếm Vinahoo. 3.2.1 Error! Bookmark not defined. Mô hình thực thi của module đánh chỉ số (index) trong Vinahoo Error! Bookmark not defined. 3.2.2 Quá trình crawler trong Vinahoo. Error! Bookmark not defined. 3.2.2.1 Cấu trúc hàng đợi các url trong VinahooError! Bookmark not defined. 3.2.2.2 Quá trình crawler trong VinahooError! Bookmark not defined. 3.3 Mô hình ứng dụng phƣơng pháp WEBSOM trong máy tìm kiếm Vinahoo. 51 3.4 Đánh giá kết quả Error! Bookmark not defined. 3.5 Kết luận Error! Bookmark not defined. Tài liệu tham khảo............................................. Error! Bookmark not defined. Formatted: Dutch (Netherlands) 4 Formatted: Dutch (Netherlands) Mở đầu Trong những năm gần đây, Internet đã trở thành một trong những phƣơng tiện cung cấp hiệu quả các thông tin khoa học, thông tin kinh tế, thƣơng mại, quảng cáo và mọi mặt khác của đời sống. 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). Theo thống kê, lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lƣợng cũng nhƣ kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Có thể nói, chúng ta đang bị “ngập” trong dữ liệu, và để có thể khai thác thông tin một cách hiệu quả từ những “núi” dữ liệu khổng lồ đó, chúng ta phải viện đến sự hỗ trợ của các công cụ tìm kiếm, cụ thể là các Máy tìm kiếm (Search Engine). Tuy nhiên, thƣờng thì các máy tìm kiếm trên Web cho kết quả nhanh nhƣng thiếu độ chính xác hoặc ngƣợc lại. Các nhà nghiên cứu ở khắp mọi nơi trên thế giới đã thực hiện những nỗ lực đáng kể để phát triển các phƣơng pháp nhằm khắc phục các yếu điểm trên, tức là cố gắng tăng độ chính xác của kết quả tìm kiếm mà vẫn không gây ảnh hƣởng tới tốc độ. Một trong các giải pháp đƣợc rất nhiều nhà nghiên cứu quan tâm và triển khai chính là giải thuật SOM (Self Organizing Map) do giáo sƣ Teuvo Kohonen đề xuất. SOM (Self Organizing Map) đƣợc giáo sƣ Teuvo Kohonen phát triển, là một công cụ rất thích hợp trong khai phá dữ liệu. SOM là một thuật toán học mạng nơron không giám sát, qua quá trình “tự tổ chức”, sắp xếp dữ liệu phức tạp và nhiều chiều, sao cho các dữ liệu giống nhau đƣợc nhận ra và xếp cạnh nhau trên bản đồ [5]. Từ việc tìm hiểu và phân tích giải thuật SOM, hƣớng tới mục tiêu nâng cao hiệu quả tìm kiếm, Luận văn với đề tài “WEB Mining với giải thuật SOM và ứng dụng cho máy tìm kiếm Vinahoo” tập trung vào lĩnh vực khai phá dữ liệu Web dùng mạng nơron, sử dụng phƣơng pháp học mạng nơron không giám sát, dùng thuật toán SOM để giải quyết bài toán phân cụm, ứng dụng cho máy tìm kiếm Vinahoo. Nội dung của Luận văn bao gồm các phần chính nhƣ sau: Chương 1: Tìm hiểu các mô hình biểu diễn dữ liệu trang Web,. bBài toán phân cụm các trang Web, các đặc điểm, yêu cầu và một số độ đo tính chính xác 5 Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) của giải thuật phân cụm. và tTổng quan về áp dụng giải thuật SOM cho bài toán phân cụm các trang Web [4, 6, 8]. Chương 2: Tìm hiểu giải thuật SOM. Tìm hiểu cCấu trúc và quá trình thực thi phƣơng pháp WEBSOM dựa trên giải thuật SOM và phƣơng pháp học mạng nơron không giám sát, ứng dụng cho bài toán phân cụm trang Web. Tìm hiểu bộ công cụ SOM Toolbox [2, 5, 7, 8]. Chương 3: Tìm hiểu cấu trúc cơ sở dữ liệu của máy tìm kiếm Vinahoo [10]. Thực nghiệm ứng dụng giải thuật SOM trong phân cụm các trang Web lƣu trữ trong cơ sở dữ liệu của máy tìm kiếm Vinahoo, đánh giá kết quả thực nghiệm, và đƣa ra các kết luận và đề xuất giải pháp tích hợp WEBSOM trong Vinahoo. Formatted: Dutch (Netherlands) 6 Formatted: Dutch (Netherlands) Lời cảm ơn Luận văn đƣợc thực hiện dƣới sự hƣớng dẫn của thầy giáo TS. Hà Quang Thụy. Tôi xin gửi tới thầy lời cảm ơn chân thành vì sự quan tâm, tận tình chỉ dẫn, giúp đỡ mà thầy đã dành cho tôi trong suốt quá trình hoàn thành luận văn. Xin trân trọng cảm ơn TS. Nguyễn Tuệ - Chủ nhiệm Bộ môn Các hệ thống thông tin, PGS.TS Trịnh Nhật Tiến – Chủ nhiệm Khoa Công nghệ thông tin. Xin cảm ơn các bạn, các đồng nghiệp của tôi tại Bộ môn Các hệ thống thông tin, những ngƣời đã hết sức nhiệt tình cho tôi những chỉ dẫn, góp ý trong suốt quá trình thực hiện luận văn. Tôi cũng xXin gửi lời cảm ơn bố mẹ, em và anhchân thành tới gia đình, bạn bè, những ngƣời đã luôn ở bên tôi, động viên và nâng đỡ giúp đỡ, tạo điều kiện cho những tiến bộ của tôi. {Nên đặt vị trí của gia đình khác với bàn bè}. Hà Nội ngày 20/12/2005 Dư Phương Hạnh Formatted: Dutch (Netherlands) 7 Formatted: Dutch (Netherlands) Các từ viết tắt CSDL Cơ sở dữ liệu VSM Vector Space Model LSI Latent Semantic Indexing SOM Self Organizing Map BMU Best Matching Unit SVD Singular-Value Decomposition Formatted: Font: Bold, Dutch (Netherlands) Formatted: Dutch (Netherlands) SVD (singular-value decomposition) Formatted: Dutch (Netherlands) 8 Formatted: Dutch (Netherlands) Chương 1. Phân cụm dữ liệu Text và Web 1.1 Khai phá dữ liệu Text và các mô hình biểu diễn dữ liệu. 1.1.1 Khai phá dữ liệu Text. Trong những năm gần đây Internet đã trở thành một trong những phƣơng tiện cung cấp hiệu quả các thông tin khoa học, thông tin kinh tế, thƣơng mại, quảng cáo và mọi mặt khác của đời sống. 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). Theo thống kê, lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lƣợng cũng nhƣ kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Có thể nói, chúng ta đang bị “ngập” trong dữ liệu, và để có thể khai thác thông tin một cách hiệu quả từ những “núi” dữ liệu khổng lồ đó, chúng ta phải viện đến sự hỗ trợ của các công cụ tìm kiếm, cụ thể là các Máy tìm kiếm (search Engine). Mục tiêu của các máy tìm kiếm là thu thập các tài liệu phù hợp với yêu cầu của ngƣời dùng trong một khoảng thời gian càng nhanh càng tốt. Tuy nhiên, với lƣợng thông tin khổng lồ không ngừng tăng trƣởng trên Internet, với những yêu cầu đôi khi rất mù mờ hoặc phức tạp từ phía ngƣời dùng, hiệu quả hoạt động của máy tìm kiếm phụ thuộc rất nhiều vào phƣơng pháp biểu diễn dữ liệu, giải thuật áp dụng cho quá trình tìm kiếm và khả năng tƣơng tác trực quan giữa máy với ngƣời dùng. 1.1.2 Các mô hình biểu diễn dữ liệu text Hiện nay, trong phần lớn các nghiên cứu trong lĩnh vực khai phá dữ liệu text, các văn bản, tài liệu thƣờng đƣợc hiển thị nhƣ một tập hợp của các từ. Cách tiếp cận này đƣợc gọi tên là "Mã hoá kiểu túi" (bag of words encoding), bỏ qua mục đích của từ cũng nhƣ cấu trúc hay dấu chấm câu nhƣng lại ghi nhớ số lần mỗi từ xuất hiện. Phƣơng pháp này là một sự đơn giản hoá tối đa về nội dung thông tin mà các văn bản, tài liệu mang lại. Mặc dù không đủ phức tạp để biểu diễn dữ liệu, nhƣng phƣơng pháp này lại mang lại một số lƣợng thông tin đáng kể về sự liên quan giữa các từ và các văn bản, điều hết sức quan trọng trong việc phân cụm dữ liệu theo chủ đề hoặc trong việc lấy thông tin 9 Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) (information retrieval) từ một tập dữ liệu lớn. Dƣới đây là một số phƣơng pháp biểu diễn dữ liệu, tập trung vào các mô hình có thể đƣợc đánh giá một cách tự động và hiệu quả thông qua một số lƣợng lớn dữ liệu và đòi hỏi tốc độ xử lý nhanh. Những mô hình này đƣợc thiết kế nhằm đƣa ra các giải pháp kiến trúc khả thi về mặt tính toán để giải quyết những công việc mà nếu sử dụng các phòng thí nghiệm thông thƣờng thì sẽ rất tốn kém, rất chậm và thậm chí là bất khả thi 1.1.2.1 Mô hình không gian véc tơ Mô hình véctơ (Vector Space Model), còn gọi là VSM do Salton đƣa ra [11], là cách thức mã hoá tài liệu phù hợp với mục tiêu thực thi nhanh chóng. Mỗi tài liệu sẽ đƣợc biểu diễn dƣới dạng một véctơ trong không gian t-chiều, trong đó t là số lƣợng từ khoá trong từ điển. Giá trị d i của thành phần thứ i biểu diễn số lần từ khoá với chỉ số i xuất hiện trong tài liệu. Hơn nữa, mỗi từ lại gắn với một trọng số thể hiện mức độ quan trọng của từ đó. Độ tƣơng tự giữa các tài liệu đƣợc tính bằng khoảng cách giữa các điểm hoặc góc giữa các véctơ (mà không cần quan tâm đến độ dài của các véctơ). Với mô hình này, việc tìm kiếm các tài liệu phù hợp với yêu cầu tìm kiếm chuyển thành tìm kiếm các véctơ tài liệu gần nhất với véctơ truy vấn. Mặc dù đơn giản, nhƣng phƣơng pháp biểu diễn véctơ và các biến thể của nó hiện là các lựa chọn phổ biến nhất để biểu diễn văn bản phục vụ mục đích khai phá text. Có thể giải thích là do tốc xử lý các phép toán trên véctơ rất nhanh, các giải thuật chuẩn áp dụng cho véctơ đều đã có sẵn. Tuy nhiên, phƣơng pháp này mắc phải yếu điểm yếu chính là, trong quá trình xử lý, bộ nhớ phải lƣu trữ các véctơ mẫu có số chiều vô cùng lớn. Tất nhiên kích cỡ của từ điển có thể đƣợc thu gọn lại bằng cách lựa chọn một tập con chứa các từ khóa quan trọng nhất xét theo một số quy luật nào đó, thế nhƣng đây vẫn là một công việc hết sức khó khăn để đảm bảo rằng, tập con các từ khóa này vẫn có khả năng biểu diễn các đặc trƣng cơ bản của các tài liệu. Formatted: Dutch (Netherlands) 10 Formatted: Dutch (Netherlands) 1.1.2.2 Đánh chỉ mục theo ngữ nghĩa tiềm tàng Để thực hiện giảm số chiều của các véctơ tài liệu mà căn bản không gây mất mát thông tin, trƣớc tiên, ngƣời ta xây dựng một ma trận mà mỗi cột của ma trận ứng với một véctơ tài liệu. Sau đó, một phƣơng pháp tính toán trên ma trận, có tên gọi là SVD (singular-value decomposition) đƣợc áp dụng để phân chia ma trận trên thành một tập hợp các yếu tố (factors) đƣợc sắp xếp theo trật tự giảm dần độ ảnh hƣởng đối với ma trận ban đầu. Và khi những yếu tố sau cùng, cũng là những yếu tố ít quan trọng nhất bị bỏ qua, thì véctơ tài liệu đƣợc xây dựng dựa trên các yếu tố còn lại sẽ có số chiều nhỏ hơn rất nhiều mà vẫn giữ đƣợc nhiều nhất có thể các thông tin quan trọng. Phƣơng pháp này đƣợc gọi là đánh chỉ mục theo ngữ nghĩa tiềm tàng (Latent Semantic Indexing - LSI) [4]. 1.1.2.3 Phép chiếu ngẫu nhiên Đây là phƣơng pháp làm giảm số chiều của véctơ tài liệu một cách triệt để mà lại đơn giản hơn rất nhiều so với phƣơng pháp LSI nêu trên và không gây ảnh hƣởng tới độ phân biệt giữa các tài liệu [4]. Xét véctơ ni Rn và một ma trận ngẫu nhiên hình chữ nhật R mà các phần tử trong cột của R ứng với Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) các véctơ phân bố chuẩn và có độ dài đơn vị. Chúng ta sẽ xây dựng các véctơ tài liệu xi Rm, với m << n bằng phép chiếu: Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) xi = Rni Nếu ta xét một cặp tài liệu bất kỳ (ni, nj), sau khi thực hiện phép chiếu ta thu đƣợc tƣơng ứng hai tài liệu (xi, xj), thì độ tƣơng tự của hai tài liệu trƣớc và sau khi thực hiện phép chiếu là không thay đổi, và khả năng lỗi thì tỷ lệ nghịch với m. Thực nghiệm với giá trị m>100, kết quả thu đƣợc cho thấy độ chính xác phân lớp của phƣơng pháp này bằng với phƣơng pháp VSM, tuy nhiên thời gian cần thiết để thực hiện thì giảm đi nhiều. 1.1.2.4 Phân cụm từ khoá Phƣơng pháp này đƣợc sử dụng nhằm làm giảm số lƣợng dữ liệu cần biểu diễn bằng cách nhóm các thành phần tƣơng tự lại với nhau. Trong biểu diễn dữ liệu, một sô phƣơng pháp phân cụm đƣợc áp dụng để nhóm các từ tƣơng tự Formatted: Dutch (Netherlands) 11 Formatted: Dutch (Netherlands) thành một nhóm, sau đó thực hiện biểu diễn tài liệu nhƣ tập hợp của các nhóm từ khoá chứ không phải là tập hợp của từng từ khoá riêng lẻ. Giải thuật SOM dựa trên phƣơng pháp học máy không giám sát là một trong những giải pháp tốt để thực hiện việc phân cụm từ khoá. Chúng ta sẽ đi sâu tìm hiểu vấn đề này ở chƣơng sau. 1.2 Phân cụm dữ liệu trong khai phá WEB 1.2.1 Bài toán phân cụm trang Web Ngày nay, 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. 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 Formatted: Font: Times New Roman, Dutch (Netherlands) Formatted: Dutch (Netherlands) đây Internet đã 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à sự thấp về giá cả 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ì chi phí cho một trang Web rẻ hơn rất nhiều, đồng thời 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. 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 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, đặc biệt là khi chúng ta không có nhiều hiểu biết về lĩnh vực mình cần tìm kiếm thông tin. Do đó, cần phải có một công cụ 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 công cụ nhƣ vậy (đƣợc gọi là máy tìm kiếm) quản lý dữ liệu nhƣ các đối tƣợng phi cấu trúc. Hiện nay chúng ta đã quen thuộc với các máy tìm kiềm nhƣ Yahoo, Google, Alvista,... Formatted: Dutch (Netherlands) 12 Formatted: Dutch (Netherlands) Một trong những bài toán quan trọng trong lĩnh vực khai phá Web là bài toán phân cụm Web. Phân cụm Web - nói một cách khái quát - là việc tự động sinh ra các lớp tài liệu dựa vào sự tƣơng tự của các tài liệu. Các lớp tài liệu ở đây là chƣa biết trƣớc, ngƣời dùng có thể chỉ yêu cầu số lƣợng các lớp cần phân loại, hệ thống sẽ đƣa ra các tài liệu theo từng tập hợp, từng cụm, mỗi tập hợp chứa các tài liệu tƣơng tự nhau. Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các tài liệu đƣợc lấy từ Web. Có hai tình huống phân cụm tài liệu. Tình huống thứ nhất là việc phân cụm trên toàn bộ một CSDL có sẵn gồm rất nhiều tài liệu Web. Thuật toán phân cụm cần tiến hành việc phân cụm toàn bộ tập dữ liệu thuộc CSDL đó. Tình huống này thƣờng đƣợc gọi là phân cụm không trực tuyến (off-line). Tình huống thứ hai thƣờng đƣợc áp dụng trên một tập tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về theo một truy vấn của ngƣời dùng. Trong trƣờng hợp này, giải pháp phân cụm đƣợc tiến hành kiểu trực tuyến (on-line) theo nghĩa việc phân cụm tiến hành theo từng bộ phận các tài liệu nhận đƣợc. Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân cụm ngay khi chƣa có đủ tài liệu và phân cụm tiếp theo cần không tiến hành với dữ liệu đã đƣợc phân cụm Quá trình xử lý truy vấn và kết quả phân hạng đƣợc phản hồi từ các máy tìm kiếm phụ thuộc vào việc tính toán độ tƣơng tự giữa truy vấn và các tài liệu. Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhƣng nó thƣờng quá ngắn và dễ xảy ra sự nhập nhằng. Nhƣ đã biết, trung bình các truy vấn trên Web chỉ gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn, truy vấn star dẫn đến sự nhập nhằng rất cao, các tài liệu lấy đƣợc liên quan đến astronomy, plants, animals, popular media and sports figures… Độ tƣơng tự giữa các tài liệu của một truy từ đơn nhƣ vậy là khác nhau rất lớn. Vì lẽ đó, nếu máy tìm kiếm phân cụm các kết quả theo từng chủ đề thì ngƣời dùng có thể hiểu truy vấn nhanh chóng hoặc tìm vào một chủ đề xác định. Đặc điểm của bài toán Phân cụm Web Việc phân cụm trực tuyến các tài liệu Web kết quả trả về từ máy tìm kiếm là rất khác so với việc phân cụm các tài liệu thông thƣờng. Một đặc điểm Formatted: Dutch (Netherlands) 13 Formatted: Dutch (Netherlands) là số lƣợng các tài liệu Web là vô cùng lớn và luôn luôn thay đổi. Ngoài ra một vấn đề nữa là các hệ thống tìm kiếm thông tin là tƣơng tác ngƣời dùng cho nên thời gian đáp ứng của hệ thống phải đủ nhanh, cụ thể bài toán ở đây cần thời gian đáp ứng cần tính bằng giây. Mỗi tài liệu Web không chỉ liên quan đến một khía cạnh cụ thể nào đó mà đề cập đến nhiều khía cạnh khác nhau. Chẳng hạn nhƣ tài liệu nói về “Việt Nam” cũng có thể đề cập đến cuộc đời và sự nghiệp của “Các danh nhân Việt Nam”. Cho nên tồn tại sự trùng lặp thông tin giữa các tài liệu, có nghĩa là một tài liệu có thể liên quan đến nhiều nội dung khác nhau. Xuất phát từ những đặc điểm đó nên việc phân cụm chỉ nên đƣợc thực hiện trên tập các tài liệu Web của mỗi truy vấn trả về từ máy từ máy tìm kiếm. Sau đó kết quả sẽ đƣợc tổ chức lại cho ngƣời sử dụng. Thông thƣờng một máy tìm kiếm phục vụ hàng triệu truy vấn một ngày cho nên việc phân phối CPU cũng nhƣ bộ nhớ cho mỗi truy vấn cần đƣợc rút ngắn tối đa. Cho nên việc phân cụm có thể đƣợc thực hiện trên một máy tách riêng tại đó chỉ nhận các kết quả của máy tìm kiếm nhƣ đầu vào, tạo ra các cụm và biểu diễn chúng cho ngƣời sử dụng. Bảng dƣới đây trình bày ví dụ về phân cụm kết quả của truy vấn “Việt Nam”, ở đây chỉ biểu diễn 5 cụm đầu tiên. Minh họa cho việc phân cụm kết quả truy vấn “Việt Nam” Số tài liệu: 185 Các cụm Số tài liệu Chủ đề liên quan 1 54 Lịch sử Việt Nam 2 10 Đất nƣớc Việt Nam 3 9 Kinh tế Việt Nam 4 7 Các danh nhân Việt Nam 5 7 Du lịchh Việt Nam … … … Các yêu cầu đối với Phân cụm Web Để có thể phân các tài liệu Web thành các cụm, việc đầu tiên là cần phải tính đƣợc độ tƣơng tự (hay độ tƣơng đồng) giữa các tài liệu trên cơ sở biểu diễn 14 Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) tài liệu Web và xem xét các đo độ tƣơng tự giữa chúng. Thuật toán phân cụm cần đƣa ra các điều kiện dừng và gắn nhán cho các cụm một các thích hợp nhất. Căn cứ đặc điểm và yêu cầu của bài toán phân cụm Web thì phƣơng pháp phân cụm đƣợc lựa chọn cần đáp ứng đƣợc các yêu cầu sau: Tính phù hợp: Phƣơng pháp phải tạo nên các cụm trong đó nhóm tài liệu phù hợp với truy vấn của ngƣời dùng tách riêng với các nhóm không phù hợp khác. Tổng hợp phải dễ đọc: Tránh trƣờng hợp thay vì ngƣời dùng không phải xem xét danh sách các tài liệu đƣợc phân hạng lại phải xem xét danh sách tài liệu trong một cụm. Do đó phƣơng pháp phải cung cấp mô tả ngắn gọn và chính xác của các cụm. Tính đa hình: Vì các tài liệu có nhiều chủ đề, nên tránh việc hạn chế một tài liệu chỉ thuộc về một cụm. Sử dụng các mẩu thông tin: Phƣơng pháp phải tạo ra các cụm tốt thậm chí chỉ sử dụng các mẩu thông tin đƣợc trả về bởi máy tìm kiếm (thông thƣờng các máy tìm kiếm chỉ trả về các mẩu thông tin mô tả về tài liệu). Điều này tránh cho việc ngƣời dùng phải chờ đợi hệ thống tải toàn bộ tài liệu gốc từ Web. Tốc độ:Một ngƣời sử dụng dù kiên nhẫn cũng chỉ có thể xem xét khoảng 100 tài liệu trong danh sách các tài liệu đƣợc phân hạng. Hệ thống cần cho phép ngƣời dùng có thể đọc qua một tập đủ lớn các tài liệu trong một thời gian chấp nhận đƣợc. Vì vậy cần một phƣơng pháp phân cụm khoảng 1000 mẩu thông tin trong vài giây. Tính gia tăng: Để tiết kiệm thời gian, phƣơng pháp nên xử lý từng mẩu thông tin ngay khi lấy đƣợc từ Web để có đƣợc kết quả tức thời ứng với mỗi thời điểm. Một số độ đo độ đánh giá Độ đo đánh giá thuật toán phân cụm là một tiêu chuẩn đƣợc chỉ ra bởi một tập n tài liệu D và một tập các truy vấn Q. Với mỗi q Є Q, một tập của các tài liệu phù hợp là Dq Є D đƣợc xác định bằng tay. Giả sử có một truy vấn đƣợc gửi đến hệ thống, một danh sách đƣợc phân hạng các tài liệu (d 1, d2, … dn) đƣợc trả về. Các hệ thống tìm kiếm thông thƣờng chỉ hiển thị một số mục đầu Formatted: Dutch (Netherlands) 15 Formatted: Dutch (Netherlands) tiên của danh sách này. Tƣơng ứng với danh sách nhƣ vậy, có thể tính một danh sách phù hợp (r1, r2,…rn) bởi các số (0/1) trong đó ri =1 nếu di Є Dq và bằng 0 trong các trƣờng hợp khác. Với truy vấn q này, độ hồi tƣởng (recall) tại hạng k ≥ 1 đƣợc xác định Recall (k) = 1 Dq Formatted: Dutch (Netherlands) r 1i  k i Formatted: Dutch (Netherlands) Độ hồi tƣởng là tỷ số của tất cả các tài liệu phù hợp bên trong (d 1, d2, … dk) và độ chính xác (precision) tại hạng k là: Precision (k) = 1  ri k 1i  k Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) Độ chính xác là tỷ số của k tài liệu trên cùng tập tài liệu mà thật sự phù hợp. Một cách đo khác là độ chính xác trung bình (Average Precision): Average Precision = 1 Dq r 1 k  D k Formatted: Dutch (Netherlands)  precision(k ) Formatted: Dutch (Netherlands) Độ chính xác trung bình là tổng của độ chính xác tại mỗi vị trí phù hợp trong danh sách đáp ứng chia cho tổng số các tài liệu phù hợp đƣợc chọn. Độ chính xác trung bình bằng 1 khi lấy đƣợc toàn bộ các tài liệu phù hợp và xếp loại chúng lên trên tất cả các tài liệu không phù hợp. 1.2.2 Sơ bộ về ứng dụng thuật toán SOM trong phân cụm Web Việc tìm kiếm các tài liệu có liên quan đến nhau trong một tập hợp dữ liệu rất lớn, thông thƣờng đƣợc thực hiện dựa trên các từ khoá và các biểu diễn logic của chúng. Tuy nhiên, thƣờng thì các kết quả trả về nhanh nhƣng thiếu độ chính xác hoặc ngƣợc lại. Những nỗ lực đáng kể đã đƣợc thực hiện để phát triển các phƣơng pháp khác, chẳng hạn dựa trên các thống kê từ đơn, nhƣng khả năng ứng dụng của chúng đều thấp. Điểm bất lợi căn bản trong các phƣơng pháp tìm kiếm truyền thống chẳng hạn nhƣ tìm kiếm thông qua từ khoá hoặc đánh chỉ mục nội dung thông tin là: rất khó để xây dựng đƣợc các biểu thức tìm kiếm phù hợp để không loại bỏ các tài liệu phù hợp và cũng không tạo ra các danh sách dài các tiêu đề không phù hợp với mục tiêu tìm kiếm. Giả sử chúng ta mô tả các tài liệu toàn văn nhờ trọng số của các từ trong tài liệu đó. Điểm hạn chế của phƣơng pháp này là, khi gặp một khối lƣợng nội dung đủ lớn, số Formatted: Dutch (Netherlands) 16 Formatted: Dutch (Netherlands) lƣợng từ đƣợc lựa chọn cũng sẽ rất lớn, chẳng hạn là con số 10.000 từ. Rất nhiều nghiên cứu đã chỉ ra rằng, tài liệu có thể đƣợc biểu diễn rất hiệu quả dƣới dạng một tập thuộc tính nhỏ hơn rất nhiều nếu nhƣ các từ đƣợc phân cụm theo nội dung của chúng từ trƣớc đó hoặc áp dụng một số phƣơng pháp khác để làm giảm số chiều (xem 1.1.2). Một vấn đề khác còn lớn hơn mà một số phƣơng pháp tìm kiếm đã không chú ý hỗ trợ, đó là các trƣờng hợp mà nội dung thông tin cần tìm kiếm là không rõ ràng và khó để mô tả thành lời. Chẳng hạn một số trƣờng hợp, thông tin cần tìm kiếm nằm ngoài phạm vi hiểu biết của cá nhân thì việc đƣa ra các biểu thức tìm kiếm thật chẳng khác nào đi tìm đƣờng trong bóng đêm và tất nhiên kết quả thu đƣợc là hết sức đáng thất vọng. Lúc này đây, nếu trong tay chúng ta có một tấm bản đồ mô tả tập hợp dữ liệu, trên đó các dữ liệu đƣợc sắp xếp và phân vùng theo nội dung, thì khi đó, ngay chỉ một thông tin nhỏ có liên quan đến vấn đề cần tìm kiếm cũng trở nên hữu ích. Bản đồ hữu ích cho việc tìm kiếm trƣớc hết là nhờ khả năng trực quan hoá không gian thông tin, sau đó là khả năng hƣớng dẫn ngƣời dùng đến với vùng thông tin cần tìm kiếm cũng nhƣ các thông tin có liên quan. Ta có thể hiểu rằng, trong trƣờng hợp này, ngƣời dùng viện đến sự trợ giúp của máy tìm kiếm không theo nghĩa tìm kiếm thông tin (searching) mà theo nghĩa thăm dò thông tin (exploration). Sự khác biệt giữa hai khái niệm này có thể đƣợc minh hoạ nhƣ sau: Một ngƣời tới hiệu sách và hỏi ngƣời bán hàng về một cuốn sách cụ thể mà anh ta đang cần (searching) và một ngƣời đi dạo qua từng kệ sách, đọc từng cái tên sách và phỏng đoán cuốn sách nào là phù hợp với yêu cầu của anh ta (exploration). Trong vài năm gần đây, một hƣớng nghiên cứu mới đã xuất hiện, đó là một phƣơng pháp tìm kiếm thông tin toàn văn có tính chất thăm dò và công cụ duyệt tin có tên là WEBSOM [4, 6, -8]. Nó đƣợc xây dựng dựa trên giải thuật SOM, là giải thuật áp dụng thuật toán học không giám sát để phân tích và trừu tƣợng hoá dữ liệu đa chiều. Phƣơng pháp này đáp ứng đƣợc cả hai nhu cầu: phân cụm dữ liệu và trực quan hoá không gian thông tin. Formatted: Dutch (Netherlands) 17 Formatted: Dutch (Netherlands) Chương 2. Phương pháp WEBSOM và bộ công cụ SOM Toolbox 2.1 Mạng nơ ron. 2.1.1 Mạng nơ ron sinh học. Bộ não con ngƣời chứa khoảng 1010 các phần tử (đƣợc gọi là nơron) liên kết chặt chẽ với nhau. Đối với mỗi nơron, có khoảng 10 4 liên kết với các nơron khác. Một nơron đƣợc cấu tạo bởi các thành phần nhƣ tế bào hình cây, tế bào thân và sợi trục thần kinh (trục cảm ứng). Tế bào hình cây có nhiệm vụ mang các tín hiệu điện tới tế bào thân, tế bào thân sẽ thực hiện gộp (sum) và phân ngƣỡng các tín hiệu đến. Sợi trục thần kinh làm nhiệm vụ đƣa tín hiệu từ tế bào thân tới tế bào hình cây của các nơron liên kết. Điểm tiếp xúc giữa một sợi trục thần kinh của nơron này với một tế bào hình cây của một nơron khác đƣợc gọi là khớp nối (synapse). Sự sắp xếp các nơron và mức độ mạnh yếu của các khớp thần kinh do các quá trình hoá học phức tạp quyết định, sẽ thiết lập chức năng của mạng nơron [2]. Formatted: Dutch (Netherlands) Xúc tu Formatted: Dutch (Netherlands) Trục cảm ứng Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) Nhân Formatted: Dutch (Netherlands) Khớp nối Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) Formatted: Dutch (Netherlands) Hình 2.1 Mô hình mạng nơron sinh học Formatted: Dutch (Netherlands) Khi con ngƣời sinh ra, một bộ phận các nơron đã có sẵn trong não, còn các bộ phận khác đƣợc phát triển thông qua quá trình học, và trong quá trình đó xảy ra việc thiết lập các liên kết mới và loại bỏ đi các liên kết cũ giữa các nơron. Cấu trúc mạng nơron luôn luôn phát triển và thay đổi. Các thay đổi có Formatted: Dutch (Netherlands) 18