基于薛定谔方程的K-Means聚类算法

doi:10.6040/j.issn.1672-3961.0.2015.056

摘要/Abstract

摘要： 提出一种基于薛定谔方程的K-Means聚类算法,利用量子力学中薛定谔方程的势能函数来确定初始聚类中心。计算每个数据样本所对应的势能函数值,将势能函数值小的数据样本放入初始聚类中心集合,设置一个距离阈值,数据集合中的数据样本和初始聚类中心集合中的数据样本进行相异度计算,将相异度大于阈值的数据样本放入初始聚类中心集合,重复这一操作,直到初始聚类中心集合中的样本数量等于K为止。试验结果表明,采用该方法能很好地筛选出初始聚类中心,得到更高的聚类结果准确率和较少的迭代次数,与其他几种方法相比,聚类结果准确率平均提高约12%,同时迭代次数减少约3次。

关键词: 聚类, 薛定谔方程, K-Means, 初始聚类中心, 势能函数

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

中图分类号:

TP391

徐平安,唐雁,石教开,张辉荣. 基于薛定谔方程的K-Means聚类算法[J]. 山东大学学报(工学版), 2016, 46(1): 34-41.

XU Pingan, TANG Yan, SHI Jiaokai, ZHANG Huirong. K-Means clustering algorithm based on the Schrödinger equation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 34-41.

参考文献

[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.

相关文章 15

[1]	王换,周忠眉. 一种基于聚类的过抽样算法[J]. 山东大学学报(工学版), 2018, 48(3): 134-139.
[2]	张佩瑞,杨燕,邢焕来,喻琇瑛. 基于核K-means的增量多视图聚类算法[J]. 山东大学学报(工学版), 2018, 48(3): 48-53.
[3]	读习习,刘华锋,景丽萍. 一种融合社交网络的叠加联合聚类推荐模型[J]. 山东大学学报(工学版), 2018, 48(3): 96-102.
[4]	杨天鹏,徐鲲鹏,陈黎飞. 非均匀数据的变异系数聚类算法[J]. 山东大学学报(工学版), 2018, 48(3): 140-145.
[5]	庞人铭,王波,叶昊,张海峰,李明亮. 基于PCA相似度和谱聚类相结合的高炉历史数据聚类[J]. 山东大学学报(工学版), 2017, 47(5): 143-149.
[6]	周旺,张晨麟,吴建鑫. 一种基于Hartigan-Wong和Lloyd的定性平衡聚类算法[J]. 山东大学学报(工学版), 2016, 46(5): 37-44.
[7]	吉兴全,韩国正,李可军,傅荣荣,朱仰贺. 基于密度的改进K均值聚类算法在配网区块划分中的应用[J]. 山东大学学报(工学版), 2016, 46(4): 41-46.
[8]	李朔,石宇良. 基于位置社交网络中地点聚类推荐方法[J]. 山东大学学报(工学版), 2016, 46(3): 44-50.
[9]	江峰,杜军威,刘国柱,眭跃飞. 基于加权的K-modes聚类初始中心选择算法[J]. 山东大学学报(工学版), 2016, 46(2): 29-34.
[10]	樊淑炎, 丁世飞. 基于多尺度的改进Graph cut算法[J]. 山东大学学报(工学版), 2016, 46(1): 28-33.
[11]	朱红, 丁世飞. 变粒度二次聚类方法[J]. 山东大学学报(工学版), 2015, 45(3): 1-6.
[12]	董红斌, 张广江, 逄锦伟, 韩启龙. 一种基于协同进化方法的聚类集成算法[J]. 山东大学学报(工学版), 2015, 45(2): 1-9.
[13]	浩庆波, 牟少敏, 尹传环, 昌腾腾, 崔文斌. 一种基于聚类的快速局部支持向量机算法[J]. 山东大学学报(工学版), 2015, 45(1): 13-18.
[14]	佀君淑,朱文兴*,沙永贺. 复杂背景下的交通信号灯综合识别方法[J]. 山东大学学报(工学版), 2014, 44(2): 64-68.
[15]	陈文强1,林琛1,2,陈珂3,陈锦秀1,邹权1,2*. 基于GraphLab的分布式近邻传播聚类算法[J]. 山东大学学报(工学版), 2013, 43(5): 13-18.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed