改良的kmeans与K近邻算法特性分析

摘要：kmeans算法作为无监督算法的一种，对初始点的选择比较敏感；而k近邻作为一种惰性且有监督的算法，对k值和样本间距离度量方式的选择也会影响结果。改良的kmeans算法通过遍历样本，筛选初始点，其准确率超过了k近邻算法，同时稳定性也优于传统的kmeans算法。无监督算法在一些情况下优于有监督算法。 
　　关键词：初始点；无监督；邻近点；有监督 
　　DOI：10.3969/j.issn.1005-5517.2016.1.022 
　　引言 
　　上个世纪60年代，MacQueen首次提出kmeans算法^[1]，而后的数十年中，kmeans算法被广泛应用于各种领域，比如马勇等人将kmeans算法应用在医疗系统中^[2]，杨明峰等人将kmeans聚类算法应用于对烤烟外观的区域分类^[3]。同时很多的学者投入到对kmeans算法本身特性的研究中^[4-5]、目前kmeans算法已经成为机器学习，数据挖掘等领域比较重要的方法之一。而k近邻算法是图像以及文本分类领域应用比较广泛的算法之一^[6-7]，对k近邻算法而言，k值的选择以及样本间距离的度量方式都会影响到分类的精确度。但是同样有许多学者对该算法进行了一些改善，比如孙秋月等^[8]通过对度量的样本数据的每个维度赋不同权值的方式，降低了样本数据分布不均匀导致的分类误差。严晓明等通过类别平均距离进行加权对大于某一个阈值的数据样本点进行剔除的方式来提高k近邻算法的精度^[9]。k近邻算法本身是一种惰性的监督算法，相较于其他监督算法比如支持向量机、逻辑回归、随机树等，具有算法简单、易于理解、易于实现、无需估计参数的特性。kmeans算法由于对初始点选择较敏感，不同的初始点将会导致不同的聚类结果。因此本文对kmeans算法进行改进，改良的kmeans算法对二分类的结果可以接近k近邻算法的正确率，甚至在k近邻算法选择不同的k值时，分类效果会优于采用k近邻算法的分类结果正确率，同时分类的结果也远高于随机指定初始点的kmeans算法。 
　　1 传统的分类算法与改进算法 
　　1.1传统的kmeans算法与k近邻算法 
　　对于传统的kmeans算法而言、对于给定的数据集n个样本，在不知道数据集的标记时，通过指定该数据集中的K（K≤n）数据样本作为初始中心，通过如下的方式进行聚类： 
　　（1）对该数据集中任意一个数据样本求其到k个中心的距离，将该数据样本归属到数据样本距离中心最短的类； 
　　（2）对于得到的类中的数据样本，以求类的均值等方法更新每类中心： 
　　（3）重复上述过程1和2更新类中心，如果类中心不变或者类中心变化小于某一个阈值，则更新结束，形成类簇，否则继续。 
　　但是对于传统的kmeans聚类算法而言，由于随机指定初始点，对kmeans算法通过迭代这样一种启发式的贪心算法而言不能形成一个全局最优解，迭代最终收敛的结果可能都是局部最优解。这样分类的精度就会难以预料，对最终的样本分类就难以消除随机指定初始点造成的聚类结果不一致的影响。 
　　对于传统的k近邻算法而言，对于给定的数据集，有n个数据样本是已标记的，另一部分数据样本是未标记的，对未标记的数据样本，通过如下的方式进行分类： 
　　（1）度量每个未标记数据样本与所有已标记数据样本的距离： 
　　（2）对所有求出的距离选择与未标记数据样本距离最近的K（K≤n）个已标记数据样本；