基于海明距离的量子k-medians算法  

Quantum K-Medians Algorithm Based on Hamming Distance

作　　者：辛娟娟 魏贺 戚晗 拱长青 XIN Juan-juan;WEI He;Qi Han;GONG Chang-qing(School of Computer Science,Shenyang Aerospace University,Shenyang Liaoning 110136,China)

机构地区：[1]沈阳航空航天大学计算机学院,辽宁沈阳110136

出　　处：《计算机仿真》2024年第1期409-414,共6页Computer Simulation

基　　金：辽宁省教育研究厅科学研究项目(LJKZ0208);沈阳航天大学高层次人才引进研究基金(18YB06)。

摘　　要：随着大数据时代的到来,传统数据的相似性度量算法不再适用于高维数据的聚类。基于量子计算,人们提出利用控制交换门(Control-Swap)计算数据间相似度。但是,由于初始量子态的分解和制备是困难的,导致该算法的实用性降低。因此提出一种基于海明距离的量子k-medians(QHk-medians)算法来实现对高维结构化数据的聚类。QHk-medians主要由子程序Hamm_DistCalc与Grover Optim组成。设计了子程序Hamm_DistCalc和Grover Optim的通用量子线路,并基于IBM Qiskit进行了实验模拟,成功对网络入侵数据聚类。提出的QHk-medians算法量子态构造简单,能准确的测量两个独立高维数据的相似度并实现聚类,与经典k-medians相比,算法时间复杂度降低,分类准确率更高。With the advent of the era of big data,traditional data similarity measurement algorithms are no longer suitable for clustering of high-dimensional data.Based on quantum computing,control-swap gate is proposed to calculate the similarity between data.However,it is difficult to decompose and prepare the initial quantum state,which reduces the practicability of the algorithm.Therefore,in this paper proposed a quantum k-medians algorithm based on Hamming distance(QHk-medians)to cluster high-dimensional structured data,which is mainly composed of subroutines Hamm_DistCalc and GroverOptim.We designed the universal quantum circuit of the subroutines Hamm_DistCalc and GroverOptim,and conducted an experimental simulation based on IBM Qiskit.The proposed QHk-medians algorithm has a simple quantum state construction and can accurately measure the similarity between two independent high-dimensional data and achieve clustering.Compared with classical k-media,the algorithm has lower time complexity and higher classification accuracy.

关 键 词：汉明距离 网络入侵检测 仿真 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]