K-means
I. Tư tưởng
- Xét bài toán cho :
+ Một số K (number of cluster)
+ Tập data (X)
- Thuật toán K-means sẽ phân loại cho ta K cụm data, với mỗi một cụm sẽ có tâm (centroid) của nó.
- Ứng dụng : Phân loại đối tượng trong market, phân loại người dùng trong social network, ...
II. Thuật toán
- Input : K và tập data X
- Ta chọn random một tập K centroids (tức tâm của các cụm)
- Thuật toán gồm 2 bước chính :
+ findClosetCentroids : tạo một mảng ci có độ dài bằng số example trong tập data. ci chứa "nhãn" (số thứ tự từ 1..K) là centroid là example thứ i gần nhất. Công thức để xét xem tâm nào gần 1 example nhất là :
sum(power(example - centroids(1, :), 2)) (ở Octave/Matlab) // Với centroids là tập các centroid (tâm) của các cụm (cluster);example là 1example của tập data
+ ComputeCentroids : Tính lại tâm (move centroids) bằng cách : mỗi tâm (centroid) được tính lại bằng cách là trung bình cộng của tập data hiện tại trong cụm của nó.
III. Tối ưu
- Mục tiêu tối ưu của ta là hàm :
J = (1 / m) * sum( sum(power(example - centroids(1, :), 2)) ) (code in Octave)
- 2 bước của thuật toán K-means sẽ minimize hàm trên.
IV. Randomly Initialize
- Thuật toán K-means đặc biệt liên quan đến việc chọn cụm (cluster), vì vậy việc khởi tạo giá trị cho các cụm rất quan trọng, thông thường ta chọn K giá trị cho cụm nằm trong tập data m phần tử (k <= m). Nhưng việc khởi tạo như vậy rất nhiều rủi ro vì các cụm có thể hội tụ không như mong muốn. Như vậy ta có một cách để chọn được một cụm tối ưu, liên quan đến hàm mục tiêu (như đã trình bày ở mục III.)
- Mã giả :
for i = 1 to 100 : // ta có thể thay 100 là 200, …
Chọn K cluster có giá trị là K phần tử được lấy ngẫu nhiên trong tập data set
Chạy K-means :
+ FindClosetCentroids
+ ComputeCentroids
Tính hàm mục tiêu J
Chọn cụm nào có hàm mục tiêu J nhỏ nhất trong các cụm đã tính ở trên .
- Trong octave có thể dùng lệnh sau để pick randomly K centroids từ tập data det X :
randidx = randperm(size(X, 1));
centroids = X(randidx(1:K), :);
V. Ứng dụng
Ví dụ : khi ta có một sites có 100000 thánh viên ta phân thành 10 cụm (thành viên tích cực, tương đối tích cực, ....) sau đó website sẽ có chế độ để "đối đãi " với từng cụm thành viên.
Hoặc ta có thể dùng K-means để nén ảnh: Khi ta có ảnh 3 channel : 128 * 128 khi đó ta đưa ảnh về 2 chiều : A * 3 với A = 128 * 128. Khi đó giả sử ta có 16 cụm 3 features, ta phân các pixels này vào các cụm, sau đó chuyển hết giá trị cả pixel trong cụm về giá trị của centroid của cụm đó.
