# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 1 Introduction
Building on the consensus clustering framework introduced in [7], which maximizes the similarity (based on the Probabilistic Rand Index) between a consensus partition and a set of given partitions, we modify its objective function to incorporate must-link and cannot-link constraints. It should be noted that the terms partition and clustering are used interchangeably throughout this paper. Compliance with the given constraints is expressed in terms of the percentage of constraints that are satisfied by the consensus partition, modeling the logical implication between constraints using a deductive closure concept derived from the theory of functional dependencies. The resulting optimization problem is solved using a simple stochastic hill-climbing strategy, preceded by an ad hoc procedure for computing the deductive closure of the input constraints. The overall algorithm is termed _CCC_, which stands for double-constrained consensus clustering. We also define a  
Figure 1: Overview of the architecture of double-constrained consensus clustering. procedure to build a minimal cover for a set of constraints, which is useful for evaluation purposes. We then present two experimental studies. In the first, conducted on standard UCI datasets, we found that by using \(CCC\), there was a marked improvement over merging the constrained base partitions with plain consensus clustering (\(CC\)). We also observed that the performance of \(CCC\), measured as a function of the main clustering factors, was not only clearly better than the average performance of the base-constrained partitions but also almost on a par with their best performance, achievable for a specific combination of clustering feature and constrained base clustering algorithm on each dataset. The second experimental study looked at web anti-counterfeiting. We applied \(CCC\) to the problem of detecting affiliate marketing programs behind fraudulent e-commerce websites. We argue that the interesting feature of this application domain is that constraints can be partly acquired automatically, thus making the overall approach more appealing and useful. The potential of \(CCC\) for discovering affiliate programs is demonstrated using a new test collection made available for reuse. The main contributions of this article are as follows:  
* We define a novel framework for semi-supervised consensus clustering that exploits constraints both to build the base partitions and to combine them through an optimization-based constrained consensus clustering algorithm. The framework is implemented in a system named \(CCC\). * We offer an analysis of the logical implications between constraints that help optimize their use not only in \(CCC\) but also in any clustering algorithm making use of must- and cannot-link constraints. * We present an experimental evaluation using the UCI datasets, showing that the re-utilization of constraints within the consensus function that combines base-constrained partitions is more effective than using unenhanced consensus clustering. * We demonstrate the potential of using CCC to analyze counterfeit web shops and detect affiliate programs. This is achieved through a comprehensive approach starting from raw data and including the automatic generation of constraints and experimentation with a new test collection made available for use. The remainder of this paper is organized as follows. In Section 2, we discuss related works, divided into two main themes: semi-supervised ensemble clustering and clustering fraudulent websites. Section 3 is devoted to the double-constrained consensus clustering framework. After providing some notations and background information, we formalize it as an optimization problem that exploits the logical implications between constraints and provides a heuristic solution. In Section 4, we describe the study conducted using the UCI datasets, detailing its design, preparation, and findings.