{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T22:50:16Z","timestamp":1794091816220,"version":"4.8.0"},"reference-count":53,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2018,11,4]],"date-time":"2018-11-04T00:00:00Z","timestamp":1541289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71272161"],"award-info":[{"award-number":["71272161"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Clustering is one of the main tasks of machine learning. Internal clustering validation indexes (CVIs) are used to measure the quality of several clustered partitions to determine the local optimal clustering results in an unsupervised manner, and can act as the objective function of clustering algorithms. In this paper, we first studied several well-known internal CVIs for categorical data clustering, and proved the ineffectiveness of evaluating the partitions of different numbers of clusters without any inter-cluster separation measures or assumptions; the accurateness of separation, along with its coordination with the intra-cluster compactness measures, can notably affect performance. Then, aiming to enhance the internal clustering validation measurement, we proposed a new internal CVI\u2014clustering utility based on the averaged information gain of isolating each cluster (CUBAGE)\u2014which measures both the compactness and the separation of the partition. The experimental results supported our findings with regard to the existing internal CVIs, and showed that the proposed CUBAGE outperforms other internal CVIs with or without a pre-known number of clusters.<\/jats:p>","DOI":"10.3390\/a11110177","type":"journal-article","created":{"date-parts":[[2018,11,5]],"date-time":"2018-11-05T10:43:45Z","timestamp":1541414625000},"page":"177","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Understanding and Enhancement of Internal Clustering Validation Indexes for Categorical Data"],"prefix":"10.3390","volume":"11","author":[{"given":"Xuedong","family":"Gao","sequence":"first","affiliation":[{"name":"Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minghan","family":"Yang","sequence":"additional","affiliation":[{"name":"Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TNN.2005.845141","article-title":"Survey of clustering algorithms","volume":"16","author":"Xu","year":"2005","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_2","first-page":"227","article-title":"Algorithms for clustering data","volume":"32","author":"Jain","year":"1988","journal-title":"Technometrics"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, A., Wemmert, C., Gan\u00e7arski, P., and Bennani, Y. (2017). Collaborative Clustering: Why, When, What and How. Inf. Fusion, 39.","DOI":"10.1016\/j.inffus.2017.04.008"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3201","DOI":"10.1093\/bioinformatics\/bti517","article-title":"Computational cluster validation in post-genomic data analysis","volume":"21","author":"Handl","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1012801612483","article-title":"On Clustering Validation Techniques","volume":"17","author":"Halkidi","year":"2001","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1080\/01621459.1971.10482356","article-title":"Objective Criteria for the Evaluation of Clustering Methods","volume":"66","author":"Rand","year":"1971","journal-title":"Publ. Am. Stat. Assoc."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Vinh, N.X., Epps, J., and Bailey, J. (2009, January 14\u201318). Information theoretic measures for clusterings comparison: Is a correction for chance necessary?. Proceedings of the International Conference on Machine Learning, Montreal, QC, Canada.","DOI":"10.1145\/1553374.1553511"},{"key":"ref_8","unstructured":"Rijsbergen, C.J.V. (1979). Information Retrieval, Butterworth-Heinemann."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1560","DOI":"10.1007\/s10618-014-0387-5","article-title":"Cluster validity functions for categorical data: A solution-space perspective","volume":"29","author":"Bai","year":"2015","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Li, H., Zhang, S., Ding, X., Zhang, C., and Dale, P. (2016). Performance evaluation of cluster validity indices (CVIs) on Multi\/Hyperspectral remote sensing datasets. Remote Sens., 8.","DOI":"10.3390\/rs8040295"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Harimurti, R., Yamasari, Y., and Asto, B.I.G.P. (2018, January 6\u20138). Predicting student\u2019s psychomotor domain on the vocational senior high school using linear regression. Proceedings of the 2018 International Conference on Information and Communications Technology (ICOIACT), Yogyakarta, Indonesia.","DOI":"10.1109\/ICOIACT.2018.8350768"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s13748-017-0135-3","article-title":"An approach to validity indices for clustering techniques in Big Data","volume":"7","author":"Santos","year":"2018","journal-title":"Prog. Artific. Intell."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.1111\/head.12850","article-title":"Validity of Cluster Diagnosis in an Electronic Health Record","volume":"56","author":"Rizzoli","year":"2016","journal-title":"Headache"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1109\/69.979972","article-title":"Finding localized associations in market basket data","volume":"14","author":"Aggarwal","year":"2002","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Barbar\u00e1, D., and Jajodia, S. (2002). Applications of Data Mining in Computer Security, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-0953-0"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1023\/A:1009982220290","article-title":"An Evaluation of Statistical Approaches to Text Categorization","volume":"1","author":"Yang","year":"1999","journal-title":"Inf. Retr."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1109\/TSMCB.2012.2220543","article-title":"Understanding and enhancement of internal clustering validation measures","volume":"43","author":"Liu","year":"2013","journal-title":"IEEE Trans. Cybern."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kremer, H., Kranen, P., Jansen, T., Seidl, T., Bifet, A., Holmes, G., and Pfahringer, B. (2011, January 21\u201324). An effective evaluation measure for clustering on evolving data streams. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/2020408.2020555"},{"key":"ref_19","unstructured":"Song, M., and Zhang, L. (2009, January 15\u201319). Comparison of Cluster Representations from Partial Second- to Full Fourth-Order Cross Moments for Data Stream Clustering. Proceedings of the Eighth IEEE International Conference on Data Mining, Pisa, Italy."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TSMCB.2008.2004559","article-title":"K-means clustering versus validation measures: A data distribution perspective","volume":"39","author":"Xiong","year":"2009","journal-title":"IEEE Trans. Syst. Man Cybern. Part B Cybern."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1016\/j.patcog.2006.06.026","article-title":"Model-based evaluation of clustering validation measures","volume":"40","author":"Brun","year":"2007","journal-title":"Pattern Recognit."},{"key":"ref_22","unstructured":"Tan, P.N., Steinbach, M., and Kumar, V. (2005). Introduction to Data Mining, Addison-Wesley Longman Publishing Co., Inc.. [1st ed.]."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/565117.565124","article-title":"Cluster validity methods: Part I","volume":"31","author":"Halkidi","year":"2002","journal-title":"ACM SIGMOD Rec."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"208","DOI":"10.3724\/SP.J.1016.2010.00208","article-title":"A Survey of Membrane Computing as a New Branch of Natural Computing","volume":"33","author":"Zhang","year":"2010","journal-title":"Chin. J. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.tcs.2006.11.021","article-title":"Using well-structured transition systems to decide divergence for catalytic P systems","volume":"372","author":"Busi","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","unstructured":"(2004, November 10). An Approximate Algorithm for NP-Complete Optimization Problems Exploiting P-systems. Available online: http:\/\/bioinfo.uib.es\/~recerca\/BUM\/nishida.pdf."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Maulik, U., and Bandyopadhyay, S. (2002). Performance Evaluation of Some Clustering Algorithms and Validity Indices, IEEE Computer Society.","DOI":"10.1109\/TPAMI.2002.1114856"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1109\/91.413225","article-title":"On cluster validity for the fuzzy c-means model","volume":"3","author":"Pal","year":"2002","journal-title":"IEEE Trans. Fuzzy Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.patcog.2016.12.003","article-title":"Ground truth bias in external cluster validity indices","volume":"65","author":"Lei","year":"2017","journal-title":"Pattern Recognit."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Barbar\u00e1, D., Li, Y., and Couto, J. (2002, January 4\u20139). COOLCAT: An entropy-based algorithm for categorical clustering. Proceedings of the Eleventh International Conference on Information and Knowledge Management, McLean, VA, USA.","DOI":"10.1145\/584792.584888"},{"key":"ref_31","unstructured":"Huang, Z. (1997). A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining. Res. Issues Data Min. Knowl. Discov., 1\u20138."},{"key":"ref_32","unstructured":"Gluck, M. (1985, January 15\u201317). Information, Uncertainty and the Utility of Categories. Proceedings of the Seventh Annual Conference on Cognitive Science Society, Irvine, CA, USA."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Yang, Y., Guan, X., and You, J. (2002, January 23\u201325). CLOPE:a fast and effective clustering algorithm for transactional data. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada.","DOI":"10.1145\/775047.775149"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.datak.2004.09.001","article-title":"Categorical Data Visualization and Clustering Using Subjective Factors","volume":"53","author":"Chang","year":"2005","journal-title":"Data Knowl. Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Labs Tech. J."},{"key":"ref_36","unstructured":"Macqueen, J. (July, January 21). Some Methods for Classification and Analysis of MultiVariate Observations. Proceedings of the Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, CA, USA."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00114265","article-title":"Knowledge acquisition via incremental conceptual clustering","volume":"2","author":"Fisher","year":"1987","journal-title":"Mach. Learn."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1145\/507338.507355","article-title":"Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems)","volume":"31","author":"Witten","year":"2011","journal-title":"ACM SIGMOD Rec."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"380","DOI":"10.3390\/a8030380","article-title":"Improving CLOPE\u2019s profit value and stability with an optimized agglomerative approach","volume":"8","author":"Li","year":"2015","journal-title":"Algorithms"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/j.eswa.2016.08.021","article-title":"A new index for clustering validation with overlapped clusters","volume":"64","author":"Campo","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Dziopa, T. (2016, January 11\u201314). Clustering Validity Indices Evaluation with Regard to Semantic Homogeneity. Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, Gdansk, Poland.","DOI":"10.15439\/2016F371"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"141","DOI":"10.4316\/AECE.2015.03020","article-title":"Evaluation of Subspace Clustering Using Internal Validity Measures","volume":"15","author":"Oszust","year":"2015","journal-title":"Adv. Electr. Comput. Eng."},{"key":"ref_43","unstructured":"Desgraupes, B. (2013). Clustering Indices, University of Paris Ouest-Lab Modal\u2019X."},{"key":"ref_44","unstructured":"Baarsch, J., and Celebi, M.E. (2012, January 14\u201316). Investigation of internal validity measures for K-means clustering. Proceedings of the International Multiconference of Engineers and Computer Scientists, HongKong, China."},{"key":"ref_45","unstructured":"Zhao, Q. (2012). Cluster Validity in Clustering Methods, University of Eastern Finland."},{"key":"ref_46","first-page":"27","article-title":"Internal versus external cluster validation indexes","volume":"5","author":"Rendon","year":"2011","journal-title":"Int. J. Comput. Commun."},{"key":"ref_47","unstructured":"Ingaramo, D., Pinto, D., Rosso, P., and Errecalde, M. (2008, January 17\u201323). Evaluation of internal validity measures in short-text corpora. Proceedings of the International Conference on Intelligent Text Processing and Computational Linguistics, Haifa, Israel."},{"key":"ref_48","unstructured":"Halkidi, M., and Vazirgiannis, M. (December, January 29). Clustering validity assessment: Finding the optimal partitioning of a data set. Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, CA, USA."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1109\/TKDE.2004.68","article-title":"Cluster analysis for gene expression data: A survey","volume":"16","author":"Jiang","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"6050","DOI":"10.1016\/j.eswa.2008.06.093","article-title":"External validation measures for K-means clustering: A data distribution perspective","volume":"36","author":"Wu","year":"2009","journal-title":"Expert Syst. Appl."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02418571","article-title":"Sur les fonctions convexes et les in\u00e9galit\u00e9s entre les valeurs moyennes","volume":"30","author":"Jensen","year":"1906","journal-title":"Acta Math."},{"key":"ref_52","unstructured":"Cover, T.M., and Thomas, J.A. (1991). Elements of Information Theory, Wiley."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF00116251","article-title":"Induction of Decision Trees","volume":"1","author":"Quinlan","year":"1986","journal-title":"Mach. Learn."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/11\/177\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:27:54Z","timestamp":1760196474000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/11\/177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,4]]},"references-count":53,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2018,11]]}},"alternative-id":["a11110177"],"URL":"https:\/\/doi.org\/10.3390\/a11110177","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,4]]}}}