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

 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]: 
xjk jk jkw tf idf= (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ả 
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ  
 55 
Về cơ bản, quá trình tìm kiếm và phân cụm kết quả tìm kiếm bằng kỹ thuật phân 
cụm mờ sẽ diễn ra theo các bước như sau [9]: 
i. Tìm kiếm dữ liệu trên Web: 
Nhiệm vụ chủ yếu của giai đoạn này là dựa vào từ khóa tìm kiếm để tìm kiếm và 
trả về một tập các trang Web bao gồm nội dung, tiêu đề, mô tả tóm tắt, URL, tương 
ứng với mỗi trang. 
ii. Tiền xử lý dữ liệu: 
Đây là giai đoạn vô cùng quan trọng, nó ảnh hưởng rất lớn đến quá trình thực hiện 
phân cụm. Nhiệm vụ của giai đoạn này là làm giảm số từ trong mỗi tài liệu, do vậy nó 
có tác dụng làm giảm độ phức tạp tính toán của các giai đoạn sau và nâng cao hiệu quả 
cho giai đoạn kế tiếp. Đây là quá trình làm sạch dữ liệu và chuyển dịch các tài liệu 
thành các dạng biểu diễn dữ liệu thích hợp. 
Giai đoạn này bao gồm các công việc như sau: 
Chuẩn hóa văn bản: chuyển văn bản thô về dạng văn bản sao cho việc xử lý sau 
này được dễ dàng, đơn giản, thuật tiện, chính xác so với việc xử lý trực tiếp trên văn bản 
thô mà ảnh hưởng ít đến kết quả xử lý, như: xóa các thẻ HTML và các loại thẻ khác để 
trích ra các từ/cụm từ; Chuyển các ký tự hoa thành các ký tự thường; Xóa bỏ các dấu 
câu, xoá các ký tự trắng dư thừa,... 
Loại bỏ stop-words: stop-words là những từ mà xuất hiện quá nhiều trong kết quả 
nhưng không giúp ích gì trong việc phân biệt nội dung của các tài liệu. Ví dụ: Trong 
tiếng Việt các từ như “thì”, “mà”, “và”, “hoặc”,...; trong tiếng Anh các từ như “a”, “an”, 
“the”, “of”, “to”, “on”, “by”,...; Vì đặc điểm của stop-words nên chúng được loại bỏ mà 
không ảnh hưởng đến các giai đoạn sau. 
Chuyển đổi về từ gốc: loại bỏ tiền tố và hậu tố của từ để biến đổi nó thành từ gốc. 
Vì trong thực tế một từ gốc có thể có nhiều hình thái biến đổi, chẳng hạn như động từ, 
danh từ, tính từ, trạng từ; và giữa chúng có mối quan hệ ngữ nghĩa. Ví dụ như những từ: 
“clusters”, “clustering”, “clustered” là có cùng mối quan hệ với từ “cluster”. 
iii. Xây dựng từ điển: 
Từ điển bao gồm các từ riêng biệt trong tập các trang Web từ kết quả truy vấn. Từ 
điển là một bảng bao gồm các từ, chỉ số của nó trong từ điển và được sắp xếp theo thứ 
tự. Theo [5], [7], [10] từ điển được xây dựng với 500 phần tử sau khi được chuẩn hóa là 
phù hợp. 
iv. Tạo ma trận tài liệu: 
Ma trận tài liệu T được tạo bằng cách đếm số lần xuất hiện của mỗi từ từ ti trong 
mỗi trang Web pj. 
v. Véctơ hóa tài liệu: 
Giai đoạn này tính tf và idf, xác định trọng số W theo công thức (4.1) cho tất cả các 
từ của mỗi trang Web và véc tơ hóa tất cả các trang Web. 
vi. Phân cụm kết quả tìm kiếm bằng thuật toán FCM: 
ĐỖ QUANG KHÔI 
 56 
1
1
( )
; 1
( )
n
m
ik k
k
i n
m
ik
k
u x
v i c
u
=
=
= ≤ ≤
∑
∑
2
1
1
1 ; 1 ;1ik
mc
ik
j jk
u k n i c
d
d
−
=
= ≤ ≤ ≤ ≤
⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠∑
™ Tư tưởng thuật toán: 
Thuật toán FCM thực hiện phân cụm bằng một chuỗi các phép lặp các công thức [4]: 
 (4.2), và: 
 (4.3) 
để tối ưu các phân hoạch mờ của tập dữ liệu dựa trên việc tính toán độ tương tự có trọng 
số giữa đối tượng xk và trọng tâm của cụm i. Sau mỗi vòng lặp, thuật toán tính toán và 
cập nhật lại phần tử ujk trong ma trận phân hoạch U. Thuật toán sẽ dừng lại khi 
( 1)k k
ij iju u ξ+ − < , trong đó ξ ∈ [0, 1] là ngưỡng kết thúc cho trước. 
™ Phát biểu bài toán: 
Input: số cụm c; tham số mờ m ∈ [1, ∞), số vòng lặp tối đa Kmax và ngưỡng kết 
thúc ξ ∈ [0, 1]. 
Output: c cụm dữ liệu sao cho hàm tiêu chuẩn [4]: 
 2
1 1
( , ) ( ) ( , )
n c
m
m ik k i
k i
J U V u d x v
= =
=∑∑ đạt giá trị cực tiểu. 
™ Thuật toán [4]: 
1. Khởi tạo ma trận U = [uij], chọn ma trận ban đầu U(0)  Mfc; 
Tại bước k, k = 0, 1, ..., Kmax: 
2. Cập nhật trọng tâm của cụm ( )kiv , i = 1, 2, ..., c theo công thức (4.2); 
3. Cập nhật ma trận thành viên (độ thuộc) ( 1) ( 1)[ ]k kikU u
+ += theo công thức 
(4.3); 
4. Nếu ( 1) ( )k kU U ξ+ − < thì thực hiện bước 5; ngược lại, đặt U(k) = U(k+1), quay 
lại bước 2; 
5. Đưa ra các cụm kết quả. 
™ Thuật toán FCM trong phân cụm kết quả tìm kiếm trang Web: 
1. Khởi tạo ngẫu nhiên ma trận độ thuộc ban đầu U(0) = [uij], với uij là độ thuộc 
của trang Web pj đối với cụm ci; 
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ  
 57 
Tại bước k, k = 0, 1,..., Kmax: 
2. Cập nhật trọng tâm của các cụm ( )kiv , i = 1, 2,..., c theo công thức (4.2); 
3. Dựa vào ma trận trọng số của các từ trong mỗi trang Web pj (công thức 4.1), 
xác định độ đo tương tự dựa trên khoảng cách giữa nó với cụm ci. Cập nhật lại ma trận 
độ thuộc ( 1) ( 1)[ ]k kikU u
+ += theo công thức (4.3); 
4. Nếu ( 1) ( )k kU U ξ+ − < thì thực hiện bước 5; ngược lại, đặt U(k) = 
U(k+1), quay lại bước 2; 
5. Đưa ra các cụm kết quả. 
Trong đó: 
X = {x1, x2, ..., xn}  Rn, là tập dữ liệu ban đầu; 
c: là số cụm dữ liệu trong X; 
m: là trọng số mũ, hay được gọi là tham số mờ, 1 ≤ m < ∞; 
U = [uik], là ma trận phân hoạch mờ của X trong C cụm, U  Mfc; 
uik  [0, 1]: độ thuộc của đối tượng xk đối với cụm i; 
V = [vji] = (v1, v2, ..., vc), là ma trận biểu diễn các đối tượng trọng tâm của cụm; 
vi = (vi1, vi2, ..., vin), là trọng tâm của cụm i; 
2 ( , )k id x v : là khoảng cách Euclide từ đối tượng xk đến trọng tâm của cụm thứ i. 
5. Kết quả thực nghiệm 
Áp dụng kỹ thuật phân cụm dữ liệu mờ trong KPDL Web được chúng tôi thực 
nghiệm thông qua một 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 cả 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 FCM nhằm có sự so sánh kết quả phân 
cụm của hai kỹ thuật phân cụm rõ và phân cụm mờ. 
5.1. Cài đặt hệ thống 
5.1.1. Kiến trúc hệ thống 
ĐỖ QUANG KHÔI 
 58 
Hình 3. Kiến trúc hệ thống của chương trình thử nghiệm. 
Chương trình thử nghiệm được chạy trên môi trường .NET Framework 4.0 với 
ngôn ngữ lập trình Visual Basic 2005 và CDSL được quản lý và lưu trữ bằng SQL 
Server 2005. Hệ thống được thiết kế như Hình 3 ở trên. 
Chương trình được kết nối với máy tìm kiếm Google bằng cách sử dụng một số 
hàm trong API của Google để lấy dữ liệu là kết quả truy vấn tìm kiếm từ Google để lưu 
vào CSDL của hệ thống phục vụ cho quá trình phân cụm. 
Việc tìm kiếm được thực hiện bằng cách sử dụng máy tìm kiếm Google để tìm 
kiếm tự động, chương trình sẽ dựa vào URL để lấy toàn văn của tài liệu đó và lưu trữ lại 
phục vụ cho quá trình tìm kiếm và phân cụm sau này. 
5.1.2. Thiết kế CSDL 
CSDL của chương trình bao gồm các bảng chính sau đây: 
¾ Bảng 1: đây là bảng lưu trữ từ điển. 
Tên trường Kiểu dữ liệu Mô tả 
PhraseID Int Khóa chính, chỉ số của mỗi từ 
Phrase Nvarchar Từ cần lưu trữ 
¾ Bảng 2: đây là bảng lưu trữ nội dung của trang Web được lấy về từ kết quả 
tìm kiếm của Yahoo. 
API 
Kết quả
phân cụm
Người dùng 
 Máy 
tìm kiếm 
Google 
Truy vấn 
đến Google
Kết quả 
truy vấn
Kết quả
truy vấn
Từ khóa 
tìm kiếm 
CSDL 
Quá trình 
phân cụm 
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ  
 59 
Tên trường Kiểu dữ liệu Mô tả 
PageID Int Khóa chính 
URL Nvarchar URL của trang Web 
Snipet Nvarchar Trích đoạn của nội dung trang Web 
Content Nvarchar Nội dung của trang Web 
IsTokenozed Bit Cho biết trang Web này đã được tách từ hay chưa 
IsClustered Bit Cho biết trang Web này đã được phân cụm hay chưa 
ClusterID Int Khóa ngoài, liên kết đến bảng Clusters, cho biết trang Web thuộc cụm nào sau khi được phân cụm 
¾ Bảng 3: đây là bảng liên kết giữa các trang Web và từ điển 
Tên trường Kiểu dữ liệu Mô tả 
DicPageID Int Khóa chính 
PageID Int Khóa ngoài, liên kết đến bảng Pages 
PhraseID Int Khóa ngoài, liên kết đến bảng Dictionary 
Score Float Cho biết tần suất xuất hiện của các từ trong trang Web 
¾ Bảng 4: đây là bảng lưu trữ các cụm đã tìm được 
Tên trường Kiểu dữ liệu Mô tả 
ClusterID Int Khóa chính, chỉ số của cụm 
Lable Nvarchar Nhãn của cụm 
5.1.3. Quá trình tìm kiếm và phân cụm được tóm tắt lại như sau: 
Input: 
+ Một tập các trang Web P tìm được theo truy vấn; 
+ Tham số mờ hóa m. 
Output: 
+ Các trang Web được phân cụm theo thuật toán k-means hoặc FCM. 
Các bước thực hiện: 
Bước 1: Tiền xử lý; 
Bước 2: Xây dựng từ điển; 
Bước 3: Tạo ma trận tài liệu; 
Bước 4: Véctơ hóa tài liệu; 
ĐỖ QUANG KHÔI 
 60 
Bước 5: Xử lý phân cụm; 
Bước 6: Hiển thị kết quả phân cụm. 
5.1.4. Một số giao diện chính của chương trình: 
Hình 4. Giao diện nhập từ khóa cần tìm. 
Hình 5. Giao diện hiển thị kết quả tiền xử lý và véctơ hóa trang Web 
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ  
 61 
Hình 6. Giao diện kết quả phân cụm bằng FCM. 
5.2. Kết quả 
Với từ khóa “cluster”, khi thực hiện tiền xử lý và phân cụm với hai thuật toán k-
means và FCM (với tham số mờ hóa m = 2.0; ngưỡng kết thúc ξ = 0.05) trên tập dữ liệu 
với hơn 4000 trang web, chương trình cho kết quả như sau: 
Bảng 6. Bảng so sánh thời gian thực hiện hai thuật toán FCM và k-means. 
Thời gian trung bình (giây) 
Phân cụm Số trang Số cụm 
Tiền xử lý 
k-mean FCM (m=2.0) 
100 10 0.85 1.319 7.167 
100 20 0.85 1.926 11.408 
200 10 0.95 2.452 25.731 
200 20 0.95 4.524 37.268 
300 10 0.102 4.588 39.902 
300 20 0.102 7.469 54.118 
400 10 0.131 8.171 62.996 
ĐỖ QUANG KHÔI 
 62 
Thời gian trung bình (giây) 
Phân cụm Số trang Số cụm 
Tiền xử lý 
k-mean FCM (m=2.0) 
400 20 0.131 11.182 79.701 
500 10 0.142 12.526 92.631 
500 20 0.142 16.986 149.390 
1000 10 0.189 22.124 306.447 
1000 20 0.189 43.935 496.282 
Qua kết quả trên, ta thấy rằng thời gian thực hiện thuật toán phụ thuộc vào độ lớn 
của tập dữ liệu và số cụm cần phân cụm. Riêng với thuật toán FCM còn phụ thuộc vào 
tham số mờ hóa m và ngưỡng kết thúc ξ. Nếu tham số mờ hóa m và ngưỡng kết thúc ξ 
được xác định tốt thì chất lượng và thời gian thực hiện phân cụm được cải thiện rất 
nhiều. Không có quy tắc nào để lựa chọn một tham số mờ hóa m tối ưu. Cho đến nay, có 
lẽ chiến lược tốt nhất để chọn được giá trị tối ưu cho m đó là thử nghiệm với các giá trị 
khác nhau của m, từ đó chọn m cho kết quả phân cụm tốt nhất. Đối với hầu hết dữ liệu, 
m  [1.5, 3.0] thường cho kết quả tốt [4]. Với đánh giá này, chương trình thực nghiệm 
đã cho kết quả tương tự. 
Chính vì vậy, thuật toán FCM cho kết quả thời gian thực hiện phân cụm lâu hơn 
thuật toán k-means. Tuy nhiên, qua khảo sát kết quả các cụm thì chất lượng của các 
cụm khi thực hiện với thuật toán FCM cho hiệu quả cao hơn thuật toán k-means bởi vì 
các trang Web trong cùng một cụm có nội dung tương tự với nhau hơn và FCM có khả 
năng phân cụm đối với những trang Web cùng thuộc về những chủ đề khác nhau, 
nghĩa là các cụm có thể chồng chéo lên nhau. 
TÀI LIỆU THAM KHẢO 
Tiếng Việt: 
[1] Đoàn Văn Ban (2003), Bài giảng Khai thác kho dữ liệu, Viện Công nghệ 
thông tin Việt Nam, Hà Nội. 
[2] Hồ Thuần và Đặng Thanh Hà (2007), Lôgic mờ và ứng dụng, NXB Đại học 
Quốc gia Hà Nội, Hà Nội. 
Tiếng Anh: 
[3] Periklis Andritsos (2002), Data Clusting Techniques, University of Toronto, 
Toronto. 
ÁP DỤNG KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ TRONG KHAI PHÁ  
 63 
[4] James C. Bezdek (1984), “FCM: The fuzzy c-means clustering algorithm”, 
Computer and Geosciences, vol. 10 (2-3), pp. 191-203. 
[5] Christian Borgelt and Andreas Nurnberger (2004), Fast Fuzzy Clustering of 
Web Page Collections, PKDD Workshop on Statistical Approaches for Web 
Mining SAWM, Pisa. 
[6] Jiawei Han, Micheline Kamber and Jian Pei (2011), Data Mining: Concepts 
and Techniques, 3rd Edition, Morgan Kaufmann Publishers, Waltham. 
[7] Raghu Krishnapuram, Anupam Joshi, and Liyu Yi (1999), “A Fuzzy Relative 
of the k-Medoids Algorithm with Application to Web Document and Snippet 
Clustering”, IEEE International Fuzzy Systems Conference Proceedings, vol. 
3, pp. 1281-1286. 
[8] Bing Liu (2007), Web Data Mining, Springer, New York. 
[9] Maofu Liu, Yanxiang He and Huijun Hu (2004), Web Fuzzy Clustering and 
Its Applications in Web Usage Mining, Proceedings of 8th International 
Symposium on Feature Software Technology (ISFST-2004). 
[10] Wenyi Ni (2004), A Survey of Web Document Clustering, Southern 
Methodist University, Dallas. 
Title: THE APPLICATION OF FUZZY DATA CLUSTERING TECHNIQUE IN 
WEB DATAMINING 
DO QUANG KHOI 
Quang Nam University 
Abstract: World Wide Web is a huge data warehouse. Therefore, using Web 
mining to discover useful information and knowledge is of important meaning. For 
that purpose, this article provides an overview of the Web data mining and Web 
document clustering approaches. Thus, this article introduces the Web fuzzy clustering 
processing model and also presents specifically the process of Web document searching 
and clustering by fuzzy data clustering technique with Fuzzy C-Means algorithm.