Có hai loại thuật toán phân hoạch như sau:
Phân cụm K-means – K-means clustering là thuật toán phân hoạch phổ biến nhất. K-means gán lại mỗi dữ liệu trong tập dữ liệu cho chỉ một trong các cụm mới được hình thành. Bản ghi hoặc điểm dữ liệu được gán cho cụm gần nhất dùng phép đo khoảng cách hoặc độ tương đồng. Có các bước sau dùng trong phân cụm K-means:
Chọn K tâm cụm ban đầu c1, c2, c3 ... ck.
Gán mỗi thể hiện x trong S cụm mà tâm cụm của nó gần nhất với x.
Đối với mỗi cụm, tính lại tâm cụm dựa trên các phần tử chứa trong cụm đó.
Quay lại (b) cho đến khi hội tụ hoàn thành.
Tách đối tượng (điểm dữ liệu) thành K cụm.
Dùng 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 mà tâm cụm gần nhất (dùng hàm khoảng cách).
Giá trị ban đầu cho các trung bình được gán tùy ý. Chúng có thể gán ngẫu nhiên hoặc có thể dùng giá trị từ k mục nhập đầu tiê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. Kỹ thuật dừng khác đơn giản khóa tại số lần lặp cố định. Số lần lặp tối đa có thể bao gồm để đảm bảo dừng ngay cả khi không hội tụ.
Thuật toán
Đầu vào (Input)
D = {t1t2 ... tn} // Tập phần tử k // Số cụm mong muốnĐầu ra (Output)
K // Tập cụm
Thuật toán K-means –
gán giá trị ban đầu cho trung bình m1m2... mk
lặp lại
gán mỗi mục ti 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ụ đạt được
Thuật toán láng giềng gần nhất (Nearest neighbour algorithm) – Thuật toán tương tự kỹ thuật single link được gọi là thuật toán láng giềng gần nhất. Với thuật toán tuần tự này, mục được lặp lại kết hợp vào cụm hiện tại gần nhất. Trong thuật toán này, ngưỡng t có thể xác định xem mục sẽ được chèn vào cụm hiện có hay cụm mới được tạo.
Thuật toán
Đầu vào (Input)
D = {t1t2 ... tn} // Tập phần tử A // Ma trận liền kề hiển thị khoảng cách giữa phần tửĐầu ra (Output)
K // Tập cụm Nearest neighbour algorithm K1 = {t1}; K = {K1}; k = 1; for i = 2 to n do find the tm in some cluster Km in K such that dis {ti, tm} is the smallest; If dis {ti, tm} $\leqslant$ t then Km = Km $\cup$ ti else k = k + 1; Kk = {ti}