Thuật toán k-mean tạo ra tham số đầu vào, k và chia một nhóm n đối tượng thành k cụm sao cho độ tương tự giữa các nhóm là lớn nhưng độ tương tự giữa các nhóm là thấp. Độ tương tự của cụm được tính toán dựa trên giá trị trung bình của các đối tượng trong một cụm, có thể được xem như là trung tâm của cụm hoặc trọng tâm.
Thuật toán k-mean tiến hành như sau. Đầu tiên, nó có thể chọn ngẫu nhiên k trong số các đối tượng, mỗi đối tượng ban đầu xác định một trung tâm hoặc trung tâm của cụm. Đối với mỗi đối tượng còn lại, một đối tượng được tạo cho cụm mà nó giống nhau, phụ thuộc vào khoảng cách giữa các đối tượng và giá trị trung bình của cụm.
Nó có thể tính toán giá trị trung bình mới cho mỗi cụm. Giai đoạn này lặp lại cho đến khi hàm nguyên tắc hội tụ. Nói chung, tiêu chí sai số bình phương được biểu thị là -
$$ \ mathrm {E =\ displaystyle \ sum \ limit_ {i =1} ^ k \ displaystyle \ sum \ limit_ {p \ epsilon C_ {i}} | p-m_ {i} | ^ 2} $$
Trong đó E là tổng sai số bình phương của một số đối tượng trong tập dữ liệu. p là điểm trong không gian xác định một đối tượng nhất định và m i là giá trị trung bình của cụm C i (cả p và m i đa chiều). Đặc biệt, đối với mỗi đối tượng trong mỗi cụm, khoảng cách từ đối tượng đến tâm cụm của nó được bình phương và các khoảng cách được ước tính. Tiêu chí này cố gắng tạo ra k cụm kết quả càng nhỏ gọn và càng độc lập càng tốt.
Thuật toán: k-mean - Thuật toán k-mean để phân vùng, trong đó trung tâm của mọi cụm được xác định bằng giá trị trung bình của các đối tượng trong cụm.
Đầu vào -
k: the number of clusters, D: a data set including n objects.
Đầu ra -
A set of k clusters.
Phương pháp -
-
tùy ý chọn k đối tượng từ D làm trung tâm cụm ban đầu;
-
lặp lại
-
(lại) gán từng đối tượng vào cụm mà đối tượng giống nhau, phụ thuộc vào giá trị trung bình của các đối tượng trong cụm;
-
cập nhật các phương tiện của cụm, tức là tính toán giá trị trung bình của các đối tượng cho mỗi cụm;
-
cho đến khi không thay đổi;
Nó được sử dụng để tùy ý chọn ba đối tượng làm ba trung tâm cụm ban đầu, trong đó các trung tâm cụm được ký hiệu bằng dấu “+”. Mỗi đối tượng được phân phối đến một cụm phụ thuộc vào trung tâm cụm mà nó 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 toán lại dựa trên các đối tượng phổ biến trong cụm. Bằng cách sử dụng các trung tâm cụm mới, các đối tượng được phân phối lại cho các cụm phụ thuộc vào trung tâm cụm nào là liền kề. Cấu trúc phân phối lại như vậy sẽ tạo ra những bóng mới được bao quanh bởi các đường cong đứt đoạn.
Giai đoạn gán lại các đối tượng theo cách lặp lại cho các cụm để tăng cường phân vùng được định nghĩa là tái định vị lặp đi lặp lại. Không có sự phân bổ lại các đối tượng trong bất kỳ cụm nào xuất hiện, và do đó, quá trình loại bỏ. Các cụm kết quả được khôi phục bằng giai đoạn phân nhóm.