每天三分钟，知晓天下事，视频、语音、文字综合版任您挑！微信搜索fgzadmin关注或点击标题下方可以快速关注。
原创不易，认可价值，动手指点并转发，就是最好的支持与肯定。淘宝特约店址：http://goldengame.
深夜十点，陪你读书。
慢工出细活
由于中、美、俄三国自2008年后基本上长期上演“三国杀”（昨天文章《原创丨中美俄世纪三国杀，谁是百年长跑冠军
其实这是个有奖活动贴。n其实这是个有奖活动贴。n其实这是个有奖活动贴。
思考者正在阅读原创丨三次世界大战亚洲开打，美国推演靠谱吗？原创丨央行连出两大招，有何深意？微历史丨张学良为啥
美国总统奥巴马日在接受媒体采访时表示，2011年对利比亚局势的干涉，是其总统生涯中做出的最
我们都知道，美国软实力很厉害，在过去很多年都一直掌控者国际话语权，他们可以提着民主、自由、人权的大棒满世界乱
思考者正在阅读原创丨重大变革，我们的世界都将逃不过被TA重塑！原创丨中美黄岩岛较量，谁是最后赢家？原创丨你射您的位置：
基于Kruskal算法进行初值选取的改进的K-means算法
基于Kruskal算法进行初值选取的改进的K-means算法
Improved K-means Algorithm of Choosing the Clustering Center Based on Kruskal Algorithm
发布时间：　　浏览量：740　　收藏数：0　　评论数：
北京邮电大学理学院；
K-means算法是聚类算法中最经典的划分算法之一，它对初值的依赖性很强，聚类结果随初始聚类中心选择的不同而波动很大。本文基于图论中著名的Kruskal算法提出了一种改进的K-means算法，该算法首先运用Kruskal算法生成聚类对象的最小生成树（MST），然后按权值从大到小删去K-1条边，将得到的K个连通子图中对象的均值作为初始聚类中心进行聚类。仿真实验表明，该算法较传统k-means算法有更好的聚类效果和准确性。
聚类；K-means算法；Kruskal算法；MST
REN Qian，
ZHUO Xinjian*
School of Science,Beijing University of Post and Communication；
Abstract：
K-means algorithm is one of the most classic partition algorithms in clustering algorithms. The result obtained by K-means algorithm varies with the choice of the initial clustering center. Motivated by this, an improved K-means algorithm is proposed based on the Kruskal algorithm, which is famous in graph theory. The procedure of this algorithm is shown as follows: Firstly, the minimum spanning tree (MST) of the clustered objects is obtained by using Kruskal algorithm. Then K-1 edges are deleted based on weights in a descending order. At last, the average value of the objects contained by the k-connected graph resulting from last two steps is regarded as the initial clustering center to cluster. Simulation exeriment shows that the improved K-means algorithm has a better clustering effect and higher efficiency than the traditional one.
Keywords：
CK-means AKruskal AMST
PDF全文下载：
&&&&（220）
作者简介：
任倩, （1986-），女，硕士研究生，数据挖掘
通信联系人：
卓新建, （1971-），男，副教授，网络编码，数据挖掘
【收录情况】
中国科技论文在线：任倩，卓新建.&基于Kruskal算法进行初值选取的改进的K-means算法[EB/OL].北京：中国科技论文在线&
[].http://www./releasepaper/content/.
发表期刊：
首发论文搜索
&> 信息科学与系统科学
&> 地球科学
&> 畜牧、兽医科学
&> 基础医学
&> 临床医学
&> 预防医学与卫生学
&> 军事医学与特种医学
&> 中医学与中药学
&> 工程与技术科学基础学科
&> 测绘科学技术
&> 材料科学
&> 矿山工程技术
&> 冶金工程技术
&> 机械工程
&> 动力与电气工程
&> 能源科学技术
&> 核科学技术
&> 电子、通信与自动控制技术
&> 计算机科学技术
&> 化学工程
&> 纺织科学技术
&> 食品科学技术
&> 土木建筑工程
&> 水利工程
&> 交通运输工程
&> 航空航天科学技术
&> 环境科学技术
&> 安全科学技术
&> 图书馆、情报与文献学
&> 体育科学
尊敬的作者，欢迎您在本站投稿：
注：请投稿作者直接在本站注册并登录提交文章，
任何个人或机构宣称代理在本站投稿均为侵权行为
本学科今日推荐
本文作者合作关系
本文相关论文
&&&&&&&&&&&&&&
中国科技论文在线
&|&&|&&|&&|&&|&nbsp
计算机科学技术基础学科
计算机系统结构
计算机软件
计算机工程
计算机应用
计算机科学技术其他学科
基于Kruskal算法进行初值选取的改进的K-means算法
&&收藏本文
&&推荐本文给好友
&&订阅本文所在学科
&&分享到我的圈子
多个邮箱请用逗号“，”隔开
分享到我的圈子一种K-means聚类算法的改进与应用
2015年电子技术应用第1期
灵，朱韵攸
　　摘 &要： 算法是基于距离作为相似性度量的，传统的K-means算法存在难以确定中心值个数、受噪声及孤立点影响较大的缺点。对此，利用类间相异度与类内相异度改进初始值K，以尽量减少人工干预；同时计算数据库中每一点与剩余点的距离和距离均和，将两者的大小比较作为识别孤立点和噪声点的依据，从而删除孤立点，减少对数据聚类划分的影响。最后将改进后的K-means算法应用于系统并进行仿真实验，结果表明，基于改进的K-means算法的入侵检测系统一定程度上降低了误报率及误检率，提高了检测的准确率。　　关键词： ；聚类算法；K-means；入侵检测0 引言　　聚类分析是将海量的数据划分为有意义或者有用的组（簇）。在同一簇中的数据相似度较高，不同的簇中数据差别比较大。聚类分析主要基于距离进行分析，它是一种无监视的学习训练方式。　　K-means聚类算法是基于划分的经典算法，但存在难以确定初始聚类中心值、受噪声及孤立点影响较大的缺点[1]。基于此，很多学者研究提出了不同的改进K-means聚类算法的方法。参考文献[2]把相互距离最远的K个高密度区域的点作为初始聚类中心点；参考文献[3]利用密度指针初始化聚类中心，从而从真实聚类中心中选取数据库初始化聚类中心；参考文献[4]利用密度和最近邻的思想来寻找初始聚类中心；参考文献[5]基于最优划分初始聚类中心，该算法首先对数据样本进行划分，根据划分样本的分布特点确定初始聚类中心；参考文献[6]利用伪随机数产生初始聚类中心，但聚类数据庞大时，聚类效果不容乐观。参考文献[7]通过对样本数据进行阈值分层快速确定K-means算法的聚类数搜索范围及其上限，利用新的聚类有效性指标评价聚类后类内与类间的相似性程度，从而在聚类数搜索范围内获得最佳聚类数。1 聚类分析的相似性度量和准则函数　　1.1 相似性度量　　聚类分析是依据对象两两之间的相似(或差异)程度来划分类的，而这相似程度通常是用距离来衡量的[8]。最广泛使用的距离计算公式是欧氏距离：　　　　其中，i=(xi1，xi2，…，xip)，j=(xj1，xj2，…，xjp)。　　1.2 准则函数　　聚类结果的质量可以由聚类准则函数来判断，若准则函数选的好，质量就会高；反之，质量达不到要求时，则须反复运行聚类过程[9]。一般的聚类准则函数有以下3种：(1)误差平方和准则；(2)加权平均平方距离和准则；(3)加权类间距离和准则。2 K-means聚类算法分析　　2.1 K-means算法过程　　K-means聚类的算法流程如下：　　输入：含有n个对象的数据集X={xi|xi∈Rd，i=1，2，…，n}，聚类的个数k。　　输出：k个类W1，W2，…，Wk。　　(1)从数据集X中随机选取k个初始聚类中心c1，c2，…，ck。　　(2)依据初始聚类中心c1，c2，…，ck对数据集进行划分，划分根据以下原则：若dij(xi，cj)&dim(xi，cm)，其中dij(xi，cj)是xi与cj的欧式距离，m=1，2，…，k，j=1，2，…，k，j≠m，i=1，2，…，n，则将xi划分到类cj。　　(3)依据公式，ni为以聚类Ci为中心数据对象的个数，重新计算类的质心。　　　(5)输出聚类结果。　　K-means聚类算法的流程如图1所示。　　2.2 K-means算法缺点　　(1)K-means算法需要首先设定K值，而算法运算中K是一个敏感值，不同的K值可能会造成不同的运算结果。　　(2)对于一些噪声和孤立的数据较为敏感。　　(3)簇的平均值只有被定义才能使用，这不利于处理一些有特殊属性的数据。　　2.3 K-means算法的改进　　(1)改进初始值K，尽量减少人工干预　　利用类间相异度与类内相异度来确定最终的K值，具体分3步来实现：首先，选取数据集合的中间点即所有数据集合的平均值，利用欧几里得距离计算公式，计算出距离中间点最远距离的对象N1，再计算出与N1距离最远的对象N2，筛选出初始聚类中心。其次计算剩余数据对象与数据中心集合间的距离，取最小距离D，计算聚类中心之间的距离，找出最小距离C，如果D&C，则将对象放入到最小距离的聚合中，否则将其纳入初始聚合中心，生成新的聚合中心，后面的数据依次与聚合中心间最小距离与D对比，循环所有数据，最终形成聚类中心集。最后，采用类间相异度与类内相异度来确定最终的聚类个数K值。　　类内的相异程度DOC：　　　　类间相异度DAC：　　　　其中，nc表示聚类的数目，mi表示类Cj中心，xkj表示Cj中的第k个数据对象的第j个属性值，d(mi，mj)表示Ci与Cj间的欧几里得距离，表示类中第j个属性值。　　改进后的计算方法如下：　　输入：含有n个对象的数据集X={xi|xi∈Rd，i=1，2，…，n}。　　输出：k个类W1，W2，…，Wk。　　①对聚类中心进行初始化，获得3个聚类中心。根据公式计算出第1个聚类中心m0，再根据欧几里得距离计算出与m0最远的数据对象作为第2个聚类中心m1，最后计算出与m1距离最远的数据对象当成第3个聚类中心m2。　　②根据欧几里得公式计算数据集和聚类中心的距离，归类所有数据，重新计算聚类中心。　　③计算剩余数据对象与聚类中心的最小距离D及聚类中心之间的最小距离C， 计算出此时的类内相异度DOC_old 和此时的类间相异度DAC_old。　　④如果D&C，则把这个数据对象作为新的聚类中心，并且计算新的类内相异度DOC_new和新的类间相异度DAC_new，运行步骤⑤；否则转到步骤⑥。　　⑤如果DOC_new&DOC_old且DAC_new&DAC_old则产生新类，转到步骤②重复步骤②～⑤；否则恢复状态，执行步骤⑥。　　⑥取下一个类Wi，如果没有新的类，则转到步骤⑦；否则反复执行步骤②～⑤。　　⑦输出聚类结果。　　(2)对噪声和孤立点处理能力的改进　　有时孤立点或噪声具有入侵特征，容易干扰 K-means算法的聚类结果，这里改进原始算法来消弱噪声和孤立点的影响。对于数据集中的所有点i，计算出每一点与剩余点的距离和Si，同时计算出距离均和H，当Si&H时，则点i被当做孤立点处理。其中n为样本数据，d为数据维数。计算如下：　　　　算法描述如下：　　①输入数据集，利用上述公式计算每一Si和H；　　②对于每一点i，如果Si&H，则将i作为孤立点；　　③删除孤立点，获得新的数据集。3 改进算法在入侵检测系统中的应用及仿真分析　　针对于入侵检测系统的缺陷,给出了基于改进算法的入侵检测模型流程，如图2所示。　　系统检测的对象是网络日志中的数据。先做标准化处理，再进行聚类分析。通过筛选孤立点和改进聚类中心从而提高聚类的准确性。接着进入决策报警分析系统。根据聚类的结果甄别具有攻击特征的记录，一旦发现潜在威胁马上启动报警系统，阻止相关攻击的进一步操作，并报告网络管理者，与此同时挖掘其他的潜在特征，为以后判断攻击提供必要的依据。若没有发现攻击行为则继续监视网络动态。对网络日志文件进行标准化的同时，也将其存入历史数据库中。并进行标准化处理和特征挖掘，进而数据匹配分类，构建成分类器。在分类器的反复训练下可从这些记录中挖掘出正常和非正常行为，并存入到规则库中，作为今后判断入侵行为的决策机构。　　表1列出的是20条网络连接记录的特征数据。其中，count表示目标主机与当前连接相同的次数；SY_error表示SYN错误连接所占的百分数；same_srv表示目标端口相同连接的百分数；Dif_srv表示目标端口不同连接的百分数；Srv_count表示目标主机与当前连接相同的次数；Srv_serror表示SYN连接错误的百分数；Rv_dif_host表示目标端口不同连接的百分数[10]。本文主要对三维数组（count，Srv_serror，Srv_count）进行分析。三组特征数据的空间分布图如图3所示。　　这个三维数组基本显示了数据是否具有攻击特征。通过分析这3个参数可以区分攻击行为、异常行为和正常行为。当目标端口与当前连接相同的次数大于15次，并且主机出现错误SYN连接的百分数大于85％，目标端口与当前连接相同次数大于25次时认为是攻击行为；若目标端口与当前连接相同的次数大于6次，并且主机出现错误SYN连接的百分数大于75％，目标端口与当前连接相同次数大于6次时认为是异常行为；其他则认为是正常行为。　　采用传统的 K-means 算法聚类分析3组数据后将20条数据信息分为3类：记录3为攻击行为(即图4中圆形区域)；记录4，5，6，12，13，19，20为异常行为(即图4中椭圆区域)；其余的记录为正常行为(即图4中矩形区域)。根据上述3种行为的特征，可以将攻击、异常和正常行为区分开来。传统K-means 算法却不能进一步分析异常行为是否有攻击特征。传统K-means 算法对实验数据聚类分析的空间结果如图4所示。　　改进算法会分离出记录3（孤立点），并判断其为攻击行为，如图5中圆形区域。改进的K-means 算法将剩余的19条记录聚类为三部分，记录4，5，6，12，13，19，20为异常行为(如图5中椭圆区域)，其中5，19接近于攻击行为(如图5中正方形区域)。其余的记录为正常行为。改进算法有效地提高了检测的准确率。改进的K-means 算法对实验数据聚类分析的空间结果如图5所示。4 总结　　本文简单介绍了K-means算法，详细阐述了对算法的改进，针对聚类算法中心个数难以确定的问题，本文改进了传统K-means聚类算法中心个数确定的方法，提出了一种新的中心个数确定算法。同时对传统K-means算法进行进一步的改进，以减少数据中噪声点和孤立点对聚类精度的影响。并将传统K-means算法和改进的K-means算法应用于入侵检测系统中。实验结果发现，基于改进的K-means算法的入侵检测系统具有更好的入侵检测效果，改进算法不仅降低了关键参数的敏感性，提高了区分精度，还在一定程度上提高了网络入侵检测的检测率，降低了误检率。参考文献　　[1] 曹永春，蔡正琦，邵亚斌.基于K-means的改进人工蜂群聚类算法[J]．计算机应用，)：204-207.　　[2] 傅德胜，周辰.基于密度的改进K均值算法及实现[J].计算机应用，)：432-434．　　[3] 牛琨，张舒博，陈俊亮．融合网格密度的聚类中心初始化方案[J]．北京邮电大学学报，)：6-10．　　[4] 张文明，吴江，袁小蛟.基于密度和最近邻的K-means文本聚类算法[J].计算机应用，)：.　　[5] 崔斌，卢阳.基于不确定数据的查询处理综述[J]．计算机应用，)：.　　[6] KOLEN J F，HNTCHESON T.Redneing the time complexityof the fuzzy c-means algorithm[J]．IEEE Transactions on Fuzzy Systems，)：263-267.　　[7] 王勇，唐靖，饶勤菲，等.高效率的K-means最佳聚类数确定算法[J]．计算机应用，)：.　　[8] 吕明磊，刘东梅，曾智勇.基于改进的K-means算法的图像检索算法[J]．计算机应用，)：195-198.　　[9] 雷小锋，谢昆青，林帆，等.一种基于K-means局部最优性的高效聚类算法[J]．软件学报，)：.　　[10] 高红艳，刘飞.基于局部相似性的K-means谱聚类算法[J]．小型微型计算机系统，)：.
继续阅读>>
热门关键词K-means算法的改进_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
K-means算法的改进
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用2下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢