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

A Quantum Principal Component Analysis Algorithm for Clustering Problems

作　　者：刘文杰[1,2] 王博思[2] 陈君琇 Liu Wenjie;Wang Bosi;Chen Junxiu(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)

机构地区：[1]数字取证教育部工程研究中心(南京信息工程大学),南京210044 [2]南京信息工程大学计算机与软件学院,南京210044

出　　处：《计算机研究与发展》2022年第12期2858-2866,共9页Journal of Computer Research and Development

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

摘　　要：聚类问题中的离群点容易影响簇中心的选择,且样本数据量规模的扩大会造成样本点间的距离计算需要消耗大量计算资源.为了解决上述问题,从簇中心选取和最短距离搜索2个方面出发,提出了一种针对聚类问题的新型量子主成分分析算法.利用阈值更新奇异值并得到主成分,再通过势函数得到簇中心,从而减少异常值对簇中心选取的影响.此外,采用量子最小值搜索算法寻找距离样本点最近的簇中心,减少聚类所需迭代次数.以小规模数据集为例,采用Cirq量子编程框架对算法进行电路设计和仿真实验.实验结果表明,该算法与已有的量子聚类算法相比,在聚类准确度上有所提升.性能分析表明,与现有经典和量子算法比较,该算法在簇中心选取和最短距离搜索时间复杂度上有不同程度的改进,消耗资源有所降低.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.

关 键 词：量子机器学习 聚类问题 量子主成分分析 量子最小值搜索算法 奇异值分解 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] O413[自动化与计算机技术—控制科学与工程]