{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T10:16:01Z","timestamp":1777371361455,"version":"3.51.4"},"reference-count":11,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,4,21]],"date-time":"2017-04-21T00:00:00Z","timestamp":1492732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The k-means is one of the most popular and widely used clustering algorithm; however, it is limited to numerical data only. The k-prototypes algorithm is an algorithm famous for dealing with both numerical and categorical data. However, there have been no studies to accelerate it. In this paper, we propose a new, fast k-prototypes algorithm that provides the same answers as those of the original k-prototypes algorithm. The proposed algorithm avoids distance computations using partial distance computation. Our k-prototypes algorithm finds minimum distance without distance computations of all attributes between an object and a cluster center, which allows it to reduce time complexity. A partial distance computation uses a fact that a value of the maximum difference between two categorical attributes is 1 during distance computations. If data objects have m categorical attributes, the maximum difference of categorical attributes between an object and a cluster center is m. Our algorithm first computes distance with numerical attributes only. If a difference of the minimum distance and the second smallest with numerical attributes is higher than m, we can find the minimum distance between an object and a cluster center without distance computations of categorical attributes. The experimental results show that the computational performance of the proposed k-prototypes algorithm is superior to the original k-prototypes algorithm in our dataset.<\/jats:p>","DOI":"10.3390\/sym9040058","type":"journal-article","created":{"date-parts":[[2017,4,21]],"date-time":"2017-04-21T10:59:30Z","timestamp":1492772370000},"page":"58","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Fast K-prototypes Algorithm Using Partial Distance Computation"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5755-7510","authenticated-orcid":false,"given":"Byoungwook","family":"Kim","sequence":"first","affiliation":[{"name":"Creative Informatics &amp; Computing Institute, Korea University, Seoul 02841, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,4,21]]},"reference":[{"key":"ref_1","unstructured":"MacQueen, J.B. (July, January 21). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability: Statistics, Oakland, CA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","article-title":"NP-hardness of euclidean sum-of-squares clustering","volume":"75","author":"Aloise","year":"2009","journal-title":"Mach. Learn."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3229","DOI":"10.1109\/TIT.2009.2021326","article-title":"Random projection trees for vector quantization","volume":"55","author":"Dasgupta","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","unstructured":"Drake, J., and Hamerly, G. (2012, January 7\u20138). Accelerated k-means with adaptive distance bounds. Proceedings of the 5th NIPS Workshop on Optimization for Machine Learning, Lake Tahoe, NV, USA."},{"key":"ref_5","unstructured":"Fawcett, T., and Mishra, N. (2003). Using the triangle inequality to accelerate k-means. Tom Fawcett and Nina Mishra, AAAI Press."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hamerly, G. (May, January 29). Making k-means even faster. Proceedings of the 2010 SIAM International Conference on Data Mining, Columbus, OH, USA.","DOI":"10.1137\/1.9781611972801.12"},{"key":"ref_7","unstructured":"Huang, Z. (1997, January 23\u201324). Clustering large data sets with mixed numeric and categorical values. Proceedings of the First Pacific Asia Knowledge Discovery and Data Mining Conference, Singapore."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Pelleg, D., and Moore, A.W. (1999, January 15\u201318). Accelerating exact k-means algorithms with geometric reasoning. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/312129.312248"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","article-title":"An efficient k-means clustering algorithm: Analysis and implementation","volume":"24","author":"Kanungo","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_10","unstructured":"Cheng, D., Gersho, A., Ramamurthi, B., and Shoham, Y. (1984, January 19\u201321). Fast search algorithms for vector quantization and pattern matching. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, San Diego, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1109\/97.863145","article-title":"Rotated partial distance search for faster vector quantization encoding","volume":"7","author":"McNames","year":"2000","journal-title":"IEEE Signal Process. Lett."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/4\/58\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:33:06Z","timestamp":1760207586000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/4\/58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,21]]},"references-count":11,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,4]]}},"alternative-id":["sym9040058"],"URL":"https:\/\/doi.org\/10.3390\/sym9040058","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201704.0099.v1","asserted-by":"object"}]},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,21]]}}}