基于聚类和密度裁剪的改进KNN算法

作     者：王艳飞 郝卫杰 范支菊 张三顺 张公敬 WANG Yan-fei;HAO Wei-jie;FAN Zhi-ju;ZHANG San-shun;ZHANG Gong-jing

作者机构：青岛大学数据科学与软件工程学院青岛266071 青岛大学计算机科学技术学院青岛266071 

出 版 物：《青岛大学学报（自然科学版）》 (Journal of Qingdao University(Natural Science Edition))

年 卷 期：2017年第30卷第2期

页      面：62-68页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：聚类 密度 样本裁剪 KNN算法 

摘      要：经典KNN算法在处理高维数据或样本数繁多的样本集时需要巨大的计算量,这使其在实际应用的过程中存在着一定的局限性;提出一种基于聚类和密度裁剪的改进KNN算法。在训练阶段,首先根据样本密度对整个训练集进行裁剪,然后将裁剪好的训练集进行聚类处理,得到若干个密度比较均匀的类簇并将其转化为超球。在测试阶段,采用两种方法,第一种是找出距离待测样本最近的k个超球,然后将这个k个超球内的训练样本作为新的训练样本集,在这个新的训练样本集上使用经典KNN算法得到待测样本的类别;第二种则是找出距离待测样本最近的1个超球,然后根据该超球的类别得出待测样本的类别。实验采用8个UCI样本集进行测试,实验结果表明,该算法同经典KNN相比具有良好的性能,是一种有效的分类方法。