# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 4 Experimenting with UCI Datasets  
### Design and Preparation  
The goal of the first experimental study was to evaluate the performance of \(CC\) and \(CCC\) when applied to a set of constrained clustering algorithms in comparison with the performance of the single constrained clustering algorithms. We use standard algorithms and datasets. For the choice of algorithms, we relied on the k-means family, partly because it is well-understood and commonly used, and partly because the constrained versions of its members have been made available online. We selected three semi-supervised k-means algorithms in the _conclust_ R package obtained from [[https://link.springer.com/chapter/10.1007/978-3-540-74958-5_67](https://link.springer.com/chapter/10.1007/978-3-540-74958-5_67)]([https://link.springer.com/chapter/10.1007/978-3-540-74958-5_67](https://link.springer.com/chapter/10.1007/978-3-540-74958-5_67)) (accessed on 2 September 2023): _lcque_[41], _mpckm_[37], and _ccls_[42]. All of them accept a list of objects, the number of clusters, and two lists of must-link and cannot-link constraints as input, and they output a partition of the objects using specific clustering models. The package contains a fourth algorithm, _ckmeans_[36], but we did not include it in the set of base algorithms because it could not process the UCI datasets used for the experiments, which are described below. For the datasets, the aim was to experiment with a varying number of objects, attributes, and classes. However, our choice of data was also determined by the characteristics of the three base clustering algorithms, which require integer or real attributes and do not support extensive experimentation with a large number of objects and attributes due to their inherent computational complexity. We selected four classical UCI datasets (_Glass Identification_, _Seeds_, _User Knowledge Modeling_, and _Vertebral Column_). Each dataset was then enriched with an ordered set of pairs of constraints, as detailed below. Each pair in the set contained a must-link and a cannot-link constraint, such that they could not be deduced from the links in the preceding pairs. The set of constraints was built incrementally: in each step, we added a pair not implied by the current set of constraints through iterative random selection of must-links and cannot-links from the dataset. The procedure halted when it was not possible to find new non-redundant links, eventually producing a cover of the whole set of constraints associated with the dataset. It is worth noting that implication rules rarely apply at the beginning of this process. For instance, during the construction of the cover for the _User Knowledge Modeling_ dataset, the first implied must-link constraint occurred in position 15. Table 2 shows the main features of each dataset and also reports the number of must-links and cannot-links in the cover, as well as the total number of must-links and cannot-links generated by the cover. Note that the sum of the total number of must-links and cannot-links is equal to the total number of constraints given by all possible pairs of objects in the dataset. For instance, the cover for the _Glass Identification_ dataset contains 208 must-links and 208 cannot-links (in this case, there are as many must-links as cannot-links, but the number of must-links and cannot-links present in a cover will, in general, not coincide), from which it is possible to generate 5921 must-links and 16,870 cannot-links. Their sum (i.e., 22,791) is equal to the total number of constraints associated with the objects in the dataset (i.e., \(\frac{214(214-1)}{2}\)), whereas the size of the smallest minimal cover (see Section 3.3) is \(214+\frac{6(6-3)}{2}=223\). To assess the effectiveness of the five clustering algorithms (i.e., the three base algorithms plus \(CC\) and \(CCC\)) in recovering the classes of the UCI datasets, we used the well-known _F measure_, which is thoroughly discussed in [43], together with related cluster validity metrics.