资源描述：
《改进的k_均值聚类算法在社团划分中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2009年青海师范大学学报(自然科学版)2009第2期JournalofQinghaiNormalUniversity(NaturalScience)No.2改进的K2均值聚类算法在社团划分中的应用王小红(青海师范大学计算机系,青海西宁810008)摘要:为了快速准确地寻找大规模复杂网络的社团结构,文中基于K2均值聚类算法的思想,提出了寻找初始聚类中心的新方法.该算法应用于社会网络分析中的一个经典问题———Zachary网络,获得了满意的结果.关键词:复杂网络;度;距离;社团结构中图分类号:N94;TP393文献标识码:A文章编号:1001-7542
2、(2009)02-0022-031引言[1-4]近几年来,复杂网络研究受到越来越多的关注,并渗透到从自然科学到工程科学甚至社会科学的多个领域.复杂网络可以用来描述人与人之间的社会关系,物种之间的捕食关系,计算机之间的网络[3]联接,科研文章的相互引用,电影演员间的相互合作关系以及网页间的链接关系等等.随着对复杂网络的深入研究以及实验,人们发现许多网络都具有一个共同性质———社团结构.社团结构是指在网络中,整个网络是由若干个“群(group)”或“团(cluster)”构成的,每个群内部各节点之间的连接相对非常[1]紧密,但是各个群之间的连接相对来说却
3、比较稀疏.社团结构的研究内容之一是对社团结构的划分,动态聚类方法是一种普遍采用的方法.聚类(clustering)是把一组个体按照类似性归成若干类别,即“物以类聚”,目的是使得属于同一类别的个体之间的相似度尽可能大,而不同类别的个体之间的相似度尽可能小.我们可以在一定条件下,按照样本间的相似性把集合划分成若干个子集.当用距离来表示两个样本间的相似度时,这样做的结果就把特征空间划分成若干个区域,每一个区域相当于一个类别.一些常用的距离度量都可以作为这种相似性度量,我们之所以常常用距离来表示样本间的相似度,是因为从经验上看,凡是同一类的样本,其特征向量应
4、该是相互靠近的,而不同类的样本其特征向量之间的距离[2]要大得多.这种对数据集进行聚类的方法,即动态聚类方法.2算法实现K均值聚类算法是一种基于样本间相似性度量的间接聚类方法,属于非监督学习方法.此算法以k为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,而且簇间的相似度较低.相似度的计算根据一个簇中对象的平均值(被看作簇的质心)来进行.此算法首先随机选择k个对象,每个对象代表一个聚类的质心.对于其余的每一个对象,根据该对象与各聚类质心之间的距离,把它分配到与之最类似的聚类中.重复上述过程,直到n个对象分配完毕.211改进的K2均值聚类算法本文
5、提出的改进的K2均值聚类算法有两个创新点.第一,在选择聚类中心时,采用了节点度比较选择法.第二,在分类过程中,运用了贪心算法的思想,根据最短路径来分类,从而使繁琐的社团结构中的分类得到了简化.这两处改进,使庞大的社团结构在划分过程中变得非常简单.21111代表点选择的改进收稿日期:2008-04-09作者简介:王小红(1982—),女(汉族),陕西宝鸡人,助教.第2期王小红:改进的K2均值聚类算法在社团划分中的应用23为了要得到最优结果,首先要对顶点集进行初始划分(分类),一般的做法是先选择一些代表点作为聚类的核心,然后把其余的点按某种方法分到各类中
6、去.关于代表点的选择,K均值聚类算法有以下几种方法:1)凭经验选择代表点2)将全部数据随机地分成k类,计算每类重心3)用“密度”法选择代表点4)用前k个样本点作为代表点[2]5)从(k21)聚类划分问题的解中产生k聚类划分问题的代表点在改进的K均值聚类算法中,关于代表点的选择,本文采用了节点度(degree)比较选择法.在社团结构中,我们把对象抽象为节点,对象与对象之间的联系可以抽象成连边,这样复杂的网络结构就抽象成了图.在这个图中,我们计算出每一个节点的度,然后将前K个度最大的节点找出来,这就是我们要找的聚类中心代表点.21112利用贪心算法实现初
7、始分类选定代表点in(n=1,2,3⋯⋯k)后,就要进行初始分类了.在这里,我们采用贪心算法,选择代表点以外的任意一个节点j,依次求出这个节点与k个代表点(i1,i2,,⋯,ik)之间的距离d(G,in,j),即连接这两个节点的最短路径长度.找到与节点j距离最短的一个代表点,把节点j归入该类中即可.同理,把其余节点一一归入距离自己最近的代表点中,这样我们就完成了社团的划分.21113改进的K2均值聚类算法的实现输入:聚类个数k,以及包含n(n∈N)个节点对象的数据库.输出:满足最小距离的k个社团结构.处理流程:1)计算集合N中每一个节点的度;2)从集
8、合N中选择前k个度最大的节点作为初始代表点,并且把这k个节点从N中删去;3)从N中任意选取一个节点j,计算d
