（电路与系统专业论文）基于复杂网络局域同步理论的聚类算法研究.pdf

u n i v e r s i t ) o fs a n dt e c h n o l o g 、o fcnv e r s i t yo fc i e n c ea n de c h n o l o q yh i n ash l adi s s e r t a t i o nf o rm a s t e r sd e gr e e r e s e ar c ho fclu s t e r in g a l g o r i t hm b a s e do nl o c a l s y n c h r o ni z a t i o n t h e o r y o f c o m p l e x n e t w o r k a u t h o r sn a m e ： s p e c i a l i t y ： s u p e r v i s o r ： f i n i s h e dt i m e ： h o n gl e i c i r c u i t sandcircuitsa n ds y s t e m s p r o f p e i l i n gz h o u m a y9 m ，2 0 1 2 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确 的说明。 作者签名：j 婊 签字日期：j 生睑d 埠 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 财么开口保密( 年) 作者签名：j 髫虹 导师签名 签字日期：j 砬位驯 签字日期：2 垒! 兰：垄她 摘要 摘要 随着复杂网络理论研究的蓬勃发展，如何将复杂网络拓扑结构和动力学模型 上取得的丰硕理论成果应用于解决实际的问题，成为下一阶段复杂网络研究的重 点。含有社团或群落结构的网络在同步化过程中能够将网络的群落结构和拓扑模 块涌现出来，而数据聚类则正是将数据划分成不同的簇。本文采用理论和实践相 结合的方式，深入研究复杂网络上的局域同步行为及其在数据聚类中的应用。 首先在已经取得的复杂网络局域同步理论成果基础上，进一步分析了网络的 同步动力学与拓扑结构之间的关系，着重研究了网络同步的相位振子模型 k u r a m o t o 模型。在深入分析网络的耦合强度对随机网络和无标度网络同步过程 的影响时，通过计算机模拟得到复杂网络局域同步的“清晰 图像。深入探讨了 含有群落结构的网络同步耦合演化过程，通过定义局部序参数衡量网络的局域同 步化水平，利用拉普拉斯连接矩阵的谱信息揭示了网络同步过程与网络的拓扑结 构之间的关系。 其次分析了数据聚类算法的研究现状，根据算法的聚类思想对其进行了分类 并详细分析了每一类中具有代表性的算法优缺点，在概述复杂网络聚类算法时， 深入研究了基于信息传播机制的a p 聚类算法。然后，简单介绍了聚类算法在图 像分割、电子商务网站中的客户细分、搜索引擎的用户意图识别等方面的应用， 重点研究基于复杂网络理论的金融市场网络结构并运用a p 聚类算法详细分析复 杂金融市场网络的社团结构，结果表明该方法能够准确的划分出股票所对应的社 会行业，并且能够在划分出的股票社团聚簇中找出最具有影响力的那支股票。 接下来，本文提出了基于复杂网络局域同步理论的数据聚类算法s y n c ，并 将该算法应用于分析功能磁共振图像( f m r i ) 数据，检测处于任务态下的大脑功能 激活区域。具体为通过融合k u r a m o t o 模型相位振子的动态特性与时间序列的相 关性，提出了一种新的衡量网络节点间相似性的方法来计算节点间的相似度，根 据最近邻准则选取最优的参数初始化设置，而后运用同步聚类算法，使得网络中 数据节点同其近邻节点进行同步耦合，随着网络不断同步演化，相似的数据节点 逐渐同步到一起形成聚簇。计算出每个聚簇内部节点问的平均关联，具有最大平 均关联的聚簇即为大脑功能的激活区域。 最后，对比分析了s y n c 算法和k m e a n s 算法分别在基于听觉和视觉的f m r i 数据集上的聚类结果，通过与脑功能区模板对比表明本文提出的聚类算法s y n c 能够更准确有效的检测出处于任务态实验的脑功能激活区域。 关键词：复杂网络局域同步数据聚类k u r a m o t o 模型f m r i 摘要 一一_ i i a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f c o m p l e xn e t w o r kt h e o r y , o no n eh a n d ，h o wt op u t t h ef r u i t f u lt h e o r e t i c a lr e s u l t so fc o m p l e xn e t w o r ki n t op r a c t i c eb e c o m e st h ef o c u si n t h en e x tp h a s eo fc o m p l e xn e t w o r kr e s e a r c h o nt h eo t h e rh a n d ，w i t ht h er a p i d d e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , f i n d i n gt h ei n t e r e s t i n gp a r ti nt h ev a s t a m o u n t so fd a t ac a t c h e st h ea t t e n t i o no fr e s e a r c h e r s d u r i n gt h e s y n c h r o n i z a t i o n p r o c e s so fc o m p l e xn e t w o r k s ，t h o s ew i t hc o m m u n i t ys t r u c t u r e so rt o p o l o g ym o d u l e s w o u l de m e r g es p o n t a n e o u s l y a n dt h ep u r p o s eo fd a t ac l u s t e r i n gi st od i v i d et h ed a t a s e t si n t od i f f e r e n tc l u s t e r s t h e r e f o r e ，t h el o c a ls y n c h r o n i z a t i o no fc o m p l e xn e t w o r k c a nb ea p p l i e dt od a t ac l u s t e r i n gr e s e a r c h i nt h i sp a p e r ，b yt h ec o m b i n a t i o no f t h e o r y a n dp r a c t i c e ，w ew o u l di n d e p t hs t u d yt h el o c a ls y n c h r o n i z a t i o nb e h a v i o ro fc o m p l e x n e t w o r k sa n di t sa p p l i c a t i o ni nl a r g e - s c a l ed a t ac l u s t e r i n g f i r s t l y , b a s e do nt h et h e o r yr e s u l t so fs y n c h r o n i z a t i o ni nc o m p l e xn e t w o r k ，t h e p a p e rg i v e sf u r t h e ra n a l y s i so ft h er e l a t i o n s h i pb e t w e e ns y n c h r o n i z a t i o nd y n a m i c sa n d t o p o l o g yo ft h en e t w o r kt h a tf o c u s i n go nt h ep h a s eo s c i l l a t o rm o d e l k u r a m o t om o d e l a n d b yu s i n gt h em e a nf i e l dt h e o r y ，w ed e r i v et h es y n c h r o n i z a t i o nd y n a m i c se q u a t i o n o fs t a t e w ef u r t h e ra n a l y s i st h ei n f l u e n c eo fc o u p l i n gs t r e n g t hi nt h es y n c h r o n i z a t i o n p r o c e s so fr a n d o mn e t w o r k sa n ds c a l e f r e en e t w o r k s a n da c q u i r et h er e a lp h i l o s o p h y o fl o c a ls y n c h r o n i z a t i o n i na d d i t i o n ，t h r o u g ht h ed e f i n i t i o no fl o c a lv i r t u a lp a r a m e t e r s a n dt h ed y n a m i cl a p l a c em a t r i x ，w es t u d yt h es y n c h r o n i z a t i o nd y n a m i c st h e o r yo f n e t w o r k sw i t hc o m m u n i t ys t r u c t u r e a f t e r c a r e f u l l yi n v e s t i g a t e t h es p e c t r a l i n f o r m a t i o n ，w ef i n dt h a tt h es y n c h r o n i z a t i o np r o c e s sr e f l e c t st h et o p o l o g yo ft h e n e t w o r kw h i l et h et o p o l o g yo ft h en e t w o r ko fa f f e c t si t ss y n c h r o n i z a t i o np r o c e s s s e c o n d l y , w es u m m a r i z ec u r r e n td a t ac l u s t e r i n ga l g o r i t h ma n dad e t a i l e da n a l y s i s o fa d v a n t a g e sa n dd i s a d v a n t a g e so fe a c ht y p eo fr e p r e s e n t a t i v ea l g o r i t h m s w h e nw e g i v ea no v e r v i e wo fc o m p l e xn e t w o r kc l u s t e r i n g ，w ea l s os t u d yar e c e n t l yp r o p o s e d m e s s a g e - - p a s s i n g - - b a s e da l g o r i t h mc a l l e da f f i n i t yp r o p a g a t i o ni si n t r o d u c e dw h i c hi s b a s e do nt h em e c h a n i s mo fi n f o r m a t i o nd i s s e m i n a t i o n l a t e r ，w ec o n s i d e rt h e a p p l i c a t i o no fd a t ac l u s t e r i n gi ni m a g es e g m e n t a t i o n ，c u s t o m e rs e g m e n t a t i o ni n e - c o m m e n c e ，u s e r s i n t e n tr e c o g n i t i o ni ns e a r c he n g i n ea n dc o m p l e xf i n a n c i a l n e t w o r ka n a l y s i s i i i i nm et h i r ds t 印，w ei n v e s t i g a t eas y n c h r o n i z a t i o n - b a s e dd a t a d r i v e nc l u s t e n n g 即p r o a c hi nt h ea n a l y s i so ff u n c t i o n a lm a g n e t i cr e s o n a n c ei m a g i n g ( 恻) d a t 姐d s p e c i j c l c a l l y ，i nd e t e c t i n gf u n c t i o n a la c t i v a t i o nf r o mf m r i d a t a w ef i r s t 雠n ean e w m e 踟r eo fs i m i l a r i t yb e t w e e na l lp a i r so fd a t ap o i n t s ( i e ，t i m e s e l l e so fv o x e i s ) i n t e 鲫 t i n g b o t h p h a s e c o h e r e n c ea n da m p l i t u d e c o r r e l a t i o n t h e s ep m m s e s i i i l i l 碰t i e sa r et a k e na st h ec o u p l i n gb e t w e e n as e to fk u r a m o t oo s c i l l a t o r s ，w 1 1 i c hm t u r ne v 0 1 v ea c c o r d i n gt oan e a r e s t - n e i g h b o rr u l e a st h e n e t w o r ke v 0 1 v e s s i m i l a rd a t a p o i n t sn 咖m l ys y n 幽n i z e w i t he a c ho t h e ra n df o r md i s t i n c tc l u s t e r s i h ec l u s t e n n g b e h a v i o ro ft h ei n t e r 枷o nn e t w o r ko f t h ec o u p l e do s c i l l a t o r st h e r e f o r em l r r o r st h e c l u s t 础gp r o p e n yo ft h eo r i g i n a lm u l t i p l et i m es e r i e s t h ed u s t e r e d 托9 1 0 n s w h o s e c r o s s c o n e l a t i o nc o e 街c i e n t sa r em u c hg r e a t e rt h a no t h e rr e g i o n s a r ec o n s i d e r e da s t h e 觚t i o n a l l ya c t i v a t e db r a i nr e g i o n s b yt h ea n a l y s i so f f m r id a t ai n 绷d i t o r y 趾d v i s u a la r e a s ，t h er e s u l t ss h o wt h a tt h er e c o g n i z e db r a i nf u n c t i o n a l a c t l v a t l o n sa r em c o 踯l e t ec o r r e s p o n d e n c ew i t ht h o s e f r o mt h eg e n e r a ll i n e a rm o d e lo fs p m ，b u t w l t ha s i g n i f i c a n t l yl o w t i m ec o m p l e x i t y f i n a l l v ，w e 矗j r t h e m o r ec o m p a r e o u rr e s u l t sw i t ht h o s ef r o mt r a d i t i o n a lk m e a n s c l u s t e r i n ga p p r o a c h w e f i n dt h a to u rn e wc l u s t e r i n ga p p r o a c hc a nd l s t m g u l s n b e t w e e nd i 仃e r e n tr e s p o n s ep a t t e r n sm o r ea c c u r a t e l y a n de f f i c i e n t l ym a nk - m e a n s a p p r o a c ha n di s u s e f u li nd e t e c t i n gf u n c t i o n a lb r a i n 枷v a _ t i o n 舶mc v e n t 。r e l a t e d e x p e r i m e n t a lf m r i d a t a k e yw 。r d s ：c o m p l e xn e t w 。r k ，l o c a l s y n c h r 。n i z a t i 。n ，d a t ac l u s t 甜n g ，k 眦锄。t o m o d e l i v 目录 目录 摘要1 a b s t r a c t l 第一章绪论1 1 1 引言l 1 2 研究背景1 1 2 1 复杂网络概述1 1 2 2 复杂网络同步研究简介3 1 2 3 数据聚类概述7 1 2 4 复杂网络中的聚类方法1 1 1 3 本文的研究内容与章节安排1 3 第二章相关工作综述1 5 2 1 引言1 5 2 2 复杂网络中的相位同步模型1 5 2 3 复杂网络的耦合同步过程1 8 2 4 含有群落结构网络的局域同步2 0 2 5 本章小结2 5 第三章数据聚类的应用研究2 7 3 1 引言一2 7 3 2 聚类算法在图像分割中的应用2 8 3 3 聚类算法在电子商务和信息检索中的应用2 9 3 4 聚类算法在复杂金融网络中的应用3 2 3 4 1 金融市场网络模型实证研究3 3 3 4 2 基于a p 聚类算法的金融市场网络社团划分研究3 7 3 5 本章小结4 0 第四章基于局域同步理论的聚类算法研究4 l 4 1 引言4 1 v 目录 4 2 基本假设4 2 4 3s y n c 算法一4 3 4 3 1 动态聚类过程描述4 4 4 3 2 基于最近邻准则的参数估计4 5 4 3 3s y n c 算法描述4 8 4 4 算法分析与实验4 9 4 4 1 数据集准备一4 9 4 4 2 相似性度量方法5 0 4 4 3 实验结果5l 4 5 本章小结5 5 第五章总结与展望5 7 5 1 本文研究工作总结5 7 5 2 工作展望5 8 参考文献5 9 致 射6 3 在读期间发表的学术论文与取得的其他研究成果6 5 v i 绪论 1 1 引言 第一章绪论 复杂网络理论自w a t t s 、s t r o g a t z 、b a r a b a s i 、a l b e r t 等人于1 9 9 8 年和1 9 9 9 年提出奠基性的模型 1 ，2 以来有了蓬勃的发展。近1 0 年成为研究领域的热点和 焦点 3 6 。( ( s c i e n c e ) ) 也在2 0 0 9 年的7 月出了专刊纪念复杂系统和网络发展的 1 0 周年，并且对复杂系统和网络实际性的应用研究提出展望。 1 2 研究背景 本文的研究工作是建立在广大科学研究工作者在复杂网络基本理论和复杂 系统的同步动力学特性获得的大量优秀成果，本节简要概述相关的研究工作。 1 2 1 复杂网络概述 一个具体的网络可以抽象为由包含节点数目为的节点集矿和连边数目 为m 的边集e 组成的图g 。节点i 的度记为k i ，e 中的每条边均同矿中的一对 节点相对应。通常用邻接矩阵彳来表示图g ，若节点f 和节点，存在连边，则 a ，= l ；否则a ，= 0 。更具有一般意义的网络模型是加权网络，由加权邻接矩阵 形描述，w i 表示节点f 和节点，连边的强度。人们通过对自然界中存在的或人为 的构造复杂网络统计特征的研究发现，不同的网络代表截然不同的复杂系统，可 以利用网络的统计特征对复杂系统进行分类。在所有的网络统计特征中，网络中 节点的度分布p ( 尼) 是最重要的特征之一，它可以有效的衡量网络节点的度的分 布概率。除了度分布外，其他统计特征如平均最短路径长度z = ( d i i ) ，d ，为节点 i 与，之间的最短路径长度、表示一个网络节点聚集程度的系数，即聚类系数c 。 度分布e ( k 1 最先被用来对复杂网络进行分类。如果网络的度分布在该网络 的度平均值( 后) 处有一峰值，然后呈指数快速衰减，即当k ( k ) 时，度为k 的 节点几乎不存在，这类网络也称为指数网络或同质网络，常见的网络模型如e r 随机图。随机图是最简单有效的网络模型，其最早研究见于e r d 6 s 及r 6 n y i 7 1 的 著作中。在e r 模型中，节点数固定为n ，节点问由无向边随机连接，由此构成 一个无向无权网络，网络中有n ( n 一1 ) 条可能边，每条边出现的概率为p 且相互 独立，与每个节点相连的边的条数即节点的度，服从二项分布或大n 极限下的 泊松分布。当p 1 1 1 0 ，时，网络中会出现一个包含节点数与n 相当的最大连 绪论 通子图，也就是说整个网络是连通的。e r 随机图模型并不适用于理解实际网络 的产生过程。因此，研究者抛开传统的完全基于随机过程的随机图模型，提出了 新的模型。在新的模型中加入了一些限制随机性的机制，使得新模型能够符合实 际复杂网络的统计特性。其中，最为基础的模型是由w a t t s 和s t r o g a t z 提出的小 世界模型( 简写为w s 模型) 8 】。小世界模型起源于如下想法：首先建立一个 低维的网络结构，网络中原有的连接代表了距离接近的节点之间的连接。然后增 加或移动一些边，以生成较低密度的“弱连接”，也可以称为是“长程连接”，因 为它们将网络中相距较远的节点连接起来。小世界模型可以通过将一小部分边 “重连接”( r e w i r i n g ) 来建立。“重连接”过程可以描述为：依次选择每条边， 按概率p 将该边的一端随机地连接到网络中一个随机选择的节点上。 r e g u l a r 毫；獭羽l 峭嘲诩 r a n d o m 舷胁幽 势= 0 9 - p = i n c r e a s i n gr a n d o m n e s s 图1 1 三种网络模型的连接机制 当网络的度分布曲线随着后的增加时，并没有出现衰减趋势，曲线反而更加 平稳。这类网络叫做异质网络。无标度网络是另外一类较特殊的网络模型，这类 网络的度分布为幂律分布曲线( 尸( j j ) 0 ； 日( ) 为系统中节点之间的耦合函数；l = ( i ) 吼川刈表示网络的拓扑结构且满足 耗散耦合条件 ! t i = 0 。在图论的研究中，网络的拓扑结构三也称为图的拉普 绪论 拉斯连接矩阵。为了简化起见，通常假设网络中不存在孤立的节点即网络是一个 连通图结构，则三成为一个不可约的矩阵。当耦合时间步t 专o 。时，如果系统中 的节点满足： 誓( f ) 专x 2 ( t ) - - + 专s ( t ) ( 1 3 ) 则认为网络达到完全同步状态。根据耗散耦合动态方程的条件，不难发现 s ( f ) 吼再一定是满足j ( f ) = 厂0 ( f ) ) 的单个孤立节点的解。 研究人员最早主要关注复杂网络在什么样的情况下能够达到完全同步状态。 而网络能否最终达到完全同步状态则完全依赖于对网络完全同步状态的稳定性 分析。如果网络的同步状态是稳定的，那么系统可以从任意一个初始时刻状态出 发，系统都能达到全局的网络完全同步。p e c o r a 1 1 等人对随机耦合网络上完全 同步的稳定性问题进行了开创性的研究提出了主稳函数( m a s t e rs t a b i l i t y f u n c t i o n ，m s f ) 方法，得到的结论是网络完全同步状态是否稳定与耦合强度仃 有关，由网络同步的主稳函数可以得到使得网络可以达到完全同步的仃取值区 间，这个区间越大，说明网络越容易达到完全同步，网络的同步化能力 ( s y n c h r o n i z a b i l i t y ) 也越强。网络的同步化能力可以用网络的特征比率来刻画， 特征比率月定义为拉普拉斯矩阵的最大特征值五。，与第二小特征值无的比值 该比值越小，说明网络的同步能力越强。通过研究各种网络的拉普拉斯 矩阵的特征谱，研究人员探讨了各种网络拓扑，如小世界网络和无标度网络，对同 步稳定性的影响。下面将介绍规则网络、小世界网络和无标度网络这几种典型网 络的同步性能。 对于规则网络上混沌振子同步的研究已经有很长的历史 1 2 】。研究中使用的 典型规则网络可以描述如下：网络由个节点组成，节点顺序排列在一个环上， 每个节点与它在环上的2 后个最近邻节点相连接，因此网络包含的边数量为似。 这种规则网络的特征值可以写为 1 3 - 丑：2 k 一2 亨 丝坚坐 ( 1 4 ) = 。 一 ，= 1 y 通过级数展开可以得到关于如和如的近似值为： 见2 x a k ( k + 1 ) _ ( 2 k + 一1 ) 2 3 n 2 如( 2 k + 1 ) ( 1 + 2 ( 3 r e ) ) 一般情况下，对于规则网络有k n ，在这种情况下， 成： r ：( 3 n - + 2 ) 一n 2 2 万3 k ( k + 1 1 4 ( 1 5 ) 特征比率尺可以近似写 ( 1 6 ) 绪论 公式( 1 6 1 表明r n 2 ，说明规则网络的同步性能很弱。实际上很难观察到通过 规则网络耦合的振子达到完全同步状态，取而代之的是振子通过相互作用生成复 杂的振动模式 14 】 b a r a h o n a 等人 1 3 】通过摄动理论( p e r t u r b a t i o na n a l y s i s ) 分析了在规则网络 中添加长程边形成的小世界网络的拉普拉斯矩阵特征值。初始规则网络具有 个节点，每个节点连接到最近邻2 尼个节点，向网络中添加n s 条长程边以生成 小世界网络。设小世界网络的拉普拉斯矩阵为三= r + f ，其中r 是初始的规则 网络的拉普拉斯矩阵，r 是重连边的随机拉普拉斯矩阵，在r 中值为0 的元素 在r 中以概率见= 2 s ( n - 2 k 一1 ) 为1 ，以概率1 一p 。为0 。当小世界网络满足条 件热 1 和夕3 k - 3 的例子。与分类 不同，聚类不需要依赖事先定义的类和带符号的训练实践。所以聚类分析是观察 式学习，而不是示例式学习。本节将首先介绍数据的特征选择、特征提取方法以 及常用的相似性度量标准；然后对现有的数据聚类算法进行分类。 把相似的数据对象通过一定的分类方法分成不同类别的过程称为聚类。由聚 类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，与 其他聚簇中的对象则存在较大的差异。典型的聚类过程为： 图1 4 典型聚类过程 为了更加详细的阐述数据聚类方法，不妨假设原始数据集x 含有个数据点 x i = ( x i 砀) ，i = 1 ，n ，其中誓用来描述数据点的特征向量，d 为特征空间 7 绪论 的维数。通常情况下，聚类分析所使用的数据特征集合也被认为是一个n d 的 特征矩阵。 聚类的第一个步骤是数据集的特征选择问题。到目前为止，还没有任何一种 普适的理论方法能够对任何特定条件下的数据集进行特征选取。人们一般只能根 据先验经验去收集大量关于数据集的信息，利用这些数据集的特征信息设计聚类 系统。通过对原始数据集所有可能的数据特征仔细的调研和数据的变换，可以大 幅的改进聚类的结果的准确性。选取好的数据特征进行聚类研究，往往可以得到 非常简明且易于解释的聚类结果；相反，当选取的数据特征较差时，即数据特征 不能够很好的描述数据集本身的性质，那么最终得到的聚类结果也会非常抽象， 没有实际意义。图1 5 给出了一个简单的示例。二维空间中的数据点形成了一个 曲线的聚簇，数据点到坐标原点的距离近似为常数。若选取在笛卡尔标准坐标系 下表示数据集，由于数据点的分布并不紧凑，导致许多常用的聚类算法将会把数 据点聚类成两个甚至两个意义上的聚簇。但是，如果在极坐标系下表示数据点， 则可以看出数据点非常紧密的聚集在一起，运用聚类算法，很容易得到一个自然 的聚簇。 l 气， 融毒： 秘，s 7 争? 岛 ： ：毒 毛熹产：p ：。：p ：f ，2 舛 ，! ： ：芰f ：牙譬一 一 ： 图1 5 数据点到原点距离近似为常数的曲线状聚簇 获得理想的聚类结果除了需要尽可能选取完备的数据特征外，数据点的相似 性度量方法同样至关重要。不同的相似性度量方法可能会导致不同的聚类结果。 由于存在大量的数据特征类型，因此，需要仔细的选择出一种合适的相似性度量 方法。其中，基于距离的度量准则在计算两类不同数据模式的相似性时，被人们 普遍采用。下面，我们将介绍基于距离的相似性度量方法。首当其冲的是欧氏距 离( e u c l i d e a nd i s t 撇o e ) 法，其表达式为： 畋( 誓，一) ：f 至( 飞七) 2 於 ( 1 9 ) k = l 欧氏距离计算方程为基于闵可夫斯基( m i n k o w s l 钮 ) 准则的相似度量函数在p ：2 时的特殊情况： 心( ) ：f 氟厂硝1 邝 ( 1 1 0 ) 绪论 欧氏距离的相似性度量准则常被用在二维或三维数据的特征空间中，当数据分布 呈较紧凑的球状时，欧氏距离能够很好的评估两个不同的数据点间的相似性大 小。当数据的维数比较高时，运用基于闵可夫斯基( m i n k o 榔蔚) 准则的相似性 度量方法，数据点间的相似性计算时间复杂度会大大提高。这种情况下，可以考 虑标准化选取的数据特征、计算数据点间的线性相关系数、数据特征变换等方法 来解决 4 1 。还可以使用马氏( m a h a l a n o b i s ) 距离来计算数据点间相似性： d m ( 誓，x ，) = ( 薯一x j ) z - 1 ( 墨一x ，) r ( 1 1 1 ) 其中假设薯、_ 为数据点f 和，的行向量特征，为数据集特征的协方差矩阵； 九( ，) 根据两个数据点间的方差和线性相关程度，计算它们的相似度。另外两个 关于距离或相异性常用度量准则为坎贝拉( c a n b e 玎a ) 度量和捷克洛夫斯基 ( c z e k a n o w s k i ) 系数。这两个度量标准都只对非负的变量定义。其表达式为： 坎贝拉度量：d ( t ，_ ) = 多照x ；生, k 二+ x 爿j , k c 2 ， o ，、 z 乙m i n ( x f ，k x 一 捷克洛夫斯基度量：d ( x ，x ，) = 1 一号一 ( 1 1 3 ) 厶l 蕾，k + ，k j k = l 当聚类的对象不能由有意义的d 维变量表示时，常根据某些特征的存在与 否，将各对象进行两两相互比较 4 2 。相似的对象比不相似的对象有更多的共同 特征。一个特征的是否存在，可以从数学上引进一个二值变量来表示，当该特征 存在时，令这个变量的取值为1 ，特征不存在时，则令它取值为0 。将两变量间 的关系表示为列联表的形式，再利用基于列联表的通用相关系数公式求得两变量 间的相似性。 到目前为止，没有任何一种聚类方法能够普遍适用于揭示各种各样的数据集 的内在结构。根据数据在聚类算法中的积聚规则，聚类算法大致分为基于划分的 方法、层次方法、基于密度的方法四类，如图1 6 所示。 9 绪论 图1 6 聚类算法分类示意图 划分方法 这种方法首先要给定需将数据划分成的类数目并创建一个初始划分，然后采 用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分从而到达最后 聚类的目的。虽然这类方法具有线性时间的高效特点，但是需要预先设定一个需 要划分成的类的数目，而且只能识别球状的类。基于划分的聚类算法需要预先指 定聚类中心或聚簇的数目；然后通过反复的进行迭代运算，逐步降低目标函数的 误差值；随着目标函数值的收敛，最终得到聚类结果。这类方法可以进一步分为 基于概率的聚类算法、k - m e d o i d s 算法、k m e a n s 算法以及基于网格和图论的聚 类算法等 2 7 。 层次方法 这种方法使用数据的连接规则，对给定数据对象集合进行分解，从而形成一 个层次序列的聚簇。根据层次的分解如何形成，层次的方法可以分为凝聚的和分 裂的 2 7 。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的 一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个( 层次的最 上层) ，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始 将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直 到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次方法的缺陷在 于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤消，因此带来后续更大的 误差。根据度量两个聚簇间的相似度的标准不同，又可将层次的聚类算法分为 s i n g l e - l i n k ，c o m p l e t e l i n k 和a v e r a g e l i l l l 【聚类算法 2 8 。其中根据两个聚簇中 最近的两个数据点问的距离来评价聚簇的相似程度的s i n g l e l i n k 方法在实际项 1 0 绪论 目中应用的最为广泛。c o m p l e t e l i n k 和a v e r a g e l i n k 聚类则根据两个聚簇中的 数据点问最远距离和平均距离来度量这两个聚簇的相似度。 基于密度的方法 由于上述两种方法都是依赖于数据之间的距离的，因此一般只能识别球状的 数据类。从而基于密度的聚类方法被提出【2 9 】，其主要思想是：只要邻近区域的 密度( 对象或数据点的数目) 超过某个阈值，就继续聚类。也就是说，对给定类 中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样 的方法可以用来过滤孤立点数据，发现任意形状的类。但是这类算法具有较大的 时间复杂度，而且需要对密度参数和噪声阈值进行仔细的选择，选择不当则导致 聚类失败。基于密度的方法又可以分为连接密度方法和密度函数方法两个子类， 其代表性的聚类算法有d b s c a n ，g d b s c a n 和d e n c l u e 等 2 7 】。 基于模型的方法 这类方法为每个数据类假定了一个模型，然后利用机器学习算法来寻找数据 对给定模型的最佳拟合。这类方法虽然精确度较高但同时时间复杂度也较高而且 一般无法获取显式的规则，主要包括基于人工神经网络方法和基于进化理论的方 法。利用人工神经网络进行聚类的典型代表方法为s o m ( 自组织映射) ，该方法 将原始数据点的聚类中心映射到二维的平面上，在二维的平面上实现对数据对象 的聚类。在基于进化理论在聚类算法的研究中，使用的较为广泛的是遗传算法、 模拟退火等方法。遗传算法通过选择、交叉、变异三个遗传算子不断迭代优化得 到最终的聚类结果；模拟退火则通过引入一个扰动因子，把数据点从当前所在类 别分配到另外一个随机的类别中，不断优化聚类的结果。这类算法对经验参数具 有很强的依赖性，且时间复杂度也比较高。也有研究人员将上述算法混合应用， 在此不再累述，具体可参见附录 2 8 1 。 1 2 4 复杂网络中的聚类方法 基于复杂网络的聚类方法的核心思想是通过分析网络的拓扑结构、网络的动 力学行为来发现隐藏在复杂网络结构下的社团聚簇 3 8 。复杂网络的聚类方法主 要分为基于优化的方法和基于启发式的聚类方法。其中基于优化理论的复杂网络 聚类方法主要包括谱分析方法和局部搜索方法以及近年来得到研究人员广泛关 注的a p ( a f f i n i t yp r o p a g a t i o n ) 聚类方法 3 9 1 。 谱分析方法最早被用来解决在图论研究中关于图的分割问题。假定无向图g 含有个节点，其对应的拉普拉斯特征矩阵三是一个n n 的对称矩阵，则网络 节点f 的度可以用矩阵三对角线上的元素厶，来表示，同时网络节点i 和节点，的 连接关系可以利用矩阵三的非对角线元素岛来描述：岛= 一1 表示两个节点之间 存在边的连接；反2 _ f l , ul u = 0 。谱分析方法的基本思想是利用网络的拉普拉斯连 接矩阵三的第- d , 特征值对应的特征向量，将网络划分为两个社团 5 9 】。该方法 绪论 的主要缺点是基于递归的二分策略每次只能将网络划为平分的两个社团，如果网 络所含聚簇的数目大于两个，那么只有通过重复迭代算法才能得到最后的社团划 分结果；另一方面，该方法需要借助人工的先验知识来判断算法的收敛条件。 典型的基于局部搜索的方法有n e w m a n 快速算法【3 4 】、g u i m e r a