基于LCA分块算法的大学科研人员信息抽取*
2016-05-28 00:51易晨辉刘梦赤武汉大学计算机学院武汉43007湖北大学计算机与信息工程学院武汉43006
计算机与生活 2016年6期
易晨辉，刘梦赤，胡 婕.武汉大学 计算机学院，武汉 43007.湖北大学 计算机与信息工程学院，武汉 43006
基于LCA分块算法的大学科研人员信息抽取*
易晨辉1+，刘梦赤1，胡婕2
1.武汉大学 计算机学院，武汉 430072
2.湖北大学 计算机与信息工程学院，武汉 430062
YI Chenhui,LIU Mengchi,HU Jie.Information extraction of university research faculty based on LCA segmentation algorithm.Journal of Frontiers of Computer Science and Technology,2016,10(6)：761-772.
摘要：现有的半结构化网页信息抽取方法主要假设有效数据间具有较强结构相似性，将网页分割为具有类似特征的数据记录与数据区域然后进行抽取。但是存有大学科研人员信息的网页大多是人工编写填入内容，结构特征并不严谨。针对这类网页的弱结构性，提出了一种基于最近公共祖先（lowest common ancestor，LCA）分块算法的人员信息抽取方法，将LCA和语义相关度强弱的联系引入网页分块中，并提出了基本语义块与有效语义块的概念。在将网页转换成文档对象模型（document object model，DOM）树并进行预处理后，首先通过向上寻找LCA节点的方法将页面划分为基本语义块，接着结合人员信息的特征将基本语义块合并为存有完整人员信息的有效语义块，最后根据有效语义块的对齐获取当前页面所有关系映射的人员信息。实验结果表明，该方法在大量真实的大学人员网页的分块与抽取中，与MDR（mining data records）算法相比仍能保持较高的准确率与召回率。
关键词：信息抽取；最近公共祖先（LCA）；基本语义块；有效语义块；关系映射
ISSN 1673-9418CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology
1673-9418/2016/10(06)-0761-12
E-mail:fcst@vip.163.com
http://www.ceaj.org
Tel:+86-10-89056056
1 引言
构建学术社交网络主要包含3部分的工作：从教学科研机构层次抽取关系映射的科研人员基本信息，从个体层次抽取科研人员具体属性信息以及人员信息的聚合与命名消歧工作。Tang等人[1]主要从个人主页的粒度完成了对单个科研人员的属性信息进行抽取。如何从科研机构的粒度获取所有关系映射的人员信息，对于学术社交网络的构建有着重要意义。大学作为教学科研机构的主要组成部分，其网站上包含的科研人员信息是学术社交网络构建最重要与最易获取的数据来源。本文主要研究如何从大学网站上的人员列表页面中抽取所有关系映射的人员信息。
大学网站上的人员列表页面具有一定的结构性，但不同于RDF（resource description framework）、RSS （really simple syndication）及XML（extensible markup language）这一类具有明确结构化语义并且是为数据库存储而设计的格式，其结构性来源于网站开发者为了方便用户阅读而对网页内容与格式进行的分块和设计；并且与商品网页这一类Deep Web不同，大学人员列表页面并不是从数据库中读取结构化数据然后通过模板生成的动态页面，而通常是由开发者人工生成的静态页面，因此属于较弱的半结构化页面。但现有的Web页面分块和信息抽取方法大多假设研究对象是诸如商品信息或论坛评论区这类本身具有一定模式的Deep Web页面，而忽略了静态页面中可能人工添加的修饰与冗余部分带来的噪声信息处理。图1是一个简单的例子，展示了冗余与修饰标签：Text1处在标签对中，而Text2没有，标签对作为修饰标签使得Text1与Text2的标签结构、视觉效果等特征都会不同。出于排版的需要，在真实的大学人员页面中，除图1中的例子外，还会出现给部分人名加粗，给部分人名加上颜色及特殊字体，给部分人名加上框表示去世等多种修饰或冗余成分，这也是现有方法在静态页面信息抽取中遇到的主要困难。
Fig.1 Redundant and decorative tags ofa real faculty page图1 一个真实页面的冗余与修饰标签示例
为克服这些缺陷，提出了一种基于最近公共祖先（lowest common ancestor，LCA）分块算法的大学科研人员信息抽取方法。
LCA的最初定义是：对于有根树T的两个节点u、v，最近公共祖先LCA(T,u,v)表示一个节点x，满足x是u、v的祖先且x的深度尽可能大。
本文组织结构如下：第2章介绍相关工作；第3章说明LCA与语义相关区域划分的联系；第4章给出基于LCA的人员页面分块方法；第5章介绍分块结果对齐及信息抽取方法；第6章在真实的大学人员页面中进行实验并给出结果分析；最后对全文进行总结，并指出未来的研究方向。
本文的创新之处在于：
（1）将节点的LCA层次作为其语义相关度强弱的判断标准引入页面分块方法中。
（2）搜索LCA节点的过程中可以排除网站开发者添加的修饰与冗余结构对页面分块的干扰。
（3）基于有效语义块的分块形式没有Data Record 和Data Region[2]这样严格的层次关系，可以处理多层嵌套的情况。
2 相关工作
对半结构化网页的信息抽取分为3步：页面分块得到储存数据的基本单元，分块结果对齐，信息结构化存储。由于后两步的效果主要依赖分块效果，当前研究主要集中在页面分块上。
当前的网页分块方法根据特征选取的不同可以归纳为4类：（1）基于文档对象模型（document object model，DOM）树结构的网页分块方法；（2）基于图论的网页分块方法；（3）基于视觉特征的网页分块方法；（4）基于标签树路径的网页分块方法。
基于DOM树的网页分块方法主要将网页的DOM树结构以及DOM树节点的标签作为特征，可计算不同树节点的相似度。其中，Liu等人[2-3]将标签树之间的编辑距离作为相似度的衡量标准；Zhao等人[4]在计算标签树编辑距离的基础上引入了内容对齐的计算；Lerman等人[5]将页面中的超链接节点作为一种特征值引入了树的相似度计算；Hong等人[6]提出的WISH系统以树中包含节点的数目与内容的多少作为计算两棵子树间相似度的特征值。DOM树的引入只是为了在浏览器中显示Web页面的布局结构，并不是用来描述Web页面的语义结构[7]，而在人工生成的大学人员网页中，DOM树中会增加修饰和冗余的部分，子树之间结构的相似性也会受到影响，因此基于DOM树结构的网页分块方法并不能取得较好的分块效果。
基于图论的网页分块方法，它的主要思想是将网页结构映射成对应的图结构，从而将网页分块问题转换为图结构的分割问题。Chakrabarti等人[8]提出了基于图分割的网页分块方法，将网页分块问题转换为权重图上的最优组合问题。该方法首先利用图结构来表示网页的结构信息，并计算出图中每条边的权重值；然后使用相关的图分割方法对图进行分割；最后通过将分割结果映射到原始页面中，完成网页分块。Ravikumar等人[9]将网页转换成权重图，权重代表页面中的任意两个DOM树节点在视觉与语义上的相似程度，通过权重的大小将网页进行分块。基于图论的网页分块方法能够较好地应用于Web页面的分块，但由于表示网页结构的图比较大，导致图分割的效率比较低，同时图中边的权重计算规则具有局限性，从而该方法不具备实用性。
基于视觉特征的网页分块方法（vision-based page segmentation，VIPS），提取字体的大小与颜色、背景颜色、各块的绝对位置信息、块与块之间的相对位置信息等作为网页的视觉特征，通过制定一些启发式规则将网页划分成多个语义块[10-11]。VIPS算法主要有3个步骤：第一，构建页面对应的DOM树结构后，提取所有视觉块；第二，识别视觉块之间的分隔条，并对分隔条的权重进行设置；第三，根据分隔条的权重，对视觉块进行重构，得到页面的分块结果。Liu等人[12]将VIPS算法[10]与Chakrabarti等人[8]提出的图论算法相结合，首先提取网页的视觉与结构特征并生成有权重的无向图，图中的点代表DOM树的叶子节点，边代表叶子节点之间的视觉关系；然后使用基于最小分割树的分块算法将上一步得到的无向图进行分割得到结果。当前许多的网页分块算法都是基于VIPS算法[13]。基于视觉特征的网页分块方法，既能使页面具有一定的分割粒度，又能使分块结果具有较好的层次性和语义性。使用视觉信息的局限性在于这些特征值依赖于网页的布局，而不同页面的布局风格可能差异会很大，同时识别分隔条的规则较复杂且是基于对一定量页面视觉特征的总结，因此使用视觉信息反而不如其他方法灵活。
基于标签树路径的网页分块方法将DOM树从根节点到每个节点的标签路径作为特征值来计算得到具有相似标签路径的树节点。其中，Thamviset等人[14-15]首先通过用户输入主题信息或者通过主题发现方法获取页面主题，过滤DOM树得到候选的数据记录；然后得到从根节点到所有候选数据记录的标签路径集合；最后通过找到集合中重复度最高的项作为正确数据记录的标签路径，从而定位出所有数据记录。文献[16-17]首先都要获取从根节点到所有文本节点的标签路径集合；然后Álvarez等人[16]计算不同标签路径的编辑距离找到重复性最强的路径，而Miao等人[17]引入了一种向量分析的方法对路径集合进行聚类得到储存有数据记录的标签路径；最后得到所有数据记录。以标签路径作为特征值的分块算法研究对象是Deep Web这一类通过模板动态生成的页面，因此同一类数据记录的标签树路径会很一致，而大学人员页面大多都是人工生成的静态页面，不具有这种一致性。
上述方法应用在大学人员页面信息提取中所共有的两个缺点是：第一，作为人工生成的静态页面，大学人员页面的结构性不够严谨，可能会有修饰与冗余的部分存在，这会对上述方法产生极大干扰。第二，上述方法大多将网页分块结果分为Data Record 和Data Region两个层次，但在实际的大学人员页面中，信息并不是严格按照这两个层次划分的，而是可能存在多层嵌套出现的情况。例如，一条单独的信息与一个Data Region共属一个父节点，并且Data Region中也可能有多层嵌套关系。
3 语义相关区域分析
现有的网页分块方法普遍假设网页中的有效信息之间具有强相关性，或是DOM树结构相关，或是从根节点到子树的路径相关，或是视觉特征上相关，而有效信息与噪声信息之间不具有相关性或相关性很弱。因此现有方法不论如何选取特征值，其根本目的在于通过相关性的计算与阈值的设定，过滤噪声信息，保留具有强相关性的部分，即为Data Record，然后类似的Data Record组合成Data Region。其中，仅仅分析DOM树结构之间相关性会有一定的局限性，因为同一种子树结构在有的地方可能包含了有效信息，在别的地方可能又是作为页面装饰的一部分出现[4]，所以在大学人员页面这一类大量异构的页面抽取中，将DOM树结构之间的相似性作为分块标准，会存在一定的局限性。
本文认为，同一页面中的所有内容在语义上都是相关的，相关性的强弱由对应DOM树节点之间的LCA节点的层次体现，而不需要通过计算DOM树的标签特征或子树结构得到。图2以一个真实的大学人员页面中的7条文本信息及其DOM树结构为例，阐述语义区域的划分和LCA节点之间的联系。
图2中整个页面对应的DOM树根节点t1是其中所有节点的公共祖先，表示页面中所有内容在整个页面区域中都是语义相关的，而LCA节点代表两个节点具有语义相关性的最小区域。例如Text5与Text6的LCA节点是t6，在网页中代表它们在t6对应的同一行区域中是语义相关的；而Text5与Text7 的LCA节点是t5，代表它们在t5对应的表格区域中是语义相关的，且t6对应的一行区域与Text7也在整个表格的区域中语义相关；同理可以得到Text5与Text3在一块更大的区域中语义相关，而Text5与Text1是在整个页面区域中语义相关。通过LCA节点的层次可以得到与Text5的语义相关程度的排序为Text6>Text7>Text3，Text4>Text1，Text2。这个结果与页面中实际的语义关系层次是一致的。
Fig.2 Semantic segmentation of a real faculty page图2 一个真实页面的语义区域划分示例
出现这种一致性的原因是，网页分块结果是一种递归结构：整个网页进行分块后，每个分块结果可以进一步分成更小的块。而DOM树也具有这种特征；且DOM树节点的标签中包含的特征具有向下传递性，节点会继承其祖先节点标签赋予的特征，因此通过寻找两节点的LCA节点可以得到它们具有共同特征的最低层次，即在页面中具有语义相关性的最小分块区域。
基于上述一致性，给出假设1，后面的研究工作将在假设1下进行阐述。
假设1一个页面中的任意两个部分都具有语义相关性，相关性由对应的DOM树节点的LCA节点的深度决定，深度越大代表在越小的区域内语义相关，即语义相关程度越高；深度越小则所属的语义相关区域越大，语义相关区域的极大值为整个页面，此时语义相关程度最弱。
语义区域的划分与人直观感受到的分块结果并不一定一致，这是因为直观感受中的分块有时会忽略掉分块结果中进一步进行分块的可能性。网页中有的部分在人的直观感受中应该划分到同一语义区域，但通过分析其中节点的LCA可以将该语义区域分解为更小语义区域的集合。例如图3所示，页面中同一行的4条文本可以使用两种不同方式构成DOM树，在人的直观感受中它们在语义层次上应该地位同等。但通过分析LCA节点可以发现，左边的树结构中，Text2与Text3除了继承t0赋予的特征外，还继承了t2赋予的特征，而Text1与Text4则只继承了t0的特征。因此可以认为Text2与Text3构成了一个小语义块t2，t2与Text1、Text4地位平等地组成一个语义块t0。这种页面异构的情况在真实网页中广泛存在，例如对页面中的一部分内容加上修饰或冗余标签后，虽然显示效果不变，但页面的语义层次已经改变。
Fig.3 Two different structures with similar visual effect图3 具有类似视觉效果的两种异构形式
4 基于LCA的人员列表页面分块算法
本章包含3部分：第一部分是DOM树的预处理；第二部分是基本语义块的定义及划分；第三部分是有效语义块的定义及划分。
4.1DOM树的预处理
大学人员网页中的人员信息以文本信息为载体，对页面进行语义划分将以文本信息为核心展开。因此，可以认为页面中直接包含文本信息的节点如是储存信息的基本单位，是组成语义块的基本对象。将这一类节点定义为单文本叶子节点。
定义1在DOM树中，若一个节点node包含文本内容，且文本内容全部直接处于node对应的标签对之间，则称该节点为单文本叶子节点。
在真实网页中，嵌套形式会导致一些标签下包含了自有文本却不符合单文本叶子节点定义的情况，对分块工作造成干扰，因此需要对DOM树进行预处理。
4.1.1单文本叶子节点包含多条信息的预处理
DOM树的构造以标签对为基础，但HTML（hy-per text markup language）规范中有一部分标签例如
、
等并不需要以成对的形式出现，而这一类标签在视觉上有明确的分块特征，其前后的文本信息在语义上具有相互独立性。因此第一步预处理如图4所示：若一个单文本叶子节点中包含
、
等非成对标签，则将非成对标签及被它们分隔的文本分别构造成新的单文本叶子节点，替代原本在DOM树中的位置，构造的单文本叶子节点HTML标签统一定义为
Fig.4 Preprocessing of single text leaf node containingmultiple text information图4 单文本叶子节点包含多条信息的预处理
4.1.2单文本叶子节点嵌套出现的预处理
真实网页中，通常会有一些节点的标签对中直接包含文本信息，同时其子孙节点中嵌套了其他文本信息的情况。这一类节点不符合单文本叶子节点的定义，但它们却直接包含了文本信息。因此第二步预处理如图5所示：若一个节点中既包含自有文本，又嵌套包含了其他文本信息，则将其自有文本构造成一个新的单文本叶子节点，替代原有文本在DOM树中的位置，构造的单文本叶子节点HTML标签统一定义为
Fig.5 Preprocessing of single text leaf nodenested with other text nodes图5 单文本叶子节点嵌套出现的预处理
4.2基本语义块定义及划分
完成DOM树的预处理后，所有单条文本信息都会属于一个单文本叶子节点，因此获取DOM树中所有单文本叶子节点即获取了页面内容的基本数据单元。
基于假设1可知，节点之间的语义相关程度可通过其LCA节点的深度进行比较。DOM树中任一节点t1与其他节点都会拥有一个LCA节点，其中深度最大的节点LCA(t1)通过假设1可以认为是t1所属的最小的语义区域，LCA(t1)中的其他节点与t1具有最接近的语义关系。因此，对一个节点t1来说，定位其所属的深度最大的LCA节点，对于页面分块具有重要意义。同时，本文认为单文本叶子节点是页面中储存数据的基本单元。因此找到页面中一块文本信息对应的节点与其他单文本叶子节点之间深度最大的LCA节点可以表示该文本信息所属的最小语义区域。将定位某个节点的这一类LCA节点的算法定义为文本最近公共祖先算法（text lowest common ancestor，TLCA）。
算法1 TLCA节点定位算法
输入：t—页面中一块文本信息对应的DOM树节点；D—经过预处理的DOM树。
输出：TLCA(t)—t节点所属的深度最大的文本最近公共祖先节点。
1.遍历D得到单文本叶子节点的集合SD
2.遍历t得到其包含的单文本叶子节点的集合St
3.vector=t
4.while（vector不包含SD-St中任一节点）do
5.vector=vector的父节点
6.return vector指向的节点
将所有单文本叶子节点代入TLCA算法得到的节点代表了所有单条文本信息在页面中所属的最小语义区域，将这一类最小语义区域定义为基本语义块。
定义2获取页面DOM树的单文本叶子节点得到页面的基本数据单元，代入TLCA算法得到每个单文本叶子节点的TLCA节点构成的集合可以认为是从语义上对页面进行了最基本的分块，将代表分块结果的TLCA节点定义为基本语义块节点。
基本语义块节点中允许嵌套包含基本语义块节点的情形，例如图2的真实页面中，单条文本信息Text1与t2（Text2与Text3组成的基本语义块）在语义上具有平等关系。可以看出，基本语义块代表的不是页面划分的最小区域，而是某个单文本叶子节点所属的最小语义区域。
找到基本语义块节点的意义在于：为页面中单条文本信息找到其所属的最小语义区域，每个单文本叶子节点都对应一个基本语义块，基本语义块的集合就是对页面的一种初步分块结果。
4.3有效语义块定义及识别
4.3.1现有的网页分块层次及其不足
对页面中有效信息的分块层次，Liu等人[2]在MDR（mining data records）算法中首先提出将页面划分为Data Record与Data Region两个层次。其中Data Record是储存单条完整信息的基本单位，例如页面中一件商品的名字、属性等完整信息，而Data Region是由具有相似结构的Data Record聚合而成的一块区域，例如页面中多个商品的Data Record在一起构成了Data Region。现有方法大多采用Record与Region两个层次对页面进行分块。
这种分块形式在Deep Web中有较好的效果，因为诸如商品信息等网页是从数据库中读取数据后通过模板动态生成的[18-19]，所以Data Record之间不论是从DOM树结构特征上还是从视觉特征上都具有强相似性，且Data Record会以并列的形式组成Data Region。但在大学人员页面中，由于是开发者人工生成静态网页，结构之间的规律性没有Deep Web中严谨，如果采用上述分块形式，“Data Record”不一定会以并列形式组成“Data Region”，可能会有嵌套的形式出现（如图3所示），并且还会出现“Data Record”中包含“Data Region”和“Data Region”中包含“Data Region”等情形。例如图3的左图中，t1与t3是Data Record，t2是由t4与t5两个Data Record组成的Data Region，而t1、t2与t3又并列组成了t0，一个新的Data Region，此时出现了“Data Region”中包含“Data Region”的情形；同样是图3的左图中，若将t1的
4.3.2有效语义块定义
针对大学人员页面的特点，不采用Data Record与Data Region两层划分的方法，而是在上一节提出的基本语义块的基础上，提出有效语义块的概念以及基于有效语义块的页面分块方法。
基本语义块仅仅从结构上获取了单条文本信息所属的最小语义区域，并不一定包含完整的人员信息。结合假设1，可以认为，从单个人员所属的基本语义块节点向上搜索其祖先节点，通过信息的边界识别，可以找到既储存该人员尽可能多的信息，又不引入其他人员信息的节点。将找到的这一类节点定义为有效语义块节点。下面给出详细定义。
定义3从单个人员信息所属的基本语义块节点出发，向上搜索祖先节点，得到的包含单个人员信息且不引入新的人员信息的最大区域对应的节点为有效语义块节点。“最大区域”的概念是：当前节点包含了单个人员及其一定量的信息，但如果继续向上搜索TLCA节点，则会引入新的人员及其信息。
每个单文本叶子节点对应属于一个基本语义块，而每一个包含人员信息的基本语义块对应属于一个有效语义块。有效语义块的定义是以单个人员为核心找到包含其信息的最大区域，但有效语义块不一定只包含单个人员信息，因为基本语义块本身有可能包含多个人员信息。例如基本语义块节点t中包含3个单文本叶子节点，结构是“rel1：name1 name2”，虽然其中有多个人员，但对人员name1而言，t既是基本语义块节点，又是有效语义块节点，其中包含了name1的关系信息rel1，若向上继续寻找TLCA节点，则会引入新的人员及其信息“rel2：name3”。因此节点t对人员name1而言，是包含name1所有信息的最大区域，且向上搜索TLCA节点会引入新的带有信息的人员，从而t对于人员name1而言是符合定义3的有效语义块节点。
4.3.3有效语义块的边界识别
通过对随机取样的大学人员页面进行观察，发现人员信息有关系信息与属性信息两种类型，对应的逻辑结构如图6所示。
Fig.6 Two logical forms of faculty information ineffective semantic bocks图6 有效语义块中人员信息的两种逻辑结构
逻辑结构（a）中，是在一个关系前导词后挂载其映射的所有人员名字，对单个人员而言，关系前导词就是其拥有的信息。在这一类逻辑结构中，人员名字呈块状出现，拥有共同的关系前导词，因此可以认为块状的人员名字具有同质性，关系前导词后挂载一个人员、一块人员、多块人员或者嵌套出现的人员块，在逻辑结构上都可认为是“rel：Name_Block”形式。
逻辑结构（b）中，一条人员记录包含了一个人员的名字信息及其属性信息，其中属性信息可以是属性名、属性值以及并不属于单文本叶子节点的个人图片等。
结合定义3及对人员信息逻辑结构的分析，可以给出有效语义块边界识别算法。
算法2有效语义块边界识别算法
输入：t—基本语义块节点。
输出：基本语义块所属的有效语义块节点。
1.Ift中不包含人名信息then
2.return NULL
3.else if（t中仅有一条人名信息）then
4.vector=t
5.While TLCA（vector）仅有一条人名do
6.vector=TLCA（vector）
7.return vector指向的节点
8.else if（t有多条人名信息andt只包含人名信息）
then
9.vector=t
10.While TLCA（vector）只有人名信息do
11.vector=TLCA（vector）
12.return vector指向的节点
13.else//t有多条人名信息且含有非人名信息
14.returnt
15.end if
其中，TLCA()函数是对算法1的调用；第5～6行的判定是为了找出单个人员拥有的属性信息的边界；第10～11行的判定是为了找出关系前导词映射下所有人名信息的边界。
5 有效语义块对齐及信息抽取
通过基于LCA的网页分块算法，可以得到符合图6中逻辑结构的有效语义块。有效语义块仅仅是从某单个人员所属的基本语义块出发，得到包含该人员信息且不引入新的带有信息的人员的最大区域，因此有效语义块会尽可能多地保存单个人员具有的信息。但有的信息并不是存在于某个特定的有效语义块中，而是属于有效语义块之间共有的特征信息。因此在获取所有有效语义块后，需要将有效语义块对齐来识别这一部分不存在于有效语义块中但仍属于人员信息的部分。
通过观察随机取样的大学人员页面的组织结构，发现不论是存有关系信息还是存有属性信息的有效语义块，通常都会与同类型有效语义块进行对齐合并。
5.1关系信息的有效语义块对齐
图7给出了存有关系信息的有效语义块的两种对齐示例。其中（a）结构的特点是：一些储存有关系信息的有效语义块可以构成一块更大的语义区域并拥有共同的关系前导词。在真实的页面中，例如有效语义块“教授xxx xx”与“副教授xx xxx”可能会拥有共同的关系前导词“在职教师”。（b）结构的特点是：有效语义块作为表格中的一行存在，这些有效语义块拥有共同的TLCA节点，即整个表格对应的节点，且这些有效语义块在共同的TLCA节点中拥有一个兄弟语义块。兄弟语义块不包含人员信息，但包含了关系（rel）信息。兄弟语义块中rel信息的位置可以与有效语义块中Name_Block的位置对齐，从而组成表格结构，表格的第一行与第一列作为关系前导词，以二维映射方式得到每个Name_Block具有的二元关系信息。
Fig.7 Two typical alignments of relation information图7 关系信息的有效语义块对齐示例
以这两种典型的关系信息对齐方式为例，可以将关系型有效语义块的对齐与抽取过程总结如下：首先寻找一个关系信息型有效语义块的TLCA节点，如果TLCA节点中包含有其他关系信息型有效语义块，且这些有效语义块之间没有其他语义块，则开始对齐工作。接下来，如果在这些有效语义块之前存在一个非人员信息的兄弟语义块，那么获取兄弟语义块中可能储存有rel信息的单文本叶子节点和基本语义块所处的位置坐标，将位置坐标与关系型有效语义块中的Name_Block坐标进行对齐。如果对齐成功，则可按照图7（b）中的关系表形式从TLCA节点中提取所有关系映射下的Name_Block；如果对齐不成功，则按照图7（a）中的人名块形式对TLCA节点进行信息抽取。
5.2属性信息的有效语义块对齐
图8给出了存有属性信息的有效语义块的两种对齐示例。其中（a）结构的特点是：每个人员的名字、属性名、属性值和个人图片等信息单独形成一块，在真实页面中通常以类似卡片的格式出现，通过上文提出的方法可以将这一块对应的节点识别为一个有效语义块，这些有效语义块可能会有共同的关系前导词存在。（b）结构的特点是：有效语义块作为表格中的一行存在，包含且仅包含了单个人员的名字和所有属性值信息，这些有效语义块拥有共同的TLCA节点，且在TLCA节点中拥有一个兄弟语义块。兄弟语义块中不包含人员信息，但包含了属性名（Attr_ Name）信息，兄弟语义块中Attr_Name信息的位置可以与有效语义块中Attr_Value的位置对齐，从而组成表格结构，表头中存放了所有人员共有的Attr_ Name。
Fig.8 Two typical alignments of attribute information图8 属性信息的有效语义块对齐示例
通过结构对比，可以发现卡片形式的对齐方式与人名块形式的对齐方式实质上是同一种方法，而属性表形式的对齐方式与关系表形式的对齐方式实质上也是同一种方法，因此这里不再赘述属性型有效语义块的对齐与抽取方法。
6 实验结果与分析
6.1实验设置
数据集：采集了8所中国大学的245个学院的所有人员列表页面，共计1 641个。本文的实验目的在于测试所提方法在大量真实的人员列表页面中是否具有普遍适用性，因此不对数据集页面的类型和特点进行统计分析，后文将直接分析实验结果。
评价指标：本文的信息抽取流程包含有效语义块识别，有效语义块对齐，抽取所有关系映射下的人员信息。其中，如果有效语义块的识别与对齐能准确识别例如图7与图8中这样的区域，那么最后的抽取只需要使用前面的对齐信息就能准确得到人员信息。有效语义块的对齐结果直接影响抽取的效果，因此将对有效语义块的对齐结果进行人工标注及评价。评价指标是：在一个页面中通过有效语义块对齐后识别出的区域中，如果包含了人员所有的属性信息和所属的关系映射，则将该对齐结果标记为“正确”，否则标记为“错误”。最后根据标注结果计算对齐结果的准确率、召回率与F1值。计算公式如下：
基准系统：由于实验数据集不同，无法进行直接对比实验，从而采用文献[2]中的MDR方法作为基准系统。并且本文与MDR方法均是基于DOM树结构的页面分块方法，因此选取MDR方法作为基准系统。由于树的相似度阈值难以确定，文献[2]原文中取阈值为0.3，本文实验中取0.3、0.5与0.7共3个阈值分别进行对比实验，统计对应阈值下对数据区域识别的效果。
人名信息识别：MDR方法中未给出人名识别方法，为保证实验结果的准确性，将在提出的系统与基准系统中使用相同的人名信息识别方法。大学人员页面中的人名信息是以条目形式出现，无上下文信息，因此实验中结合中文人名的构造规则，使用汉语人名姓氏库文件匹配得到符合规则的候选人名，然后通过常用词词典匹配可排除“党委”、“学工”等通常作为先导词的关系型噪声信息，通过候选人名的重复度与位置信息比对可排除“文科楼”、“第一批”等通常会重复在不同人员中出现的属性型噪声信息。本文重点讨论基于LCA分块方法的人员信息抽取，因此不对人名信息识别与去噪部分进行详细阐述。
6.2实验结果及分析
表1显示了对数据集中的1 641个大学人员页面进行人员信息所属区域定位的结果。
Table 1 Experimental results on 1 641 real faculty list pages表1 1 641个人员页面数据区域识别结果
从表1可以看出，随着阈值的提高，MDR分块算法的准确率会有提高，而召回率会降低。因为阈值提高代表Data Region中对Data Record之间的相似度要求更严格，所以准确率会上升而召回率会降低。
TLCA分块及有效语义块对齐算法在准确率上与不同阈值的MDR分块算法相差不大，是因为不论是通过有效语义块对齐还是通过计算Data Record之间的相似度，都能够有效过滤噪声信息；而有效语义块的边界识别也是以尽可能不引入噪声信息为前提。
TLCA分块及有效语义块对齐算法在召回率上相对不同阈值的MDR分块算法均有较显著提升。这是因为在大学人员页面中作为非Deep Web的人工静态页面，普遍会有修饰与冗余标签的存在，在MDR算法中这些标签会降低实际上应该相关的Data Record之间的相似度，从而对Data Region的识别造成干扰，所以会有较多的Data Region被遗漏；而LCA分块算法实质上是一种自底向上寻找祖先节点的方法，在寻找祖先节点的过程中不会受到修饰标签与冗余标签的影响，所以在大学人员页面中有较好的召回率。
除了人名信息识别错误造成准确率与召回率下降，实验结果中影响TLCA分块及有效语义块对齐算法效果的主要限制在有效语义块对齐这一步。真实页面中，有少数情况并没有严格区分人的属性信息与关系信息，或者有的信息同时属于属性类和关系类，因此无法对齐有效语义块而导致人员信息区域的识别会遗漏信息。这一类页面的示例如图9所示，在准确识别出每个人员所属的有效语义块，即表格中名字与属性信息所在的一行后，依照有效语义块对齐的方法得到的格式是“rel：card card”这种类型，而无法识别出表头中的“职称”、“性别”等属性名信息。在该类型页面中，出现这种问题的原因是“xx学系”既是所有人员共有的关系前导词，又是所有人员共有的“单位”属性名对应的属性值，对这种既是关系信息，又是属性信息的部分难以对齐，最后不论采用哪种对齐方法，得到的区域都会遗漏一部分人员信息。针对这种情况，提出一种加入人工干预的解决思路。例如图9中，首先对“xx学系”这一类具有双重类型的词进行人工标注，识别出“xx学系”仅位于第一个人员的有效语义块中且可以与存有表头信息的兄弟节点对齐；然后对表头节点预处理删掉“单位”，对第一个人员的有效语义块预处理删掉“xx学系”，将表格作为属性表对齐后抽取所有人员属性信息；最后给每个人员加上属性“单位：xx学系”和关系前导词“xx学系”。
Fig.9 Asituation where effective semantic blocks can hardly align图9 有效语义块难以对齐的页面示例
7 结束语
从大学网站中抽取所有关系映射下的人员信息，对于学术社交网络的构建有重要意义。针对大学科研人员列表页面的特点，提出了一种基于LCA对页面进行语义划分的TLCA算法，并在此基础上提出了有效语义块的识别及对齐方法用于人员列表信息的抽取。通过在真实的大学人员列表页面中进行实验，证明了本文方法具有普遍适用性，且能够克服现有网页分块方法在大量的大学人员列表页面中的一些缺陷。但在实际测试中发现少量页面的结构中使用有效语义块对齐方法会造成人员信息的部分丢失，在后续的研究中，需要解决有效语义块对齐方法在更加复杂情况中的局限性。
References:
[1]Tang Jie,Zhang Jing,Yao Limin,et al.ArnetMiner:extraction and mining of academic social networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Las Vegas, USA,Aug 24-27,2008.New York,USA:ACM,2008:990-998.
[2]Liu Bing,Grossman R,Zhai Yanhong.Mining data records in Web pages[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,USA,Aug 24-27,2003.New York, USA:ACM,2003:601-606.
[3]Liu Bing,Zhai Yanhong.NET—a system for extracting Web data from flat and nested data records[C]//Proceedings of the 6th International Conference on Web Information Systems Engineering,New York,USA,Nov 20-22,2005. Berlin,Heidelberg:Springer,2005:487-495.
[4]Zhao Hongkun,Meng Weiyi,Yu C.Mining templates from search result records of search engines[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,USA,Aug 12-15,2007.New York,USA:ACM,2007:884-893.
[5]Lerman K,Getoor L,Minton S,et al.Using the structure of Web sites for automatic segmentation of tables[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,Paris,France,Jun 13-18,2004.New York,USA:ACM,2004:119-130.
[6]Hong J L,Siew E G,Egerton S.Information extraction for search engines using fast heuristic techniques[J].Data& Knowledge Engineering,2010,69(2):169-196.
[7]Gao Le,Zhang Jian,Tian Xianzhong.Improvement and Implementation of VIPS algorithm[J].Computer Systems& Applications,2009,18(4):65-69.
[8]Chakrabarti D,Kumar R,Punera K.A graph-theoretic approach to webpage segmentation[C]//Proceedings of the 17th International Conference on World Wide Web,Beijing,China,Apr 21-25,2008.New York,USA:ACM,2008: 377-386.
[9]Ravikumar S,Chakrabarti D,Punera K.Method for seg-menting webpages by parsing webpages into document object modules(DOMs)and creating weighted graphs:U.S. Patent 7,974,934[P].2011-07-05.
[10]Cai Deng,Yu Shipeng,Wen Jirong,et al.VIPS:a visionbased page segmentation algorithm,MSR-TR-2003-79[R]. Microsoft,2003.
[11]Chakrabarti D,Mital M R,Hajela S,et al.Automatic visual segmentation of webpages:U.S.Patent 8,255,793[P].2012-08-28.
[12]Liu Xinyue,Lin Hongfei,Tian Ye.Segmenting webpage with Gomory-Hu tree based clustering[J].Journal of Software,2011,6(12):2421-2425.
[13]Chen Yu,Ma Weiying,Zhang Hongjiang.Detecting Web page structure for adaptive viewing on small form factor devices[C]//Proceedings of the 12th International Conference on World Wide Web,Budapest,Hungary,May 20-24,2003. New York,USA:ACM,2003:225-233.
[14]Thamviset W,Wongthanavasu S.Structured Web information extraction using repetitive subject pattern[C]//Proceedings of the 2012 9th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology,Phetchaburi,Thailand,May 16-18, 2012.Piscataway,USA:IEEE Computer Society,2012:1-4.
[15]Thamviset W,Wongthanavasu S.Information extraction for deep Web using repetitive subject pattern[J].World Wide Web,2014,17(5):1109-1139.
[16]Álvarez M,Pan A,Raposo J,et al.Extracting lists of data records from semi-structured Web pages[J].Data&Knowledge Engineering,2008,64(2):491-509.
[17]Miao G,Tatemura J,Hsiung W P,et al.Extracting data records from the Web using tag path clustering[C]//Proceedings of the 18th International Conference on World Wide Web,Madrid,Spain,Apr 20-24,2009.New York,USA:ACM, 2009:981-990.
[18]He Bin,Patel M,Zhang Zhen,et al.Accessing the deep Web [J].Communications of theACM,2007,50(5):94-101.
[19]Furche T,Gottlob G,Grasso G,et al.OXPath:a language for scalable data extraction,automation,and crawling on the deep Web[J].The VLDB Journal,2013,22(1):47-72.
附中文参考文献:
[7]高乐,张健,田贤忠.基于视觉的Web页面分块算法的改进与实现[J].计算机系统应用,2009,18(4):65-69.
YI Chenhui was born in 1991.He is an M.S.candidate at School of Computer,Wuhan University.His research interest is Web data extraction.
易晨辉（1991—），男，湖北鄂州人，武汉大学计算机学院硕士研究生，主要研究领域为Web数据抽取。
LIU Mengchi was born in 1962.He received the Ph.D.degree from University of Calgary in 1992.Now he is a professor and Ph.D.supervisor at Wuhan University,and tenured professor at University of Regina.His research interests include database theory and systems,data model,XML and Web data management,etc.
刘梦赤（1962—），男，湖北武汉人，1992年于卡尔顿大学获得博士学位，现为武汉大学特聘教授、博士生导师，加拿大里贾纳大学终身教授，主要研究领域为数据库理论与系统，数据模型，XML，网络数据管理等。在国内外期刊及学术会议上发表论文100余篇，主持和承担多项国家杰出青年科学基金（外籍）、国家重点基础研究发展计划（973计划）、加拿大国家自然科学与工程基金等项目。
HU Jie was born in 1977.She received the Ph.D.degree from Wuhan University in 2010.Now she is an associate professor and M.S.supervisor at Hubei University.Her research interests include database,intelligent information system and social network,etc.
胡婕（1977—），女，湖北汉川人，2010年于武汉大学获得博士学位，现为湖北大学副教授、硕士生导师，主要研究领域为数据库，智能信息系统，社交网络等。在国内外期刊及学术会议上发表论文10余篇，承担和参与国家自然科学基金、国家重点实验室开放课题、国家杰出青年科学基金、国家重点基础研究发展计划（973计划）等项目。
*The National Natural Science Foundation of China under Grant No.61202100(国家自然科学基金);the Open Foundation of State Key Laboratory of Software Engineering under Grant No.SKLSE2012-09-20(软件工程国家重点实验室开放基金).
Received 2015-07,Accepted 2015-09.
CNKI网络优先出版:2015-09-07,http://www.cnki.net/kcms/detail/11.5602.TP.20150907.1039.002.html
+Corresponding author:E-mail:c_hui_y@163.com
文献标志码：A
中图分类号：TP391
doi:10.3778/j.issn.1673-9418.1508055
Information Extraction of University Research Faculty Based on LCA SegmentationAlgorithm*
YI Chenhui1+,LIU Mengchi1,HU Jie2
1.School of Computer,Wuhan University,Wuhan 430072,China
2.School of Computer Science and Information Engineering,Hubei University,Wuhan 430062,China
Abstract:Conventional information extraction methods of semi-structured pages usually assume that valid data have relatively strong structural similarity,divide the page into data records and data region with similar characteristics and then extract from them.However,faculty list pages of universities mostly are written artificially and filled by human beings instead of automatic generation by using templates,so their structure is not rigorous.This paper proposes a faculty information extraction method based on LCA(lowest common ancestor)segmentation algorithm,introduces the connection between LCAand semantic relation into Web segmentation,and presents the new concepts of basic semantic blocks and effective semantic blocks.After converting the page into a DOM(document object model)tree and the preprocessing,the page is divided into the basic semantic blocks with LCA algorithm firstly.Then the basic semantic blocks are merged into their corresponding effective semantic blocks with complete personnel information.Finally, according to the alignment of effective semantic blocks,all faculty information mapped by all relationships in current page is gotten.The experimental results show that the proposed method still has high precision and recall rates in thesegmentation and extraction of quantities of real university research faculty list pages by compared with the MDR (mining data records)algorithm.
Key words:information extraction;lowest common ancestor(LCA);basic semantic block;effective semantic block; relational mapping
