基于薛定谔方程的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]. 山东大学学报 (工学版), 2025, 55(5): 101-109.
[2]	陈素根,赵志忠. 融合局部截断距离及小簇合并的密度峰值聚类[J]. 山东大学学报 (工学版), 2025, 55(2): 58-70.
[3]	王梅,宋凯文,刘勇,王志宝,万达. DMKK-means——一种深度多核K-means聚类算法[J]. 山东大学学报 (工学版), 2024, 54(6): 1-7.
[4]	王丽娟,徐晓,丁世飞. 面向密度峰值聚类的高效相似度度量[J]. 山东大学学报 (工学版), 2024, 54(3): 12-21.
[5]	张鑫,费可可. 基于log鲁棒核岭回归的子空间聚类算法[J]. 山东大学学报 (工学版), 2023, 53(6): 26-34.
[6]	李兆彬,叶军,周浩岩,卢岚,谢立. 变异萤火虫优化的粗糙K-均值聚类算法[J]. 山东大学学报 (工学版), 2023, 53(4): 74-82.
[7]	侯延琛,赵金东. 任意形状聚类的SPK-means算法[J]. 山东大学学报 (工学版), 2023, 53(2): 87-92.
[8]	程业超,刘惊雷. 自适应图正则的单步子空间聚类[J]. 山东大学学报 (工学版), 2022, 52(2): 57-66.
[9]	卢建云,张蔚,李林. 一种基于动态局部密度和聚类结构的聚类算法[J]. 山东大学学报 (工学版), 2022, 52(2): 118-127.
[10]	孟银凤,杨佳宇,曹付元. 函数型数据的分裂转移式层次聚类算法[J]. 山东大学学报 (工学版), 2022, 52(1): 19-27.
[11]	朱恒东, 马盈仓, 代雪珍. 自适应半监督邻域聚类算法[J]. 山东大学学报 (工学版), 2021, 51(4): 24-34.
[12]	朱昌明,岳闻,王盼红,沈震宇,周日贵. 主动三支聚类下的全局和局部多视角多标签学习算法[J]. 山东大学学报 (工学版), 2021, 51(2): 34-46.
[13]	解子奇,王立宏,李嫚. 块对角子空间聚类中成对约束的主动式学习[J]. 山东大学学报 (工学版), 2021, 51(2): 65-73.
[14]	李蓓,赵松,谢志佳,牛萌. 电动汽车虚拟储能可用容量建模[J]. 山东大学学报 (工学版), 2020, 50(6): 101-111.
[15]	董新宇,陈瀚阅,李家国,孟庆岩,邢世和,张黎明. 基于多方法融合的非监督彩色图像分割[J]. 山东大学学报 (工学版), 2019, 49(2): 96-101.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed