# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 3 Double-Constrained Consensus Clustering Framework  
### Notations and Background  
Given a set \(O\) of \(n\) objects \(O=\{o_{1},\ldots o_{n}\}\), a partition \(\Pi=\{\pi_{1},\ldots\pi_{m}\}\) of \(O\) is a grouping of the elements of \(O\) into \(m\) non-empty subsets (or clusters) in such a way that every element is included in one and only one of the subsets; i.e, \(\bigcup_{i=1}^{m}\pi_{i}=O\) and \(\pi_{i}\cap\pi_{j}=\emptyset\), for \(1\leq i\
eq j\leq m\).  
The similarity between two different partitions is key to consensus clustering. One of the best-known similarity strategies is the Rand index [33], which measures the agreement among the decisions made by the two partitions on individual pairs of objects. Given two partitions of \(O\) to compare, \(\Pi_{1}=\{\pi_{1,1},\ldots\pi_{1,m_{1}}\}\) and \(\Pi_{2}=\{\pi_{2,1},\ldots\pi_{2,m_{2}}\}\), the Rand index (\(RI\)) is defined as:  
\[RI=\frac{n_{11}+n_{00}}{n_{00}+n_{01}+n_{10}+n_{11}}=\frac{n_{11}+n_{00}}{ \left(\begin{array}{c}n\\ 2\end{array}\right)} \tag{1}\]  
where:  
* \(n_{11}\) is the number of pairs of objects that are in the same cluster in both \(\Pi_{1}\) and \(\Pi_{2}\);
* \(n_{00}\) is the number of pairs of objects that are in different clusters in both \(\Pi_{1}\) and \(\Pi_{2}\);
* \(n_{10}\) is the number of pairs of objects that are in the same cluster in \(\Pi_{1}\) but in different clusters in \(\Pi_{2}\);
* \(n_{01}\) is the number of pairs of objects that are in different clusters in \(\Pi_{1}\) but in the same cluster in \(\Pi_{2}\).  
Intuitively, one can think of \(n_{11}+n_{00}\) as the number of agreements between \(\Pi_{1}\) and \(\Pi_{2}\), and \(n_{10}+n_{01}\) as the number of disagreements between \(\Pi_{1}\) and \(\Pi_{2}\). The Rand index has a value between 0 (i.e., no agreement on any pair of objects, which happens only when one partition consists of a single cluster while the other consists only of clusters containing single objects) and 1 (i.e., when the two partitions coincide).  
The problem with the Rand and other pair-counting-based indices such as the Adjusted Rand Index [34] is that the individual contribution of the different types of agreements and disagreements to the overall similarity is the same, even when there is a high probability that they occurred by chance. The Probabilistic Rand Index (PRI), introduced in [7], further analyzed in [35], and recently made available for use at [[https://github.com/giannromao8](https://github.com/giannromao8)]([https://github.com/giannromao8](https://github.com/giannromao8)) /Probabilistic-Rand-Index (accessed on 2 September 2023) is based on the observation that as the number of clusters grows, the likelihood of a pair of objects being placed in the same cluster decreases, while at the same time, the likelihood of being placed in different clusters increases. Using the PRI, agreements and disagreements are inversely weighted with the probability of their occurring by chance:  
\[PRI=\frac{w_{11}\cdot n_{11}+w_{00}\cdot n_{00}}{w_{00}\cdot n_{00}+w_{01} \cdot n_{01}+w_{10}\cdot n_{10}+w_{11}\cdot n_{11}} \tag{2}\]  
In Equation (2), the weights are estimated with the self-information (i.e., \(w_{11}=-\log_{2}\ p_{11}\), \(w_{00}=-\log_{2}\ p_{00}\),...), and the probabilities are expressed as a function of the number of clusters in each partition:  
* \(p_{11}=\frac{1}{m_{1}}\cdot\frac{1}{m_{2}}\),
* \(p_{00}=\frac{m_{1}-1}{m_{1}}\cdot\frac{m_{2}-1}{m_{2}}\),
* \(p_{10}=\frac{1}{m_{1}}\cdot\frac{m_{2}-1}{m_{2}}\),
* \(p_{01}=\frac{m_{1}-1}{m_{1}}\cdot\frac{1}{m_{2}}\).