Xem mẫu
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ
TRONG KHAI PHÁ DỮ LIỆU WEB
Đỗ Quang Khôi1
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
để 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.
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
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
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
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
C-Means.
1. Giới thiệu
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
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
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
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
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
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
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
đã á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
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ờ).
Hơn nữa, World Wide Web (WWW) 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. Để đáp ứng phần nào nhu cầu tìm kiếm và sử dụng
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
cách áp dụng các kỹ thuật khai phá dữ liệu (KPDL) trong khai phá tài nguyên Web.
Trong đó, PCDL Web là một bài toán điển hình trong khai phá tài nguyên Web.
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ư
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,
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
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
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
dụng các kỹ thuật PCDL theo cách tiếp cận mờ trong KPDL Web.
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
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
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
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).
1
ThS, Trung tâm Học liệu, trường Đại học Quảng Nam
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …
2. Tổng quan về khai phá dữ liệu Web
Với sự phát triển nhanh chóng của Internet, các thông tin trên WWW đã trở thành
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,
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
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
cập và sử dụng thông tin, cung cấp một nguồn dữ liệu đồ sộ cho KPDL.
Hình 1. Phân loại KPDL Web.
Có nhiều khái niệm khác nhau về KPDL Web. Tuy nhiên, theo [6], [8], ta có khái
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
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
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
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à
khai phá theo sử dụng [8].
• Khai phá nội dung Web:
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
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
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
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
đí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
CSDL và các ứng dụng KPDL.
• Khai phá cấu trúc Web:
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
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ó
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
đượ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ư
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ệ.
51
ĐỖ QUANG KHÔI
• Khai phá theo sử dụng Web:
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
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
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
đố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
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
ghi sử dụng nhằm đem lại dữ liệu đúng đắn để khai phá.
3. Các hướng tiếp cận phân cụm tài liệu Web
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
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
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
thuật toán phân cụm tài liệu Web có thể chia làm các loại sau [9]:
• Phân cụm dựa trên văn bản:
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
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
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ả
năng hai tài liệu này là rất giống nhau.
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,
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
xác suất,...
• Phân cụm dựa trên liên kết:
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
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
đồ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
đượ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
siêu liên kết.
Ý 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
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
phân hoạch các tài liệu về các cụm.
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
toán PageRank (S. Brin và đồng nghiệp, 1998) và thuật toán HITS (J. M. Kleinberg,
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à
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,
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
đó, 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.
• Phân cụm lai ghép:
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
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
52
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …
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
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ó
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
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
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
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
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
bản mà còn có thể là hình ảnh, âm thanh, hay đa phương tiện.
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
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
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
cụm nội dung-liên kết (Weiss và đồng nghiệp, 1996), Toric k-means (Modha &
Spangler, 2000),...
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
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
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ể
và lĩnh vực ứng dụng.
4. Kỹ thuật PCDL mờ trong phân cụm kết quả tìm kiếm trên Web
4.1. Hướng tiếp cận
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
tương đương về một cụm. Có nhiều phương pháp để đánh giá mức độ quan trọng của
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
số cho trang. Các thuật toán PageRank, HITS,... đều dựa trên phương pháp này. Một
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
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
độ quan trọng tương đương và sẽ cùng thuộc về một cụm.
Hình 2. Mô hình tiếp cận phân cụm kết quả tìm kiếm
bằng kỹ thuật PCDL mờ.
53
ĐỖ QUANG KHÔI
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 đã
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
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
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
độ 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
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à
phân cụm kết quả sẽ được trình bày cụ thể trong mục dưới dây.
4.2. Kỹ thuật phân cụm kết quả tìm kiếm
4.2.1. Mô hình biểu diễn tài liệu Web
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 ở
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
đượ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
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
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ơ
đặ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
nó.
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ô
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
được biểu diễn bằng một véctơ pj = {tfj1, tfj2, …, tfjn} trong đó tfjk (k = 1, …, n) là tần
suất xuất hiện (TF-Term Frequency) của từ tk trong trang Web pj. Để biểu diễn tất cả
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
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
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
hoặc wjk = 1 + log(tfjk).
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
nghịch đảo tần suất xuất hiện (IDF-Inverse Document Frequency). Theo [10], nghịch
đảo tần suất xuất hiện của từ tk trong trang trang Web pj được định nghĩa là idfjk =
log(n/hk). Trong đó, n là tổng số trang Web và hk là số lượng trang Web có chứa từ tk.
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
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
trong trang Web pj được định nghĩa như sau [10]:
w jk = tf jk x idf jk
(4.1)
Trong đó:
tfjk: là tần suất xuất hiện của từ tk trong trang Web pj;
idfjk = log(n/hk) là nghịch đảo tần suất xuất hiện của từ tk trong trang Web pj;
n: tổng số trang Web trong tập trang Web C;
hk: số lượng trang Web có chứa từ tk.
4.2.2. Quá trình tìm kiếm và xử lý kết quả
54
nguon tai.lieu . vn
TRONG KHAI PHÁ DỮ LIỆU WEB
Đỗ Quang Khôi1
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
để 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.
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
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
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
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
C-Means.
1. Giới thiệu
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
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
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
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
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
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
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
đã á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
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ờ).
Hơn nữa, World Wide Web (WWW) 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. Để đáp ứng phần nào nhu cầu tìm kiếm và sử dụng
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
cách áp dụng các kỹ thuật khai phá dữ liệu (KPDL) trong khai phá tài nguyên Web.
Trong đó, PCDL Web là một bài toán điển hình trong khai phá tài nguyên Web.
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ư
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,
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
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
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
dụng các kỹ thuật PCDL theo cách tiếp cận mờ trong KPDL Web.
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
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
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
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).
1
ThS, Trung tâm Học liệu, trường Đại học Quảng Nam
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …
2. Tổng quan về khai phá dữ liệu Web
Với sự phát triển nhanh chóng của Internet, các thông tin trên WWW đã trở thành
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,
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
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
cập và sử dụng thông tin, cung cấp một nguồn dữ liệu đồ sộ cho KPDL.
Hình 1. Phân loại KPDL Web.
Có nhiều khái niệm khác nhau về KPDL Web. Tuy nhiên, theo [6], [8], ta có khái
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
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
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
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à
khai phá theo sử dụng [8].
• Khai phá nội dung Web:
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
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
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
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
đí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
CSDL và các ứng dụng KPDL.
• Khai phá cấu trúc Web:
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
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ó
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
đượ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ư
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ệ.
51
ĐỖ QUANG KHÔI
• Khai phá theo sử dụng Web:
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
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
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
đố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
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
ghi sử dụng nhằm đem lại dữ liệu đúng đắn để khai phá.
3. Các hướng tiếp cận phân cụm tài liệu Web
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
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
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
thuật toán phân cụm tài liệu Web có thể chia làm các loại sau [9]:
• Phân cụm dựa trên văn bản:
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
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
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ả
năng hai tài liệu này là rất giống nhau.
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,
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
xác suất,...
• Phân cụm dựa trên liên kết:
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
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
đồ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
đượ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
siêu liên kết.
Ý 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
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
phân hoạch các tài liệu về các cụm.
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
toán PageRank (S. Brin và đồng nghiệp, 1998) và thuật toán HITS (J. M. Kleinberg,
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à
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,
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
đó, 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.
• Phân cụm lai ghép:
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
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
52
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ …
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
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ó
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
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
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
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
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
bản mà còn có thể là hình ảnh, âm thanh, hay đa phương tiện.
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
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
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
cụm nội dung-liên kết (Weiss và đồng nghiệp, 1996), Toric k-means (Modha &
Spangler, 2000),...
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
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
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ể
và lĩnh vực ứng dụng.
4. Kỹ thuật PCDL mờ trong phân cụm kết quả tìm kiếm trên Web
4.1. Hướng tiếp cận
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
tương đương về một cụm. Có nhiều phương pháp để đánh giá mức độ quan trọng của
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
số cho trang. Các thuật toán PageRank, HITS,... đều dựa trên phương pháp này. Một
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
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
độ quan trọng tương đương và sẽ cùng thuộc về một cụm.
Hình 2. Mô hình tiếp cận phân cụm kết quả tìm kiếm
bằng kỹ thuật PCDL mờ.
53
ĐỖ QUANG KHÔI
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 đã
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
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
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
độ 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
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à
phân cụm kết quả sẽ được trình bày cụ thể trong mục dưới dây.
4.2. Kỹ thuật phân cụm kết quả tìm kiếm
4.2.1. Mô hình biểu diễn tài liệu Web
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 ở
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
đượ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
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
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ơ
đặ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
nó.
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ô
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
được biểu diễn bằng một véctơ pj = {tfj1, tfj2, …, tfjn} trong đó tfjk (k = 1, …, n) là tần
suất xuất hiện (TF-Term Frequency) của từ tk trong trang Web pj. Để biểu diễn tất cả
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
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
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
hoặc wjk = 1 + log(tfjk).
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
nghịch đảo tần suất xuất hiện (IDF-Inverse Document Frequency). Theo [10], nghịch
đảo tần suất xuất hiện của từ tk trong trang trang Web pj được định nghĩa là idfjk =
log(n/hk). Trong đó, n là tổng số trang Web và hk là số lượng trang Web có chứa từ tk.
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
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
trong trang Web pj được định nghĩa như sau [10]:
w jk = tf jk x idf jk
(4.1)
Trong đó:
tfjk: là tần suất xuất hiện của từ tk trong trang Web pj;
idfjk = log(n/hk) là nghịch đảo tần suất xuất hiện của từ tk trong trang Web pj;
n: tổng số trang Web trong tập trang Web C;
hk: số lượng trang Web có chứa từ tk.
4.2.2. Quá trình tìm kiếm và xử lý kết quả
54