# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 3 Double-Constrained Consensus Clustering Framework
### Analysis of Constraints  
First, consider the number of constraints associated with \(n\) objects and \(m\) partitions. There may be at most \(\frac{n(n-1)}{2}\) constraints, one for each possible pair of objects (this bound is independent of \(m\)). Let us denote this set as \(C\). By analogy with the theory of functional dependencies, the logical implication between constraints can be characterized by two axioms (or inference rules):  
\[ \begin{array}{l}\text{\it transitivity}\\ \text{if }\ \Pi(i)=\Pi(j)\ \text{ and }\ \Pi(j)=\Pi(l)\text{, then }\ \Pi(i)=\Pi(l)\\ \text{\it composition}\\ \text{if }\ \Pi(i)=\Pi(j)\ \text{ and }\ \Pi(j)\
eq\Pi(l)\text{, then }\ \Pi(i)\
eq\Pi(l)\end{array} \]  
These logical properties of constraints are well known, although they have been expressed in various ways. It follows that the deductive closure of a set of constraints is the complete set of all possible constraints that can be derived from the given set using the inference rules. We can now modify the second addend in Expression (6) to take into account all the constraints provided as inputs, whether explicitly or implicitly. It suffices to compute the deductive closure of the input constraints, denoted as \(\text{\it Ded}(\{ML\}\cup\{CL\})\), and then use all the constraints in it to compute the numerator and the denominator in Expression (6). The objective function to be maximized becomes:  
\[ \begin{array}{l}\Psi_{c}(\Pi,\Pi_{1},\ldots,\Pi_{q},ML,CL)=\frac{1}{q}\sum _{r=1}^{q}\ PRI\left(\Pi,\Pi_{r}\right)\ +\\ \frac{\sum_{(i,j)\in ML}\mathbb{1}\left[\Pi(i)=\Pi(j)\right]+\sum_{(i,j)\in CL ^{*}}\mathbb{1}\left[\Pi(i)\
eq\Pi(j)\right]}{|\text{\it Ded}(\{ML\}\cup\{CL\})| }\end{array}  \tag{7}\]  
where \(ML^{*}\) and \(CL^{*}\) are, respectively, the set of must-link and cannot-link constraints in \(\text{\it Ded}(\{ML\}\cup\{CL\})\). An optimal constrained consensus partition \(\Pi_{c}^{opt}\) is then given by:  
\[\Pi_{c}^{opt}=\operatorname*{arg\,max}_{\Pi}\Psi_{c} \tag{8}\]  
The dependencies between constraints also naturally lead to the definition of minimal cover, which is useful for characterizing the behavior of clustering algorithms as the number of constraints varies. A minimal cover \(M\) of \(C\) is a set of constraints, such that (i) \(M\) is equivalent to \(C\) (i.e., it is possible to generate \(C\) from \(M\) by repeatedly applying the axioms to the constraints in \(M\)), and (ii) we cannot remove any constraint from \(M\) and still have a set of constraints that are equivalent to \(C\). A minimal cover of the whole set of constraints associated with \(n\) objects partitioned into \(m\) clusters can be easily constructed using the following procedure. For each cluster in the partition, we need to express two properties. The first is that all objects in the cluster are co-clustered (this requires, by transitivity, as many must-link constraints as the number of objects in the cluster minus one). The second is that the objects in the cluster cannot be co-clustered with the objects in each of the remaining clusters (this requires, by composition, as many cannot-link constraints as all the possible pairs of \(m\) clusters). This minimal cover thus has a size of \(n-m+\frac{m(m-1)}{2}=n+\frac{m(m-3)}{2}\). Different minimal covers of the same size can be constructed by choosing the objects involved in the \(n-m\) must-link and \(\frac{m(m-1)}{2}\) cannot-link constraints in alternative ways. These are the smallest minimal covers associated with \(n\) objects partitioned into \(m\) clusters. The following example illustrates the concepts described so far, including the process that leads to the generation of multiple smallest minimal covers. Consider a set of five objects \(\{0_{1},0_{2},0_{3},0_{4},0_{5}\}\) with three input constraints: \(\Pi(1)=\Pi(2)\), \(\Pi(2)=\Pi(3)\), and \(\Pi(3)\
eq\Pi(4)\). We can derive three logically implied constraints: \(\Pi(1)=\Pi(3)\), by transitivity, and \(\Pi(1)\
eq\Pi(4)\), \(\Pi(2)\
eq\Pi(4)\), by composition.