Có nhiều kỹ thuật khác nhau được yêu cầu để xử lý các ràng buộc cụ thể. Các nguyên tắc chung để xử lý các ràng buộc cứng và mềm như sau -
Xử lý các ràng buộc khó khăn - Một phương pháp chung để xử lý các ràng buộc khó là xem xét chặt chẽ các ràng buộc trong thủ tục phân công cụm. Đưa ra một tập dữ liệu và một nhóm các ràng buộc trên các ví dụ (tức là các ràng buộc phải liên kết hoặc không thể liên kết), làm cách nào chúng ta có thể phát triển phương pháp tiếp cận k-mean để 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 phiên bản cho các ràng buộc phải liên kết - Nó có thể tính toán việc đóng bắc cầu của các ràng buộc phải liên kết. Do đó, tất cả các ràng buộc phải liên kết được coi là một quan hệ tương đương. Bao đóng cung cấp một hoặc một số tập hợp con của các đối tượng trong đó một số đối tượng trong tập hợp con sẽ được gán cho một cụm.
Nó có thể định nghĩa một tập hợp con như vậy, nó có thể thay thế một số đối tượng trong tập hợp con đó một cách có nghĩa. Siêu cá thể cũng tạo ra trọng số, là số lượng đối tượng mà nó xác định. Sau quá trình này, các ràng buộc phải liên kết liên tục được thỏa mãn.
Tiến hành phân nhóm k-mean đã sửa đổi - Trong k-means, một đối tượng được tạo ra gần tâm nhất. Nó có thể tôn trọng các ràng buộc không thể liên kết và nó thay đổi quy trình phân công trung tâm trong k-means thành phân công trung tâm khả thi gần nhất.
Khi các đối tượng được gán cho các trung tâm theo thứ tự, ở mỗi bước nó có thể đảm bảo các phép gán cho đến nay không làm gián đoạn một số ràng buộc không thể liên kết. Một đối tượng được gán cho trung tâm gần nhất để phép gán tuân theo một số ràng buộc không thể liên kết.
Vì COP-k-means cung cấp rằng không có ràng buộc nào bị vi phạm ở mỗi bước, nên nó không cần bất kỳ bẻ khóa ngược nào. Đây là một thuật toán tham lam để tạo một phân cụm thỏa mãn tất cả các ràng buộc, được hỗ trợ để không tồn tại xung đột giữa các ràng buộc.
Xử lý các ràng buộc mềm - Phân cụm với các ràng buộc mềm là một vấn đề tối ưu hóa. Khi một phân cụm phá vỡ một ràng buộc mềm, một hình phạt được yêu cầu đối với việc 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 như tối ưu hóa khía cạnh phân cụm và giảm thiểu hình phạt vi phạm ràng buộc. Dịch vụ mục tiêu là một tập hợp của điểm chất lượng nhóm và điểm phạt.
Đưa ra một tập dữ liệu và một tập hợp các ràng buộc mềm trên các ví dụ, chiến lược thuật toán CVQE (Lỗi lượng tử hóa vectơ bị ràng buộc) k-có nghĩa là phân cụm trong khi thực thi các hình phạt vi phạm ràng buộc. Hàm mục tiêu được sử dụng trong CVQE là tổng khoảng cách được sử dụng trong k-method, được sửa đổi bởi các hình phạt vi phạm ràng buộc, được tính như sau -
Hình phạt của vi phạm phải liên kết - Nếu có ràng buộc phải liên kết đối với các đối tượng x và y, nhưng chúng được tạo thành hai trung tâm, c 1 và c 2 , do đó, do đó ràng buộc bị vi phạm. Do đó, dist (c 1 , c 2 ), khoảng cách giữa c 1 và c 2 , được chèn vào hàm mục tiêu như một hình phạt.
Hình phạt của vi phạm không thể liên kết - Nếu có ràng buộc không thể liên kết trên các đối tượng x và y, nhưng chúng được tạo ra về một tâm chung, c, do đó ràng buộc bị vi phạm. Khoảng cách, dist (c, c ’ ), giữa c và c ’ được chèn vào hàm mục tiêu như một hình phạt.