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)

836

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] LI Xiaohui, LIU Xiaofei, SUN Weitong, ZHAO Yi, DONG Yuan, JIN Yinli. An inspection task assignment and path planning algorithm based on vehicles-UAVs collaboration [J]. Journal of Shandong University(Engineering Science), 2025, 55(5): 101-109.
[2] CHEN Sugen, ZHAO Zhizhong. Density peak clustering combining local truncation distance and small clusters merging [J]. Journal of Shandong University(Engineering Science), 2025, 55(2): 58-70.
[3] ZHU Hengdong, MA Yingcang, DAI Xuezhen. Adaptive semi-supervised neighborhood clustering algorithm [J]. Journal of Shandong University(Engineering Science), 2021, 51(4): 24-34.
[4] ZHU Changming, YUE Wen, WANG Panhong, SHEN Zhenyu, ZHOU Rigui. Global and local multi-view multi-label learning with active three-way clustering [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 34-46.
[5] XIE Ziqi, WANG Lihong, LI Man. Active learning of pairwise constraints in block diagonal subspace clustering [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 65-73.
[6] Bei LI,Song ZHAO,Zhijia XIE,Meng NIU. Electric vehicle virtual energy storage available capacity modeling [J]. Journal of Shandong University(Engineering Science), 2020, 50(6): 101-111.
[7] Xinyu DONG,Hanyue CHEN,Jiaguo LI,Qingyan MENG,Shihe XING,Liming ZHANG. An unsupervised color image segmentation method based on fusion of multiple methods [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 96-101.
[8] Jun QIN,Yuanpeng ZHANG,Yizhang JIANG,Wenlong HANG. Transfer fuzzy clustering based on self-constraint of multiple medoids [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 107-115.
[9] Yingxue ZHU,Ruizhang HUANG,Can MA. A short text dynamic clustering approach bias on new topic [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 8-18.
[10] Qiyue SONG, Xuewen MU, Huan CHENG. Segmentation of connected characters based on improved drop-fall algorithm [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 89-94.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[2] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[3] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[4] 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 .
[5] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[6] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[7] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[8] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
[9] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 92 -95 .
[10] SUN Yu-li,LI De-fa,ZUO Dun-wen,QI mei . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 19 -23 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd