多视图生成与证据理论融合的k近邻分类算法

K-nearest Neighbor Classification Algorithm Integrating Multi-view Generation and D-S Theory

摘要

在使用k近邻算法进行分类任务时,原始数据特征描述不充分和使用多数投票法进行分类决策会严重限制算法的分类效果.为此,本文提出了一种新的多视图生成和证据理论融合的k近邻算法,通过更全面地描述数据特征以及更准确的进行分类决策,从而提升k近邻算法的分类性能.该算法首先使用超父亲一依赖决策器和随机森林算法对原始属性视图进行分类并生成两个新的标签视图,然后在原始属性视图和两个生成的标签视图上分别构建距离加权的k近邻算法,最后通过D-S证据理论融合来自不同视图k近邻算法的预测结果,从而得到最终的分类结果.实验结果表明,本文提出的算法在分类准确率和根相对平方误差两个指标上均优于传统k近邻算法及其他对比算法.

Abstract

In classification tasks utilizing k-nearest neighbors(kNN)algorithm,insufficient feature representation of original data and reliance on majority voting for decision-making can significantly hinder the algorithm′s classification performance.To address this issue,this paper proposes an Enhanced k-Nearest Neighbor algorithm(EnDWkNN)based on multi-view generation and evidence theory.This approach aims to enhance the classification performance of kNN by providing a more comprehensive description of data features and making more accurate classification decisions.It first employs multiple super-parent class-dependent estimators along with random forest algorithms to classify the original attribute view,generating two new label views.Then,distance-weighted k-NN algorithms are constructed separately on original attribute view and two generated label views.Finally,Dempster-Shafer(D-S)theory is applied to fuse the predictions from different view-based k-NN algorithms,resulting in an aggregated final classification outcome.Experimental results demonstrate that EnDWkNN outperforms traditional kNN as well as other competitors in terms of both classification accuracy and root relative squared error metrics.

关键词

分类 / k近邻 / 多视图生成 / D-S证据理论

Key words

classification / k-nearest neighbor algorithm / multi-view generation / D-S theory

[1] Jin S,Zhang F,Zheng Y,et al.CSKNN:cost-sensitive k-nearest neighbor using hyperspectral imaging for identification of wheat varieties[J].Computers and Electrical Engineering,2023,111:108896,doi:10.1016/j.compeleceng.2023.108896.
[2] Zhang J,Li Y,Shen F,et al.Hierarchical text classification with multi-label contrastive learning and KNN[J].Neurocomputing,2024,577:127323,doi:10.3390/bdcc7020106.
[3] Nguyen L V,Vo Q T,Nguyen T H.Adaptive KNN-based extended collaborative filtering recommendation services[J].Big Data and Cognitive Computing,2023,7(2):1-13,doi:10.3390/bdcc7020106.
[4] Bahrani P,Minaei Bidgoli B,Keshavarz A.A new improved KNN-based recommender system[J].The Journal of Supercomputing,2024,80(1):800-834.
[5] Guo N,Lin C,Yan H,et al.Real-time pantograph anomaly detection using unsupervised deep learning and K-nearest neighbor classification[J].IEEE Transactions on Instrumentation and Measurement,2024,73:1-13,doi:10.1109/tim.2024.330747.
[6] Wagner T.Convergence of the nearest neighbor rule[J].IEEE Transactions on Information Theory,1971,17(5):566-571.
[7] Uddin S,Haque I,Gide E.Comparative performance analysis of K-nearest neighbour(KNN)algorithm and its different variants for disease prediction[J].Scientific Reports,2023,12(1):1-11,doi:10.1038/s41598-022-10358-X.
[8] Halder R K,Uddin M N,Khraisat A.Enhancing K-nearest neighbor algorithm:a comprehensive review and performance analysis of modifications[J].Journal of Big Data,2024,11(1):1-55.
[9] Shafer G.A mathematical theory of evidence[M].Princetor:Princeton University Press,1976.
[10] Kavya R,Jabez C,Subhrakanta P.A new belief interval-based total uncertainty measure for dempster-shafer theory[J].Information Sciences,2023,642:1-19,doi:10.1016/j.ins.2023.119150.
[11] Dudani S A.The distance-weighted k-nearest-neighbor rule[J].IEEE Transactions on Systems,Man,and Cybernetics,1976,6(4):325-327.
[12] Gou J,Du L,Zhang Y,et al.A new distance-weighted k-nearest neighbor classifier[J].Journal of Information and Computational Science,2012,9(6):1429-1436.
[13] Gou J,Xiong T,Kuang Y.A novel weighted voting for k-nearest neighbor rule[J].Journal of Computers,2011,6(5):833-840.
[14] Chen J,Li Z.Adaptive condensed fuzzy monotonic K-nearest neighbors for monotonic classification[J].International Journal of Machine Learning and Cybernetics,2024,16(5):3977-3996.
[15] Zhang Y,Wang C,Huang Y,et al.Adaptive relative fuzzy rough learning for k-nearest classification[J].IEEE Transactions on Fuzzy Systems,2024,32(11):6267-6276.
[16] Li C,Jiang L,Li H,et al.Attribute weighted value difference metric[C]//Proceedings of 25th International Conference on Tools with Artificial Intelligence,2013:575-580.
[17] Jiang L,Li C.Two improved attribute weighting schemes for value difference metric[J].Knowledge and Information Systems,2019,60(2):949-970.
[18] Li C,Jiang L X,Li H W,et al.Toward value difference metric with attribute weighting[J].Knowledge and Information Systems,2017,50(3):795-825.
[19] Stanfill C,Waltz D.Toward memory-based reasoning[J].Communications of the ACM,1986,19(12):1213-1228.
[20] Fang Gong,Xingfeng Guo,Dianhong Wang,et al.Using differential evolution for an attribute-weighted inverted specific-class distance measure for nominal attributes[J].Data Mining and Knowledge Discovery,2023,37(1):409-433.
[21] El Hindi K.Specific-class distance measures for nominal attributes[J].AI Communications,2013,26(3):261-279.
[22] Zhang H,Jiang L,Li C.Multi-view attribute weighted naive bayes[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(7):7291-7302.
[23] Simsek S,Dag A,Coussement K,et al.Decision support framework for misstatement identification in financial reporting:a hybrid tree-augmented Bayesian belief approach[J].Decision Support Systems,2025,189:114369.
[24] Webb G,Boughton J,Wang Zhihai.Not so naive Bayes:aggregating one-dependence estimators[J].Machine Learning,2005,58(1):5-24.
[25] Sahami M.Learning limited dependence Bayesian classifiers[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,1996:334-338.
[26] Zhang S,Li X,Zong M,et al.Efficient kNN classification with different numbers of nearest neighbors[J].IEEE Transactions on Neural Networks and Learning Systems,2018,29(5):1774-1785.
[27] Pan Z,Wang Y,Pan Y.A new locally adaptive k-nearest neighbor algorithm based on discrimination class[J].Knowledge-Based Systems,2020,204:106185,doi:10.1016/j.knosys.2020.106185.
[28] Fan Z,Huang Y,Xi C,et al.Multiview adaptive k-nearest neighbor classification[J].IEEE Transactions on Artificial Intelligence,2024,5(3):1221-1234,doi:10.1109/access.2024.3392729.
[29] Ali A,Khan Z,Khan D M,et al.An optimal random projection k nearest neighbours nnsemble via extended neighbourhood rule for binary classification[J].IEEE Access,2024,12:61401-61409.
[30] Keogh E J,Pazzani M J.Learning augmented Bayesian classifiers:a comparison of distribution-based and classification-based approaches[C]//Proceedings of the 7th International Workshop on Artificial Intelligence and Statistics,1999:225-230,doi:10.1016/j.eswa.2023.121549.
[31] Sun Z,Wang G,Li P,et al.An improved random forest based on the classification accuracy and correlation measurement of decision trees[J].Expert Systems with Applications,2024,237:121549,doi:10.1016/j.eswa.2023.121549.
[32] Yang Y,Lv H,Chen N.A survey on ensemble learning under the era of deep learning[J].Artificial Intelligence Review,2023,56(6):5545-5589.
[33] Qiao S,Song B,Fan Y,et al.A fuzzy dempster-shafer evidence theory method with belief divergence for unmanned surface vehicle multi-sensor data fusion[J].Journal of Marine Science and Engineering,2023,11(8):1-19.
[34] Fei L,Li T,Ding W.Dempster-shafer theory-based information fusion for natural disaster emergency management:a systematic literature review[J].Information Fusion,2024,112:102585,10.1016/j.inffus.2024.102585.
[35] Gong F,Wang X,Jiang L,et al.Fine-grained attribute weighted inverted specific-class distance measure for nominal attributes[J].Information Sciences,2021,578:848-869,doi:10.1016/j.ins.2021.08.041.
[36] Qamar U,Raza M S.Practical data science with WEKA[M].Cham:Springer International Publishing,2023.
[37] Denoeux T.A k-nearest neighbor classification rule based on dempster-shafer theory[J].IEEE Transactions on Systems,Man,and Cybernetics,1995,25(5):804-813.
[38] Zeng Y,Yang Y,Zhao L.Pseudo nearest neighbor rule for pattern classification[J].Expert Systems with Applications,2009,36(2):3587-3595.
[39] Parvin H,Alizadeh H,Minaei Bidgoli B.MKNN:modified k-nearest neighbor[C]//Proceedings of the World Congress on Engineering and Computer Science,2008:1-4.
[40] Gong F,Jiang L,Zhang H,et al.Gain ratio weighted inverted specific-class distance measure for nominal attributes[J].International Journal of Machine Learning and Cybernetics,2020,11(10):2237-2246.
[41] Markelle K N,Longjohn R.UCI machine learning repository[EB/OL].https://archive.ics.uci.edu,2024.
[42] Zhang W,Jiang L,Li C.ELDP:enhanced label distribution propagation for crowdsourcing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2024,47(3):1850-1862.
[43] Fayyad U,Irani K B.Multi-intervel discretization of continuous-valued attributes for classification learning[C]//13th International Joint Conference on Artificial Intelligence,1993:1022-1027.
[44] Xu Y,Zeevi A.Towards optimal problem dependent generalization error bounds in statistical learning theory[J].Mathematics of Operations Research,2025,50(1):40-67.
[45] Su B,Jiang L,Si S.Confident learning-based noise correction for crowdsourcing[J].Pattern Recognition,2025,169:111962,doi:10.1016/j.patcog.2025.111962.
[46] Vierra A,Razzaq A,Andreadis A.Continuous variable analyses:t-test,mann-whitney,Wilcoxon sign rank[M].Cambridge:Academic Press,2023.
[47] Rainio O,Teuho J,Klén R.Evaluation metrics and statistical tests for machine learning[J].Scientific Reports,2024,14(1):1-14.

基金资助

国家自然科学基金青年项目(62406294)资助;多媒体网络通信工程湖北省重点实验室开放基金项目(2025KFKT17)资助;武汉工程大学第十六届研究生教育创新基金项目(CX2024161)资助.