基于聚类的加速k-近邻分类方法

SPEEDING K-NN CLASSIFICATION METHOD BASED ON CLUSTERING

实际生活中,经常会遇到大规模数据的分类问题,传统k-近邻k-NN(k-Nearest Neighbor)分类方法需要遍历整个训练样本集,因此分类效率较低,无法处理具有大规模训练集的分类任务。针对这个问题,提出一种基于聚类的加速k-NN分类方法 C_kNN(Speeding k-NN Classification Method Based on Clustering)。该方法首先对训练样本进行聚类,得到初始聚类结果,并计算每个类的聚类中心,选择与聚类中心相似度最高的训练样本构成新的训练样本集,然后针对每个测试样本,计算新训练样本集中与其相似度最高的k个样本,并选择该k个近邻样本中最多的类别标签作为该测试样本的预测模式类别。实验结果表明,C_k-NN分类方法在保持较高分类精度的同时大幅度提高模型的分类效率。

There are a lot of large-scale data classification problems in practical life,and traditional k-nearest neighbour （k-NN） classification method always needs to traverse entire training sample set,so its classification efficiency is low and can not solve the classification problems with large-scale training set.To solve this problem,this paper presents a clustering-based speeding k-NN classification method,called C_k-NN.The method first clusters the training sample to obtain initial clustering results,and calculates the cluster centres of each category,and chooses those training samples having the highest similarity to the cluster centre to form the new training sample set.Then aiming at every test sample it calculates k samples in the new training sample set with the highest similarities as it,and selects the category labels the most in number in these k nearest neighbour samples as the forecasting pattern category of this testing sample.Experimental results demonstrate that the proposed C _k-NN classification method can improve the model classification efficiency greatly while keeping higher accuracy as well.