Có nhiều kỹ thuật cần thiết để xử lý các ràng buộc cụ thể. Các nguyên tắc chung xử lý ràng buộc cứng (hard) và mềm (soft) như sau:
Xử lý Ràng buộc Cứng (Handling Hard Constraints)
Một phương pháp chung cho ràng buộc khó là tuân thủ nghiêm ngặt ràng buộc trong quá trình gán cụm. Cho tập dữ liệu và nhóm ràng buộc trên các ví dụ (ví dụ: ràng buộc must-link hoặc cannot-link), làm thế nào để phát triển phương pháp k-means để thỏa mãn các ràng buộc đó? Thuật toán COP-kmeans hoạt động như sau:
Tạo siêu thể hiện cho ràng buộc must-link
Tính bao đóng bắc cầu (transitive closure) của các ràng buộc must-link. Do đó, tất cả ràng buộc must-link được coi như quan hệ tương đương. Bao đóng cung cấp một hoặc nhiều tập con đối tượng nơi tất cả đối tượng trong tập con phải được gán vào một cụm.
Để định nghĩa tập con như vậy, có thể thay thế tất cả đối tượng trong tập con bằng giá trị trung bình. Siêu thể hiện (super instance) cũng mang trọng số, là số đối tượng nó đại diện. Sau quá trình này, ràng buộc must-link luôn được thỏa mãn.
Thực hiện phân cụm k-means đã sửa đổi
Trong k-means, đối tượng được gán cho tâm cụm (center) gần nhất. Để tôn trọng ràng buộc cannot-link, sửa đổi quy trình gán tâm trong k-means thành gán tâm khả thi gần nhất (closest feasible center assignment).
Khi đối tượng được gán cho tâm theo trình tự, tại mỗi bước cần đảm bảo các gán cho đến nay không vi phạm ràng buộc cannot-link nào. Một đối tượng được gán cho tâm gần nhất sao cho việc gán đó tôn trọng tất cả ràng buộc cannot-link.
Vì COP-k-means đảm bảo không ràng buộc nào bị vi phạm tại mỗi bước, nó không cần backtracking (quay lui). Đây là thuật toán tham lam (greedy) để tạo phân cụm thỏa mãn tất cả ràng buộc, miễn là không có xung đột giữa các ràng buộc.
Xử lý Ràng buộc Mềm (Handling Soft Constraints)
Phân cụm với ràng buộc mềm là bài toán tối ưu hóa. Khi một phân cụm vi phạm ràng buộc mềm, một hình phạt (penalty) được áp dụng cho phân cụm đó. Do đó, mục tiêu tối ưu hóa của phân cụm bao gồm hai phần: tối ưu hóa khía cạnh phân cụm và tối thiểu hóa hình phạt vi phạm ràng buộc. Hàm mục tiêu là tổng của điểm chất lượng phân cụm và điểm hình phạt.
Cho tập dữ liệu và tập ràng buộc mềm trên ví dụ, thuật toán CVQE (Constrained Vector Quantization Error) điều chỉnh phân cụm k-means trong khi thi hành hình phạt vi phạm ràng buộc. Hàm mục tiêu dùng trong CVQE là tổng khoảng cách dùng trong k-means, được sửa đổi bằng hình phạt vi phạm ràng buộc, được tính như sau:
Hình phạt vi phạm must-link
Nếu có ràng buộc must-link trên đối tượng x và y, nhưng chúng được gán cho hai tâm khác nhau c₁ và c₂ tương ứng, ràng buộc bị vi phạm. Kết quả là, dist(c₁,c₂), khoảng cách giữa c₁ và c₂, được thêm vào hàm mục tiêu làm hình phạt.
Hình phạt vi phạm cannot-link
Nếu có ràng buộc cannot-link trên đối tượng x và y, nhưng chúng được gán cho chung một tâm c, ràng buộc bị vi phạm. Khoảng cách dist(c,c') giữa c và c' được thêm vào hàm mục tiêu làm hình phạt.