# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 2 Related Works
### Semi-Supervised Ensemble Clustering  
In their survey on ensemble learning [6], which focuses on semi-supervised ensemble clustering, the authors pointed out that existing semi-supervised ensemble clustering algorithms make unsatisfactory use of constraint information, and they encouraged more research on this issue. We have addressed this issue from two perspectives, as described below. Previous work on semi-supervised ensemble clustering can be described according to the strategy used for combining constraints and consensus clustering. The most common approach consists of using constraints prior to ensemble clustering to identify better base partitions. [PERSON] et al. [8] used constraints to eliminate redundant ensemble members from a larger set generated using the random subspace method [9], where member selection is driven by an objective function that incorporates constraints and the similarity of attributes in the subspaces. The selection of ensemble members was also pursued in [10; 11], again using the random subspace method. In [10], constraints were used to transform features after their random generation, whereas in [11], constraints were projected onto subspaces and weighted. Two other different examples of the first combination strategy can be found in [12; 13]. In [12], constraints were used within a specific clustering algorithm (i.e., semi-supervised spectral clustering [14]) to build constrained base partitions before their merging using an unconstrained consensus algorithm. This is similar to the first step of our double-constrained framework. In [13], confidence scores were assigned to each ensemble member based on its compliance with constraints, and the weighted partitions were then merged through a consensus matrix. The second main strategy is to incorporate domain knowledge directly within the construction of the clustering ensemble, rather than using it as a pre-processing technique. In [15; 16], constraints were used to modify the graph-based consensus function of Chameleon [17] to make more informed decisions when merging or splitting subgraphs. In [18], constraints were integrated into a consensus function based on frequent closed itemset mining; similar to CCC, the number of clusters in the consensus partition does not need to be specified. In [19], constraints were used to compute the similarity matrix associated with ant colony clusterings, modifying the pick-up and drop-down probabilities. In [20], consensus clustering was cast as a form of semi-supervised hierarchical clustering, and the base partitions were provided by HAC algorithms. A third, seldom-explored combination strategy is to refine the clustering ensemble using constraints after its generation. In [21], an initial consensus partition was modified to strictly satisfy the constraints while changing as little as possible. The cluster similarity is modeled through anchors, (i.e., sets of data points that are representative of clusters), and the optimization framework is cast as an integer linear programming problem. Compared to earlier works, our combination strategy is different because constraints are used in two distinct phases of the semi-supervised ensemble clustering process, namely for generating ensemble members and for merging them. To the best of our knowledge, this is novel. While it can be argued that other existing (single) constrained consensus clustering algorithms may, in principle, be applied to constraint-enhanced rather than unconstrained base partitions (thus becoming double-constrained approaches), so far, this hypothesis has neither been explicitly considered nor been experimentally evaluated. Aside from combination strategies, a few earlier works have focused on the treatment of constraints in an attempt to extract additional knowledge from them. Building upon [22], [PERSON] et al. [8] generated a constraint matrix in which supervised information is propagated from labeled to unlabeled pairs of objects using q-nearest-neighbor graphs.