# Common Nearest Neighbor Clustering--A Benchmark
## 1 Introduction
\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline  & **Dataset** & & & \multicolumn{3}{c}{**CNN Parameter**} & \multicolumn{3}{c}{**DBSCAN Parameter**} \\ \hline
**Name** & \(n\) & \(d\) & \(k_{R}\) & \(R\) & \(N\) & \(M\) & \(Eps\) & \(MP\) & \(M\) \\ \hline \multicolumn{10}{c}{S sets [13]} \\ \hline S1 & 5000 & 2 & 15 & \(2.5\times 10^{4}\) & 5 & 10 & \(2.0\times 10^{4}\) & 9 & 10 \\ S2 & 5000 & 2 & 15 & \(2.5\times 10^{4}\) & 17 & 10 & \(2.0\times 10^{4}\) & 9 & 10 \\ S3 & 5000 & 2 & 15 & \(2.5\times 10^{4}\) & 25 & 10 & \(1.7\times 10^{4}\) & 9 & 10 \\ S4 & 5000 & 2 & 15 & \(2.5\times 10^{4}\) & 30 & 10 & \(1.7\times 10^{4}\) & 9 & 10 \\ \hline \multicolumn{10}{c}{Birch sets [14]} \\ \hline Birch1 & 10,000 \({}^{B}\) & 2 & 100 & \(2.5\times 10^{4}\) & 23 & 10 & \(1.5\times 10^{4}\) & 9 & 10 \\ Birch2 & 10,000 \({}^{B}\) & 2 & 100 & \(2.5\times 10^{3}\) & 20 & 10 & \(1.5\times 10^{3}\) & 9 & 10 \\ Birch3 \({}^{A}\) & 10,000 \({}^{B}\) & 2 & 100 & \(3\times 10^{4}\) & 10 & 10 & — & — & — \\ — & — & — & — & \(2\times 10^{4}\) & 10 & 10 & — & — & — \\ — & — & — & — & \(1.5\times 10^{4}\) & 10 & 10 & \(1.5\times 10^{4}\) & 9 & 10 \\ \hline \multicolumn{10}{c}{Dim sets [15; 16]} \\ \hline Dim-32 & 1024 & 32 & 16 & 10 & 5 & 10 & 15 & 9 & 10 \\ Dim-64 & 1024 & 64 & 16 & 10 & 5 & 10 & 15 & 9 & 10 \\ Dim-128 & 1024 & 128 & 16 & 10 & 5 & 10 & 15 & 9 & 10 \\ Dim-256 & 1024 & 256 & 16 & 10 & 5 & 10 & 15 & 9 & 10 \\ Dim-512 & 1024 & 512 & 16 & 10 & 5 & 10 & 20 & 9 & 10 \\ Dim-1024 & 1024 & 1024 & 16 & 10 & 5 & 10 & 20 & 9 & 10 \\ \hline \multicolumn{10}{c}{Unbalance [17]} \\ \hline Unbalance & 6500 & 2 & 8 & \(1\times 10^{4}\) & 5 & 10 & \(6\times 10^{3}\) & 9 & 10 \\ \hline \multicolumn{10}{c}{Shape sets} \\ \hline Aggregation [18] & 788 & 2 & 7 & 2.50 & 17 & 10 & — & — & — \\ Compound [19] & 399 & 2 & 6 & 2.00 & 15 & 10 & — & — & — \\ D31 [20] & 3100 & 2 & 31 & 0.45 & 4 & 10 & — & — & — \\ Flame [3] & 240 & 2 & 2 & 2.00 & 15 & 10 & — & — & — \\ Jain [21] & 373 & 2 & 2 & 2.50 & 3 & 10 & — & — & — \\ Path-based [22] & 300 & 2 & 3 & 1.40 & 2 & 5 & 1.4 & 2 & 5 \\ R15 [20] & 600 & 2 & 15 & 0.60 & 9 & 10 & — & — & — \\ Spiral [22] & 312 & 2 & 3 & 3.00 & 3 & 10 & — & — & — \\
4.8k [2] & 8000 & 2 & 6 & 10.00 & 15 & 10 & — & — & — \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._In this contribution, we ask whether the CNN algorithm is limited to MD datasets, or whether it can successfully cluster a diverse benchmark dataset with challenges that are unlikely to occur in the context of MD simulations. We analyze the performance of the CNN algorithm with respect to general properties of datasets, such as the cluster size, cluster shape or cluster overlap, in Section 4.1. A characterization of a probability density by a partitioning into core sets \(\{\mathrm{C}_{1},\mathrm{C}_{2},...\}\) and an intermediate region \(I=\Omega\setminus\bigcup_{i=1}^{n}\tilde{\mathrm{C}}_{i}\) seems insufficient at first glance, because, particularly for high-dimensional probability densities, the vast majority of the state space tends to be assigned to the intermediate region. We demonstrate why such a partitioning is in fact often preferable to a strict partitioning when it comes to characterizing high-dimensional probability densities in Section 4.2. Section 2 contains a brief review of MD simulations. The CNN algorithm is explained in Section 3.1.