Thuật toán K-means Clustering là gì? Giải thích dễ hiểu kèm demo trực quan trên mặt phẳng 2D

Trong bài viết này, chúng ta sẽ:

• Hiểu trực giác: K-means đang làm gì với các điểm dữ liệu 2D.
• Nắm được từng bước thuật toán K-means (assign & update).
• Biết một số lưu ý khi chọn K và khởi tạo tâm cụm (centroid).
• Xem demo trực quan: click tạo điểm trên mặt phẳng và để thuật toán “tự chia cụm” bằng JavaScript.

K-means Clustering là gì?

Cho một tập điểm trên mặt phẳng 2D, K-means sẽ chia các điểm thành K cụm sao cho:

• Mỗi cụm có một “tâm cụm” (centroid) – trung bình vị trí các điểm trong cụm.
• Các điểm “gần” tâm cụm nào nhất sẽ thuộc về cụm đó.
• Tổng bình phương khoảng cách từ các điểm đến tâm cụm của chúng là nhỏ nhất.

Trực giác:

• Giả sử bạn rải nhiều điểm lên canvas.
• Bạn chọn 3 màu: đỏ, xanh, vàng.
• Mỗi màu tương ứng một centroid.
• Mỗi điểm sẽ được tô theo centroid gần nhất → sau đó centroid lại dịch chuyển về trung tâm nhóm điểm của nó.

Đó chính là K-means: lặp đi lặp lại gán cụm và cập nhật centroid cho đến khi ổn định.

Ý tưởng thuật toán K-means (bản 2D)

1. Chọn K tâm cụm ban đầu (centroid).
2. Assign Step: mỗi điểm gán vào centroid gần nhất.
3. Update Step: mỗi cụm cập nhật centroid = trung bình toạ độ điểm trong cụm.
4. Lặp lại cho đến khi không còn thay đổi.

K nên chọn bao nhiêu?

• Nhìn dữ liệu và đoán.
• Dùng Elbow Method.
• Trong demo này cho nhập K trực tiếp.

Mô hình demo: K-means 2D

• Click canvas để tạo điểm.
• Nhập số cụm K.
• Nút “Chạy 1 bước K-means”.
• Nút “Chạy đến khi hội tụ”.
• Log chi tiết assign/update.

Demo K-means Clustering 2D bằng JavaScript

Code giải thích

1. Biểu diễn điểm và centroids

var points = [];
var centroids = [];
var assignments = [];

2. Hàm tính khoảng cách Euclid bình phương

function dist2(a, b) {
    var dx = a.x - b.x;
    var dy = a.y - b.y;
    return dx*dx + dy*dy;
}

3. Assign Step

function assignPoints() {
    var changed = false;
    for (var i = 0; i < points.length; i++) {
        var p = points[i];
        var bestIndex = 0;
        var bestDist = dist2(p, centroids[0]);

        for (var j = 1; j < centroids.length; j++) {
            var d = dist2(p, centroids[j]);
            if (d < bestDist) {
                bestDist = d;
                bestIndex = j;
            }
        }

        if (assignments[i] !== bestIndex) {
            changed = true;
        }
        assignments[i] = bestIndex;
    }

    return changed;
}

4. Update Step

function updateCentroids() {
    var sums = [];
    var counts = [];

    for (var k = 0; k < centroids.length; k++) {
        sums[k] = {x:0, y:0};
        counts[k] = 0;
    }

    for (var i = 0; i < points.length; i++) {
        var c = assignments[i];
        sums[c].x += points[i].x;
        sums[c].y += points[i].y;
        counts[c]++;
    }

    var moved = false;
    for (var k = 0; k < centroids.length; k++) {
        if (counts[k] === 0) continue;

        var newX = sums[k].x / counts[k];
        var newY = sums[k].y / counts[k];

        if (newX !== centroids[k].x || newY !== centroids[k].y) {
            moved = true;
        }

        centroids[k].x = newX;
        centroids[k].y = newY;
    }
    return moved;
}

5. Chạy 1 bước và chạy đến khi hội tụ

Sau mỗi lần chạy: gán cụm → cập nhật centroid → vẽ lại.

Khi nào nên dùng K-means?

• Khi dữ liệu dạng số (vector) và cụm có hình dạng gần tròn.
• Khi cần thuật toán nhanh, đơn giản, chạy được cho dữ liệu lớn.
• Nhạy với khởi tạo.
• Không tự tìm được K.
• Không phù hợp với dữ liệu có dạng “vòng donut”.

Mở rộng demo

• Thêm thuật toán khởi tạo K-means++.
• Vẽ biểu đồ lỗi (SSE) sau mỗi vòng lặp.
• Mở rộng lên không gian 3D.