Constraint-Based Cluster Analysis

1. Motivation

Pure clustering is data-driven only — it ignores the user's domain knowledge, preferences, physical limitations and application semantics. Constraint-based clustering searches for clusters that satisfy user-specified constraints, which:

Reduces the search space and produces more meaningful, actionable clusters,
Lets background knowledge (e.g. 'a delivery zone must be reachable in 30 minutes', 'a class size must be ≤ 40') be enforced directly,
Makes clustering interactive and domain-aware.

Constraints can come from: domain knowledge, application semantics (capacity, budget), physical constraints (road networks, obstacles), user preference, and data quality requirements (must-link / cannot-link).

2. Types of Constraints

Type	Meaning	Example
Must-link (equivalence)	Two objects must be in the same cluster	Same criminal record ⇒ same person
Cannot-link (inequality)	Two objects must be in different clusters	Different customer ids
Capacity / cardinality constraint	Each cluster must contain between $l$ and $u$ objects	School class size 20-40 students
Balancing constraint	Clusters must have (roughly) equal sizes	Fair workload partition
Minimum separation / radius	Cluster diameter or radius bounded	Fire station must be within 10 km
Density threshold	Density in each dimension must exceed a threshold	Micro-array clustering requiring co-expression in every experimental condition
Obstacle / connection constraint	Clusters must be connected through free space; obstacles cannot be crossed	Cable routing around buildings
Ordering / monotonicity constraint	Values along a dimension must be monotone within the cluster	Time-series / sequence clusters with a trend
User-given preference	Specific dimensions, weights, or attribute preferences	"Cluster mainly on income and age"

Formally, a constrained clustering problem looks for a partition $\mathcal{P} = \{C_1,\dots,C_k\}$ such that:

\bigcup_{i=1}^{k} C_i = D,\quad C_i \cap C_j = \emptyset,\quad \text{and}\quad \mathcal{P} \models \mathcal{K}\ \ (\text{all constraints in } \mathcal{K} \text{ satisfied})

3. Hard vs Soft Constraints

	Hard constraint	Soft constraint
Violation	Not allowed at all	Allowed with a penalty
Effect	Restricts the feasible solution space	Weights the objective (trade-off)
Example	Number of clusters exactly $k$	Clusters as balanced as possible
Techniques	Constrained k-means, COP-k-means, graph partitioning with must/cannot-link edges	Penalised objective / Lagrangian relaxation: $\min\ \text{SSE}(C) + \lambda\cdot\text{violations}(C)$

4. Clustering with Obstacles and Facilitators

Objects, obstacles and facilitators are all represented in the same spatial space.

Obstacles — regions that cannot be crossed (lakes, mountains, buildings, property lines).
Facilitators — regions that ease movement (highways, rivers, conveyor belts).
The distance between two objects is no longer Euclidean but shortest-path (obstacle) distance.

Example grid with an obstacle X:

  A . . . . . .          Euclidean d(A,B) = 7 cells
  . . X X X X .          Obstacle path must go around:
  . . X . . X .            A -> down/up around the wall -> B
  . . X . . X .            obstacle distance = 9 cells (the cluster that
  . . X X X X .            respects the obstacle may split into two)
  . . . . . . B

 d_obstacle(A,B) >= d_Euclidean(A,B),   and clusters must be
 connected through obstacle-free space only.

Clustering with obstacles/density constraints (COD / DBCluC style):

Start from density-based clustering (DBSCAN-like) so clusters are arbitrary shapes.
Micro-clusters and then clusters are merged only if they are connected by micro-clusters meeting the density requirement, and no obstacle boundary is crossed.
Merge cost combines density, size, connectivity and shape of the resulting cluster.

5. Constraint-Based Clustering Algorithms

Algorithm	Constraint handled
COP-k-means (Constrained K-means)	Must-link / cannot-link; assignment violates a cannot-link ⇒ algorithm fails
Constrained DBSCAN	Must-link / cannot-link combined with density reachability
C-DBSCAN / DBCluC	Density threshold in every dimension, obstacles
COD (Clustering with Obstacle Distance)	Obstacles and facilitators in spatial data (uses the obstacle distance matrix and micro-cluster merging)
Clustering with balancing constraints (CBLO / balanced k-means, MinCostFlow)	Equal-sized clusters — minimises a balanced sum of squares and uses a minimum-cost flow algorithm to enforce capacity
Constrained graph partitioning / spectral	Partition the graph with must/cannot-link edges
Fuzzy/soft constrained clustering	Membership degrees + penalties for soft constraints

Balanced clustering objective (balancing the cluster sizes $n_1,\dots,n_k$ ):

\text{Sum of squares } \mathcal{Q}(\mathcal{P})=\sum_{i=1}^{k}\sum_{p\in C_i}\|p-\bar C_i\|^{2},\qquad \text{balanced version: minimise } \sum_{i=1}^{k}\frac{1}{n_i}\sum_{p\in C_i}\|p-\bar C_i\|^{2}

6. Worked Example — Constrained k-means (must-link / cannot-link)

Points: A(1,1), B(1.2,1.1), C(5,5), D(5.2,5.1); constraints: must-link(A,B), cannot-link(A,C), $k=2$ .

Initialise centroids at $\mu_1=(1,1.1)$ (A, B), $\mu_2=(5,5.05)$ (C, D).
Assign: A and B both nearest $\mu_1$ → consistent with must-link ✔; A and C are in different clusters ✔.
Update: $\mu_1=(1.1,1.05)$ , $\mu_2=(5.1,5.05)$ ; reassignment leaves the same partition.
If instead A had been assigned to $\mu_2$ , the cannot-link(A,C) constraint would be violated and the assignment must be rejected.

7. Applications

GIS / facility location: school districts, ambulance/fire-station service zones respecting roads, rivers and capacity.
Micro-array / gene expression: clusters that are dense in every experimental condition (user-specified conditions).
Telecom network design: clustering of base stations with capacity and backhaul constraints.
Manufacturing / VLSI: partition cells with area and pin constraints.
Image segmentation with must-link (same region) from the user's scribbles.
Marketing / CRM: segment sizes must be big enough to be actionable, must respect pre-existing segments.
Document/entity resolution: must-link and cannot-link from rules ('same SSN ⇒ same person').

8. Exam Points

Define constrained clustering; classify constraints (hard/soft, must-link/cannot-link, capacity, density, obstacle) with examples — 7-10 marks (frequent).
Explain clustering with obstacles and facilitators, and how the distance measure changes — 7 marks.
Explain balanced clustering and its objective; how a minimum-cost-flow solution enforces capacity — 5-7 marks.
Give two real applications of constraint-based clustering with justification — 3-5 marks.

Constraint-Based Cluster Analysis