K―means算法研究综述.docVIP

K―means算法研究综述 　　摘 要 　　K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。本文主要阐述了K-means的基本算法流程，总结评述了改进的k-means算法的研究现状，以及和经典算法的比较。最后总结了k-means算法存在的一些问题，并指出了改进的方向。 　　【关键词】K-Means聚类算法 初始聚类中心 　　K-means聚类算法是由J.B.MacQueen在1967年提出的，之后迅速应用在不同的学科和领域。虽然K-means聚类算法被提出有50多年了，但目前还是被应用最广泛的算法之一。其容易实施、简单、高效的 特征，以及解决无数成功案例，仍然使其依旧是被研究的热点。 　　本人主要是在研究K-Means基本算法的基础上，总结阐述了改进的K-Means算法。基于向量语义相似度的K-means算法，针对传统的K-Means算法的不足，提出通过向量语义相似度的计算自动确定初始聚类中心，在聚类过程中，达到语义相似度阈值的网页才使用K-Means算法进行聚类；基于初始聚类中心优化的K-means算法，通过数据之间距离，计算密度参数，保留高密度区域，删除低密度区域，找出数据的真实分布。 　　1 K-Means算法简介 　　K-means算法，它是一种基于距离远近的聚类算法，同时也是一种无监督学习算法，对以后的算法改进具有很大的影响。该算法的优点是简单易行，容易理解，时间复杂性接近线性，对大规模数据挖掘具有高效性和可伸缩性，在科研以及实际应用中有着很重要的作用。 　　按照K-means的基本思想，可以将K-means聚类算法描述如下： 　　步骤： 　　输入：数据集中的n个数据对象，聚类个数为k； 　　输出：满足误差平方和准则函数最小的K个聚类； 　　算法流程： 　　（1）从n个数据对象中随机选取k个对象作为初始聚类中心； 　　（2）计算数据集中各个数据对象与聚类中心的距离，并根据最小距离对数据对象进行类群划分； 　　（3）在形成的子类群中，重新计算每个聚类中所包含的数据对象的平均值作为新的聚类中心； 　　（4）循环流程（2）到（3）直到前后两次迭代得到的每个类群的中心点不再高于某个阈值为止。 　　2 K-Means算法改进 　　2.1 基于向量语义相似度的K-means算法 　　针对传统的K-Means算法对网页处理的不足，以及其在文本聚类中存在的局限性，提出了基于网页向量语义相似度的改进K-Means算法。新算法通过向量语义相似度的计算确定初始聚类中心，在聚类过程中，达到语义相似度阈值的网页才使用K-Means算法进行聚类。新算法很好地克服了传统K-Means算法随机选取聚类中心以及无法处理语义信息的问题，提高了聚类的质量。 　　2.2 基于初始聚类中心优化的K-means算法 　　传统的算法对初始聚类中心特别敏感，聚类结果随不同的初始输入而波动，基于初始聚类中心优化的K-means算法通过计算对象相互之间的距离，产生密度参数，很好的排除了低密度区域的脏数据，从而也优化了传统K-Means算法对脏数据的敏感性。 　　3 K-means算法的其他改进 　　在K-means聚类算法中，每个数据点都被唯一的划分到一个类别中，这被称为硬聚类算法，它不易处理聚类不是致密而是壳型的情形。这对这一情况，Dunn等人于1973年提出了模糊K-means聚类算法。Kashima等人于2008年使用L1距离，最终聚类中心是每一类的中位向量。对于一维数据集X={x1，x2，x3，…，xi，…，xn}而言，中位数M比均值对异常数据有较强的抗干扰性，聚类结果受数据中异常值的影响较小。Mao Jain[4]于1996年提出使用Mahalanobis距离，但计算代价太大。在应用中，Linde等于1980年提出使用Itakura-Saito距离。Banerjee等人2004年提出，如果使用Bregman差异作为距离度量，有许多突出优点，如克服局部最优、类别之间的线性分离、线性时间复杂度等。 　　4 与经典K-means算法的比较 　　基于向量语义相似度的K-means算法首先计算网易语义之间的相似度，只有达到一定阈值时，才进行聚类，新算法克服了传统K-Means算法无法处理语义信息的问题，提高了聚类的质量。基于初始聚类中心优化的K-means算法通过对象相互之间的距离，产生密度参数，很好的排出了低密度区域的脏数据，从而也优化了传统K-Means算法对脏数据的敏感性。 　　5 结束语 　　对于K-means算法，笔者比较感兴趣的是未来K-means算法对于稀疏数据的处理能力。大家