American Institute of Mathematical Sciences

Advanced
July  2012, 8(3): 565-575. doi: 10.3934/jimo.2012.8.565

A Max-Min clustering method for $k$-means algorithm of data clustering

Baolan Yuan 1, , Wanjun Zhang 2, and  Yubo Yuan 3,

1. 

School of Information Engineering, Hangzhou Dianzi University, Hangzhou 310012, China
2. 

School of Software Engineering, Hangzhou Dianzi University, Hangzhou 310012, China
3. 

School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China

Received  March 2011 Revised  November 2011 Published  June 2012

As it is known that the performance of the $k$-means algorithm for data clustering largely depends on the choice of the Max-Min centers, and the algorithm generally uses random procedures to get them. In order to improve the efficiency of the $k$-means algorithm, a good selection method of clustering starting centers is proposed in this paper. The proposed algorithm determines a Max-Min scale for each cluster of patterns, and calculate Max-Min clustering centers according to the norm of the points. Experiments results show that the proposed algorithm provides good performance of clustering.
Keywords: $k$-means algorithm, combinatorial optimization, Clustering, data mining..
Mathematics Subject Classification: Primary: 68T10; Secondary: 90C2.
Citation: Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565
References:
[1]

V. S. Ananthanarayana, M. Narasimha Murty and D. K. Subramanian, Rapid and brief communication efficient clustering of large data sets, Pattern Recognition, 34 (2001), 2561-2563. Google Scholar

[2]

Sanghamitra Bandyopadhyay and Ujjwal Maulik, An evolutionary technique based on K-means algorithm for optimal clustering in $R^N$, Information Sciences, 146 (2002), 221-237.  Google Scholar

[3]

Bjarni Bodvarsson, M. Morkebjerg, L. K. Hansen, G. M. Knudsen and C. Svarer, Extraction of time activity curves from positron emission tomography: K-means clustering or non-negative matrix factorization, NeuroImage, 31 (2006), 185-186. Google Scholar

[4]

Paul S. Bradley and Usama M. Fayyad, Refining max-min points for K-means clustering, in "Proc. 15th International Conf. on Machine Learning," Morgan Kaufmann, San Francisco, CA, (1998), 91-99. Google Scholar

[5]

P. S. Bradley, O. L. Mangasarian and W. N. Street, Clustering via concave minimization, in "Advances in Neural Information Systems," (eds. M. C. Mozer, M. I. Jordan and T. Petsche), MIT Press, Cambridge, MA, (1996), 368-374. Google Scholar

[6]

R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification," second edition, Wiley-Interscience, New York, 2001.  Google Scholar

[7]

David J. Hand and Wojtek J. Krzanowski, Optimising k-means clustering results with standard software packages, Computational Statistics & Data Analysis, 49 (2005), 969-973.  Google Scholar

[8]

A. K. Jain and R. C. Dubes, "Algorithms for Clustering Data," Prentice Hall Advanced Reference Series, Prentice-Hall, Englewood Cliffs, NJ, 1988.  Google Scholar

[9]

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman and Angela Y. Wu, A local search approximation algorithm for k-means clustering, Computational Geometry, 28 (2004), 89-112.  Google Scholar

[10]

Shehroz S. Khan and Amir Ahmad, Cluster center max-minization algorithm for K-means clustering, Pattern Recognition Letters, 25 (2004), 1293-1302. doi: 10.1016/j.patrec.2004.04.007.  Google Scholar

[11]

R. J. Kuo, H. S. Wang, Tung-Lai Hu and S. H. Chou, Application of ant K-means on clustering analysis, Computers & Mathematics with Applications, 50 (2005), 1709-1724.  Google Scholar

[12]

Youssef M. Marzouk and Ahmed F. Ghoniem, K-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical N-body simulations, Journal of Computational Physics, 207 (2005), 493-528.  Google Scholar

[13]

Boris Mirkin, Clustering algorithms: A review, in "Mathematical Classification and Clustering," Chapter 3, Kluwer Academic Publishers, (1996), 109-169. Google Scholar

[14]

Boris Mirkin, K-means clustering, in "Clustering for Data Mining," Chapter 3, Taylor & Francis Group, (2005), 75-110. Google Scholar

[15]

Boris Mirkin, Concept learning and feature selection based on square-error clustering, Machine Learning, 35 (1999), 25-39. Google Scholar

[16]

D. J. Newman, S. Hettich, C. L. Blake and C. J. Merz, "UCI Repository of Machine Learning Databases," University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available from: http://www.ics.uci.edu/~mlearn/MLRepository.html. Google Scholar

[17]

Makoto Otsubo, Katsushi Sato and Atsushi Yamaji, Computerized identification of stress tensors determined from heterogeneous fault-slip data by combining the multiple inverse method and k-means clustering, Journal of Structural Geology, 28 (2006), 991-997. Google Scholar

[18]

Georg Peters, Some refinements of rough k-means clustering, Pattern Recognition, 39 (2006), 1481-1491. Google Scholar

[19]

S. Z. Selim and M. A. Ismail, K-means type algorithms: A generalized convergence theorem and characterization of local optimality, IEEE Trans. Pattern Anal. Mach. Inteli, 6 (1984), 81-87. Google Scholar

[20]

Y. Yuan, J. Yan and C. Xu, Polynomial Smooth Support Vector Machine(PSSVM), Chinese Journal Of Computers, 28 (2005), 9-17. Google Scholar

[21]

Y. Yuan and T. Huang, A Polynomial Smooth Support Vector Machine for Classification, Lecture Note in Artificial Intelligence, 3584 (2005), 157-164. Google Scholar

[22]

Y. Yuan, W. G. Fan and D. M. Pu, Spline function smooth support vector machine for classification, Journal of Industrial Management and Optimization, 3 (2007), 529-542.  Google Scholar

show all references

References:
[1]

V. S. Ananthanarayana, M. Narasimha Murty and D. K. Subramanian, Rapid and brief communication efficient clustering of large data sets, Pattern Recognition, 34 (2001), 2561-2563. Google Scholar

[2]

Sanghamitra Bandyopadhyay and Ujjwal Maulik, An evolutionary technique based on K-means algorithm for optimal clustering in $R^N$, Information Sciences, 146 (2002), 221-237.  Google Scholar

[3]

Bjarni Bodvarsson, M. Morkebjerg, L. K. Hansen, G. M. Knudsen and C. Svarer, Extraction of time activity curves from positron emission tomography: K-means clustering or non-negative matrix factorization, NeuroImage, 31 (2006), 185-186. Google Scholar

[4]

Paul S. Bradley and Usama M. Fayyad, Refining max-min points for K-means clustering, in "Proc. 15th International Conf. on Machine Learning," Morgan Kaufmann, San Francisco, CA, (1998), 91-99. Google Scholar

[5]

P. S. Bradley, O. L. Mangasarian and W. N. Street, Clustering via concave minimization, in "Advances in Neural Information Systems," (eds. M. C. Mozer, M. I. Jordan and T. Petsche), MIT Press, Cambridge, MA, (1996), 368-374. Google Scholar

[6]

R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification," second edition, Wiley-Interscience, New York, 2001.  Google Scholar

[7]

David J. Hand and Wojtek J. Krzanowski, Optimising k-means clustering results with standard software packages, Computational Statistics & Data Analysis, 49 (2005), 969-973.  Google Scholar

[8]

A. K. Jain and R. C. Dubes, "Algorithms for Clustering Data," Prentice Hall Advanced Reference Series, Prentice-Hall, Englewood Cliffs, NJ, 1988.  Google Scholar

[9]

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman and Angela Y. Wu, A local search approximation algorithm for k-means clustering, Computational Geometry, 28 (2004), 89-112.  Google Scholar

[10]

Shehroz S. Khan and Amir Ahmad, Cluster center max-minization algorithm for K-means clustering, Pattern Recognition Letters, 25 (2004), 1293-1302. doi: 10.1016/j.patrec.2004.04.007.  Google Scholar

[11]

R. J. Kuo, H. S. Wang, Tung-Lai Hu and S. H. Chou, Application of ant K-means on clustering analysis, Computers & Mathematics with Applications, 50 (2005), 1709-1724.  Google Scholar

[12]

Youssef M. Marzouk and Ahmed F. Ghoniem, K-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical N-body simulations, Journal of Computational Physics, 207 (2005), 493-528.  Google Scholar

[13]

Boris Mirkin, Clustering algorithms: A review, in "Mathematical Classification and Clustering," Chapter 3, Kluwer Academic Publishers, (1996), 109-169. Google Scholar

[14]

Boris Mirkin, K-means clustering, in "Clustering for Data Mining," Chapter 3, Taylor & Francis Group, (2005), 75-110. Google Scholar

[15]

Boris Mirkin, Concept learning and feature selection based on square-error clustering, Machine Learning, 35 (1999), 25-39. Google Scholar

[16]

D. J. Newman, S. Hettich, C. L. Blake and C. J. Merz, "UCI Repository of Machine Learning Databases," University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available from: http://www.ics.uci.edu/~mlearn/MLRepository.html. Google Scholar

[17]

Makoto Otsubo, Katsushi Sato and Atsushi Yamaji, Computerized identification of stress tensors determined from heterogeneous fault-slip data by combining the multiple inverse method and k-means clustering, Journal of Structural Geology, 28 (2006), 991-997. Google Scholar

[18]

Georg Peters, Some refinements of rough k-means clustering, Pattern Recognition, 39 (2006), 1481-1491. Google Scholar

[19]

S. Z. Selim and M. A. Ismail, K-means type algorithms: A generalized convergence theorem and characterization of local optimality, IEEE Trans. Pattern Anal. Mach. Inteli, 6 (1984), 81-87. Google Scholar

[20]

Y. Yuan, J. Yan and C. Xu, Polynomial Smooth Support Vector Machine(PSSVM), Chinese Journal Of Computers, 28 (2005), 9-17. Google Scholar

[21]

Y. Yuan and T. Huang, A Polynomial Smooth Support Vector Machine for Classification, Lecture Note in Artificial Intelligence, 3584 (2005), 157-164. Google Scholar

[22]

Y. Yuan, W. G. Fan and D. M. Pu, Spline function smooth support vector machine for classification, Journal of Industrial Management and Optimization, 3 (2007), 529-542.  Google Scholar

[1]

Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial & Management Optimization, 2019, 15 (2) : 565-576. doi: 10.3934/jimo.2018057
[2]

Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022
[3]

Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020160
[4]

Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021067
[5]

Guojun Gan, Qiujun Lan, Shiyang Sima. Scalable clustering by truncated fuzzy $c$-means. Big Data & Information Analytics, 2016, 1 (2&3) : 247-259. doi: 10.3934/bdia.2016007
[6]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
[7]

Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021122
[8]

Sung Ha Kang, Berta Sandberg, Andy M. Yip. A regularized k-means and multiphase scale segmentation. Inverse Problems & Imaging, 2011, 5 (2) : 407-429. doi: 10.3934/ipi.2011.5.407
[9]

Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921
[10]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515
[11]

Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014
[12]

Michael Herty, Lorenzo Pareschi, Giuseppe Visconti. Mean field models for large data–clustering problems. Networks & Heterogeneous Media, 2020, 15 (3) : 463-487. doi: 10.3934/nhm.2020027
[13]

Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079
[14]

Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang. A clustering based mate selection for evolutionary optimization. Big Data & Information Analytics, 2017, 2 (1) : 77-85. doi: 10.3934/bdia.2017010
[15]

Qinglei Zhang, Wenying Feng. Detecting coalition attacks in online advertising: A hybrid data mining approach. Big Data & Information Analytics, 2016, 1 (2&3) : 227-245. doi: 10.3934/bdia.2016006
[16]

Zhen Mei. Manifold data mining helps businesses grow more effectively. Big Data & Information Analytics, 2016, 1 (2&3) : 275-276. doi: 10.3934/bdia.2016009
[17]

Sunmoo Yoon, Maria Patrao, Debbie Schauer, Jose Gutierrez. Prediction models for burden of caregivers applying data mining techniques. Big Data & Information Analytics, 2017  doi: 10.3934/bdia.2017014
[18]

Anupama N, Sudarson Jena. A novel approach using incremental under sampling for data stream mining. Big Data & Information Analytics, 2018  doi: 10.3934/bdia.2017017
[19]

Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401
[20]

Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (82)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences