基于社会网络的跨文本同名消歧

陈晨,王厚峰

(1.北京大学计算语言学教育部重点实验室,北京100871;2.北京大学信息化建设与管理办公室,北京100871)

引言

在互联网上找人是最常见的搜索。但是,人名重名现象十分普遍,返回的结果往往含有大量相同名字的网页。我们曾搜索“李小鹏”,在结果去重后,选取前55个搜索结果,发现这些网页中的“李小鹏”代表了9个不同的人。

跨文本人名同名消歧是判断不同文本中的相同人名是否指称现实中相同实体的过程。跨文本人名消歧是准确获取感兴趣人物相关信息的基础,对多文本摘要(Multi-text summary)、信息融合(Information fusion)等具体应用也有重要的作用。但跨文本人名消歧是一项具有挑战性的任务,主要有以下几个方面的原因。其一,重名的人数具有随机性,有的名字的重名人可能成百上千,有些可能没有重名;其二,不同名字重名不遵循统一的分布;其三,文本中存在与人物实体无关、而字串相同的噪音。

随着多文本处理应用的日益广泛,跨文本同名消歧研究也受到了越来越多的重视。SemEval-2007评测设立了针对英文的网络人物搜索 Web People Search(WePS)[1],2009年的WWW国际会议,再次设立了这一评测任务,在 CLP SIGHAN 2010上也首次设置了中文跨文本人名消歧任务。

本文针对中文跨文本人名同指问题,使用社会网络实现同名消歧。首先从文本中抽取与待消歧人名相关的实体,并利用实体共现信息构建社会网络,再对社会网络进行划分,最后把具有相同社会网络子图的文本聚为一类,代表相同的名字指向相同实体。

本文结构如下：第1节是相关工作的介绍;第2节给出基于社会网络分析法的人名消歧框架;第3节介绍了社会网络的获取方法和实体关系权值的计算公式;第4节描述了基于社会网络的聚类算法,包括多种图划分准则以及聚类停止条件;第5节介绍了实验数据和评测标准,同时给出并分析了实验结果;第6节是本文的小结和今后研究工作的展望。

1 相关工作

Bagga和Baldwin于1998年首先提出了跨文本的同指(Coreference)消歧任务[2]。他们对每个文本形成待消歧名字的同指链,并为同指链生成简单摘要;然后,将各个摘要用特征向量来表示,在此基础上,通过聚类方法将具有人名同指关系的文本聚在一起。Mann和Yarow sky通过学习模板在丰富的特征空间中自动提取人物实体的个人信息作为特征,进行跨文本的同名消歧[3]。Fleischman和Hovy提出使用最大熵模型来计算两个名字指向同一实体的概率,并使用改进的层次聚类算法对同名的人名进行分类[4]。Malin创建社会网络图来实现人名消歧,第一种方法是基于局部社会网络计算相似度并采用层次聚类进行划分;第二种方法将全局社会网络用相似度进行严格划分,再采用随机游走的方法实现类别划分[5]。郎君等依据同名不同人物具有不同社会网络的思想,对检索结果中有重名的人名进行消歧[6]。Pedersen和Anagha则研究了实体数目(类的个数)的判定问题[7]。

社会网络分析法是在人类学、心理学、社会学、数学以及统计学等领域中发展起来的,已经经历了约60多年的历史。至今,社会网络分析法早已突破了社会学领域的范围,为其他领域的学者所采用。“不同人物、不同社会关系;相同人物,相同社会关系”的思想本身体现了“类聚”特点,本文将社会网络分析方法引入到同名消歧中,并使用谱聚类实现了基于社会网络关系的聚类,同时,比较了不同社会网络边权值和不同图划分准则对同名消歧结果的影响以及不同模块度停止条件阈值下的人名消歧结果。

2 基于社会网络的人名消歧

处于现实社会中的每一个人都有自己的社会关系和社交活动圈：如可能接触到的人、活动的场所以及所属的机构等,这就构成了社会网络。社会网络分析中的概念“自我中心网络”和“团块”正是该现象的概括。自我中心网络(Egocentric network)指环绕在自我周围的社会网络,它既包括自我与他人的直接联结,也包括这些与自我联结的他人之间的联结。团块(Clique)是一个群体中的子群体,其成员彼此间的平均紧密程度超过对其子群体外(大群体之内)的其他成员的平均紧密程度[8]。

应用社会网络分析法实现人名消歧,首先分析同名的人各自对应的自我中心网络和团块,如果对应的实体不同,所具有的社会网络往往不同,因而很可能属于不同的团块,并拥有自我中心网络的特点,以此为依据,可以通过集团划分来区分不同实体。当然,有相同名字的两个人也有可能出现在相似的社会网络中,但概率是非常小的,本文忽略这种情况。

假设D={d1,d2,…,dn}表示文本集合,其中的每个文本di(0＜i＜n+1)都含有某个相同的人名Name。在集合D中,Name所指称的实体表示为集合E={e1,e2,…,em},其中的每一个实体ej都有与之对应的社会网络关系Mj,Mj可以理解为与ej相关的实体(主要是人和机构)的集合。基于社会网络的人名消歧,首先是从文本集合D中提取信息,建立Name的总的社会网络关系图M,然后使用社会网络分析方法分析出它的子图M1,…,Mm,并将待消歧文本d1,d2,…,dn对应到各个社会网络子图M1,…,Mm中,将属于同一社会网络的文本聚为一类。在“不同人物、不同社会关系;相同人物、相同社会关系”的假设下,为社会子网M1,…,Mm对应的实体e1,e2,…,em找到对应的文本子集Dj,其中Dj⊆D,Dj∩Dk=Ф,1≤j,k≤m,j≠k。

基于社会网络的同名消歧框架如下：

1)第一步：文本预处理;对集合D的每个文本d1,d2,…,dn进行预处理,包括分词、词性标注、命名实体识别等;

2)第二步：社会网络的获取与表达;在d1,d2,…,dn中根据社会网络获取原则来构建同一人名的初始关系网络M;

3)第三步：社会网络聚类;在Name的社会网络关系图M上采用图分割的算法来实现图聚类算法,得到M的社会网络关系子图M1,…,Mm;

4)第四步：社会网络映射;将形成各个社会关系子图 M1,…,Mm映射回到文本集合D={d1,d2,…,dn}上,使得每个文本di对应一个子图Mj,映射到同一个子图的文本代表它们包含的人名Name指称同一实体,从而实现人名消歧。

经过社会网络获取步骤,系统可以构建一个初始的社会网络图,称为基本网络图,为无向图,图中的节点表示与Name有关联的实体,图中的边代表实体与实体之间的权值(相似值)。当且仅当两个实体在同一个文本中共现时,图中的这两个实体对应的点之间才存在连接边,如图1左图所示。社会网络图聚类是对基本网络图的划分。图1的基本社会网络图经过聚类得到的社会网络图划分如图1右图所示。

图1 社会网络聚类示意图

根据社会网络图中的子图来划分各个实体的类别,以实现社会网络映射。依次查看包含人名Name的文本,统计文本中包含的实体类别,选择最多的实体类别作为该文本的类别,从而实现文本类别的划分,完成聚类。

下面将详细介绍社会网络获取、表达和基于社会网络的聚类算法。

3 社会网络表达

在文本预处理之后,可以得到文本中的人名和机构名列表,然后将包含人名、机构名数目不小于2的文本选择有效文本,从有效文本中获取社会网络关系。

社会网络的构造可以看成是构造节点关系矩阵的过程。每个节点对应于一个名字(人名和机构名)。如果两个节点同现于一个文本中,其间就有关系,依据其出现的上下文来计算之间的权值,本文考虑了三种不同的权值方法。

1)共现作为权值

如果两个节点共现于同一个文本,这两个节点就相似。假设用x1…xz表示节点,M1ij表示 xi与yj的权值,则权值计算公式如(1)所示：

2)共现频次作为权值

用实体与实体共现的次数作为权值,计算实体关系权值M2ij,计算公式如(2)所示：

3)共现频次对数作为权值

对共现次数矩阵进行指数化调整,计算对数型关系权值M3ij,计算公式如(3)所示：

其中,M2ij为共现频次,c为常数,作为调节因子。与权值方法2)相比,采用共现频次的对数作为权值可以平滑数据,对统计结果和概率估计进行必要的调整和修补,以降低由于数据稀疏现象带来的统计误差。

4 社会网络聚类

社会网络是由若干个“团块”(Clique)构成,每个“团块”内部节点之间的连接相对紧密,而不同“团块”之间的连接则相对松散。社会网络聚类与一般意义上的聚类不一样,社会网络聚类可以认为是“团块”的发现过程,而一般的聚类更多是以共同特征为基础对节点聚类。从构建的网络结构中发现团块有很多种方法,比较典型的有谱聚类的图分割方法。谱聚类算法建立在谱图理论基础上,其本质是将聚类问题转化为图的最优化划分问题。与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。图划分的最优解已经证明都是NPC问题。一个比较可行的方法就是把问题松弛到连续区间,然后利用谱图理论求得其松弛解。谱图理论将图划分问题转换成求解相似矩阵或Laplacian矩阵的谱分解[9]。

4.1 图划分准则

图划分的基本原则是：子图内的权重和最大化和各子图间的边权重最小化。

图划分可以分为2-way和任意 k-way,2-way划分是每次将图划分为两个子图,k-way则将图划分为k个子图。由于无法事先确定合理的k值,任意给定k会因为选择不当而得到比较差的聚类结果。因此,通常情况下按2-way迭代谱聚类更适合。常见的2-way划分准则有Minimum cut,Average cut,Normalized cut,Minmax cut,Ratio cut等。很多实验表明,Normalized cut比Average cut得到的结果更好[9],Minmax cut与Normalized cut具有相似的行为。在本实验中,分别尝试了Minimum cut,Normalized cut和Ratio cut三种方法。

1)最小割(Minimum cut)准则

对一个连通图,将一组边去掉后,可以将原来的图分成两个独立的连通子图。如果少去掉一条边,整个图仍然保持为连通的,则称去掉的这组边为割集。去掉割集后,图G便划分为两个独立的子图A和¯A,这也称为割。割值按公式(4)计算：

一个连通图有多组割集,不同的割集对应的割值可能是不相等的,割值最小的割称为最小割。Wu和Leahy提出以最小割来划分图G,产生了较好的效果[10]。但是最小割准则容易出现歪斜分割,即容易把小区域分割出来。

2)规范割(Normalized cut)准则

为了避免斜歪分割问题,Shi和Malik提出了Normalized cut(Ncut)方法[11]。其规范化割值的计算方法如公式(5)：

di表示第i个节点的度。最小化Ncut函数称作规范割准则,该准则不仅能够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。

3)比例割准则(Ratio cut)

Hagen和Kahng提出了比例割目标函数Rcut[12],如公式(7)：

4.2 谱聚类算法

按照使用的划分准则,可将谱聚类算法分为2-way谱和k-way谱两类。2-way划分准则采取了迭代方式,如果希望得到k个子图,则只需要经过k-1轮的划分。本文将2-way运用到基于社会网络的人名消歧中,主要参考了SM算法[11]。

SM算法(二分递归算法)如下：

1)第一步：建立无向图G,根据图G构造矩阵相似W和对角D,对角矩阵表示各个节点的度;

2)第二步：计算(D-W)x=λ Dx第二小特征值及其对应的Fiedler向量v2;

3)第三步：升序排列v2中的元素,将重新排序的v2分成两个部分,使得到划分的 Ncut(A,¯A)值最小;

4)第四步：转到第二步再进一步划分,直到满足停止条件。

4.3 模块度停止条件

2-way的谱聚类算法与聚合式聚类一样,构造一棵聚类树,只不过是按自上而下方式。所以也同样需要确定停止条件的问题。停止条件对聚类效果好坏有很大影响。Newman等人定义了一个用以评价网络划分质量的指标,称为模块度(Modularity)[13]。模块度的定义为：假设网络已经被分裂成k个子图,定义k×k维的矩阵,其中元素b=[bij]n*n表示子图i和子图j之间的边数占总边数的比例,表示与第i个子图中的节点相连的边在所有边种所占的比例。在此基础上,用公式(8)来定义模块度的衡量标准：

如果子图内部边的比例不大于任意连接时的期望权值,则有Q=0。Q的上限为1,而Q越接近1,说明团块结构越明显,即图划分的效果越好。实际网络中,该值通常位于0.3～0.7之间,因此,可以通过设置一个模块度阈值来决定是否停止聚类。

5 实验结果与分析

5.1 测试集与评价指标

本文采用CLP 2010的中文人名消歧任务提供的训练数据作为评测数据。该语料对每一个选定的人名,按“字串”匹配的方法从新华社的语料库中抽出含有该字串的文本,该“人名”的文本集。所提供的数据共有32个中文人名的文本集,每个文本集含有100～300个文本。如果文本中对应的字串不表示人名(例如,“高明”字串出现在某个文本中,但并不是人名,而是形容词),则应该标记为“丢弃”。在所提供的32个人名数据集合中,不同人名指称的实体数各有差异,但都在4～166之间,其构成分布具有很强的随机性。

社会网络利用的是实体之间的相互关系。如果某个文本中只出现了所给的人名,而没有出现其他实体,就不能使用社会网络,本文所用的方法排出了这样的文本。

在评测时,CLP 2010使用B_Cubed和P_IP指标,本文也采用这两种指标评价实验结果,计算公式如下：

1)B_Cubed指标

首先对参与聚类的每个文档分别求出可得到的最大的Precision和Recall,然后再求出平均值作为聚类结果的Precision和Recall。F-measure采用通常的计算公式计算：

2)P_IP指标

该计算指标对每个类,计算使得值最大的Purity和InversePurity,然后再求出平均值作为聚类结果的Purity和InversePurity。F-measure采用通常的计算公式计算：

其中,S为标准聚类结果集合,Si∈S代表标准结果类别集合中的其中一类;R为实际聚类结果集合,Rj∈R代表实际结果聚类集合中的其中一类。|Si|和|Rj|表示集合Si和Rj的大小。

5.2 实验一：聚类对社会网络人名消歧的影响

本文所用的谱聚类工具是 MATLAB中的Spectralib①http：//www.stat.washington.edu/spectral/工具包。为了取得较佳的社会网络聚类效果,系统在调用SM 算法的Ncut分割函数完成谱聚类同时,设置标准类别个数作为社会网络聚类个数,将其实验结果与基本图的实验结果进行比较。基本图直接由图的连通部件划分实体类别,即在基本社会网络图中如果两实体之间存在一条路径互相可达,则这两个实体属于一类。实验结果如表1所示 。其中,B_Cubed 的“#Pre”为精确率,“#Rec”为召回率,P_IP 的“#Pre”为 Purity,“#Rec”为InversePurity,表中以上数据为32个人名实验下的平均值。“#best”代表实验结果评测的F值取得最佳结果时的人名实验结果数。

由表1可以看出,经过聚类后,基于社会网络的人名消歧精确度有很大的提高,B_cubed和P_IP的精确率提升了10%以上,F值也有6%以上的提升,但召回率有1%以上的下降。可能的原因有以下几点：

1)社会网络中的名字有歧义。如果社会网络中的某个名字本身也是指称了不同的实体对象,系统却将其视为同一个实体,这样该歧义名字会将本不连通的两个子图连接形成一个连通子图,从而降低了基本图划分下人名消歧的精确率。基于社会网络的聚类对含歧义名字的连通子图进行划分,可以利用割集理论将上述错连的子图划分开,从而提高人名消歧精确率。

表1 社会网络聚类对人名消歧的影响实验结果

2)社会网络中的名字没有歧义,但是该名字对应的实体确实与待消歧人名对应的不同实体都有关系,如某个单位有两个“李明”。与1)类似,社会网络聚类也可以将关联度低的不同社会网络子图划分开。

3)召回率的下降,主要是不恰当的划分造成的。由于数据集中提取的社会网络比较稀疏,系统会视其为结构不紧凑并进行不必要的划分。

社会网络中歧义现象包括上面1)和2)中提到的两种情况：社会网络中的名字有歧义,称之为“名字歧义”;社会网络中的实体与待消歧歧义人名对应的两个实体都有关系,称之为“关系歧义”,“名字歧义”和“关系歧义”统称为“歧义”。我们对测试集中32个待消歧人名的社会网络歧义现象进行了统计,统计结果如表2所示。统计时,我们默认出现在同一篇文本中的名字仅代表一个实体,表中“多指总数”是指出现在多于一个文本中的实体名称总数;“歧义总数”是指实体名称出现在多个文本中,但这些文本在待消歧人名的标准聚类中却不属于同一类的实体名称数量,也就是“歧义”的数量;“比例”表示“歧义总数”占“多指总数”的比率。“实体关系对”为存在共现的实体对。

“实体”的歧义比例达到19.53%,所以仅仅根据社会网络基本图来进行人名消歧是不准确的。“实体关系对”的歧义比例为3.16%,社会网络聚类对“实体关系歧义”进行分析,对于人名消歧任务是很有帮助的。

表2 测试集中社会网络歧义比例统计

5.3 实验二：实体关系权值计算方法对比

前面第3节介绍了三种实体关系紧密度的计算方式：共现作为权值、共现频次作为权值和共现频次对数作为权值。共现权值矩阵为01矩阵,值为0代表两个实体没有共现,1为有共现。共现频次权值矩阵的元素为两实体共现频次。共现频次对数权值矩阵,对共现次数计算对数值,并加入常数指标c进行平滑。

本实验对将实体关系权值不同计算方法进行对比,使用SM算法,设置歧义人名的标准类别个数作为社会网络聚类个数,在对数化矩阵中设置c=1。实验结果如表3所示。

表3 实体关系权值计算方法实验对比

在32个人名消歧的实验中,有14个人名的聚类实验使用三种实体关系矩阵得到完全相同的结果,平均F值的数值仅有约0.4%的差别,最佳结果人名数也没有特别大的差别。这说明实体关系权值的计算方法对基于社会网络的人名消歧实验影响不大。

5.4 实验三：谱聚类图划分准则函数对比

实验研究不同图划分准则对人名消歧的影响,设置歧义人名的标准类别个数作为社会网络聚类个数 ,将 MiNcut、Rcut、Ncut 图划分准则使用在社会网络聚类的人名消歧实验中,并将实验结果进行比较。如表4所示。

对每个人名测试数据取 Ncut、Rcut、MiNcut三种图划分准则下的最佳结果比较,若Ncut对应的结果在三个结果中的表现最好,则 Ncut对应的#best统计量加1。因此,#best统计量高表明对应的划分准则表现好。根据以上表格可知,从#best值统计量来看,Ncut和Rcut的结果要好于Mincut。加之 Ncut的 F值最高,所以 Ncut又好于Rcut方法。从更多细节来看,在32个人名消歧的实验中,Ncut和 Rcut的#best都是22,其中聚类效果完全一样的有14个,也说明了这两种方法的结果一致性是比较高的。

表4 图划分准则函数实验对比

5.5 实验四：谱聚类停止条件对比

SM算法与自顶向下的层次聚类的过程类似,构造了一颗聚类树,需要定义停止条件来决定聚类树的停止层次,即最终类别的个数。本文4.3节介绍了基于模块度的谱聚类停止条件计算方法。本实验按模块度停止条件进行实验,结果如表5所示。

表5 模块度停止条件实验对比

从实验结果来看,停止条件的效果并不好。由于在实际网络中该值通常位于0.3～0.7之间,我们一共对三个阈值0.41、0.4、0.3进行了实验。在最好结果中,平均精确率和平均召回率大致相等,F值也只有67.94%。在我们的实验中,模块度停止条件的结果并不好,一个可能的原因是使用了统一的模块度阈值。不同的人名需要的模块度阈值可能是不一样的。本文对模块度阈值等于0.41时,共有13个人名的F值低于70%。阈值取值不恰当,精确率和召回率会严重分化,从而导致F值很低。随着精确率和召回率之间的值差越来越小,F值逐渐升高。F值超过80%的人名实验也是13个,所取的阈值可能符合预期。

由实验的结果来看,如果要将社会网络聚类运用到人名消歧中,需要解决停止条件的问题,这也是聚类算法普遍面临的问题。

6 结论

本文研究了基于社会网络的人名消歧。社会网络表示了特定实体之间比较持久的、稳定的社会关系。社会网络可以看成由多个节点构成的一种社会结构,节点通常是指人或组织机构。节点之间的边代表各种社会关系。

在基于社会网络的人名消歧中,将人名消歧看成是社会网络的图划分问题。本文详细讨论了社会网络获取、关系矩阵构造、社会网络聚类、社会网络映射的实现。社会网络聚类主要是采取了谱聚类的方法,介绍了谱聚类中的谱图理论、图划分准则、谱聚类算法及模块度停止条件。最后,针对基于社会网络的人名消歧进行了实验。

今后的工作重点是对社会网络分析功能的完善和社会网络聚类停止条件的研究。同时,采用更好的实体识别模块来提高识别正确率,增加其他类型的命名实体作为特征以及将文本聚类的思想与之相结合,以更好地实现人名消歧。

[1]J.Artiles,J.Gonzalo,S.Sekine.The SemEval-2007WePS Evaluation：Establishing a benchmark for the Web People Search Task[C]//SemEval,2007.

[2]A.Bagga,B.Baldwin.Entity-based cross-document coreferencing using the Vector Space Model[C]//Proceedings of the 17th international conference on Computational linguistics-Volume 1,1998：79-85.

[3]G.S.Mann,D.Yarowsky.Unsupervised personal name disambiguation[C]//Proceedings of the seventh conference on Natural languagelearningat HLTNAACL,2003：33-40.

[4]M.B.Fleischman,E.Hovy.Multi-document person name resolution[C]//Proceedings of ACL-42,Reference Resolution Workshop,2004.

[5]B.M alin.Unsupervised Name Disambiguation via Social Network Similarity[C]//Workshop Notes on Link Analysis,Counterterrorism,and Security,2005.

[6]郎君,秦兵,宋巍,等.基于社会网络的人名检索结果重名消歧[J].计算机学报,2009,32(7)：1365-1374.

[7]T.Pedersen,K.Anagha.Automatic Cluster Stopping with Criterion Functions and the Gap Statistic[C]//Proceedings of the Demonstration Session of the Human Language Technology Conference and the Sixth Annual Meeting of the North American Chapter of the Association for Computational Linguistic,New York City.2006.

[8]Scott J.Social network analysis：A handbook(2nd ed.)[M].Thousands Oaks,CA：Sage.2000.

[9]Ng A,Jordan M,Weiss Y.On spectral clustering：A-nalysis and an algorithm.Advances in Neural Information Precessing Systems 14[C]//MIT Press,2002.

[10]Z.Wu,R.Leahy.An Optimal Graph Theoretic Approach to Data Clustering：Theory and Its Application to Image Segmentation[J].IEEE Trans.Pattern Analysis and Machine Intelligence,1993,15(11)：1101-1113.

[11]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Trans.Pattern Analysis and Machine Intelligence,2000,22(8)：888-905.

[12]L.Hagen,A.B.Kahng.New spectral methods for ratio cut partitioning and clustering[J].IEEE.T rans.On Computed Aided Desgin,1992,11：1074-1085.

[13]Newman M.E.J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2)：026113.