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

　　（3）统计这k个已标记的数据样本，哪一类的数据样本个数最多，则未标记的数据样本标记为该类样本K近邻算法没有一个数据样本训练的过程，本身是一种惰性的监督算法，该算法对k值的选择以及距离的度量方式都会影响最终的分类精度。因为该算法只是选择。 
　　k个近邻而没有判断近邻中样本是否分布得均匀。因此，该算法如果样本分布不均匀，也会大大影响分类的结果。 
　　1.2改进的kmeans算法 
　　由于传统kmeans算法初始点的影响较大，因此可以做如下改进。 
　　对于给定的数据集样本，kmeans可以通过两两比较数据集中数据样本点间的距离，选择距离最远的两个点A，B作为初始标记。同时为了去除噪声对初始点的影响，对于选定的初始标记点，可以选择以初始标记点为中心，与初始标记点距离小于阈值的若干个点的几何均值A'，B'作为最终的初始点。对于A初始标记点的若干点的选择原则是离初始标记A距离与离B距离的比值大于一定阈值的若干点，而对于B初始标记点的若干点的选择原则是离初始标记B距离与A距离的比值大于一定阈值的若干点。选定了初始点后，其后的步骤如下： 
　　（1）对该数据集中任意一个数据样本求其到A'，B'两个中心的距离，将该数据样本归属到数据样本距离A'，B'短的类； 
　　（2）对于得到的类中的数据样本，求类的均值更新两类中心； 
　　（3）重复上述过程1和2更新类中心，如果类中心不变或者类中心变化小于某一个阈值，则更新结束，形成类簇，否则继续。 
　　2实验结果与分析 
　　采用手写数字集M NIST Ha ndwritten Digits^[10]进行实验，该数字集库含有0-9的10类手写训练数据集和0-9的10类手写测试数据集。每个数据集样本的大小是28*28的图片，转化成向量是1*784维大小。从手写数据集中抽取标记为1和2的两类数据集样本，从这类数据集中随机抽取标记为1和2的数据样本各1000个，共计2000个数据样本进行实验分析。从这2000个数据样本中随机选择1600个数据样本（标记为1和2的两类数据各800个数据样本）进行k近邻分析，400个数据样本（标记为1和2的两类数据样本各200个）进行测试。对于改进的kmeans算法，将小于阈值的5个点取几何均值作为最终的初始点和传统的kmeans算法采用400个数据样本进行测试。改进的kmeans算法测试的正确率为84.25%，传统的kmeans算法初始值不确定，可能的正确率为15.75%，51%以及83.75%等。很明显，改进的kmeans算法不管从精度还是稳定性方面都优于传统的kmeans算法。k近邻算法选择曼哈顿距离和欧式距离作为距离度量的方式，同时改变k值对k近邻算法的结果进行测量，结果如图1所示，横轴表示k值选择的样本数，纵轴表示对应的测试正确率。
    从图1中可以看出，随着近邻数的增多，在一定的范围内，k近邻的精度是下降趋势。对于选择曼哈顿距离度量样本间距离的k近邻算法，当k值大于200的时候，k近邻算法对样本的分类正确率明显低于改良的kmeans算法对样本分类的正确率。而采用欧式距离度量样本间距离的k近邻算法，当k值大于380的时候，k近邻算法对样本的分类正确率才明显低于改良的kmeans算法对样本分类的正确率。因此对于k近邻算法而言，k近邻数目的选择以及样本间距离度量的方式对分类的结果都是至关重要的。同时从中可以发现，在某些情况下，无监督的学习方式可能比有监督的学习方式更有利，也更方便。 
　　参考文献： 
　　[1]Macqueen J Some methods for dassification and analysis of multivariate observations[C]Proceedings of the fifth Berkeley symposium on mathematical statistics and probabihty， 1967： 281-297 
　　[2]马勇，一种改进的K-means聚类分析算法在医院信息系统中的应用研究[J]信息资源管理学报，2012，（03）：93-96 
　　[3]杨明峰，詹良，魏春阳，等基于K-means聚类分析的不同种植区烤烟外观质量区域分类[J]中国烟草科学，2012，（02）： 12-16 
　　[4]张文明，吴江，袁小蛟基于密度和最近邻的K-means文本聚类算法[J]计算机应用，2010，（07）：1933-1935 
　　[5]袁方，周志勇，宋鑫初始聚类中心优化的k-means算法[J]计算机工程，2007，（03）：65-66 
　　[6]陈帅均，蒋平，吴钦章改进的KNN算法在光测图像关键事件评估中的应用[J]光电工程，2014，（08）：66-72 
　　[7]王渊，刘业政，姜元春基于粗糙KNN算法的文本分类方法[J]台肥工业大学学报（自然科学版），2014，（12）：1513-1517 
　　[8]孙秋月，基于SNN相似度的KNN分类算法研究[D]云南大学，2008 
　　[9]严晓明，基于类别平均距离的加权KNN分类算法[J]计算机系统应用，2014，（02）：128-132 
　　[10]The MNIST database of handwritten digits[EB/OU. http：//yann.lecun.com/exdb/mnist/