Next Article in Journal
Collaborative CAD Synchronization Based on a Symmetric and Consistent Modeling Procedure
Next Article in Special Issue
Analysis of Clustering Evaluation Considering Features of Item Response Data Using Data Mining Technique for Setting Cut-Off Scores
Previous Article in Journal
A Matter of Degree: Strength of Brain Asymmetry and Behaviour
Previous Article in Special Issue
3D Reconstruction Framework for Multiple Remote Robots on Cloud System
Article Menu

Export Article

Open AccessArticle
Symmetry 2017, 9(4), 58; doi:10.3390/sym9040058

A Fast K-prototypes Algorithm Using Partial Distance Computation

Creative Informatics & Computing Institute, Korea University, Seoul 02841, Korea
Academic Editor: Doo-Soon Park
Received: 6 April 2017 / Revised: 17 April 2017 / Accepted: 18 April 2017 / Published: 21 April 2017
(This article belongs to the Special Issue Scientific Programming in Practical Symmetric Big Data)
View Full-Text   |   Download PDF [712 KB, uploaded 24 April 2017]   |  

Abstract

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. View Full-Text
Keywords: clustering algorithm; k-prototypes algorithm; partial distance computation clustering algorithm; k-prototypes algorithm; partial distance computation
Figures

Figure 1

This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. (CC BY 4.0).

Scifeed alert for new publications

Never miss any articles matching your research from any publisher
  • Get alerts for new papers matching your research
  • Find out the new papers from selected authors
  • Updated daily for 49'000+ journals and 6000+ publishers
  • Define your Scifeed now

Share & Cite This Article

MDPI and ACS Style

Kim, B. A Fast K-prototypes Algorithm Using Partial Distance Computation. Symmetry 2017, 9, 58.

Show more citation formats Show less citations formats

Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Related Articles

Article Metrics

Article Access Statistics

1

Comments

[Return to top]
Symmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert
Back to Top
{"cc_re__cc_re__cc_by_3_0": ["4c\" >\n\t<meta name=\"dc.title\" content=\"A Fast K-prototypes Algorithm Using Partial Distance Computation\">\n\n            <meta name=\"dc.creator\" content=\"Byoungwook Kim\">\n    \n    <meta name=\"dc.type\" content=\"Article\">\n    <meta name=\"dc.source\" content=\"Symmetry 2017, Vol. 9, Page 58\">\n    <meta name=\"dc.date\" content=\"2017-04-21\">\n            <meta name =\"dc.identifier\" content=\"10.3390/sym9040058\">\n    \n    <meta name=\"dc.publisher\" content=\"Multidisciplinary Digital Publishing Institute\">\n    <meta name=\"dc.rights\" content=\"http://creativecommons.org/licenses/by/3.0/\">\n    <meta name=\"dc.format\" content=\"application/pdf\" >\n    <meta name=\"dc.language\" content=\"en\" >\n\t<meta name=\"dc.description\" content=\"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 s"], "cc_re__cc_re__cc_by_4_0": ["               &lt;caption&gt;\n          &lt;p&gt;Effect of cardinality. FKPT (fast k-prototypes) is the result of our propose k-prototypes algorithm and TKPT (traditional k-prototypes) is the result of original k-prototypes algorithm.&lt;/p&gt;\n        &lt;/caption&gt;\n                                                            \"></a></div>\t\t\t\n\t\t\t\n\t\t\t<div class=\"licenseText in-tab\" style=\"padding: 1em 0;\">\n                                    This is an open access article distributed under the <a href=\"https://creativecommons.org/licenses/by/4.0/\" target=\"_blank\">Creative Commons Attribution License</a> which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. (CC BY 4.0).\n                \t\t\t</div>\n\t\n\t   </div>\n\t   \n\t\t<div class=\"show-for-small\" >\n            <h1>Scifeed alert for new publications</h1> \n            <strong>Never miss any articles</strong> matching your research <strong>from any publisher</strong>\n            <ul>\n                <li>Get alerts for new papers matching your "], "copyright__copyright__copyright": ["PI and ACS Style\n\nKim, B. A Fast K-prototypes Algorithm Using Partial Distance Computation. Symmetry 2017, 9, 58.\n\nShow more citation formats Show less citations formats\n\nNote that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.\n\nRelated Articles\n\nArticle Metrics\n\nArticle Access Statistics\n\n1\n\nComments\n\n[Return to top]\nSymmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert\nBack to Top", "PI and ACS Style\n\nKim, B. A Fast K-prototypes Algorithm Using Partial Distance Computation. Symmetry 2017, 9, 58.\n\nShow more citation formats Show less citations formats\n\nNote that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.\n\nRelated Articles\n\nArticle Metrics\n\nArticle Access Statistics\n\n1\n\nComments\n\n[Return to top]\nSymmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert\nBack to Top", "PI and ACS Style\n\nKim, B. A Fast K-prototypes Algorithm Using Partial Distance Computation. Symmetry 2017, 9, 58.\n\nShow more citation formats Show less citations formats\n\nNote that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.\n\nRelated Articles\n\nArticle Metrics\n\nArticle Access Statistics\n\n1\n\nComments\n\n[Return to top]\nSymmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert\nBack to Top"]}