Phân cụm K-means (K-means clustering) là thuật toán phân hoạch (partitioning algorithm) phổ biến nhất. K-means gán lại mỗi dữ liệu trong tập dữ liệu chỉ cho một trong các cụm mới được hình thành. Một bản ghi hoặc điểm dữ liệu được gán cho cụm gần nhất bằng cách sử dụng đo lường khoảng cách hoặc độ tương đồng.
Thuật toán k-means tạo 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 trong cụm (intracluster similarity) kết quả là lớn nhưng độ tương tự giữa cụm (intercluster similarity) thấp. Độ tương đồng cụm được tính liên quan đến giá trị trung bình (mean value) của các đối tượng trong một cụm, có thể được xem như centroid (trung tâm) hoặc trọng tâm (center of gravity) của cụm.
Có các bước sau được dùng trong phân cụm K-means:
- Chọn K centroid cụm ban đầu c₁, c₂, c₃... cₖ.
- Gán mỗi thể hiện x trong cụm S có centroid gần nhất với x.
- Đối với mỗi cụm, tính lại centroid dựa trên các yếu tố chứa trong cụm đó.
- Đi đến (b) cho đến khi hội tụ (convergence) hoàn thành.
- Tách đối tượng (điểm dữ liệu) thành K cụm.
- Dùng trung tâm cụm (centroid) = trung bình của tất cả điểm dữ liệu trong cụm.
- Gán mỗi điểm cho cụm có centroid gần nhất (sử dụng hàm khoảng cách).
Các giá trị ban đầu cho các trung bình được cho phép tùy ý. Chúng có thể được gán ngẫu nhiên hoặc có thể dùng giá trị từ k mục đầu vào đầu tiên chính thân. Yếu tố hội tụ có thể dựa trên sai số bình phương, nhưng không bắt buộc. Ví dụ, thuật toán được gán cho các cụm khác nhau. Các kỹ thuật chấm dứt khác đơn giản khóa ở một số lần lặp cố định. Số lần lặp tối đa có thể được bao gồm để đảm bảo dừng ngay cả khi không hội tụ.
Thuật toán
Đầu vào —
D = {t₁ t₂ … tₙ} // Tập các phần tử k // Số cụm mong muốn
Đầu ra —
K // Tập các cụm
Thuật toán K-means —
gán giá trị ban đầu cho trung bình m₁ m₂ … mₖ lặp gán mỗi mục tᵢ cho cụm có trung bình gần nhất tính trung bình mới cho mỗi cụm cho đến khi tiêu chí hội tụ được đáp ứng
Sử dụng tùy ý chọn ba đối tượng làm ba trung tâm cụm ban đầu, nơi trung tâm cụm được biểu thị bằng "+". Mỗi đối tượng được phân phối cho một cụm tùy thuộc vào trung tâm cụm nào thuận tiện.
Tiếp theo, các trung tâm cụm được cập nhật. Giá trị trung bình của mỗi cụm được tính lại dựa trên các đối tượng hiện tại trong cụm. Bằng cách sử dụng trung tâm cụm mới, các đối tượng được phân phối lại cho các cụm tùy thuộc vào trung tâm cụm nào liền kề. Phân phối lại như vậy tạo ra các hình dáng mới bị bao quanh bởi các đường nét đứt.
Quy trình lặp lại phân phối đối tượng cho cụm để cải thiện phân hoạch được gọi là di dời 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à do đó quy trình dừng. Các cụm kết quả được khôi phục bởi giai đoạn phân cụm.