有序规范实数对多相似度K最近邻分类算法

doi:10.11772/j.issn.1001-9081.2022091376

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2673-2678.DOI: 10.11772/j.issn.1001-9081.2022091376

• 2022第10届CCF大数据学术会议 • 上一篇下一篇

有序规范实数对多相似度K最近邻分类算法

崔昊阳¹, 张晖²(), 周雷², 杨春明¹, 李波¹, 赵旭剑¹

^1.西南科技大学计算机科学与技术学院，四川绵阳 621010
^2.西南科技大学数理学院，四川绵阳 621010

收稿日期:2022-09-06 修回日期:2022-09-26 接受日期:2022-10-08 发布日期:2022-11-01 出版日期:2023-09-10
通讯作者: 张晖
作者简介:崔昊阳（1996—），男，山西长治人，硕士研究生，CCF会员，主要研究方向：机器学习、数据挖掘
周雷（1981—），男，四川眉山人，讲师，博士，主要研究方向：模糊数学、量子计算与量子信息
杨春明（1980—），男，云南华坪人，副教授，硕士，CCF会员，主要研究方向：数据挖掘、自然语言处理、大数据
李波（1977—），男，四川绵阳人，讲师，硕士，CCF会员，主要研究方向：信息安全、信息过滤
赵旭剑（1984—），男，四川绵阳人，副教授，博士，CCF会员，主要研究方向：机器学习、自然语言处理。
基金资助:
四川省科技厅重点研发项目(2021YFG0031);四川省省级科研院所科技成果转化项目(2022JDZH0035)

Multi-similarity K-nearest neighbor classification algorithm with ordered pairs of normalized real numbers

Haoyang CUI¹, Hui ZHANG²(), Lei ZHOU², Chunming YANG¹, Bo LI¹, Xujian ZHAO¹

^1.School of Computer Science and Technology，Southwest University of Science and Technology，Mianyang Sichuan 621010，China
^2.School of Mathematics and Physics，Southwest University of Science and Technology，Mianyang Sichuan 621010，China

Received:2022-09-06 Revised:2022-09-26 Accepted:2022-10-08 Online:2022-11-01 Published:2023-09-10
Contact: Hui ZHANG
About author:CUI Haoyang，born in 1996， M. S. candidate. His research interests include machine learning， data mining.
ZHOU Lei， born in 1981， Ph. D.， lecturer. His research interests include fuzzy mathematics， quantum computation and quantum information.
YANG Chunming， born in 1980， M. S.， associate professor. His research interests include data mining， natural language processing， big data.
LI Bo， born in 1977， M. S.， lecturer. His research interests include information security， information filtering.
ZHAO Xujian， born in 1984， Ph. D.， associate professor. His research interests include machine learning， natural language processing.
Supported by:
Key Research and Development Project of Science and Technology Department of Sichuan Province(2021YFG0031);Provincial Scientific Research Institutes’ Achievement Transformation Project of Science and Technology Department of Sichuan Province(2022JDZH0035)

摘要/Abstract

摘要：

针对最近邻分类算法性能受到所采用的相似度或距离度量方法影响大，且难以选择最优的相似度或距离度量方法的问题，提出一种采用多相似度的基于有序规范实数对的K最近邻分类算法（OPNs-KNN）。首先，在机器学习领域中引入有序规范实数对（OPN）这一新的数学理论，利用多种相似度或距离度量方法将训练集和测试集中所有样本全部转换为OPN，使每个OPN均包含不同的相似度信息；然后再通过改进的最近邻算法对OPN进行分类，实现不同相似度或距离度量方法的结合与互补，从而提高分类性能。实验结果表明，在Iris、seeds等数据集上与距离加权K近邻规则（WKNN）等6种最近邻分类的改进算法相比，OPNs-KNN的分类准确率提高了0.29~15.28个百分点，验证了所提算法能大幅提升分类的性能。

关键词: 机器学习, 最近邻算法, 多相似度, 分类算法, 有序规范实数对

Abstract:

For the problems that the performance of the nearest neighbor classification algorithm is greatly affected by the adopted similarity or distance measuring method， and it is difficult to select the optimal similarity or distance measuring method， with multi-similarity method adopted， a K-Nearest Neighbor algorithm with Ordered Pairs of Normalized real numbers （OPNs-KNN） was proposed. Firstly， the new mathematical theory of Ordered Pair of Normalized real numbers （OPN） was introduced in machine learning. And all the samples in the training and test sets were converted into OPNs by multiple similarity or distance measuring methods， so that different similarity information was included in each OPN. Then， the improved nearest neighbor algorithm was used to classify the OPNs， so that different similarity or distance measuring methods were able to be mixed and complemented to improve the classification performance. Experimental results show that compared with 6 improved nearest neighbor classification algorithms， such as distance-Weighted K-Nearest-Neighbor rule （WKNN） rule on Iris， seeds， and other datasets， OPNs-KNN has the classification accuracy improved by 0.29 to 15.28 percentage points， which proves that the performance of classification can be improved greatly by the proposed algorithm.

Key words: machine learning, nearest neighbor algorithm, multi-similarity, classification algorithm, Ordered Pair of Normalized real numbers (OPN)

中图分类号:

TP181

崔昊阳, 张晖, 周雷, 杨春明, 李波, 赵旭剑. 有序规范实数对多相似度K最近邻分类算法[J]. 计算机应用, 2023, 43(9): 2673-2678.

Haoyang CUI, Hui ZHANG, Lei ZHOU, Chunming YANG, Bo LI, Xujian ZHAO. Multi-similarity K-nearest neighbor classification algorithm with ordered pairs of normalized real numbers[J]. Journal of Computer Applications, 2023, 43(9): 2673-2678.

图/表 10

参考文献 20

1	REN L， MA Y Z， SHI H T， et al. Overview of machine learning algorithms［M］// WANG Y， FU M X， XU L X， et al. Signal and Information Processing， Networking and Computers： Proceedings of the 6th International Conference on Signal and Information Processing， Networking and Computers， LNEE 628. Singapore： Springer， 2020： 672-678. 10.1007/978-981-15-4163-6_80
2	BOATENG E Y， OTOO J， ABAYE D A. Basic tenets of classification algorithms K-nearest-neighbor， support vector machine， random forest and neural network： a review［J］. Journal of Data Analysis and Information Processing， 2020， 8（4）： 341-357. 10.4236/jdaip.2020.84020
3	MALVIYA A. Machine learning： an overview of classification techniques［M］// GIRI V K， VERMA N K， PATEL R K， et al. Computing Algorithms with Applications in Engineering： Proceedings of ICCAEEE 2019， AIS. Singapore： Springer， 2020： 389-401. 10.1007/978-981-15-2369-4_33
4	ALFEILAT H A ABU， HASSANAT A B A， LASASSMEH O， et al. Effects of distance measure choice on k-nearest neighbor classifier performance： a review［J］. Big Data， 2019， 7（4）： 221-248. 10.1089/big.2018.0175
5	ZHOU L. Ordered pair of normalized real numbers［J］. Information Sciences， 2020， 538： 290-313. 10.1016/j.ins.2020.05.036
6	DUDANI S A. The distance-weighted k-nearest-neighbor rule［J］. IEEE Transactions on Systems， Man， and Cybernetics， 1976， SMC-6（4）： 325-327. 10.1109/tsmc.1976.5408784
7	GOU J P， QIU W M， YI Z， et al. Locality constrained representation-based K-nearest neighbor classification［J］. Knowledge-Based Systems， 2019， 167： 38-52. 10.1016/j.knosys.2019.01.016
8	周芸，杜景林，陶晔. 基于属性加权k最近邻算法的降雨预测［J］. 计算机工程与设计， 2020， 41（6）：1605-1609.
	ZHOU Y， DU J L， TAO Y. Method for precipitation forecast based on improved k-nearest neighbor algorithm［J］. Computer Engineering and Design， 2020， 41（6）： 1605-1609.
9	刘晋胜. 基于熵降噪优化相似性距离的KNN算法研究［J］. 计算机应用与软件， 2015， 32（9）： 254-256， 285. 10.3969/j.issn.1000-386x.2015.09.061
	LIU J S. On KNN algorithm based on optimising similarity distance with entropy noise reduction［J］. Computer Applications and Software， 2015， 32（9）： 254-256， 285. 10.3969/j.issn.1000-386x.2015.09.061
10	肖辉辉，段艳明. 基于属性值相关距离的KNN算法的改进研究［J］. 计算机科学， 2013， 40（11A）：157-159， 187. 10.3969/j.issn.1002-137X.2013.z2.040
	XIAO H H， DUAN Y M. Improved the KNN algorithm based on related to the distance of attribute value［J］. Computer Science， 2013， 40（11A）： 157-159， 187. 10.3969/j.issn.1002-137X.2013.z2.040
11	TOMAŠEV N， MLADENIĆ D. Hubness-aware shared neighbor distances for high-dimensional k-nearest neighbor classification［J］. Knowledge and Information Systems， 2014， 39（1）： 89-122. 10.1007/s10115-012-0607-5
12	ZHONG X F， GUO S Z， GAO L， et al. An improved k-NN classification with dynamic k［C］// Proceedings of the 9th International Conference on Machine Learning and Computing. New York： ACM， 2017： 211-216. 10.1145/3055635.3056604
13	谢妙，林泳昌，朱晓姝. 一种基于信息熵的自适应k值KNN二分类方法［J］. 合肥工业大学学报（自然科学版）， 2021， 44（11）：1483-1486， 1505. 10.1002/clc.23746
	XIE M， LIN Y C， ZHU X S. An adaptive k-value KNN binary classification method based on information entropy［J］. Journal of Hefei University of Technology （Natural Science Edition）， 2021， 44（11）： 1483-1486， 1505. 10.1002/clc.23746
14	MITANI Y， HAMAMOTO Y. A local mean-based nonparametric classifier［J］. Pattern Recognition Letters， 2006， 27（10）： 1151-1159. 10.1016/j.patrec.2005.12.016
15	GOU J P， ZHAN Y Z， RAO Y B， et al. Improved pseudo nearest neighbor classification［J］. Knowledge-Based Systems， 2014， 70： 361-375. 10.1016/j.knosys.2014.07.020
16	GOU J P， QIU W M， MAO Q R， et al. A multi-local means based nearest neighbor classifier［C］// Proceedings of the IEEE 29th International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2017：448-452. 10.1109/ictai.2017.00075
17	WISWEDEL B， HÖPPNER F， BERTHOLD M R. Learning in parallel universes［J］. Data Mining and Knowledge Discovery， 2010， 21（1）： 130-152. 10.1007/s10618-010-0170-1
18	赵存秀. 基于混淆矩阵的分类器性能评价指标比较［J］. 电子技术与软件工程， 2020（13）：146-147.
	ZHAO C X. Comparison of classifier performance evaluation indexes based on confusion matrix［J］. Electronic Technology and Software Engineering， 2020（13）： 146-147.
19	王钰，赵晓艳，杨杏丽，等. 基于K折交叉验证Beta分布的AUC度量的置信区间［J］. 系统科学与数学， 2020， 40（9）：1564-1577. 10.12341/jssms13965
	WANG Y， ZHAO X Y， YANG X L， et al. Confidence interval of AUC measurement based on K-fold cross validation beta distribution［J］. Journal of Systems Science and Mathematical Sciences， 2020， 40（9）： 1564-1577. 10.12341/jssms13965
20	蔡瑞光，张德生，肖燕婷. 参数独立的加权局部均值伪近邻分类算法［J］. 计算机应用， 2021， 41（6）：1694-1700. 10.11772/j.issn.1001-9081.2020091370
	CAI R G， ZHANG D S， XIAO Y T. Parameter independent weighted local mean-based pseudo nearest neighbor classification algorithm［J］. Journal of Computer Applications， 2021， 41（6）： 1694-1700. 10.11772/j.issn.1001-9081.2020091370

数据集	数据量	维度数	类别数	数据集	数据量	维度数	类别数
Iris	150	4	3	wdbc	569	30	2
seeds	210	7	3	wine	178	13	3
sonar	208	60	2	sobar72	72	19	2
tae	151	5	3	glass	214	9	6

数据集	数据量	维度数	类别数	数据集	数据量	维度数	类别数
Iris	150	4	3	wdbc	569	30	2
seeds	210	7	3	wine	178	13	3
sonar	208	60	2	sobar72	72	19	2
tae	151	5	3	glass	214	9	6

数据集	k	准确率/%	召回率/%	F1值/%
glass	1	97.99	97.01	96.28
Iris	12	97.60	97.60	97.60
seeds	4	93.81	93.81	93.85
sobar72	5	90.28	87.54	88.07
sonar	1	83.51	83.18	83.33
tae	1	59.80	59.82	59.79
wdbc	3	96.84	96.16	96.58
wine	1	94.44	94.94	94.40

数据集	k	准确率/%	召回率/%	F1值/%
glass	1	97.99	97.01	96.28
Iris	12	97.60	97.60	97.60
seeds	4	93.81	93.81	93.85
sobar72	5	90.28	87.54	88.07
sonar	1	83.51	83.18	83.33
tae	1	59.80	59.82	59.79
wdbc	3	96.84	96.16	96.58
wine	1	94.44	94.94	94.40

数据集	相似度度量1	相似度度量2	q	k
glass	曼哈顿距离	闵氏距离（p=5）	11.3	1
Iris	欧氏距离	闵氏距离（p=3）	10.5	1
seeds	余弦相似度	闵氏距离（p=10）	18.9	4
sobar72	欧氏距离	闵氏距离（p=3）	18.6	1
sonar	闵氏距离（p=5）	闵氏距离（p=7）	1.7	1
tae	闵氏距离（p=8）	闵氏距离（p=9）	0.4	1
wdbc	余弦相似度	闵氏距离（p=4）	0.1	3
wine	余弦相似度	欧氏距离	0.1	1

有序规范实数对多相似度K最近邻分类算法

Multi-similarity K-nearest neighbor classification algorithm with ordered pairs of normalized real numbers

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 20

相关文章 15

编辑推荐

Metrics

数据集	准确率	召回率	F1值
glass	98.74	96.63	97.25
Iris	98.87	98.87	98.87
seeds	95.29	95.29	95.32
sobar72	92.78	90.70	91.16
sonar	88.94	88.57	88.79
tae	68.87	68.83	68.82
wdbc	97.07	96.43	96.83
wine	94.44	94.94	94.40

数据集	WKNN	LMPNN	LMKNN	MLMNN	WRKNN	WLMRKNN	OPNs-KNN
Iris	96.21	94.21	93.68	93.49	96.37	96.59	98.87
wine	82.88	86.10	86.19	87.20	92.03	92.54	94.44
sonar	80.51	82.32	81.59	83.99	84.28	85.07	88.94
wdbc	94.41	93.11	92.89	94.07	95.71	93.24	97.07
seeds	91.16	91.30	92.25	91.09	95.00	94.42	95.29
tae	53.59	58.71	57.98	57.47	57.76	58.76	68.87

[1]	钟静, 林晨, 盛志伟, 张仕斌. 基于汉明距离的量子K-Means算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2493-2498.
[2]	蓝梦婕, 蔡剑平, 孙岚. 非独立同分布数据下的自正则化联邦学习优化方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2073-2081.
[3]	黄晓辉, 杨凯铭, 凌嘉壕. 基于共享注意力的多智能体强化学习订单派送[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1620-1624.
[4]	郝劭辰, 卫孜钻, 马垚, 于丹, 陈永乐. 基于高效联邦学习算法的网络入侵检测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1169-1175.
[5]	孙晓飞, 朱静远, 陈斌, 游恒志. 融合多模态数据的药物合成反应的虚拟筛选[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 622-629.
[6]	李洪亮, 张弄, 孙婷, 李想. 分布式机器学习作业性能干扰分析与预测[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1649-1655.
[7]	包永春, 张建臣, 杜守信, 张军军. 基于非负矩阵分解与稀疏表示的多标签分类算法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1375-1382.
[8]	李晓寒, 贾华丁, 程雪, 李太勇. 基于改进遗传算法和图神经网络的股市波动预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1624-1633.
[9]	陈浩杰, 范江亭, 刘勇. 深度强化学习解决动态旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1194-1200.
[10]	王颖洁, 朱久祺, 汪祖民, 白凤波, 弓箭. 自然语言处理在文本情感分析领域应用综述[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1011-1020.
[11]	陈露, 张晓霞, 于洪. 基于先验知识的非负矩阵半可解释三因子分解算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 671-675.
[12]	许仁杰, 刘宝弟, 张凯, 刘伟锋. 基于贝叶斯权函数的模型无关元学习算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 708-712.
[13]	刘海杨, 孟令航, 林仲航, 谷源涛. 基于轨迹点聚类的航路发现方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 890-894.
[14]	谢鑫, 张贤勇, 王旋晔, 唐鹏飞. 变精度邻域等价粒的邻域决策树构造算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 382-388.
[15]	李颖之, 李曼, 董平, 周华春. 基于集成学习的多类型应用层DDoS攻击检测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3775-3784.