Áp dụng kỹ thuật phân cụm dữ liệu mờ trong khai phá dữ liệu Web

ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ<br /> TRONG KHAI PHÁ DỮ LIỆU WEB<br /> Đỗ Quang Khôi1<br /> Tóm tắt: World Wide Web là một kho dữ liệu khổng lồ, vì vậy việc khai phá Web<br /> để khám phá ra những thông tin, tri thức hữu ích mang một ý nghĩa hết sức quan trọng.<br /> Với mục đích đó, bài báo này trình bày tổng quan về khai phá dữ liệu Web, các hướng<br /> tiếp cận phân cụm tài liệu Web. Qua đó, bài báo giới thiệu mô hình tiếp cận phân cụm<br /> tài liệu Web bằng kỹ thuật phân cụm dữ liệu mờ và trình bày cụ thể quá trình tìm kiếm<br /> và phân cụm tài liệu Web bằng kỹ thuật phân cụm dữ liệu mờ với thuật toán Fuzzy<br /> C-Means.<br /> 1. Giới thiệu<br /> Các phương pháp phân tích dữ liệu truyền thống (dữ liệu rõ) tập trung phân tích<br /> một tập dữ liệu ban đầu thành các cụm dữ liệu có tính tự nhiên và mỗi đối tượng dữ liệu<br /> chỉ thuộc về một cụm dữ liệu, phương pháp này chỉ phù hợp với việc khám phá ra các<br /> cụm có mật độ cao và rời nhau, với đường biên giữa các cụm được xác định tốt. Tuy<br /> nhiên, trong thực tế, đường biên giữa các cụm có thể mờ, các cụm có thể chồng lên<br /> nhau, nghĩa là một số các đối tượng dữ liệu thuộc về nhiều cụm khác nhau. Do đó, các<br /> phương pháp phân cụm truyền thống không mô tả được dữ liệu thực. Vì vậy, người ta<br /> đã áp dụng lý thuyết tập mờ trong phân cụm dữ liệu (PCDL) để giải quyết cho trường<br /> hợp này. Cách thức kết hợp này được gọi là PCDL mờ (gọi tắt là phân cụm mờ).<br /> Hơn nữa, World Wide Web (WWW) là một kho thông tin khổng lồ với tiềm năng<br /> được coi là không có giới hạn. Để đáp ứng phần nào nhu cầu tìm kiếm và sử dụng<br /> nguồn tri thức này, người ta đã xây dựng các công cụ tìm kiếm và xử lý thông tin bằng<br /> cách áp dụng các kỹ thuật khai phá dữ liệu (KPDL) trong khai phá tài nguyên Web.<br /> Trong đó, PCDL Web là một bài toán điển hình trong khai phá tài nguyên Web.<br /> Hiện tại đã có một số thuật toán PCDL được sử dụng trong phân cụm tài liệu như<br /> các thuật toán phân cụm phân hoạch, các thuật toán phân cụm phân cấp,… Tuy nhiên,<br /> trong thực tế nội dung của một trang Web có thể thuộc vào nhiều nhóm chủ đề khác<br /> nhau. Vì vậy, phân cụm theo nội dung trang Web với hướng tiếp cận truyền thống tỏ ra<br /> còn nhiều hạn chế. Để giải quyết vấn đề này, một hướng đi mới đó là nghiên cứu và áp<br /> dụng các kỹ thuật PCDL theo cách tiếp cận mờ trong KPDL Web.<br /> Bài báo này xem xét khía cạnh sử dụng kỹ thuật phân cụm dữ liệu mờ trong<br /> KPDL Web và được thực nghiệm bằng chương trình ứng dụng thực hiện tìm kiếm trên<br /> Web và sau đó phân cụm kết quả tìm kiếm này bằng hai kỹ thuật phân cụm: phân cụm<br /> rõ với thuật toán k-means và phân cụm mờ với thuật toán Fuzzy C-Means (FCM).<br /> <br /> 1<br /> <br /> ThS, Trung tâm Học liệu, trường Đại học Quảng Nam<br /> <br /> ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …<br /> 2. Tổng quan về khai phá dữ liệu Web<br /> Với sự phát triển nhanh chóng của Internet, các thông tin trên WWW đã trở thành<br /> một kho dữ liệu khổng lồ trong hầu hết các lĩnh vực kinh tế, xã hội, chính trị, giáo dục,<br /> khoa học,... WWW chứa một bộ sưu tập các thông tin phong phú và đa dạng về nội<br /> dung trang web với cấu trúc siêu văn bản và đa phương tiện, thông tin siêu liên kết, truy<br /> cập và sử dụng thông tin, cung cấp một nguồn dữ liệu đồ sộ cho KPDL.<br /> <br /> Hình 1. Phân loại KPDL Web.<br /> Có nhiều khái niệm khác nhau về KPDL Web. Tuy nhiên, theo [6], [8], ta có khái<br /> niệm tổng quát nhất như sau: KPDL Web là việc sử dụng các kỹ thuật KPDL để khám<br /> phá ra những thông tin, tri thức hữu ích từ các cấu trúc siêu liên kết, nội dung trang web<br /> và dữ liệu sử dụng. Dựa trên các kiểu dữ liệu chính được sử dụng trong quá trình khai<br /> phá, KPDL Web có thể được phân thành ba loại: khai phá nội dung, khai phá cấu trúc và<br /> khai phá theo sử dụng [8].<br /> • Khai phá nội dung Web:<br /> Khai phá nội dung Web nhằm trích lọc hoặc khai thác những thông tin hữu ích, tri<br /> thức từ nội dung trang. Khai phá nội dung Web có thể được phân biệt bởi hai cách tiếp<br /> cận: tiếp cận dựa trên hành động và tiếp cận dựa trên CSDL. Cách tiếp cận thứ nhất nhằm<br /> mục đích cải thiện việc tìm kiếm và trích lọc thông tin. Cách tiếp cận thứ hai nhằm mục<br /> đích mô hình hóa dữ liệu trên Web thành dạng có cấu trúc hơn để áp dụng vào truy vấn<br /> CSDL và các ứng dụng KPDL.<br /> • Khai phá cấu trúc Web:<br /> Khai phá cấu trúc Web nhằm phát hiện ra tri thức hữu ích từ các siêu liên kết, các<br /> siêu liên kết này chính là đặc trưng cho cấu trúc Web. Ví dụ, từ các liên kết, chúng ta có<br /> thể khám phá các trang web quan trọng, và chúng cũng chính là một kỹ thuật quan trọng<br /> được sử dụng trong các máy tìm kiếm. KPDL truyền thống không thực hiện được như<br /> vậy bởi vì nó thường là không có cấu trúc liên kết trong một bảng quan hệ.<br /> 51<br /> <br /> ĐỖ QUANG KHÔI<br /> • Khai phá theo sử dụng Web:<br /> Khai phá theo sử dụng Web đề cập đến sự khám phá các mẫu truy cập của người<br /> dùng từ các bản ghi sử dụng Web (Web log records). Phân tích quá trình đăng nhập<br /> Web của người dùng cũng có thể giúp cho việc xây dựng các dịch vụ Web theo yêu cầu<br /> đối với từng người dùng riêng lẻ được tốt hơn. Một trong những vấn đề quan trọng<br /> trong khai phá theo sử dụng Web là tiền xử lý luồng dữ liệu nhấp chuột trong các bản<br /> ghi sử dụng nhằm đem lại dữ liệu đúng đắn để khai phá.<br /> 3. Các hướng tiếp cận phân cụm tài liệu Web<br /> Có rất nhiều phương pháp tiếp cận phân cụm tài liệu Web đã được đề xuất. Mỗi<br /> hướng tiếp cận theo một cách khác nhau, như: kiểu dữ liệu của các thuộc tính; độ đo<br /> tương tự,... Dựa trên những đặc trưng hay thuộc tính của tài liệu, hướng tiếp cận của các<br /> thuật toán phân cụm tài liệu Web có thể chia làm các loại sau [9]:<br /> • Phân cụm dựa trên văn bản:<br /> Hướng tiếp cận phân cụm tài liệu Web dựa trên văn bản đặc tả mỗi tài liệu theo<br /> nội dung của nó, tức là các từ (hoặc đoạn văn bản) chứa trong nó. Ý tưởng chính của<br /> hướng tiếp cận này đó là nếu hai tài liệu có chứa nhiều từ chung với nhau thì có khả<br /> năng hai tài liệu này là rất giống nhau.<br /> Các kỹ thuật phân cụm tài liệu Web dựa trên văn bản như: phân cụm phân hoạch,<br /> phân cụm phân cấp, phân cụm mờ, phân cụm dựa vào mạng nơron, phân cụm dựa vào<br /> xác suất,...<br /> • Phân cụm dựa trên liên kết:<br /> Các phương pháp phân cụm dựa trên văn bản được phát triển để sử dụng đối với<br /> bộ tài liệu tĩnh, đồng nhất và nhỏ. Ngược lại, WWW là một tập khổng lồ các trang web<br /> đồng nhất và liên kết với nhau. Hơn nữa, các trang web lại có thêm những thông tin<br /> được đính kèm theo nhưng lại rất hữu ích cho quá trình phân cụm, như: siêu dữ liệu, các<br /> siêu liên kết.<br /> Ý tưởng của hướng tiếp cận này đó là khi hai tài liệu được kết nối thông qua một<br /> liên kết có mối quan hệ về mặt ngữ nghĩa giữa chúng thì đó có thể là cơ sở cho việc<br /> phân hoạch các tài liệu về các cụm.<br /> Hai thuật toán tiêu biểu được phát triển dựa theo hướng tiếp cận này đó là: thuật<br /> toán PageRank (S. Brin và đồng nghiệp, 1998) và thuật toán HITS (J. M. Kleinberg,<br /> 1998). Trong đó, thuật toán PageRank lập chỉ mục cho các liên kết giữa các website và<br /> xác định giá trị liên kết của một trang web (gọi là PageRank). Dựa vào PageRank này,<br /> thuật toán xác định thứ tự sắp xếp của mỗi trang trong các kết quả tìm kiếm. Trong khi<br /> đó, thuật toán HITS xếp thứ hạng tài liệu dựa trên thông tin liên kết giữa tập các tài liệu.<br /> • Phân cụm lai ghép:<br /> Phương pháp phân cụm tài liệu Web dựa trên liên kết chỉ đặc tả các tài liệu bằng<br /> các thông tin được trích xuất từ cấu trúc liên kết của tập tài liệu. Còn các phương pháp<br /> 52<br /> <br /> ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …<br /> phân cụm tài liệu Web dựa trên văn bản thì đặc tả tài liệu bởi các từ chứa trong nó. Mặc<br /> dù các liên kết có thể dẫn đến những trang khác nhau từ một trang nhưng nó không có<br /> mục đích chỉ ra sự giống nhau giữa các trang. Các thuật toán phân cụm này có thể cho<br /> kết quả có hiệu quả không cao vì mật độ cấu trúc liên kết thu được có thể là quá nhiều<br /> hoặc quá ít. Còn các thuật toán phân cụm dựa trên văn bản thì lại có vấn đề khi tiếp cận<br /> với các ngôn ngữ khác nhau hay với đặc thù của mỗi ngôn ngữ, ví dụ như: từ đồng<br /> nghĩa, từ trái nghĩa,... Mặt khác, các thông tin trên trang web không chỉ ở dưới dạng văn<br /> bản mà còn có thể là hình ảnh, âm thanh, hay đa phương tiện.<br /> Chính vì những lý do trên, một phương pháp phân cụm lai ghép giữa hai phương<br /> pháp trên được đề xuất để kết hợp những ưu điểm và hạn chế những nhược điểm cho<br /> nhau. Các thuật toán được phát triển theo hướng tiếp cận này như là: thuật toán Phân<br /> cụm nội dung-liên kết (Weiss và đồng nghiệp, 1996), Toric k-means (Modha &<br /> Spangler, 2000),...<br /> Tóm lại, việc lựa chọn phương pháp phân cụm tài liệu Web nào tốt nhất là một<br /> vấn đề không dễ dàng, bởi vì trước hết, mỗi phương pháp đều có ưu và nhược điểm<br /> riêng của nó. Thứ hai, hiệu quả của mỗi phương pháp phụ thuộc vào tập dữ liệu cụ thể<br /> và lĩnh vực ứng dụng.<br /> 4. Kỹ thuật PCDL mờ trong phân cụm kết quả tìm kiếm trên Web<br /> 4.1. Hướng tiếp cận<br /> Việc phân cụm tài liệu Web nhằm phân các trang Web có mức độ quan trọng<br /> tương đương về một cụm. Có nhiều phương pháp để đánh giá mức độ quan trọng của<br /> một trang Web, trong đó có phương pháp dựa vào các liên kết trang để xác định trọng<br /> số cho trang. Các thuật toán PageRank, HITS,... đều dựa trên phương pháp này. Một<br /> cách tiếp cận khác để đánh giá mức độ quan trọng đó là dựa vào nội dung của các trang<br /> Web để xác định trọng số, nếu các trang Web có nội dung tương tự nhau thì sẽ có mức<br /> độ quan trọng tương đương và sẽ cùng thuộc về một cụm.<br /> <br /> Hình 2. Mô hình tiếp cận phân cụm kết quả tìm kiếm<br /> bằng kỹ thuật PCDL mờ.<br /> 53<br /> <br /> ĐỖ QUANG KHÔI<br /> Sử dụng kỹ thuật phân cụm mờ để phân một tập các trang Web với dữ liệu đã<br /> chuẩn hóa được truy vấn từ dữ liệu Web thành c cụm sao cho mỗi trang Web trong cùng<br /> một cụm là tương tự nhau về nội dung, các trang Web ở các cụm khác nhau thì không<br /> tương tự nhau. Dựa vào đặc trưng của mỗi trang Web, kỹ thuật phân cụm mờ xác định<br /> độ thuộc của trang Web vào một cụm và trọng tâm của cụm đó để thực hiện quá trình<br /> phân cụm kết quả tìm kiếm. Mô hình tiếp cận ở Hình 2 cũng như quá trình tìm kiếm và<br /> phân cụm kết quả sẽ được trình bày cụ thể trong mục dưới dây.<br /> 4.2. Kỹ thuật phân cụm kết quả tìm kiếm<br /> <br /> 4.2.1. Mô hình biểu diễn tài liệu Web<br /> Hầu hết các thuật toán phân cụm đều yêu cầu tập dữ liệu cần được phân cụm ở<br /> dạng một tập các véctơ xj = {xj1, xj2, …, xjm} trong không gian m chiều. Mỗi tài liệu j<br /> được mô tả bởi một véctơ xj – gọi là véctơ đặc trưng (feature vector) và mỗi phần tử của<br /> véctơ đặc trưng tương ứng với một từ của tập tài liệu. Việc tách lọc các đặc trưng cần<br /> thiết thông qua véctơ đặc trưng phụ thuộc nhiều vào từng lĩnh vực. Số chiều của véctơ<br /> đặc trưng là nhân tố chủ chốt trong thời gian chạy của thuật toán cũng như độ lớn của<br /> nó.<br /> Trong phân cụm tài liệu Web, hầu hết các kỹ thuật phân cụm thường sử dụng mô<br /> hình không gian véctơ (vector space) để biểu diễn các đối tượng dữ liệu. Mỗi trang Web<br /> được biểu diễn bằng một véctơ pj = {tfj1, tfj2, …, tfjn} trong đó tfjk (k = 1, …, n) là tần<br /> suất xuất hiện (TF-Term Frequency) của từ tk trong trang Web pj. Để biểu diễn tất cả<br /> các trang Web cùng với một tập từ thì cần tách tất cả các từ tìm được trên tổng các trang<br /> Web và sử dụng chúng như véctơ đặc trưng. Theo mô hình TF này thì trọng số wjk của<br /> từ tk trong trang Web pj được xác định theo một trong các công thức sau [10]: wjk = tf jk<br /> hoặc wjk = 1 + log(tfjk).<br /> Ngoài mô hình TF, các đối tượng dữ liệu có thể được biểu diễn dựa trên mô hình<br /> nghịch đảo tần suất xuất hiện (IDF-Inverse Document Frequency). Theo [10], nghịch<br /> đảo tần suất xuất hiện của từ tk trong trang trang Web pj được định nghĩa là idfjk =<br /> log(n/hk). Trong đó, n là tổng số trang Web và hk là số lượng trang Web có chứa từ tk.<br /> Một mô hình biểu diễn dữ liệu khác cũng thường được sử dụng trong phân cụm<br /> tài liệu Web đó là mô hình kết hợp TF-IDF. Với mô hình này, trọng số wjk của từ tk<br /> trong trang Web pj được định nghĩa như sau [10]:<br /> <br /> w jk = tf jk x idf jk<br /> <br /> (4.1)<br /> <br /> Trong đó:<br /> tfjk: là tần suất xuất hiện của từ tk trong trang Web pj;<br /> idfjk = log(n/hk) là nghịch đảo tần suất xuất hiện của từ tk trong trang Web pj;<br /> n: tổng số trang Web trong tập trang Web C;<br /> hk: số lượng trang Web có chứa từ tk.<br /> 4.2.2. Quá trình tìm kiếm và xử lý kết quả<br /> <br /> 54<br /> <br />