K—means算法研究综述

2014-11-05 13:49吴进宝
电子技术与软件工程 2014年18期
关键词:语义聚类向量

吴进宝

摘 要

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.

作者单位

北京航空航天大学软件学院 北京市 100083endprint

猜你喜欢
语义聚类向量
向量的分解
聚焦“向量与三角”创新题
语言与语义
基于DBSACN聚类算法的XML文档聚类
基于高斯混合聚类的阵列干涉SAR三维成像
“上”与“下”语义的不对称性及其认知阐释
向量垂直在解析几何中的应用
向量五种“变身” 玩转圆锥曲线
一种层次初始的聚类个数自适应的聚类方法研究
认知范畴模糊与语义模糊