一种针对聚类问题的量子主成分分析算法

刘文杰; 王博思; 陈君琇

doi:10.7544/issn1000-1239.20210333

一种针对聚类问题的量子主成分分析算法

¹(数字取证教育部工程研究中心(南京信息工程大学) 南京 210044)
²(南京信息工程大学计算机与软件学院南京 210044) (wenjie@163.com)

基金项目: 国家自然科学基金项目(62071240)；江苏省高校优势学科建设工程项目(PAPD)

详细信息

中图分类号: TP181; O413
计量
- 文章访问数: 172
- HTML全文浏览量: 13
- PDF下载量: 90
出版历程
- 发布日期: 2022-11-30

A Quantum Principal Component Analysis Algorithm for Clustering Problems

¹(Engineering Research Center of Digital Forensics Ministry of Education (Nanjing University of Information Science and Technology), Nanjing 210044)
²(School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044)

Funds: This work was supported by the National Natural Science Foundation of China (62071240) and the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).

摘要

摘要: 聚类问题中的离群点容易影响簇中心的选择，且样本数据量规模的扩大会造成样本点间的距离计算需要消耗大量计算资源.为了解决上述问题，从簇中心选取和最短距离搜索2个方面出发，提出了一种针对聚类问题的新型量子主成分分析算法.利用阈值更新奇异值并得到主成分，再通过势函数得到簇中心，从而减少异常值对簇中心选取的影响.此外，采用量子最小值搜索算法寻找距离样本点最近的簇中心，减少聚类所需迭代次数.以小规模数据集为例，采用Cirq量子编程框架对算法进行电路设计和仿真实验.实验结果表明，该算法与已有的量子聚类算法相比，在聚类准确度上有所提升.性能分析表明，与现有经典和量子算法比较，该算法在簇中心选取和最短距离搜索时间复杂度上有不同程度的改进，消耗资源有所降低.
- 量子机器学习 /
- 聚类问题 /
- 量子主成分分析 /
- 量子最小值搜索算法 /
- 奇异值分解
Abstract: The outliers in the clustering problem can easily affect the selection of cluster centers, and the expansion of the clustering scale will cause more computing resources to be consumed in the calculation of the distance between sample points. To address the above issues, a new quantum principal component analysis algorithm for clustering problems (QC-PCA) is proposed, improving the selection of the cluster center and the shortest distance search. In this paper, the principal components are marked by adding and subtracting thresholds to singular values and the cluster center is selected according to the potential function of the subset, thereby reduce the influence of abnormal points on the selection of the cluster center. In addition, a quantum minimum search algorithm is used to find the cluster center closest to the sample point, reducing the number of iterations required for clustering. Taking a small-scale data set as an example, the Cirq quantum programming framework is used to circuit design and simulation experiments. The experimental results show that compared with the existing quantum algorithms, the proposed QC-PCA algorithm improves the clustering accuracy. Performance analysis shows that compared with the existing classical and quantum algorithms, our algorithm has different degrees of improvement in the time complexity of the cluster center selection and the shortest distance search. And the resource consumption of the proposed QC-PCA algorithm is also lower than that of them.
- quantum machine learning /
- clustering problem /
- quantum principal component analysis /
- quantum minimum searching algorithm /
- singular value decomposition

HTML全文

参考文献(0)

施引文献(2)

期刊类型引用(2)

1.	聂萌瑶，刘鑫. 考虑最大通信量的物联网群体访问路由算法. 计算机仿真. 2024(02): 415-419 . 百度学术
2.	陈淑平，李祎，何王全，漆锋滨. 胖树拓扑中高效实用的定制多播路由算法. 计算机研究与发展. 2022(12): 2689-2707 . 本站查看