高级检索

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

    A Quantum Principal Component Analysis Algorithm for Clustering Problems

    • 摘要: 聚类问题中的离群点容易影响簇中心的选择,且样本数据量规模的扩大会造成样本点间的距离计算需要消耗大量计算资源.为了解决上述问题,从簇中心选取和最短距离搜索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.

       

    /

    返回文章
    返回