# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 3 Double-Constrained Consensus Clustering Framework
### Constrained Consensus Clustering as an Optimization Problem  
A very common and general approach to consensus clustering consists of casting it as an optimization problem, where the objective is to find a consensus partition \(\Pi^{opt}\), such that the similarity \(\Psi\) between \(\Pi^{opt}\) and \(q\) base partitions \(\Pi_{1},\Pi_{2},\ldots,\Pi_{q}\) built using \(q\) base clustering algorithms is maximal:\[\Pi^{opt}=\underset{\Pi}{\arg\max}\ \Psi(\Pi,\Pi_{1},\ldots,\Pi_{q}) \tag{3}\]  
The objective function \(\Psi\) can be defined in terms of a pairwise similarity measure:  
\[\Psi(\Pi,\Pi_{1},\Pi_{2},\ldots,\Pi_{q})=\frac{1}{q}\sum_{r=1}^{q}\ PRI\left( \Pi,\Pi_{r}\right) \tag{4}\]  
Here, we use the PRI because it is more reliable than the RI, especially when, as in many domains of interest, including online anti-counterfeiting, the number of clusters to find may be high. Following [36], we now assume that background knowledge is given in the form of pairwise constraints that indicate whether two objects should be in the same cluster. This form of supervision is more realistic than providing class labels in many applications and is also more general: a set of classified points implies an equivalent set of pairwise constraints, but not vice versa [37]. Specifically, we assume that we are given a set of must-link constraints \(ML\), where \((i,j)\in ML\) indicates that objects \(o_{i}\) and \(o_{j}\) should be in the same cluster. Similarly, we are given a set of cannot-link constraints \(CL\), where \((i,j)\in CL\) indicates that objects \(o_{i}\) and \(o_{j}\) should be in different clusters. Using \(\Pi(i)=k\) and \(\Pi(i)\
otin k\), we denote, respectively, that in partition \(\Pi\) object \(o_{i}\) is, or is not, an element of cluster \(\pi_{k}\). The two sets of constraints may be exploited using the base clustering algorithms to generate constrained base partitions as input. This is our reference scenario, but the consensus clustering framework can also be applied to unconstrained base partitions. We can then use the provided constraints to modify our objective function. One possibility is to require that the consensus partition should strictly respect the constraints, which would lead to the following optimization problem:  
\[ \begin{array}{ll}\text{Maximize}&\frac{1}{q}\sum_{r=1}^{q}\ PRI\left(\Pi, \Pi_{r}\right)\\ \\ \text{\emph{subject to}}&\Pi(i)=\Pi(j),\forall(i,j)\in ML;\\ &\Pi(i)\
eq\Pi(j),\forall(i,j)\in CL\end{array}  \tag{5}\]  
However, this formulation does not allow for exceptions: all the constraints must be satisfied. Such a requirement is, in general, not the best choice [38], and in our case, it may further complicate the search for an admissible consensus partition because the input partitions do not necessarily satisfy the given constraints. It seems more convenient to use soft constraints, where compliance is rewarded but violation is still allowed. Maximizing both the similarity to the input partitions and the compliance with constraints naturally leads to the following form of the objective function, where the second addend is the percentage of the given constraints that are satisfied by the (constrained) consensus partition:  
\[\frac{1}{q}\sum_{r=1}^{q}\ PRI\left(\Pi,\Pi_{r}\right)\ +\ \frac{\sum_{(i,j)\in ML}\mathbb{I}\left[\Pi(i)=\Pi(j) \right]+\sum_{(i,j)\in CL}\mathbb{I}\left[\Pi(i)\
eq\Pi(j)\right]}{|ML|+|CL|} \tag{6}\]  
In the above expression, \(\mathbb{I}\) is an indicator function with a value of \(1\) if the enclosed expression is true and \(0\) otherwise, whereas \(ML\) and \(CL\) refer to the constraints provided as inputs. We now have to consider the fact that constraints are not independent. In a set of given constraints, some of them may be logically implied by others, while there may also be constraints not in the set that can be derived from those in the set. This issue affects the actual compliance of the consensus partition with the initial constraints, extending their usefulness in the clustering process through implicit constraints.