JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (1): 34-41.doi: 10.6040/j.issn.1672-3961.0.2015.056

Previous Articles     Next Articles

K-Means clustering algorithm based on the Schrödinger equation

XU Pingan, TANG Yan*, SHI Jiaokai, ZHANG Huirong   

  1. School of Computer and Information Science, Southwest University, Chongqing 400715, China
  • Received:2015-03-12 Online:2016-02-20 Published:2015-03-12

PDF (PC)

763

Abstract: A new method based on the Schrödinger equation was proposed to find better initial centers. According to the values of potential energy function, initial centers could be selected. Potential energy function value was calculated for each data sample. The data sample with the minimum potential energy function value was placed in the initial cluster centers set. A distance threshold was set to compute distances between the samples from the data set and cluster centers. If a distance was greater than the threshold, this sample would be put into the cluster center and removed from the data set. Otherwise, it would be removed from the data set directly. Repeated this process until the number of initial cluster centers set was equal to K. The experimental results showed that the method could find better initial centers and achieve a higher clustering accuracy with fewer iterations. Compared with other methods, the number of iterations could be reduced about 3 times and the accuracy could be increased about 12% by using this method.

Key words: K-means, dinger equation, initial cluster center, Schr&#xF6, clustering, potential energy function

CLC Number: 

  • TP391
[1] 汪中,刘贵全,陈恩红.一种优化初始中心点的K-means算法[J].模式识别与人工智能,2009,22(2):299-304. WANG Zhong, LIU Guiquan, CHEN Enhong. A K-means algorithm based on optimized initial center points[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(2):299-304.
[2] TZORTZIS G, LIKAS A. The minmax k-means clustering algorithm[J]. Pattern Recognition, 2014, 47(7):2505-2516.
[3] ZHANG Y J, CHENG E. An optimized method for selection of the initial centers of k-means clustering[M]. Berlin, Germany: Springer, 2013: 149-156.
[4] MA G W, XU Z H, ZHANG W, et al. An enriched K-means clustering method for grouping fractures with meliorated initial centers[J]. Arabian Journal of Geosciences, 2014, 8(4):1881-1893.
[5] JOSHI K D, NALWADE P S. Modified K-Means for better initial cluster centres[J]. International Journal of Computer Science and Mobile Computing, 2013, 2(7):219-223.
[6] YUAN Fang, ZHOU Zhiyong, SONG Xin. K-means clustering algorithm with meliorated initial center[J]. Computer Engineering, 2007, 33(3):65-66.
[7] HAN L, WANG Q, JIANG Z F, et al. Improved k-means initial clustering center selection algorithm[J]. Jisuanji Gongcheng yu Yingyong(Computer Engineering and Applications), 2010, 46(17):150-152.
[8] HE Y X, CAI R, WU L B, et al. K-Means optimization algorithms of initial clustering center based on regional density[J]. Applied Mechanics and Materials, 2014, 513:478-482.
[9] 王玲, 薄列峰, 焦李成. 密度敏感的谱聚类[J]. 电子学报, 2007, 35(8):1577-1581. WANG L, BO L F, JIAO L C. Density-Sensitive spectral clustering[J]. Acta Electronica Sinica, 2007, 35(8):1577-1581.
[10] 钱线, 黄萱菁, 吴立德. 初始化K-means的谱方法[J]. 自动化学报, 2007, 33(4):342-346. QIAN X, HUANG X J, WU L D. A spectral method of K-means initialization[J]. Acta Automatica Sinica, 2007, 33(4):342-346.
[11] 张靖, 段富. 优化初始聚类中心的改进k-means算法[J]. 计算机工程与设计, 2013, 34(5):1691-1694. ZHANG J, DUAN F. Improved k-means algorithm with meliorated initial centers[J]. Computer Engineering and Design, 2013, 34(5):1691-1694.
[12] XU J, XU B, ZHANG W, et al. Stable initialization scheme for k-means clustering[J]. Wuhan University Journal of Natural Sciences, 2009, 14(1):24-28.
[13] 孙秀娟, 刘希玉. 基于初始中心优化的遗传K-means聚类新算法[J]. 计算机工程与应用, 2008, 44(23):166-168. SUN Xiujuan, LIU Xiyu. New genetic K-means clustering algorithm based on meliorated initial center[J]. Computer Engineering and Applications, 2008, 44(23):166-168.
[14] PELLEG D, MOORE A. Accelerating exact k-means algorithms with geometric reasoning[C] // Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. NewYork, USA: ACM, 1999: 277-281.
[15] KAREGOWDA A G, VIDYA T, JAYARAM M A, et al. Improving performance of K-Means clustering by initializing cluster centers using genetic algorithm and entropy based fuzzy clustering for categorization of diabetic patients[C] // Proceedings of International Conference on Advances in Computing. Delhi, India: Springer, 2012: 899-904.
[16] SATHIYA G, KAVITHA P. An efficient enhanced K-Means approach with improved initial cluster centers[J]. Middle-East Journal of Scientific Research, 2014, 20(1):100-107.
[17] NAZEER K A A, SEBASTIAN M P. Improving the accuracy and efficiency of the k-means clustering algorithm[C] // Proceedings of the World Congress on Engineering. London, UK: IAENG, 2009, 1:1-3.
[18] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C] // Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. California, USA: University of California Press, 1967, 1(14): 281-297.
[19] MERCER J. Functions of positive and negative type, and their connection with the theory of integral equations[J]. Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, 1909, 209:415-446.
[20] GASIOROWICZ S. Quantum physics[M]. New York, USA: John Wiley & Sons, 2007.
[21] LICHMAN M.(2013). UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science. http://archive.ics.uci.edu/ml.
[1] ZHANG Peirui, YANG Yan, XING Huanlai, YU Xiuying. Incremental multi-view clustering algorithm based on kernel K-means [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 48-53.
[2] DU Xixi, LIU Huafeng, JING Liping. An additive co-clustering for recommendation of integrating social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 96-102.
[3] YANG Tianpeng, XU Kunpeng, CHEN Lifei. Coefficient of variation clustering algorithm for non-uniform data [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 140-145.
[4] PANG Renming, WANG Bo, YE Hao, ZHANG Haifeng, LI Mingliang. Clustering of blast furnace historical data based on PCA similarity factor and spectral clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 143-149.
[5] ZHOU Wang, ZHANG Chenlin, WU Jianxin. Qualitative balanced clustering algorithm based on Hartigan-Wong and Lloyd [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 37-44.
[6] JI Xingquan, HAN Guozheng, LI Kejun, FU Rongrong, ZHU Yanghe. Application of improved K-means clustering algorithm based on density in distribution network block partitioning [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 41-46.
[7] LI Shuo, SHI Yuliang. The method of spot cluster recommendation in location-based social networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 44-50.
[8] JIANG Feng, DU Junwei, LIU Guozhu, SUI Yuefei. A weight-based initial centers selection algorithm for K-modes clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 29-34.
[9] FAN Shuyan, DING Shifei. An improved multi-scale Graph cut algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 28-33.
[10] ZHU Hong, DING Shifei. Twice clustering method based on variable granularity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 1-6.
[11] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[12] HAO Qingbo, MU Shaomin, YIN Chuanhuan, CHANG Tengteng, CUI Wenbin. An algorithm of fast local support vector machine based on clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(1): 13-18.
[13] YAO Huachuan, WANG Lizhen, WU Pingping, ZOU Muquan. AC_SAR: actionable clustering algorithm based on strong association rule [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 38-46.
[14] SI Junshu, ZHU Wenxing*, SHA Yonghe. A comprehensive method for traffic lights detection in complex background [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 64-68.
[15] CHEN Wen-qiang1, LIN Chen1,2, CHEN Ke3, CHEN Jin-xiu1, ZOU Quan1,2*. Distributed affinity propagation clustering algorithm based on GraphLab [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(5): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[2] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[3] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[4] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[5] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[6] XUE Cheng-qian,DONG Jian-wen,MENG Xian-feng,CHANG Hong,CAO Ning,CHEN Hua-ying,LI Mu-sen . The effect of C／C+HA bonerepairing material to the physiological and biochemical response of the crossed Boer Goat[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 73 -76 .
[7] XU Xiaodan, DUAN Zhengjie, CHEN Zhongyu. The sentiment mining method based on extended sentiment dictionary and integrated features[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 15 -18 .
[8] MENG Jian, LI Yibin, LI Bin. Bound gait controlling method of quadruped robot[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 28 -34 .
[9] SUN Xiang-yong . A note on total colorings of planar graphs without 4cycle and adjacent 3cycle[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 118 -121 .
[10] SHI Lai-shun,WAN Zhong-yi,WANG Lu-yan,XUE Yu-tao . Synthesis and performance evaluation of a novel Gemini cationic asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 122 -126 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd