# Common Nearest Neighbor Clustering--A Benchmark
## 4 Results
### Benchmark
#### 4.1.6 Comparison to Other Cluster Algorithms  
To evaluate the obtained results discussed in the former chapters, other cluster algorithms were also tested. One algorithm is the _kMeans(++)_ algorithm [40; 42], as implemented in the MD analysis package _pyEMMA_[41], which is often applied for the analysis of MD simulations. This algorithm shows satisfactory partition for datasets consisting of well-separated spherical clusters such as the _Dim_ sets. However, the more the clusters overlap, the worse the results of the _kMeans++_ algorithm become. For convex clusters (Shape sets), the algorithm fails completely. Hence, a highly increased cluster number is needed to apply to real data, such as MD data. Additionally, the _kMeans(++)_ algorithm is not capable of extracting only the cores and also yields, for most cases, bad boundaries. For further comparison, the results for other _kMeans_ variants are also added to Table 3. The results were taken from [39] and are therefore not further discussed. In [24], we showed that other density-based cluster algorithms are also capable of extracting core sets in MD data. One of these algorithms is the DBSCAN algorithm [6]. There are two main differences between CNN and DBSCAN: (1) The CNN algorithm estimates the data-point density in the region between two data points, whereas DBSCAN estimates the data-point density for which a single data point merges this data point with its neighbors  
Figure 7: Further evaluation of the clustering: (**a**) Parameters \(R\) (solid, left axis) and \(N\) (dashed, right axis) for the clustering of the \(G2\) datasets for 2 (**blue**), 8 (**red**) and 128 (**green**) dimensions. For \(N\) the minimal value is reported for which a split of the two clusters is observed. The colored region highlights the cluster sizes that are possible to extract. We note that beyond \(\sigma=60\) for two dimensions and \(\sigma=70\) for eight dimensions, no split of the clusters is observed. (**b**) Clustering for the _Birch3_ (**upper**) and the _Path-based_ (**lower**) datasets using the common nearest neighbor (CNN), the DBSCAN and the density peaks algorithms.  
independent of whether there is dip in the data-point density or not. (2) The results of DBSCAN depend on the initialization, whereas with CNN, the cluster results depend only on the parameters \(R\), \(N\), and \(M\). For the DBSCAN algorithm, the sorted-9-dist graph as proposed by [6] was applied to determine the cut-off parameter. To make this algorithm comparable to the CNN algorithm, a minimal cluster size of 10 was added. The results of the DBSCAN algorithm show that using this scheme, for most datasets, only worse results compared to the CNN algorithm were obtained. Only for the \(Dim\) datasets [16] were better results observed. However, in [24] we showed that using a comparable scheme for the parameter selection as presented in this paper for the CNN algorithm, better results for the DBSCAN algorithm were observed. It has to be remembered that if the noise level of the dataset is not known in both parameter selection schemes, at least one parameter is chosen manually by the user. For two datasets, the CNN algorithm failed completely: the _Pathbased_ and the _Birch3_ dataset. To check if other density-based cluster algorithms could handle these datasets besides the DBSCAN algorithm, the density peaks algorithm [9; 10] was also evaluated. For the reduced _Birch3_ dataset, both algorithms failed, resulting in a CI of 59 for DBSCAN and a CI of 87 for the density peaks algorithm (\(\delta=10^{5},\rho=100\); 13 clusters isolated). The _Pathbased_ dataset could also not be resolved as a result of the reasons explained above (DBSCAN: 13 clusters; density peaks (\(\delta=10;\rho=2\)): three clusters, but not perfectly resolved). The results for the two datasets are shown in Figure 7b.