tài liệu Thuật toán k means
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (622.06 KB, 13 trang )
1
Là thuật toán lặp đơn giản để chia CSDL thành k
nhóm (k do người dùng chỉ định).
Được phát triển bởi nhiều nhà nghiên cứu khác
nhau, điển hình là Lloyd (1957, 1982), Forgey
(1965), Friedman và Rubin (1967), McQueen
(1967).
2
2.1. Thuật toán
Thuật toán thao tác trên một tập các vectơ d-chiều, D = {x
i
| i = 1
N} trong đó x
i
d
là điểm dữ liệu thứ i. Thuật toán bắt đầu bằng
cách chọn k điểm làm trọng tâm. Kỹ thuật để chọn các điểm hạt
giống này là “ngẫu nhiên”. Sau đó thuật toán gọi hai bước sau cho
đến khi hội tụ (không còn thay đổi nữa):
Bước 1. Gán dữ liệu: Mỗi điểm dữ liệu được gán vào nhóm nào
gần nhất. Đây là việc phân chia dữ liệu.
Bước 2. Tính lại trọng tâm: đại diện của mỗi nhóm được tính lại
bằng với trung bình (mean) của các điểm dữ liệu thuộc nhóm.
Nếu các điểm dữ liệu được tính bởi xác suất (probability measure
/ weights) thì đại diện được tính bằng giá trị kì vọng (expectation)
của dữ liệu.
3
2.1. Thuật toán - ví dụ minh họa
Lần lặp 0 Lần lặp 1 Lần lặp 2
Lần lặp 3 Lần lặp 4 Lần lặp 5
4
2.1. Thuật toán – Vấn đề tối ưu cục bộ
Việc chọn giá trị khởi đầu cho các trọng tâm của k-means sẽ quyết
định đến việc hội tụ “cục bộ” hay “toàn cục” của dữ liệu.
Lần lặp 0 Lần lặp 1 Lần lặp 2
5
2.2. Khoảng cách giữa hai đối tượng
Kho
ả
ng cách Minkowski
:
Trong đó
i
= (
x
i1
,
x
i2
, …,
x
ip
) và
j
= (
x
j1
,
x
j2
, …,
x
jp
) là
hai đối tượng dữ liệu
p-chi
ề
u
và q là số nguyên
dương.
Nếu
q
=
1
,
d
là khoảng cách Manhattan
q
q
pp
j
x
i
x
j
x
i
x
j
x
i
xjid )|| |||(|),(
2211
|| ||||),(
2211 pp j
x
i
x
j
x
i
x
j
x
i
xjid
2.2. Khoảng cách giữa hai đối tượng
N
ế
u q
=
2
,
d là kho
ả
ng cách
Euclidean:
◦ Các tính chất của khoảng cách Euclidean
d(i,j)
0
d(i,i)
= 0
d(i,j)
=
d(j,i)
d(i,j) d(i,k)
+
d(k,j)
)|| |||(|),(
22
22
2
11 pp j
x
i
x
j
x
i
x
j
x
i
xjid
7
2.3. Ví dụ minh họa
Với k = 2 và n = 5 {A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
Gọi M1, M2 là trọng tâm của hai nhóm, ta có kết quả như sau:
Bước 1: Gán M1 = A, M2 = B
Bước 2:
Xét C: d(C,M1) =
d(C,M2) =
C thuộc Nhóm 1
Xét D: d(D,M1) =
d(D,M2) =
D thuộc Nhóm 1
5)21()13(
22
13)31()03(
22
3)22()14(
22
17)32()04(
22
8
Xét C: d(C,M1) =
d(C,M2) =
C thuộc Nhóm 1
Xét D: d(D,M1) =
d(D,M2) =
D thuộc Nhóm 1
Xét E: d(E,M1) =
d(E,M2) =
E thuộc Nhóm 1
Vậy: Nhóm 1 gồm {A, C, D, E}
Nhóm 2 gồm {B}
5)21()13(
22
13)31()03(
22
3)22()14(
22
17)32()04(
22
M1 = A, M2 = B
13)20()14(
22
23)30()04(
22
{A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
9
Bước 2:
Xét A: d(A,M1)=
d(A,M2)=
A thuộc nhóm 2
Xét B: B là M2
B thuộc nhóm 2
Bước 3:
Tính lại trọng tâm M1 =
M2 = (0,3)
)
4
5
,4()
4
212
,
4
4431
(
16
153
)
4
5
2()41(
22
2)32()01(
22
{A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
10
Bước 2 (tt):
Xét C: d(C,M1)=
d(C,M2)=
C thuộc nhóm 1
Xét D: d(D,M1)=
d(D,M2)=
D thuộc nhóm 1
Xét E: d(E,M1)=
d(E,M2)=
E thuộc nhóm 1
16
17
)
4
5
1()43(
22
13)31()03(
22
4
5
)
4
5
0()44(
22
23)30()04(
22
4
3
)
4
5
2()44(
22
17)32()04(
22
{A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
11
Bước 2:
Xét A: d(A,M1)=
d(A,M2)=
A thuộc nhóm 2
Xét B: d(B,M1)=
d(B,M2)=
B thuộc nhóm 2
Bước 3:
Tính lại trọng tâm M1 =
M2 =
)1,
3
11
()
3
21
,
3
443
(
9
73
)12()
3
11
1(
22
2
1
)
2
5
2()
2
1
1(
22
)
2
5
,
2
1
()
2
23
,
2
10
(
9
133
)13()
3
11
0(
22
2
1
)
2
5
3()
2
1
0(
22
{A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
12
Bước 2 (tt):
Xét C: d(C,M1)=
d(C,M2)=
C thuộc nhóm 1
Xét D: d(D,M1)=
d(D,M2)=
D thuộc nhóm 1
Xét E: d(E,M1)=
d(E,M2)=
E thuộc nhóm 1
Không còn thay đổi nữa, dừng
3
2
)11()
3
11
3(
22
13)31()03(
22
9
10
)10()
3
11
4(
22
23)30()04(
22
9
10
)12()
3
11
4(
22
17)32()04(
22
{A(1,2), B(0,3), C(3,1), D(4,2), E(4,0)}
13
2.4. Hướng tiếp theo
-Có thể xem xét một số cách tiếp cận “trung bình” theo mô hình khả
xuất thay vì dựa vào các điểm.
-Vấn đề gom nhóm mờ (c-mean)
-Cần nghiên cứu giải pháp tăng tốc độ khi dữ liệu lớn.
