基于海明距离的量子k-medians算法
Quantum K-Medians Algorithm Based on Hamming Distance
辛娟娟 1魏贺 2戚晗 2拱长青2
作者信息
- 1. 沈阳航空航天大学计算机学院,辽宁 沈阳 110136;沈阳航空航天大学计算机学院,辽宁 沈阳 110136
- 2. 沈阳航空航天大学计算机学院,辽宁 沈阳 110136
- 折叠
摘要
随着大数据时代的到来,传统数据的相似性度量算法不再适用于高维数据的聚类.基于量子计算,人们提出利用控制交换门(Control-Swap)计算数据间相似度.但是,由于初始量子态的分解和制备是困难的,导致该算法的实用性降低.因此提出一种基于海明距离的量子k-medians(QHk-medians)算法来实现对高维结构化数据的聚类.QHk-medians主要由子程序Hamm DistCalc与GroverOptim组成.设计了子程序Hamm DistCalc和GroverOptim的通用量子线路,并基于IBM Qiskit进行了实验模拟,成功对网络入侵数据聚类.提出的QHk-medians算法量子态构造简单,能准确的测量两个独立高维数据的相似度并实现聚类,与经典k-medians相比,算法时间复杂度降低,分类准确率更高.
Abstract
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 cal-culate 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 subrou-tines 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-medi-ans algorithm has a simple quantum state construction and can accurately measure the similarity between two inde-pendent high-dimensional data and achieve clustering.Compared with classical k-media,the algorithm has lower time complexity and higher classification accuracy.
关键词
汉明距离/网络入侵检测/仿真Key words
Hamming distance/Network intrusion detection/Simulation引用本文复制引用
基金项目
辽宁省教育研究厅科学研究项目(LJKZ0208)
沈阳航天大学高层次人才引进研究基金(18YB06)
出版年
2024
NETL
NSTL
维普
万方数据