{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T08:24:17Z","timestamp":1775982257909,"version":"3.50.1"},"reference-count":60,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T00:00:00Z","timestamp":1518134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100004875","name":"DFG","doi-asserted-by":"publisher","award":["CRC 765"],"award-info":[{"award-number":["CRC 765"]}],"id":[{"id":"10.13039\/100004875","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Cluster analyses are often conducted with the goal to characterize an underlying probability density, for which the data-point density serves as an estimate for this probability density. We here test and benchmark the common nearest neighbor (CNN) cluster algorithm. This algorithm assigns a spherical neighborhood R to each data point and estimates the data-point density between two data points as the number of data points N in the overlapping region of their neighborhoods (step 1). The main principle in the CNN cluster algorithm is cluster growing. This grows the clusters by sequentially adding data points and thereby effectively positions the border of the clusters along an iso-surface of the underlying probability density. This yields a strict partitioning with outliers, for which the cluster represents peaks in the underlying probability density\u2014termed core sets (step 2). The removal of the outliers on the basis of a threshold criterion is optional (step 3). The benchmark datasets address a series of typical challenges, including datasets with a very high dimensional state space and datasets in which the cluster centroids are aligned along an underlying structure (Birch sets). The performance of the CNN algorithm is evaluated with respect to these challenges. The results indicate that the CNN cluster algorithm can be useful in a wide range of settings. Cluster algorithms are particularly important for the analysis of molecular dynamics (MD) simulations. We demonstrate how the CNN cluster results can be used as a discretization of the molecular state space for the construction of a core-set model of the MD improving the accuracy compared to conventional full-partitioning models. The software for the CNN clustering is available on GitHub.<\/jats:p>","DOI":"10.3390\/a11020019","type":"journal-article","created":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T12:46:27Z","timestamp":1518180387000},"page":"19","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Common Nearest Neighbor Clustering\u2014A Benchmark"],"prefix":"10.3390","volume":"11","author":[{"given":"Oliver","family":"Lemke","sequence":"first","affiliation":[{"name":"Department of Biology, Chemistry, Pharmacy, Freie Universit\u00e4t Berlin, Takustra\u00dfe 3, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bettina","family":"Keller","sequence":"additional","affiliation":[{"name":"Department of Biology, Chemistry, Pharmacy, Freie Universit\u00e4t Berlin, Takustra\u00dfe 3, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,9]]},"reference":[{"key":"ref_1","first-page":"1","article-title":"Dimensionality Reduction: Rough Set Based Feature Reduction","volume":"2","author":"JeraldBeno","year":"2012","journal-title":"Int. J. Sci. Res. Publ."},{"key":"ref_2","first-page":"68","article-title":"CHAMELEON: A hierarchical 765 clustering algorithm using dynamic modeling","volume":"32","author":"Karypis","year":"1999","journal-title":"IEEE Trans. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Fu, L., and Medico, E. (2007). FLAME, a novel fuzzy clustering method for the analysis of DNA microarray data. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"074110","DOI":"10.1063\/1.3301140","article-title":"Comparing geometric and kinetic cluster algorithms for molecular simulation data","volume":"132","author":"Keller","year":"2010","journal-title":"J. Chem. Phys."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1109\/T-C.1973.223640","article-title":"Clustering Using a Similarity Measure Based on Shared Near Neighbors","volume":"C-22","author":"Jarvis","year":"1973","journal-title":"IEEE Trans. Comp."},{"key":"ref_6","unstructured":"Ester, M., Kriegel, H.P., Sander, J., and Xu, X. (1996, January 2\u20134). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the KDD-96 the Second International Conference on Knowledge Discovery and Data Mining, Portland, OR, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1109\/34.1000236","article-title":"Mean shift: A robust approach toward feature space analysis","volume":"24","author":"Comaniciu","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ankerst, M., Breuning, M.M., Kriegel, H.P., and Sander, J. (1999, January 1\u20133). OPTICS: Ordering Points To Identify the Clustering Structure. Proceedings of the ACM SIGMOD International Conference on Management of Data, Philadelphia, PA, USA.","DOI":"10.1145\/304182.304187"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1492","DOI":"10.1126\/science.1242072","article-title":"Clustering by fast search and find of density peaks","volume":"344","author":"Rodriguez","year":"2014","journal-title":"Science"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1002\/jcc.24664","article-title":"Adaptive partitioning by local density-peaks: An efficient density-based clustering algorithm for analyzing molecular dynamics trajectories","volume":"38","author":"Liu","year":"2016","journal-title":"J. Comput. Chem."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Jain, A.K., Topchy, A., Law, M.H.C., and Buhmann, J.M. (2004, January 23\u201326). Landscape of Clustering Algorithms. Proceedings of the ICPR\u201904 17th International Conference on Pattern Recognition, Cambridge, UK.","DOI":"10.1109\/ICPR.2004.1334073"},{"key":"ref_12","unstructured":"K\u00e4rkk\u00e4inen, I., and Fr\u00e4nti, P. (2002). Dynamic Local Search Algorithm for the Clustering Problem, University of Joensuu. Technical Report A-2002-6."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1016\/j.patcog.2005.09.012","article-title":"Iterative shrinking method for clustering problems","volume":"39","author":"Virmajoki","year":"2006","journal-title":"Pattern Recognit."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1023\/A:1009783824328","article-title":"BIRCH: A new data clustering algorithm and its applications","volume":"1","author":"Zhang","year":"1997","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1016\/j.patcog.2006.06.023","article-title":"Gradual model generator for single-pass clustering","volume":"40","year":"2007","journal-title":"Pattern Recognit."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1109\/TPAMI.2006.227","article-title":"Fast agglomerative clustering using a k-nearest neighbor graph","volume":"28","author":"Virmajoki","year":"2006","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2173","DOI":"10.1109\/TKDE.2016.2551240","article-title":"Set-matching methods for external cluster validity","volume":"28","author":"Rezaei","year":"2016","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1217299.1217303","article-title":"Clustering aggregation","volume":"1","author":"Gionis","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/T-C.1971.223083","article-title":"Graph-theoretical methods for detecting and describing gestalt clusters","volume":"100","author":"Zahn","year":"1971","journal-title":"IEEE Trans. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1109\/TPAMI.2002.1033218","article-title":"A maximum variance cluster algorithm","volume":"24","author":"Veenman","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Jain, A.K., and Law, M.H.C. (2005). Data Clustering: A User\u2019s Dilemma. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/11590316_1"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.patcog.2007.04.010","article-title":"Robust path-based spectral clustering","volume":"41","author":"Chang","year":"2008","journal-title":"Pattern Recognit."},{"key":"ref_23","unstructured":"Lemke, O., and Keller, B.G. (2017, January 06). CNNClustering. Available online: https:\/\/github.com\/BDGSoftware\/CNNClustering."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"164104","DOI":"10.1063\/1.4965440","article-title":"Density-based cluster algorithms for the identification of core sets","volume":"145","author":"Lemke","year":"2016","journal-title":"J. Chem. Phys."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"258","DOI":"10.3390\/e16010258","article-title":"Markov State Models for Rare Events in Molecular Dynamics","volume":"16","author":"Sarich","year":"2014","journal-title":"Entropy"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"174102","DOI":"10.1063\/1.2996509","article-title":"On the assumptions underlying milestoning","volume":"129","author":"Venturoli","year":"2008","journal-title":"J. Chem. Phys."},{"key":"ref_27","unstructured":"Sch\u00fctte, C. (1999). Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules. [Habilitation Thesis, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"204105","DOI":"10.1063\/1.3590108","article-title":"Markov state models based on milestoning","volume":"134","author":"Lu","year":"2011","journal-title":"J. Chem. Phys."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2445","DOI":"10.1140\/epjst\/e2015-02421-0","article-title":"A critical appraisal of Markov state models","volume":"224","author":"Sarich","year":"2015","journal-title":"Eur. Phys. J. Spec. Top."},{"key":"ref_30","unstructured":"Frenkel, D., and Smit, B. (1996). Understanding Molecular Simulations, Academic Press."},{"key":"ref_31","unstructured":"Allen, M.P., and Tildesley, D.J. (1987). Computer Simulation of Liquids, Oxford University Press."},{"key":"ref_32","unstructured":"Leach, A.R. (1996). Molecular Modelling, Addison Wesley Longman."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"12176","DOI":"10.1021\/jacs.6b05458","article-title":"Intradomain Allosteric Network Modulates Calcium Affinity of the C-Type Lectin Receptor Langerin","volume":"138","author":"Hanske","year":"2016","journal-title":"J. Am. Chem. Soc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1021\/acs.jcim.6b00251","article-title":"Kinetic Models of Cyclosporin a in Polar and Apolar Environments Reveal Multiple Congruent Conformational States","volume":"56","author":"Witek","year":"2016","journal-title":"J. Chem. Inf. Model."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Tsai, C.J., and Nussinov, R. (2014). A Unified View of \u201cHow Allostery Works\u201d. PLoS Comput. Biol., 10.","DOI":"10.1371\/journal.pcbi.1003394"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1002\/bs.3830120210","article-title":"A clustering technique for summarizing multivariate data","volume":"12","author":"Ball","year":"1967","journal-title":"Behav. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"3034","DOI":"10.1016\/j.patcog.2014.03.017","article-title":"Centroid index: Cluster level similarity measure","volume":"47","author":"Rezaei","year":"2014","journal-title":"Pattern Recognit."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of State Calculations by Fast Computing Machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"ref_39","unstructured":"Fr\u00e4nti, P., and Sieranoja, S. (2017). Clustering datasets. Algorithms, submitted."},{"key":"ref_40","unstructured":"Arthur, D., and Vassilvitskii, S. (2007, January 7\u20139). K-means++: The advantages of careful seeding. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"5525","DOI":"10.1021\/acs.jctc.5b00743","article-title":"PyEMMA 2: A Software Package for Estimation, Validation, and Analysis of Markov Models","volume":"11","author":"Scherer","year":"2015","journal-title":"J. Chem. Theory Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in pcm","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","article-title":"Clustering to minimize the maximum intercluster distance","volume":"38","author":"Gonzalez","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"ref_44","first-page":"207","article-title":"XNN graph","volume":"LNCS 10029","author":"Zhong","year":"2016","journal-title":"Joint Int. Workshop Struct. Syntactic Stat. Pattern Recognit."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1021\/ct5007357","article-title":"Modeling Molecular Kinetics with tICA and the Kernel Trick","volume":"11","author":"Schwantes","year":"2015","journal-title":"J. Chem. Theory Comput."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.is.2015.04.007","article-title":"Time-series clustering\u2014A decade review","volume":"53","author":"Aghabozorgi","year":"2015","journal-title":"Inf. Syst."},{"key":"ref_47","first-page":"1","article-title":"Grid-Based Method for GPS Route Analysis for Retrieval","volume":"3","year":"2017","journal-title":"ACM Trans. Algorithm"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Chandrakala, S., and Sekhar, C.C. (2008, January 1\u20138). A density based method for multivariate time series clustering in kernel feature space. Proceedings of the 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), Hong Kong, China.","DOI":"10.1109\/IJCNN.2008.4634055"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1063\/1.1330216","article-title":"A strategy for analysis of (molecular) equilibrium simulations: Configuration space density estimation, clustering, and visualization","volume":"114","author":"Hamprecht","year":"2001","journal-title":"J. Chem. Phys."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jcph.1999.6231","article-title":"A Direct Approach to Conformational Dynamics Based on Hybrid Monte Carlo","volume":"151","author":"Fischer","year":"1999","journal-title":"J. Comput. Phys."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"6571","DOI":"10.1021\/jp037421y","article-title":"Describing Protein Folding Kinetics by Molecular Dynamics Simulations","volume":"108","author":"Swope","year":"2004","journal-title":"J. Phys. Chem. B"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"155101","DOI":"10.1063\/1.2714538","article-title":"Automatic discovery of metastable states for the construction of Markov models of macromolecular conformational dynamics","volume":"126","author":"Chodera","year":"2007","journal-title":"J. Chem. Phys."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"6057","DOI":"10.1021\/jp0761665","article-title":"Coarse Master Equations for Peptide Folding Dynamics","volume":"112","author":"Buchete","year":"2008","journal-title":"J. Phys. Chem. B"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1021\/ct200069c","article-title":"An Analysis of the Validity of Markov State Models for Emulating the Dynamics of Classical Molecular Systems and Ensembles","volume":"7","author":"Keller","year":"2011","journal-title":"J. Chem. Theory Comput."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"174105","DOI":"10.1063\/1.3565032","article-title":"Markov models of molecular kinetics: Generation and validation","volume":"134","author":"Prinz","year":"2011","journal-title":"J. Chem. Phys."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1137\/090764049","article-title":"On the Approximation Quality of Markov State Models","volume":"8","author":"Sarich","year":"2010","journal-title":"Multisc. Model. Simul."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"1739","DOI":"10.1021\/ct4009156","article-title":"Variational Approach to Molecular Kinetics","volume":"10","author":"Keller","year":"2014","journal-title":"J. Chem. Theory Comput."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"3992","DOI":"10.1021\/acs.jctc.5b00498","article-title":"A Basis Set for Peptides for the Variational Approach to Conformational Kinetics","volume":"11","author":"Vitalini","year":"2015","journal-title":"J. Chem. Theory Comput."},{"key":"ref_59","unstructured":"Fackeldey, K., R\u00f6blitz, S., Scharkoi, O., and Weber, M. (2011). Soft Versus Hard Metastable Conformations in Molecular Simulations, ZIB. Technical Report 11-27."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"124133","DOI":"10.1063\/1.4978501","article-title":"Set-free Markov state model building","volume":"146","author":"Weber","year":"2017","journal-title":"J. Chem. Phys."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/19\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:29Z","timestamp":1760194469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,9]]},"references-count":60,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["a11020019"],"URL":"https:\/\/doi.org\/10.3390\/a11020019","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,9]]}}}