章宦记

摘要：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算法由于对初始点选择较敏感，不同的初始点将会导致不同的聚类结果。……