Thuật toán k-means nhận tham số đầu vào k, và phân chia một nhóm n đối tượng thành k cụm sao cho độ tương đồng nội cụm (intracluster) lớn nhưng độ tương đồng liên cụm (intercluster) thấp. Độ tương đồng cụm được tính liên quan đến giá trị trung bình của các đối tượng trong cụm, có thể nhìn như tâm cụm (centroid) hoặc trọng tâm.
Thuật toán k-means tiến hành như sau. Trước tiên, nó chọn ngẫu nhiên k đối tượng, mỗi đối tượng ban đầu định nghĩa một trung tâm cụm. Đối với mỗi đối tượng còn lại, đối tượng được gán cho cụm mà nó giống nhất, dựa trên khoảng cách giữa đối tượng và trung tâm cụm.
Nó tính trung tâm mới cho mỗi cụm. Giai đoạn này lặp lại cho đến khi hàm mục tiêu hội tụ. Thông thường, tiêu chí lỗi bình phương được biểu diễn như sau:
E = Σᵢ₌₁ᵏ Σₚ∈Cᵢ |p - mᵢ|²
Trong đó E là tổng lỗi bình phương cho tất cả đối tượng trong tập dữ liệu. p là điểm trong không gian định nghĩa đối tượng cho trước và mᵢ là trung bình của cụm Cᵢ (cả p và mᵢ đều đa chiều). Cụ thể, cho mỗi đối tượng trong mỗi cụm, khoảng cách từ đối tượng đến tâm cụm được bình phương, và các khoảng cách được cộng tổng. Tiêu chí này cố gắng làm cho k cụm kết quả càng gọn gàng và độc lập càng tốt.
Thuật toán: k-means − Thuật toán k-means cho phân vùng, nơi tâm mỗi cụm được định nghĩa bởi giá trị trung bình của đối tượng trong cụm.
Đầu vào: k (số cụm), D (tập dữ liệu n đối tượng).
Đầu ra: Tập k cụm.
Phương pháp:
- Chọn ngẫu nhiên k đối tượng từ D làm tâm cụm ban đầu;
- Lặp lại:
- (Gán lại) gán mỗi đối tượng cho cụm mà đối tượng giống nhất, dựa trên giá trị trung bình đối tượng trong cụm;
- Cập nhật trung tâm cụm, tức là tính giá trị trung bình đối tượng cho mỗi cụm;
- Cho đến khi không có thay đổi;
Dùng để chọn ngẫu nhiên ba đối tượng làm ba tâm cụm ban đầu, tâm cụm ký hiệu bằng "+". Mỗi đối tượng được phân phối đến cụm dựa trên tâm cụm thuận tiện nhất.
Tiếp theo, tâm cụm được cập nhật. Giá trị trung bình mỗi cụm được tính lại dựa trên đối tượng hiện tại trong cụm. Sử dụng tâm cụm mới, đối tượng được phân phối lại đến cụm dựa trên tâm cụm liền kề. Sự phân phối lại này tạo hình dáng mới được bao quanh bởi đường cong nét đứt.
Giai đoạn lặp lại gán đối tượng vào cụm để cải thiện phân vùng gọi là di chuyển lặp lại (iterative relocation). Không có phân phối lại đối tượng trong bất kỳ cụm nào xuất hiện, và quy trình dừng. Các cụm kết quả được khôi phục bởi giai đoạn cụm hóa.