Improved Local Mean-Based Pseudo Nearest Neighbor Algorithm

doi:10.3778/j.issn.1002-8331.2307-0117

Abstract

Abstract: Since the local mean-based pseudo nearest neighbor classification algorithm (LMPNN) is easily influenced by the parameter [k] of neighbors and noise points, an improved local mean-based pseudo nearest neighbor classification algorithm (IPLMPNN) is proposed in this paper. Firstly, the nearest neighbors of the test sample are selected by using the two-layer search rule to improve the quality of selecting neighbors. Secondly, in order to overcome the adverse influence of the subjective weighting method and strengthen the effect of each local mean vector for classification, the attention mechanism is introduced to calculate the distance weighting coefficients. Finally, an improved harmonic mean distance is provided to calculate the weighted multi-harmonic mean distance between a test sample and a local mean vector. Furthermore, the pseudo nearest neighbor points are found by the weighted multi-harmonic mean distances to classify test samples. The proposed algorithm is assessed and compared with relative algorithms for multiple data sets from UCI and KEEL. The experimental results show that IPLMPNN obtains satisfactory classification results.

Key words: local mean-based pseudo nearest neighbor classification algorithm (LMPNN), two-layer search, attention mechanism, multi-harmonic mean distance

摘要： 针对基于局部均值的伪近邻分类算法（LMPNN）易受近邻参数[k]和噪声点影响的问题，提出了一种改进的局部均值伪近邻分类算法（IPLMPNN）。利用双层搜索规则确定待测样本的最近邻，提高近邻集的选择质量；为了克服主观赋权法的不利影响，并且加强每个局部均值向量对分类的作用，引入注意力机制计算距离加权系数；使用改进的调和平均距离计算待测样本与局部均值向量之间的加权多调和平均距离，由此查找伪近邻点对待测样本进行分类。利用UCI和KEEL中的多个数据集对IPLMPNN算法进行仿真实验，并与8种相关算法进行比较。实验结果表明，IPLMPNN算法取得了令人满意的分类结果。

关键词: 局部均值的伪近邻分类算法（LMPNN）, 双层搜索, 注意力机制, 多调和平均距离

LI Yi, ZHANG Desheng, ZHANG Xiao. Improved Local Mean-Based Pseudo Nearest Neighbor Algorithm[J]. Computer Engineering and Applications, 2024, 60(5): 88-94.

李毅, 张德生, 张晓. 一种改进的局部均值伪近邻算法[J]. 计算机工程与应用, 2024, 60(5): 88-94.

References

[1] RUPPERT D, BRAUN W J, HLYNKA M, et al. The elements of statistical learning: data mining, inference, and prediction[J]. Journal of the American Statistical Association, 2010, 173: 693-694.
[2] BAILEY T L. MD-SVM: a novel SVM-based algorithm for the motif discovery of transcription factor binding sites[J]. Bioinformatics, 2019, 28(1): 56-62.
[3] MDG A, LMVB C, RER D, et al. Canadian children’s and youth’s adherence to the 24-h movement guidelines during the COVID-19 pandemic: a decision tree analysis[J]. Journal of Sport and Health Science, 2020, 9(4): 313-321.
[4] DONG Y L, WANG H M. Robust output feedback stabilization for uncertain discrete-time stochastic neural networks with time-varying delay[J]. Neural Processing Letters, 2020, 51(1): 83-103.
[5] THANT K S, THU E T T, KHAING M M, et al. Evaluation of student academic performance using na?ve Bayes classifier[J]. Advances in Computer and Communications, 2020, 1(1): 46-52.
[6] COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE Transaction on Information Theory, 1967, 13(1): 21-27.
[7] LIU F, YANG S, DING Y, et al. Single sample face recognition via BoF using multistage KNN collaborative coding[J]. Multimedia Tools and Applications, 2019, 78(10): 13297-13311.
[8] MADETI S R, SINGH S N. Modeling of P system based on experimental data for fault detection using KNN method[J]. Solar Energy, 2018, 173: 139-151.
[9] BARWAL R K, RAHEJA N. Comparative analysis of classification methods based on medical datasets[J]. Journal of Computational and Theoretical Nanoscience, 2020, 17(6): 2737-2745.
[10] TALLURI T, CHUNG H T, SHIN K. Study of battery state-of-charge estimatio with KNN machine learning method[J]. IEIE Transactions on Smart Processing and Computing, 2021, 10(6): 496-504.
[11] GOU J P, XIONG T, KUANG Y. A novel weighted voting for k-nearest neighbor rule[J]. Journal of Computers, 2011, 6(5): 833-840.
[12] ZENG Y, YANG Y, ZHAO L. Pseudo nearest neighbor rule for pattern classification[J]. Expert Systems with Applications, 2009, 36(2): 3587-3595.
[13] 曾勇, 舒欢, 胡江平, 等. 基于BP神经网络的自适应伪最近邻分类[J]. 电子与信息学报, 2016, 38(11): 2774-2779.
ZENG Y, SHU H, HU J P, et al. Adaptive pseudo nearest neighbor classification based on BP neural network[J]. Journal of Electronics and Information Technology, 2016, 38(11): 2774-2779.
[14] GOU J P, ZHAN Y, RAO Y, et al. Improved pseudo nearest neighbor classification[J]. Knowledge-Based Systems, 2014, 70: 361-375.
[15] 蔡瑞光, 张德生, 张晓. 基于双向选择的伪近邻算法[J]. 计算机工程与应用, 2021, 57(13): 102-107.
CAI R G, ZHANG D S, ZHANG X. Bidirectional selection-based pseudo nearest neighbor algorithm[J]. Computer Engineering and Applications, 2021, 57(13): 102-107.
[16] WANG Y, PAN Z, DONG J. A new two-layer nearest neighbor selection method for KNN classifier[J]. Knowledge-Based Systems, 2022, 235: 107604.
[17] 朱张莉, 饶元, 吴渊, 等. 注意力机制在深度学习中的研究进展[J]. 中文信息学报, 2019, 33(6): 1-11.
ZHU Z L, RAO Y, WU Y, et al. Research progress of attention mechanism in deep learning[J]. Joural of Information Processing, 2019, 33(6): 1-11.
[18] PAN Z, WANG Y, KU W. A new [k]-harmonic nearest neighbor classifier based on the multi-local means[J]. Expert Systems with Applications, 2017, 67(1): 115-125.
[19] PAN Z, WANG Y, KU W. A new general nearest neighbor classification based on the mutual neighborhood information[J]. Knowledge-Based Systems, 2017, 121(4): 142-152.
[20] GOU J P, SUN L Y, DU L, et al. A representation coefficient-based k-nearest centroid neighbor classifier[J]. Expert Systems with Applications, 2022, 194: 1-15.
[21] PAN Z, WANG Y, PAN Y. A new locally adaptive [k]-nearest neighbor algorithm based on discrimination class[J]. Knowledge-Based Systems, 2020, 204(9): 1-13.