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

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

2.3 NetClus算法

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

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

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

2.3.1排名函数

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

1.简单排名

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

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

2.权威排名

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

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

其中，为了归一化，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的概率定义如下。

其中，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的生成概率由子网属性类型的条件排名分布计算得到：

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

其中，参数λ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）的局部最大。

我们利用如下两个迭代公式，通过EM算法获得p（k），设置初始值

当计算好每个聚类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的后验概率可由如下式子计算得到：

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

2.3.5实验结果

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

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

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

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

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

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

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

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

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

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