Phân cụm K-Means (học máy không giám sát)

Thuật toán K-means:

<1> Chọn ngẫu nhiên K điểm làm trung tâm của K cụm

<2> Gán các điểm gần với mỗi cụm, nếu không có phép gán nào thì dừng

<3> Tính lại trung tâm của mỗi cụm

<4> Lặp lại bước 2

Khoảng cách euclid: 

A(a1, a2) và B(b1, b2) => AB = sqrt(sqr(a1-b1) + sqr(a2-b2))

Khoảng cách manhattan:

A(a1, a2) và B(b1, b2) => AB = abs(a1-b1) + abs(a2-b2)

Đề bài – Example

Giả sử có 4 sinh viên A, B, C, D. Mỗi sinh viên được biểu diễn bởi hai đặc trưng X, Y.

Sinh viên	Sở thích (X)	Quê quán (Y)
A	1	1
B	2	1
C	4	3
D	5	4

 Mục đích là nhóm các sinh viên đã cho vào 2 nhóm/phòng (K=2) dựa vào các đặc trưng của chúng. 

Giải

Chọn điểm A là tâm của cụm 1, điểm B là tâm của cụm 2. 

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0    1    3.6    5

Cụm 2     1    0    2.8    4.2

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A)

Cụm 2 (B, C, D)

Tính tâm của mỗi cụm:

Cụm 1 tâm (1,1)

Cụm 2 tâm ((2+4+5)/3 , (1+3+4)/3 )  = (3.6 , 2.6)

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0    1    3.6    5

Cụm 2     3.05    2.2    0.5    1.9

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A, B)

Cụm 2 (C, D)

Tính tâm của mỗi cụm:

Cụm 1 tâm (1.5, 1)

Cụm 2 tâm (4.5, 3.5)

Khoảng cách euclid các điểm đến tâm của mỗi cụm:

                A    B    C    D

Cụm 1     0.5    0.5    3.2    4.6

Cụm 2     4.3    3.5    0.7    0.7

Gán các điểm cho gần với mỗi cụm:

Cụm 1 (A, B)

Cụm 2 (C, D)

Vì phép gán lần này giống với lần trước nên thuật toán dừng 

Vậy ta được 2 cụm (A, B) và (C, D)