{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T20:04:54Z","timestamp":1781294694558,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T00:00:00Z","timestamp":1548720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Youth and Sports of Czech Republic"},{"name":"Agency of the Czech Republic","award":["GA18-18080S"],"award-info":[{"award-number":["GA18-18080S"]}]},{"name":"Ministry of Education","award":["NPU I (LO1220)"],"award-info":[{"award-number":["NPU I (LO1220)"]}]},{"name":"CTU","award":["SGS17\/210\/OHK3\/3T\/18"],"award-info":[{"award-number":["SGS17\/210\/OHK3\/3T\/18"]}]},{"name":"ERDF Grant Upgrade of National Infrastructure for Chemical Biology","award":["CZ.02.1.01\/0.0\/0.0\/16_013\/0001799"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_013\/0001799"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>Traditional clustering algorithms fail to produce human-like results when confronted with data of variable density, complex distributions, or in the presence of noise. We propose an improved graph-based clustering algorithm called Chameleon 2, which overcomes several drawbacks of state-of-the-art clustering approaches. We modified the internal cluster quality measure and added an extra step to ensure algorithm robustness. Our results reveal a significant positive impact on the clustering quality measured by Normalized Mutual Information on 32 artificial datasets used in the clustering literature. This significant improvement is also confirmed on real-world datasets.<\/jats:p>\n          <jats:p>The performance of clustering algorithms such as DBSCAN is extremely parameter sensitive, and exhaustive manual parameter tuning is necessary to obtain a meaningful result. All hierarchical clustering methods are very sensitive to cutoff selection, and a human expert is often required to find the true cutoff for each clustering result. We present an automated cutoff selection method that enables the Chameleon 2 algorithm to generate high-quality clustering in autonomous mode.<\/jats:p>","DOI":"10.1145\/3299876","type":"journal-article","created":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T13:16:22Z","timestamp":1548767782000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Chameleon 2"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8163-9687","authenticated-orcid":false,"given":"Tomas","family":"Barton","sequence":"first","affiliation":[{"name":"Czech Technical University in Prague, Institute of Molecular Genetics ASCR"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomas","family":"Bruna","sequence":"additional","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Kordik","sequence":"additional","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,29]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1201\/b17320"},{"key":"e_1_2_2_2_1","volume-title":"ISODATA: A Novel Method of Data Analysis and Pattern Classification. Technical Report","author":"Ball G.","year":"1965"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW\u201916)","author":"Barton T."},{"key":"e_1_2_2_4_1","series-title":"Lecture Notes in Computer Science","volume-title":"Evaluation of relative indexes for multi-objective clustering","author":"Barto\u0148 Tom\u00e1\u0161"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1198704"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1654758.1654774"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"M. R. Brito E. L. Ch\u00e1vez A. J. Quiroz and J. E. Yukich. 1997. Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection. Statistics 8 Probability Letters 35 1 (15 Aug. 1997) 33--42.  M. R. Brito E. L. Ch\u00e1vez A. J. Quiroz and J. E. Yukich. 1997. Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection. Statistics 8 Probability Letters 35 1 (15 Aug. 1997) 33--42.","DOI":"10.1016\/S0167-7152(96)00213-1"},{"key":"e_1_2_2_8_1","unstructured":"Tomas Bruna. 2015. Implementation of the Chameleon Clustering Algorithm. Bachelor\u2019s Thesis. CTU in Prague.  Tomas Bruna. 2015. Implementation of the Chameleon Clustering Algorithm. Bachelor\u2019s Thesis. CTU in Prague."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610927408827101"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.103"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2007.04.010"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1979.4766909"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD). Evangelos Simoudis, Jiawei Han, and Usama M. Fayyad (Eds.). AAAI Press, 226--231","author":"Ester Martin","year":"1996"},{"key":"e_1_2_2_15_1","unstructured":"B. S. Everitt. 1993. Cluster Analysis. Edward Arnold.  B. S. Everitt. 1993. Cluster Analysis. Edward Arnold."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 19th Design Automation Conference (DAC\u201982)","author":"Fiduccia C. M."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.09.012"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1136800"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-8-3"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737792"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217303"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2006.877146"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"e_1_2_2_26_1","volume-title":"Dubes","author":"Jain Anil K.","year":"1988"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590316_1"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 17th International Conference on Pattern Recognition (ICPR\u201904)","author":"Jain Anil K."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1973.223640"},{"key":"e_1_2_2_31_1","unstructured":"George Karypis. 2002b. Karypis Lab - CLUTO\u2019s Datasets. Retrieved from http:\/\/glaros.dtc.umn.edu\/gkhome\/cluto\/cluto\/download.  George Karypis. 2002b. Karypis Lab - CLUTO\u2019s Datasets. Retrieved from http:\/\/glaros.dtc.umn.edu\/gkhome\/cluto\/cluto\/download."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.309954"},{"key":"e_1_2_2_35_1","volume-title":"Data: An Introduction to Cluster Analysis","author":"Kaufman L.","year":"1990"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1987.4309069"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/9.4.373"},{"key":"e_1_2_2_38_1","unstructured":"Yann Lecun and Corinna Cortes. 2013. The MNIST database of handwritten digits. Retrieved from http:\/\/yann.lecun.com\/exdb\/mnist.  Yann Lecun and Corinna Cortes. 2013. The MNIST database of handwritten digits. Retrieved from http:\/\/yann.lecun.com\/exdb\/mnist."},{"key":"e_1_2_2_39_1","unstructured":"M. Lichman. 2013. UCI Machine Learning Repository. Retrieved from http:\/\/archive.ics.uci.edu\/ml.  M. Lichman. 2013. UCI Machine Learning Repository. Retrieved from http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_41_1","volume-title":"Proceedngs of the 5th Berkeley Symposium on Mathematical Statistics and Probability, L. M. Le Cam and J. Neyman (Eds.)","volume":"1","author":"MacQueen J. B.","year":"1967"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00205"},{"key":"e_1_2_2_43_1","volume-title":"Mixture Models: Inference and Applications to Clustering","author":"McLachlan G. J.","year":"1988"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_2_2_45_1","first-page":"2837","article-title":"Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance","volume":"11","author":"Nguyen Xuan Vinh","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_46_1","volume-title":"Clustering by fast search and find of density peaks. Science 344, 6191","author":"Rodriguez Alex","year":"2014"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2004.50"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the ISTA (LNI), Heinrich C. Mayr and Dimitris Karagiannis (Eds.)","volume":"107","author":"Shatovska Tetyana","year":"2007"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244303321897735"},{"key":"e_1_2_2_50_1","first-page":"175","article-title":"Fuzzy C-means algorithm with a point symmetry distance","volume":"7","author":"Su Mu-Chun","year":"2005","journal-title":"International Journal of Fuzzy Systems"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00293"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1033218"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223083"},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of Neural Information Processing Systems (NIPS\u201904)","author":"Zelnik-Manor Lihi","year":"2004"},{"key":"e_1_2_2_56_1","unstructured":"Y. Zhao and G. Karypis. 2001. Criterion Functions for Document Clustering: Experiments and Analysis. Technical Report TR 01--40. Department of Computer Science University of Minnesota Minneapolis MN.  Y. Zhao and G. Karypis. 2001. Criterion Functions for Document Clustering: Experiments and Analysis. Technical Report TR 01--40. Department of Computer Science University of Minnesota Minneapolis MN."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299876","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3299876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:38Z","timestamp":1750204418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299876"}},"subtitle":["An Improved Graph-Based Clustering Algorithm"],"short-title":[],"issued":{"date-parts":[[2019,1,29]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3299876"],"URL":"https:\/\/doi.org\/10.1145\/3299876","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,29]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}