（计算机软件与理论专业论文）基于蚁群算法的网络社区聚类算法研究.pdf

基于蚁群算法的网络社区聚类算法研究 摘要 论文题目：基于蚁群算法的网络社区聚类算法研究 专业：计算机软件与理论 硕士生：王继娜 指导老师：印鉴教授 摘要 网络社区聚类是指通过聚类技术找到网络中团体内节点关联密切，团体间节 点关联松散的结构，该问题的研究已经成为数据挖掘领域研究的一个热点，它与 计算机科学中的图分割和图聚类有着密切的关系。通过聚类技术可以从网络社区 中挖掘出隐藏的有价值的信息，目前网络社区聚类算法已广泛应用于科技、经济、 商业、生物等各个领域。 本文在分析现有网络社区聚类算法研究现状基础上，提出了一种基于蚁群优 化算法的网络社区聚类算法a n t c c ( a n tb a s e dc o m m u n i t yc l u s t e r i n g ) 。a n t c c 算法用节点间拥有的公共邻居数目来描述节点之间的距离以及在此之上定义了 聚类内核心顶点，利用蚁群优化算法来搜索网络社区中的聚类，并且找出每个聚 类中的核心顶点。蚁群优化算法中的每只蚂蚁根据概率转移函数产生一个解及用 网络模块性q 来衡量找到的网络社区聚类质量；信息素局部和全局更新策略将 蚂蚁的聚类结果评价反馈给信息素矩阵，使得并行工作的蚂蚁间能够更好的进行 信息交流；蚁群优化算法的搜索策略是从较好的几个解中变异出新模式的解，避 免局部最优。实验运行于合成数据集和基准数据集上，结果表明该算法相比现有 的网络社区聚类算法具有较高的准确度，达到了网络社区聚类和核心节点发现的 目的。 关键字：蚁群，网络社区发现，聚类，核心节点 基于蚁群算法的网络社区聚类算法研究 a b s t r a c t t i t l e ：a n tc o l o n ya l g o r i t h mb a s e dc o m m u n i t yc l u s t e r i n gr e s e a r c h m a j o r c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：w a n g j i n a s u p e r v i s o r ：y i n j i a n a b s t r a c t c o m m u n i t yc l u s t e r i n gm e a n st h ev e r t i c e si nn e t w o r k sa r eo f t e nf o u n dt oc l u s t e r i n t ot i g h t l y - k n i tg r o u p sw i t hah i g hd e n s i t yo fw i t i n - g r o u pe d g e sa n dal o w e rd e n s i t y o fb e t w e e n g r o u pe d g e s t h er e s e a r c ho nd e t e c t i o no fc o m m u n i t ys t r u c t u r eb e c o m e s t h eh o tt o p i ci nt h ea r e ao fd a t am i n i n g i ti sc l o s e l yr e l a t e dt ot h ec o m p u t e rs c i e n c e p r o b l e mo fg r a p hp a r t i t i o n i n ga n dg r a p hc l u s t e r i n g m a n yh i d d e na n dv a l u a b l e i n f o r m a t i o nc a l lb em i n i n gf r o mt h ec o m m u n i t ys t r u c t u r eb yc l u s t e r i n g c u r r e n t l y , c o m m u n i t yc l u s t e r i n ga l g o r i t h m sh a v eb e e na p p l i e df o rm a n yf i e l d ss u c ha ss c i e n c e a n dt e c h n o l o g y , e c o n o m y , b u s i n e s s ，b i o l o g ya n ds oo n b a s e do nt h ea n a l y s e so ft h er e s e a r c ha c t u a l i t yo ft h ee x i s t i n gc o m m u n i t y c l u s t e r i n ga l g o r i t h m s ， w eu s et h ei d e ao fa n tc o l o n yo p t i m i z a t i o np r o p o s e sa c o m m u n i t yc l u s t e r i n ga l g o r i t h ma n t c c ( a n t b a s e dc o m m u n i t yc l u s t e r i n g ) a n t c c d e t e c tt h ec o m m u n i t yc l u s t e rs t r u c t u r eb yt h ea n tc o l o n ya l g o r i t h m ，a n df i n dt h ec o r e m e m b e r si ne a c hc l u s t e r t h ev e r t e xd i s t a n c ew a sd e s c r i b e db yt h ec o m m o nn e i g h b o r s o ft h ev e r t e xa n dt h ec o r em e m b e r s d e f i n i t i o nw a sf o l l o w e d e a c ha n tf o u n dap r o p e r s o l u t i o no ft h ep r o b l e ma c c o r d i n gt ot h es t a t et r a n s i t i o nr u l ea n dm e a s u r et h e c o m m u n i t yc l u s t e r i n gq u a l i t yb yt h em o d u l a r i t yq ；t h el o c a la n dg l o b a lp h e r o m o n e u p d a t es t r a t e g yr e f l e c tt h ee v a l u a t i o no ft h ea n tc l u s t e r i n gt ot h ep h e r o m o n em a t r i x ，s o t h ep a r a l l e lw o r k i n ga n tc a nc o m m u n i c a t ew i t he a c ho t h e rb e t t e r t h el o c a ls e a r c h i n g s t r a t e g yg e t ss o m ev a r i a t i o nn e wp a t t e rf r o mt h eb e t t e rs o l u t i o n ，s o a st oa v o i dt h e l o c a lo p t i m u m t h ee x p e r i m e n tr u no nt h ec o m p u t e rg e n e r a t e dd a t a s e ta n dt h e b e n c h m a r kr e a ld a t a s e t ；t h er e s u l t ss h o wt h a tt h ea l g o r i t h mp r o v i d e dab e t t e rp r e c i s i o n a n da c h i e v et h ea i mo fn e t w o r kc o m m u n i t yd e t e c t i o na n dc o r em e m b e r sd i s c o v e r i n g k e yw o r d s ：a n tc o l o n y , c o m m u n i t yd e t e c t i o n ，c l u s t e r i n g ，c o r em e m b e r s i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者鹕：工鲫 同期：岬年箩月加同 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 靴敝储擗：上q r 期：抄叩年歹月刀同 导师签名： 同期：如叩年歹月幻同 基于蚁群算法的网络社区聚类算法研究 第1 章引言 1 1 研究背景 第1 章引言 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取出 可信、新颖、有效并能被人理解的模式的高级处理过程，也被称为数据库中的知 识发现【l 】。数据挖掘是- - f - j 交叉学科，与数据库、机器学习、人工智能、模式识 别及统计学等学科密切相关，主要可以对复杂的任务进行描述或预测，描述任务 的主要目的是发现庞大数据中隐含的某种模式，包括相关性、聚类和异常等，预 测任务的主要目的是根据一些已知变量得出未知变量，主要通过分类和回归等。 聚类分析是数据挖掘领域的一个核心技术，其源于物以类聚的思想，根据物体的 特征对物体进行聚类或分类。 电信网络、计算机网络、运输网和万维网等复杂网络中包含了很多有价值的 信息，但是在复杂庞大的网络里，人们如何从海量的数据中挖掘出感兴趣的信 息? 基于这样的问题，很多学者已经采用统计知识发现了网络拓扑中一些隐含的 性质，如网络的幂律的度分布、顶点的高聚团性、六度分隔原理、小世界现象等。 为了更好的从网络结构中挖掘出隐含的、有价值的、可理解的知识，将数据挖掘 的方法( 尤其是聚类分析技术) 应用于网络社区分析越来越受到人们的关注，因此 网络社区聚类的研究已经成为数据挖掘领域研究的一个新方向。 网络社区的研究有着很长的历史，它与计算机科学中的图分割或图聚类的研 究有密切关系【2 3 】。在许多网络中都存在这样的团体关系结构：团体内部的节点 之间有大量的连接，而团体之间的节点相对只有少量连接。2 0 0 2 年n e w m a n 根 据顶点的这种高聚团现象提出了复杂网络的社区结构的概念【4 1 。社区就是指网络 中节点的集合，社区内的节点之间具有紧密的连接，而社区之间则为松散的连接， 它体现了复杂系统的层次和模块结构。从数据挖掘的观点来看，网络社区是由图 表示的异构多关系的数据集，节点对应对象，边对应表示对象间联系或相互作用 的链接，节点和边都有属性。与传统的数据挖掘研究的对象不同，在网络社区分 析中个体之间由于存在着相互的联系，故不满足独立的假设，所以对网络社区的 基于蚊群算法的网络社区聚茄算法研究 第1 章引言 研究将更侧重于关系结构的挖掘。发现网络中的社区结构有助于我们更加有效的 理解网络结构和分析网络特性，挖掘出隐藏的信息，并可进一步对网络进行社会 关系挖掘、信息传播和扩散的涌现性分析、网络鲁棒性及稳定性判定、风险控制 等，而网络的核心性节点则在社区结构中起着至关重要的作用吼 b 图i - 1 网络社区示例。( a ) 为w c b 网络社区结构，每个节点代袭一个阿页，每个边代表阿 页问的链接。一个杜区即具有共同兴趣话题的网页集合；( b ) 为科学家合作网络，每个节点 代表作者，边代表相互台作、论文引用、致谢等关系，一个社区即对同一主题的相关论文感 兴趣的作者集合i ( c ) 为电话呼叫网络；( d ) 为e - m a i l 交互网络。 许多现实模型都可以建模为网络，社会网络中的社区代表根据兴趣或背景而 形成真实的社会团体，如：万维网可以看成由大量网站社区组成，同一个社区内 部的各个网站讨论的是一些共同兴趣的话题哪】，如图1 1 ( a ) ：科学家的合著网络 和引用网络中的杜区代表对同一主题的相关论文感兴趣的团体j ，如图1 1 ( b ) ： 电话交互网络图中的社区结构代表经常通电话的一个团体，如图1 - 1 ( c ) ；还有其 他网络社区，如公司工作组内的e - m a i l 信息交互网络、新闻组、聊天室、朋友 联系等l l 】：类似的，在生物网络中还有流行病学网络、细胞与新陈代谢网络、基 因网络，计算机科学中的网络拓扑，p 2 p 网络，w e b 结构图，还有其他的网络如： 2 删燃豢0 基于蚁群算法的网络社区聚类算法研究第1 章引言 电力网格、计算机病毒传播网、消费者网络和协同过滤网络等。 网络社区结构的研究越来越多，也衍生了很多其他的相关分支，其中一些基 本问题仍然值得我们深入地研究。在各种复杂网络中，如何找出具有较高相似度 的社区结构，并用定量分析的方法寻找网络中哪个节点( 边) 最重要，或者某个节 点相对于其他节点的重要程度，是网络社区研究中的一个基本问题。另外还有一 些问题值得我们思考：如何度量社区聚类的质量；对于多关系的网络，如何评定 各种关系指标，并找到符合实际的社区聚类；对于起到两个社区间关联作用的 h u b 节点，将其划分到哪个聚类中，是否允许其同时属于两个不同的聚类等。 1 2 研究现状及意义 人们对网络社区感兴趣的原因何在? 感兴趣于刻画网络的特征和挖掘它们 从而更多地了解它们的结构的意义又何在? 因为结构总是能影响功能的。现实社 会中，有许多科技、经济、商业、生物等网络实例，这些复杂网络大部分都表现 出社会网络的特征。人们希望通过对网络社区结构的分析，发现网络数据中隐藏 的知识，挖掘出潜在的规律，进而发现事物的本质特征，利用这些指导商业、经 济、人口管理等方面的决策。如社会网络的拓扑结构使得传染病通过有结构的人 群蔓延，发现社区结构可以有效进行隔离和预防；在罪犯关系网络中发现以犯罪 头目为首的犯罪团伙，可以快速准确的侦破案件，所以网络社区结构研究可以辅 助信息传播和扩散的涌现性分析；在电力网络及p 2 p 网络中，可能存在网络的瓶 颈，这些网络瓶颈很可能是连接两个或多个社区的关联节点，所以网络社区结构 研究结果可以进一步为网络鲁棒性及稳定性判定提供参考；在营销网络中，对网 络社区中的核心成员或有影响力的成员进行推销，可以达到风险控制等目的。而 且随着互联网的发展，社区分析对社交网络、博客搜索、论坛挖掘等具有重要作 用。总之，社会网络分析能够发现网络拓扑结构的特征与网络的行为趋势之间的 关系，从而帮助人们更有效地利用信息或其他资源，降低人类生活、商业生产、 自然规划等领域遇到的问题的复杂性，并对其做出更好的判断、管理和决策支持。 传统的用于网络社区聚类的试探性算法主要包括：基于图划分的 k e n l _ i g h a l l l i n 算澍9 1 ，谱聚类算法【1 0 , 1 1 , 1 2 】，基于相似度的层次聚类算法( 凝聚、分 裂算法) ，但是这些算法在解决现实问题时往往时间复杂性过高或算法精度不够， 3 基于蚁群算法的网络社区聚类算法研究第l 章引言 所以不断有新的网络社区聚类算法被提出。2 0 0 2 年g i r v a n 和n e w m a n 通过边介数 的定义，提出了g n 算法【4 】，并通过网络模块性来度量网络社区聚类质量，很多 学者对g n 算法进行改进，如文献 1 3 】中提出的算法与g n 算法效果差不多，但是 速度却有了很大的改善；n e w m a n 等人提出的f n 算法通过优化网络模块性q 的方 式在很大程度上提高了算法的时间效率，但算法精度却有待改掣1 4 】。很多学者已 经在优化q 值的方法中做了研究，w h i t e 和s m y t h 提出了一种谱方法w s 【l5 1 ，该方 法将优化q 值问题转化为一个特征分解问题，为了确定社区数目k ，算法执行多 次，并选择最高q 值对应的髟怍为最终的社区数目；g u i m e r a 提出了通过模拟退火 算法来实现网络聚类的功能【1 6 j ，但模拟退火算法的时间消耗是参数依赖的； n e w m a n 提出了采用分解得到的特征向量来求解，算法的时间复杂性为 o ( n 2 1 0 9 n ) 17 】；c l a u s e t 等人进一步针对大的社会网络时间复杂度很大的情况，提 出一种新的算法c n m 1 8 1 ，贪婪的合并使得模块度增益最大的社区或节点，在大 的稀疏社会网络中，算法时间复杂度j ；j o ( n l 0 9 2 n ) ，接近于线性时间，c n m 算法 是目前解决大规模网络社区问题的非常重要的聚类算法。 前期的网络社区分析算法很多都是基于静态的网络，忽略了引起网络状态变 化的重要因素，造成了信息的缺失。这两年里，x i a o w e ix u 等人受到基于密度的 聚类算法的启发，提出了社区挖掘算法s c a n 1 9 】，该算法能够在网络社区中检验 出社区、孤立点以及关联两个或多个社区但不单独属于任何聚类的h u b 节点，它 是基于结构的相似性来进行聚类的。n a nd u 等人提出c o m t e c t o r 算法【2 0 1 ， c o m t e c t o r 舅：法能够有效的在一个大的社会网络中检测出社区，并且可以发现重 叠的社区结构，这个算法不需要知道社区的个数。p e d r o 等人通过自上而下、组 合、递进的方法构建w e b 社区【2 1 1 ，该方法是先选择一个小的但重要的社区源， 然后对它进行扩展形成一个社区。z h o u 等人提出一个在社会网络中挖掘动态社 区的算法 2 2 1 ，该算法先根据某一时刻的网络挖掘出社区，由该时刻的静态结构 和之前成员的结构关系来挖掘出动态的社区。v a s i l e i o s 等人提出一个社区聚类的 算法s t e e m e r 2 3 1 ，它能够在网络社区中挖掘出凝聚的社区结构，还能在动态的社 会网络结构中预测社区变化。通过扩展g i r v a n 和n e w m a n 算法，s t e v eg r e g o r y 提 出一个分级聚类的划分算法【2 4 1 ，该算法允许节点被重复聚类，也就是说一个节点 可以属于多个社区，更加有实际的意义。l e it a n g 等人利用时间信息提出一个方 法【2 5 1 ，它能在动态和异构的社会网络当中进行社区发现。 4 基于蚁群算法的网络社区聚类算法研究 第l 章引言 在国内，杨楠等人提出将基于流的社区特征和马尔可夫图形聚类算法的簇结 合起来寻找隐含社区的方法【2 6 】，将镜像或近似镜像页面的删除放在图形聚类之后， 大大减少了比较的代价。沈华伟等人提出一种映射方法，把单部网络变换成二部 图网络，针对得到的二部图网络，在信息论的框架下，提出了一种基于信息瓶颈 的社区发现方法【2 7 1 。可见社会网络中的社区结构挖掘已经成为当今一个非常具有 挑战性和前景性的研究领域。 1 3 本文主要工作 从上面的分析可以看出，网络社区聚类算法的研究有着重要的意义，并且引 起国内外学者的关注。本文在分析已有国内外网络社区聚类算法研究现状基础 上，对基于优化思想的蚁群算法做了较为深入的分析和研究，提出了一种新的网 络社区聚类算法a n t c c ( a n tb a s e dc o m m u n i t yc l u s t e r i n g ) ，通过蚁群算法来解 决网络社区的聚类问题，目的是找出网络中的聚类，并且发现每个聚类中的核心 项点。本文的选题主要基于以下几点考虑： 1 通过贪婪策略和局部优化等方式获得较大的网络模块性q 的社区挖掘算 法是社区聚类的重要方式，其主要基于两种思想：a ) 基于目标函数值的优化， 即给定适应度函数并采用贪婪策略求解，如c n m 算法b ) 通过层次或其他聚类 算法对网络社区进行聚类，通过模块性来衡量聚类质量，并找出使得聚类质量最 好的划分方式，如g n 算法。本文将提出一种基于目标函数值优化的网络社区聚 类算法，因为贪婪策略可能存在局部最优，而无法达到全局最优的情况，蚁群算 法在解决复杂问题时表现出良好的优化性能，所以通过蚁群优化算法来解决网络 社区聚类问题在理论上是具有可行性的。 2 g u i m e r a 等学者已经提出了通过模拟退火算法来解决网络社区聚类问题， 并且获得了较好的聚类质量。c l a r a 提出了通过遗传算法来发现网络中的社区结 构，同样作为一种优化算法的蚁群算法具有良好的优化性能，其适用范围也是非 常广泛的，但并没有学者尝试通过蚁群算法来解决网络社区聚类问题，所以本文 将对此做深入的研究。本文将网络社区聚类问题转化为网络模块性的优化问题， 提出一种通过蚁群优化算法来解决网络社区聚类问题的a n t c c 算法。 基于以上考虑，本文的主要工作如下：在已有的网络社区聚类算法研究基础 5 基于蚁群算法的网络社区聚类算法研究 第l 章引言 上，本文利用蚁群算法来解决网络社区聚类问题，提出了一种基于蚁群算法的网 络社区聚类算法a n t c c ( a n tb a s e dc o m m u n i t yc l u s t e r i n g ) 。a n t c c 用节点间拥 有的公共邻居数目来描述节点之间的距离以及在此之上定义了聚类内核心顶点， 将无权网络转化为加权网络，并利用蚁群算法良好的优化性能找出社区聚类。蚁 群优化算法中的每只蚂蚁产生一个解及用网络模块性q 来衡量找到的网络社区 聚类质量；信息素更新策略将蚂蚁的聚类结果评价反馈给信息素矩阵，使得并行 工作的蚂蚁间能够更好的进行信息交流；蚁群优化算法的局部搜索策略是从较好 的几个解中变异出新模式的解，避免局部最优。实验结果表明a n t c c 算法比 f n 算法、c n m 算法及g n 算法具有更好的准确率，达到了网络社区聚类和核心 节点发现的目的。 1 4 论文的结构和组织 本文主要分为六章，其结构和相关章节的主题如下： 第一章主要介绍了网络社区的概念，数据挖掘中网络社区聚类的研究意义和 国内外研究进展情况，同时阐述了本文的研究范围和组织。 第二章主要介绍了聚类分析技术及度量准则，并详细对有代表性的网络社区 聚类算法如g n 算法，f n 算法等进行介绍和比较。 第三章主要研究了蚁群优化算法，介绍了蚁群优化算法的产生、发展及应用 的过程，以t s p 问题为基础介绍了蚁群优化算法原理、蚁群优化算法流程。 第四章是本文的重点。首先通过节点拥有的公共邻居数衡量网络社区节点的 距离并给出了核心性节点的定义，并提出了一种用蚁群优化算法来解决网络社区 聚类问题的a n t c c 算法，并详细介绍了算法的流程。 第五章是a n t c c 算法的实验部分。通过合成数据集和基准数据集的实验证 明了a n t c c 算法的有效性。 第六章对全文的内容进行了总结，并讨论了进一步的研究工作。 6 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 第2 章网络社区聚类算法概述 2 1 聚类分析技术 所谓聚类就是把以个d 维数据样本聚集到k 个类中，使得同一类中的样本 的相似性很大，不同类中的样本的相似性很小。典型的聚类过程主要包括数据( 或 称之为样本或模式) 准备、特征选择和特征提取、相似度计算、聚类( 或分组) 、对 聚类结果进行有效性评估等步骤 2 8 】。聚类过程： 1 数据预处理：包括特征标准化、剔除孤立点、降维等； 2 特征选择：从最初的特征中选择最重要的特征； 3 特征提取：通过对所选择的特征进行转换形成新的显著特征； 4 相似性度量：根据合适的特征为衡量数据点间的相似度定义一个距离函数， 进行相似度的度量； 5 聚类或分组：基于不同的方法将数据点分类，使得聚类内的相似性高，聚类 间节点的相似性低； 6 评估输出：对聚类结果的质量进行评估，评估主要有3 种：外部有效性评估、 内部有效性评估和相关性测试评估。 聚类分析作为数据挖掘领域的一个重要分支已被应用于多个方面，它可以作 为一个单独的工具以发现数据库中数据分布的一些深入信息，并且概况出每一类 的特征，集中对待定的簇集合作进一步的分析，如在商业领域其可以将客户划分 成不同的客户群，并通过购买模式刻画每个群体的特征，在生物上其可以对基因 进行分类，并获取对每组基因的固有结构和功能的认识等，聚类分析也可以作为 其他分析算法( 如分类和定性归纳算法) 的一个预处理步骤，也可将聚类结果用于 进一步的关联分析。聚类分析也可以发现数据中的孤立点，在某些特定的应用中 孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为。 2 1 1 聚类好坏的度量 任何聚类算法的结果都应该采用一种客观公正的质量评价方法来进行评价。 常用的聚类好坏的度量准则都主要有两个方面特性：聚类内部的数据点应该是紧 7 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 凑的，而聚类间的数据点应该是尽量远离的，用软件工程的思想可以将聚类概括 为：类内高内聚，类间低耦合。一般而言，聚类质量的度量准则分为外部评价法 和内部评价法两种2 9 , 3 0 】。聚类的目的是将数据对象分组形成多个簇，簇中的数据 对象的距离较小，簇间数据对象的距离较大。度量聚类分析的标准有许多，常见 的有如下几种【1 】： l 、可伸缩性 指随着数据集的扩展，算法依然能够具有较好的性能。有的算法在数据规模 较小的情况下，性能很好，但是在一个大规模数据库上进行聚类可能会产生有偏 差的结果，算法性能下降，没有良好的可伸缩性。 2 、高维性 一个数据库中的数据可能包含若干维或多个属性，在高维数据中进行聚类是 一个具有挑战性的问题，特别是当数据非常稀疏且可能高度倾斜时，很多的高维 空间聚类算法应运而生。 3 、发现任意形状的聚类的能力 许多聚类算法基于欧氏距离度量方法，能够发现一些球状的聚类。实际应用 中，数据库的聚类可能是任意形状的，如带状聚类，环状聚类，提出发现任意形 状簇的算法是很重要的。 4 、用于决定输入参数的领域知识最小化 聚类分析的结果不仅对输入参数如聚类数目、结果的支持度、置信度等很敏 感，而且对数据的输入顺序是敏感的，特别是高维数据中，要求用户输入参数不 仅加重了用户的负担，也使得聚类分析的结果会很难控制，因此应该尽量减少领 域知识。 5 、处理噪声数据的能力 噪声是一些异常数据，是和数据集中数据对象不一致的例外数据，绝大多数 现实世界中的数据都包括了一些孤立点，空缺，未知数据和错误数据。然而这些 数据可能导致错误的分析结果。 6 、基于限制条件后的聚类 r 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 实际应用中会有各种限制，聚类算法在考虑这些限制的条件下，仍具有较好 的性能表现。要找到彻底满足特定的约束、又具有良好聚类特性的数据分组是一 项具有挑战性的任务。 7 、可解释性和可用性 用户希望聚类结果是易于理解和可用的。即聚类算法应该与具体的应用背景 相结合，或对特定的聚类问题及应用，如何选择合适的聚类算法，应用目标如何 影响聚类算法的选择也是一个重要的研究课题。 2 1 2 有代表性的聚类算法 现有聚类算法多种多样，对于不同的数据集或应用背景，不同的聚类算法的 正确率和运行效率是不同的，本文将数据挖掘领域中广泛应用的主要聚类分析算 法分为以下四类【1 2 8 】：基于层次( h i e r a r c h i c a l ) 的聚类算法，基于划分( p a r t i t i o n a l ) 的聚类算法，基于密度( d e n s i t y ) 、网格( g r i d ) 的聚类算法，和其他类型的聚类算 法，如图2 1 所示。 图2 1 聚类算法分类图 层次聚类算法将数据对象组成一棵聚类的树( d e n d r o g r a m ) ，如果按自底向上 进行层次分解则称为凝聚( a g g l o m e r a t i v e ) 的层次聚类方法；如果按照自项向下进 行层次分解，则称为分裂的层次聚类。凝聚的层次聚类首先将每个对象作为一个 簇，然后逐渐合并这些簇变成较大的簇，直到所有对象都在同一个簇中，或者满 足某个终止条件。分裂的层次聚类与之相反，它首先将所有对象置于一个簇中， 9 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 然后逐渐划分成越来越小的簇，直到每个对象属于单独一个簇，或者满足某个终 止条件，如达到用户希望的聚类个数。这类方法主要包括：b i r c h 、c u r e 、r o c k 、 c h a m e l e o n 、b i n a r yp o s i t i v e 算法等。 划分方法是将给定的一个包含个数据对象的数据集划分成k 个划分，其 中每个划分表示一个簇。通常会采用一个划分准则，如距离，从而使得在同一个 簇中的对象距离较近，在不同聚类中的对象距离较远。比较经典的划分聚类算法 如k m e a n s 算法和k - m e d o i d s 算法，k m e a n s 首先从玎个数据对象随机选择k 个 对象作为初始聚类中心，剩下的对象根据它们与聚类中心的相似度或距离将其分 配到与其相似度最大的聚类中，重新计算每个新聚类的聚类中心( 聚类中所有对 象的均值) ，重复这一过程直到满足终止条件。k - m e d o i d s 算法与k - m e a n s 算法 类似，只是重新计算聚类中心时通过所有对象的中心点。其他划分算法主要有基 于图论的算法m d s c l u s t e r ，模糊聚类算法f c m 等。 基于密度的聚类算法目的是为了发现任意形状的聚类。很多算法中都使用距 离作为描述数据间相似性的准则，但对于非球状数据集，通过距离来衡量不能够 很好的找出符合要求的聚类。而通过密度来取代相似性度量可以解决该问题。这 类算法将聚类看成是数据空间中被低密度区域分割开的高密度数据的区域。常见 的基于密度的聚类算法有d b s c a n 、o p t i c s 、d e n c l u e 等。d b s c a n 算法将 高密度的区域划分为簇，并可以在有孤立点的数据库挖掘到任意形状的聚类。 d b s c a n 算法主要是根据对于某一聚类中的所有对象，在给定半径的邻域内数 据对象个数必须大于某个阈值。基于网格的聚类算法使用一个网格结构，围绕模 式组织由矩形块划分的值空间，基于块的分布信息实现模式聚类。基于网格的聚 类算法主要有g d i l c 、s g c 、g c h l 等，该类算法常常与其他方法结合，特别 是与基于密度的聚类方法相结合使用。 另外一类聚类算法包括基于生物学启发的蚁群聚类算法，该类算法是根据蚂 蚁铸造坟墓、分类尸体、以及具有分类能力等现象提出的模型，蚂蚁通过改变周 围环境来进行间接的通信，很多学者将这种通信方式称之为s t i g m e r g y ”1 ，并模 拟含有s t i g m e r g y 的人工蚂蚁的群体智能来处理数据挖掘中的聚类问题。如 d e n e u b o u r g 等人提出的基本蚁群聚类算法模型b m 3 2 1 ，用来解释蚂蚁尸体堆积成 墓地的行为；l u m e r 和f a i e t a 基于基本蚁群聚类算法b m 提出了l f 蚁群聚类算 1 0 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 法【3 3 1 ，将b m 推广应用到数据分析，使得聚类出现以下特征：簇内距离小于簇 间距离，通过物体与环境中群体的相似度和概率转移函数进行聚类；徐晓华等人 针对b m 和l f 算法在处理聚类问题时存在的一些不足，提出了一种人工蚂蚁 运动模型a m ( a n tm o v e m e n t ) 和在此模型上的一个自适应的聚类算法 a a c ( a d a p t i v e a n tc l u s t e r i n g ) 【3 4 】，体现了蚂蚁具有“物以类聚，人以群分”的智 能。蚁群算法也可以将聚类问题题转化为优化问题，对特定的问题定义一个目标 函数，并通过不断优化获得最终聚类结果，达到聚类的目的【3 5 1 。如蚁群系统 ( a c s ) 、利用模拟退火和竞技选择策略高效的发现具有明显边界的聚类的具有特 定偏好的蚁群系统( a c o d f ) 【3 6 1 、可以发现任意形状的聚类的受限蚁群优化聚类 算法( c a c o ) 3 7 】。 2 2 网络社区聚类算法 图2 - 2复杂网络社区聚类算法分类图 为了寻找网络中存在着的社区结构，人们提出了许多社区分析算法。传统的 用于网络社区发现的试探性算法主要包括：1 ) 基于优化的方法，如谱聚类算法、 基于图划分的k e r n i g h a l l l i n 算澍9 1 、基于模块性度量的f n 算法【1 4 1 及c n m 算法 【l8 】等。该类算法预先定义目标函数，并将聚类问题转化为优化问题，最优化某个 目标质量函数，从而得出网络社区聚类结构，如谱聚类方法将网络聚类问题转化 为二次型优化问题，通过计算特殊矩阵的特征向量来优化定义的割函数，但谱分 割法将网络一分为二，当网络中团体数比较多时，往往不能给出一个好的结果； 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 2 ) 启发式方法，如g i r v a n 和n e w m a n 提出的g n 算法的启发式规则是聚类问的 边介数应大于聚类内的边介数，但g n 分裂算法不能直接给出网络中团体数，而 且对于大型网络并不适用。h i t s 算法的启发式规则是如果链接到一个网页的页 面越多，该页面越具有权威性；3 ) 其他社区聚类算法，如基于相似度的随机行 走算法【3 8 】、基于连边密度的s c a n 1 9 1 算法、基于信息中心度算法【3 9 1 ，还有一些 聚类组合算法等。图2 2 为复杂网络社区聚类算法的分类图1 4 0 , 4 1 1 ，本节将介绍几 种经典的网络社区聚类算法。 2 2 1 基于边介数的启发式分裂算法 g i r v a n 和n e w m a n 于2 0 0 2 年提出了基于边介数的聚类算法g n ，并将其应 用于社会网络和生物网络的团体结构分析嗍。g n 算法的基本思想是：社区之间 所存在的少数几个连接应该是社区之间通信的瓶颈，是社区之间通信时通行流量 的必经之路。考虑网络中某种形式的通信并且寻找到最高通信流量的边，则该边 就应该是连接不同社区的通道。若将这样的边去除就应该获得了网络的最自然分 解。因此不断地从网络中移除介数( b e t w e e n n e s s ) 最大的边，从而将整个网络分解 为各个社区。 f r e e m a n 于1 9 7 9 年首次提出节点介数的概念。在图g 兰( y ，e ) 中矿代表节 点的集合，e 代表边的集合，设盯。表示从节点s 到节点t 所经过的边的数目，则 在无向图中有o r “= o r 臼。设( 力表示从节点s 到节点t 的最短路径经过节点1 ，的 数目。则节点的介数的定义如公式( 2 1 ) 所示。 c b - - e $ ，t v # t e v 掣 ( 2 - 1 ) fj ， 从节点的介数定义出发，可以引申定义边的介数，边介数定义为网络中经过 每条边的最短路径的数目。它为区分一个社团的内部边和连接社团之间的边提供 了一种有效的度量标准。在图g = ( 矿，e ) 中，设吼，表示从节点s 到节点t 所经 过的边的数目，( p ) 代表从节点s 到节点t 的最短路径经过边p e 的数目，边 e 的两个端点分别为u 、1 ，则边的介数的定义如公式( 2 2 ) 所示。 1 2 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 c b 阱朋毛脚岩 仁2 ， f 产 v f r ，踞占j ， 边的介数取决于通过它的最短路径数。网络中社区间的边与许多不同社区中 的节点相连，所以其介数大，而社区内部的边的介数相对较小，通过这种特性可 以区分社区间与社区内部的边。g n 算法的基本流程如下： 1 计算网络中所有边的边介数； 2 找到边介数最高的边并将它从网络中移除； 3 重复步骤2 ，直到每个节点就是一个社区为止或达到其他终止条件。 图2 3 连接不j 司团体的边具有大的介数 观察图2 3 所示的网络，它含有两个社区，这两个社区有边a b 相连，边 a b 具有最大的介数。如果去掉这条边，则网络分解为两个独立的社区。对于一 个待分析的网络，g n 算法通过反复计算边介数、识别簇间连接、删除簇间连接、 以自顶向下的分裂方式建立一棵层次聚类树d e n d r o g r a m 。基于分裂思想的g n 算 法，通过不断的将网络介数最高的边除去，直到网络中的每个节点都互不连通( 即 每个节点都是一个社团) ，因此可以得到一系列的网络社团划分。 g n 算法从开始执行，直到网络的每个节点都成为一个独立的社团，可以得 到许多的网络划分方式，需要附加的关于特定网络的一些信息来判断所得到的划 分是否具有实际意义，得出最好的聚类结果。为了达到这个目的，n e w m a n 等人 引入网络模块性q 来对一个划分的优劣进行定量的度量。网络划分的模块性q 的定义如下：定义一个后k 维的对称矩阵e = ( e o - ) ，其中元素表示网络中连接 1 3 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 两个不同社区的节点的边在所有边中所占的比例，这两个节点分别位于的第f 个 社区和第个社区。设矩阵中对角线的各元素之和为t r e = e i l 它给出了网络中连 接某一个社区内部各节点的边在所有边的数目中所占的比例。定义每行( 或者列) 中各元素之和为铆= e e u 它表示与第f 个社区中的节点相连的边在所有边中所占 的比例。网络模块性定义为： o = e i f 一口f 2 = t r e - i f n e w m a n 等人发现，随着g n 分解的进行，所得到网络划分的q 值也逐渐的 变化，而q 值曲线通常只有1 、2 个峰值，这些峰值位置所对应的划分通常与所 期望的结果密切相关。可以看到模块性越接近1 ，网络的社团结构就越明显。 g n 算法的最大缺陷是计算速度慢，由于边介数的计算开销为o ( m 玎) ，g n 算法的时间复杂度为o ( m 2 咒) ，其中m 为边数，n 为顶点数，不适于对大规模网 络进行分析。但g i r v a n 等人首次发现了复杂网络中普遍存在的网络社区结构， 启发其他读者对该问题进行深入研究，所以g n 算法在复杂网络聚类研究中仍占 有重要位置，g n 算法的t y l e r 改进的基本思想是利用某个节点集内的一部分节 点代替g n 算法中的所有节点来作为源节点，计算边的介数【4 2 1 。显然，当节点集 取得比较少时，它可以显著的提高计算速度，但同时也降低了计算的准确性。 2 2 2 基于模块划分的社区挖掘 如果q 值越大，代表的网络社区划分越好，为什么不简单的在所有可能划 分上优化q ，从而获得最好的划分呢? 简单的优化q 值是非常耗时的，将靠个 顶点分到k 个非空的聚类中，根据第二类s t r i l i n g 数，可能有y ：，s ，种情况， _ 五= l ” 我们知道西+ s ：2 = 2 卜1 对于( n 1 ) ，所以可能的聚类情况数是以指数级增长 的，枚举出所有可能的划分的搜索时间至少是指数级。对于现实生活中超过2 0 或3 0 个节点的网络，这个时间是不可取的。 很多学者提出了应用各种近似优化方法( 模拟退火算法，遗传算法，贪婪优 化方法等) 及谱聚类方法优化网络模块性q 的挖掘社区的方法【4 3 1 ，如表2 1 所示， 其中m 为边的数目，n 为节点的数目，k 为聚类数目，e 为使得算法收敛的迭代 次数。 1 4 基于蚁群算法的网络社区聚类算法研究第2 章网络社区聚类算法概述 表2 - 1 基于p 函数算法时间性能比较 作者文献算法时间复杂度 g i r v a na n dn e w m a n 4 g n0 ( m 2 n ) n e w m a n 1 4 f n0 ( ( m + n ) n ) o r0 ( n 2 ) n e 硼a n 1 7 n e 0 ( n 2 l o g n ) c l a u s e t ，n e w m a na n dm o o r e 1 8 c n m 0 ( n l 0 9 2 n ) w h i t ea n ds m y t h 1 5 w s0 ( n k 2 e ) e 为迭代次数 r u a na n dz h a n g 4 4 k c u t 小于w s 算法时日j 开销 g u i m e r ae ta l 1 6 s a依赖参数 2 0 0 4 年，n e w m a n 等人提出了基于局部搜索的快速复杂网络社区聚类算法 f n 算法【m 】，该方法是一种贪婪优化算法。其优化目标是极大化n e w m a n 和g i r v a n 网络社区结构的模块性度量函数一网络模块性( n e t w o r km o d u l a r i t yq ) ，q 函数定 义为聚类内实际连接数目与随机连接情况下聚类内期望连接数目之差，用来衡量 网络社区聚类结果