一种更有效的K—means聚类算法

一种更有效的K—means聚类算法 一种更有效的K—means聚类算法 计算机系统应用2009年第8期 一 种更有效的K—means聚类算法? AMoreEffectiveK——MeansClusteringAlgorithm 单玉双邢长征(辽宁工程技术大学电子与信息工程学院辽宁葫芦岛125105) 摘要:一个好的聚类算法不仅要考虑"同类内尽可能的相似,不同类间尽可能的相异",而且也要考虑算法 的时间复杂度.针对K—means算法依赖于初始聚类中心而影响聚类结果,提出了一种基于样本分布 选取初始聚类中心的方法;针对K—means算法中每次调整聚类中心后指定聚类所需要的大量的距离 计算,提出了三角不等式原理避免冗余计算的方法.将两种方法结合进行实验,结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明新的方法更 加有效,不仅较原算法有良好的聚类划分,而且加快了原算法的运行速度. 关键词:聚类算法时间复杂度样本分布冗余计算聚类划分 K—means算法是一种最常用的基于划分的聚类 算法,该算法目前主要存在两个问题:算法对初始聚 类中心敏感,从不同的初始聚类中心出发,得到的聚 类结果也不一样,并且一般不会得到全局最优解;算 法在每次调整了中心点之后,需要大量的距离计算确 定新的聚类,其中的许多计算是冗余的. 1引言 1.1文章安排 本文第2节介绍原K—means算法.第3节给出 初始中心选择的优化.第4节给出收敛速度的优化. 第5节给出一种更有效的K—means聚类算法.第6 节给出结论以及未来工作. 1.1.1基本介绍 聚类分析是数据挖掘中的一个非常活跃的研究领 域,也是一种重要的数据分析技术.聚类分析也已经 广泛地应用到诸多领域中,包括模式识别,数据分析, 图像处理以及市场研究等【1】.然而,面对大规模的, 高维的数据,如何建立有效的聚类算法是当今的一个 研究热点.对聚类算法的进一步优化研究不仅有助于 算法理论的完善,更有助于算法的推广和应用. 为了实现对数据对象的聚类,人们提出了很多种 不同的算法.K—means算法是一种最常用的基于划分 的聚类算法,该算法主要存在两个问题:算法对初始 ?收稿时间:2008-12-08 96研究开发ResearchandDevelopment 聚类中心敏感,从不同的初始聚类中心出发,得到的 聚类结果也不一样,并且一般不会得到全局最优解; 算法在每次调整了中心点之后,需要大量的距离计算 确定新的聚类,其中的许多计算是冗余的.本文针对 这两个问题对原K—means算法进行改进,提出了一 种更有效的K—means聚类算法,不仅较原算法有良 好的聚类划分,而且加快了原算法的运行速度. 2K—means算法 2.1K—means算法 K—means算法如下I2】: 输入:聚类个数k,以及包含n个数据对象的数 据库. 输出:满足方差最小标准的k个聚类. 处理 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 : 1)从n个数据对象任意选择k个对象作为初始聚 类中心: 2)循环3到4直到每个聚类不再发生变化为止; 3)根据每个聚类对象的均值(中心对象),计算每 个对象与这些中心对象的距离,并根据最小距离重新 对相应对象进行划分; 4)重新计算每个(有变化)聚类的的平均值(中心 对象); K—means算法的工作过程说明如下:首先从n 2009年第8期计算机系统应用 个数据对象任意选择k个对象作为初始聚类中心;而 对于所剩下其它对象,则根据它们与这些聚类中心的 相似度(距离),分别将它们分配给与其最相似的(聚类 中心所代表的)聚类:然后再计算每个所获新聚类的聚 类中心(该聚类中所有对象的均值);不断重复这一过程 直到标准测度函数开始收敛为止.一般采用均方差作 为标准测度函数,具体如公式1: = ??P—mil 其中,E为数据库中所有对象的均方差之和;P代表对 象的空间中的一个点;mi为聚类Ci的均值(p和Ci都 是多维的).K—means算法的时间复杂度为O(nkt), n为对象的个数:k为聚类个数;而t为循环次数. K—means算法常常终于局部最优. 2.2K—means算法存在的两个问题 I)在K—means算法中,初始聚类中心的选择对 聚类结果有较大的影响,一旦初始值选择的不好,不 但无法得到有效的聚类结果,而且会增加迭代的次数, 影响收敛速度l3j.所以需要对算法的初始中心的选择 进行优化. 2)从K—means算法框架可以看出,该算法需要 不断地进行样本分类调整,并不断地计算调整后的新 的聚类中心,使算法的时间开销是非常大的.所以需 要对算法的时间复杂度进行分析,改进,提高算法应 用效率. 下文从上述两个方面对K—means算法进行优化. 3初始中心选择的优化 3.1基本概念 为了便于说明问题,给出如下基本概念: 定义1.数据对象=,X2,…,)和_y=Yl,Y2,…,Yp) 之间的距离为f41: d(x,)=?(一:)+(:一Y2):+..?+(一Ye): 定义2.一个数据对象X和一个数据对象集合V 之间的距离,定义为这个数据对象与这个数据对象集 合中所有数据对象当中最近的距离: d(x,)=min((,),?V) 定义3.两个对象集合S和V之间的距离,定义 为两个集合S和V中最近的两个数据对象X和Y之间 的距离: d(S,V)=rain(d(,),?S,Y?VJ 3.2样本分布优化初始中心选择 设数据对象集合U有n个数据对象,要将其聚为 k类,m的初值为1,(1?m?k).则算法描述如下: 输入:聚类个数k包含n个数据对象的数据样本 集: 输出:k个初始聚类中心 处理流程: 1)计算任意两个数据对象问的距离d(x,y),找到集合U中距离最近的两个数据对象,形成集合Am, 并从集合U中删除这两个对象; 2)在U中找到距离集合Am最近的数据对象, 将其加入集合Am,并从集合U中删除该对象; 3)重复2直到集合中的数据对象个数大于等于 俚n/k,(O<?1): 4)如果m<k,则m—m+1,再从集合U中找到 距离最近的两个数据对象,形成新的集合Am,并从 集合U中删除这两个数据对象,返回2执行; 5)将最终形成的k个集合中的数据对象分别进 行算术平均,从而形成k个聚类中心. 4收敛速度优化 4.1基本概念 为了便于说明,给出如下基本概念: 定义4.假设存在数据集X(xl,x2,…,x),若X中 存在划分,使得:【J()(七<),其中sj成为其中的 一 个聚类. 定义5.假设C为所有已聚类中心的集合,当 Vx?.3c?C,使得d(x,c)=mind(x,C),那么c为向 量x的聚类中心. 定理1.任一个三角行都有两边之和大于第三边, 两边之差小于第三边Is】.欧式距离满足三角不等式特 性,将它扩展到多维的欧几里得空间.欧几里得空间 中任意3个向量x,b和C满足:d(b,c)+d(×,b)? d(x,c),d(b,C)一d(x,b)?d(x,c). 推论1.设X代表一个点,b和C代表两个中心 点.如果2d(x,b)?d(b,c),那么d(x.b)?d(x,c). 证明:由于假设有2d(x,b)?d(b,c),同时在不 等式两边减去d(x,b),则有:2d(x,b)一d(x,b)? d(b,c)-d(x,b),即d(x,b)?d(b,c)一d(x,b);又由于 定理1:d(b,c)一d(x,b)?d(x,c),因此,我们得到 d(x,b)?d(x,c):所以,如果2d(x,b)?d(b,c),那么 ResearchandDevelopment研究开发97 计算机系统应用2009年第8期 d(x,b)?d(x,c). 根据推论1可以减少冗余的距离计算,应用如下: 当在迭代过程中计算将点X分配到中心点b还是C时, 如果已知d(x,b)?d(x,c)时,此时再计算X和C的距 离已无实际意义,因为存在距离该点较近的中心点b. 同样,若已知某一个点X距离某一个中心点b最近, 也没必要再计算X与b的距离.为减少距离计算次数, 我们设定一个上界和下界函数用来约束某点到各个中 心点的距离,使得迭代计算时减少距离次数,提高运 算速度. 4.2三角不等式原理避免冗余计算 对于每个数据点x和中心c,置下界约束 l(x,c)=0.对于每个点计算X到其中心点距离,将× 分配给最近中心点C,定义c(×)为服务于X的中心点. 在计算X到中心点距离时,可利用推论1避免冗余计 算.每当d(x,c)被计算时,置l(x,c)=d(×,C),同时求 出上界约束u(x)=mind(x,c). 处理流程如下: 1)对所有的中心C和C',计算d(c,c'o对所有 的中心c,计算s(c)=mincd(c.c'o 2)识别所有满足u(x)?s(c(×))的数据向量. 3)对所有剩下的同时满足条件C?c(x);u(x)> I(x,C):2u(×)>d(c(×),c)的数据点X和中心C: a.如果r(x)=true,那么计算d(c(x),×)并且置 r(x)=false.否贝lJd(c(×),x)=u(×). b.如果d(c(×),×)>l(x,c)或者d(c(×),×)> d(c(×),c)/2,那么计算d(x,c),如果d(x,c)<d(×,c(×)), 那么置c(×)=C. 4)为每一个中心C,让re(c)是以C为中心的所有 数据点的平均值. 5)为每一个数据点X和中心C,置l(x.c)=max {I(x,c)-d(c,m(c)),O}. 6)为每个数据点×,置u(x)=u(x)+d(m(c(x)), c(×)),r(x)=true. 7)将每个中心点c以m(c)替换. 在步骤3)对于任何X和C,每当d(x,c)被计算时, 它的下界约束被更新通过置l(x.c)=d(x,c).同样,只 要c(x)改变或者d(x,c(×))被计算,上界约束u(x)就被 更新.在3)a步骤中,如果r(×)为真,那么u(×)是过 期的,即可d(x,c(x))?u(x).否则,没必要计算 d(x.c(×)).步骤3)b重复核对步骤3)中的条件,为了 尽可能避免计算d(x,c).而该算法能有效地减少距离 98研究开发ResearchandDevelopment 计算次数的基本原因是,在每次循环的开始,对于许 多数据点X和中心C来说,上界约束u(×)和下界约束 l(x,c)是相当紧凑的.如果在一次循环的开始这些约束 是紧的,上界约束在下一次循环的开始仍然是紧的, 因为许多中心只是稍稍改变了一下,因此,约束的改 变也是轻微的. 5一种更有效的K—means聚类算法 将上述两种算法相结合得出一种更有效的 K—means聚类算法,处理流程如下: 输入:聚类个数k,以及包含n个数据对象的数 据库. 输出:满足方差最小标准的k个聚类. 处理流程: 1)计算任意两个数据对象间的距离d(x,Y),找到 集合U中距离最近的两个数据对象,形成集合Am, 并从集合U中删除这两个对象: 2)在U中找到距离集合Am最近的数据对象, 将其加入集合Am,并从集合U中删除该对象; 3)重复2直到集合中的数据对象个数大于等于 n/k,(1<d?1); 4)如果m<k.则m+_-m+1,再从集合U中找到 距离最近的两个数据对象,形成新的集合Am,并从 集合U中删除这两个数据对象,返回2执行: S)将最终形成的k个集合中的数据对象分别进 行算术平均,从而形成k个聚类中心. 6)循环7到14直到每个聚类不再发生变化为 止: 7)对于每个数据点x和中心c,置下界约束 I(x,c)=O.将X归为与它最近的中心c(x),(c(×)为服 务于X的中心点). 8)对所有的中心C和C',计算d(c,c'o对所有 的中心c,计算s(c)=mincd(c,C'). 9)识别所有满足u(x)?s(c(×))的数据向量. 10)对所有剩下的同时满足条件c?c(x);u(×)> I(x.C);2u(×)>d(c(×),c)的数据点X和中心C: a.如果r(x)=true,那么计算d(c(×),×)并且置 r(x)=false.否贝Id(c(×),x)=u(x). b.如果d(c(×),x)>I(x,c)或者d(c(×),×)>d(c(×), c)/2,那么计算d(x,c),如果d(x,c)<d(×,c(x)),那 么置c(×)=C. 11)为每一个中心C,让re(c)是以C为中心的所 2009年第8期计算机系统应用 有数据点的平均值. 12)为每一个数据点×和中心C,置I(x,c)=max {I(x,c)-d(c,m(c)),O}. 13)为每个数据点X,置:u(×)=u(×)+d(m(c(x)), c(x)),r(x)=true. 14)将每个中心点C以m(c)替换. 对改进后的K—means算法的要求: 1)原K—means算法能聚类的数据集,改进的 K—means算法也能被应用: 2)由于初始中心已经选定,所以在k值固定的情 况下,改进的K—means算法只有一个稳定的划分结 果,而且聚类的精度有所提高 3)改进的K—means算法比原算法运行的速度 快: 6实验结果 为评价算法有效性,采用matlab编写算法,机 器配置为Pentium4CPU,3.2GHz,IGB内存,80GB 硬盘.选用UCI中3个数据集来测试该算法的有效性, 这3个数据集的描述如表1所示.由于原算法为随机 算法,所以采用运算20次该算法后所求的平均聚类 值和最小聚类值与传统K—means算法所求结果相对 应的值进行对比用来判断新算法的有效性,如表2所 示.表3则根据每次迭代过程中,由于点的重新分配 而进行的距离个数计算的平均值以及平均运算时间用 来对比两个算法的运算时间. 注:新算法改进值公式=(1一新算法值/原算法 值)100% 表1选用数据集说明 根据测试结果我们可以得出结果如表2和表3: 通过表2和表3可以看出,新算法与传统算法 相比,无论从聚类的精度还是从运算时间上都得到了 较大提高,取得了较为令人满意的结果.当数据集的 空间维数较大时如Spam数据集,本算法取得更佳的 效果. 表2算法的聚类值对比 平均聚类值最小震类值 数据集埴 传统算法新算法改进传统算法新算法改进传统算法新算法改进传统算法新算法 改进 数据集七值 7结论 新的算法对于数据集的空间维数较大情况时,无论 从聚类的质量上还是运算效率上都具有非常大的提高. 本文结合传统K—means算法求解过程,分别从 初始点选取,收敛过程加速等方面提出一种新的有效 的改进方法.实验表明本算法能够获得较好的划分结 果.本算法结构简单,易于实现.文中初始中心优化 过程的仅值的选取有待进一步研究. 参考, l朱明.数据挖掘.合肥:中国科学技术大学出版社, 2002:138—139. 2谭斯坦巴赫.范明,范宏建译.数据挖掘导论.北京:人 民邮电出版社.2006:182一l83. 3李听,郑宇,江芳泽.用改进RPCL算法提取聚类的最 佳数目.上海大学,1999,5(5):409—4l3. 4唐立新,王梦光.用遗传算法改进聚类分析中的k平 均算法.数理统计与应用概率,1997,6(4):45—46. 5陈小云,王平.基于三角不等式原理的TTSAS聚类加 速算法.兰州大学,2006,32(17):l一2. ResearchandDevelopment研究开发99