Abstract
K-Means is a very common method of unsupervised learning in data mining. It is introduced by Steinhaus in 1956. As time flies, many other enhanced methods of k-Means have been introduced and applied. One of the significant characteristic of k-Means is randomize. Thus, this paper proposes a balanced k-Means method, which means number of items distributed within clusters are more balanced, provide more equal-sized clusters. Cases those are suitable to apply this method are also discussed, such as Travelling Salesman Problem (TSP). In order to enhance the performance and usability, we are in the process of proposing a learning ability of this method in the future.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Travelling salesman problem, https://en.wikipedia.org/wiki/Travelling_salesman_problem.
References
Likas, A., Vlassis, N., Verbeek, J.: The global k-Means clustering algorithm. Technical report 12 (2011)
Ball, G., Hall, D.: ISODATA, a novel method of data analysis and pattern classification. Technical report NTIS AD 699616. Stanford Research Institute, Stanford, CA (1965)
Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Mach. Learn. 56(1–3), 9–33 (1999)
He, R., Xu, W., Sun, J., Zu, B.: Balanced k-Means algorithm for partitioning areas in large-scale vehicle routing problem. In: Third International Symposium on IEEE Intelligent Information Technology Application, IITA 2009, vol. 3, pp. 87–90 (2009)
Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. (CSUR) 31(3), 264–323 (1999)
Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice Hall, Upper Saddle River (1988)
Jain, A.K.: Data clustering: 50 years beyond k-Means. Pattern Recogn. Lett. 31(8), 651–666 (2010)
Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inform. Theory 28, 129–137 (1982)
MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Fifth Berkeley Symposium on Mathematics, Statistics and Probability, pp. 281–297. University of California Press (1967)
Meila, M.: The uniqueness of a good optimum for k-Means. In: Proceedings of 23rd International Conference Machine Learning, pp. 625–632 (2006)
Steinhaus, H.: Sur La Division des Corp Materiels En Parties. Bull. Acad. Polon. Sci. IV(C1.III), 801–804 (1956)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Tai, CL., Wang, CS. (2017). Balanced k-Means. In: Nguyen, N., Tojo, S., Nguyen, L., Trawiński, B. (eds) Intelligent Information and Database Systems. ACIIDS 2017. Lecture Notes in Computer Science(), vol 10192. Springer, Cham. https://doi.org/10.1007/978-3-319-54430-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-54430-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-54429-8
Online ISBN: 978-3-319-54430-4
eBook Packages: Computer ScienceComputer Science (R0)