（计算机软件与理论专业论文）基于evs相似度的邮件社区划分方法研究.pdf

摘要 摘要 近年来，复杂网络中社区结构的发现及社会关系知识的挖掘，已经成为数 据挖掘领域的研究热点之一。电子邮件系统中的邮件通信网络是一种较简单的 社会网络，其社区划分问题本质上可以归结为稀疏图的聚类问题。聚类方法的 核心是邻近性度量，因此发掘新的更加有效的邻近性度量方法进而提高邮件社 区的划分质量，对以后的垃圾邮件的识别与过滤以及大型复杂网络的研究，具 有非常重要的意义。 本文以网络社区为背景，对邮件通信网络中的社区进行了重点研究，主要 工作如下： ( 1 ) 提出了一种新的邻近性度量方法e v s ，用于指导邮件社区聚类。通过 学习和研究各种邻近性度量方法以及国内外复杂网络社区挖掘的相关方法，论 文将邮件社区划分转化为图的聚类。首先介绍了邮件特征的向量表示形式、构 建了邮件特征矩阵。在此基础上，使用变形后的极值分布函数模型拟合邮件间 通信特征信息，然后在转换后的信息矩阵上构建e v s 。 ( 2 ) 结合微聚类一宏聚类的技术提出了基于e v s 相似度的邮件社区聚类算 法，验证了e v s 的有效性。本文将余弦、皮尔森等经典的相似性度量方法引入邮 件社区划分中，用于进行对比分析，并且从具体邮件社区的特点来评估邮件社 区的划分质量。 ( 3 ) 实验结果表明，在实际的测试数据集上，基于e v s 度量的邮件社区聚 类算法比基于余弦、皮尔森相似性的邮件聚类方法更加有效，更能够发现高质 量的社区。 本文的研究具有很强的实际应用价值，对垃圾邮件的识别与过滤技术的进 一步发展，大型复杂社会网络的社区发掘以及一些商业应用，都有十分重要的 意义。 关键词：数据挖掘；邮件社区发现；邻近性度量；e v s 相似度；复杂社会网络 第l 页 a b s t r a c t a b s t r a c t n o w a d a y s ，t h ec o m m u n i t yd e t e c t i o ni nc o m p l e xn e t w o r k sa n dt h ek n o w l e d g e m i n i n go fs o c i a lr e l a t i o n sh a sb e c o m eo n eo f t h eh o ts p o t si nt h ea r e ao fd a t am i n i n g e m a i lc o m m u n i c a t i o nn e t w o r k ，w h i c hi sas i m p l e rs o c i a ln e t w o r k ，b e l o n g st ot h e c l u s t e r i n go f as p a r s eg r a p hi nn a t u r e t h ek e yt ot h ep r o b l e mo f c l u s t e r i n gi ss e a r c h i n g f o re f f e c t i v ep r o x i m i t ym e a s u r e m e n tb e t w e e no b j e c t s t h e r e f o r e ，i ti s h e l p f u lo f d e t e c t i n ga n dc o n s t r u c t i n gn e ws i m i l a r i t ym e a s u r e t oi m p r o v et h e q u a l i t yo f c o m m u n i t yp a r t i t i o n w h a tw eh a v ed o n ew i l lb ei m p o r t a n tt or e c o g n i z ea n df i l t e r s p a r na n dd ot h er e s e a r c ho nc o m p l e xn e t w o r k s i nc o n t a c t 诵1w e bc o m m u n i t y , t h et h e s i se x p l o r e st h ec o m m u n i t yo fm a i l c o m m u n i c a t i o nn e t w o r ki nd e p t h t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) p r o p o s ean e wp r o x i m i t ym e a s m e m e n tm e t h o d ，e v s ( e x t r e m ev a l u e d i s t r i b u t i o ns i m i l a r i t y ) ，f o rt h ee m a i lc o m m u n i t yc l u s t e r i n g a f t e ra n a l y z i n gv a r i o u s k i n d so fs i m i l a r i t ym e a s u r e sa n dt h er e s e a r c ho ft h ew e bc o m m u n i t yb o t ha th o m ea n d b r o a d ，w et r a n s f o r mt h ep r o b l e mo f t h em a i lc o m m u n i t yp a r t i t i o na sag r a p hc l u s t e r i n g t h i sp a p e rf i r s t l yi n t r o d u c e st h ee m a i lf e a t u r ev e c t o rt oc o n s t r u c tt h ee m a i lf e a t u r e m a t r i xa n dt h e nm o d e l st h ei n f o r m a t i o no fe r n a i lf e a t u r e su s i n gt h et r a n s f o r m e d e x t r e m ev a l u ed i s t r i b u t i o n b a s e do nt h i s ，w ec o n s t r u c te v s ( 2 ) t ov a l i d a t ee v s ，t h et h e s i sp r o p o s e san e wm a i lc o m m u n i t yc l u s t e r i n g a l g o r i t h mb a s e do ne v si nc o m b i n a t i o nw i t hm i c r o m a c r oc l u s t e r i n gt e c h n i q u e i n a d d i t i o n ，w ei n d u c ec o s i n e - b a s e ds i m i l a r i t ya n dp e a r s o nc o r r e l a t i o nc o e f f i c i e n tt o e m a i lc o m m u n i t yp a r t i t i o np r o b l e m t h e n ，b a s e do nt h ee x p e r i m e n t a lc o m p a r i s o n b e t w e e nt h e m ，w ee v a l u a t et h eq u a l i t yo fe m a i lc o m m u n i t ya c c o r d i n gt ot h es p e c i f i c c h a r a c t e r i s t i c so fe - m a i lc o m m u n i t y ( 3 ) t h ee x p e r i m e n t ss h o wt h a t ，c o m p a r i n gt oc o s i n e - b a s e ds i m i l a r i t ya n d p e a r s o nc o r r e l a t i o nc o e f f i c i e n t ，t h ea l g o r i t h mb a s e do ne v si sm o r ec o m p e t i t i v ef o r d e t e c t i n ge m a i lc o m m u n i t y t h i sr e s e a r c hh a sh i l g hp r a c t i c a l i ti si m p o r t a n ta n du s e f u lt o t h ed e v e l o p m e n to f s p a md e t e c t i n gt e c h n i q u e ，t h ec o m m u n i t y d e t e c t i o no f l a r g ec o m p l e xs o c i a ln e t w o r k s 第1 i 页 a b s n 。a c t a n ds o m eo t h e rc o m m e r c i a la c t i v i t i e s k e y w o r d s ：d a t am i n i n g ；e - m a i lc o m m u n i t yd c t e 圮t i o n ；p r o x i m i t ym e a s u r e ；e v s ； c o m p l e xs o c i a ln e t w o r k 第l l l 页 目录 摘要 目录 l a b s t r a c t 。i i e j 录i v 1 弓l 言1 1 1 研究背景1 1 2 网络社区的特征2 1 3 本文的主要贡献4 1 4 本文的内容组织5 2 邻近性度量和相关社区发掘算法6 2 1 邻近性度量方法一6 2 1 1 欧氏距离6 2 1 2 阂可夫斯基距离7 2 1 3 相似性系数7 2 1 4 共享近邻相似度8 2 1 5 余弦相似度9 2 1 6 皮尔森相似度1 0 2 2 现有算法简介1o 2 2 1 层次聚类方法11 2 2 2 基于重要度分析的算法12 2 2 3 迭代二分法1 4 2 2 4 基于边介数的g n 算法1 4 2 2 5 基于网络三角环的算法。15 2 3 现有算法评价l6 2 4 本章小结l6 3 相关表示与e v s 相似度。1 7 3 1 相关表示17 第页 目录 3 2 邮件特征的向量表示1 8 3 3 邮件的e v s 相似度度量2 0 3 3 1 极值分布一2 2 3 3 2 基本思想2 3 3 3 3e v s 相似度2 4 3 4 本章小结。2 7 4 基于相似度度量的邮件社区划分方法 4 1 基本思想2 8 4 2 基本框架2 9 4 3 性能分析3 2 4 4 本章小结3 2 5 实验与结果分析 3 3 5 1 测试数据集3 3 5 2 实验说明3 3 5 2 1 实验环境。3 3 5 2 2 实验设置3 4 5 3 结果与分析3 4 5 3 1 实验一3 4 5 3 2 实验二3 5 5 4 本章小结3 8 6 总结与展望3 9 6 1 总结3 9 6 2 工作展望一4 0 参考文献 致谢 个人简历、在学期间发表的学术论文与研究成果 第v 页 4 l 4 5 4 6 1 引言 1 引言 现代信息社会中，因特网正以迅猛之势融入到人类社会的各个领域，网络 成为大量信息的形成、中间过程加工和散播流通的主要途径。凭借其信息面涵 盖之广，信息容量之大，网络毋庸置疑地成为最强大的数据资源和信息库。 1 1 研究背景 复杂网络的社区结构发现，已经成为数据挖掘领域的研究热点之一。社会 网络即是复杂网络中的一个代表，其中社区表示根据兴趣和背景而形成的真实 的社会团体，而社区划分能够展现网络的一些本质特征。研究分析社区的成员 构成关系、网络结构【l 2 】特征等，可以更有效地开发这些网络并应用于从事其它 活动项目。与实际生活中受地域限制的社区不同，网络中的社区其实是一个不 受任何地域和空间限制的团体。通常认为网页的生成与链接具有离散性和难预 知性，然而，从宏观上来看，这些网页之间却因为某种类似一致的内容或兴趣 产生了愈加紧密的联系，从而产生了所谓的社区。 网络社区 3 4 1 1 5 l 被主观上视为一个虚拟的群团体，其内部成员之间有着共同 的兴趣爱好、目标或社会关系。研究社区中的信息，深入挖掘社区中的资源， 对社会网络的发展与实际应用具有很重要的价值。在商业营销活动中，社区可 以帮助商家更科学更准确地定位某种商品或某项业务的目标客户( 例如中国移 动有关集团客户和家庭客户的研究) 。社区的发现，能够帮助我们根据网络中 人们的兴趣方向获取更多更有价值的信息。由此得出，对社区结构的研究，将 为信息的发掘与检索提供一条更加高效、方便、快捷的渠道。 现在有关复杂网络社区结构的发掘方法很多，主要包含对页面或关系链接的 分析 6 1 7 1 羽，有关基于图的聚类 9 1 1 1 0 1 ，学习和应用生物智斛1 1 】f 1 2 1 等。这些思想已 经得到相当广泛的应用，例如科学家或研究学者的合著【1 3 1 、文献的参考引用关 系1 4 1 、有关社会网络【1 5 】1 1 6 1 的研究、垃圾邮件的识别与过、滤【1 7 1 1 8 】f 1 9 1 、危机信息 的传播【2 0 】等领域。专家研究证明，网络中的社区结构遵循“六度分离”的特性， 显著符合社会网络中小世界网络【2 l 】【2 2 2 3 1 的基本特征。 i n t e m e t 经迅速渗透到人类社会生活的各个领域，e m a i l 也逐渐成为信息急 第l 页 1 引言 速膨胀的现代社会中人与人之间联系沟通的主要方式。电子邮件凭借其廉价、 方便快捷的优点，已经在所有联系方式中占有极为可观的优势，并且起着不可 或缺的作用。尤其是现在电子邮件已经应用到一些企业或大公司的工作沟通以 及人事资源的管理上。因此，邮件通信网络能够真实地反映人与人之间的社会 关系，比如一个公司的内部员工、某学校同一个学院的老师、同学、或是某个 社团等等。他们之间邮件的往来通常是因为共同的爱好兴趣或某些社会关系， 从而将他们拉进一个社交圈，也就是我们所说的邮件社区。假如我们类比一般 的w e b 社区的探索方法，将电子邮件通信网络划分成若干社区，那么该项工作的 研究将具有以下几方面的价值： ( 1 ) 认识社区内部各个成员的社交圈及邮件动态，从而及时准确地把握邮箱 用户的兴趣取向，进而获取具有价值的信息。 ( 2 ) 分析研究邮件社区的通信特征和行为，寻求垃圾邮件的收发行为的特殊 性与可区分性，为垃圾邮件的识别和过滤打下坚实的基础，卉提高过滤的效率 和准确率。 ( 3 ) 在已经发掘好邮件社区的邮件通信网络中，若一个社区内某成员受到网 络攻击，则可以及时向其它成员发出侵入预警，一定程度上维护了网络安全。 ( 4 ) 剖析社区内部成员的网络兴趣偏好，便于电子邮件系统为用户提供面向 用户的、更加友好周到的、别具特色的服务。 1 2 网络社区的特征 在互联网以及复杂的社会网络中，社区的结构具有普遍性和客观存在性， 并已经得到人们的认可，吸引了一大批学者竟相研究。 我们所研究的复杂网络，通俗来讲，就是基于图论的知测2 4 】将一个系统表 示成一个图。它从其本质的拓扑结构【2 5 】【2 6 】出发，将一个系统中的所有元素都表 示成一个一个的节点，而两个节点之间的边表示这两个元素间存在某种联系。 上个世纪9 0 年代末，该领域的研究学者b a r a b a s i 和a l b e r t t 2 6 1 深入研究了复杂网络 的拓扑结构1 2 7 】，经过实验分析得出一个共识：无标度是复杂网络所具有的一个 重要特性。后来，此问题引起了一批数学和物理背景领域的学者或人士进行进 一步的探索，他们发掘出了在复杂网络中，社区结构还有许多其它的本质特征。 我们着重讲述下面几个： 第2 页 l 引言 ( 1 ) 网络社区的“小世界性质f 2 翻 ； 整体情况下，社区内部节点之间的平均距离比较小，换句话说，一个节点 经过较少的跳转数( 边的数目) 即可到达另外一个节点，这就是所谓的“小世 界特性 。 小世界网络，尤其是社会网络已经成为近年来复杂网络领域研究的热点。 其最初是用来表明“世界其实很小”这一说法。两个根本不相识的人，他们可 以之间可以通过很少的几个他们各自熟识的人，建立起相应的联系。 ( 2 ) 网络社区的“聚簇性质1 2 s 】 ； 该性质表示，两个节点很可能可以通过共同的邻居节点连接起来成为近邻， 可用聚类因子来度量。 ( 3 ) 网络社区的“稠化幂律【冽”； 大量实验和研究的结果颠覆了以前有关“节点平均度数不变 的假定。伴 随时间推移，网络中边的数目将随着节点的增加而非线性递增。时间t 条件j f ， 边数p 与节点数目刀( f ) 之间的关系遵守稠化幂律： 砸) o c 刀( f ) 4 其中，a 1 ，2 。 ( 4 ) 网络社区的“重尾出度 和“重尾入度 分布特征【2 6 1 。 世 丑 咂 拉 节甬l 袄 图1 1 重尾出度分布图 如图1 1 所示，一个节点的出度( 或入度) 是遵循一定的规律而分布的：其 分布情况服从l n 口的幂律，其中n 为在出度( 或入度) 递减条件下，其对应的 节点的秩，a e ( 0 ，2 ) ，并且节点的尾部会随其值的愈小而愈厚重。此类现象在经 典的“首选配置模型 中显得尤其显著。向一个网络中增添新的节点时，在保 证其所带的固定出度连接的条件下，该新节点便会呈现出更多连接的情况。同 第3 页 l 引言 样，其节点的入度分布也符合上述规律。 ( 5 ) 网络社区的“收缩直径【2 8 】 ； 探索得出，在复杂网络中，其社区的有效直径并非之前理论所说的：随着 网络规模的不断扩大而增大，相反却是随之相应的减小。举例来说，在引文关 系网络中，每篇论文即是一个节点，而论文之间的引用关系，可以抽象为一条 有向的边。我们可以通过引用其直接关联的论文，间接地引用该被关联的论文 的参考文献中的文章，从而大大缩短了两个节点间的最短路径长度。 从性质( 4 ) 所述的出度和入度来考虑，同时经过实践检验证明，“重尾出度 的节点恰巧可以作为一个桥梁，从而连接之前并不关联的子网，因此，大大缩 短了网络中节点间的最短距离，其有效直径的收缩性质也得到了进一步验证。 1 3 本文的主要贡献 为了提升网络社区的划分效果，本文针对人们比较熟悉的一种复杂网络一 一邮件通信网络进行了深入的研究，将一些经典的相似度度量方法应用到邮件 社区的聚类中，最重要的工作是，提出了一种新的邻近性度量方法，用于指导 邮件社区划分，从而有效地提高了邮件社区划分的质量。 与以往的研究方法有所不同，本文的主要工作如下： ( 1 ) 问题的转化与数据的表示 本文基于图论，将邮件网络的通信行为归结为稀疏图的问题。通过对邮箱 进行逐一标识，搜集并统计邮件间的通信行为信息，将邮件特征用向量表示， 基于此，构建了邮件( 属性) 特征矩阵，为相似度度量奠定基础。 ( 2 ) 新的邻近性度量e v s 的提出与构建 在邮件特征向量矩阵的基础上，本文结合概率统计学的相关知识，使用极 值分布函数模型经过变形后拟合邮件之间的通信特征信息，进而提出了一个新 的邻近性度量方法e v s ( e x t r e m ev a l u ed i s t r i b u t i o ns i m i l a r i t y ) ，用于指导邮件 社区的划分。 ( 3 ) 聚类效果的增强 使用微聚类一宏聚类邮件社区划分算法验证了新方法e v s 的有效性。实验表 明，在测试数据集上，相比余弦、皮尔森相似度等经典的邻近性度量方法，以 e v s 作为划分依据的邮件社区划分算法能够更加有效地发现高质量的邮件社区。 第4 页 l 引言 并且我们验证了该类基于相似度度量的邮件社区划分算法的适用性与高效性， 无需进行调整，一次性就可以达到良好的聚类效果。 1 4 本文的内容组织 围绕前述研究内容，本文以下内容结构安排如下： 第二章主要介绍了邻近性度量方法和网络社区划分的研究现状。首先详细 介绍了部分常用的邻近性度量方法，如欧氏距离、闵可夫斯基距离等距离度量 和相似性系数、共享近邻相似度、余弦、皮尔森等相似度度量方法，后针对国 内外现有的主要的有关复杂网络社区的结构划分算法进行了研究与分析。 第三章介绍社区划分的基本概念知识和邮箱的向量表示方法，使用变异的 极值分布函数建模邮件通信特征信息，基于此，详细地介绍了e v s 相似性的基 本思想与构造方法。 第四章介绍了基于邻近性度量的邮件社区划分框架。主要介绍了以e v s 相 似度度量为依据与微聚类一宏聚类方法相结合的邮件社区划分方法。 第五章主要是结合微一宏聚类算法验证新方法的有效性。将余弦、皮尔森等 相似性度量方法应用于邮件社区划分进行对比实验，并就实验结果进行分析。 第六章是本文的工作总结和展望。 最后是参考文献、致谢和附录。 第5 页 2 邻近性度量和相关社区发掘算法 2 邻近性度量和相关社区发掘算法 近年来，复杂网络社区的挖掘已经关联到相当广泛的领域的许多知识，例 如网络的拓扑结构模型，并且有很多研究是基于图论的知识、基于信息论【刈、 基于p c a 主成分分析1 3 u 以及基于网络三角环、聚类技术等等。事物之间的邻近 性度量是聚类方法的关键，并且我们将网络社区的结构划分问题转化为图的聚 类问题，因此，认真研究和分析现有的邻近性度量方法【3 2 1 以及已有的网络社区 结构划分方法与涉及的技术，极其有利于我们进行邮件社区的划分以及对其相 关应用的研究。 2 1 邻近性度量方法 聚类方法的核心是如何度量事物之间的邻近性。邮件社区的划分在本质上 也是一个聚类的问题。我们在文中将邮件社区的划分问题基于图的理论归结为 稀疏图的聚类，本节将详细介绍已有的各种邻近性度量方法，主要包括欧氏距 离、闵可夫斯基距离等距离度量和余弦、皮尔森等相似度度量方法。 2 1 1 欧氏距离 最经常使用的距离定义是著名的“欧几里德距离【3 2 】( e u c l i d e a nd i s t a n c e ) ， 简称“欧氏距离 。在二维和三维空间里，该距离即表示两个点之间的距离。 我们将其推广应用到n 维空间上，该距离用公式表示如下： d = k 一而：2 ， = 1 ，2 n 欧氏距离可以简单地衡量相似程度( 例如信号的相似度) ，上述距离值越 小，代表其相似程度越高。 当数据的分布情况比较相似于正态分布，属性之间有所关联的情况下，我 们可以应用欧几里德距离的推广m a h a l 觚0 b i s 距离【3 2 】。该距离将两个向量之 间的相似度距离定义为： m a h a l a n o b i s ( x ，y ) = o y ) 一( x - y ) ， 其中，的第 j 个元素表示第f 个元素的第j 个属性的协方差；同时，d 代表了e ( 协方差矩阵) 的逆。 第6 页 2 邻近性度量和相关社区发掘算法 马氏距离考虑属性之间的区分性与关联性，但过多受极小变化数据的影响。 2 2 闵可夫斯基距离 闵可夫斯基距离3 2 】( m i n k o w s k id i s t a n c e ) 是欧几里德距离的广泛推广形式。 在n 维空间上的具体公式表示为： ft,、lr d 似y ) = i k - y 。l r i 其中，r 是一个可变的参数，随着其值的变化，由上式可以产生许多不同的 距离。如下： ( 1 ) 当，= 1 时，就是曼哈顿距离( 又称为城市块距离) 。其中我们最熟悉 的例如：汉明距离( h a m m i n gd i s t a n c e ) ，它描述的是两个二元向量对象之间的 二进制位中不同位的个数。 ( 2 ) 当，= 2 时，其实就是式子中的l 2 - 范数，也就是常见的欧氏距离。 ( 3 ) 当r = 0 0 时，为厶，盘r 范数( 或：o - 范数) ，它描述的是两个对象或向量 属性之间的最大距离，该距离即为“上确界距离 。该距离可以更加确切地表 示为下式： 、l ， m ，力= l i m 喀l x k r - - i o o |一儿l ，j 。 j 闵可夫斯基距离通常可以用来衡量两个对象在r l 维属性上的相似度，其值 越小，代表两个对象的距离越近，相似度越高。 2 1 3 相似性系数 ( 1 ) s m c 系到3 2 】 最简单常用的一种相似性系数是s m c 系数，其全名为简单匹配系数( s i m p l e m a t c h i n gc o e f f i c i e n t ) ，该度量方法主要是用于描述计算对是否出现( o 或1 ) 的数目。具体定义如下： 渊= 号鬈竽= 石 因此，该系数可以用来发现在是非题目的调查问卷中回答相似的被调查人 员或判定测验中学生是否答案类似。 第7 页 2 邻近性度量和相关社区发掘算法 ( 2 ) j a c c a r d 系数【3 2 j a c c a r dc o e f f i c i e n t ，该系数主要用来解决对象是非对称的二元属性的情况。 将所有的数据对象表示成为一个事务矩阵，抽取其中的两行数据对象作为两个 事务向量。二元属性的值用l 和0 来表示，若0 的情况个数远远大于l 的个数 时，用s m c 方法则认为都类似，在这种情况下，可使用j a c c a r d 系数度量，用 下面等式来定义，表示为符号_ ，如下： ， 匹配的个数 ，= ， 不涉及0 一o 匹配的属性个数 兀+ 石o + 石。 该系数度量中，j 的值越大，相似性越高。该系数与s m c 系数一样，都仅 能表示有关二元属性值的问题，具有较大的局限性。 ( 3 ) t a n i m o t o 系数【3 2 】 上述两种系数都仅能解决二元属性的问题，而t a n i m o t o 系数实际上是一种 广义的j a c 宅a r d 系数，它是推广到多元属性的情况。可以使用于文本数据的分析 与研究。该系数表示如下： 彤( 训) 2 雨丽x y ； 该系数的意义为：e j 的值越大，相似程度越高。可以用来表示两个向量之 间的相似程度，具有一定的适用价值。 2 1 4 共享近邻相似度 共享最近邻( s h a r e dn e a r e s tn e i g h b o r ，简称为s n n ) 相似度【3 2 1 ，它是一种间 接地计算两个对象相似度的方法。 该方法的主要思想是：在高维数据对象空间中，虽然存在低相似度的问题， 并且针对两个不同的簇，其密度的分布情况通常是有较大差别的。但一个对象 的最近的最直接的大部分邻居仍然是通常情况属于同一个类中的可能性极大。 因此我们在定义和使用该相似度的度量时还需要具体考虑具体的对象节点的环 境。 我们可以用s n n 来定义量化两个对象的相似度大小。根本上来说，s n n 相 似度就是如果两个对象是直接近邻，那么该相似度的值就是它们共同的( 除对 方外) 的直接邻居的数目。 第8 页 2 邻近性度量和相关社区发掘算法 如图2 1 所示，其中的两个黑点分别有8 个最近邻居和7 个最近邻居。它们 两个也分别互相包含在其中。图中有4 个灰色的点是两者的共同最近邻居，则 它们的s n n 相似度值为4 。 图2 1 两个点之间s n n 相似度的计算 s n n 相似度考虑到两个节点之间的间接联系，但是并没有考虑到具体边的 权重意义。该相似度的具体计算方法如算法2 1 所描述。 算法2 1 ：s n n 相似度的计算 输入：一个高维空间的所有点。 输出：两两节点之间的相似度值。 l ： 找出所有点的后最近邻。 2 ： i f 两个点石和y 不是互相在对象的如最近邻中t h e n 3 ： s i m i l a r i t y ( x , 力= 0 4 ：e l s e 5 ： s i m i l a r i t y ( x , 力= 共享的近邻个数 6 ：e n di f 2 1 5 余弦相似度 余弦( c o s ) 相似度【3 3 】的几何意义为两个向量之间的夹角的度量，通常情 况下，更多地是用来衡量两个文本之间的相似程度，c o s 度量公式为： 加谳2 珊 该公式的数学意义是通过计算向量x 与y 的夹角余弦来度量两向量之间的 第9 页 2 邻近性度量和相关社区发掘算法 相似性，当夹角越小( 即c o s 值越大时) ，两个向量x 和】，越相似，它们之间 的邻近性就越大、联系越紧密。 余弦相似度的度量比较常见，但更适合于判定文本内容的相似程度或用于 文本聚类。如果某个向量的某一维上没有数据，则c o s 相似度会把该数据假设 为0 ，因此该相似性度量方法对于处理数据比较稀疏的情况，会存在一定的问题。 2 1 6 皮尔森相似度 皮尔逊相关系数( p e a r s o nc o r r e l a t i o nc o e f f i c i e n t ，简称为p c c ) 3 4 】，也称为 皮尔森相似度。它也是一种非常经典的相似度度量方法，已经被广泛地应用到 协同过滤算法中，用于衡量两个用户之间的相似度，并取得了很好的效果。 基本的p e a r s o n 相关性系数，最初是用来判断两组数据中的点是否在同一条 直线上，可以表示为： y x y y x y ， ( x 2 一( x ) 2 ) ( y 2 一( 】，) 2 ) 其中，该函数数学意义是向量x 与】，之间的相关性，如果厂= 0 ，则x 与】， 之间无关， 0 ，则x 与y 之间正相关，r o ，则 与萄之间正相关，p c c ( v f ，劫 0 ，并且在表示其标准的位移一尺度分布形式中，2 = 1 o 。 根据概率统计学的知识可得，在样本数据中，其样本密度表示为： p ( x t x 。) = 兀旯e x p - 2 ( x , 一) 一e x p ( - 五( 毛一) ) 】 接着，对极值分布做其参数的极大似然估计i 剐，其极大似然函数是在当 样本点( x l 、勋硝给定时，关于参数，a 的函数，表示如下： l ( x 。i a ，) = 刀母e x p l - 2 ( x , - l u ) - e x p 卜a ( 一) ) l 我们对该似然函数取对数，对于参数小a 求偏导，当取最大值时( 令 其偏导函数值为0 ) ，估计极值分布的参数、五，得到下列两式： p2 州寺喜时以而) 砉一三喜+ 喜x i e x p c 一互毛，喜一互幸x ，= 。 c 木水， 第2 2 页 3 相关表示与e v s 相似度 可以看出，上述两个方程很难求解。只能采用n e w t o n - r a p h s o n 法，从而通过迭 代求方程的数值解的方法来解方程。该方法的主要步骤如下： ( 1 ) 对方程( 料) 建立一个目标函数，令等式左边的式子等于我们设定的那 一个目标函数； ( 2 ) 通过迭代的方法逐步估计参数值，直至目标函数逼近为0 为止，就得到 了我们的参数a 最终的估计值。 ( 3 ) 代入式子中即可求得z 参数的估计值p 。 通常情况下，我们习惯于采用“最d x - - 乘法 来估计极值分布的参数，但 是发现该方法得到的参数估计值的误差比较大；而对数据规模比较大的实际情 况，像上述步骤一样使用极大似然估计方法( m a x i m u ml i k e l i h o o de s t i m a t i o n ) 则过程相当复杂，仍然存在一定的误差，因此本文中为方便处理采用近似估计。 0 3 2 基本思想 经典的协同过滤思想与研究在2 0 0 8 年有了突破创新的研究方法【4 9 1 一将拉 普拉斯分布用于拟合专家用户对某个项目的评分数据。对某个特定项目的所有 用户评分通常是围绕某个均值分布的，在经典的p c c 相似度度量中，如果两个 用户给一个项目相同的评分，那么计算结果将显示两个用户具有较高的相似度。 但我们更需要考虑的是评分与均值之间的关系：一方面，如果评分接近均值， 只能说明这两个用户和大多数其他人相似，而无法判定两个用户之间是否相似； 另一方面，如果评分与均值相差较大，则该评分对区分用户相似度更有价值， 即一个稀有的评分更有利于我们发现该用户的特点。 现实生活中，我们发现虽然大多数用户对某个项目的评分差别不大，但仍 有个别用户会给出偏高或偏低的分数。换句话说，评分的分布是具有重尾特性 的。为了解决上述问题，用l a p l a c e 随机变量对某个项目的所有用户评分进行建 模，该数据建模方法对协同过滤中评判用户相似度中显现出了很好的效果。 在我们所研究的邮件社区划分中，我们从上述思想中有感而发邮箱与 邮箱之间的通信特征行为也可以抽象成“用户对项目的评分”。一个邮箱与所 有邮箱之间的通信信息，可以看作是对某个项目的所有用户评分。实际上，所 有邮箱与一个邮箱之间的通信联系信息也通常也是围绕某个信息均值分布，并 具有一定的“重尾性质”；然而，这个重尾性质还具有一定的偏重。在一个大 型邮件通信网络中，大多数邮箱之间极少或没有通信联系的，此时，我们获得 第2 3 页 3 相关表示与e v s 相似度 的通信信息极少或没有信息( 值极其接近o 或为o ) ，即说明数据是稀疏的。在 这种情况下，所有邮箱与一个邮箱的通信信息中，它的联系值的均值相对更接 近于“低分 ，同时通信信息值较大并且远大于均值的值有一定量的分布( “评 分 大于均值的值更有意义) 。鉴于邮件通信网络的特殊情况来具体分析，我 们考虑用极值分布来拟合该数据，但是需要进行变形分析。 3 3 3e v s 相似度 在统计学中，通常假设随机变量符合高斯分布，这种假设相当于忽略距离 均值很远的取值。在本文的邮件社区问题中，我们认为，对于某一邮件特征来 说，两个邮箱在邮件特征上的取值x 甜、x f l 越大( 即邮箱和都与邮箱有很 大的直接关联度) 时，邮箱和v j 就越相关( 具有更小的距离或更大的相似性) ， 此时x i i 、x f l 不可忽略，其值对于衡量邮箱间的相似度更有贡献价值；然而当x 打、 石都低于均值时，邮箱和呀相关性极小( 具有相当大的距离或极小的相似性) 。 因此，本文使用一个变异的极值变量( ，口) 对所有邮箱的第，个属性特征值( 列 向量) 进行建模。 极值分布的密度函数的标准定义形式为 g i ，仃) ：土e x p f 型一唧f 型1 1 ( 3 5 ) 仃 口 盯 其密度函数分布图如下图： 图3 2 标准的极值分布的密度函数分布图 第2 4 页 3 相关表示与e v s 相似度 在图3 2 中，图像为t = 0 ，盯= l 时的密度函数分布情况。其中坐标y 轴表示 公式中的函数触l t ，力的值。 为了使该函数符合本文的假设，沿x = t 对函数( 3 5 ) 对称变换得： 如q ) = 击d 掣一e x p ( 荆 阶回 其中，是位置参数，口 o 是尺度参数。当，- - - 0 ，o t = l 时，其图像如图3 3 所示。 其中，坐标x 轴代表魂，坐标y 轴表示觚，i 肋，砌的值。 图3 3 变形后的极值分布的密度函数分布趋势图 邮件特征矩阵第，维的值x l l ，x 2 t ，翰f ，假定它们之间是相互独立的；我 们通过已经进行的详细考察得到这样的结论：使用最大似然方法估计、0 ，需 要采用n e w t o n - r a p h s o n 方法，通过迭代逐步估计参数值来求解，并且存在一定 的估计误差。为方便处理，本文采用近似计算，用下式估计，和田： 届= i 1 ，一 x f ，( 邮件特征矩阵第，维的均值) ， ( 3 7 ) i = i o t = l 。 ( 3 8 ) 在此基础上，我们重新构建邮箱s 的特征向量，称为监督向量，定义如下： t-：-，ys,!,，。，,ys力,n【sgn(x。j。j，(工。，。)，sgn(，。，p，)。，(ji，)f，。，：。，n(：；9) = ，1 一力1 ) ，( t ，1 ) ，( z ，一p ) 事，( ，) ，s = 1 ， 、7 第2 5 页 3 相关表示与e v s 相似度 共甲，s g n ( x , j 一朋j 是：f q - 亏幽双，盹，利问毕图像则图3 4 所不，；j e l lj 商赞删贝瓢 n g i ( x , ) 定义如下： ) = - i n u 鳓硼山h 一k 时 掣一唧( 掣 - 1 + k m 1 一( 掣一唧( 掣) ) - l 式( 3 一1 0 ) 是由式( 3 6 ) 变换( 取对数，取反，平移) 获得。式( 3 9 ) 对贡献 信息做去平均值处理，使不同的贡献信息分列于均值的两侧，如图3 a 所示。其 中，横坐标表示邮件特征矗，的值，纵坐标表示y s , t 的值。 图3 ay s , 1 的图像简图 若邮箱m 在，维上的取值坛，郢、y t , l o 、y t 1 o 的情况，而不太关注y s , l - - o 、y t a _ o ，所以我们将构造相似性 度量函数如下： 删蛳咖鼍y 船s 阻 、厶。| 、厶t j 第2 6 页 3 相关表示与e v s 相似度 若a v s , t ，y 庐l ，则式( 3 1 1 ) 退化为p c c 和c o s ( 已做去均值处理) 。 e v s 相似度的涵义为：相似度s i m i l a r i t y ( v s ，均的值越大，邮箱屹和m 的通信 特征行为越相似，表明它们之间的联系越紧密。我们主要是通过相似度较大的 值来判断邮件之间紧密性，从而根据同一个社区内部的节点行为相似，并且联 系比较紧密，而社区间则联系比较少这一理论依据，更好地进行邮件社区的划 分。 3 4 本章小结 本章重点介绍了邮件特征的向量表示形式，以及邮箱之间的邻近性度量， 最重要的是构造了一种新的适合指导邮件社区划分的度量标准e v s 相似 度。 我们首先介绍了社区结构以及社区的基本概念，并引入了邮件通信网络中 通常采用的社区划分评估标准。 然后，我们详细描述了邮件通信网络中邮件特征的向量表示形式，在此基 础上，提出了使用相似度度量作为邮件社区划分的依据，并转化了部分适合描 述邮箱( 用户) 之间相似度的相似性度量方法。 最后，基于极值分布，在邮件特征向量矩阵上，用变形后的极值分布对每 一维的邮件属性特征( 列向量) 进行建模，构建了邮件监督矩阵，在此基础上， 最终形成了我们新的e v s ( e x a e m ev a l u ed i s t r i b u t i o ns i m i l a r i t y ) 度量方法。 e v s 邻近性度量方法为下章指导邮件社区聚类，进行邮件社区的划分奠定 了坚实的基础。 第2 7 页 4 基于相似度度量的邮件社区划分方法 4 基于相似度度量的邮件社区划分方法 传统的网络社区划分算法都在一定程度上存在一定的局限性。例如：迭代 二分方法需要指定两个子图的大小