Bài 57: Minh họa giải thuật gom cụm K-Means bằng toán học

K-Means là một trong những thuật toán phổ biến và được sử dụng rất nhiều trong kỹ thuật gom cụm. Ý tưởng chính của thuật toán này là tìm cách phân nhóm các đối tượng đã cho vào K cụm sao cho tổng khoảng cách giữa các đối tượng đến tâm nhóm là nhỏ nhất. Thường K là số cụm được xác định trước và thường lấy ý kiến của chuyên gia, K phải nguyên dương. Khoảng cách giữa các đối tượng thường được sử dụng là khoảng cách Euclid.

Trong toán học, khoảng cách Euclid (tiếng Anh: Euclidean distance) giữa hai điểm trong không gian Euclid là độ dài của đoạn thẳng nối hai điểm đó. Có thể tính nó từ tọa độ Descartes của hai điểm bằng cách sử dụng định lý Pythagoras, do đó còn có tên gọi khác là khoảng cách Pythagoras (tiếng Anh: Pythagorean distance).

Src: Wikipedia

Đầu vào:

•Tập các  đối tượng X = {x_i| i = 1, 2, …, N},

•Số cụm: K

Đầu ra:

•Các cụm Ci ( i = 1 ÷ K) tách rời và hàm tiêu chuẩn E đạt giá trị tối thiểu.

Trong đó c_j là trọng tâm của cụm C_j

Chu trình hoạt động 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.

Các bước thực hiện thuật toán:

Dựa vào chu trình và lưu đồ thuật toán, ta có thể diễn giải các bước thực hiện như sau:

•Bước 1 – Khởi tạo

  Chọn K trọng tâm {c_i} ngẫu nhiên hoặc theo tiêu chuẩn (i = 1÷K).

•Bước 2 – Tính toán khoảng cách

•Bước 3 – Cập nhật lại trọng tâm, ta thường tính giá trị trung bình

•Bước 4 – Điều kiện dừng

Ví dụ gom cụm bằng K-Means với bảng dữ liệu sau (k=2) và giả sử r3, r5 là center mặc định:

…	Value 1	Value 2	Value 3	Value 4	Value 5	Value 6	Value 7	Value 8	Value 9	Value 10	Value 11
r1	1	1	0.5	0.5	0	0	0	0.5	0.25	0	0
r2	1	1	0.5	0.5	0	0	0	0.5	0.25	0	0
r3	0.5	0.5	1	1	0	0	0	0.33	0.33	0	0
r4	0.5	0.5	1	1	0	0	0	0.33	0.33	0	0
r5	0	0	0	0	1	1	1	0	0	0	0
r6	0	0	0	0	1	1	1	0	0	0	0
r7	0	0	0	0	1	1	1	0	0	0	0
r8	0.5	0.5	0.33	0.33	0	0	0	1	0.25	0.17	0.17
r9	0.25	0.25	0.33	0.33	0	0	0	0.25	1	0.75	0.75
r10	0	0	0	0	0	0	0	0.17	0.75	1	1
r11	0	0	0	0	0	0	0	0.17	0.75	1	1

Sau đây là chi tiết các bước thực hiện giải thuật K-Means để gom cụm. Dùng Euclid để tính các khoảng cách:

Bước 1: Khởi tạo
Giả sử chọn ngẫu nhiên 2 Trọng tâm ban đầu: r3; r5

* Gọi V1 là véc tơ trọng tâm của C1: Ta tính được V1(0.5,0.5,1,1,0,0,0,0.33,0.33,0,0)
* Gọi V2 là véc tơ trọng tâm của C2: Ta tính được V2(0,0,0,0,1,1,1,0,0,0,0)

Bước 2: Tính khoảng cách từ các đỉnh tới các Vector trọng tâm:

– d([r1],V1)=1.02 < d([r1],V2)=2.41. Vậy ta gom [r1] vào cụm C1.

Lý giải:

Ta tính được d([r1],V1)=1.02 từ công thức sau:

Tương tự ta cũng tính được d([r1],V2)=2.41 từ công thức sau:

Tương tự ta tính được khoảng cách tới trọng tâm cho các đỉnh còn lại (Các bạn cần viết lại công thức chi tiết như minh họa ở trên):

– d([r2],V1)=1.02 < d([r2],V2)=2.41. Vậy ta gom [r2] vào cụm C1.
– d([r4],V1)=0 < d([r4],V2)=2.39.Vậy ta gom [r4] vào cụm C1.
– d([r6],V1)=2.39 > d([r6],V2)=0. Vậy ta gom [r6] vào cụm C2.
– d([r7],V1)=2.39 > d([r7],V2)=0. Vậy ta gom [r7] vào cụm C2.
– d([r8],V1)=1.18 < d([r8],V2)=2.2. Vậy ta gom [r8] vào cụm C1.
– d([r9],V1)=1.61 < d([r9],V2)=2.35. Vậy ta gom [r9] vào cụm C1
– d([r10],V1)=2.17 < d([r10],V2)=2.36. Vậy ta gom [r10] vào cụm C1
– d([r11],V1)=2.17 < d([r11],V2)=2.36. Vậy ta gom [r11] gom vào cụm C1

*Vậy ta có phân bố cụm lần 1:

U=1	r1	r2	r3	r4	r5	r6	r7	r8	r9	r10	r11
C1	1	1	1	1	0	0	0	1	1	1	1
C2	0	0	0	0	1	1	1	0	0	0	0

Bước 3: Cập nhật lại vector trọng tâm
* Gọi V1 là véc tơ trọng tâm mới của C1:
Ta tính được V1(0.47,0.47,0.46,0.46,0,0,0,0.41,0.49,0.36,0.36)

Lý giải trọng tâm mới được tính như sau:

Tương tự cho các thuộc tính và Vector còn lại.
* Gọi V2 là véc tơ trọng tâm mới của C2: Ta tính được V2(0,0,0,0,1,1,1,0,0,0,0)

Bước 4: Kiểm tra điều kiện dừng
Ta so sánh Vector trọng tâm mới được tạo ở bước 3 so với Vector trọng tâm cũ:
Tập Vector Trọng tâm cũ:
V1(0.5,0.5,1,1,0,0,0,0.33,0.33,0,0)

V2(0,0,0,0,1,1,1,0,0,0,0)
Tập Vector Trọng tâm Mới:
V1(0.47,0.47,0.46,0.46,0,0,0,0.41,0.49,0.36,0.36)

V2(0,0,0,0,1,1,1,0,0,0,0)
Ta kiểm tra thấy trọng tâm bị thay đổi nên lặp lại bước 2.

Bước 2: Tính khoảng cách từ các đỉnh tới các Vector trọng tâm:
– d([r1],V1)=0.95 < d([r1],V2)=2.41. Vậy ta gom [r1] vào cụm C1.
– d([r2],V1)=0.95 < d([r2],V2)=2.41. Vậy ta gom [r2] vào cụm C1.
– d([r3],V1)=0.94 < d([r3],V2)=2.39. Vậy ta gom [r3] vào cụm C1.
– d([r4],V1)=0.94 < d([r4],V2)=2.39. Vậy ta gom [r4] vào cụm C1.
– d([r5],V1)=2.13 > d([r5],V2)=0 . Vậy ta gom [r5] vào cụm C2.
– d([r6],V1)=2.13 > d([r6],V2)=0. Vậy ta gom [r6] vào cụm C2.
– d([r7],V1)=2.13 > d([r7],V2)=0. Vậy ta gom [r7] vào cụm C2.
– d([r8],V1)=0.72 < d([r8],V2)=2.2. Vậy ta gom [r8] vào cụm C1.
– d([r9],V1)=0.84 < d([r9],V2)=2.35.  Vậy ta gom [r9] vào cụm C1.
– d([r10],V1)=1.34 < d([r10],V2)=2.36. Vậy ta gom [r10] vào cụm C1.
– d([r11],V1)=1.34 < d([r11],V2)=2.36. Vậy ta gom [r11] vào cụm C1.
*Vậy ta có phân bố cụm lần 2:

U=2	r1	r2	r3	r4	r5	r6	r7	r8	r9	r10	r11
C1	1	1	1	1	0	0	0	1	1	1	1
C2	0	0	0	0	1	1	1	0	0	0	0

Bước 3: Cập nhật lại vector trọng tâm

* Gọi V1 là véc tơ trọng tâm mới của C1:

Ta tính được V1(0.47,0.47,0.46,0.46,0,0,0,0.41,0.49,0.36,0.36)

* Gọi V2 là véc tơ trọng tâm mới của C2:

Ta tính được V2(0,0,0,0,1,1,1,0,0,0,0)

Bước 4: Kiểm tra điều kiện dừng
Ta so sánh Vector trọng tâm mới được tạo ở bước 3 so với Vector trọng tâm cũ:

Tập Vector Trọng tâm cũ:

V1(0.47,0.47,0.46,0.46,0,0,0,0.41,0.49,0.36,0.36) ;V2(0,0,0,0,1,1,1,0,0,0,0)

Tập Vector Trọng tâm Mới:

V1(0.47,0.47,0.46,0.46,0,0,0,0.41,0.49,0.36,0.36);V2(0,0,0,0,1,1,1,0,0,0,0)

Vậy ta thấy U2 và U1 Không có sự thay đổi. Giải thuật K-Means kết thúc.

Cuối cùng ta được 2 cụm như sau:

Cụm 1 {r1;r2;r3;r4;r8;r9;r10;r11}

Cụm 2 {r5;r6;r7}

Bài tập tương tự: Cho bảng ma trận dữ liệu dưới đây, hãy giải thích từng bước quá trình K-Means hoạt động, với số cụm là 3, center vector khởi tạo ban đầu là Daisy, Vitor, Real

Customer	Attribute 1	Attribute 2
John	1	1
Peter	11	12
Daisy	2	3
Case	1	2
Ronie	2	6
Vitor	9	8
Rehm	0	1
Tom	11	10
Bob	0	2
Lie	10	11
Tide	10	12
Real	7	4
Jassor	5	6

Bài học sau Tui hướng dẫn cách sử dụng K-Means để gom cụm khách hàng theo thu nhập, độ tuổi và ngân sách chi tiêu. Chúng ta dùng phương pháp Elbow để tìm ra K Cụm tối ưu nhất để gom, trực quan hóa các cụm bằng 2D và 3D. Đồng thời phân loại chi tiết Khách hàng theo từng cụm để dễ dàng đưa ra các chính sách chăm sóc và tiếp thị phù hợp.

Các bạn chú ý theo dõi

Chúc các bạn thành công