K-mean clustering là thuật toán phân vùng phổ biến nhất. K-mean chỉ định lại mỗi dữ liệu trong tập dữ liệu 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 thước đo khoảng cách hoặc độ tương tự.
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.
Có các bước sau được sử dụng trong phân cụm K-mean -
-
Nó có thể chọn K cụm đầu tiên centroid c 1 , c 2 , c 3 …. . c k .
-
Nó có thể gán từng phiên bản x trong cụm S có tâm gần nhất với x.
-
Đối với mỗi cụm, hãy tính toán lại trung tâm của nó dựa trên các phần tử được chứa trong cụm đó.
-
Chuyển đến (b) cho đến khi quá trình hội tụ hoàn tất.
-
Nó có thể tách đối tượng (điểm dữ liệu) thành K cụm.
-
Nó được sử dụng để phân cụm trung tâm (centroid) =điểm trung bình của tất cả các điểm dữ liệu trong cụm.
-
Nó có thể gán từng điểm cho cụm có tâm gần nhất (sử dụng chức năng khoảng cách).
Các giá trị ban đầu cho các phương tiện được ủy quyền tùy ý. Chúng có thể được chỉ định ngẫu nhiên hoặc có thể có thể sử dụng các giá trị từ chính k mục đầu vào đầu tiên. Phần tử hội tụ có thể dựa trên sai số bình phương, nhưng chúng không được yêu cầu. Ví dụ, thuật toán được gán cho các cụm khác nhau. Các kỹ thuật kết thúc khác chỉ đơn giản là khóa ở một số lần lặp lại cố định. Có thể bao gồm số lần lặp lại tối đa để đảm bảo mua sắm ngay cả khi không có sự hội tụ.
Thuật toán
Đầu vào -
D = {t1 t2 … tn} // Set of elements
k // Number of desired clusters Đầu ra -
K // Set of clusters
Thuật toán K-mean -
assign initial values for means m1 m2 … . . mk repeat assign each item ti to the cluster which has the closest mean calculate the new mean for each cluster until convergence criteria are met
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 tùy 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 tùy thuộc vào trung tâm cụm nào liền kề. Một cấu trúc phân phối lại như vậy, những bóng mới được bao quanh bởi những đường cong đứt đoạn.
Quy trình tái tạo lặp đi lặp lại các đối tượng thành các cụm để cải thiện việc 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.