ĐỀ ÁN

Áp dụng kỹ thuật phân
cụm dữ liệu trong phân
cụm kết quả tìm kiếm 1
Áp dụng kỹ thuật phân cụm dữ liệu trong phân cụm kết quả tìm kiếm
The Application of data clustering technique in the
result classification data searching
Vũ Đức Thi
1
, Hoàng Văn Dũng
2

Abstract
Nowadays, searching information with big data is one of main subjects for
data mining. In this paper we would like to introduce an approach to search and
classify web documents by using data clustering technique, we solve the
mathematical problem according to three main phases: search Web documents,
data preprocessing, presenting data with vector models and cluster web
documents.
Từ khóa: data mining, phân cụm dữ liệu, phân cụm Web…
1. Giới thiệu
Ngày nay, nhờ sự cải tiến không ngừng của các Search engine về cả chức
năng tìm kiếm lẫn giao diện đã giúp cho người sử dụng dễ dàng hơn trong việc
tìm kiếm thông tin trên web. Tuy nhiên, người sử dụng thường vẫn phải duyệt
qua hàng trăm thậm chí hàng ngàn trang Web mới có thể tìm kiếm được thứ mà

và các phần tử ở các cụm khác nhau thì “phi tương tự” với nhau.
Từ tập S-R, ta tìm cách đưa các phần tử này vào một trong k cụm đã được
thiết lập ở trên. Những phần tử nào “tương tự” với trọng tâm cụm (theo một
ngưỡng xác định nào đó) thì đưa vào cụm này, những phần tử không thỏa mãn
xem như không phù hợp với truy vấn và loại bỏ nó khỏi tập kết quả. Kế tiếp, ta
đánh trọng số cho các cụm và các trang trong tập kết quả theo thuật toán sau:
Đầu vào: tập dữ liệu D chứa các trang gồm k cụm và k trọng tâm
Đầu ra: trọng số của các trang
Phương pháp
B1: Mỗi cụm dữ liệu thứ m và trọng tâm C
m
ta gán cho nó một trọng số ts
m
.

Với các trọng tâm C
i
, C
j
bất kỳ ta luôn có ts
i
>ts
j
nếu t
i
tương tự với truy vấn
hơn t
j
.
B2: Với mỗi trang p trong cụm m ta xác định trọng số trang là pw. Với mọi

cách tiếp cận mờ.
3. Quá trình tìm kiếm và phân cụm tài liệu
Về cơ bản, quá trình phân cụm kết quả tìm kiếm sẽ diễn ra theo các bước
chính được thể hiện như Hình 2 [14]:
- Tìm kiếm các trang Web từ các Website thỏa mãn nội dung truy vấn.
- Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL
tương ứng.
- Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang Web
thành các cụm, sao cho các trang trong cụm “tương tự” về nội dung với nhau
hơn các trang ngoài cụm.

Hình 2. Các bước phân cụm kết quả tìm kiếm trên Web
Dữ liệu web
Tìm kiếm và
trích rút dữ liệu
Tiền xử lý
Biểu diễn
dữ liệu
Phân cụm và xác
định trọng số trang
Biểu diễn
kết quả
4
3.1. 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ập từ khóa tìm kiếm để
tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt, URL,…
tương ứng với các trang đó.

Để đơn giản trong ứng dụng thực tế, ta có thể tổ chức thành một danh sách
các từ dừng để xoá bỏ nó và sử dụng định luật Zipf để xóa bỏ các từ có tần số
xuất hiện thấp hoặc quá cao.
3.2.3. Kết hợp các từ có cùng gốc
Hầu hết trong các ngôn ngữ đều có rất nhiều từ có chung nguồn gốc với
nhau, chúng mang ý nghĩa tương tự nhau. Để giảm bởt số chiều trong biểu diễn
văn bản, ta sẽ kết hợp các từ có cùng gốc thành một từ. Theo một số nghiên
cứu[2] việc kết hợp này sẽ giảm được khoảng 40-50% kích thước chiều trong
biểu diễn văn bản.
Ví dụ trong tiếng Anh các từ user, users, used, using có cùng từ gốc và sẽ
được quy về là use; các từ engineering, engineered, engineer có cùng từ gốc sẽ
được quy về là engineer.
Ví dụ xử lý từ gốc trong tiếng Anh:
- Nếu một từ kết thúc bằng “ing” thì xóa “ing”, ngoại trừ trường hợp sau
khi xóa còn lại một ký tự hoặc còn lại “th”.
- Nếu một từ kết thúc bằng “ies” nhưng không phải là “eies” hoặc “aies” thì
thay thế “ies” bằng “y”
- Nếu một từ kết thúc bằng “es” thì bỏ “s”.
- Nếu một từ kết thúc bằng "s" và đứng trước nó là một phụ âm khác “s” thì
xóa “s”.
- Nếu một từ kết thúc bằng “ed”, nếu trước nó là một phụ âm thì xóa “ed”
ngoại trừ sau khi xóa từ chỉ còn lại một ký tự, nếu đứng trước là nguyên âm “i”
thì đổi “ied” thành “y”.
3.3. Biểu diễn tài liệu
Đây là giai đoạn số hoá và đưa văn bản về dạng thuận lợi cho quá trình xử
lý, ở đây ta có thể sử dụng mô hình vector để biểu diễn tài liệu.
3.3.1. Xây dựng từ điển
Việc xây dựng từ điển là rất quan trọng trong quá trình vector hóa văn bản,
từ điển sẽ gồm các từ/cụm từ riêng biệt trong toàn bộ tập tài liệu. Có thể tổ chức



Trong đó:
tf
ij
là tần số xuất hiện của t
i
trong tài liệu d
j

idf
ij
là tần số văn bản nghịch đảo của thuật ngữ t
i
.
h
i
là số các tài liệu mà t
i
xuất hiện.
n là tổng số tài liệu.
W
ij
=
)log()]log(1[
i
ijijij
h
n
tfidftf 
nếu t

Hình 3. Thuật toán k-means trong phân cụm nội dung tài liệu Web
Trong thuật toán k-means, chất lượng phân cụm được đánh giá thông qua
hàm tiêu chuẩn




k
i
x
i
C
mxE
i
D
1
2
)(
, trong đó x là các vector biểu diễn tài
liệu, m
i
là các trọng tâm của các cụm, k là số cụm, C
i
là cụm thứ i.
Độ phức tạp của thuật toán k-means là O((n.k.d).r).
Trong đó: n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều, r là
số vòng lặp.
Sau khi phân cụm xong tài liệu, trả về kết quả là các cụm dữ liệu và các
trọng tâm tương ứng.
3.5. Biểu diễn kết quả

Tiền xử lý và biểu
diễn văn bản
Phân cụm
tài liệu
50
10
0,206
0,957
50
15
0,206
1,156
100
10
0,353
2,518
100
15
0,353
3,709
150
10
0,515
4,553
150
15
0,515
5,834
250
10

[10] Oren Zamir and Oren Etzioni, Web document Clustering: A Feasibility
Demonstration, University of Washington, USA, ACM, 1998.
[11] Periklis Andritsos, Data Clusting Techniques, University Toronto,2002.
[12] Raghu Krishnapuram, Anupam Joshi, and Liyu Yi, A Fuzzy Relative of the K -
Medoids Algorithm with Application toWeb Document and Snippet Clustering, 2001
[13] Wang Jicheng, Huang Yuan, Wu Gangshan, and Zhang Fuyan, Web Mining:
Knowledge Discovery on the Web, IEEE, 1999.
[14] Wenyi Ni, A Survey of Web Document Clustering, Southern Methodist
University, 2004.
[15] Zifeng Cui, Baowen Xu , Weifeng Zhang, Junling Xu, Web Documents
Clustering with Interest Links, IEEE, 2005.