# Double-Constrained Consensus Clustering with Application to Online Anti-Counterfeiting
## 4 Experimenting with UCI Datasets
### Results  
We first studied the behavior of the single base clustering algorithms with respect to the number of constraints. For each dataset, we ran the three algorithms using the set of constraint pairs associated with the dataset (produced as described in the preceding section). More specifically, growing subsets of pairs were provided as input to each algorithm by taking the pairs in their order until the last pair in the set. We considered the full spectrum of constraints rather than only a small percentage, as was often reported in previous studies, because this results in a better understanding of the potential and limitations of constraints to aid in the clustering process. Clustering effectiveness was measured using the _F measure_. The results are shown in Figure 2. There are four charts, one for each dataset. Each point on the x-axis of a chart refers to a set of constraint pairs, from the set with one pair (containing one must-link and one cannot-link) to the set that is as large as the cover of the specific dataset of the chart, as detailed in Table 2. The four charts thus have different x-axis scales. It is worth noting that the point with zero constraints is not depicted because the three clustering algorithms used were not run with an empty set of constraints. Figure 2 suggests that, in general, performance increased as more constraints were seen, although with frequent ample oscillations and with modest overall gains in performance for some combinations of clustering algorithms and datasets. These findings are consistent with those reported in [44] for a restricted percentage of constraints. However, rather surprisingly, even when applying 100% of constraints, only one algorithm achieved the maximum performance on all datasets, with the other two algorithms not performing particularly well on some datasets. The likely explanation is that at least some of these algorithms disregarded the implication issue, thus not taking full advantage of the constraints. Aside from the absolute results, we were interested in the relative performance of the three algorithms. Figure 2 shows that they were deeply affected by the specific dataset and  
Figure 2: Performance of the three base clustering algorithms (ccs, lcvqe, mpckm) as a function of the number of constraints (on the x-axis) for each of the four UCI datasets (User Knowledge Modeling, Seeds, Vertebral Column, Glass Identification). Performance is expressed through the F measure (on the y-axis). the number of constraints used. In detail, _mpckm_ generally performed the best with a very large number of constraints, while with fewer constraints, it achieved the worst results for many data points on the _Seeds_ and _Vertebral Column_ datasets due to its ample oscillations. Also, _lcvape_ achieved very good results (without dropping spikes) on the _Seeds_ dataset and, with a more limited range of constraints, on the _Vertebral Column_ dataset, but it performed badly for most data points on the _User Knowledge Modeling_ and _Glass Identification_ datasets. Finally, _ccls_ struck a better balance between good and bad results due to its greater stability, although it achieved the best results only for some data points on the _Glass Identification_ dataset. Having seen that there was no single best algorithm across the different datasets and sets of constraints, the question arose of whether it was possible to mitigate the inherent lack of robustness of individual algorithms and improve their average effectiveness through consensus clustering techniques. We now address this issue. For each dataset and each set of constraint pairs associated with it, we computed the three (constrained) partitions generated by the clustering algorithms and then used them as inputs to both \(CC\) and, again, together with constraints, \(CCC\). In all, we computed \(5\times(208+207+282+340)=5185\) partitions. Figure 3 shows the performance of CC and CCC as a function of the number of constraints.