基于密度的KNN分类器样本裁剪算法  

A Density-based Method for Reducing Training Data in KNN

作　　者：苟和平[1] 景永霞[1] 冯百明[2] 李勇[2] 

机构地区：[1]琼台师范高等专科学校信息技术系,海南海口571100 [2]西北师范大学计算机科学与工程学院,甘肃兰州730070

出　　处：《佳木斯大学学报（自然科学版）》2013年第2期242-244,248,共4页Journal of Jiamusi University：Natural Science Edition

基　　金：教育部科学技术研究重点项目(208148);海南省自然科学基金项目(612136);琼台师范高等专科学校项目(qtkz201115)

摘　　要：KNN算法在分类准确率和召回率方面具有较好的性能,但由于样本相似度计算开销大,导致分类效率低.针对此问题,本文提出一种基于密度的训练样本裁剪算法,对训练样本的各个样本类进行聚类,根据密度不同聚集成不同的簇,删除噪声数据并计算每个样本类的相似度阈值,然后将样本类内大于类相似度阈值的样本进行合并,以减少训练样本总数.实验表明,此样本裁剪算法能够在保持KNN算法分类性能基本稳定的前提下,实现各个样本类内高相似度样本的合并,减少分类计算开销.KNN algorithm is efficient text categorization algorithm in recall and accuracy, but the computational overhead of similarity computing is huge, so the classification efficiency is lower. In this paper, a density -based method for reducing training data is presented. The method classified the samples into different clusters according to the densities, removed the noise data and calculated the similarity threshold. Some higher similar sample documents in each class were combined into one document. The experiments showed that the method can reduce the computational overhead effectively and maintain the classification stability of the KNN algorithm.

关 键 词：KNN分类 聚类 样本裁剪 相似度阈值 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]