（应用数学专业论文）基于项点度和顶点个数的图聚类算法.pdf

l | i i ii ii ll lll l i i i ll illi y 18 9 6 0 0 2 g r a p hc l u s t e r i n ga l g o r i t h mb a s e do nt h ed e g r e ea n d t h en u m b e ro fv e r t i c e s at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i n p a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h ed e g r e eo f t y p e so fd e g r e e b y x u j i n g ( a p p l i e dm a t h e m a t i c s ) t h e s i ss u p e r v i s o r ：p r o f e s s o rw a n gd e q i a n g m a y 2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文= = 基王亟壶廑塑亟点仝数的图鐾羞篡选：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体己经公开 发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：拴盛 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密酉( 请在以上方框内打“ ) 论文作者签名：除幽 导师签名： 郴魄 日期：2 , , 0 1 4 年月谚日 中文摘要 摘要 聚类( 或分类) 是数学、计算科学、管理科学等领域的热门研究话题，并且 在诸如模式识别、数据分析、通信、生物以及商务等领域有着广泛的应用图聚 类，就是应用图理论方法对图( 顶点集) 进行分类，是数据聚类领域一种很重要 的变体与普通的数值聚类不同的是，基于图理论的聚类具有其本身的特殊性， 可以用图来表示数据集中的相似程度 一般来说，图聚类是按照图结点间所具有的关联特性对结点进行分类或标识， 其最终目标是将图中结点分组，使其组内具有紧密的关联，而组间的关联相对稀 疏本文在分析了m o u s s i a d e s 与v a k a l i ( c l u s t e r i n gd e n s eg r a p h ：aw e bs i t eg r a p h p a r a d i g m i n f o r m a t i o np r o c e s s i n ga n dm a n a g e m e n t ，2 0 1 0 ) 提出的基于内部连通比率 ( i n t e rc o n n e c t i o nr a t i o ，i c r ) 的图聚类算法( 以下简称m v i c r 聚类算法) 基础 上，进行了相应的改进，提出了一个新的聚类指标和基于新指标的聚类算法主 要工作如下： ( 1 ) 提出了一种基于i c r 的聚类策略，改进了m v i c r 聚类算法中无法将关 系相等的多个类同时归类的问题，改进后的算法使得聚类过程更加快速、聚类结 果更加清晰，较m v - i c r 算法更加合理有效 ( 2 ) 提出了一种基于类内关联顶点个数的新聚类指标( 称为类内顶点连接比 率) ，并给出了基于类内顶点连接比率的聚类算法；实例分析表明，提出的新算 法合理有效 ( 3 ) 对i c r 算法、i c r 改进算法以及i v c r 算法所适应的图类进行了比较讨 论 关键词：图聚类；聚类系数；i c r 算法；i v c r 算法 英文摘要 a b s t r a c t c l u s t e r i n g ( o rp a r t i t i o n ) i sah o tr e s e a r c hi s s u ei nm a t h e m a t i c s ，c o m p u t e rs c i e n c e ， m a n a g e m e n ts c i e n c ea n do t h e ra r e a s i t i sa l s ow i d e l ya p p l i e di nt h ef i e l d ss u c ha s p a t t e r nr e c o g n i t i o n , d a t aa n a l y s i s ， c o m m u n i c a t i o n ，b i o l o g ya n db u s i n e s s g r a p h c l u s t e r i n ga p p l i e st h eg r a p ht h e o r ym e t h o dt og r a p hc l a s s i f i c a t i o n , a n d i ti sav e r y i m p o r t a n tv a r i a n to f d a t ac l u s t e r i n g d i f f e r e n tf r o mo r d i n a r yn u m e r i c a lc l u s t e r i n g ，t h e c l u s t e r i n gb a s e do ng r a p ht h e o r yh a si t so w np a r t i c u l a r i t y , t h es i m i l a r i t yb e t w e e nd a t a o b j e c t si nd a t as e ti so f t e ne x p r e s s e db yag r a p h g e n e r a l l y , g r a p hc l u s t e r i n gd u s t e r sa r eg r o u p sw i t hah i g hd e n s i t yo fw i t h i n - g r o u p e d g e sa n dal o w e rd e n s i t yo fb e t w e e n g r o u pe d g e s i nt h i sp a p e r , w ea n a l y z et h e g r a p h - c l u s t e r i n ga l g o r i t h m sb a s e do nt h ei n t e rc o n n e c t i o nr a t i o ( m v - i c rf o rs h o r t ) p r o p o s e db ym o u s s i a d e s a n dv a k a l i ( c l u s t e r i n gd e n s eg r a p h ：aw e bs i t eg r a p h p a r a d i g m i n f o r m a t i o np r o c e s s i n ga n dm a n a g e m e n t , 2 0 10 ) ，d e v e l o p t h em v - i c r c l u s t e r i n ga l g o r i t h m ，p r o p o s e dan e wc l u s t e r i n g c o e f f i c i e n ta n dan e wc l u s t e r i n g a l g o r i t h m t h em a i nw o r k sa r ea sf o l l o w s ： ( 1 ) i tp r o p o s e sac l u s t e r i n gs t r a t e g yb a s e do ni c ra n di m p r o v e st h ep r o b l e mt h a t s e v e r a lc l u s t e r so fe q u a lr e l a t i o nc a n tb ec l a s s i f i e da tt h es a m et i m ea si ni c rc l u s t e r i n g a l g o r i t h m t h ei m p r o v e da l g o r i t h mm a k e sc l u s t e r i n gp r o c e s sq u i c k l ya n dc l u s t e r i n g r e s u l tc l e a r l y i ti sm o r er e a s o n a b l ea n de f f e c t i v et oc o m p a r e dw i t hm v - i c ra l g o r i t h m ( 2 ) i tp r o p o s e san e wc l u s t e r i n gc o e f f i c i e n tb a s e d0 1 1t h en u m b e ro fc o n n e c t i n g v e r t i c e sw i t h i nac l u s t e r ( c a l l e di n t e rv e r t e xc o n n e c t i o nr a t i o ，r v c r ) a n dp r o p o s e san e w c l u s t e r i n ga l g o r i t h mb a s e do ni v c r s o m ee x a m p l e si n d i c a t et h a tt h en e wa l g o r i t h m p r o p o s e di sr e a s o n a b l ea n de f f e c t i v e ( 3 ) i tc o m p a r e sa n ds t u d i e st h eg r a p ht y p e sa p p l i c a b l et oi c ra l g o r i t h m ，i m p r o v e d i c ra l g o r i t h ma n di v c ra l g o r i t h m k e yw o r d s ：g r a p h c l u s t e r i n g ；c l u s t e r i n gc o e f f i c i e n t ；i c ra l g o r i t h m ；i v c r a l g o r i t h m 第3 章基于i c r 的图聚类算法及其改进算法9 3 1 基于i c r 的图聚类算法9 3 2 基于m v i c r 聚类算法的实例分析1 1 3 3 改进的基于i c r 聚类算法1 7 3 4 基于i c r 的改进算法的实例分析2 l 第4 章图的i v c r 聚类算法2 7 4 1 相关概念2 7 4 2 基于i v c r 的聚类算法2 7 4 3 基于i v c r 聚类算法的实例分析2 8 4 4 算法适用图类的比较3 3 第5 章结论3 6 5 1 本文研究的主要工作3 6 5 2 待研究的问题3 6 参考文献3 7 致谢4 2 研究生履历4 3 基于顶点度和顶点个数的图聚类算法 第1 章绪论 1 1 引言 图论( g r a p ht h e o r y ) 作为应用数学的一个分支，在处理离散数学的某些问题 上是一个很强大的工具瑞士的数学家欧拉在1 7 3 6 年发表了一篇有关哥尼斯堡七 桥问题的著名论文【l 】，在论文中引出了图的概念，自此图论便成了应用数学的一 个分支【2 1 在自然界和人类社会中的大量事物以及事物之间的关系，常可用图 来描述如：物质结构、城市规划、交通运输、工作调配等等都可以用点和 线所组成的图来模拟【3 】随后，欧拉发表了一篇著名的论文依据几何位置 的解题方法，这是图论领域的第一篇论文，标志着图论的诞生 图论的产生和发展已经历了二百多年的历史，从欧拉用一笔画的方法证明 了七桥问题开始到十九世纪中叶，图论处于萌芽阶段；从十九世纪中叶到1 9 3 6 年，这期间图论问题大量出现，对图论的研究便进入到发展阶段，如1 8 4 7 年基 尔霍夫( k i r c h h o f f ) 运用图论解决了电路理论中求解联立方程问题，他引进了“树一 的概念【侧、1 8 5 2 年由一个叫法兰西斯哥斯尔的伦敦学生提出的“四色猜想是 一个至今没有得到理论证明的数学难题，但是在1 0 0 年来试图证明“四色猜想 的历史长河中发展了图论的许多方面、1 8 5 7 年由英国数学家汉密尔顿( h a m i l t o n ) 设计了一种名为周游世界的游戏，即著名的h a m i l t o n 问题、1 8 5 7 年凯莱( c a y l e y ) 在有机化学领域里发现了一族重要的图，称为树，他应用树来计算饱和氢化合物 c n h 2 n + 2 、1 8 7 8 年“图( g r a p h ) 这个词第一次出现在英国自然杂志中、1 9 3 0 年，波兰数学家库拉托夫斯基( k u l a t o w s k y ) 证明了平面图可以画在平面上、1 9 3 6 年匈牙利数学家寇尼格( k o n i g ) 出版了图论的第一部专著有限图与无限图理论， 由此图论才正式成为- f - j 独立学科f l 】图论的广泛应用，也极大地促进了它自身的 发展，图论进入了它的快速发展期；1 9 3 6 年以后进入第三阶段，图论已经发展成 一个理论与应用兼有的研究领埘0 1 除了经典图论之外，图论与代数结合形成了 代数图论，与拓扑结合形成了拓扑图论，图论的应用也渗透到许多其他学科领域， 如物理、化学、信息学、运筹学、博弈论，以及计算机网络等，特别是许多离散 第1 章绪论 性问题的出现促进了图论的大力发展，二十世纪六十年代以后，由于高速计算机 的广泛应用，使得图论在计算机和模式识别等领域具有很高的应用价值，促使和 丰富了图论的内容和应用 聚类是分析和处理数据的重要工具俗话说“物以类聚，人以群分 ，e v e r i t t 在1 9 7 4 年对于聚类给出了如下的定义：一个类簇内的实体是相似的，不同类簇的 实体是不相似的；一个类簇是测试空间中点的聚合，同一类簇的任意两个点间的 距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较 高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与 其他区域( 类簇) 相分离聚类在很多领域有着广泛的应用【7 j 5 1 ，在商务方面，聚 类能帮助市场分析人员从客户库中发现不同的客户群，并用购买模式来刻画不同 客户群的特征在生物学方面，聚类可用于推导植物和动物的基因分类，从而获 得对种群中固有结构的认识在地球观测数据库中相似地区的确定，保险单持有 者的分组，以及根据房子的类型、价值和地理位置对一个城市的房屋分组上，聚 类也发挥着巨大作用【1 6 - 2 2 1 此外，聚类还可以对w e b 上的分档进行分类，以发现 信息一般地，聚类是在未知目标数据库到底有多少类的情况下，以某种度量为 标准将所有的记录组成不同的类，或者叫做“聚类 ( c l u s t e r ) 主要的聚类方法有以下几种： ( 1 ) 划分式聚类算法( p a r t i t i o nm e t h e d ) 其主要思想是：对于一个包含刀 个数据对象的数据集，构建鼠翩) 个簇( 或类) ，使得每一个簇( 或类) 中至少包 含一个对象，每个对象属于且仅属于一个簇( 或类) ，并且要求同一个簇( 或类) 中的对象越接近越好，不同簇( 或类) 中的对象越远越好【刀对于给定的k ，算法 首先给出一个初始的划分方法，然后通过反复迭代来改变分组，使得每一次迭代 后的划分结果都较前一次更优用一个目标函数来衡量划分方案的好坏，算法进 行反复迭代的过程就是目标函数最优化的过程，则此方法也称为最优化方法属 于此类的算法有k - m e a n s 算法【引、p a m 算法、c l a r a 算法等【9 q 5 1 ( 2 ) 层次式聚类算法( h i e r a r c h i c a lm e t h e d ) 层次方法又称为树聚类算法， 其主要思想是：使用数据联接规则，透过一种层次架构的方式，反复将数据进行 2 基于顶点度和顶点个数的图聚类算法 分裂或合并，以形成一个层次序列的聚类问题根据层次的形成过程，层次方法 又分为聚合( a g g l o m e r a t i v e ) 方法和分裂( d i v i s i v e ) 方法层次聚合算法的计算 复杂度为o ( n 2 ) ，适合于小型数据集的分类，属于此类算法的有b i r c h 算法 9 1 、 c u r e 算法【9 】等 ( 3 ) 基于密度聚类算法( d e n s i t y - b a s e dm e t h o d ) 其主要思想是：只要邻近 区域的密度超过某个值，就继续聚类，最终相对高密度的区域被相对低密度的区 域分割成类代表算法有：d b s c a n 算法【1 0 】、o p t i c s 算法、d e n c l u e 算法【1 1 1 、 d b c l a s d 算法、c l i q u e 算、法【1 2 】等 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) 其主要思想是：把对象空间化 为有限数目单元，从而形成网格结构，然后在这个网格结构上进行聚类操作该 类方法的执行时间只与数据对象的数目有关，因此速度很快代表算法有：s t i n g 算法【1 3 1 、w a v e c l u s t c r 算法、o p t i g r i d 算法等 ( 5 ) 基于模型的方法( m e d e l h a s e dm e t h e d ) 其主要思想是：事先为每个类 假设一个模型，可以是数据点在空间中的密度分布函数( 或其他) ，然后寻找数 据对该模型的最佳拟合该方法主要有两大类：统计学方法和神经网络方法统 计学方法的代表算法有：c o b w e b 算法、c l a s s i t 算法、f c m 算法、m m 算法 等神经网络方法的代表算法有：竞争学习算法( s p l l ) 、自组织特征映射算法 ( s o f m ) 、l v q 算法等 ( 6 ) 对于一些大规模的数据集和高维数据，还有一些其他的聚类方法大尺 度数据集的算法有：c l a r a 算法、c l a r a n s 算法等：对高维数据有p c a 算法、 i c a 算法、i s o m a p 算法掣2 3 2 6 】 1 2 图的聚类算法的研究与现状 图的聚类是数据聚类的一种很重要的变体简单地说，图的聚类是指按照某 种给定的指标，将图中相对连接紧密的顶点及其相关联的边分组形成一个子图 【9 】通过取代所有这样的子图可以获得一个粗略的聚类图，这种聚类图可以极大地 降低视觉复杂度，对图进行聚类分析增强了问题可视性，有助于可视化的分析和 3 ( 1 ) 缺少强有力的数据分析方法与理论支持； ( 2 ) 拥有较大的计算量，尤其在相似性度量方面； ( 3 ) 图的顶点和边没有一个标准化的规定，也就没有一种标准的方法可以映 射点和边成为向量，因此将很难利用现有的数据空间和聚类成果； ( 4 ) 图的结构特性也是影响聚类效果的一个十分重要的因素 因此很难找到一种普遍适应多种多样图结构的聚类方法 4 基于顶点度和顶点个数的图聚类算法 1 3 本文的研究内容与安排 第l 章，绪论本章简单的介绍了基于图理论聚类算法的发展及其现状，给出 了文章的结构安排 第2 章，基本概念与预备知识本章介绍了图论的一些基本概念和记号 第3 章，基于i c r 的图聚类算法及其改进算法本章先对m v i c r 算法进行分 析，在具体图中应用并给出聚类过程；然后引入并行计算的思想，并给出了改进 后的聚类算法 第4 章，基于i v c r 的图聚类算法本章在对第三章中两种算法的分析基础上， 提出了新的聚类指标内部顶点连接比率( c r ) ，并给出基于i v c r 的图聚 类算法比较m v i c r 算法、基于i c r 的改进算法以及i v c r 算法聚类过程，讨 论了三种算法在两种特殊图类上的优劣性 第5 章，结论本章对本文的主要研究结果进行了总结，并提出了一些有待解 决问题 5 第2 章基本概念与预备知识 第2 章基本概念与预备知识 2 1 基本概念与记号 为了讨论起来方便起见，首先引用一些图论术语和记号，这些术语和记号主 要来自于参考文献 4 ，5 ，2 1 ，2 7 等 。 定义2 1 图g = ( v ，d 是由顶点集y 和边集e 构成的有序对，其中净坎回= y l ，v 2 ，吻) ，脚( 铲 e l ，e 2 ，e q 是由v x v 的元素组成的可重集合 定义2 2 若p = ( 一，吩) e ( g ) ，则称v 和相邻或邻接；也称g 与m ，巧关联； 有公共顶点的两条边称为相邻或邻接若一个点没有任何边与之关联，则称此点为 孤立点 定义2 3 图g 。称为图g 的补图，若v ( g 。) = y ( g ) ，且 ( z ，y ) e ( g 。) e ( 五y ) 萑e ( g ) 定义2 4 对图鼠图g ，如果v ( h ) 量v ( g ) e ( h ) e ( g ) 且，称图h 为图g 的一个子图，记为日gg ，也称g 包含日作为一个子图如果日g ，且唧) 为坎回的一个真子集( 或者耳功为耳回的一个真子集) ，那么称日是g 的一个 真子图 定义2 5 图g 中一条“y 链形即为g 的一个顶点序列，满足：从材出发，到 ，结束，且连续的顶点是邻接的若铲v 链中没有重复的顶点，那么它是一条删 路如果图g 包含一条“，路，那么就称“和，是连通的；换言之，如果对于图g 中每对不同顶点“，y ，g 都包含一条“1 ，路，那么g 称为连通的 定义2 6 图g 中顶点1 ，的度，记为d g ( d 或d ( v ) ，是关联到1 ，的边的条数，注 意1 ，上的环在计算度时要计算两次最大的顶点度记为( g ) ，最小的顶点度记为 6 ( g ) 如果a ( g ) = 8 ( g ) ，则称g 是正则的如果所有顶点度是k ，则称g 是k 正则的v 的邻域，记为或，是由1 ，的邻接顶点构成的集合若对于g 的任意一个顶点1 ，都有d ( 1 ，) = ，( 咚r s n - 1 ) ，则称g 是，正则图 6 基于顶点度和顶点个数的图聚类算法 定义2 7 图g 中顶点集坎6 ) 的非空真子集夕的邻集，记为似国表示与夕 中点相关联的点的集合 定义2 8 任何不同的两顶点之间都有边相连的简单无向图称为完全图 定义2 9 设萌= ( 跖，局) 和卵( 压，囝是两个图，若巧n 坯= 1 2 j ，则称g 与伤是 不相交的 定义2 1 0 设崩= ( 所，蜀) 和分( 历，历) 是两个不相交的图，定义 翻+ 岔= ( 所u 经，局u 历u 历) ， 这里历= ，称伤+ 伤为翻与伤的和 2 2i c r 算法的有关概念及结论 设庐( 啦) 为一个图，纵6 ) 的划分( 记为仅6 ) ) 称为g 上的一个聚类，q 回 中的元素称为类( 或块) 下面的术语、记号和相关结论主要来自于参考文献【2 7 】 定义2 1 1 对任意的类c , s ea 回，称g 中关联类f 与类j 的边的个数为f 与， 的类间连通度，记为力亿力( 简记为d ( c , 4 ) 特别地，对任意的类c ea 回， 类f 与图g 内顶点之间的连通度，记为喀( 岛力( 简记为政g 力) 定义2 1 2 对任意的类f a 回，类c 中边所邻接的点都在类c 内的边的个数 ( 内部边) 称为类c 的内部度，记为厶 定义2 1 3 对任意的类f a 回，类c 的边中只有一个邻接点在类f 内的边的 个数( 外部边) 称为类c 的外部度，记为以类f 的外部度以等于类内部的每 个顶点与类外部顶点的连通度之和，用攻肛g 力表示，记为 丘= 故肛g 力 定义2 1 4 设双回为图g 上的一个聚类，对任意的类f 双回，称踹 为c 的内部连通比率，记为肋d 力( 简记为叫力) 注：因为v l ，破力 o ，所以v f c ，瞧，放力 o f 面b v c ec ， 7 第2 章基本概念与预备知识 。，识d = 炬，以岛力+ 。，d ( y - c , v ) ， 传。破力炬，以岛功 定义2 1 5 聚类q 6 ) 的内部连通比率，记为亿殒d ，等于q 6 ) 中所有类的内 部连通比率之和，即对v f f ，i c r a ( c ) = i c r ( c ) 饱c 定理2 1 对任意的类c eq 回的内部度等于顶点l ，f 与f 连通度之和除以2 ， 即乇= ev e 了c d 一( c , v ) 定理2 2 对任意的类c ，q 回，则f u j 的内部度钆j 为名+ + 以岛力， 鼬j 奏j s = j c 七i s 七d 婶，心 定理2 3 对任意的类c ，j 仅6 ) ，则f u ，的外部度z u 岁为以+ 以一2 敏岛力， 鼬x s = x c 七x s 一2 d ( c , s ) 定理2 4 对任意的类c ，j a 回，则f u j 的内部连通率为 2 ( i c + i s + d ( c , s ) )2 厶2 6 2 u c 七i 七x c 七x s1 j c 七x c2 j s 七x s j 记为，( 刀( 岛力( 不至混淆的情况下简记为a 尼刀) 基于顶点度和顶点个数的图聚类算法 第3 章基于i c r 的图聚类算法及其改进算法 3 1 基于i c r 的图聚类算法 m o u s s i a d e s 与v a k a l i 在文献 2 7 】中提出了一种基于内部连通比率( i n t e r c o n n e c t i o nr a t i o ，简写为i c r ) 的图聚类算法其中包含着使i c r 最大的集聚思想具 体地讲，该算法将指标作用在图的分类中，通过对类之间关系的运算，把关系最 紧密的类合并，直到有最完美的划分 由在定义2 1 5 知，类c 的i c r ( c ) 的值介于0 ，l 之间特别地，以单点为一类 的i c r ( c ) 值等于0 ，而所有内部连接大于l 的类的i c r ( c ) 值都大于0 若图中的一个 类c 不与该类余图连接，则其i c r ( c ) 值等于1 同样由于群集的模块化，类c 的州0 指标反映了类内部连接的紧密与类外部连接的稀疏，如果一个类的i c r ( c ) 指标较高， 则标志着该类具有较高的内部联系和较低的外部联系当给出一个图的聚类结果 后，定义i c r 为所有属于这个聚类中类的i c r 指标之和，而i c r 的值有多大取决 于图g 的类型对一次聚类来讲，如果图中只包含单点，则i c r 的值为0 ，如果 图中只有一个类则i c r 的值为1 ，如果图存在至少一个更精细的类，则该图的i c r 值通常大于1 如图3 1 ，聚类 0 ，1 ，2 ) ， 3 ，4 ，5 ) ) 的i c r 值等于1 3 3 因此，计算i c r 的最大值并不适用于只含单个的类或只有单个点的图 图3 1图g f i g3 1g r a p h g 一种普遍的方法去最优化一个标准函数是用贪婪策略，基于相似矩阵的性能 用交替的方法、或者多种多层的最优化思想在i c r 算法中，修改了一种普遍的 凝聚算法以达到对i c r 的最优化类似的方法曾经被n e w m a n 采用过 2 7 1 更精确 9 第3 章基于i c r 的图聚类算法及其改进算法 地，i c r 算法由一个最初的每一顶点为一类开始在循环的每一步，选择i c r 的 增加量最大的两类合并 m o u s s i a d e s 和v a k a l i 在 2 7 中提出了基于i c r 图顶点聚类算法，其聚类过程 如下： 算法3 1 基于i c r 图顶点聚类算法( 简称m v - i c r 聚类算法) s l ：给定图g = ( 啊) s 2 ：令c = c l ，c 2 ，c m ，其中c i = v i ) s 3 ：v m y ，令l = 0 s 4 ：v 以，y ，) e ： + = l ，+ = 1 ，d ( u ， _ ) ) = 1 ， s 5 ：v “，1 ，) e ： i c r ( v i ，川) ) - 赢5 s 6 ：当i c l l 时 氛找到勰值最大的两类c f ，9 ，且d ( c i ，q ) o ； b 如果这样的 c i ，c ! j ) 不存在，则退出 c 合并e l ，c j 为一类，记为q ； d c = c + c e - c r c ： c l = + 一d ( q ，勺) ； t x c ：= xc t + xc i - 2 d ( q ，c 沁 舀v cc q ，重新计算廊( c 七，c ) 结束循环 算法开始将图中的每一个顶点作为一类，计算每一组相关联的类( 顶点) 之 f s q 的a t c r在循环里，选择脓值最大的两个顶点合并为一类，如果这样的顶 点数大于1 ，那么从脓值最大的顶点对集合中任选一对合并为一类；若不存在这 1 0 基于顶点度和顶点个数的图聚类算法 样的两类使得腴值最大，则表明对图g 进行的聚类包含不连通的部分，退出算 法；对于合并后的新类c 七，在原类集中去掉这两个已合并的类 c i ，c ! i ) 并嵌入新类o k ， 构成一组新的类集；然后，根据定理2 2 和定理2 3 对新类的内部度和外部度重新 赋值；最后，重新计算已经得到的类c 七与新的类集中除去c k 以外的类间的勰的 值算法进行迭代直到图中所有的顶点聚为一类或类c 包含不连通的部分，生成 分层聚类 3 2 基于m v i c r 聚类算法的实例分析 按照m v i c r 聚类算法( 算法3 1 ) ，对图3 2 中的图g 的顶点进行聚类，其 过程如下： 图3 2 图g f i g3 2 g r a p h g ( 1 ) 将图中每一顶点作为一类，计算两类间的廊值，其中最大值为 a i c r ( 1 7 ，1 8 ) = a 1 c 置( 1 8 ，1 9 ) = 心( 1 7 ，1 9 ) = ：1 ， j 则任选其一，合并 1 7 ) ， 1 8 ) ( 见图3 3 ) 则任选其一，合并 4 ) ， 6 ( 见图3 5 ) 1 2 大的两类，即合并 大的两类， 1 3 1 4 基于顶点度和顶点个数的图聚类算法 c o ) ( e ) ( d ) ( o f i g 3 9c l u s t e r i n gp r o c e s s 根据上面对图的聚类可以看出，i c r 聚类算法是从一个脓最大的基础类开 始，计算这个类与它邻接类之间的职，逐步将图中的所有点聚为一类这样的 1 6 基于顶点度和顶点个数的图聚类算法 聚类结果是以小范围为基础逐步扩大到整个图的，由于图中的职的最大值( 或 较大值) 不一定唯一，有可能具有最大值( 或较大值) 这样的类的组合有多个， 那么在聚类时，选择哪一个先合并就是一个i 口- j 题，如图3 2 ，在计算顶点类的腴 1 时，有最大的值为a t c r ( 1 7 ，1 8 ) = a r c r ( 1 8 ，1 9 ) = a ，c r ( 1 7 ，1 9 ) 一- - 9 1 ，算法从 1 7 ，1 8 、 j 1 8 ，1 9 、 1 7 ，1 8 这- - - - 组中任选一组合并，而且无论选择那组，在第二次循环中这 一组必定与三个顶点中剩余的顶点合并，假设选择 1 7 ，1 8 合并，那么与其合并的 类必为 1 9 ) ，由于 1 7 ，1 8 ，1 9 两两间的脓值最大且联系最为紧密，如果通过一次 循环将三点同时合并，则必定会减少聚类步骤，并且类之间的关系将更加清楚在 i c r 改进算法中将提出同时合并多个点的算法 3 3 改进的基于i c r 聚类算法 m v i c r 聚类算法是从，c 置值最大的单类开始，逐步将图中的点聚为一类，而 当职值较大的类有多个时，只是从中任选一个合并实际上，对于姗值大的 类来说，它们应该是关联最紧密的，应该在动态的聚类过程中首先合并的因此， 对于勰值最大的关联类，在一次聚类循环中将它们归为一类，即通过一次循环 将脓值最大的关联类同时合并 现在，考虑一个极端情况，用m v i c r 算法对完全图进行分类( 见图3 1 0 ) ： 首先将图中的每个顶点作为一类c = c o ， 1 ) ， 2 ) ， 3 ) ， 4 ) ，计算各类间的脓值， 1 得到任何两类间的脚值皆相等，均为 根据m v - i c r 算法，任选一类合并， t 那么不妨合并 o ) ， 1 ) 为一类，再计算类c = c o ，l ， 2 ， 3 ) ， 4 ) ) 间的脚值，得到 l 的廊值依然两两相等，且值仍为，同样按照m v i c r 算法，可以合并c 中任 何两类但是，直观来看，由完全图顶点的高度对称性，第一步将每个点作为一 类后，再进行聚类时，每个点所处的地位是相同的( 脓值相同) ，应该归为一类， 即对完全图的聚类结果应该只有两个：一个是每个点是一类 0 ) ， 1 ) ， 2 ) ， 3 ) ， 4 ) ， 1 7 得 l = + 毛+ d ( c l ，c 2 ) ， 定理结论也成立 假设当刀= k l 时，定理结论也成立即 当刀= 七时，记c = c lu c 2u ku c k l ，则有 1 8 基于顶点度和顶点个数的图聚类算法 i = l i = 乞+ 。+ d ( c ，仁) = + d ( c f ，q ) + + d ( q ，q ) 1 = 1 i = t 爿+ l 1 = 1 = + d ( q ，c ，) i = 1 l = l 户l + i 故，结论成立 定理3 2 设q g ) 为图g 上的一个聚类，q c ( g ) ( i = 1 ，2 ，刀) 若 c - c luc 2u ku 巳，则c 的外部度 月n - !n 置= - 2 x d ( q ，c j ) i f f i li = 1j = i + l 证明：用数学归纳法证明 得 当以= 1 时，c = q ，定理结论显然成立当刀= 2 时，c = qu 乞，由定理2 3 x c = x c l + x c 。一2 d ( c , ，c ， 定理结论也成立 假设当咒= k 一1 时，定理结论也成立即 i r - ik - 2k - ! 五= 一2 d ( q ，c j ) ， 当n = 后时，记c k q uc 2 u kk 9 c k l ，则有 x = x 。 。 “t = 置+ 置一豺( c ，q ) = x - 2 x e d ( c , ，q ) + k 一2 j ( q ，q ) i i l1 1 1 j 一+ l l = l = t 一2 北，q ) 鲥 鲥j = + l 故，结论成立， 下面基于定理3 1 和定理3 2 的结论，给出一个可同时合并多个类的图顶点聚 1 9 第3 章基于i c r 的图聚类算法及其改进算法 类算法： 算法3 2 基于i c r 图顶点聚类改进算法 s 1 ：给定图皑以d s 2 ：c o = c i ，c j ，c i 吲) ，c ：f = ) ，s = o s 3 ：v m v ，= 0 s 4 ：v “，) e ， + = l ，k + = l ，d ( k ) ， _ ) ) = 1 ， 职( 咻2 丽2 ； s 5 ：v d ( q ，勺) o ， 姝咖一一最一旦2 1 e + x e ； s 6 ：当ic oi 1 时， i = 1 ，c ：= c l u s t e r i n g ( c | f 1 ) ，f + + ； c l u s t e r i n g ( s ) d o w h i l e i s l 1 找积的值最大的墨和勺，d ( 墨，s j ) o 肛l ，辟l ： 若有脓值两两相等的类集，则 合并勰值两两相等的类集： s = s + s t ： 其中疗代表符合条件的类的个数 = 墨 。埘 s = s s ，重新计算s 中姗的值； ) 否则 t 合并s t 七s j = s i ； s t _ s + s i ： i 。= i s i 七is j + d b t ，s ； x s l = xs j xs i 一2 d ( s j ，s j ) ； n + ： s = s s ，重新计算s 中脓的值； ) ) 返回s 3 4 基于i c r 的改进算法的实例分析 根据上面所提出的改进算法对图3 2 进行聚类，其过程如下： ( 1 ) 首先将图中每一顶点作为一类，即 c o = “1 ) ， 2 ) ， 3 ， 1 9 ) 令s = c o ，计算s 中两类间的腺值，得 脓( 1 7 ，1 8 ) - 一- - a i c r ( 1 8 ，1 9 ) = a 勰( 1 7 ，1 9 ) = ；1 ， 焉= 1 7 ，1 8 ，1 9 ) ，s t - s + s j 2 1 第3 章基于i c r 的图聚类算法及其改进算法 即1 7 ，1 8 ，1 9 归为一类( 见图3 11 ) 图3 11 1 7 ， 1 8 和 1 9 ) 归为一类 f i g3 11m e r g e d 1 7 ) ， 1 8 a n d ( 1 9 ) t o g e t h e r 计算s s 中两类间的脓值，单点集 o ) ， 1 ) ， ，s 3 = 4 ，5 ，7 ) ，s 4 = 1 3 ，1 4 ，1 5 ，1 6 ) 即得到类 o ，1 ，2 ，3 ) ， 4 , 5 ，7 ) ， 1 3 ，1 4 ，1 5 ，1 6 ) ( 见图3 1 2 ) 图3 1 2 o ) ， 1 ) ， 2 ) ， 3 ； 4 ) ， 5 ) ， 7 ； 1 3 ， 1 4 ， 1 5 ， 1 6 分别归为一类 f i g3 1 2m e r g e d o ) ， 1 ) ， 2 a n d 3 ； 4 ) ， 5 a n d 7 ) ； 1 3 ， 1 4 ， 1 5 ) a n d 1 6 t o g e t h e r 计算s s 。中两类间的脚值，单点集 8 ) ， 9 ) ， 1 0 ) ， 1 1 ) ， 1 2 ) 两两 间的廊值为三，则墨= 8 ，9 ，1 0 ，11 ，1 2 ) ，单点集 6 ) 为一类= 6 ) ( 见图3 1 3 ) o 图3 1 3 8 ， 9 ) ， l o ， 11 ) ， 1 2 归为一类 f i g3 1 3m e r g e d 8 ) ， 9 ) ， 1 0 ) ， 1 1 ) a n d 1 2 t o g e t h e r ( 2 ) 由第一次分类，得到： g = 0 ，1 ，2 ，3 3 ， 4 ，5 ，7 3 ， 6 3 ， 8 ，9 ，1 0 ，1 1 ，1 2 3 ，1 1 3 ，