# Common Nearest Neighbor Clustering--A Benchmark
## 4 Results
### Benchmark
\begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline \multicolumn{2}{c}{**Dataset**} & \multicolumn{2}{c}{**CNN**} & \multicolumn{2}{c}{**DBSCAN**} & \multicolumn{4}{c}{**CI**} \\ \hline
**Name** & \(k_{R}\) & \(k_{C}\) & **Noise** & \(k_{C}\) & **Noise** & **CNN** & **DBSCAN** & **kM(++)** & **kM [39]** & **kM (Max) [39]** \\ \hline \multicolumn{10}{c}{A sets [12]} \\ \hline A1 & 20 & 20 & 22\% & 19 & 19\% & 0 & 1 & 1 & 2.5 & 1.0 \\ A2 & 35 & 35 & 22\% & 34 & 18\% & 0 & 1 & 1 & 4.5 & 2.6 \\ A3 & 50 & 50 & 22\% & 50 & 18\% & 0 & 1 & 2 & 6.6 & 2.9 \\ \hline \multicolumn{10}{c}{S sets [13]} \\ \hline S1 & 15 & 15 & 4\% & 16 & 6\% & 0 & 1 & 0 & 1.8 & 0.7 \\ S2 & 15 & 15 & 28\% & 14 & 12\% & 0 & 2 & 1 & 1.4 & 1.0 \\ S3 & 15 & 16 & 46\% & 15 & 20\% & 1 & 5 & 0 & 1.3 & 0.7 \\ S4 & 15 & 16 & 48\% & 12 & 14\% & 1 & 4 & 1 & 0.9 & 1.0 \\ \hline \multicolumn{10}{c}{Birch sets [14]} \\ \hline Birch1 & 100 & 100 & 34\% & 95 & 14\% & 0 & 9 & 4 & 6.6 & 5.5 \\ Birch2 & 100 & 100 & 9\% & 100 & 3\% & 0 & 0 & 0 & 16.6 & 7.3 \\ Birch3 \({}^{A}\) & 100 & 21 & 2\% & & & & & & & \\  & 35 & 11\% & & & & & & & & \\  & 42 & 32\% & 41 & 6\% & 58 \({}^{B}\) & 59 & 16 & — & — \\ \hline \multicolumn{10}{c}{Dim sets [15,16]} \\ \hline Dim-32 & 16 & 16 & 50\% & 16 & 29\% & 0 & 0 & 0 & 3.6 & 0.0 \\ Dim-64 & 16 & 16 & 47\% & 16 & 27\% & 0 & 0 & 0 & 3.7 & — \\ Dim-128 & 16 & 16 & 51\% & 16 & 32\% & 0 & 0 & 0 & 3.8 & — \\ Dim-256 & 16 & 16 & 60\% & 16 & 34\% & 0 & 0 & 0 & 3.9 & — \\ Dim-512 & 16 & 15 & 71\% & 16 & 25\% & 1 & 0 & 0 & 4.1 & — \\ Dim-1024 & 16 & 16 & 78\% & 16 & 26\% & 0 & 0 & 0 & 3.8 & — \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Clustering results for different datasets. The left part shows the number of isolated clusters \(k_{C}\) for the common nearest neighbor (CNN) and the DBSCAN algorithm (compared to the reference number of cluster \(k_{R}\)) as well as the percentage of data points declared as noise. The right part shows the centroid index at cluster level (CI) [37] using the CNN algorithm, the DBSCAN-algorithm and the _kMeans(++)_ algorithm (_kM_(++)) [40] as implemented in _pyEMMA_[41]. The CI values are compared to reference values provided by the authors of [39] for the _kMeans_ algorithm [42] using a random initialization (kM) and using a further point heuristic (Max) [43] initialization. The reference data were averaged over 5,000 runs. \({}^{A}\) Hierarchical clustering was necessary. \({}^{B}\) After the last clustering step. To determine the quality of the clustering, we visually inspected the results (Figure 2). Additionally, we used the CI [37]. This measure maps the original centroids of the dataset (if available) to the centroids obtained by the clustering algorithm and counts mismatches. A perfect clustering has a CI of zero. As a third criterion, we analyzed the distribution of pairwise distances within each cluster (Figure 5). For datasets without any nested clusters, the distance distribution within each cluster should show a single maximum. Otherwise, the cluster can be split into two separate clusters. This is even true for datasets with convex but well-separated clusters; see, for example, datasets _Compound_[19] and _Spiral_[22]. However, if the dataset contains convex clusters that are nested at a very small distance, the rule does not apply. This is shown for the dataset _t4.8k_[2]. CNN clustering correctly partitioned the vast majority of the benchmark datasets (Figure 2 and Table 3). To obtain a deeper insight into the performance of the CNN algorithm as well as the dependency on the choice of parameters, we analyzed the clustering results with respect to five main challenges of typical datasets: (1) differences in cluster size and shape; (2) number of clusters; (3) unbalanced data-point density; (4) cluster overlap; (5) dimensionality of the dataset.