一种基于Web的大规模人物社会关系提取方法(

1一种基于Web的大规模人物社会关系提取方法姚从磊，邸楠（北京大学网络与分布式系统实验室，北京100871）摘要：Web上的人物社会关系是一类重要的Web信息，如何高效准确地从Web上大规模提取人物社会关系信息，是本文研究的重点。本文提出了一种轻量级的大规模人物社会关系提取方法，并引入模拟退火方法，迭代发掘网页中蕴涵的表述人物社会关系的最小描述模式集合，利用Web信息冗余性，高效、准确地从Web上提取人物关系信息。为验证该方法的有效性，定义了六种人物社会关系，基于一大规模Web人名列表，对这六种关系进行提取。实验结果表明该方法的平均准确率为84.79%，平均召回率为81.69%。关键词:人物社会关系;描述模式;关系提取;模拟退火;Web中图分类号：TP3911引言Web已经成为包含人类社会各种知识的信息库，其规模正在以指数级速度膨胀[1]。其中，人物社会关系信息是一类重要的信息。然而，现有的搜索引擎仅能返回与用户关心人物相关的网页，而与该人物有密切联系的关系人物的信息，用户只能花费大量的时间，阅读分析大量网页才能获得。在基于Web的社会网络分析研究中，人物关系的定义是一个难点，没有很好的方法自动获取人物之间真实存在的社会关系（亲属、朋友等）。当前工作仅以人物在网页中的相对位置作为人物关系定义的标准，其结果具有一定局限性。若以Web中人物社会关系来定义社会网络，进行相关分析，相信会得到更好效果。本文以从Web信息中自动提取人物社会关系为目标，提出一种基于Web的大规模人物社会关系提取方法。对每类人物社会关系，首先以描述该类关系的几个关键词出发，获得一具有此类关系的人物对集合；进而利用该集合进行迭代，结合模拟退火方法，从Web中挖掘出可充分描述此类关系的最小模式集合；在此基础上，利用该集合，对任一Web上出现的人物，高效、准确地提取出与之相关的关系人物，实现人物社会关系提取。2相关研究人物社会关系提取属于实体关系提取的范畴，实体关系提取研究可分为两类，一类基于标注训练数据集，利用训练得到的模型进行实体关系提取[2,3,4]；另一类利用自举的方法，通过迭代发现描述实体关系的模式集合，利用其进行实体关系提取[5,6,7]。前一类方法局限于特定的训练数据集，扩展性不佳，无法应用到Web上的实体关系提取中；后者可充分利用Web信息海量的优势，从中发掘特定的模式集合，用基金项目：国家自然科学基金项目(60435020,60573166,60603056)作者简介：姚从磊，男，1981年生，博士研究生，主要研究方向为Web信息提取，Email:[e-mail].邸楠，男，1981年生，博士研究生，主要研究方向为Web社会网络分析，Email:[e-mail]2于关系提取，但如何保证获得的模式集合以较高准确率和召回率进行关系提取，并保证较高效率，是需要深入研究的问题。ReferralWeb[8,9]是第一个在Web上进行人物发现的系统，其人物间关系由人名在网页中共现标识，关系的类型不够自然且过于粗糙。PHOLYNET[10]定义了四种科研人员间的简单关系，基于人工标注的训练集，利用C4.5训练得到分类器，根据任意两个人物相关网页的特征，对其关系进行分类；文中定义的关系面向一个较小的领域，利用人工训练的方法可以得到较好的结果，但若将其扩展到一个大的领域，比如朋友关系的提取，则不能适用。本文提出的方法，与上述研究有三点不同：（1）不局限于一个狭窄领域的人物关系，而以人物社会关系为目标，并利用Web信息的冗余性，提取人物关系；（2）不依赖特定的训练集，面向海量的Web信息，首先挖掘与特定类别人物关系相关的描述模式集合，在保证高准确率和召回率的基础上，最小化该集合，继而对于确定的人物，利用其从Web中提取关系人物；（3）无需人工构造种子集合，而是以类别关系描述信息为输入，利用一大规模的Web人物列表，从海量Web信息中自动抽取该类别人物关系的人物关系对，作为迭代过程的输入。3人物社会关系提取3.1问题定义定义1人物社会关系：人物由于其特定的社会存在而产生的与其他人之间的关系。人物社会关系有很多种，例如父子关系、好友关系等。本文仅研究存在于两个人物之间的社会关系。一特定类别的人物社会关系stKeywordsLiFeaturesNamePR,,由关系名称、关系特征、关键词列表组成，下例定义了一个人物-子女关系，PC=Person-Children,{1-N},{儿子，女儿，孩子}，其名称为Person-Children，特征为1-N（表示一个家长可以有多个孩子），关键词为“儿子”、“女儿”和“孩子”。对于确定的关系PR，存在一个人物对集合Pair，满足trueppPRPairpppair),(,,2121，其中trueppPR),(21表示1p和2p满足关系PR。定义2：人物关系描述模式：文档中用来描述特定类别人物关系的文本段或文本段的集合。在一确定文档集D中，对于确定的关系PR及对应的人物对集合Pair，若存在一个人物关系描述模式集合PatternSet，其中PatternSetpattern,均DDPairPair'',,对于,,,,2121dppatternpDdrPaipprpai或dpdpatterndp21，则称PatternSet为PR对应的人物描述模式，记为：truePatternSetPRDescribe),(。基于上述定义，基于Web的人物社会关系提取问题可形式化为：1.确定一类人物社会关系PR；2.获取Web上PR对应的PatternSetPS,使得truePSPRDescribe),(，且对SP，PSSPtrueSPPRDescribe),(；33.对于确定的人物p,利用PS在D中提取同p满足PR关系的人物列表PList，使得PListp,PSspDd,,满足dpspp，或dpdspdp。3.2人物关系描述模式集合获取从3.1的问题形式化可以看出，其中最重要的部分为人物关系描述模式集合的获取，即对人物关系PR，分析包含此类关系的网页，获取对应的人物关系描述模式集合PS。具体过程如下：（1）首先，基于PR和一个大规模Web人名列表PL，从Web上自动抽取PL中人物对应PR关系对，作为初始的种子集合S；获得S的过程为；对于PL中的每一人名pn，利用搜索引擎得到pn和PR.KeyWordsList中词共现的网页短摘要，提取所有包含pn和keywords的短句，从中识别出人名，将其按照出现频率排序，取前k个人名同pn形成人物关系对，放入S中；k的取值由关系PR.Features决定。在人名识别时，我们将基于统计规则的识别方法[11]、基于隐马模型的识别方法[12]以及基于正反例人名集合的贝叶斯识别方法结合起来[13]，对于网页中存在的人名，进行准确识别。（2）然后，启动自动创建描述模式的循环。首先利用搜索引擎获得与S相关的网页短摘要WPA，得到WPA中S元素之间的文本段集合TextSegSet；对于其中的每一文本段TextSeg，识别出其中的人名，并用“PersonName”标记替换，得到对应的候选描述模式CandidatePattern，并记录下CandidatePattern出现的次数；之后，对于所有的CandidatePattern，选取其中出现次数大于某一阈值PatternThreshold的部分，作为对应的描述模式集合。图1为一Parents-Children关系描述模式；在获取S对应的模式集合PS’之后，将其中的新模式放入PS中，利用PS和PL从Web中产生新的人物关系对，并随机从中选择一定量的关系对，作为下次循环的种子。在每次循环结束时，计算当前PS在S上对应的F1值，若连续N次循环F1值没有变化时停止循环，))(Re)((Pr)(Re)(Pr2)(1PScallPSecisionPScallPSecisionPSF，)(PrPSecision指利用PS对种子集合S中人物关系对正确提取的准确率，)(RePScall为对应的召回率。（3）在得到完整的关系描述模式集合后，由于模式发现关系的作用域可能叠加，对于PS，可能其某子集即可涵盖全部作用域。为提高人物关系提取的效率，必须最小化PS，得到一最小的描述集合，作为关系PR的描述模式集合。3.3人物关系描述模式集合最小化假设PS中包含N个模式，最小化PS的目标即是发现一集合PSPSmin，truePSPStyEqualAbili),(min，且truePSSPtyEqualAbiliPSSP),(,，有SPPSmin。这是一个NP完全组合优化问题，问题求解需要N的指数阶时间，需要一种能够兼顾解的质量及求解时间的算法，模拟退火[14]可以满足这一需要。…[毛泽东]和杨开慧之子[毛岸英]……………[邓小平]和卓琳之子[邓朴方]…P1和PersonName之子P2图1Parents-Children关系描述模式示例Figure1AnexampleofdescriptivepatternaboutParents-Childrenrelation4表1六种人物社会关系Table1Sextypesofsocialrelationsofpersons模拟退火算法的过程为：从任意初始解开始，逐步递减控制参数t，产生一系列Markov链，在每一链中利用一新解产生器和接受准则，重复产生新解--计算目标函数差--判断是否接受新解--接受/拒绝新解这一过程，对当前解进行迭代，从而达到使目标函数最优的目标。在利用模拟退火算法最小化人物关系描述模式集合的过程中，有以下两个关键步骤：1.产生新解：用当前解currentPS初始化新解newPS，然后产生两个随机数),1(,Nji，对PS中任一模式，若在newPS中，定义其状态为1，否则为0。若PS中第i和第j个模式状态相同，则改变第i个模式的状态；若状态不同，则交换第i和第j个模式的状态。2.计算目标函数差：对于currentPS和newPS，其目标函数差)()(currentnewPSfPSff，其中对,PS)(1)(PSFPSf。由于模拟退火算法的随机性，迭代终止时得到的解未必是整个迭代过程所产生的解中的最优解，因此，通过在迭代过程中加入一记忆器，用于记忆当前得到的最优解，即可在迭代终止时得到最优解。3.4人物关系提取利用3.3节得到的minPS，可以对任一确定人物p从Web上提取其关系人物。首先，对于每一PSpattern，利用pattern和p形成查询并提交至搜索引擎，获取返回的网页短摘要，得到其中包含pattern和p的短句集合，并利用pattern获得其中包含的p的候选关系人物姓名；这样，可以得到p的候选关系人物集合，若关系PR为一对一关系，则该集合中出现频率最高的姓名p即为p的关系人物的姓名；否则，根据实际情况选取该集合中出现频率最高的前k个姓名作为p的关系人物的姓名。4实验及分析4.1实验设计首先，我们从一产生自Web的人名集合[14]（包含7,951,826个人名）中随机挑选出150,000个人名，滤掉相关网页数低于500的人名，得到一50,026个人名的集合allPL，从中随机选取10,000人形成集合trainPL，基于该集合设计相关实验。同时，参考RELATIONSHIP[15]中定义的人物关系，根据关系的重要程度，加以适当的选择和细化，得到如表1所示的六种人物社会关系。人物关系名称关系特征关键词列表人物关系对示例Person-Wife1→1妻子，夫人，老婆毛泽东，杨开慧Person-Husband1→1丈夫，老公杨开慧，毛泽东Person-Father1→1父亲，爸爸，老爸释小龙，陈同山Person-Mother1→1母亲，妈妈，老妈宋庆龄，倪佳珍P