Thuật toán K-Means demo

Trong thế giới của khoa học dữ liệu và học máy, việc tìm kiếm các mẫu và cấu trúc ẩn trong dữ liệu là một nhiệm vụ quan trọng. Thuật toán K-means là một trong những phương pháp phân cụm phổ biến nhất, giúp chúng ta nhóm các điểm dữ liệu tương tự lại với nhau một cách tự động.

K-means là một thuật toán học máy không giám sát (unsupervised learning), có nghĩa là nó hoạt động trên dữ liệu không có nhãn. Mục tiêu của thuật toán là phân chia tập dữ liệu thành $k$ cụm khác nhau, trong đó $k$ là một số được xác định trước. Các điểm dữ liệu trong cùng một cụm có xu hướng tương đồng với nhau hơn so với các điểm dữ liệu ở các cụm khác.

Thuật toán

Giả định rằng bộ dữ liệu là một tập hợp $n$ vector $p_i \in \mathbb R^m$: $S=\{P_1(x_{11}, x_{12},\dots,x_{1m}), P_2(x_{21}, x_{22},\dots,x_{2m}),\dots, P_n(x_{n1}, x_{n2},\dots,x_{nm})\}$

Thuật toán được mô tả như sau:

• Khởi tạo: Chọn ngẫu nhiên $k$ điểm trong không gian dữ liệu làm tâm (centroid) của $k$ cụm ban đầu. Ta ký hiệu các cụm lần lượt là $\mathcal C_1, \mathcal C_2, \dots, \mathcal C_k$ với các centroid tương ứng $C_1, C_2, \dots, C_k$.

• Gán nhãn: Tính toán khoảng cách từ mỗi điểm dữ liệu $P \in S$ đến từng tâm cụm $C_i$:

  • Khoảng cách Euclide từ điểm $P(p_1,p_2,\dots, p_m)$ đến điểm $Q(q_1,q_2,\dots,q_m)$ được cho bởi công thức $d(P, Q) = \sqrt{\sum_{j=1}^m (p_j - q_j)^2}$

  • Một điểm $P$ sẽ được gán vào cụm $C_i$ nếu khoảng cách $d(P, C_i)$ là nhỏ nhất $(i = 1,2,\dots,k)$

• Cập nhật tâm: Tính toán lại tâm của mỗi cụm bằng cách lấy trung bình của tất cả các điểm dữ liệu $P(p_1,p_2,\dots,p_m)$ thuộc cụm đó. $\displaystyle C_i = \left(\frac {\sum_{P \in \mathcal C_i} p_1} {|\mathcal C_i|}, \frac {\sum_{P \in \mathcal C_i} p_2} {|\mathcal C_i|}, \dots, \frac {\sum_{P \in \mathcal C_i} p_m} {|\mathcal C_i|} \right)$, với $|\mathcal C_i|$ là số lượng các điểm trong cụm $\mathcal C_i$.

• Lặp lại: Lặp lại bước 2 và 3 cho đến khi các tâm cụm không thay đổi đáng kể hoặc đạt đến số lần lặp tối đa.

Chọn bao nhiêu cụm thì tốt?

Việc chọn $k$ không thể dựa trên cảm tính. Chúng ta cần các thước đo định lượng để đánh giá hiệu quả của việc phân cụm.

1. Phương pháp Khuỷu tay (Elbow Method) và WCSS

Phương pháp này dựa trên việc cực tiểu hóa tổng bình phương khoảng cách nội cụm (Within-Cluster Sum of Squares - WCSS).

Công thức tính WCSS:

$$Trong đó:

• $k$: Số lượng cụm.

• $\mathcal C_i$: Tập hợp các điểm dữ liệu thuộc cụm thứ $i$.

• $\mu_i$: Tâm cụm (centroid) của cụm $i$.

• $||x - \mu_i||^2$: Bình phương khoảng cách Euclidean từ điểm $x$ đến tâm cụm.

Khi $k$ tăng, WCSS chắc chắn giảm. Ta chọn $k$ tại vị trí mà tốc độ giảm của WCSS bắt đầu chậm lại rõ rệt (tạo thành một góc nhọn như cái khuỷu tay trên đồ thị). Lý do là vì tại đó, việc thêm cụm mới không còn giúp giải thích thêm nhiều biến động của dữ liệu nữa

2. Chỉ số Silhouette (Silhouette Coefficient)

Chỉ số này đánh giá xem một điểm dữ liệu "thuộc về" cụm của nó tốt đến mức nào so với các cụm khác.

Công thức: Cho một điểm dữ liệu $i$:

Trong đó:

• $n$ là tổng số điểm dữ liệu trong toàn bộ tập dữ liệu

• $a(i)$: Khoảng cách trung bình từ điểm $i$ đến tất cả các điểm khác trong cùng một cụm (độ gắn kết nội bộ).

• $b(i)$: Khoảng cách trung bình từ điểm $i$ đến tất cả các điểm trong cụm gần nhất mà $i$ không thuộc về (độ tách biệt).

Giá trị hệ số Silhouette trung bình ($S$):

• $s(i) \approx 1$: Điểm được phân cụm rất tốt.

• $s(i) \approx 0$: Điểm nằm ở ranh giới giữa 2 cụm.

• $s(i) \approx -1$: Điểm bị gán sai cụm.

Ta sẽ chọn $k$ có giá trị $S$ trung bình lớn nhất.

3. Phương pháp Thống kê Gap (Gap Statistic)

Phương pháp này so sánh logarit của WCSS từ dữ liệu thực với giá trị kỳ vọng của WCSS từ một tập dữ liệu tham chiếu (thường là phân bố đều, không có cấu trúc cụm).

Công thức tính Gap:

Trong đó:

• $W_k$: Là giá trị WCSS của dữ liệu thực với $k$ cụm.

• $E_n^*\{\log(W_k)\}$ tiêu biểu cho giá trị trung bình của $\log(W_k)$ thu được từ các mẫu dữ liệu phân bố ngẫu nhiên (Bootstrapping).

Cách xác định: Giá trị $k$ tối ưu là giá trị $k$ nhỏ nhất sao cho $Gap(k)$ lớn hơn hoặc bằng giá trị của $Gap(k+1)$ sau khi đã trừ đi một sai số tiêu chuẩn $s_{k+1}$:

Phương pháp này giúp loại bỏ tính chủ quan của phương pháp Elbow bằng cách cung cấp một tiêu chuẩn toán học cụ thể để dừng lại.

Demo

Ứng dụng

Thuật toán K-means có nhiều ứng dụng trong thực tế, bao gồm:

• Phân khúc khách hàng: Phân chia khách hàng thành các nhóm khác nhau dựa trên hành vi mua sắm, nhân khẩu học, v.v., để giúp doanh nghiệp đưa ra chiến lược tiếp thị phù hợp.

• Phân loại tài liệu: Nhóm các tài liệu tương tự nhau lại để giúp tổ chức và tìm kiếm thông tin dễ dàng hơn.

• Nén ảnh: Giảm số lượng màu sắc trong một bức ảnh bằng cách nhóm các pixel có màu tương tự lại với nhau.

• Phát hiện bất thường: Xác định các điểm dữ liệu khác biệt so với phần còn lại của tập dữ liệu, có thể là dấu hiệu của sự bất thường hoặc gian lận.