# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 1 Introduction  
Today, after many years of research, there are specialized clustering algorithms that can find groupings with complex contiguous shapes in data that were previously impossible to identify. However, it is well known that no single algorithm is suitable for all datasets because the groups may be similar or dissimilar for very different reasons. The diversity of approaches reflects the difficulty of providing a formal definition of clustering ([1, 2]). This phenomenon has been concisely described using the expression 'clustering is in the eye of the beholder'. The subjectivity issue is compounded by sensitivity to design factors. When clustering a dataset, we are confronted with a number of choices: the clustering algorithm family (e.g., hierarchical agglomerative clustering, k-means, spectral, density-based), the clustering family instance (e.g., the linkage method for hierarchical agglomerative clustering), the setting of clustering instance parameters (e.g., cutoff threshold), and the data features used for clustering. A change in any of these factors often results in significant overall performance variations. The user must thus grapple with the dilemma of selecting appropriate techniques, parameters, and features, given the dataset to be investigated. These inherent limitations have spurred explorations of ways to add other sources of evidence to the clustering process, beyond the paradigm of a single unsupervised algorithm. One line of research, termed ensemble clustering (or consensus clustering), has focused on merging multiple clustering partitions into a consensus partition that shares their common characteristics and is more robust to changes and errors compared to individual methods [3]. Another area of research, termed semi-supervised clustering, has investigated the use of a limited amount of domain knowledge, such as cannot-link and must-link constraints in the clustering process, to find a solution that is more aligned with the user's preferences (e.g., [4], which focuses on semi-supervised k-means algorithms, and [5], which covers several clustering families). While the two lines of research arose independently, in recent years, we have seen several attempts to combine them in an effort to retain the main advantages of each. The semi-supervised ensemble clustering algorithms that have been proposed so far, as reviewed in [6], exploit various combination strategies. Constraints have been used to create or select better ensemble members prior to their merging, to find a better consensus partition from unenhanced given partitions, or to refine the consensus partition after its generation. However, constraints are usually employed to improve only one of the steps involved in the semi-supervised ensemble clustering process. Moreover, most approaches use constraints as they are, without trying to infer more knowledge from them. Our work was inspired by a desire to make the most of constraints, extending their use and understanding in the semi-supervised ensemble clustering process. In the proposed framework, the role played by constraints is twofold. First, they are used to enhance the generation of the base partitions. Second, the same constraints are used again to combine the enhanced base partitions. To the best of our knowledge, this combination strategy, as depicted in Figure 1, is novel. In this article, we do not dwell on the generation of constrained base partitions. We assume that the base clustering algorithm or algorithms are equipped with a constraint-enhanced version and that their results are provided as input. Our focus is on the merging of these results, aided by constraints, and on the benefits of the double use of constraints. It should be noted that the terms partition and clustering are used interchangeably throughout this paper.