量子k-means算法

doi:10.13229/j.cnki.jdxbgxb20170051

摘要/Abstract

摘要： 为提高经典k-means算法的计算效率,引入量子计算理论得到量子k-means算法。先将聚类数据和k个聚类中心制备成量子态,并行计算其相似度,接着利用相位估计算法将相似度信息保存到量子比特中,然后利用最小值查找量子算法查找最相似的聚类中心点。对比两种算法的复杂度可知,在一定条件下,相对经典算法而言,量子k-means算法的时间复杂度降低,空间复杂度得到指数级降低。

关键词: 人工智能, 聚类, 量子计算, 量子算法, 量子k-means

Abstract: In this paper a quantum k-means algorithm is proposed by integrating the quantum paradigm to improve the efficiency of traditional k-means algorithm. First, each vector and k cluster centers are prepared to be in quantum superposition, which are then utilized to compute the similarities in parallel. Second, the quantum amplitude estimation algorithm is applied to convert the similarities into quantum bit. Finally, from the quantum bit the most similar center of the vector is obtained using the quantum algorithm for determining the minimum. Theoretical analysis shows that, compared with the traditional quantum algorithm, the time complexity of the quantum k-means algorithm decreases under given condition and the space complexity diminishes exponentially.

Key words: artificial intelligence, clustering, quantum computation, quantum algorithm, quantum k-means

中图分类号:

TP387

刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.

LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.

参考文献

[1] 王书浩, 龙桂鲁. 大数据与量子计算[J].科学通报, 2015,60 (5): 499-508.
Wang Shu-hao, Long Gui-lu. Big data and quantum computation[J]. Chin Sci Bull, 2015, 60(5):499-508.
[2] Anguita D, Ridella S, Rivieccio F, et al. Quantum optimization for training support vector machines[J]. Neural Networks, 2003, 16(5/6): 763-770.
[3] Grover L K. A fast quantum mechanical algorithm for database search[C] ∥Proc 28th Ann ACM Symp Theory of Computing, New York, USA,1996:212-219.
[4] Rebentrost P, Mohseni M, Lloyd S. Quantum support vector machine for big data classification[J]. Physical Review Letters, 2014, 113(13): 130503.
[5] Lu S,Braunstein S L. Quantum decision tree classifier[J]. Quantum Information Processing, 2014, 13(3): 757-770.
[6] 阮越, 陈汉武, 刘志昊, 等. 量子主成分分析算法[J]. 计算机学报, 2014, 37(3): 666-676.
Ruan Yue, Chen Han-wu, Liu Zhi-hao, et al. Quantum principal component analysis algorithm[J]. Chinese Journal of Computers, 2014,37(3):666-676.
[7] 徐永振, 郭躬德, 蔡彬彬, 等. 基于一维三态量子游走的量子聚类算法[J]. 计算机科学, 2016, 43(3): 80-83.
Xu Yong-zhen, Guo Gong-de, Cai Bin-bin, et al. Quantum clustering algorithm based on one-dimensional three-state quantum walk[J]. Computer Science, 2016, 43(3): 80-83.
[8] Elhaddad M E, Mohammed S A O. Analysing the impact of quantum computing using system dynamics[C]∥Engineering & MIS (ICEMIS), IEEE, 2016: 1-5.
[9] Jain A K,Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys (CSUR), 1999, 31(3): 264-323.
[10] 许美慧,尹建芹,张玲,等. 可处理暗腔的日冕物质抛射检测新方法[J]. 光学精密工程, 2016, 24(10s):591-599.
Xu Mei-hui, Yin Jian-qin, Zhang Ling, et al. New detection method for coronal mass ejection capable of dark cavity processing[J]. Optics and Precision Engineering, 2016, 24(10s): 591-599.
[11] 王丽. 融合底层和中层字典特征的行人重识别[J]. 中国光学, 2016, 9(5): 540-546.
Wang Li. Pedestrian re-identification based on fusing low-level and mid-level features[J]. Chinese Optics, 2016, 9(5): 540-546.
[12] Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1):1-37.
[13] 秦大同, 詹森,漆正刚,等. 基于 K-均值聚类算法的行驶工况构建方法[J].吉林大学学报:工学版,2016,46(2):383-389.
Qin Da-tong, Zhan Sen, Qi Zheng-gang, et al. Driving cycle construction using K-means clustering method[J]. Journal of Jilin University(Engineering and Technology Edition),2016 ,46(2): 383-389.
[14] 赵文昌, 李忠木. 融合改进人工蜂群和K均值聚类的图像分割[J]. 液晶与显示, 2017,32(9):726-735.
Zhao Wen-chang, Li Zhong-mu. Image segmentation algorithm based on improved artificial bee colony and K-mean clustering[J]. Chinese Journal of Liquid Crystals and Displays, 2017, 32(9): 726-735.
[15] 丁有伟, 秦小麟, 刘亮, 等. 一种异构集群中能量高效的大数据处理算法[J]. 计算机研究与发展, 2015, 52(2): 377-390.
Ding You-wei, Qin Xiao-lin, Liu Liang, et al. An energy efficient algorithm for big data processing in heterogeneous cluster[J]. Journal of Computer Research and Development, 2015, 52(2): 377-390.
[16] Forrest W. How to cut datacentre carbon emissions? [EB/OL].[2014-12-08].http∥www.computerweekly.com/Articles/2008/12/05/233748/how-tocut-data-centre carbon-emissions.htm
[17] Aïmeur E, Brassard G, Gambs S. Machine learning in a quantum world[J]. Advances in Artificial Intelligence,2006,4013:431-442.
[18] Aïmeur E, Brassard G, Gambs S. Quantum clustering algorithms[C]∥Proceedings of the 24th International Conference on Machine Learning, 2007: 1-8.
[19] Aïmeur E, Brassard G, Gambs S. Quantum speed-up for unsupervised learning[J]. Machine Learning, 2013, 90(2):261-287.
[20] Lloyd S, Mohseni M, Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning[J]. arXiv, 2013:1307.0411.
[21] Brassard G, Hoyer P,Mosca M, et al. Quantum amplitude amplification and estimation[J]. Contemporary Mathematics, 2002, 305: 53-74.
[22] Durr C, Hoyer P. A quantum algorithm for finding the minimum[J/OL]. [2016-07-11].https://arxiv.org/abs/quant-ph/9607014.
[23] 李强,蒋静坪.量子K最近邻算法[J].系统工程与电子技术,2008,30(5):940-943.
Li Qiang, Jiang Jing-ping. Quantum K nearest neighbor algorithm[J]. Systems Engineering and Electronics, 2008,30(5):940-943.
[24] 陈汉武,高越,张军.量子K-近邻算法[J].东南大学学报:自然科学版, 2015, 45(4):647-651.
Chen Han-wu, Gao Yue, Zhang Jun. Quantum K-nearest neighbor algorithm[J]. Journal of Southeast University(Natural Science Edition), 2015,45(4):647-651.

相关文章 15

[1]	刘仲民,王阳,李战明,胡文瑾. 基于简单线性迭代聚类和快速最近邻区域合并的图像分割算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1931-1937.
[2]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[3]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[4]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[5]	张曼, 施树明. 典型汽车运行工况的状态转移特征分析[J]. 吉林大学学报(工学版), 2018, 48(4): 1008-1015.
[6]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[7]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[8]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[9]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[10]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[11]	邓剑勋, 熊忠阳, 邓欣. 基于谱聚类矩阵的改进DNALA算法[J]. 吉林大学学报(工学版), 2018, 48(3): 903-908.
[12]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[13]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[14]	侯现耀, 陈学武. 基于态度的公交出行信息使用市场细分[J]. 吉林大学学报(工学版), 2018, 48(1): 98-104.
[15]	赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed