# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 3 Double-Constrained Consensus Clustering Framework
### A Heuristic Solution  
The input of the algorithm is a set of objects, a set of constrained partitions of the objects, and two sets of constraints (must-link and cannot-link). Its output is an optimal double-constrained consensus partition of the objects. Note that, unlike most semi-supervised ensemble clustering algorithms, the input partitions may have a different number of clusters, and CCC does not require the number of clusters in the consensus partition as an input parameter.  
The first step of the algorithm is the computation of the deductive closure of the input constraints based on the inference rules introduced in Section 3.3. We examine one constraint at a time and incrementally update the current set of holding constraints. If the new constraint is a must-link between objects \(i\) and \(j\), then we create a new must-link between any object co-clustered with \(i\) and any object co-clustered with \(j\), and, in addition, we create a cannot-link between any object that cannot be co-clustered with \(i\) and any object that cannot be co-clustered with \(j\). If the new constraint is a cannot-link between objects  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \(o_{1}\) & \(o_{2}\) & \(o_{3}\) & \(o_{4}\) & \(o_{5}\) \\ \hline \(o_{1}\) & & & & \\ \(o_{2}\) & \(1\) & & & \\ \(o_{3}\) & \(\mathbf{1}\) & \(1\) & & \\ \(o_{4}\) & \(\mathbf{-1}\) & \(\mathbf{-1}\) & \(\mathbf{-1}\) & \\ \(o_{5}\) & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 1: Example database with explicit and implicit (in bold) constraints.  
and \(j\), then we create a cannot-link between any object co-clustered with \(i\) and any object co-clustered with \(j\). With the deductive closure, it is possible to calculate the value of the objective function (Expression (7)) for any set of partitions and constraints. The next step is to find an optimal partition.  
We used a simple, efficient stochastic hill-climbing strategy, as used in [7; 39] and for similar objective functions not enriched with constraints. It consists of starting with a partition and iteratively moving a single object to a different (possibly empty) cluster until the objective function (Expression (7)) associated with the newly created partition and the given set of constraints increases. This procedure is very efficient and experimentally generates good approximate solutions. We checked that using alternative meta-heuristic optimization strategies [40] that are, in principle, more powerful for avoiding local optima, such as simulated and quantum annealing, did not produce better results. These findings are analogous to those reported in [7; 39].  
In the implementation of the \(CCC\) algorithm, the seed (initial) partition is the input partition with the highest similarity value with the given partitions. Successors are selected randomly, and the computation is halted after testing all possible \(nm\) successors for the current partition. These choices were made after extensive experimentation with other possible ways of choosing the seed partition, such as emphasizing its compliance with constraints, as well as with different termination criteria, such as random-restart hill climbing. The full algorithm is described in Algorithm 1.  
```
0: A set \(O\) of \(n\) objects A set \(SP\) of \(q\) (constrained) partitions \(\{\Pi_{1},\ldots,\Pi_{q}\}\) of \(O\) A set \(ML\) of must-link constraints A set \(CL\) of cannot-link constraints Output: A partition \(\Pi_{c}\) of \(O\)
1. Find \(Ded(\{ML\}\cup\{CL\})\).
2. Set \(\Pi_{c}\) to the input partition with the highest \(\Psi^{c}\) similarity with \(SP\).
3. Assign an object in \(\Pi_{c}\) to a different (possibly empty) cluster such that the newly created partition \(\Pi^{\prime}\) has a higher \(\Psi^{c}\) similarity with \(SP\) than \(\Pi_{c}\).
4. Update \(\Pi_{c}\) to \(\Pi^{\prime}\).
5. Iterate between (3) and (4) until no partition with a higher \(\Psi^{c}\) has been found.
6. Return \(\Pi_{c}\).
```  
**Algorithm 1** The double-constrained consensus clustering (CCC)