An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance
The K-nearest neighbor (KNN) algorithm is one of the most extensively used classification algorithms, while its high time complexity limits its performance in the era of big data. The quantum K-nearest neighbor (QKNN) algorithm can handle the above problem with satisfactory efficiency; however, its...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/1/127 |
| _version_ | 1827626068259897344 |
|---|---|
| author | Congcong Feng Bo Zhao Xin Zhou Xiaodong Ding Zheng Shan |
| author_facet | Congcong Feng Bo Zhao Xin Zhou Xiaodong Ding Zheng Shan |
| author_sort | Congcong Feng |
| collection | DOAJ |
| description | The K-nearest neighbor (KNN) algorithm is one of the most extensively used classification algorithms, while its high time complexity limits its performance in the era of big data. The quantum K-nearest neighbor (QKNN) algorithm can handle the above problem with satisfactory efficiency; however, its accuracy is sacrificed when directly applying the traditional similarity measure based on Euclidean distance. Inspired by the Polar coordinate system and the quantum property, this work proposes a new similarity measure to replace the Euclidean distance, which is defined as Polar distance. Polar distance considers both angular and module length information, introducing a weight parameter adjusted to the specific application data. To validate the efficiency of Polar distance, we conducted various experiments using several typical datasets. For the conventional KNN algorithm, the accuracy performance is comparable when using Polar distance for similarity measurement, while for the QKNN algorithm, it significantly outperforms the Euclidean distance in terms of classification accuracy. Furthermore, the Polar distance shows scalability and robustness superior to the Euclidean distance, providing an opportunity for the large-scale application of QKNN in practice. |
| first_indexed | 2024-03-09T12:48:41Z |
| format | Article |
| id | doaj.art-1370ba6670d74276a9229b4ef7788d9f |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T12:48:41Z |
| publishDate | 2023-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-1370ba6670d74276a9229b4ef7788d9f2023-11-30T22:09:03ZengMDPI AGEntropy1099-43002023-01-0125112710.3390/e25010127An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar DistanceCongcong Feng0Bo Zhao1Xin Zhou2Xiaodong Ding3Zheng Shan4School of Cyber Science and Engineering, Zhengzhou University, Zhengzhou 450002, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, ChinaThe K-nearest neighbor (KNN) algorithm is one of the most extensively used classification algorithms, while its high time complexity limits its performance in the era of big data. The quantum K-nearest neighbor (QKNN) algorithm can handle the above problem with satisfactory efficiency; however, its accuracy is sacrificed when directly applying the traditional similarity measure based on Euclidean distance. Inspired by the Polar coordinate system and the quantum property, this work proposes a new similarity measure to replace the Euclidean distance, which is defined as Polar distance. Polar distance considers both angular and module length information, introducing a weight parameter adjusted to the specific application data. To validate the efficiency of Polar distance, we conducted various experiments using several typical datasets. For the conventional KNN algorithm, the accuracy performance is comparable when using Polar distance for similarity measurement, while for the QKNN algorithm, it significantly outperforms the Euclidean distance in terms of classification accuracy. Furthermore, the Polar distance shows scalability and robustness superior to the Euclidean distance, providing an opportunity for the large-scale application of QKNN in practice.https://www.mdpi.com/1099-4300/25/1/127quantum computationquantum machine learningK-nearest neighbor algorithmquantum K-nearest neighbor algorithm |
| spellingShingle | Congcong Feng Bo Zhao Xin Zhou Xiaodong Ding Zheng Shan An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance Entropy quantum computation quantum machine learning K-nearest neighbor algorithm quantum K-nearest neighbor algorithm |
| title | An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance |
| title_full | An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance |
| title_fullStr | An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance |
| title_full_unstemmed | An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance |
| title_short | An Enhanced Quantum K-Nearest Neighbor Classification Algorithm Based on Polar Distance |
| title_sort | enhanced quantum k nearest neighbor classification algorithm based on polar distance |
| topic | quantum computation quantum machine learning K-nearest neighbor algorithm quantum K-nearest neighbor algorithm |
| url | https://www.mdpi.com/1099-4300/25/1/127 |
| work_keys_str_mv | AT congcongfeng anenhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT bozhao anenhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT xinzhou anenhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT xiaodongding anenhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT zhengshan anenhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT congcongfeng enhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT bozhao enhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT xinzhou enhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT xiaodongding enhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance AT zhengshan enhancedquantumknearestneighborclassificationalgorithmbasedonpolardistance |