基于分块后重叠K-means聚类的KNN分类算法

因为KNN最近邻算法的复杂度至少为线性,所以KNN算法在大数据环境下的计算量,以及所需要的硬件开销都面临挑战。提出一种新的KNN算法即在KNN分类前引入分块和聚类算法。具体描述为:对样本先随机进行分块,再在块上聚类,形成数目比较多的簇,但如果簇的数目过多虽然能提升计算速度,但是在分类时会影响分类的精确度,所以在很多簇的基础上再进行聚类,这样不仅速度大大提高,精确度也能提高,从而达到分类精确度的提高。最后在测试过程中找出与待测样本距离最短的块作为新的训练样本作为进行分类算法。

This paper proposes an improved KNN algorithm that use clustering algorithm in each random divided block before classification.More specifically,it first randomly divides the samples into several blocks and then cluster on each block to produce a large number of clusters.To increase computation speed,uses cluster algorithm to accomplish secondary cluster on the initial results of clustering.In this way,this paper improves the speed and accuracy of traditional KNN algorithm.