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 \(\mathcal 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.

Demo & Code

Ứ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.