188宝金博页面版

  作者简介：张兵(1991-)，女，硕士生，主要研究方向为数据挖掘、粗糙集，(E-mail:1365026003qq.com)；蒙祖强(1989-)，男，博士，教授，博士生导师，主要研究方向为人工智能、粒度计算、知识发现等。 *国家自然科学基金项目（NO.61363027）和广西自然科学基金项目（NO.2015GXNSFAA139292）资助。 1 基于局部密度和纯度的自适应 k 近邻算法 张兵 蒙祖强 沈亮亮 李虹利 （广西大学 计算机与电子信息学院 广西南宁 530004） 摘要： 【目的】针对 KNN 算法中 k 值的选取通常是人为设定，而且通常是固定的缺点，研究如何更好地选取 k 值。 【方法】引入了 k 的可信度的概念，提出了一种基于局部密度和纯度的自适应选取 k 值的方法，并将其引入到传统的 KNN 分类算法中。 【结果】该算法合理的考虑了样本的局部密度、纯度与选取 k 值的关系，不仅解决了 k 值的选取问题，并且避免了固定 k 值对分类的影响。 【结论】该算法是有效的，可以得到较高的准确率，且算法的时效性有待提高。 关键词：k 的可信度 自适应 k 值 KNN 分类 中图法分类号: :TP18 文献标识码: :A Adaptive k neighbor algorithm based on local density and purity ZHANG Bing MENG Zuqiang SHEN Liangliang LI Hongli (College of Computer, Electronics and Information, Guangxi University, Nanning,Guangxi,530004, China) Abstract： 【Objective】 】Aiming at the selection of parameter k value(usually fixed) in KNN algorithm is usually set by users,we should study how to better select of k values.【Methods】This paper introduced the concept of the credibility of k, and proposed an improved adaptive selection of k values based on the local density and purity, and introduced into the traditional KNN classification algorithm. 【Results】The algorithm is reasonable to consider the relationship between the local density and purity and the seletion of k values, which not only solves the problems of choosing k values, but also avoids the influence of fixed k value on classification. 【Conclusion】The algorithm is effective and can get higher accuracy, and timeliness is also enhanced. Keywords: Credibility of k, Adaptive k, KNN classification 0.引言 【 研究意义】KNN 算法是数据挖掘“十大经典算法”之一 [1] 。KNN 分类方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史记录的已知特征值来预测当前记录的未知或者遗失特征值[2] 。KNN 是基于统计的分类方法 [3] ，如果待分类样本在特征空间中的 k 个最相似（即特征空间中最邻近）的样本中的大多数样本属于某一个类别，则该样本也属于这个类别。因此具有简单直观、无需先验统计知识、性能优越的特点，得到了广泛应用。但是传统的 KNN 算法是一种懒惰的学习方法，具有以下的缺点：（1）在样本较大以及特征属性较多时，分类的效率就大大降低；（2）参数 K 值只能由经验设置，并且对某一个数据集分类效果较好的取值对于其他数据集可能并没有很好的分类效果。【 前人研究进展】为了克服传统 KNN 算法的缺点，学者们提出了许多针对 KNN 的改进算法。这些算法大致可以分为两类。一类是通过优化或者降维来减少样本之间相关性的计算，以提高分类的效率；如胡元等 [4] 于 2012 年提出了一种基于区域划分的 kNN 文本快速分类算法，该算法是将训练样本集按空间分布划分成若干个区域，然后根据测试样本与各个区域之间的位置关系快速查找其 k 个近邻，大大降低了 KNN 算法的计算量。林啟锋等 [5] 于2013 年提出结合同义向量聚合和特征多类别的改进 KNN 分类算法，该算法明显提高了文本分类效率，提高了分类的精度。耿丽娟等 [6] 于 2014 年提出多层差分 KNN 算法，该算法对已知样本数据类域进行分层，大大降低了无效的计算量，提高了分类的准确性。另一类是通过改进参数 k 取值的方法，提高分类准确率。 DOI：10.13657/j.cnki.gxkxyxb.20170215.002 网络出版时间：2017-02-15 16:59:19网络出版地址：http://www.cnki.net/kcms/detail/45.1075.N.20170215.1659.004.html