MỤC LỤC
1
GOM CỤM DỮ LIỆU
I. Giới thiệu
Ngày nay sự phát triển nhanh chóng của mạng Internet đã sinh ra một khối
lượng khổng lồ các dữ liệu, để khai thác dữ liệu ấy 1 cách chính xác và hiệu
quả là 1 vấn đề được đặt ra.
Có nhiều hướng tiếp cận khác nhau để giải quyết vấn đề này. Các hướng
này thường chú ý giảm sự nhập nhằng bằng các phương pháp lọc hay thêm
các tùy chọn để cắt bớt thông tin và hướng biểu diễn các thông tin trả về bởi
các máy tìm kiếm thành từng cụm để cho người dùng có thể dễ dàng tìm
được thông tin mà họ cần. Đã có nhiều thuật toán phân cụm tài liệu dựa trên
phân cụm ngoại tuyến toàn bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu của
các máy tìm kiếm là quá lớn và luôn thay đổi thì khó có thể phân cụm ngoại
tuyến. Do đó, việc phân cụm phải được ứng dụng trên tập các tài liệu nhỏ
hơn được trả về từ các truy vấn và thay vì trả về một danh sách rất dài các
thông tin gây nhập nhằng cho người sử dụng cần có một phương pháp tổ
chức lại các kết quả tìm kiếm một cách hợp lý.
Hiện nay, đã có nhiều kỹ thuật, thuật toán về thu thập, phân cụm dữ liệu tự
động tuy nhiên hầu hết các kỹ thuật này khi phân cụm đều yêu cầu xác định số
cụm cần thực thi đặc biệt là với thuật toán K-means hoặc yêu cầu mức độ khác
biệt trong việc xác định các thành phần có tính chất giống nhau. Ngoài ra, các
kỹ thuật này còn đòi hỏi phải chọn trước số điểm làm trọng tâm, với số điểm
chọn ngẫu nhiên làm trọng tâm này sẽ cho các kết quả khác nhau. Do vậy,
các kết quả trên có thể là không chính xác, với mức độ sai số có thể rất lớn.
Để khắc phục nhược điểm trên, việc cải tiến thuật toán K- means trong thu
thập, phân cụm tài liệu và thay vì chọn số điểm làm trọng tâm, chúng ta không
chọn số điểm làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm
bằng cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng lớn nhất và
tính lại trọng tâm các cụm
II. Tóm tắt lý thuyết

tùy thuộc vào: lọai dữ liệu khảo sát và lọai tương tự cần thiết.
Tương tự và không tương tự giữa hai đối tượng thường được biểu
diễn qua khoảng cách(x,y)
c. Các loại dữ liệu trong phân tích cụm
- Các biến khoảng tỉ lệ
- Biến nhị phân
3
- Các biến định danh, thứ tự, tỉ lệ
- Các biến có kiểu hỗn hợp
- Các kiểu dữ liệu phức tạp
d. Các phưong pháp gom cụm chính yếu
- Các phương pháp phân hoạch
- Các phương pháp phân cấp
- Các phương pháp dựa trên mật độ
- Các phương pháp dựa trên mô hình (gom cụm khái niệm, mạng
neural)
e. Các phương pháp phân hoạch
- Phương pháp phân hoạch: tạo phân hoạch CSDL D có n đối
tượng thành tập có k cụm sao cho:
 Mỗi cụm chứa ít nhất một đối tượng
 Mỗi đối tượng thuộc về một cụm duy nhất
 Cho trị k, tìm phân hoạch có k cụm sao cho tối ưu hoá tiêu
chuẩn phân hoạch được chọn
- Tiêu chuẩn suy đoán chất lưọng phân hoạch
 Tối ưu toàn cục: liệt kê vét cạn tất cả các phân hoạch
- Các phương pháp heuristic:
 K-means: mỗi cụm được đại diện bằng trọng tâm của cụm
(centroid)
 K-medoids: mỗi cụm được đại diện trong các đối tượng
của cụm (medoid)

các điểm còn lại này vào một trong hai cluster, những điểm có màu trắng
vào cluster 1, những điểm có màu đen vào cluster 2. Hiệu chỉnh lại tâm
của hai cluster, điểm màu xám là tâm mới của hai cluster. Tính lại các
khoảng cách các điểm đến tâm mới và gán lại các điểm này. Tiếp tục hiệu
chỉnh lại tâm của hai cluster. Rồi, lặp lại cho đến khi không còn sự thay đổi
nữa thì dừng
5
Hình 1: Minh họa thuật toán K-means
Độ phức tạp của thuật toán này là O(tKn). Trong đó n là số mẫu
trong CSDL, K là số cluster, t là số lần lặp.
Nhận xét:
Điểm mạnh của phương pháp gom cụm k- means:
- Có thể scalable trong khi xử lý dữ liệu lớn
- Hiệu suất tương đối: O(tkn), với n là số đối tượng, k là số cụm, t
là số lần lập. thông thường k, t << n
- Thường kết thúc ở tối ưu cục bộ, có thể tìm được tối ưu toàn
cục,dùng kỹ thuật thuật giải di truyền
Điểm yếu của phương pháp gom cụm k- means:
- Có thể áp dụng chỉ khi xác định được trị trung bình
- Cần chỉ định trước k, số các cụm
- Không thể xử lý nhiễu và outliers
- Không thích hợp nhằm khám phá các cụm có dạng không lồi hay
các dạng có kích thước khác nhau
b. Thuật toán K-Medoid
Ý tưởng: Để tìm ra k cụm với n đối tượng thì k-medoids chọn ngẫu
nhiên k đối tượng vào k cụm, coi mỗi đối tượng này là tâm của cụm. Phân
bổ các đối tượng còn lại vào cụm mà sự khác nhau của nó với đối tượng
6
tâm của cụm là gần nhất. Sau đó lặp lại quá trình: Thay đổi đối tượng tâm
của mỗi cụm sao cho chất lượng của cụm được cải thiện. Chất lượng

random
thì p được gán lại vào O
random
Các trường hợp đối với điểm p
Thuật toán K-medoid được mô tả như sau:
Input: Số nguyên k và CSDL gồm n đối tượng cần phân cụm.
Output: Một tập gồm k cụm mà tổng giá trị của sự khác nhau của tất
cả các đối tượng đến đối tượng tâm của nhóm chứa nó là nhỏ nhất.
Thuật toán:
7
Bước 1: Chọn k đối tượng bất kì vào k cụm. Coi mỗi đối tượng này
là tâm của nhóm.
Bước 2: Lặp
Bước 3: Gán mỗi đối tượng còn lại vào một cụm mà nó gần với đối
tượng tâm của cụm nhất.
Bước 4: Chọn ngẫu nhiên một đối tượng không là đối tượng tâm,
O
random
.
Bước 5: Tính lại giá trị, S, đối với việc đổi Oj với O
random
.
Bước 6: Nếu S<0 thì đổi Oj với Orandom để tạo ra một tập với đối
tượngtâm mới.
Bước 7: Đến khi không có sự thay đổi nào nữa thì dừng
Ví dụ: Trong không gian hai chiều cho n = 10 điểm, cần chia thành
k =2 cụm. Các bước thực hiện của thuật toán K-medoids được chỉ ra
trong hình sau:
Đầu tiên, chọn hai điểm bất kì vào hai cụm (điểm màu đen), rồi xét
các điểm còn lại và đưa chúng vào một trong hai cụm với điểm tâm lần

means bắt đầu bằng cách chọn k cụm và chọn ngẫu nhiên k điểm làm
trung tâm cụm, hoặc chọn phân hoạch ngẫu nhiên k cụm và tính trọng tâm
của từng cụm này. Việc chọn ngẫu nhiên k điểm làm trung tâm cụm như
đã nói ở trên có thể cho ra các kết quả khác nhau tùy vào chọn k điểm
này.
9
Thuật toán K-means cải tiến:
Bước 1: Khởi tạo giá trị ban đầu cho K: K=1
Bước 2:
Bước 2.1: Kiểm tra điều kiện K
Nếu K=1: chọn bất kỳ một điểm làm trung tâm của cụm.
Nếu K>1: thêm trung tâm của cụm mới vào cụm có biến
dạng max.
Bước 2.2: Gán từng điểm vào cụm có trung tâm gần nhất với
điểm đang xét và cập nhật lại trung tâm cụm
Bươc 2.3: Nếu trung tâm cụm không thay đổi, chuyển sang
bước 3.
Ngược lại, quay trở lại bước 2.2 (bước 2).
Bước 3: (Tăng số cụm)
Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở lại bước 2.1
(bước 2).
Ngược lại, thuật toán dừng.
Với thuật toán K-means cải tiến: đưa ra sự khác biệt, đó là mức độ
biến dạng của các cụm (dựa trên biến dạng để phân cụm).Mức độ biến
dạng của các cụm được tính như sau:
I=S-N(d(w,x ))
Trong đó: w: trung tâm của cụm, N: Số các thành phần trong cụm;
S: Tổng bình phương khoảng cách giữa các thành phần trong cụm và
trung tâm của không gian Euclidean; I: Mức độ biến dạng của cụm; d(w,x):
là khoảng cách giữa trung tâm w của cụm và trung tâm của không gian

cụm là những điểm có tọa độ (x, y), và ta sẽ gom chúng lại trong k cụm
cho trước. Chương trình chỉ mặc định tối đa là 9 cụm cho phép.
b. Mô tả
Input: Tập các điểm {Xi=(x,y)}, Số cụm cần gom: K
11
Output : C
i
={(x,y}, i=1 K
- Chọn K Điểm X
i
, i=1 K làm K tâm điểm. Và các điểm X
i
nằm trong cụm C
i
- Với mỗi điểm x trong tập X
i
o B1:Tính khoảng cách từ x đến tất cả các tâm điểm.
o B2:Điểm x sẽ được đưa vào cụm nào mà khoảng
các từ nó đến cụm đó là nhỏ nhất.
o B3:Tính lại tọa độ các tâm điểm.
o Lập lại bước 1 đến bước 3 cho đến khi không còn
sự thay đổi nhóm của các điểm
c. Kiểm nghiệm chương trình
Với 4 điểm: X1(1,1), X2(2,1), X3(4,3), X4(5,4)
Lấy 2 điểm X1, X2 làm trọng tâm là C1(X1), C2(X2)
Lần lược xem xét từng điểm X1,X2, X3, X4 để xem chúng thuộc vào
nhóm nào.
B1: Tính khoảng cách
d(X3,C1)= (4-1)^2+(3-1)^2=13
d(X3,C2)= (4-2)^2+(3-1)^2=8

 X2 thuộc C1
d(X3,C1)=10,25
d(X3,C2)=0,5
 X3 thuộc C2
d(X4,C1)=21,25
d(X4,C2)=0,5
 X4 thuộc C2
Quá trình lặp lại cho đến khi các điểm không dịch chuyển nhóm sau
khi tính lại tâm mới thì dừng.
Kết quả:
C1 gồm các điểm: X1,X2
C2 gồm các điềm X3,X4
d. Cấu trúc chương trình
Các trường:
kc_Euclid: tính khỏang cách eclid giữa 2 điểm
listCluster: lưu trữ các điểm cần gom cụm
listCenter: lưu trữ tâm của các cụm
Các phương thức:
Clustering: gom cụm tập các điểm trong listCluster bằng giải
thuật K-means
13
addClusterObj: thêm 1 điểm vào tập các điểm cần gom cụm
Class hổ trợ cho việc thể hiện đồ họa 2D: các phương thức hổ trợ
việc vẽ hệ trục tọa độ, và vẽ các điểm thêm vào trên mặt phẳng tọa
độ XY.
14
PHỤ LỤC
1. Giao diện chương trình
2. Tài liệu tham khảo
- Giáo trình khai thác dữ liệu- Biên sọan PGS.TS ĐỖ PHÚC-