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

An Improved KNN Method for Reducing the Amount of Training Samples Based on Clustering and Density

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

Classical KNN method has some limitations in the practical application process because of its large computational demands when using it to deal with high-dimensional data set including lots of sam-ples. An improved KNN method is proposed for reducing the amount of training samples based on cluste-ring and density. In the training stage, first, reduce the amount of training samples based on the samples’ density, then, cluster the training samples and turn the class clusters into hyper-spheres. In the testing stage, two methods are designed, the first is to find the testing samplers k nearest hyper-spheres, and rec-ognize all the training samples in the k nearest hyper-spheres as the new trainset, then use the classical KNN method to get the testing sample’s class in this new training set. The second is to find the testing samplers nearest hyper-sphere, and get the testing samplers class according to the hyper-sphere＇s class. Eight UCI datasets are used to do the experiments. The results show that the improved KNN method is effective and has good performance compared with classical KNN method.