职称论文发表 发表论文
职称论文 发表论文 合作流程 联系方式 论文发表
职称论文发表 会员登录 用户名: 密码: 我要注册
职称论文发表网   首页   经济论文 |法学论文 |理工科论文 |管理学论文 |计算机论文 |文史论文 |医学论文 |教育论文 |艺术论文 |社会学论文 |政治论文 |试题 |应用文 |论文投稿 |职称评定 |教案 |论文关键词 |电子商务 |体育论文 |学术机构 |发表论文 |教育资讯 |医学资讯 |物联网论文 |中国论文网 | 职称论文
职称论文 本站论文搜索
职称论文 设为首页 职称论文发表网 收藏本站 职称论文发表 联系我们
职称论文  首页-->理工科论文-->数学论文-->文章正文
一种改进的K-means算法

作者 :李 卓 君更新时间:2012-10-31

职称论文发表
职称论文发表 专业提供:发表论文、论文发表、毕业论文、职称论...
住在汉口网
住在汉口网是一个专业提供汉口房产信息、车辆服务、生活服务、招...
职称论文网
职称论文网提供:发表论文、论文发表、毕业论文、职称论等服务。
摘 要: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

1
论文首页】【设为主页】【加入收藏】【打印本文】【回到顶部
最新上传
 中英校际交流,校园足球添...
 《原地单手肩上投篮》教学...
 七年级《篮球运球》教学设...
 职校教师的角色定位
 我对因材施教的看法
 物理教学中德育渗透
 中职德育课堂的应用表现性...
 肺结核治疗综述
 肺结核治疗方案
 肺结核治疗问题
 肺结核50例临床治疗
 肺结核病人护理
 农村城镇化探析
 篮球运动员身体素质训练
 国防经济研究
职称论文
本站推荐
 中英校际交流,校园足球添...
 《原地单手肩上投篮》教学...
 七年级《篮球运球》教学设...
 我对因材施教的看法
 中职德育课堂的应用表现性...
 肺结核治疗方案
 肺结核治疗问题
 肺结核50例临床治疗
 肺结核病人护理
 农村城镇化探析
 篮球运动员身体素质训练
 国防经济研究
 公共危机应急保障机制建设
 科研院所物业管理社会化
 油田企业信息系统审计
职称论文发表
所有资料均源于网上的共享资源及期刊共享,请特别注意勿做其他非法用途。
如有侵犯您的版权或其他有损您利益的行为,请联系指出,我们会立即进行改正或删除有关内容!
  网站介绍 联系我们 广告服务 网站导航 投诉建议 服务承诺 人才招聘 版权声明  
  •   投稿邮箱:83041061@qq.com    服务热线:027-62220402 手机: 18907137973
    点击及可直接咨询
    联系地址:武汉市江汉区新华下路江花苑13楼   电子地图
  • Copyright (C) 2007-2009 http://www.issncn.com/ All Rights Reserved.. 鄂ICP备:09016318号
    技术支持:腾浪科技    法律顾问:廖泉冰律师