《异构信息网络挖掘: 原理和方法》—— 2.3 NetClus算法-阿里云开发者社区

开发者社区> 华章计算机> 正文

《异构信息网络挖掘: 原理和方法》—— 2.3 NetClus算法

简介: 我们解决的第二项聚类任务是针对包含更多类型的对象和链接、更一般性的异构信息网络,对各个类型对象实现软聚类。在异构信息网络中,具有星型网络模式的网络普遍存在且重要,例如以论文为中心的文献网络(例2.6),以带标签事件为中心的标签网络。
+关注继续查看

本节书摘来自华章出版社《异构信息网络挖掘: 原理和方法法》一 书中的第2章,第2.3节,作者( 美)孙艺洲(Yizhou Sun),(美)韩家炜(Jiawei Han),更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3 NetClus算法

我们解决的第二项聚类任务是针对包含更多类型的对象和链接、更一般性的异构信息网络,对各个类型对象实现软聚类。在异构信息网络中,具有星型网络模式的网络普遍存在且重要,例如以论文为中心的文献网络(例2.6),以带标签事件为中心的标签网络。事实上,任何n元关系集合,例如关系数据库的记录可以映射到一个星型网络,其中关系中每条元组都是中心对象,所有属性实体与之相连。

f9c06f55bd612d66cd9167326db51039aa741893ca148b5a29ab70257a21dc7905dbbbf051e4f45d

NetClus被设计用于带有星型网络模式的异构网络。与RankClus的思想一样,NetClus也是一个基于排名的迭代方法,即利用排名提升聚类。与RankClus不同的是:只要网络是星型的,NetClus能够处理任意数量的类型对象,而且产生的聚类结果也不是对单个类型对象的集合,而是具有相同拓扑结构的输入网络的子网络集合。对于一个给定的星型网络和指定的聚类数量K。NetClus输出K个网络聚类结果(见图28)。每个网络聚类都是一个代表网络社区概念的子层,它是由聚集的目标对象所生成的网络,并且附带了每个对象的统计信息。
309ed78c86e170f86cd2b79900633b00ea2f194e

计算两两对象间的相似性非常耗时并且难以在异构网络中定义,取而代之,NetClus将每个目标对象从中心类型映射为一个K维向量,其中K是用户设定的聚类数目。对于每个网络聚类中目标对象的概率生成模型是基于排名的,该模型将一个网络聚类分解为T个独立的成分,其中T是属性类型的数目。在这一节,我们使用例26介绍的星型文献网络来阐述NetClus算法。

2.3.1排名函数

在2.2.1节,我们介绍了排名函数,现在我们将重新审视两个处理带星型网络模式的文献网络的排名函数,并阐述两个用于简单
3-(属性)类型星型网络的排名方法的性质。

1.简单排名

简单排名就是对每个对象根据其类型归一化后简单地统计出现次数。给定网络G,每个对象的属性类型的排名分布定义如下:

d026d2d44dcd8745f8c0f828a1da3370483e4bad

其中,x是类型Tx的一个对象,NG(x)是x在G中的邻居集合。例如,在文献网络中,对刊物使用简单排名计算的排名分数成比例于论文发表数量。
2.权威排名

对每个对象进行权威排名实质上是一个考虑对象权威性在整个网络中传播的排名函数。与双类型信息网络不同,我们需要考虑排名分数在异构信息网络中某条路径上的传播。对于一个一般性的星型网络G,从类型X通过中心类型Z到类型Y的权威分数传播的定义如下。

其中,WXY和WZX是两个相对应的对象类型间的权重矩阵,必要时可以进行归一化。总的来说,一个对象类型的权值分数可能由不同对象类型的分数组合得到。例如PopRank[51]中提出的方法。已有研究表明,通过选择网络中的一条游走路径(或多条路径的组合)计算排名分布的迭代方法是计算表示特定类型对象两两间强度的方阵的主特征向量的有力工具。关于该路径更系统化的定义请参见第4章有关基于元路径的概念。
在DBLP数据集中,依据规则:(1)排名靠前的刊物接受了很多排名靠前的作者的论文;(2)排名靠前的作者在排名靠前的刊物发表了很多好论文,我们定义如下迭代式。

b1f024ff8ece3340258cda6f2041ae6127f24f55

其中,为了归一化,DDA和DDV是对角值与WDA和WDV行之和相等的对角阵。归一化意味着如果一篇论文有多个作者,在计算刊物的排名分数时,就应该考虑这些作者的平均排名分数。由于所有这些矩阵都是稀疏的,在实际操作时,对象的排名分数仅需要根据它有限个数的邻居进行迭代计算。
3.集成先验知识于排名函数

在这两个排名函数中,可以集成特定类型对象中不同聚类的先验分布。例如,用户可能给出几个具有代表性的对象作为先验知识,例如每个研究领域的术语和刊物。先验给定的类型X表达为PP(X|TX,k) (k=1,2,…,K)的形式。首先,先验在网络中按个性化的PageRank[86]方式将分数传播给先验范围以外的对象。然后,传播的先验与由给定排名函数计算得到的排名分布在参数λP∈[0,1]下线性结合在一起,λP值越大,最终的条件排名分布越依赖于先验。

2.3.2NetClus算法框架

首先,我们介绍NetClus的总体框架,并在随后章节详细介绍算法的每个部分。给定聚类数目K,NetClus算法的总体思想由以下步骤构成。

  • 步骤0:产生目标对象的初始划分,并根据这些划分生成初始网络聚类,即{C0k}Kk=1。
  • 步骤1:对每个网络聚类构建基于排名的概率生成模型,即{P(x|Ctk)}Kk=1。
  • 步骤2:计算每个目标对象的后验概率(p(Ctk|x)),然后根据聚类后验概率定义的新评价来调整对象的聚类分配。
  • 步骤3:重复步骤1和步骤2直到所有聚类都不再有显著变化。即,{C*k}Kk=1={Ctk}Kk=1={Ct-1k}Kk=1。
  • 步骤4:计算每个网络聚类中各个属性对象的后验概率(p(C*k|x))。

总的来说,NetClus的时间复杂度与网络中链接个数(||)线性相关。当网络非常稀疏时——大多数应用的真实情况,时间复杂度与网络中对象个数近似线性相关。

2.3.3网络聚类中目标对象生成模型

根据现有研究[4;20;50],在许多真实网络中节点的链接是有偏的,这意味着一个度越高(即高出现频率)的对象被链接的概率越高,高出现频率的对象也容易与更多对象相链接。如在DBLP数据集中,764%的高产作者发表了全部论文的742%,其中5672%的论文在862%的刊物发表,这说明大量的刊物和高产作者通过论文连在一起。我们使用代表对象在网络中重要性的排名分数替代对象的度来扩展获得的启发。符合这个直觉的例子有:被很多低排名网页所链接的(高的度但低排名)网页不大有机会获得来自真正重要网页的链接,在低级别刊物发表许多论文,不会提高这个作者在顶级刊物发表论文的概率。

基于这个观测,我们提出目标对象的概率生产模型来简化网络结构,其中排名高的属性对象更可能共同出现来产生一个中心对象。为了解释这个想法,我们使用星型文献信息网络作为一个实例来演示模型是如何发挥作用的。我们假设每种类型中不相同的对象的数目分别为|A|、|V|、|T|和|D|,每个类型对象的集合记为:A={a1,a2,…,a|A|},V={v1,v2,…,v|V|},T={t1,t2,…,t|T|},以及D={d1,d2,…,d|D|}。
为了简化含有多种类型对象的复杂网络,我们尝试将不同类型的属性对象的影响进行因子分解,然后对目标对象的生成行为建模。对网络因子分解的主要思想是:假设给定网络G,不同属性类型访问对象的概率相互独立。同时,另一个独立性假设:在相同类型对象间,访问不同对象的概率相互独立:

p(xi,xj|Tx,G)=p(xi|Tx,G)×p(xj|Tx,G)
其中,xi,xj??Tx并且Tx是某个属性类型。

现在,给定属性对象在网络G中的排名分布,我们来建立目标对象的生成模型。继续以文献网络为例,每篇论文di由多个作者完成,在一个刊物发表,其题目包含了多个术语。因此,论文di由多个属性对象,记为xi1,xi2,…,xini所确定,其中ni是di链接的数目。论文di的生成概率等于以边的权值为出现次数生成这些属性对象的概率。基于我们所做出的独立性假设,在网络G中生成论文di的概率定义如下。

5958af4a32f8756f9298d080c5efaf7f51507270

其中,NG(di)是对象di在网络G中的邻居,Tx表示对象x的类型。直观地,如果一篇论文发表的刊物、作者、题目包含的术语以很高的概率属于一个聚类,那么这篇论文也有很高的概率属于该聚类。

2.3.4目标对象和属性对象的后验概率

一旦获得了每个网络聚类的生成模型,我们就可以计算每个目标对象的后验概率。现在的问题是假设我们知道了聚类
k(k=1,2,…,K)中每个目标对象的生成概率,那么由聚类k生成的后验概率是多少?这里,K是用户设定聚类数量。由于一些目标对象可能不属于任何网络聚类,我们对每个目标对象计算K+1个后验概率而不仅是K个,其中前K个后验概率是对每个真实存在的网络聚类C1,C2,…,CK计算的,最后一个实际是对初始网络G计算的。现在,G中的目标对象的生成模型充当了一个隐藏模型,与任何聚类都不相关的目标对象在隐藏模型中会得到一个大的后验概率。这一节,我们将介绍计算目标对象和属性对象的后验概率的方法。

根据目标对象的生成模型,目标类型为D的目标对象d在子网络Gk的生成概率由子网属性类型的条件排名分布计算得到:

3ab52b7fc65d82a25970c30f2d430a23a9cb9a45

其中,NGk(d)表示子网Gk中对象d的邻域。在式(2.13)中,为了避免条件排名分数中概率为0的情况,每个条件排名分数首先使用全局排名进行平滑:
1f447779ca86be411a094390932377c2dc299d47

其中,参数λS表示从全局排名中使用排名分布的程度。
平滑[82]是信息检索中一个常用的技术。在语言模型中使用平滑的原因之一是解决文档中术语缺失导致的0概率问题。当使用基于排名的生成模型计算目标对象的生成概率时,我们会遇到类似的问题。例如,网络聚类中的一篇论文可能链接了该聚类中多个排名分数为0的对象。如果我们简单地将目标对象在这个聚类中的概率赋为0,我们会丢失由其他对象提供的信息。事实上,在聚类过程的初始阶段,对象很可能被分配到错误的聚类,如果我们不使用平滑技术,就很难将这些对象重新分到正确聚类中。

一旦在输入网络G有了聚类,记为C1,C2,…,CK,我们可以很容易地根据贝叶斯规则:πi,k∝p(di|k)×p(k),计算每个目标对象(论文di)的后验概率,其中πi,k是在当前给定生成模型下,论文di由聚类k生成的概率,p(k)表示聚类k的相对大小,即论文属于聚类k的概率,其中k=1,2,…,K,K+1。

为了获得每个聚类k的可能聚类规模p(k),我们选择使得对数似然最大化的聚类规模p(k)来生成整个论文集合,然后使用EM算法获得p(k)的局部最大。

a197f4a047262b50776d22f1d7136e32eb7014f3

我们利用如下两个迭代公式,通过EM算法获得p(k),设置初始值
93ee94f79afb6aade3b019a6cccb7ae176b294fe

当计算好每个聚类Ck中的目标对象的后验概率,每个目标对象d可以被表示为一个K维向量:v→(di)=(πi,1,πi,2,…,πi,K)。每个聚类CK的中心可以表示为聚类中所有目标对象在新评价下的平均向量。接下来,我们计算每个目标对象和每个聚类中心的余弦相似度,并且将目标对象分配给最近的聚类中心。现在,目标对象只属于一个聚类,如果di被划分到聚类k,则令p(k|di)为1,反之为0。一个新的子网Gk可以由当前属于聚类k的目标对象生成。整个调整是一个迭代过程,直到目标对象的聚类标签在当前评估下不再有显著的变化。注意,当我们评价目标对象时,我们没有使用隐藏模型的后验概率。我们这么做有两个原因:首先,隐藏模型后验概率的绝对值不应该影响目标对象之间的相似性;其次,前K个后验概率之和反映了一个对象对确定聚类中心的重要性。
属性对象x∈A∪V∪T的后验概率可由如下式子计算得到:
6f262891d63d2a13fe1bc148c559fbbe24fbbd9d

这说明了一个刊物属于聚类Ck的概率等于在这个刊物上发表论文的平均后验概率,对作者和其他属性对象也有类似性质。

2.3.5实验结果

我们研究NetClus的有效性并将之与几个最先进的基准算法进行比较。
数据集我们依据例26从DBLP中构建了星型文献网络。对两个不同规模的网络开展研究:一个是较大(“全领域”)的数据集,覆盖了DBLP中所有的刊物、作者、论文和术语;另一个较小的(从DBLP提取的)数据集,包含了来自数据库、数据挖掘、信息检索以及人工智能这4个领域的20个刊物。(这个数据集也被称为“四领域”数据集)网络中包含了所有在这20个刊物上发表过论文的作者、所有发表的论文以及出现在论文标题中的术语。通过使用“四领域”数据集,我们可以比较不同方法的聚类准确性。
案例学习首先,我们展示在“全领域”数据集上发现的网络聚类的排名分布。我们对刊物和作者使用权威排名,并将刊物的类型视为已知信息,聚类数目为8。表26展示了其中4个网络聚类。同样,可以对子网络迭代地使用NetClus算法来生成更精细的网络聚类。表27列出了从数据库子网络中提取的关于XML领域的精细网络聚类中排名最靠前的5个作者。

70e5d4d3e129fbdb59fd853e64204d32ec1a7003

排名函数研究在2.3.1节,我们提出了两种排名方法,分别是简单排名和权威排名。这里,我们研究从排名分布中获得的低维度评价是如何提高聚类结果,以及聚类结果如何又反过来提高该评价(图2.9)。在本研究中,术语由简单排名方法来排名,刊物和作者由权威排名或简单排名(两种不同的设置)来进行排名。

第一,我们对各个属性类型X计算每个条件排名分布和全局排名分布之间的平均KL散度avgKL(X),用以测量不同条件排名分布之间的相似度:

70782c2f31207bc776c3a33131ab75c3f4e1857a

第二,为了评价在采用排名函数f时每一轮聚类结果的质量,我们计算当前聚类下类内相似度与类间相似度的平均比值作为紧密度Cf来进行评价:
a15da75ace1d2df26459b9d5dab66ac049d648dd

第三,我们跟踪目标对象在每轮迭代中聚类结果的准确性,定义如下:
8d938d9d118c13a87aafd4a9caa2c20101f08f02

换句话说,我们计算被正确聚类的论文的百分比。然而,即便只是在“四领域”数据集中,|D|值也很大,因此我们随机地人工标注了100篇论文到4个聚类,并使用这些论文来计算准确性。

第四,我们跟踪了聚类迭代中生成模型的对数似然式(2.15)。如图29所示,权威排名在各种评价下都优于简单排名。

dbe92ca91d2f028215c0977f5427602afd1cc2b6

准确性研究在这一节,我们将我们的算法与另外两个算法进行比较。一个算法是仅使用文档术语信息的主题模型算法PLSA[25];另一个算法是只适用于双类型网络的RankClus算法。因为这两种算法都不可以直接用于星型模式的异构信息网络,我们对网络进行必要的简化。对于PLSA,仅用网络中的术语类型和论文类型,并且使用NetClus中同样的术语先验知识。表28列出了对论文进行聚类的结果的准确性。
45ea66637eb8589585d1d9ab3783af3c89475c6b

由于RankClus只能对刊物聚类,我们以刊物聚类的准确性来作比较。对于NetClus,聚类标签依最大后验概率获得,并采用标准化互信息(NMI)来评价准确性。因为大多数作者只发表了很少的论文,并且其中可能有不利于正确聚类刊物的噪声,因此我们对RankClus设置不同的阈值来筛选作者子集合。表29给出了结果,其中,d(a)>n意味着我们选择了有超过n篇论文发表的作者来构建双类型文献网络。所有结果都基于算法20次运行。
7d07608ae88e6355931b9a7e388b9ad68e91e04e

可以看出,随着网络中对象类型的增多,NetClus的执行结果比另外两种只使用了网络部分信息的算法更好。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【开源】QuickPager ASP.NET2.0分页控件V2.0.0.4 增加了几个分页算法
================================ 欢迎转载,但是请注明出处。本文出自博客园 。谢谢合作! ================================                最近忙一个项目,没有太多的时间来升级分页控件。
821 0
PostgreSQL · 特性分析 · 统计信息计算方法
一条SQL在PG中的执行过程是: ----> SQL输入 ----> 解析SQL,获取解析后的语法树 ----> 分析、重写语法树,获取查询树 ----> 根据重写、分析后的查询树计算各路径代价,从而选择一条成本最优的执行树 ----> 根据执行树进行执行 ----> 获取结果并返回
1577 0
Android系统应用信息中存储和缓存的计算方法
进行如下操作: 设置->应用->选择一个应用->应用信息 会到达如下界面: 可以看到这个应用占用的磁盘空间。 先说结果,这几项会计算哪些文件(夹)。
781 0
《异构信息网络挖掘: 原理和方法》—— 导读
当下大数据技术发展变化日新月异,大数据应用已经遍及工业和社会生活的方方面面,原有的数据管理理论体系与大数据产业应用之间的差距日益加大,而工业界对于大数据人才的需求却急剧增加。大数据专业人才的培养是新一轮科技较量的基础,高等院校承担着大数据人才培养的重任。
2088 0
网络安全与机器学习(一):网络安全中的机器学习算法
网络安全遇见机器学习,会摩擦出怎样的火花呢?
2982 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载