|
职称论文发表 | 职称论文发表 专业提供:发表论文、论文发表、毕业论文、职称论... | |
住在汉口网 | 住在汉口网是一个专业提供汉口房产信息、车辆服务、生活服务、招... | |
职称论文网 | 职称论文网提供:发表论文、论文发表、毕业论文、职称论等服务。 | |
|
摘 要:K-means算法是聚类算法中最经典的划分算法之一,它对初值的依赖性很强,聚类结果随初始聚类中心选择的不同而波动很大。提出了一种改进的K-means算法,运用Kruskal算法生成聚类对象的最小生成树(MST),按权值从大到小删去K-1条边,得到的K个连通子图中对象的均值作为初始聚类中心进行聚类。由仿真实验表明,K-means算法较传统算法有更好的聚类效果和准确性。
关键词:聚类;K-means算法;MST
随着数据挖掘技术研究的不断成熟,作为其主要算法之一的聚类算法也越来越得到人们的关注,有关聚类算法的研究也已经取得了丰硕的成果。根据对象间的相似性度量和聚类评价准则等的不同,聚类方法一般包括:基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法。此外还有模糊聚类方法、核聚类方法,谱聚类方法等新发展的聚类方法。K-均值(K-means)聚类法是典型的划分方法,具有简单、快速的优点。然而这种算法对初始聚类中心的选择很敏感,初值选取的不同往往导致聚类结果差异很大,当初始聚类中心选择不当时,算法极易陷入局部极小点。近年来人们提出了多种改进和优化的方法,例如PaulS.Bradley等提出的基于采样的初始类簇中心算法。
Moh’dB.Al-Daoud和Stuart A.Roberts提出的基于划分的密度估计法,Kaufman提出的通过数据点的局部密度来估算初始类簇中心,周海岩等提出的基于图论的连通分支来进行初始聚类中心选取的K-means算法,步媛媛提出的基于欧几里德距离确定相隔最远的两个数据点之间的距离,将数据集均分为k个段,进而寻求聚类中心的方法,李卫平提出的基于贪心算法对初始聚类中心进行选取的k-means算法,苏锦旗等提出的基于划分的K-均值初始聚类中心优化算法。笔者基于图论中的Kruskal算法对聚类中心的选取进行了改进,提出了一种改进的K-means算法,并通过仿真实验,证实该算法改善了传统K-means算法对初值选取的依赖性,提高了聚类结果的稳定性和准确性。
1 K-means算法
1.1 K-means算法的基本原理
假定需要聚类的对象共有n个,K-means算法的目的是把n个样本对象分为K个簇,使得簇内的样本对象有较高的相似度,而簇间的样本对象相似度很低。具体思路如下:①从n个数据对象任意选择k个对象作为初始聚类中心;②根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;③重新计算每个(有变化)聚类的均值(中心对象);④循环②~③步骤直到每个聚类不再发生变化为止。
1.2 K-means算法的流程图(见图1)
1.3 K-means算法的缺点
K-means算法有两个缺点:①对于不同初始聚类中心的选取可能导致不同的聚类结果;②该算法是基于目标函数的寻优算法,通常采用梯度法求解极值,算法很容易陷入局部极值。本文针对第一个缺点对K-menas算法进行改进,提出一种基于图论中Kruskal算法寻找初始聚类中心的算法。
2 改进的K-means算法
2.1 Kruskal算法
设无向连通图G=(V,E),令G的最小生成树为T=(U,H),其初始状态为U=V,H=?覷,这样T中各顶点各自构成一个连通分支,然后按照边的权值由小到大的顺序,依次选择边集E中的各条边,若被选择的边的两个顶点属于T的两个不同的连通分支,则将此边加入到H中去,同时把两个连通分支连接成一个连通分支;若被选择的两个节点属于同一个连通分支,则舍去此边,以免造成回路,如此下去,当T中的连通分支个数为1时,此连通分支为G的一棵最小生成树(MST)。
2.2 改进K-means算法的思想
对于给定的数据集,笔者的任务是对X中的数据对象进行聚类。首先定义数据对象之间的距离,笔者采用欧几里德距离,将X中任意两个对象之间的距离作为权值赋予连接这两个对象的边,于是得到一个无向赋权图G(X)。
利用Kruskal算法求出此无向赋权图G(X)的最小生成树(MST),按权值从大到小删除最小生成树中的K-1条边,得到K个连通子图,计算这K个连通子图中数据对象的平均值作为初始的聚类中心,然后用原始的K-means算法做聚类分析。
2.3 改进K-means算法的流程图(见图2)
3 仿真实验及结果分析
3.1 实验环境
Windows XP操作系统,MATLAB7.1编程语言。
3.2 实验数据
随机生成50个二维数据对象,其数据分布见图3。K为聚类数目,进行聚类分析前输入。
3.3 结果分析
经传统K-means算法聚类后(K=4),结果分布见图4;经改进K-means算法聚类后(K=4),结果分布见图5。
将随机生成的50个二维数据对象根据分类数的不同分别用传统K-means算法和本文提出的改进算法进行5次聚类实验,目标函数值见表1。
由图4、图5可知,改进的K-means算法改善了聚类分析的效果,整体分布比较均匀。由表1可知,K-means算法随机选取初值,每次试验得到的目标函数值都不一样,结果波动很大。而改进的K-means算法利用Kruskal算法已经确定初始中心,聚类结果稳定,实验证明该算法有效解决了传统K-means算法对初始聚类中心敏感的缺点。同时改进算法得到的目标函数值比传统K-means算法的平均目标函数值小,符合聚类算法使聚类准则函数收敛到最小的要求。
4 结语
传统K-means聚类算法的聚类结果取决于初始聚类中心的选择,本文基于此,利用图论中的Kruskal算法寻找最小树(MST)取得初始聚类中心,对K-means算法进行改进。通过仿真实验,分析得出该算法成功解决了传统K-means算法对初始聚类中心敏感的问题,并且改进后的算法在聚类准确性和稳定性方面优于传统的K-means算法。
参考文献
5 周海岩,白晓林. 基于图的K-均值聚类法中初始聚类中心选择[J]. 计算机测量与控制,2010(9)
6 步媛媛,关中仁.基于K-Means聚类算法的研究[J].广西南民族大学学报,2009(1)
7 李卫平. 对k-means聚类算法的改进研究[J]. 中国西部科技,2010(24)
8 苏锦旗,薛惠锋,詹海亮.基于划分的K-均值初始聚类中心优化算法[J]. 微电子学与计算机,2009(1) 职称论文发表网http://www.issncn.com
职称论文发表网http://www.issncn.com
|
|
|
|