您好, 访客   登录/注册

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算法对于稀疏数据的处理能力。大家都知道,随着大型互联网公司的发展,以及商品数量的增多,数据对象稀疏问题对聚类过程影响很大,现在已有的处理数据稀疏的技术,比如平均、平滑等,笔者不是很满意。我们可以假设数据对象的属性就好比一个人在不同成长阶段的性格,没必要刻意塑造,而在于它自己丰富。
  参考文献
  [1] Meng Jianliang, Shang Hai kun,Bian Ling. The application on intrusion detection based on K-means cluster algorithm [C].International Forum on InformationTechnology and Applications,2009:150-152.
  [2]孙士保,秦克云.改进的k-Means聚类算法研究[J].计算机工程,2007(07):200-202.
  [3]Dunn JC.A fuzzy relative of the isodata process and itsuse in detecting compact well-separated clusters [J].Journal of Cybernetics,1973(3):32-57.
  [4]Mao J,Jain A K.A self-organizing network for hyper-ellipsoidal clustering.IEEE Transactions on neural net-works,1996(7):16-29.
  作者单位
  北京航空航天大学软件学院 北京市 100083
转载注明来源:https://www.xzbu.com/1/view-6275193.htm