基于参考点的改进k近邻分类算法

详细信息    查看全文 | 推荐本文 |

英文篇名：Improvement k-Nearest Neighbor Classification Algorithm Based on Reference Points 作者：梁聪 ; 夏书银 ; 陈子忠 英文作者：LIANG Cong;XIA Shuyin;CHEN Zizhong;College of Computer Science and Technology,Chongqing University of Posts and Telecommunications; 关键词：k近邻 ; 参考点 ; 自适应权重 ; 方差 ; 分类效率 英文关键词：k-Nearest Neighbor(kNN);;reference points;;self-adaptive weight;;variance;;classification efficiency 中文刊名：JSJC 英文刊名：Computer Engineering 机构：重庆邮电大学计算机科学与技术学院; 出版日期：2018-03-14 09:29 出版单位：计算机工程 年：2019 期：v.45;No.497 基金：国家重点研发计划(2016QY01W0200,2016YFB1000905);; 重庆市教委科学技术研究项目(KJ1600426,KJ1600419) 语种：中文; 页：JSJC201902028 页数：6 CN：02 ISSN：31-1289/TP 分类号：173-178

摘要

基本k近邻(kNN)分类算法具有二次方的时间复杂度,且分类效率和精度较低。针对该问题,提出一种改进的参考点kNN分类算法。依据点到样本距离的方差选择参考点,并赋予参考点自适应权重。实验结果表明,与基本k NN算法及kd-tree近邻算法相比,该算法具有较高的分类精度及较低的时间复杂度。
        The basic k-Nearest Neighbor( kNN) classification algorithm has quadratic time complexity,has a low classification efficiency and has a low classification accuracy. Aiming at this problem,an improvement reference points kNN classification algorithm is proposed. The reference point is selected according to the variance of the point-to-sample distance,and the reference point is given an adaptive weight. Experimental results show that compared with the basic kNN algorithm and kd-tree neighbor algorithm,this algorithm has high classification accuracy and has low time complexity.

引文

[1]何清,李宁,罗文娟,等.大数据下的机器学习算法综述[J].模式识别与人工智能,2014,27(4):327-336.
    [2]王煜,张明,王正欧,等.用于文本分类的改进KNN算法[J].计算机工程与应用,2007,43(13):159-162.
    [3] POLI G,LLAPA E,CECATTO J R,et al. Solar flare detection system based on tolerance near sets in a GPUCUDA framew ork[J]. Know ledge-Based Systems,2014,70(C):345-360.
    [4] BHATTACHARYA G,GHOSH K,CHOWDHURY A S.Granger causality driven AHP for feature weighted k NN[J]. Pattern Recognition,2017,66:425-436.
    [5]吴泽泰,蔡仁钦,徐书燕,等.基于K近邻法的WiFi定位研究与改进[J].计算机工程,2017,43(3):289-293.
    [6] UGUZ H. A two-stage feature selection method for text categorization by using information gain,principal component analysis and genetic algorithm[J].Know ledge-Based Systems,2011,12(5):1024-1032.
    [7]周红标,乔俊飞.基于高维k-近邻互信息的特征选择方法[J].智能系统学报,2017,12(5):595-600.
    [8] XIA Shuyin,XIONG Zhongyang,LUO Yueguo,et al.Location difference of multiple distances based k-nearest neighbors algorithm[J]. Know ledge-Based Systems,2015,90(C):99-110.
    [9] GOU J,ZHAN Y,RAO Y,et al. Improved pseudo nearest neighbor classification[J]. Know ledge-Based Systems,2014,70(C):361-375.
    [10] FRIEDMAN J H,BENTLEY J L,FINKEL R A. An algorithm for finding best matches in logarithmic expected time[J]. ACM Transactions on M athematical Softw are,1977,3(3):209-226.
    [11] FUKUNAGA K,NARENDRA P M. A branch and bound algorithm for computing k-nearest neighbors[J]. IEEE Transactions on Computers,1975,24(7):750-753.
    [12] CHEN Y S,HUNG Y P,TEN T F,et al. Fast and versatile algorithm for nearest neighbor search based on a low er bound tree[J]. Pattern Recognition,2007,40(2):360-375.
    [13] LIAW Y C,LEOU M L,WU C M. Fast exact k nearest neighbors search using an orthogonal search tree[J].Pattern Recognition,2010,43(6):2351-2358.
    [14]钱途,钱江波,董一鸿,等. SLSB-forest:高维数据的近似k近邻查询[J].电信科学,2017,33(9):58-68.
    [15] YANG Liu,DONG Limei,BI Xiaoru. An improved location difference of multiple distances based nearest neighbors searching algorithm[J]. International Journal for Light and Electron Optics,2016,127(22):10838-10843.