-
针对联合作战战役行动中平台聚类编组问题, 本文提出了一种基于量子K-means的量子增强求解方法. 该方法首先分别对经典K-means算法中的聚类类别数目设定和聚类中心点选择两部分进行了优化处理; 其次, 该方法针对聚类数据样本与各聚类中心点之间的欧氏距离构建对应的量子线路; 然后, 该方法针对聚类数据集的误差平方和构建对应的量子线路. 实验结果表明, 所提方法不但有效解决了此类行动规模下的平台聚类编组问题, 与经典K-means算法相比, 算法的时间复杂度和空间复杂度都有较大幅度降低.
-
关键词:
- 量子K-means算法 /
- 量子增强 /
- 平台聚类
The paper proposes a quantum enhanced solution method based on quantum K-means for platform clustering and grouping in joint operations campaigns. The method first calculates the number of categories for platform clustering based on the determined number of task clusters, and sets the number of clustering categories in the classical K-means algorithm. By using the location information of the tasks, the clustering center points are calculated and derived. Secondly, the Euclidean distance is used as an indicator to measure the distance between the platform data and each cluster center point. The platform data are quantized and transformed into their corresponding quantum state representations. According to theoretical derivation, the Euclidean distance solution is transformed into the quantum state inner product solution. By designing and constructing a universal quantum state inner product solution quantum circuit, the Euclidean distance solution is completed. Then, based on the sum of squared errors of the clustering dataset, the corresponding quantum circuits are constructed through calculation and deduction. The experimental results show that compared with the classical K-means algorithm, the proposed method not only effectively solves the platform clustering and grouping problem on such action scales, but also significantly reduces the time and space complexity of the algorithm.-
Keywords:
- QK-means algorithm /
- quantum enhancement /
- platform clustering
[1] 张守玉, 张炜 2016 装备学院学报 27 36
Google Scholar
Zhang S Y, Zhang W 2016 J. Equip. Acad. 27 36
Google Scholar
[2] Wang X, Yao P Y, Zhang J Y, Wan L J, Jia F C 2019 J. Syst. Eng. Electron. 30 110
Google Scholar
[3] 杨宇 2023 电讯技术 63 941
Yang Y 2023 Telecommun. Eng. 63 941
[4] Márquez C R, Braganholo V, Ribeiro C C 2024 Ann. Oper. Res. 338 05995
Google Scholar
[5] Macqueen J 1967 Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability (Berkeley: University of California Press) p281
[6] Lin Y S, Wang K D, Ding Z G 2023 Ieee Wirel. Commun. Le. 12 1130
Google Scholar
[7] Moyème K D, Yao B, Kwami S S, Pidéname T, Yendoubé L 2024 Energies 17 3022
Google Scholar
[8] Mottier M, Chardon G, Pascal F 2024 Ieee T. Aero. Elec. Sys. 60 3639
[9] Ayad M J, Ku R K 2021 Indon. J. Electr. Eng. Co. 24 1744
[10] Li Y X, Liu M L, Wang W C, Zhang Y H 2020 Ieee T. Multimedia 22 1385
[11] Rani R S, Madhavan P, Prakash A 2022 Circ. Syst. Signal Pr. 41 3882
Google Scholar
[12] Al-Rahayfeh A, Atiewi S, Abuhussein A, Almiani M 2019 Future Internet 11 109
Google Scholar
[13] Tang D, Man J P, Tang L, Feng Y, Yang Q W 2020 Ad Hoc Netw. 102 102145
Google Scholar
[14] Pu Y N, Sun J, Tang N S, Xu Z B 2023 Image Vision Comput. 135 104707
[15] Borzooei S, Miranda Ge H B, Abolfathi S, Scibilia G, Meucci L, Zanetti M C 2020 Water Sci. Technol. 81 1541
Google Scholar
[16] Culos A E, Andrews J L, Afshari H 2020 Commun. Stat-Simul C. 51 5658
[17] Barkha N, Poonam V, Priya K 2016 IJLTET 7 121
[18] Ikotun A M, Ezugwu A E, Abualigah L, Abuhaija B, Jia H E 2022 Inform. Sci. 622 178
[19] Zhang Z B, Ling B W, Huang G H 2024 Ieee T. Signal Proces. 72 1348
Google Scholar
[20] Capó M, Pérez A, Lozano J A 2021 Ieee T. Neur. Net. Lear. 32 2195
[21] Wan B T, Huang W K, Pierre B, Cheng W W, Zhou S F 2024 Granular Comput. 9 45
Google Scholar
[22] Hamzehi M, Hosseini S 2022 Multimed. Tools Appl. 81 33233
Google Scholar
[23] Serkan T, Fatih O 2022 Appl. Sci. 12 11
[24] Eissa M A Q 2022 Tehnički Glasnik 16 3
[25] Wei R K, Liu Y, Song J K, Xie Y Z, Zhou K 2024 Ieee T. Image Process. 33 1768
Google Scholar
[26] Pavan P, Vani B 2022 ECS Transactions 107 13055
Google Scholar
[27] Crognale M, Iuliis M D, Rinaldi C, Gattulli V 2023 Earthq. Eng. Eng. Vib. 22 333
Google Scholar
[28] Mohit M, Madhur M, Ketan L 2020 Int. J. Futur. Gener. Co. 13 2S
[29] Ibrahem A W, Hashim H A, AbdulKhaleq N Y, Jalal A A 2022 Indon. J. Electr. Eng. Co. 27 1151
[30] Bezdan T, Stoean C, Naamany A A, Bacanin N, Rashid T A, Zivkovic M, Venkatachalam K 2021 Mathematics 9 1929
Google Scholar
[31] Tomesh T, Gokhale P, Anschuetz E R, Chong F T C 2021 Electronics 10 1690
Google Scholar
[32] Ouedrhiri O, Banouar O, Hadaj S E, Raghay S 2022 Concurr. Comp-Pract E. 34 e6943
Google Scholar
[33] Gong C G, Dong Z Y, Gani A, Han Q 2021 Quantum Inf. Process. 20 130
Google Scholar
[34] 张毅军, 慕晓冬, 郭乐勐, 张朋, 赵导, 白文华 2023 物理学报 72 070302
Google Scholar
Zhang Y J, Mu X D, Guo L M, Zhang P, Zhao D, Bai W H 2023 Acta Phys. Sin. 72 070302
Google Scholar
[35] 刘雪娟, 袁家斌, 许娟, 段博佳 2018 吉林大学学报(工学版) 48 539
Liu X J, Yuan J B, Xu J, Duan B J 2018 J. Jilin Univ. (Eng. Ed. ) 48 539
[36] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503
Google Scholar
-
图 1 K-means算法的具体聚类流程图
Fig. 1. Specific clustering process diagram of the K-means algorithm.
图 2 初始化平台集聚类分簇K值图
Fig. 2. K value graph of initialization platform clustering class clustering.
图 3 制备量子态${S_{11}}$量子线路概率图
Fig. 3. Probability diagram for preparing quantum circuits of quantum state ${S_{11}}$.
图 4 制备量子态${\left| 0 \right\rangle _1}{\left| \varphi \right\rangle _2}{\left| \phi \right\rangle _3}\xrightarrow{{1:H}}\dfrac{1}{{\sqrt 2 }}\left( {{{\left| 0 \right\rangle }_1}{{\left| \varphi \right\rangle }_2}{{\left| \phi \right\rangle }_3} + {{\left| 1 \right\rangle }_1}{{\left| \varphi \right\rangle }_2}{{\left| \phi \right\rangle }_3}} \right)$的通用量子线路图
Fig. 4. The general quantum circuit diagram for preparing quantum states ${\left| 0 \right\rangle _1}{\left| \varphi \right\rangle _2}{\left| \phi \right\rangle _3}\xrightarrow{{1:H}}\dfrac{1}{{\sqrt 2 }}\left( {{{\left| 0 \right\rangle }_1}{{\left| \varphi \right\rangle }_2}{{\left| \phi \right\rangle }_3} + {{\left| 1 \right\rangle }_1}{{\left| \varphi \right\rangle }_2}{{\left| \phi \right\rangle }_3}} \right)$.
图 5 量子态内积求解对应的量子线路图
Fig. 5. The quantum circuit diagram corresponding to solving the inner product of quantum states.
图 6 在4种公共数据集下, 两种算法的准确率比较图
Fig. 6. Comparison of accuracy between two algorithms on four common datasets.
图 7 在4种公共数据集下, 两种算法的运行时间对比图
Fig. 7. Comparison of runtime between the two algorithms on four common datasets.
图 8 在4种公共数据集下, 两种算法的迭代次数对比图
Fig. 8. Comparison of iteration times of two algorithms on four common datasets.
图 10 在3组平台数据下, 两种算法的实验结果比较图
Fig. 10. Comparison of experimental results of two algorithms under three sets of platform data.
图 11 在3组平台数据下, 两种算法的运行时间对比图
Fig. 11. Comparison of runtime between two algorithms under three sets of platform data.
图 12 在3组平台数据下, 两种算法的迭代次数对比图
Fig. 12. Comparison of iteration times of two algorithms under three platform data groups.
表 1 实验数据集信息表
Table 1. Experimental dataset information table.
数据集 样本数 特征维度数 类别数 Haberman 306 3 2 Iris 150 4 3 Diabetes 768 8 2 Wine 178 13 3 
下载: 导出CSV
表 2 基于QK-means的量子增强求解方法的伪代码
Table 2. Pseudo code of the quantum enhancement solution method based on QK-means.
算法1. 基于QK-means的量子增强求解方法的伪代码 输入: 输入数据集S(N, M, K), 其中N表示数据集样本数量, M表示数据样本维度, K表示数据分类个数. 初始化量子软件开发环境与量子云平台 输出: K个聚类分簇以及每个分簇所包含的数据样本 初始化量子软件开发环境${Q_r}$与量子比特数量 1) 根据输入数据集分类个数确定聚类中心数为K 2) 结合公共数据集实际情况, 根据3.1节中所述选取聚类中心点的方法, 将每个分簇数据集合的平均值作为初始聚类中心点位置 3) 对数据样本和聚类中心点进行量子化, 并给SSE赋一个较大值 4) while SSE值$ \geqslant $阈值 do 5) 通过基于QK-means的量子线路制备量子态, 计算数据样本与各聚类中心点之间的欧氏距离$D\left( {{x_i}, {c_k}} \right)$ 6) 根据$D\left( {{x_i}, {c_k}} \right)$, 当$D\left( {{x_i}, {c_k}} \right)$取到$\mathop {\min }\limits_{i, k} D\left( {{x_i}, {c_k}} \right)$时, 将${x_i} \to {C_k}$ 7) 计算每个${N_k}$, 并求该聚类分簇的平均值${c'_k} = \dfrac1{{{N_k}}}{{\displaystyle\sum\limits_{{x_i} \in {C_k}} {{x_i}} }}$ 8) 通过${c'_k}$更新聚类中心位置 9) 求解整个聚类数据集的残差平方和${\text{SSE}} = {\displaystyle\sum\limits_{k = 1}^K {\displaystyle\sum\limits_{{x_i} \in {C_k}} {\left| {D\left( {{x_i}, {c_k}} \right)} \right|} } ^2}$ 10) end while 11) 输出每个${C_k}$
下载: 导出CSV
-
[1] 张守玉, 张炜 2016 装备学院学报 27 36
Google Scholar
Zhang S Y, Zhang W 2016 J. Equip. Acad. 27 36
Google Scholar
[2] Wang X, Yao P Y, Zhang J Y, Wan L J, Jia F C 2019 J. Syst. Eng. Electron. 30 110
Google Scholar
[3] 杨宇 2023 电讯技术 63 941
Yang Y 2023 Telecommun. Eng. 63 941
[4] Márquez C R, Braganholo V, Ribeiro C C 2024 Ann. Oper. Res. 338 05995
Google Scholar
[5] Macqueen J 1967 Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability (Berkeley: University of California Press) p281
[6] Lin Y S, Wang K D, Ding Z G 2023 Ieee Wirel. Commun. Le. 12 1130
Google Scholar
[7] Moyème K D, Yao B, Kwami S S, Pidéname T, Yendoubé L 2024 Energies 17 3022
Google Scholar
[8] Mottier M, Chardon G, Pascal F 2024 Ieee T. Aero. Elec. Sys. 60 3639
[9] Ayad M J, Ku R K 2021 Indon. J. Electr. Eng. Co. 24 1744
[10] Li Y X, Liu M L, Wang W C, Zhang Y H 2020 Ieee T. Multimedia 22 1385
[11] Rani R S, Madhavan P, Prakash A 2022 Circ. Syst. Signal Pr. 41 3882
Google Scholar
[12] Al-Rahayfeh A, Atiewi S, Abuhussein A, Almiani M 2019 Future Internet 11 109
Google Scholar
[13] Tang D, Man J P, Tang L, Feng Y, Yang Q W 2020 Ad Hoc Netw. 102 102145
Google Scholar
[14] Pu Y N, Sun J, Tang N S, Xu Z B 2023 Image Vision Comput. 135 104707
[15] Borzooei S, Miranda Ge H B, Abolfathi S, Scibilia G, Meucci L, Zanetti M C 2020 Water Sci. Technol. 81 1541
Google Scholar
[16] Culos A E, Andrews J L, Afshari H 2020 Commun. Stat-Simul C. 51 5658
[17] Barkha N, Poonam V, Priya K 2016 IJLTET 7 121
[18] Ikotun A M, Ezugwu A E, Abualigah L, Abuhaija B, Jia H E 2022 Inform. Sci. 622 178
[19] Zhang Z B, Ling B W, Huang G H 2024 Ieee T. Signal Proces. 72 1348
Google Scholar
[20] Capó M, Pérez A, Lozano J A 2021 Ieee T. Neur. Net. Lear. 32 2195
[21] Wan B T, Huang W K, Pierre B, Cheng W W, Zhou S F 2024 Granular Comput. 9 45
Google Scholar
[22] Hamzehi M, Hosseini S 2022 Multimed. Tools Appl. 81 33233
Google Scholar
[23] Serkan T, Fatih O 2022 Appl. Sci. 12 11
[24] Eissa M A Q 2022 Tehnički Glasnik 16 3
[25] Wei R K, Liu Y, Song J K, Xie Y Z, Zhou K 2024 Ieee T. Image Process. 33 1768
Google Scholar
[26] Pavan P, Vani B 2022 ECS Transactions 107 13055
Google Scholar
[27] Crognale M, Iuliis M D, Rinaldi C, Gattulli V 2023 Earthq. Eng. Eng. Vib. 22 333
Google Scholar
[28] Mohit M, Madhur M, Ketan L 2020 Int. J. Futur. Gener. Co. 13 2S
[29] Ibrahem A W, Hashim H A, AbdulKhaleq N Y, Jalal A A 2022 Indon. J. Electr. Eng. Co. 27 1151
[30] Bezdan T, Stoean C, Naamany A A, Bacanin N, Rashid T A, Zivkovic M, Venkatachalam K 2021 Mathematics 9 1929
Google Scholar
[31] Tomesh T, Gokhale P, Anschuetz E R, Chong F T C 2021 Electronics 10 1690
Google Scholar
[32] Ouedrhiri O, Banouar O, Hadaj S E, Raghay S 2022 Concurr. Comp-Pract E. 34 e6943
Google Scholar
[33] Gong C G, Dong Z Y, Gani A, Han Q 2021 Quantum Inf. Process. 20 130
Google Scholar
[34] 张毅军, 慕晓冬, 郭乐勐, 张朋, 赵导, 白文华 2023 物理学报 72 070302
Google Scholar
Zhang Y J, Mu X D, Guo L M, Zhang P, Zhao D, Bai W H 2023 Acta Phys. Sin. 72 070302
Google Scholar
[35] 刘雪娟, 袁家斌, 许娟, 段博佳 2018 吉林大学学报(工学版) 48 539
Liu X J, Yuan J B, Xu J, Duan B J 2018 J. Jilin Univ. (Eng. Ed. ) 48 539
[36] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503
Google Scholar
下载:
计量
- 文章访问数: 297
- PDF下载量: 13
- 被引次数: 0
