K-Means clustering¶
Một công việc thường được quan tâm khi xử lý dữ liệu là phân loại một nhóm các đối tượng thành những nhóm nhỏ hơn theo những tiêu chí nhất định.
Tương tự như phần trước, chúng ta có \(N\) điểm dữ liệu \(\bm{x}_i\) thuộc \(\mathbb{R}^d\). Ta muốn phân cụm các vector này vào những cluster (cụm) sao cho chúng gần nhau nhất (về mặt khoảng cách Euclid).
Giả sử ta muốn phân \(N\) điểm dữ liệu trên vào \(K < N\) cluster. Ta cần tìm các điểm \(\bm{m}_1\), \(\bm{m}_2\), ..., \(\bm{m}_K\) là tâm của các cụm, sao cho tổng khoảng cách từ các điểm \(\bm{x}_i\) tới tâm cluster mà nó được phân vào là nhỏ nhất. Nghĩa là ứng với center \(\bm{m}_1\) ta cần tìm các điểm \(\bm{x}_{i_1}\), \(\bm{x}_{i_2}\), ..., \(\bm{x}_{i_t}\) sao cho \(\sum\limits_{j=1}^t \lVert \bm{x}_{i_j} - \bm{m}_1 \rVert^2\) nhỏ nhất. Tương tự cho các tâm khác.
Nhưng câu chuyện phức tạp ở đây là, tâm nằm ở đâu để có thể bao quát các điểm? Tâm được chọn phải có tính tổng quát, và việc phân các điểm vào cluster tương ứng với tâm thực hiện như thế nào?
Một kỹ thuật thường được sử dụng là one-hot. Với mỗi điểm dữ liệu \(\bm{x}_i\) ta thêm một label \(\bm{y}_i = (y_{i1}, \ldots y_{iK})\). Điểm \(\bm{x}_i\) sẽ thuộc cluster \(j\) khi \(y_{ij} = 1\), không thuộc thì bằng \(0\). Như vậy chỉ có đúng một phần tử của \(\bm{y}_i\) bằng \(1\), còn lại bằng \(0\), suy ra ràng buộc của \(\bm{y}_i = (y_{i1}, y_{i2}, \ldots, y_{iK})\) là \(y_{ij} \in \{ 0, 1 \}\) và \(\sum\limits_{j=1}^K y_{ij} = 1\).
Khi đó, ta mong muốn phân các điểm \(\bm{x}_i\) vào cluster \(\bm{m}_k\) để khoảng cách tới tâm \(\bm{m}_k\) là ngắn nhất, hay \(\lVert \bm{x}_i - \bm{m}_k \rVert^2 \to \min\). Thêm nữa, với cách kí hiệu \(y_{ij}\) như trên, biểu thức tương đương với
vì điểm \(\bm{x}_i\) sẽ thuộc cluster \(\bm{m}_k\) nào đó với \(1 \leqslant k \leqslant K\).
Sai số cho toàn bộ dữ liệu lúc này sẽ là
Ta cần tối ưu \(\bm{Y}\) và \(\bm{M}\). Việc tối ưu hai ma trận cùng lúc là rất khó thậm chí bất khả thi. Do đó chúng ta có một cách tiếp cận khác là luân phiên cố định một bên và tối ưu bên còn lại. Từ đó công việc được chia làm hai bước.
Bước 1. Cố định \(\bm{M}\), tìm \(\bm{Y}\).
Giả sử ta đã biết các center \(\bm{m}_1\), \(\bm{m}_2\), ..., \(\bm{m}_K\). Lúc này ta cần phân các điểm \(\bm{x}_i\) vào cluster gần nó nhất. Dễ thấy rằng center gần nó nhất sẽ có khoảng cách Euclid ngắn nhất. Do đó ta tìm \(j\) sao cho \(\lVert \bm{x}_i - \bm{m}_j \rVert^2\) đạt nhỏ nhất. Không cần thiết phải tính căn bậc hai để giảm độ phức tạp.
Bước 2. Cố định \(\bm{Y}\), tìm \(\bm{M}\).
Khi đã biết \(\bm{Y}\) tức là ta đã biết điểm nào được phân vào cluster nào. Khi đó ta cần tìm tâm cho từng cluster. Gọi \(l(\bm{m}_j)\) là hàm tổng bình phương khoảng cách các điểm trong cluster tới tâm \(\bm{m}_j\), nghĩa là
Mục tiêu của chúng ta là tối ưu tâm \(\bm{m}_j\). Do đó ta đạo hàm theo vector \(\bm{m}_j\) thu được
Cho đạo hàm bằng \(0\) và biến đổi ta có
Để ý rằng, \(\sum\limits_{i=1}^N y_{ij}\) là số lượng điểm trong cluster, và \(\sum\limits_{i=1}^N y_{ij} \bm{x}_i\) là tổng các điểm trong cluster. Như vậy \(\bm{m}_j\) là trung bình cộng các điểm trong cluster \(j\).
Thuật toán 1 (Thuật toán K-Means clustering)
Input: Dữ liệu \(\bm{X}\) (có \(N\) điểm dữ liệu) và số cluster \(K\)
Output: Các center \(\bm{M}\) và label \(\bm{y}\) cho mỗi điểm dữ liệu
Chọn \(K\) điểm bất kì làm các cluster ban đầu.
Phân mỗi điểm dữ liệu vào cluster gần nó nhất (cố định \(M\), tìm \(Y\)).
Nếu việc phân dữ liệu vào các cluster ở bước 2 không thay đổi so với trước đó thì dừng thuật toán.
Cập nhật center mới cho mỗi cluster bằng cách lấy trung bình cộng các điểm trong cluster (cố định \(Y\), tìm \(M\)).
Quay lại bước 2.