一种实体识别的后期处理优化算法

蒋存锋 赵 川

1(上海计算机软件技术开发中心 上海 201112)2(天睿公司 美国加利福尼亚洲 圣地亚哥 92127 )

0 引 言

在传统的实体识别算法中，经常使用数据属性值之间的文本相似性。一些改进的算法则考虑由数据上下文导出的关系相似性作为附加信息，而另一些改进方法则基于概率模型。匹配含有多个属性记录的方法大致可以分为两类，一类是依靠学习数据来“学习”如何匹配数据，这一类方法包括一些使用概率的方法以及监督的机器学习技术，另一类方法则是依靠领域知识或者属性距离度量标准来匹配记录。

1 实体识别算法

本文改进了传统实体识别算法中常用的两种方法：基于概率模型的机器学习方法以及依靠领域知识作度量标准匹配的方法[1]。改进的算法提出一个既使用直接相似度又使用间接相似度的结构化的相似度度量标准。该方法对于非监督学习使用一个简单的相似度模型，而对于监督学习则提供了一个概率的分类模型以及估算概率的方法。此外，该算法提供了简单的更新算法来消除分类匹配结果中的不一致性。本文沿用了该算法的相似度度量和概率模型，并在此基础上做了较大的改进，不但进行实体的识别，还兼顾到对象的合并。增加了数据预处理的步骤，设计了一种数据过滤策略。在后期处理过程中，设计了几种不一致性消除的方法，以及两个有效的记录更新算法。这些步骤都大大改进了计算效率和分类结果。而且，其中的记录更新算法还可以找到“正确”的记录，即拥有“真实”属性值的记录，并为非监督学习找到一个好的匹配临界值。

对于较大的数据集或者是计算起来比较耗费时间的相似度度量，整个实体识别过程的运行时间可能会是一个问题。为了解决这个问题，一般会使用分块(blocking)或者遮蔽(canopy)[2-5]的方法来有效地选择记录对的一个子集来进行相似度计算，而简单地忽略其他“不相似”的记录对。本文设计了一个数据过滤方法，它和遮蔽有着类似的效果。此外，并行和分布式计算也是近年来一个比较受重视的加快实体识别速度的方法[7-8]。本文提出的方法和一些常见的大数据处理框架的结合将是我们下一步研究的重点。

本文的方法和经典的FSM(Fellegi-Sunter Model)主要有两点不同。首先，本文使用不同的概率匹配模型。FSM使用属性值的模式，而本文的方法使用相似值的模式。其次，FSM只使用直接匹配，而本文的方法使用直接匹配、传递等价以及断言等价。本文算法使用的间接相似度度量是基于上下文的，这就提供了进行关联分析的好处，当然本文并不作直接的集体匹配决策。

2 不一致性消除

匹配结果中经常会有不一致性出现，比如三个记录a、b、c，a和b被认为是等价的，a和c也被认为是等价的，但是b和c却被认为不等价。本文称这样的三元组为不一致的三角。对监督学习中的一个不一致的三角来说，如果有记录对是在学习数据集中，那我们可以用它(们)来更正测试数据集中的记录对匹配结果，本文称这种方法为MT。如果所有三个边(记录对)都在测试集中，那可以有更多的选择来让不一致的三角变得一致。这种情况下一般来说我们可以使用传递闭包。

2.1 传递闭包(TC)

一个常用的消除分类结果中不一致性的方法是使用传递闭包。本文设计了算法1来消除三个边都在测试集中的不一致分类结果。在此算法中，S(x,y)是记录x和y之间的直接相似度，P(x,y)是记录x和y是等价记录的概率，t是当前的匹配临界值。实验表明该算法每一次都能消除分类匹配结果中的所有的三个边都在测试集中的不一致三角形。

算法1用传递闭包(TC)消除不一致性

输入： 分类后的候选记录对。

输出： 分类后的不一致结果被消除的候选记录对。

循环开始

change=0

对于每一个记录a；

对于每一个(a,b)在候选记录对中的记录b；

对于每一个(a,c)在候选记录对中的记录c；

如果(b,c)在候选记录对中；

如果(a,b)、(a,c)、(b,c)都在测试集中并且其中两对是等价对并且另外一对是非等价对；

将非等价对变成等价对;

change=change+1;

否则如果(a,b)、(a,c)都是等价对；

将(b,c)变为等价对，并将(b,c)放入候选记录对中，对于非监督学习：S(b,c)=S(c,b)=max(S(b,c),t)；对于监督学习：P(b,c)=P(c,b)=t；

如果change是0，退出循环；

循环结束

在施加TC算法后，测试集中不一致性都得以消除，但是可能会出现新的不一致三角，既有边在学习集又有边在测试集。实验结果表明这种新的不一致三角通常很少，所以我们可以施加一些其他的后期处理方法来消除它们。

2.2 一般的不一致性消除算法(IE)

MT和TC都是比较特殊的不一致性消除算法，运用它们虽然能消除大部分不一致结果，但是常常不能完全消除。如果单独施加MT，所有边在测试集中的不一致三角经常还会存在；而如果单独施加TC，既有边在学习集又有边在测试集的不一致三角又经常会留下来。如果两个都用，取决于使用的顺序，通常也会有类似的结果。因此，本文还设计了两个一般的算法来消除使用MT和(或)TC后剩下的不一致结果。它们是算法2和算法3。

算法2IE(一般的不一致消除)

输入： 分类后的候选记录对。

输出： 分类后的不一致性结果被消除的候选记录对。

1. 收集所有的不一致三角在测试集里的边(集合E)；

2. 将E分割为组，每组含有n个边(比如n=10)；

3. 对于每个组，尝试所有2n个可能的值的组合(每条边可以取等价和非等价两种值)，统计每个组合里不一致三角的个数；

4. 对于每个组，选择不一致三角最少的那个组合。

算法2的效率并不是很好，因为对于每一对组合我们必须检查全局集合E中的每一个三角，而不是在一个局部的组里面，所以我们设计了下面的改进算法。

算法3改进的IE(改进的不一致消除)

输入：分类后的候选记录对。

输出：分类后的不一致性结果被消除的候选记录对。

1. 构建一个不一致三角和边(在测试集里)之间的二部图；

2. 获得该二部图里的所有最大连通子图；

3. 将这些子图分组，让每个组的边的个数尽量接近某个值t，比如10。边的个数大于t的子图自成一组；

4. 对于每个组，如果它的边的个数大于t，把它分割成每个大小为t的子组。对于每一个子组，尝试所有2t个不同的值的组合，然后选择不一致三角最少的子组。如果组的大小不大于t，则尝试所有2t个不同的值的组合，然后选择不一致三角最少的组。

在算法3中，对于每一个局部组，不一致三角只会由组里的边构成。因此，对于每一个组合在重新计算不一致三角的个数的时候，我们只需要检查所有边都在这个组里面的三角。实验结果表明算法3的速度比算法2要快很多，而不一致消除的结果却达到了算法2的水平。

在算法3中，我们可以按照不同的顺序来组合子图：大的子图优先，或者小的子图优先，或者随机。实验结果表明优先组合大的子图可以获得最好的结果。实验结果还表明，不论是使用算法2还是算法3，绝大多数的不一致结果都能得到消除。

2.3 非传递性方法(NT)

除了传递闭包，我们也可以使用类似于MT的方法来消除测试集中的不一致三角。本文的方法是：

• 除了允许把非等价边变成等价边，还允许等价边变成非等价边；

• 当三角中有超过一条边需要改变时，选择等价概率最接近匹配临界值的那条边；

• 如果三角中只有一条边可以改变，则在改变后固定它的值(等价或者非等价)，或不改变。

和MT类似，因为可以在等价和非等价两者之间转变，NT也不能总是消除所有的不等价结果。

另一个非传递性方法类似于TC。不过，不是把非等价变成等价，我们把一条等价边变成非等价。同样的，本文仍然选择等价概率最接近匹配临界值的那条边。类似于TC，该算法也可以消除测试集中的所有不一致性。

2.4 结合不同的不一致性消除方法

前面介绍的这些不一致性消除方法有时候对同一条边会产生不同的决策。我们可以结合使用这些方法来得到更好的结果。本文尝试了一些不同的组合：没有不一致性消除、MT、TC、MT+TC、TC+MT、MT+TC+MT、TC+MT+TC。这里“+”的意思是接着使用。每一种组合之后我们都再使用IE。实验结果表明没有不一致性消除、TC、TC+MT+TC总是会产生很多不一致结果，而另外4种组合则不会。其中TC+MT不太稳定，有时候也会产生很多不一致结果。后面4种组合表现出了不同的不一致性能力。本文也尝试了MT+NT+IE的组合。在第3节中本文提供了详细的实验结果。

我们相信不同的组合拥有不同的不一致性消除能力是因为不同的方法会产生不同类型的不一致三角。通过对实验结果中不一致三角的观察，我们发现如果使用MT+TC，结果中大部分不一致三角都由一条在学习集中的非等价边和两条在测试集中的等价边构成；而如果使用MT、TC+MT、MT+TC+MT，大部分不一致三角则由测试集中的两条等价边和一条非等价边构成；如果使用MT+NT，大部分不一致三角包含学习集中的一条等价边和测试集中的一条等价边及一条非等价边。显然，如果不一致三角的所有边都在测试集中，不一致性会更容易消除。

3 记录更新及等价消除

记录更新算法的基本思想是通过更新某些记录的属性值来减少不同记录的数量。针对非监督学习和监督学习，本文设计了不同的记录更新算法。限于篇幅，本文只给出监督学习的算法如算法4所示。其中，步骤1到步骤5可以反复迭代，但是对于最后一次迭代，步骤5不执行。通常整个算法只需要执行一次即可。

算法4监督学习的记录更新算法

输入：所有候选记录对中的记录。

输出：有“真实”属性值和等价记录的记录。

步骤1： 初始化一个空的集群集合C。在记录匹配后，对每个候选记录对中的记录r1，寻找一个和r1等价的概率最大的记录r2。对某个匹配临界值t，如果p不小于t，进入步骤2；否则跳过该记录。

步骤2： 如果r1和r2都不在任何集群中，创建一个新的集群c，将r1和r2放入c中，将c加入C中；如果r1和r2都已经在某个集群中，什么都不用做；如果两者中的一个在某个集群c中，则将另一个也放入c中。

步骤3： 当所有的输入记录都在步骤1和步骤2中处理过之后，对于C中的每一个集群，寻找它的中位记录。中位记录是和同一个集群中的其他记录有最大直接相似度的和的记录。然后根据每个集群的中位记录和同集群其他记录的平均直接相似度降序排序集群。如果两个集群的中位记录是等价的，则将两者中在集群集合中索引较低的集群合并入索引较高的集群。然后重新计算合并后的集群的中位记录。重复这一过程直到没有集群的中位记录之间是等价的。中位记录和所有不在候选记录对中的记录合起来就形成了有“真实”属性的记录集合。

步骤4： 对于每一个集群，用中位记录去更新同集群中的其他记录。

步骤5： 重新做数据过滤，并重新计算每个候选记录对的等价概率。

记录更新算法的细节如下：

(1) 如何使用其他记录的属性值来更新某个记录的属性值：本文用更新记录的属性值来更新被更新记录的所有属性值，而不只是部分属性。

(2) 对于记录r1来说，如何确定一个记录集从中选择记录r2：我们可以从所有候选记录对中选择r2，也可以从当前迭代中还没有被选择作为r1的记录中选择。

(3) 如何选择匹配临界值t：简单地说，我们用当前的匹配临界值。本文选择在进行当前这一步更新之前获得最佳F1值的匹配临界值。

(4) 对于k组交叉验证：在记录更新和重新进行数据过滤之后，我们把之前的候选记录对保留在它们原来的组中，这会使记录更新的过程更加稳定。

(5) 如何获得最终结果：记录更新算法的结果收敛得很快，通常一轮更新即可获得稳定结果。

本文使用领导记录(非监督学习，是有真实属性和等价记录的记录)或者中位记录(监督学习)以及那些不属于任何候选记录对的记录作为拥有“真实”属性的记录，称为等价消除或实体身份确定。

4 实验结果

4.1 实验环境

所有实验在一台PC上进行，配置如下：

• CPU：AMD Phenom II 2.9 GHz；

• 内存：3.25 GB。

本文使用公共的数据集Cora。Cora是一个科学出版物参考文献信息的数据集。我们从Weis等[9]处下载此数据集。它包含了1 878个引用，而这些引用实际上只对应139个研究论文。它是McCallum[10]提供的数据集的扩展版本。Cora数据集中的记录有五个属性：标题、作者、出处、卷号、日期。本文在数据预处理步骤中对该数据集进行了一些清洗工作。

本文去除了一些标点符号。如果某个记录的作者超过一个，则把该记录的每一个作者单独作为一个作者属性值。

4.2 监督学习实验结果

因篇幅所限，本文略去非监督学习的实验结果。

表1 Cora数据集不一致性消除实验结果

表1中，“/”前后的数据表示施加IE算法前后的数据；“#”表示不一致三角的个数；“#r”的意思是去除等价记录后的有等价记录的记录个数，也就是有“真实”属性值的而且在数据集中有它的等价记录的记录个数。所有结果都是三次运行的平均结果。本文只使用了直接相似度，并使用算法3，设置t=5。首先，可以看到不一致性消除改进了分类匹配的精确度，而且基本上消除了不一致结果。其次，在记录更新后，不一致三角的数量大大降低。再次，除了MT+TC+IE以外，所有的组合都表现出了良好的不一致性消除能力。MT+TC+MT+IE产生了最少的不一致三角以及最好的分类精确性。最后，所有的组合都得到了不错的记录个数，且是“真实”属性值而且存在和其等价的记录。

表2 Cora数据集结果和其他方法比较

表2中，“5组”和“3组”是指进行5组交叉验证和3组交叉验证，“25%”的意思是每次随机选取25%的记录对作为学习集，共进行4组交叉验证。“/”前后的数据表示施加领域优化的直接相似度计算前后的数据。表2中的数据表明本文的方法比其他的方法获得了更好的结果。

5 结 语

本文主要通过一些后期处理算法改进了一个实体识别算法，该算法属于传统的混合-清除算法。后期处理过程主要包括不一致性消除、记录更新以及等价消除，它们可以显著提高实体识别的结果。本文针对不同情况提供了不同的不一致性消除算法。本文方法在两种不同的数据集上都获得了很好的实验结果。