Các thuật toán dựa trên ràng buộc (constraint-based algorithms) cần ràng buộc để giảm không gian tìm kiếm trong giai đoạn sinh tập mục thường xuyên (bước tạo luật liên kết chính xác như thuật toán toàn diện).
Tầm quan trọng của ràng buộc được định nghĩa rõ ràng và chúng chỉ tạo ra các luật liên kết thú vị với người dùng. Phương pháp khá đơn giản và không gian luật bị giảm trong khi các luật còn lại tuân thủ ràng buộc.
Có ba loại ràng buộc như sau:
Ràng buộc trên thể hiện (Constraints on Instances)
Ràng buộc trên thể hiện định nghĩa cách một cặp hoặc tập thể hiện phải được gom nhóm trong phân tích cụm. Có hai loại ràng buộc từ thể loại này:
- Ràng buộc Must-link: Nếu ràng buộc must-link được định nghĩa trên hai đối tượng x và y, thì x và y phải được gom vào một cụm trong kết quả phân tích cụm. Các ràng buộc must-link mang tính bắc cầu (transitive), tức là must-link(x, y) và must-link(y,z) thì must-link(x,z).
- Ràng buộc Cannot-link: Ràng buộc cannot-link là ngược lại của must-link. Nếu ràng buộc cannot-link được định nghĩa trên hai đối tượng x và y, thì trong kết quả phân tích cụm, x và y phải thuộc các cụm khác nhau. Ràng buộc cannot-link có thể suy diễn. Nếu cannot-link(x, y), must-link(x, x') và must-link(y, y'), thì cannot-link(x', y').
Ràng buộc trên cụm (Constraints on Clusters)
Ràng buộc trên cụm định nghĩa yêu cầu trên các cụm, có thể dùng thuộc tính của cụm. Ví dụ, ràng buộc có thể định nghĩa số lượng đối tượng tối thiểu trong cụm, đường kính tối đa của cụm, hoặc hình dạng cụm (ví dụ: lồi - convex). Số lượng cụm định nghĩa cho phương pháp phân cụm phân vùng có thể được coi là ràng buộc trên cụm.
Ràng buộc trên đo lường tương đồng (Constraints on Similarity Measurement)
Đo lường tương đồng, bao gồm khoảng cách Euclid, được dùng để tính toán tương đồng giữa đối tượng trong phân tích cụm. Trong nhiều ứng dụng, có ngoại lệ. Ràng buộc trên đo lường tương đồng định nghĩa yêu cầu mà phép tính tương đồng phải tôn trọng.
Ví dụ, có thể gom cụm người như các đối tượng di chuyển trong quảng trường, trong khi khoảng cách Euclid cho khoảng cách đi bộ giữa hai điểm, một ràng buộc trên đo lường tương đồng là quỹ đạo thực hiện khoảng cách ngắn nhất không được đi qua tường.
Có phương pháp khác phân loại ràng buộc phân cụm xem xét mức độ cứng nhắc ràng buộc phải được tôn trọng. Ràng buộc là cứng (hard) nếu phân cụm vi phạm ràng buộc là không thể chấp nhận. Ràng buộc là mềm (soft) nếu phân cụm vi phạm ràng buộc không mong muốn nhưng có thể chấp nhận khi không tìm thấy giải pháp tốt hơn. Ràng buộc mềm còn gọi là sở thích (preferences).