标题：基于分块后重叠K-means聚类的KNN分类算法
作者：秦亚辉 何利力
作者单位：浙江理工大学信息学院，浙江 杭州 310018
关键字：KNN最邻近算法，数据分块，重叠聚类
摘要：因为KNN最近邻算法的复杂度至少为线性，所以KNN算法在大数据环境下的计算量，以及所需要的硬件开销都面临挑战。提出一种新的KNN算法即在KNN分类前引入分块和聚类算法。具体描述为：对样本先随机进行分块，再在块上聚类，形成数目比较多的簇，但如果簇的数目过多虽然能提升计算速度，但是在分类时会影响分类的精确度，所以在很多簇的基础上再进行聚类，这样不仅速度大大提高，精确度也能提高，从而达到分类精确度的提高。最后在测试过程中找出与待测样本距离最短的块作为新的训练样本作为进行分类算法。