# Common Nearest Neighbor Clustering--A Benchmark
## 3 Materials and Methods
### Common Nearest Neighbor Algorithm
Thus, the number of clusters is also defined by these parameters. Additionally, the cluster result is completely independent of the choice for the initial cluster member. The CNN algorithm merely extracts the cluster memberships from the datasets by checking the density criterion. Starting from an initial cluster member, it grows a specific cluster by adding members one-by-one (single-link). A data point becomes a cluster member if it is density-connected to any of the current cluster members. Unclustered points are checked several times until the cluster cannot be extended any further. The remaining unclustered data points belong to either another cluster or are outliers. The cluster is thus removed from the dataset and a new cluster is initialized. That is, the clusters are sequentially \"cut out\" from the dataset. The algorithm can yield clusters with only a single member. These clusters are labeled as noise points and are combined into a single set. Alternatively, one can assign all clusters with less than \(M\) members to the set of noise points. The parameter \(M\) then represents the minimal cluster size, for which the default value is \(M=2\). Figure 4: Clustering process using the common nearest neighbor (CNN) algorithm: (**a**) A dataset that consists of two clusters and several noise points. (**b**–**e**) Depiction of the density criteria that determine whether two data points \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) belong to the same cluster: (**b**) The first density criterion, \(N\) shared nearest neighbors, is fulfilled. (**c**) The second density criterion, \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) are nearest neighbors with respect to the other data point, is fulfilled. (**d**) Both criteria (**b**,**c**) are fulfilled at the same time. Hence, \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) belong to the same cluster. (**e**) One criterion is fulfilled, the other is not. Hence, \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) do not belong to the same cluster. (**f**) \(\mathbf{x}_{a}\) and \(\mathbf{x}_{b}\) fulfil no density criteria but belong to the same cluster as they are density-connected (reproduced from [PERSON]; [PERSON] “Density-based cluster algorithms for the identification of core sets”, J. Chem. Phys. **2016**, _145_, 164104, with the permission of AIP Publishing). (**g**) Depiction of a clustering process over several cluster expansion steps (iterations). We note that the cluster is expanded by adding single data points to the current cluster that fulfil the density criterion with respect to a data point within the cluster. The parameters \(R\) and \(N\) together represent a data-point density threshold. They thus have to be adapted to the data-point density of the dataset at hand. The neighborhood radius \(R\) is chosen to be smaller than the position of the first peak \(d_{0}\) in the histogram of pairwise distances. For the benchmark datasets, we chose \(R=0.9\cdot d_{0}\) (see Section 4.1 and Figure 5 for more details and an illustration). \(N\) is chosen by reclustering the dataset with different values of \(N\) and plotting the number of clusters as a function of \(N\). Usually one finds a plateau region in this plot, which then determines the value for \(N\) (see [4]). Alternatively, one can analyze the distance distribution within the clusters to decide on the value of \(N\) (see Section 4.1 and Figure 5 for more details and an illustration). At the moment, there is no scheme to choose the parameters \(R\) and \(N\) automatically. However, following the schemes described above, it is very easy to find a good parameter set manually. For the benchmark datasets, the parameter \(M\) has been set to 10. For MD datasets, we find that \(M=0.001\cdot n\), where \(n\) is the size of the dataset, is a useful heuristic. We note that in each cluster extraction step (steps 1 and 2), the algorithm identifies a single cluster, which is then removed from the set of unclustered data points. There are two modifications that decrease the run-time of the algorithm.