THUẬT TOÁN K-MEAN
VÀ ỨNG DỤNG
1
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
NỘI DUNG CHÍNH
I. Phân cụm
II. Thuật toán K-Mean
1. Khái quát về thuật toán
2. Các bước của thuật toán
3. Ví dụ minh họa – Demo thuật toán
4. Đánh giá thuật toán
III. Ứng dụng của thuật toán K-Mean
2
K

3
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
I. PHÂN CỤM
Nếu X : 1 tập các điểm dữ liệu
C
i
: cụm thứ i
X = C
1
… C
k
… C
ngoại lai

I. PHÂN CỤM
2. Một số độ đo trong phân cụm

Minkowski

Euclidean – p = 2

Độ đo tương tự (gần nhau): cosin hai vectơ
cosµ =
5
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
1
1

e
a
n

v
à

n
g

d
u
n
g
ứ
I. PHÂN CỤM
4. Một số phương pháp phân cụm điển hình

Phân cụm phân hoạch

Phân cụm phân cấp

Phân cụm dựa trên mật độ

Phân cụm dựa trên lưới

Phân cụm dựa trên mô hình

Phân cụm có ràng buộc
7


Đặc điểm:

Mỗi đối tượng chỉ thuộc về 1 cụm.

Mỗi cụm có tối thiểu 1 đối tượng.

Một số thuật toán điển hình : K-mean, PAM, CLARA,…
8
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
II.2. Thuật toán K-Means
Phát biểu bài toán:


g

d
u
n
g
ứ
II.1. KHÁI QUÁT VỀ THUẬT TOÁN

Thuật toán hoạt động trên 1 tập vectơ d chiều, tập dữ liệu
X gồm N phần tử:
X = {x
i
| i = 1, 2, …, N}

K-Mean lặp lại nhiều lần quá trình:

Gán dữ liệu.

Cập nhật lại vị trí trọng tâm.

Quá trình lặp dừng lại khi trọng tâm hội tụ và mỗi đối
tượng là 1 bộ phận của 1 cụm.
10
K
-
M
e
a
n

i j
i x C
x c
= ∈
−
∑ ∑
11
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
II.2. CÁC BƯỚC CỦA THUẬT TOÁN

Bước 1 - Khởi tạo
Chọn K trọng tâm {c
i

j i
t
i j
t
x S
i
c x
S
+
∈
=
∑
II.3 VÍ D MINH H AỤ Ọ
Đ i t ngố ượ Thu c tính 1 (X)ộ Thu c tính 2 (Y)ộ
A 1 1
B 2 1
C 4 3
D 5 4
13
K
-
M
e
a
n

v
à

n

c m Kụ
Tr ng tâmọ
Tr ng tâmọ
Kho ng cách các ả
đ i t ng đ n các ố ượ ế
tr ng tâmọ
Nhóm các đ i ố
t ng vào các c mượ ụ
Không có
đ i t ng ố ượ
chuy n ể
nhóm
K t thúcế
K t thúcế
+
-
II.3 VÍ D MINH H AỤ Ọ

B c 1:ướ Kh i t oở ạ
Ch n 2 tr ng tâm ban đ u: ọ ọ ầ
c
1
(1,1) A và c≡
2
(2,1) B, thu c 2 c m 1 và 2≡ ộ ụ
15
K
-
M
e

) C thu c c m 2ộ ụ


d(D, c
1
) =
= 25
d(D, c
2
) =
= 18
d(D,c
1
) > d(D, c
2
) D thu c c m 2ộ ụ
2 2
(4 1) (3 1)− + −
2 2
(4 2) (3 1)− + −
2 2
(5 1) (4 1)− + −
2 2
(5 2) (4 1)− + −
16
K
-
M
e
a

17
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
II.3 VÍ D MINH H AỤ Ọ

B c 4-1:ướ L p l i b c 2 – Tính toán kho ng ặ ạ ướ ả
cách

d(A, c
1
) = 0 < d(A, c
2
) = 9.89
A thu c c m 1ộ ụ

v
à

n
g

d
u
n
g
ứ
II.3 VÍ DỤ MINH HỌA

B c 4-2: ướ L p l i b c 3-C p nh t tr ng tâmặ ạ ướ ậ ậ ọ
c
1
= (3/2, 1) và c
2
= (9/2, 7/2)
19
K
-
M
e
a
n

v
à


) = 0.5
C thu c c m 2ộ ụ

d(D, c
1
) = 21.25 > d(D, c
2
) = 0.5
D thu c c m 2ộ ụ
20
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
II.3 VÍ D MINH H AỤ Ọ
21

. .K N l
22
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ
II.4 ĐÁNH GIÁ THUẬT TOÁN – NHƯỢC
ĐIỂM
1. Không có khả năng tìm ra các cụm không lồi hoặc các
cụm có hình dạng phức tạp.
2. Khó khăn trong việc xác định các trọng tâm cụm ban đầu
- Chọn ngẫu nhiên các trung tâm cụm lúc khởi tạo
- Độ hội tụ của thuật toán phụ thuộc vào việc khởi tạo
các vector trung tâm cụm
1. Khó để chọn ra được số lượng cụm tối ưu ngay từ đầu,
mà phải qua nhiều lần thử để tìm ra được số lượng cụm

2. Áp dụng K-Mean
Kết quả trả về là các cụm tài liệu và các trọng tâm tương
ứng.

Phân vùng ảnh
24
K
-
M
e
a
n

v
à

n
g

d
u
n
g
ứ