实体解析(entity resolution, 简称ER)是数据集成和数据清洗的重要组成部分, 它将数据源中描述相同实体的记录分到同一组^[1-15].大数据具有多样性的特点, 描述同一实体的记录可能以多种形式出现, 成为大数据可用性的一个瓶颈, 因此, ER是大数据分析与挖掘的必要预处理操作^[15].传统的ER包括分块、相似性计算和匹配决定等步骤, 将整个脏数据集作为输入, 批处理之后整体输出解析结果^{[1, 3]}.在大数据时代, 一方面, 数据产生的速度和更新的频率比以往更快; 另一方面, 大量(近似)实时的数据分析应用出现要求有限的时间内解析出尽量多的匹配记录, 称为时间约束的实体解析(entity resolution with time constraint, 简称TC-ER), 传统的批处理ER无法满足这种新需求.

当前有很多时间约束的ER应用, 例如犯罪侦查应用中要求近似实时的实体解析, 希望在较短时间内解析出一部分嫌疑人记录来, 以便及时地布署侦查行动.尽管短时间内解析的结果不完整, 但及时的解析结果可以大大增加抓捕到嫌疑人的可能性.再例如网购比价服务(如一淘网)中, 互联网用户搜索了一件商品后, 系统将尽快返回一部分匹配的商品条目, 并逐渐优化搜索结果, 这样可以提升用户体验, 因为众所周知, 互联网用户是没有耐心的.

时间约束的ER希望在给定的短时间(远少于批处理运行时间)内将解析结果最大化.TC-ER的关键在于实体解析过程中的记录对选择, 即优先选择匹配可能性大的记录对进行解析.Whang等人提出了3个基于“线索”的启发式Pay-as-you-go ER方法, 其中的“线索”分别是排序的记录对列表、记录集合的层次划分和排序的记录列表^[6].Papenbrock等人提出一组基于排序的记录列表的渐进式ER方法, 其中, 渐进式滑动窗口方法将变化的窗口多次滑过排序列表生成候选对; 渐进式分块方法将排序列表划分成等规模小块, 然后渐进地扩大分块范围^[7]. Papenbrock等人提出的基于排序列表的方法要优于Whang等人提出的基于“线索”的方法^[7].这些方法都假定已知最优分块键或排序键, 并且无法对记录对进行全局排序, 因此可用性和实时召回率都比较受限.由此可见, 已有的时间约束的ER方法有较大的改进空间.

本文研究时间约束的实体解析中记录对排序, 通过优先选择匹配可能性高的记录对进行解析, 来保证实时的召回率.分块是ER中降低计算代价的基本的、有效的手段^[16-26], 然而单凭分块方法无法实现时间约束的ER.整体而言, 将分析和挖掘分块信息来估计记录对的相似性.将脏数据集进行多路分块后生成有交叠的块集合, 如果一个块包含的记录越多, 那么块内记录的匹配可能性越小; 如果两条记录共同出现的块数目越多, 那么它们的匹配可能性越大.首先, 基于这些直观的思想, 提出两个基本的记录对相似性估计方法, 分别利用了块内信息和块间信息.接下来, 通过考虑记录对的相似性与块的质量之间的相互影响来改进基本的相似性估计方法.将记录对、块及其关联关系映射成二分图; 然后相似性在二分图上迭代地传播, 直到收敛, 获得最终的相似性.基于图传播的相似性估计充分挖掘了分块的隐藏信息, 从而更有效.提出了基于不动点迭代的收敛结果计算方法, 然而其计算代价较大; 进一步提出了近似的收敛结果计算方法, 力求在不影响记录对相似性估计有效性的前提下降低计算代价, 从而保证时间约束的ER的实时召回率.通过实验评估, 证明了提出方法的有效性.

本文的主要贡献总结如下:

●提出两种基本的记录对相似性估计方法, 分别利用了块的质量(块内信息)和记录与不同块的隶属关系(块间信息);

●提出了基于相似性传播的记录对相似性估计方法, 利用二分图上可收敛的相似性传播来衡量记录对的相似性, 通过不动点迭代来计算收敛结果, 并提出了近似方法来降低计算代价;

●在两个数据集上, 通过与已有方法的对比测试, 证明了本文提出方法的有效性; 此外, 对比了不同的相似性估计方法的表现, 并测试了迭代次数对基于相似性传播的记录对相似性估计方法的影响.

本文第1节定义研究的问题, 并概括地介绍研究框架.第2节介绍两种基本的记录对相似性估计方法.第3节提出基于二分图上相似性传播的记录对相似性估计方法, 并通过近似方法降低计算代价.第4节在两个数据集上评价本文提出的方法, 验证其有效性.第5节介绍相关工作.最后总结全文, 并指出下一步可能的研究方向.

1 研究概述

定义1(实体解析).给定一个脏数据集R={r}, ER将描述相同实体的记录分到一组, $C=\left\{c_{k} | \forall r_{i} \in c_{k}, r_{i} \in R \wedge\right.$, 其中, $\varphi $$\left.\varphi\left(r_{i}\right)=e_{k} \wedge \nexists r_{j} \in c_{l} \wedge \varphi\left(r_{j}\right)=e_{k}\right\}$(·)是从记录到实体的映射函数, e_k表示分组c_k对应的实体, c_l为不同于c_k的一个分组.

如图 1所示, ER传统上是批处理操作, 通常包括3个步骤:分块、相似度计算和匹配决定, 其中, 前者是可选步骤, 后两者是必要步骤^[1].

(1) 相似性计算

利用记录相似性函数计算两条记录的相似性, 通常, 相似性表示为[0, 1]范围内的数值.两条记录的相似性越大, 匹配可能性越大, 0表示不可能匹配, 1表示完全匹配.记录通常包括多个属性, 比如, 一条个人信息的记录包括姓名、年龄、工作单位、城市、省份和邮编等, 不同的属性需要使用不同的相似性函数来计算相似性.记录属性以文本型为主, 以数字型为辅.针对文本属性, 目前已有多种字符串相似性函数, 如TF-IDF、Q-gram、Jaccard、编辑距离等^[27].针对数字属性, 则需要采用专门的函数进行比较, 比如差值、汉明距离等.记录相似性函数选择多个属性, 分别选择适合的相似性函数来计算属性相似性, 最后将多个属性相似性聚集得到记录相似性, 聚集方式包括线性组合、非线性组合等, 与匹配决定的策略相关.

(2) 匹配决定

根据记录的相似性来决定记录是否匹配有两类方法:分类和聚类.基于分类的匹配决定使用支持向量机(support vector machine, 简称SVM)、遗传算法、主动学习和决策树等方法来决定记录对是否匹配^[3].一部分分类方法是监督的, 需要专家标注大量的训练数据, 从而学习出有效的匹配规则(即分类器).还有一部分分类方法的匹配规则是由领域专家定义的, 需要较多的领域知识.基于聚类的匹配决定使用MinCut, Markov Clustering等聚类算法来处理成对的相似性, 得到的聚类结果即为实体解析结果.同一类簇表示同一实体, 不同类簇表示不同实体^{[2, 28]}.本文将ER当作分类问题, 认为匹配规则已获得, 记作m(*, *), 也称为解析函数.如果m(r_i, r_j)返回真, 记录r_i, r_j匹配; 否则, m(r_i, r_j)返回假, 记录r_i, r_j不匹配.

(3) 分块

实体解析是两两比较的运算, 因此计算代价为平方级.当待处理的脏数据集规模较大时, 计算代价将是巨大的, 并且包含大量的无用计算.分块是ER中最常用的减小计算代价的技术^[16-26], 可以在不影响解析质量的前提下, 有效地缩小搜索空间.分块技术将描述可能匹配的记录分到同一块内, 将不可能匹配的记录分在不同的块内.分块通过分块键(blocking key, 简称BK)来实现, 而BK通过记录属性来构建.当利用一个分块键对数据集进行划分后, 拥有相同分块键值(blocking key value, 简称BKV)的记录将进入同一块内.同一块内的任意两条记录称为候选匹配记录对或候选对.

定义2(时间约束的实体解析).给定一个脏数据集R, 传统的ER处理R的时间为T_ER, 给定时间t < < T_ER, 时间约束的ER将输出尽量多的匹配记录对.给定时间t内, TC-ER比传统ER输出更多的匹配记录对, 如果运行到自然终止, 那么两者的解析结果是相同的.显然, 当解析函数的准确率确定时, 一个TC-ER方法的好坏由时效性和解析的召回率共同决定, 可以通过实时召回率来评价.

TC-ER的流程见算法1.

算法1. TC-ER框架.

输入:脏数据集R, 时间预算t;

输出:解析结果Λ.

1.对R进行多路分块, 得到块集合B;      //参考定义3

2.利用B中分块信息来估计候选对的相似性;      //本文的核心工作所在

3. repeat

4.根据估计的相似性, 对部分候选对进行排序, 得到候选列表list;

5.根据部分排序结果list, 依次对候选对进行解析;      //包括相似性计算和匹配决定

6.实时地输出解析结果Λ;

7. until (执行时间 > t) or (剩余候选对为0)

观察算法1可知, TC-ER的核心问题在于优化实体解析的顺序, 优先解析匹配可能性大的记录对.如图 1所示, 在分块与相似度计算之间增加记录对排序.记录对排序的依据是记录对的匹配可能性, 即估计的记录对相似性, 因此, TC-ER的关键在于如何通过较小的代价准确地估计记录对的相似性.

本文将通过分析和挖掘分块信息来估计记录对的相似性:(1)第2节提出两个基本的记录对相似性估计方法, 这两个方法分别从分块质量和记录-块的隶属关系的角度来分析块信息, 从而估计记录对相似性; (2)第3节提出基于相似性传播的记录对相似性估计方法, 将记录对、块及其关联关系表示为二分图, 并通过迭代的传播算法来挖掘分块信息, 从而改进基本的相似性估计.

定义3(多路分块).给定一个脏数据集R={r}和一组分块键的集合BK={bk_i|0≤i < K}, 依次利用bk_i∈BK对R进行分块, 得到有交叠的块集合B_mul=B¹∪B²∪…∪B^K={b}, Bⁱ表示用分块键bk_i生成的无交叠的块集合.任意r∈R最多可能出现在K个块内, 也称为K路分块, K为多路分块的路数.

b表示块, 块中的一对记录r_i, r_j∈b称为候选对, 记作〈r_i, r_j〉; |b|表示块b的规模, ||b||表示块b的势(cardinality), 即块内候选对的数目, 记作||b||=|b|(|b|-1)/2.|B|表示块集合B的规模, ||B||表示块集合B的势, 即集合内候选对的总数目.B_i表示记录r_i所在块的集合.

2 基本的记录对相似性估计

本节提出两种基本的相似性估计方法(basic estimated similarity, 简称BES), BES通过直观地分析分块信息来计算记录对的相似性.

2.1 基于块质量的记录对相似性估计

给定一个块, 这个块包含的记录对越多, 那么这个块内的任意一个记录对的匹配可能性越小.将一个块内记录对的匹配可能性的平均值称为块的冗余性.一个块的信息量是确定的, 块内的记录对越多, 那么每个记录对平均分得的信息量就越小, 块的冗余性就越小.将用冗余性(redudancy, 简称rd)评估块的质量, 表示为公式(1):

$ r d\left(b_{i}\right)=1 /\left\|b_{i}\right\| $

(1)

例如, 块b₁包括一个记录对, 块b₂包括3个记录对, 那么rd(b₁)=1 > rd(b₂)=1/3.

给定一个记录对〈r_i, r_j〉, 将它所在块的冗余性进行聚集来估计相似性, 如公式(2), 记作RD-ES, 其中, K是多路分块的路数, 通过K来规约, 保证相似性落在[0, 1]范围:

$e{s_{RD}}({r_i}, {r_j}) = \frac{1}{K}\sum\limits_{{b_k} \in {B_i} \cap {B_j}} {rd({b_k})} $

(2)

2.2 基于Jaccard系数的记录对相似性估计

对于一对记录〈r_i, r_j〉, 如果两者共同出现在越多的块中, 那么两者的相似性应该越大; 另一方面, 如果两者分别出现在越多的不同块中, 那么两者的差异性应该越大.通过Jaccard系数可以表达上述思想, 用一个对记录的共同出现的块的数目除以这对记录各自出现的块的并集的规模, 如公式(3), 记作JC-ES:

$e{s_{JC}}({r_i}, {r_j}) = \frac{{|{B_i} \cap {B_j}|}}{{|{B_i} \cup {B_j}|}}$

(3)

3 基于相似性传播的记录对相似性估计

BES通过静态地分析分块信息来估计记录对的相似性, 没有考虑记录对相似性与块质量的潜在的相互影响.将通过记录对-块之间的相似性传播来改进BES, 称为基于相似性传播的相似性估计(similarity propagation based estimated similarity, 简称SP-ES).显然, SP-ES是以RD-ES或者JC-ES为基础的.

例1:一个脏数据集d={r₁, r₂, r₃, r₄, r₅, r₆, r₇}, 经过分块得到块集合B={b₁, b₂, b₃, b₄}, b₁={r₁, r₂, r₃}, b₂={r₂, r₃}, b₃= {r₄, r₅, r₆}, b₄={r₅, r₇}, 如图 2(a)所示; 块集合可表示为记录对形式, B'={b_p1, b_p2, b_p3, b_p4}, b_p1={p₁₂, p₁₃, p₂₃}, b_p2={p₂₃}, b_p3={p₄₅, p₄₆, p₅₆}, b_p4={p₅₇}, 如图 2(b)所示.关注两个候选对p₁₂和p₄₅, 利用两个BES方法估计相似性, 得到如下结果:(1) RD-ES, es_RD(p₁₂)=1/3, es_RD(p₄₅)=1/3, 即es_RD(p₁₂)=es_RD(p₄₅); (2) JC-ES, es_JC(p₁₂)=1/2, es_JC(p₄₅)=1/2, 即es_JC(p₁₂)= es_JC(p₄₅).两个BES方法都认为p₁₂和p₄₅的相似性是相等的.然而进一步分析分块情况发现:p₂₃来自块b₂的相似性可以增强块b₁的冗余性, 进而p0₁₂从块b₁获得更大的相似性; 而块b₃不存在此类状况.由此可见, 应该有es(p₁₂) > es(p₄₅).接下来, 将通过相似性传播来改进BES, 解决上述问题.

3.1 相似性传播的基本思想

本文中, 相似性传播的基本思想为:记录对的相似性可以促进所在块的冗余性, 块的冗余性可以促进块内记录对的相似性.为了充分地表示记录对与块之间的关联关系, 将分块结果表示为“记录对-块”二分图(严格描述见定义4).相似性传播是一种基于图结构的相似性计算方法^{[29, 30]}, 充分地挖隐藏信息, 可以弥补其他相似性的不足.将通过例2来直观地了解记录对与块之间的相似性传播.

定义4(“记录对-块”二分图, 简称“对-块图”).给定一个记录对形式的块集合B, B对应的候选对集合为P, 构建一个无向的二分图G=(V_p, V_b, E), 其中, V_p={v_pi|0≤i≤m}为记录对结点集合, 每个记录对结点对应一个记录对; V_b={v_bj|0≤j≤n}为块结点集合, 每个块结点对应一个块; E⊂V_p×V_b是边集合, 表示记录对与块的隶属关系.可以结合上方向来解读边的含义, 给定一条边, 从块结点到记录对结点, 表示“包含”关系; 而从记录对结点到块结点, 则表示“出现在”关系.本文为了便于表达, 将用P同时表示记录对结点集合和记录对集合, 用p同时表示记录对结点和记录对, 用B同时表示块结点集合和块集合, 用b同时表示块结点和块.

例2:续例1.将例1中B'表示为二分图G, 如图 3所示.初始时, 用RD-ES来估计记录对相似性(es), 所有块冗余性(rd)初始化为0, 得到表 1中第1行的初始值.接下来, 相似性通过二分图传播.

(1) P→B传播.以图 3(a)为例, 记录对结点p₁₂和p₁₃分别传递各自当前的相似性(都是1/3)给邻接的块结点b_p1, p₂₃将当前的相似性4/3分别传递给邻接的块结点b_p1和b_p2; b_p1获得3个相似性(分别为1/3, 1/3, 4/3), 取均值为2/3作为更新的冗余性, 同理, b_p2更新的冗余性为4/3, 对G所有的连通分量进行相同的操作后, 得到表 1中第2行的结果;

(2) B→P传播.以图 3(a)为例, 块结点b_p1将当前的冗余性2/3传给邻接的记录对结点p₁₂, p₁₃和p₂₃, b_p2将当前的冗余性4/3传给邻接的结点p₂₃; 记录对结点p₁₂和p₁₃分别获得一个冗余性2/3, 分别作为各自最新的相似性, 同理, p₂₃获得两个冗余性2/3和4/3, 求和得到2作为p₂₃最新的相似性(此处为简单的计算方式, 后续将给出严格的计算方式), 对G所有的连通分量进行相同的操作后, 得到表 1中第3行的结果.

经过一次P→B→P传播后, es(p₁₂)=2/3, es(p₄₅)=1/3, 那么es(p₁₂) > es(p₄₅), 符合例1中提出的预期.可见, 相似性传播有助于准确地估计记录对的相似性, 弥补基本的相似性估计方法的不足.

3.2 基于对-块图的相似性传播

接下来, 严格地定义对-块图上相似性传播.首先定义两个单步传播:从记录对结点到块结点(P→B)的传播和从块结点到记录对结点(B→P)的传播.然后, 在单步传播的基础上定义迭代的相似性传播.

定义5(P→B传播).给定一个对-块图G=(P, B, E), p_ij∈P, b_k∈B, p_ij与b_k是邻接结点, p_ij将当前的相似性传递给每一个邻接的块结点, b_k从每个邻接记录对结点接受相似性, 并求平均值作为最新的冗余性, 如公式(4)所示:

$rd({b_k}) = \frac{1}{{|N({b_k})|}}\sum\limits_{{p_{ij}} \in N({b_k})} {es({p_{ij}})} $

(4)

其中, N(b_k)表示b_k的相邻结点的集合.

一次P→B传播后, 所有块结点的冗余性将更新, 而记录对结点的相似性不变.

定义6(B→P传播).给定一个对-块图G=(P, B, E), p_ij∈P, b_k∈B, p_ij与b_k是邻接结点, b_k将当前的冗余性传递给每一个邻接的记录对结点, p_ij从每个邻接块结点接受冗余性, 求和后除以K作为最新的冗余性, 如公式(5)所示:

$es({p_{ij}}) = \frac{1}{K}\sum\limits_{{b_k} \in N({p_{ij}})} {rd({b_k})} $

(5)

一次B→P传播后, 所有记录对结点的相似性将更新, 而块结点的冗余性不变.

参数K是多路分块的路数, 公式(5)中除以K是为了将es值规约到[0, 1]范围内, 一个记录对最多可能出现在K个块内.es的规约对于后续迭代计算的收敛性非常重要.

定义7(P↔B传播).给定一个对-块图G=(P, B, E), 初始的记录对相似性通过BES得到, 初始的块冗余性为0.经过一次P→B传播, 更新块冗余性; 再经过一次B→P传播, 更新记录对相似性.如此不断迭代, 直到记录对相似性不再发生变化.容易知道, P↔B传播是不可约、非周期、有限状态的马尔可夫链, 因此必定收敛于平稳分布^[29].

例3:对图 3(a)进行一次P→B→P传播, 其中多路分块的路数K≥2.初始时, 各记录对相似性记作es₀(p₁₂), es₀(p₁₃)和es₀(p₂₃).

(1) P→B传播.根据定义5, 计算得到更新的块冗余性:

$\left. \begin{gathered} r{d_1}({b_{p1}}) = e{s_0}({p_{12}})/3 + e{s_0}({p_{13}})/3 + e{s_0}({p_{23}})/3, \\ r{d_1}({b_{p2}}) = e{s_0}({p_{23}}) \\ \end{gathered} \right\}$

(6)

(2) B→P传播.根据定义6, 利用公式(6)的计算结果, 计算得到更新的记录对相似性:

$\left. \begin{gathered} e{s_1}({p_{12}}) = e{s_0}({p_{12}})/3K + e{s_0}({p_{13}})/3K + e{s_0}({p_{23}})/3K, \\ e{s_1}({p_{13}}) = e{s_0}({p_{12}})/3K + e{s_0}({p_{13}})/3K + e{s_0}({p_{23}})/3K, \\ e{s_1}({p_{23}}) = e{s_0}({p_{12}})/3K + e{s_0}({p_{13}})/3K + 4e{s_0}({p_{23}})/3K \\ \end{gathered} \right\}$

(7)

可以发现, 等式组(7)是记录相似性的递推关系, 它隐藏了块结点, 将P→B→P传播转化为P→P传播.

3.3 不动点计算

P↔B传播的收敛结果计算可以作为一个不动点计算(fixpoint computation)的问题.本文主要关注记录对相似性, 因此直接使用记录对相似性的递推关系.将等式组(7)改写成向量与矩阵的运算形式, 如公式(8):

${\left( {\begin{array}{*{20}{c}} {e{s_1}({p_{12}})} \\ {e{s_1}({p_{13}})} \\ {e{s_1}({p_{23}})} \end{array}} \right)^T} = {\left( {\begin{array}{*{20}{c}} {e{s_0}({p_{12}})} \\ {e{s_0}({p_{13}})} \\ {e{s_0}({p_{23}})} \end{array}} \right)^T}\left( {\begin{array}{*{20}{c}} {1/3K}&{1/3K}&{1/3K} \\ {1/3K}&{1/3K}&{1/3K} \\ {1/3K}&{1/3K}&{4/3K} \end{array}} \right)$

(8)

其中, 向量为行向量.公式(8)中的3×3矩阵是一个马尔可夫链的转移矩阵, 记作Q₀={q_ij|0≤i, j < 3}, q_ij表示从状态i转移到状态j的概率, Q₀不要求为对称阵.特别地, K的存在确保0≤q_ij≤1, 并进一步保证P↔B传播的收敛性(例3中K≥2);如果去掉K, 则Q₀不再是转移矩阵, P↔B传播不一定收敛.计算P↔B传播的关键是转移矩阵, 接下来讨论如何计算转移矩阵.

定义8(邻接矩阵).给定一个对-块图G=(P, B, E), P={p_i|0≤i < m}, B={b_j|0≤j < n}, E⊂P×B, G的对→块邻接矩阵为公式组(9)中的A_mn, 块→对邻接矩阵则为A_nm=(A_mn)^T.

$\begin{gathered} {\mathit{\boldsymbol{A}}_{\mathit{\boldsymbol{mn}}}} = \{ {a_{ij}}|0 \leqslant i < m, 0 \leqslant j < n\} \\ {a_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1, {\rm{ }}{e_{ij}} \in E} \\ {0, {\rm{ }}{e_{ij}} \notin E} \end{array}} \right. \\ \end{gathered} $

(9)

定义9(转移矩阵).给定一个对-块图G和对→块邻接矩阵A_mn, 那么对→块转移矩阵Q_mn为

${\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mn}}}} = \{ {q_{ij}}|{q_{ij}} = {{{a_{ij}}} / {\sum {{a_{i*}}} }}, {a_{ij}} \in {\mathit{\boldsymbol{A}}_{\mathit{\boldsymbol{mn}}}}\} $

(10)

同理, 可以根据块→对邻接矩阵A_nm计算得到块→对转移矩阵Q_nm.

用矩阵来表示P→B→P传播, 当前记录对的相似性向量为es_x, 块的冗余性向量为rd_x.那么:

(1) P→B传播.块冗余性更新:

$\mathit{\boldsymbol{rd}}_{x + 1}^T = \mathit{\boldsymbol{es}}_{\boldsymbol{x}}^T{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mn}}}}$

(11)

(2) B→P传播.记录对相似性更新:

$\mathit{\boldsymbol{es}}_{\mathit{\boldsymbol{x}} + 1}^T = \mathit{\boldsymbol{rd}}_{\mathit{\boldsymbol{x}} + 1}^T{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{nm}}}} = \mathit{\boldsymbol{es}}_\mathit{\boldsymbol{x}}^T{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mn}}}}{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{nm}}}}$

(12)

根据公式(12)易知, P→B→P传播的整体转移矩阵为Q_mm:

$ \begin{array}{*{20}{l}} {{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mm}}}} = {\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mn}}}}{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{nm}}}}} \end{array} $

(13)

对于记录对相似性, P→P传播与P→B→P传播等价, 进而P↔P传播与P↔B传播等价.

定义10(P↔P传播).给定一个对-块图G和P→P转移矩阵Q_mm, 与P↔B传播等价的P↔P传播中, 一次P→P传播可表示为

$\mathit{\boldsymbol{es}}_{\mathit{\boldsymbol{x}} + 1}^T = \mathit{\boldsymbol{es}}_\mathit{\boldsymbol{x}}^T{\mathit{\boldsymbol{Q}}_{\mathit{\boldsymbol{mm}}}}$

(14)

不动点计算的流程.

(1) 利用BES初始化记录对相似性向量为es₀;

(2) 利用公式(14)计算下一轮记录对相似性向量es_x+1;

(3) 不断迭代步骤(2), 直到残差向量(es_x+1, es_x)的每一维都小于.为残差阈值, 一般取一个较小常数, 例如0.005;

(4) 当迭代结束后, 将最终的记录对相似性向量记作es_sp, 作为基于相似性传播的相似性估计的结果输出.

代价分析:P↔P传播的一次迭代代价为O(m²), 迭代次数为X, 那么总代价为O(Xm²).对-块图G实际是由多个连通分量组成, 分量集合记作C={c_i}, |c_i| < < m, P↔P传播只发生在每个连通分量内部, 那么实际的代价:

$ O({\sum {{X_i}|{c_i}|} ^2}) < < O(X{m^2}). $

(15)

3.4 近似的相似性传播

P↔P传播的不动点计算的代价较大, 对于时间约束的ER来说不可接受.为此, 希望通过近似方法降低计算代价.下面将通过分析迭代过程中相似性传播的情况, 来说明较少的迭代次数可以近似地计算出相似性, 并极大地减小计算代价.

例4:图 4呈现了一个较大的对-块图, 观察记录对p₃, 其初始相似性为es₀(p₃), 第1次P→P传播后, p₃的相似性传递到p₃所在块的其他记录对p₁, p₂和p₄, p₅, 分别得到es₀(p₃)/6;第2次P→P传播后, p₃的相似性传递到块b₃中的记录对p₆, p₇, 分别得到es₀(p₃)/36;第3次P→P传播后, p₃的相似性传递到块b₄中的记录对p₈, p₉, 分别得到es₀(p₃)/216.可以发现:随着迭代次数的增加, 相似性传递得越来越远, 并且传递量发生指数级的衰减, 而计算代价成倍增长.从物理意义的角度分析, p₃与同一块内的记录对关联最强, 而与间接关联的记录对的关联强度则随距离增加而极大地减弱.由此得到启发, 用较少的P↔P传播的迭代来代替不动点计算, 即迭代次数X取较小数值, 如1或2.这样可以近似地计算出记录对相似性, 只损失微小的准确性, 但可以降低计算代价, 从而保证时间约束的ER的实时召回率.将通过实验验证这种近似方法的有效性.

4 实验评价 4.1 实验设置

实验代码通过Java实现, Java版本为1.7.运行环境如下:处理器3.4GHz Intel(R) Core i7-2600, 内存8GB, 操作系统为微软Windows 10专业版(64位).

●数据集.

实验评价使用两个数据集:一个真实数据集和一个合成数据集.真实的引文数据集DBLP-Scholar(记作DBLP)包含66 879条引文记录, 其中有5 347对匹配记录, 通过标题、作者、期刊/会议、年份等4个属性描述^[3].利用Febrl数据生成器构建一个合成的个人信息数据集(记作FB), 包含150K条个人记录, 其中有81 694对匹配记录, 通过姓名、性别、生日、住址、城市、州和邮编等8个属性描述^{[32, 33]}.

●评价指标.

本文的研究目标是优化实体解析顺序, 认为解析函数已提前确定, 准确率与研究目标是正交关系, 因此采用实时召回率来评估方法.在第4.3节的部分对比测试中, 还采用Top-N命中率来评价, 将在后续详细介绍.

●解析函数.

本文采用SVM来训练分类器作为解析函数m(*, *)^[33].

●方法设置.

对DBLP-Scholar数据集进行四路分块, 4个分块键为标题的前3个实词、姓+名的前两个字母、期刊/会议的前3个实词和年份.对FB数据集进行四路分块, 4个分块键为姓+名的前两个字母、生日、城市和邮编.渐进式滑动窗口(progressive sorted neighborhood method, 简称PSNM)方法、渐进式分块(progressive blocking, 简称PB)方法和以记录对排序列表(sorted list of record pairs, 简称SLORP)为线索的方法的排序键^{[6, 7]}:DBLP-Scholar数据集上采用标题的前3个实词+前两个作者的姓; FB数据集上采用姓+名+城市.如果没有特别说明, SP-ES的迭代次数设置为1.TC-ER默认采用基于RD-ES的SP-ES来估计记录对相似性, 记作TC-ER0;将采用基于JC-ES的SP-ES的TC-ER记作TC-ER1;将采用RD-ES的TC-ER记作TC-ER2;将采用JC-ES的TC-ER记作TC-ER3.

4.2 综合测试

综合测试将TC-ER0与一个基准方法以及3个已有工作进行对比.Papenbrock等人提出的基于排序列表的PSNM和PB已经被证明优于Whang等人提出的基于“线索”的方法, 而基于“线索”的方法中表现最好的为SLORP^{[6, 7]}, 因此选择PSNM, PB和SLORP这3个方法作为比较对象.基准方法采用m(*, *)直接解析分块后生成的候选对, 记作Baseline.将随机地生成10个候选对顺序, 分别执行Baseline方法, 将10次的结果取平均值作为Baseline的结果.PSNM将从小到大扩展的窗口多次滑过排序的记录列表, PB先根据排序的记录列表生成同等规模的小块, 然后逐渐拓展分块范围, 这两个方法都渐进地生成候选对, 从而优先处理匹配可能性大的记录对^[7]. SLORP通过排序的记录列表一次性生成排序的记录对列表, 并根据记录对顺序来依次进行解析^[6].PSNM, PB和SLORP都要依赖于排序的记录列表, 其排序键请参考第4.1节中的方法设置.

图 5和图 6分别呈现了在DBLP数据集上和FB数据集上5个方法的对比情况.

总体而言, 存在TC-ER0 > > PSNM, PB > SLORP > Baseline.TC-ER0的实时召回率显著地高于其他4个方法; PSNM, PB和SLORP明显优于Baseline; PSNM, PB明显优于SLORP; 在前期时, PSNM总优于PB, PB在后期可能有机会超越PSNM(如在FB数据集上).例如:在DBLP数据集上, TC-ER0花费11.5s解析出82.47%的匹配对, PSNM花费13s只能解析出56.69%的匹配对, PB花费16s只能解析出57.18%的匹配对, SLORP花费17s只能解析出55.41%的匹配对, Baseline花费18s甚至只能解析出46.19%的匹配对; 在FB数据集上, TC-ER0花费22s解析出88.9%的匹配对, 而PSNM花费34s解析出62.47%的匹配对, PB花费36s解析出51.72%的匹配对, SLORP花费35s解析出40.41%的匹配对, Baseline花费42s只能解析出33.67%的匹配对.由此可见, 在较少时间预算约束下, TC-ER0可以解析出更多的匹配对.Baseline的实时召回率随时间线性增长, 因为它随机地解析候选对, 解析顺序没有任何优化.PSNM在迭代中由小到大调整窗口, 以此来优化候选对的解析顺序; PB通过逐渐拓展分块范围来优化解析顺序; SLORP通过粗糙的方法来估计候选对的相似性来优化解析顺序.因此, 它们的实时召回率要比Baseline高.然而, PSNM和PB无法将候选对按匹配可能性排序, 无法直接定位到最可能匹配的候选对; SLORP虽然对候选进行了全排序, 但其相似性估计十分粗糙, 同样无法直接定位到最可能匹配的候选对, 甚至不如前两者的表现.这些原因局限了PSNM, PB和SLORP的实时召回率.TC-ER0则通过基于相似性估计的候选对排序来全局地优化解析顺序, 从而获得最高的实时召回率.

再者, 观察最终召回率和运行时间.

(1) PSNM, PB和SLORP的最终召回率要低于TC-ER0和Baseline.前三者只有一个排序键, 只产生一个记录排序列表, 由此生成的候选对集合对真实的匹配对覆盖较少; 而后两个方法, 通过多路分块生成候选对集合, 可以更好地覆盖真实的匹配对.如果将PSNM和PB扩展到多个排序键AC-PSNM和AC- PB, 可以提高最终召回率, 但这样要维护多个排序列表并依次滑动, 会大大增加实时的计算代价和总的计算代价, 明显降低实时召回率;

(2) 就总的运行时间而言, TC-ER0, PSNM, PB和SLORP都比Baseline要长, 因为前四者针对解析顺序的预处理操作花费了一定的时间, 而Baseline没有预处理操作.就预处理时间而言, TC-ER0要比PSNM, PB和SLORP稍长一些, 但它们的预处理时间占总运行时间的比例都极小.

4.3 分项测试 4.3.1 相似性估计测试

相似性估计测试将比较两个基本的相似性估计方法RD-ES, JC-ES和基于前两者的SP-ES方法在TC-ER中的表现, 对应该ER方法分别为TC-ER2(RD-ES), TC-ER3(JC-ES), TC-ER0(基于RD-ES的SP-ES)和TC-ER1(基于JC-ES的SP-ES).相似性估计方法的好坏将决定记录对排序的有效性, 进而影响实时召回率.图 7和图 8分别是在DBLP数据集上和FB数据集上4个方法的对比情况, Baseline作为参考.

整体而言, 就实时召回率而言, 在两个数据集上均有TC-ER0 > TC-ER1, TC-ER2 > TC-ER3 > Baseline.在DBLP数据集上, TC-ER0显著地优于其他3个方法; TC-ER1与TC-ER2不相上下, 但都明显优于TC-ER3.取单点进行对比, TC-ER0花费11.5s解析出82.47%的匹配对, TC-ER1花费13s解析出78.18%的匹配对, TC-ER2花费12s解析出71.54%的匹配对, TC-ER3花费15s只解析出63.41%的匹配对.在FB数据集上, TC-ER0显著地优于其他3种方法; TC-ER1微弱地优于TC-ER2, 但两者都明显优于TC-ER3.取单点进行对比, TC-ER0花费22s解析出88.9%的匹配对, TC-ER1花费26s解析出82.14%的匹配对, TC-ER2花费28s解析出75.38%的匹配对, TC-ER3花费29s只解析出65.94%的匹配对.接下来, 观察相似性传播对相似性估计的影响.分别对比TC-ER0和TC- ER2, TC-ER1和TC-ER3可以发现:TC-ER中, 基于相似性传播的相似性估计方法(TC-ER0和TC-ER1)要明显优于基本的相似性估计方法(TC-ER2和TC-ER3).相似性传播挖掘了记录与块之间隐藏的关联关系, 从而有效地改进了两个基本的相似性估计方法.最后, 分别对比TC-ER0和TC-ER1, TC-ER2和TC-ER3可以发现:在TR-ER中, 基于分块质量的相似性估计(对应TC-ER0和TC-ER2)要明显优于基于Jaccard系数的相似性估计(对应TC- ER1和TC-ER3), 说明分块质量可以更有效地帮助估计记录对的相似性.

4.3.2 SP-ES的迭代测试

本节测试TC-ER中SP-ES的迭代次数对相似性估计的影响, 验证近似的相似性传播的有效性.当残差阈值=0.005时, TC-ER0在DBLP数据集上和FB数据集上分别需要7次和11次迭代达到收敛.将从两个角度来进行测试:(1)在两个数据集上, 测试TC-ER0分别进行1, 2, 4和7次迭代的实时召回率的情况, 从直观上了解随着迭代次数的增加, 相似性估计和运行时间的变化情况; (2)在两个数据集上, 测试TC-ER0随着迭代次数的增加直到自然收敛过程中, Top-N命中率和启动时间的变化情况.

TC-ER0默认进行1次迭代, 现将TC-ER0分别进行2m4和7次迭代, 分别记作TC-ER0-2, TC-ER0-4和TC- ER0-7.图 9和图 10分别展示了在DBLP数据集上和FB数据集上这4种方法的对比情况, Baseline作为参考.

整体而言, 随着迭代次数的增加, 预处理的时间代价接近成倍地增加; 然而预处理之后的实时召回率却没有明显的提升, 即相似性估计的准确性只是非常微弱地提高.取单点来对比, 在DBLP数据集上, 运行时间为7s时, TC-ER0的实时召回率为65.63%, 而TC-ER0-2约为40%, TC-ER0-4和TC-ER0-7都为0;在FB数据集上, 运行时间为18s时, TC-ER0的实时召回率超过70%, 而TC-ER0-2为32.47%, TC-ER0-4和TC-ER0-7都为0.直观来看, 基于1次迭代SP-ES对于TC-ER来说是最佳的选择.

接下来, 从Top-N命中率和启动时间的角度来分析迭代的效果, Top-N命中率是指在观测的前N次比较中匹配对占的比例, 启动时间是指TC-ER0从启动运行到开始产生解析结果的时间间隔.将数据集中真实的匹配对数目设为N, 那么, 在DBLP数据集上N=5347, 在FB数据集上N=81694.图 11、图 12展示了TC-ER0方法在两个数据集上的Top-N命中率(对应主轴刻度)和启动时间(对应次轴刻度)随迭代次数增加而变化的情况.可以发现:随着迭代次数的增加, 命中率的提高非常小, 而启动时间则几乎是线性增长.由此可知, 迭代次数的增加不会明显提高相似性估计的准确性, 而启动时间大幅增长.结合图 9、图 10可知:随着迭代次数的增加, 实时召回率曲线的趋势变化微弱, 大体上是整体向后平移, 启动时间占总运行时间比重大幅增加.这导致解析结果输出推迟, 影响TC-ER0的表现.综上分析, 为了兼顾时效性和召回率, 应当选择较少的迭代次数, 1次迭代是TC-ER0的最好选择.

5 相关工作

实体解析是数据集成与数据清洗不可或缺的组成部分, 也称为实体识别、实体匹配、记录链接等^[1-15].传统的实体解析是批处理操作, 将整个数据集输入, 经过分块、相似性计算和匹配决定后, 输出解析结果^{[1, 2]}.这种整体解析的运行时间通常比较长.随着大数据产业的发展, 数据产生的速度和更新的频率与以往相比都有了质的飞跃, 而一些数据应用要求(近似)实时的响应, 因此时间约束的ER成为研究热点^{[6, 7]}.与本文相关的研究还包括分块技术和基于图的相似性传播.

Whang等人提出了Pay-as-you-go实体解析的概念:在运行时间或计算资源有限的情况下, 使得实体解析的输出结果最大化; 并定义了“线索”的概念, 帮助预测哪些记录的匹配可能性更大, 它需要与已有的ER方法结合起来使用^[6].Papenbrock等人提出了一组时间约束的ER方法, 它们都基于排序的记录列表^[7].渐进式滑动窗口(progressive sorted neighborhood method, 简称PSNM)通过从小到大扩大窗口来多次滑过列表, 渐进地生成候选对; 渐进式分块(progressive blocking, 简称PB)先根据记录列表生成同样规模的小块, 然后逐渐拓展分块范围, 渐进地生成候选对.在此基础上, 还对两个方法进行了多属性扩展, 同时生成多个排序列表, 并交替地对排序列表执行PSNM和PB, 从而提高总的召回率, 但同时也降低了渐进性.这两类方法都无法将所有候选对按匹配可能性进行全局排序, 限制了实时召回率; 再者, 两类方法都依赖于已知的分块键或排序键, 限制了适用范围.

分块是ER中最常用的降低时间开销的技术, 它可以有效地缩小搜索空间^[16-26].分块方法可分为两类:基于分块键的方法和基于排序键的方法.前者定义分块键(blocking key, 简称BK), 然后根据每条记录的属性信息生成对应的分块键值(blocking key value, 简称BKV), 最后将拥有相同BKV的记录分在同一块内, 分块方法以此类居多^{[17-20, 23-26]}.后者也称为滑动窗口方法, 首先定义排序键, 然后将记录按排序键值排序, 最后将一个窗口在记录列表上滑动来生成候选对^{[21, 22]}.

基于图的相似性传播可以挖掘结构信息来计算数据对象(data object)之间的相似性, 这类方法已经应用在了多个领域, 如模式匹配^[29]、联合式实体解析^[4]、推荐系统^[30]等.Melnick等人设计了SF(similarity flooding)算法来帮助模式匹配, 但其应用范围不局限于此^[29].将两个关系模式分别构建成模式图, 并根据领域知识计算出两个图之间结点的初步的相似性, 将这两个图作为SF算法的输入.SF将两个图中的结点建立映射关系, 并构建成一个成对的关联图, 图中的每个结点对应原模式图中一个映射结点对, 例如关联图中的三元组((x, y), p, (x', y')), 对应模式图中的两个三元组(x, p, x')和(y, p, y').相似性通过((x, y), p, (x', y'))的正向和反向不断迭代地传播, 迭代停止时每个结点上的对象对(例如(x, y))获得最终的相似性.利用SF最终的相似性可以决定模式匹配的结果.SF通过不动点计算来获得最终的相似性.如果相似性收敛, 那么SF自然终止; 如果不收敛, 则运行到SF设定的最大迭代次数时终止.Simrank是一个更通用的两两(pairwise)相似性计算方法, 其基本思想是:如果与两个对象关联的对象是相似的, 那么这两个对象也是相似的^[30].Simrank将一个有向的对象图转换成一个有向的对象对图, 对象对图与SF中的成对关联图类似, 也是((x, y), p, (x', y'))的形式.在对象对图中, 初始时将由同一对象组成的结点的相似性设为1, 其他结点的相似性为0.然后相似性在对象对图中沿着有向边不断传递, 直到收敛.在传递过程中, 一个结点(x, y)将相似性经过衰减少后传给它所有指向的结点; 另一个结点(x', y')从指向它的所有结点处获得相似性, 取均值作为自己最新的相似性.Simrank保证收敛性, 可以通过不动点计算获得收敛结果.Dong等人通过相似性传播来解析关联的数据, 例如引文数据、电影数据等^[4].以引文数据为例, 文章、作者及会议之间存在语义关联, 如果两个文章记录是匹配的, 那么它们的作者记录的匹配可能性将会增加.将关联的数据构建依赖图, 其中, 边既有单向的, 也有双向的.根据文本相似性来计算每个结点的初始相似性, 然后, 相似性通过有向边来传播.当某个结点的相似性超过阈值, 就认为它对应的记录是匹配的, 匹配的结点将进入非激活状态.不断迭代, 直到所有结点都被解析完.以上3种相似性传播都是在对象(记录)之间的传播, 而本文的相似性传播则是在记录与块之间进行.

当前, 还出现了一些新型的ER方法:Ramadan等人提出了面向查询的ER方法^[5]; Kushagrat等人针对ER中聚类问题, 提出了选择策略^[8]; Lin等人提出了面向异构记录的ER方法^[9]; 多个研究团队提出了基于图的ER方法^[10-12]; 多个研究团队提出了基于深度学习的ER方法^{[13, 14]}.

6 结束语

时间约束的实体解析是大数据研究的热点问题, 本文研究时间约束的ER中记录对相似性估计与排序.在多路分块的基础上, 分析块内信息, 提出了基于块质量的记录对相似性估计方法; 分析块间信息, 提出了基于Jaccard系数的记录对相似性估计方法.针对两个基本的相似性估计方法, 提出了基于相似性图传播的改进.构建记录对和块组成的二分图.在二分图上运行相似性传播, 在此过程中记录对的相似性动态变化, 直到收敛.提出了基于不动点迭代的收敛结果计算方法, 并提出了近似方法来降低计算代价.在一个真实数据集和一个合成数据集上测试提出的方法, 证明其有效性, 并测试了提出方法的各个方面的特点.在未来的工作中, 将研究联合式实体解析在时间约束条件下的解决方案.

本文由人工智能赋能的数据管理、分析与系统专刊特约编辑李战怀教授、于戈教授和杨晓春教授推荐.