Chương I Phân tích bằng gom cụm là gì ?
Gom cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thường mà chúng ta vẫn
làm và thực hiện hàng ngày ví dụ như phân loại học sinh khá, giỏi trong lớp, phân loại
đất đai, phân loại tài sản, phân loại sách trong thư viện…
1. Gom cụm: Gom các đối tượng dữ liệu
o Tương tự với một đối tượng khác trong cùng cụm
o Không tương tự với các đối tượng trong các cụm khác
(Tức là thực hiện gom các đối tượng có cùng tính chất hay có các tính chất
gần giống nhau thành nhóm)
o Ví dụ: Phân loại học sinh trong một lớp theo điểm số thành 5 nhóm giỏi,
khá, trung bình khá, trung bình, yếu. Những học sinh có điểm từ 8-10 phân
vào nhóm giỏi, từ 7-8 phân vào nhóm khá, 6-7 phân vào nhóm trung bình
khá, 5-6 nhóm TB, 5 trở xuống vào nhóm yếu.
2. Mục tiêu của gom cụm:
Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối
tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc
cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không
tương đồng.
3. Ứng dụng của gom cụm:
o Kinh doanh: phát hiện ra nhóm khách hàng. Ví dụ Trong tiếp thị mỹ phẩm
có thể phân nhóm khách hang ưa chuộng mỹ phẩm Hàn Quốc, nhóm khách
hang ưa chuộng Mỹ phẩm pháp…
o Sinh học: phân loại động, thực vật, phân loại gen.
o Địa lí: nhận ra các vùng đất giống nhau dựa vào CSDL quan sát trên trái
đất, phân nhóm nhà,…
o Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với
chi phí đền bù trung bình cao
o Hoạch định thành phố: nhận dạng các nhóm nhà cửa theo loại nhà, giá trị
và vị trí địa lý.
o Một công cụ độc lập để xem xét phân bố dữ liệu
o Làm bước tiền xử lý cho các thuật toán khác

xydyxd
yxyxd
yxd
+≤
=
==
≥
Chương II Loại dữ liệu trong phân tích cụm
1. Các biến trị khoảng
Định nghĩa: Biến trị khoảng là các phép đo liên tục của các thang đo tuyến tính, thô. Ví
dụ: trọng lượng, chiều cao, chiều ngang, chiều dọc, tuổi, nhiệt độ thời tiết.
 Một nhóm các độ đo khoảng cách phổ biến cho biến tỉ lệ theo khoảng là khoảng
cách Minkowski.
)|| |||(|),(
2211
q
q
jpip
q
ji
q
ji
xxxxxxjid −++−+−=
+ Với i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là các đối tượng dữ liệu p-chiều và q
là số nguên dương
 Nếu q = 1, độ đo khoảng cách là Manhattan
 Nếu q = 2, độ đo khoảng cách là khoảng cách Euclidean
2. Các biến nhị phân
 Biến nhị phân chỉ có hai trạng thái là 0 hay 1
 Bảng contingency table cho dữ liệu nhị phân:

1
01
|| ||||),(
2211 pp
j
x
i
x
j
x
i
x
j
x
i
xjid
−++−+−=
3. Biến nhị phân đối xứng và bất đối xứng
o Một biến nhị phân là đối xứng nếu đồng thời các trạng thái của nó có tầm quan
trọng như nhau và mang cùng một trọng số. Do đó, không có sự ưu tiên khi kết
quả đưa ra phải được mã hoá là 0 hoặc 1. Ví dụ thuộc tính giới tính có 2 trạng thái
là male và female. Tính tương tự giữa các biến nhị phân đối xứng được gọi là tính
tương tự bất biến, trong đó kết quả không thay đổi khi 1 hoặc tất cả các biến nhị
phân được mã hoá khác nhau. Với các tính giống nhau bất biến, một hệ số được
biết đến nhiều nhất để xác định sự khác nhau giữa đối tượng i và j là hệ số đối
sánh đơn giản, được định nghĩa như sau:
- Một biến nhị phân là không đối xứng nếu các kết quả của các trạng thái không có tầm
quan trọng như nhau. Chẳng hạn kết quả âm tính và dương tính khi khám bệnh. Theo thói
quen, chúng ta sẽ mã hoá kết quả quan trọng nhất, thường là kết quả ít xẩy ra bằng 1
(HIV dương tính) và bằng 0 cho kết quả khác (HIV âm tính). Tính tương tự giữa các

Ta gán các trị Y và P bằng 1 và trị N được gán bằng 0. Tính khoảng cách giữa các
bệnh nhân dựa vào các bất đối xứng dùng hệ số Jacard ta có bảng giá trị như sau:
name Fever Cough Test-1 Test-2 Test-3 Test-4
Jack 1 0 1 0 0 0
Marry 1 0 1 0 1 0
Jim 1 1 0 0 0 0
5
+ Tính d(Jack,Marry):
• Bảng dữ liệu dạng nhị phân:
Marry
Jack
1 0
sum
1 2 0 2
0 1 3 4
sum 3 3 6
Từ bảng ta có:a=2, b=0, c=1, d=3
D(Jack,Marry):
102
10
++
+
=0.33
+ Tính:d(Jack,Jim):
Bảng dữ liệu nhị phân:
6
Jim
Jack
1 0 sum
1 1 1 2

Có hai phương pháp để tính toán sự tương tự giữa hai đối tượng:
• Phương pháp 1: Đối sánh đơn giản với m là số lần đối sáng, p là tổng số các
biến
p
mp
jid
−
=),(
• Phương pháp 2: Dùng một số lượng lớn các biến nhị phân.
 Tạo biến nhị phân mới cho từng trạng thái định danh.
5. Các biến thứ tự :
có thể là liên tục hay rời rạc
 Thứ tự của các trị là quan trọng, ví dụ hạng.
 Có thể xử lý như tỉ lệ khoảng như sau:
- Thay thế x
if
bởi hạng của chúng
- ánh xạ phạm vi của từng biến vào đoạn [0,1] bằng cách thay thế
đối tượng i trong biến thứ f bởi
}, ,1{
fif
Mr ∈
- Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo
khoảng
1
1
−
−
=
f

p
f
f
ij
f
ij
d
jid
1
)(
1
)()(
),(
δ
δ
với
0=
f
ij
δ
nếu x
if
hoặc x
jf
missing
hoặc x
if
=x
jf
=0

như thang đo khoảng
1
1
−
−
=
f
if
if
M
r
z
8. Các biến tỉ lệ
o Độ đo dương trên thang phi tuyến, xấp xỉ thang đo mũ
o Ví dụ Ae
Bt
hay Ae
-Bt

o Các phương pháp:
xử lý chúng như các biến thang đo khoảng không phải là lựa chọn tốt !
áp dụng biến đổi logarithmic yif = log(xif)
xử lý chúng như dữ liệu thứ tự liên tục và xử lý chúng theo hạng như thang đo
khoảng
9. Các biến có kiểu hỗn hợp
o CSDL Có thể chứa cả sáu loại biến
o Có thể dùng công thức được gán trọng để kết hợp các hiệu quả:
Đóng góp của biến f vào khoảng cách d(i,j):
- Nếu f là biến nhị phân hay định danh:
0

p
f
d
jid
δ
δ
=
=
Σ
Σ
=
1 otherwise
;0or
missing, is or if 0
)(
=
==
=
δ
(f)
ij
jfif
jfif
f
ij
xx
xx
δ
- Nếu f là dựa trên khoảng cách: dùng khoảng cách được chuẩn hoá.
- Nếu f là thứ tự thang đo tỉ số tính các hạng r

1.1 Cây các cụm
Phân cấp cụm thường được biểu diễn dưới dạng cây của các cụm. Trong đó:
- Các lá của cây biểu diễn từng đối tượng
- Các nút trong biểu diễn các cụm
Có hai phương pháp tạo cây phân cấp: từ trên xuống và tù dưới lên:
1.2 Phương pháp phân cấp từ trên xuống:
Bắt đầu từ cụm lớn nhất chứa tất cả các đối tượng. Chia cụm phân biệt nhất thành các
cụm nhỏ hơn và tiếp diễn cho đến khi có n cụm thoả mãn điều kiện dừng.
12
b
d
c
e
a
a b
d e
c d e
a b c d e
Step 4
Step 3 Step 2 Step 1 Step 0
Ph
Ph
ân chia-
ân chia-
divisive
divisive
1.3 Phương pháp từ dưới lên:
Các bước thực hiện:
B1: Tạo n nhóm, mỗi nhóm gồm một đối tượng và lập ma trận khoảng cách cấp n.
B2:Tìm 2 nhóm u,v có khoảng cách nhỏ nhất (duv)

nhóm còn lại ta tính theo công thức (*) .
D(12,3)= min(drs) với r thuộc nhóm (12), và s thuộc nhóm 3.
D(1,3)=6, d(2,3)=5. vậy nên d(12,3)=5.
Hoàn toàn tương tự ta tính được d(12,5)=8, d(12,4)=9.
Khi đó ta thu được ma trận khoảng cách mới D1 là
0 5 9 8
D1= 5 0 4 5
9 4 0 3
8 5 3 0
14

B4:
- Lặp lại bước 2, khoảng cách của nhóm 5 và nhóm 4 là nhỏ nhất d(5,4)=3
- Lặp lại bước 3, Ta sẽ gộp nhóm 4 và 5 thành một nhóm Khi đó ta sẽ cập nhật lại
ma trận khoảng cách mới là D2
+ xoá cột 4 và dòng 4 của nhóm 4. Xoá cột 5 và dòng 5 của nhóm 5
+ Thêm một dòng và một cột để lưư khoảng cách của nhóm (45) tớ các nhóm
khác. Ta tính theo công thức (*)
D(45, 12)=min(drs) với r thuộc (45), s thuộc (12)
D(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8.
vậy d(45,12)=8.
Hoàn toàn tương tự ta tính đựoc d(45,3)=4.
Khi đó ta thu được ma trận khoảng cách mới D2 là:
0 5 8
D2 = 5 0 4
8 4 0
- Lặp lại bước 2: d (45,3)= 4 là nhỏ nhất
- Lặp lại bước 3: ta gộp nhóm (45) và nhóm 3 thành một nhóm. Cập nhật ma trận khoảng
cách mới là D3.
+ Xoá dòng và cột của nhóm (45), xoá dòng và cột của nhóm 3

Khoảng cách giữa một cluster này và một cluster khác là tương đương khoảng
cách trung bình từ một vài thành viên của một nhóm này đến một vài thành viên
của nhóm khác.
)(
21
1
)2,1(
2
1
1
1
drs
nn
CCD
n
s
n
r
∑∑
==
=
Với r thuộc C1, s thuộc C2.
Đánh giá:
- Các phương pháp phân cấp có ưu điểm lớn là: khái niệm đơn giản, lý thuyết tốt.
Khi cụm được trộn tách, quyết định là vĩnh cửu, vì vậy số các phương án khác cần
xem xét bị rút giảm.
- Điểm yếu của phương pháp phân cấp: Do việc trộn tách các cụm là vĩnh cửu nên
quyết định sai là không thể khắc phục được. Các phương pháp phân chia cần thời gian
tính toán và không thể scalable cho tập dữ liệu lớn
17

1x
=
6
544333 +++++
= 3.67
1y
=
6
876541 +++++
=5.17
2x
=
4
8775 +++
= 6.75
2y
=
4
5543 +++
= 4.25
19
Bước 3: Tính khoảng cách từ các centroid đến các điểm
STT Toạ độ các
điểm
Khoảng cách đến
centroid 1 (3.67, 5.17)
Khoảng cách đến
centroid 2 (6.75, 4.25)
Thuộc
cụm 1

=
4
5431 +++
= 3.25
Bước 3: Tính khoảng cách từ các centroid đến các điểm
STT Toạ độ
các điểm
Khoảng cách đến
centroid 1 (3.67, 5.17)
Khoảng cách đến
centroid 2 (6.75, 4.25)
Thuộc
cụm 1
Thuộc cụm
2
1 (5,1) 5.00 2.85 x
2 (7,3) 4.37 0.35 x
3 (3,4) 1.95 3.82 x
4 (7,4) 3.80 0.79 x
5 (4,5) 0.44 2.82 x
6 (5,5) 1.57 2.47 x
7 (8,5) 4.4 2.15 x
8 (3,6) 0.69 4.65 x
9 (4,7) 1.21 4.65 x
10 (3,8) 2.17 6.05 x
20
Nhận xét: Sau khi thực hiện bước 3 các cụm không có sự thay đổi nên dừng tại đây.
 Điểm mạnh của phương pháp gom cụm k- means
- Hiệu suất tương đối: O(nkt) 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.

đến K2(6,4)
Thuộc cụm
k1
Thuộc cụm
k2
1 (2,6) 2.24 4.47 x
2 (3,4) 4.00 3.00 x
3 (3,8) 0 5.00 x
4 (4,7) 1.41 3.61 x
5 (6,2) 6.71 2.00 x
6 (6,4) 5.00 0 x
7 (7,3) 6.40 1.41 x
8 (7,4) 5.66 1.00 x
9 (7,6) 4.47 2.24 x
10 (8,5) 5.83 2.24 x
• Bước 3: Chọn điểm (7,6) làm tâm.
STT Tọa độ các
điểm
Khoảng cách đến
K1 (3,8)
Khoảng cách
đến K2 (7,6)
Thuộc cụm
k1
Thuộc cụm
k2
1 (2,6) 2.24 5.00 x
2 (3,4) 4.00 4.47 x
3 (3,8) 0 4.47 x
4 (4,7) 1.41 3.16 x

Nhận xét: Đối tượng trong cụm k1, k2 không thay đổi nên dừng.

Điểm mạnh:
mạnh mẽ hơn k-means là trong sự hiện diện của nhiễu và Bên ngoài, bởi vì medoid
một ít chịu ảnh hưởng bởi giá trị nhiễu hoặc các giá trị đặc biệt.
Điểm yếu:
- Tương đối tốn kém hơn, phức tạp là O (ik (nk)
2
)
- Tổng số lần lặp lại, tổng số số cụm, và n là tổng số của các đối tượng.
tương đối không nhiều hiệu quả.
- C n xác nhầ đị k, t ng s c mổ ố ụ
- Kết quả và tổng thời gian chạy phụ thuộc vào phân vùng ban đầu

24
KẾT LUẬN
Trong bài thu hoạch trên đây là tổng hợp về các phương pháp Gom cụm để khai phá
dữ liệu là một phần quan trọng trong môn học này. Dữ liệu có rất nhiều dạng và loại khác
nhau ta muốn có được tri thức nó thì phải phân hoạch lại để cho dữ liệu dễ dàng truy cập
và truy xuất tốt hơn.
Trong bài thu hoạch em chỉ tìm hiểu được :
Phân tích gom cụm các đôi tượng dựa trên
Phân tích gom cụm các đôi tượng dựa trênsự tương tự , Phân tích gom cụm có phạm vi ứng dụng to lớn ,Có thể tính độ đo tương tự
sự tương tự , Phân tích gom cụm có phạm vi ứng dụng to lớn ,Có thể tính độ đo tương tựcho nhiều loại dữ liệu khác nhau. Việc lựa chọn độ đo tương tự tùy thuộc vào dữ liệu