# Common Nearest Neighbor Clustering--A Benchmark
## 1 Introduction
Density-based clustering algorithms [4; 5; 6; 7; 8; 9; 10] circumvent this problem by using the number of data points in the neighborhood of a data point \(\mathbf{x}_{i}\) as a proxy for the data-point density. As a consequence, the objective function of these algorithms is often only given implicitly [11]. Figure 1: (**a**) Potential energy surface (PES) spanned by two coordinates \(x1\) and \(x2\); (**b**) trajectories within the PES (projection onto \(x1\) and \(x2\)); (**c**) Boltzmann distribution of the PES divided into three states; (**d**) core sets (**blue**) within the Boltzmann distribution; all non-assigned data points are outside the core sets. \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**Dataset**} & \multicolumn{4}{c}{**CNN Parameter**} & \multicolumn{4}{c}{**DBSCAN Parameter**} \\ \hline
**Name** & \(n\) & \(d\) & \(k_{R}\) & \(R\) & \(N\) & \(M\) & \(Eps\) & \(MP\) & \(M\) \\ \hline \multicolumn{10}{c}{A sets [12]} \\ \hline A1 & 3000 & 2 & 20 & \(1\times 10^{3}\) & 9 & 10 & 800 & 9 & 10 \\ A2 & 5200 & 2 & 35 & \(1\times 10^{3}\) & 9 & 10 & 800 & 9 & 10 \\ A3 & 7500 & 2 & 50 & \(1\times 10^{3}\) & 9 & 10 & 800 & 9 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Properties of the benchmark datasets: \(n\): dataset size; \(d\): dimensionality; \(k_{R}\): reference number of clusters. Parameters for the common nearest neighbor (CNN) algorithm: \(R\) and \(N\): cluster parameter set; \(M\): minimal cluster size. Parameter for the Density based spatial clustering of applications with noise DBSCAN algorithm: \(Eps\): cutoff distance; \(MP\): minimum number of neighbors; \(M\): minimal cluster size. \({}^{A}\) Hierarchical clustering was necessary. \({}^{B}\) The size was reduced from 100,000 extracting every 10 th data point. Figure 2: Performance of the common nearest neighbor (CNN) algorithm on a variety of different two-dimensional (2D) datasets; the parameter sets are presented in Table 1; non-assigned data points (noise) are highlighted in light gray; if accessible, the true centroids are highlighted blue. \({}^{A}\) For the _Birch_3 dataset, a three-step hierarchical clustering approach was applied. The original clusters after the first step are highlighted in light red and light blue. When the goal of the cluster analysis is to characterize an underlying probability density, one would ideally like to partition the state space along iso-density lines. We have developed the common nearest neighbor (CNN) clustering for this purpose [4; 23]. The algorithm defines a small spherical neighborhood around each data point and approximates the data-point density between two data points \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) as the number of data points within the overlapping region of the two neighborhoods. If the data-point density in the overlap region exceeds a threshold value, the two data points are assigned to the same cluster. Thus, CNN clustering is a density-based clustering that yields a strict partitioning with outliers. We refer to the clusters from such a strict partitioning with outliers, which are interpreted as designating peaks in the underlying probability density, as _core sets_. In [24], the algorithm has been extended to a hierarchical cluster algorithm. The initial purpose of the CNN algorithms was to analyze molecular dynamics (MD) simulations, which yield a sample of a particularly high-dimensional and complicated probability distribution, the Boltzmann distribution. The CNN algorithm successfully processes MD data without prior dimensionality reduction of the dataset [4; 24]. It also compares favorably to other density-based cluster algorithms for the analysis of MD data [24]. The CNN algorithm has been used to characterize the molecular ensemble as well as to discretize the molecular state space for the construction of a core-set model of MD [24; 25; 26; 27; 28; 29].