搜索
龙源期刊网算法研究综述作者：丛思安王星星来源：《电子技术与软件工程》2018年第17期摘要k-means算法是一种非常简单并且使用广泛的聚类算法，但是一是k值需要预先给定，很多情况下k值的佑计很困难。二是K-Means算法对初始选取的聚类中心点很敏感，不同的中心点聚类结果有很大的不同。也就是说，有可能陷入局部最优解。三是对离群点敏感，聚类结果易产生误差。四是相似性度量的函数不同也会对聚类结果产生影响。本文针对k-means的缺陷，对这几年k-means算法的研究进展进行了综述。从初始中心点的选取、离群点的检测与去除、相似性度量等几个方面进行概括、比较最后，对k-means算法的未来趋势进行展望。【关键词】k-means算法初始聚类中心相似性度量离群点K-means聚类算法是由Steinhaus1955年、Lloyd1957年、Ball&Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，经过多年的实践证明，k-means算法依然是简单、高效的算法，并且被广泛应用在科学研究以及工业应用中，发展出大量的改进的算法。目前，k-means算法仍然是一个研究热点。K-means算法的改进主要从以下几个方面：一是如何确定合适的k值，二是如何选取好的初始聚类中心，三是离群点的检测与去除，四是距离与相似度度量的改进以及其他方面的改进等等。本文则从以上几个方面对k-means算法的研究进展进行综述。本文第一部分介绍传统的k-means算法，第二部分从各个方面介绍k-means算法的优化，第三部分进行总结以及展望。1传统的k-means算法K-means算法是一种简单、高效的聚类算法，并得到了广泛的应用。K-means算法的基本思想是首先随机选取初始聚类中心，然后计算每个样本点到初始聚类中心的欧式距离，按照距离最近的准则将它们分配给相似度最大的聚类中心所代表的类。计算每个类别所有样本点的均值，更新聚类中心，直到目标准则函数收敛为止。具体算法步骤如下：（1）用户输入类簇数目的值k，从n个样本点中随机选取k个点作为初始聚类中心;（2）遍历所有的样本点，计算每个样本点到初始聚类中心的欧式距离，欧氏距离的大小作为相似度的评判标准，欧氏距离越小，相似度越大。按照距离最近的准则将样本点分配给相似度最大的聚类中心所代表的类。（3）重新确定聚类中心。将每个类簇中的所有样本点的均值作为新的聚类中心。龙源期刊网（4）重复（2）和（3），直到聚类中心不再发生变化。2k-means算法的改进2.1初始聚类中心的选取初始聚类中心的选取对k-means算法聚类结果的影响很大，不同的初始聚类中心，可能会产生不同的聚类结果。也可以说，k-means算法是一种贪心算法，容易陷入局部最优解。贾瑞玉等人[2]主要运用了RodriguezA等人[3]提出的类簇中心都处在局部密度比较大的位置，且距离具有比它更大的局部密度的对象相对较远的思想。运用此思想可以确定最佳初始聚类中心及数据集的最佳类簇数目。贾瑞玉等人在这个思想的基础上，为了避免密度对截断距离的依赖性，重新定义了计算样本局部密度ρi的方法，计算样本点到具有比它更高的局部密度数据对象的最近距离δi（当样本点xi是数据集中具有最大局部密度的样本点时，δi定义为xi和距离他最远的样本点之间的欧氏距离）。根据ρi和δi构造决策图，运用统计学中残差分析的方法，选取残差绝对值大于阈值的异常点，即为聚类中心。在二维以及高维数据集上的实验结果均验证了该算法的有效性。但是不足之处在于这个算法适用于比较集中的数据集，稀疏的数据集结果并不理想。LeiGu[4]等人采用减法聚类的算法确定初始聚类中心。首先是计算每个样本点的山峰函数值，选取山峰函数值最大的点作为聚类中心。选取下一个聚类中心时要消除已经确定的聚类中心的影响，就修改山峰函数，减去上一个确定的聚类中心的比例高斯函数，如此反复，直到得到足够多的聚类中心。这个方法的缺点在于对于离群点、异常值抗干扰能力比较弱，且需要设置的参数较多（一般需要3个）。M.S.Premkumar等人[5]采用了四分位数的概念来确定初始聚类中心。首先采用特征选择的方法选取数据有意义的属性。然后将将属性的值按照顺序排列，以分成两类为例，将数据集的上四分位点和下四分位点作为初始聚类中心，计算所有样本点到到这两个聚类中心的距离，进行分类;接下来更新聚类中心，将每类所有样本点的均值作为新的聚类中心，直到类簇不再发生变化。这个方法不足之处是当数据集比较大时，花费时间会比较长。C.Lasheng等人[6]首先是采用最大一最小准则算法初步确定初始聚类中心，然后通过FLANT（快速最近邻搜索库）将聚类中心偏移到尽可能地靠近实际的聚类中心。最大一最小准则算法是首先随机选取一个点作为第一个聚类中心，选取距离这个点最远的点作为第二个聚类中心，然后计算每个点到这两个聚类中心的距离，选取较小的距离加入到集合V中，在集合V中选取距离最远的点作为下一个聚类中心，依次类推，直到最大最小距离不大于θ·D1，2（C1，2为第一个和第二个聚类中心的距离）。FLANT是一个在高维空间中快速搜索k个最近邻居的库。使用FLANT找到聚类中心的k近邻，计算中心点即为新的聚类中心。2.2距离和相似性度量龙源期刊网算法使用欧几里得距离来度量相似度。陈磊磊[7]采用了欧式距离、平方欧式距离、曼哈顿距离、余弦距离、谷本距离分别作为相似度度量对文本数据进行处理，实验结果显示余弦距离、谷本距离者在文本聚类中的表现更优。不同的测度距离作为相似性度量对聚类结果会产生不同的影响，对于不同类型的数据也应采用不同的距离函数作为相似度度量。