时间约束的实体解析中记录对排序研究
时间约束的实体解析中记录对排序研究
摘 要:实体解析是数据集成和数据清洗的重要组成部分,也是大数据分析与挖掘的必要预处理步骤.传统的批处理式实体解析的整体运行时间较长,无法满足当前(近似)实时的数据应用需求.因此,研究时间约束的实体解析,其核心问题是基于匹配可能性的记录对排序.通过对多路分块得到的块内信息与块间信息分别进行分析,提出两个基本的记录匹配可能性计算方法.在此基础上,提出一种基于二分图上相似性传播的记录匹配可能性计算方法.将记录对、块及其关联关系构建二分图;相似性沿着二分图不断地在记录对结点与块结点之间传播,直到收敛.收敛结果可以通过不动点计算得到.提出近似的收敛计算方法来降低计算代价,从而保证实体解析的实时召回率.最后,在两个数据集上进行实验评价,验证了所提出方法的有效性,并测试方法的各个方面。
实体解析(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={ck|∀ri∈ck,ri∈r∧φ(ri)=ek∧∄rj∈cl∧φ(rj)=ek},其中,φ(⋅)是从记录到实体的映射函数,ek 表示分组ck 对应的实体,cl 为不同于ck 的一个分组.
如图1 所示,er 传统上是批处理操作,通常包括3 个步骤:分块、相似度计算和匹配决定,其中,前者是可选步骤,后两者是必要步骤[1].
fig.1 entity resolution model
图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(ri,rj)返回真,记录ri,rj 匹配;否则,m(ri,rj)返回假,记录ri,rj 不匹配.
(3)分块
实体解析是两两比较的运算,因此计算代价为平方级.当待处理的脏数据集规模较大时,计算代价将是巨大的,并且包含大量的无用计算.分块是er 中最常用的减小计算代价的技术[16−26],可以在不影响解析质量的前提下,有效地缩小搜索空间.分块技术将描述可能匹配的记录分到同一块内,将不可能匹配的记录分在不同的块内.分块通过分块键(blocking key,简称bk)来实现,而bk 通过记录属性来构建.当利用一个分块键对数据集进行划分后,拥有相同分块键值(blocking key value,简称bkv)的记录将进入同一块内.同一块内的任意两条记录称为候选匹配记录对或候选对.
定义2(时间约束的实体解析).给定一个脏数据集r,传统的er 处理r 的时间为ter,给定时间trd(b2)=1/3.
给定一个记录对〈ri,rj〉,将它所在块的冗余性进行聚集来估计相似性,如公式(2),记作rd-es,其中,k 是多路分块的路数,通过k来规约,保证相似性落在[0,1]范围:
2.2 基于jaccard系数的记录对相似性估计
对于一对记录〈ri,rj〉,如果两者共同出现在越多的块中,那么两者的相似性应该越大;另一方面,如果两者分别出现在越多的不同块中,那么两者的差异性应该越大.通过jaccard 系数可以表达上述思想,用一个对记录的共同出现的块的数目除以这对记录各自出现的块的并集的规模,如公式(3),记作jc-es:
3 基于相似性传播的记录对相似性估计
bes 通过静态地分析分块信息来估计记录对的相似性,没有考虑记录对相似性与块质量的潜在的相互影响.将通过记录对-块之间的相似性传播来改进bes,称为基于相似性传播的相似性估计(similarity propagation based estimated similarity,简称sp-es).显然,sp-es 是以rd-es 或者jc-es 为基础的.
例1:一个脏数据集d={r1,r2,r3,r4,r5,r6,r7},经过分块得到块集合b={b1,b2,b3,b4},b1={r1,r2,r3},b2={r2,r3},b3={r4,r5,r6},b4={r5,r7},如图2(a)所示;块集合可表示为记录对形式,b′={bp1,bp2,bp3,bp4},bp1={p12,p13,p23},bp2={p23},bp3={p45,p46,p56},bp4={p57},如图2(b)所示.关注两个候选对p12和p45,利用两个bes 方法估计相似性,得到如下结果:(1)rd-es,esrd(p12)=1/3,esrd(p45)=1/3,即esrd(p12)=esrd(p45);(2)jc-es,esjc(p12)=1/2,esjc(p45)=1/2,即esjc(p12)=esjc(p45).两个bes 方法都认为p12和p45的相似性是相等的.然而进一步分析分块情况发现:p23来自块b2的相似性可以增强块b1的冗余性,进而p12从块b1获得更大的相似性;而块b3不存在此类状况.由此可见,应该有es(p12)>es(p45).接下来,将通过相似性传播来改进bes,解决上述问题.
fig.2 an example of basic similarity estimations’ disadvantage
图2 基本的记录对相似性估计缺陷示例
3.1 相似性传播的基本思想
本文中,相似性传播的基本思想为:记录对的相似性可以促进所在块的冗余性,块的冗余性可以促进块内记录对的相似性.为了充分地表示记录对与块之间的关联关系,将分块结果表示为“记录对-块”二分图(严格描述见定义4).相似性传播是一种基于图结构的相似性计算方法[29,30],充分地挖隐藏信息,可以弥补其他相似性的不足.将通过例2 来直观地了解记录对与块之间的相似性传播.
定义4(“记录对-块”二分图,简称“对-块图”).给定一个记录对形式的块集合b,b 对应的候选对集合为p,构建一个无向的二分图g=(vp,vb,e),其中,vp={vpi|0≤i≤m}为记录对结点集合,每个记录对结点对应一个记录对;vb={vbj|0≤j≤n}为块结点集合,每个块结点对应一个块;e⊂vp×vb 是边集合,表示记录对与块的隶属关系.可以结合上方向来解读边的含义,给定一条边,从块结点到记录对结点,表示“包含”关系;而从记录对结点到块结点,则表示“出现在”关系.本文为了便于表达,将用p 同时表示记录对结点集合和记录对集合,用p 同时表示记录对结点和记录对,用b 同时表示块结点集合和块集合,用b 同时表示块结点和块.
例2:续例1.将例1 中b′表示为二分图g,如图3 所示.初始时,用rd-es 来估计记录对相似性(es),所有块冗余性(rd)初始化为0,得到表1 中第1 行的初始值.接下来,相似性通过二分图传播.
(1)p→b 传播.以图3(a)为例,记录对结点p12和p13分别传递各自当前的相似性(都是1/3)给邻接的块结点bp1,p23将当前的相似性4/3 分别传递给邻接的块结点bp1和bp2;bp1获得3 个相似性(分别为1/3,1/3,4/3),取均值为2/3 作为更新的冗余性,同理,bp2更新的冗余性为4/3,对g 所有的连通分量进行相同的操作后,得到表1 中第2 行的结果;
(2)b→p 传播.以图3(a)为例,块结点bp1将当前的冗余性2/3 传给邻接的记录对结点p12,p13和p23,bp2将当前的冗余性4/3 传给邻接的结点p23;记录对结点p12和p13分别获得一个冗余性2/3,分别作为各自最新的相似性,同理,p23获得两个冗余性2/3 和4/3,求和得到2 作为p23最新的相似性(此处为简单的计算方式,后续将给出严格的计算方式),对g 所有的连通分量进行相同的操作后,得到表1 中第3 行的结果.
经过一次p→b→p 传播后,es(p12)=2/3,es(p45)=1/3,那么es(p12)>es(p45),符合例1 中提出的预期.可见,相似性传播有助于准确地估计记录对的相似性,弥补基本的相似性估计方法的不足.
fig.3 an example of pair-block barpitite graph
图3“记录对-块”二分图示例
table 1 example of similairity propagation on bipartite graphs
表1 二分图上相似性传播示例
3.2 基于对-块图的相似性传播
接下来,严格地定义对-块图上相似性传播.首先定义两个单步传播:从记录对结点到块结点(p→b)的传播和从块结点到记录对结点(b→p)的传播.然后,在单步传播的基础上定义迭代的相似性传播.
定义5(p→b 传播).给定一个对-块图g=(p,b,e),pij∈p,bk∈b,pij 与bk 是邻接结点,pij 将当前的相似性传递给每一个邻接的块结点,bk 从每个邻接记录对结点接受相似性,并求平均值作为最新的冗余性,如公式(4)所示:
其中,n(bk)表示bk 的相邻结点的集合.
一次p→b 传播后,所有块结点的冗余性将更新,而记录对结点的相似性不变.
定义6(b→p 传播).给定一个对-块图g=(p,b,e),pij∈p,bk∈b,pij 与bk 是邻接结点,bk 将当前的冗余性传递给每一个邻接的记录对结点,pij 从每个邻接块结点接受冗余性,求和后除以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.初始时,各记录对相似性记作es0(p12),es0(p13)和es0(p23).
(1)p→b 传播.根据定义5,计算得到更新的块冗余性:
(2)b→p 传播.根据定义6,利用公式(6)的计算结果,计算得到更新的记录对相似性:
可以发现,等式组(7)是记录相似性的递推关系,它隐藏了块结点,将p→b→p 传播转化为p→p 传播.
3.3 不动点计算
p↔b 传播的收敛结果计算可以作为一个不动点计算(fixpoint computation)的问题.本文主要关注记录对相似性,因此直接使用记录对相似性的递推关系.将等式组(7)改写成向量与矩阵的运算形式,如公式(8):
其中,向量为行向量.公式(8)中的3×3 矩阵是一个马尔可夫链的转移矩阵,记作q0={qij|0≤i,j<3},qij 表示从状态i转移到状态j 的概率,q0不要求为对称阵.特别地,k 的存在确保0≤qij≤1,并进一步保证p↔b 传播的收敛性(例3 中k≥2);如果去掉k,则q0不再是转移矩阵,p↔b 传播不一定收敛.计算p↔b 传播的关键是转移矩阵,接下来讨论如何计算转移矩阵.
定义8(邻接矩阵).给定一个对-块图g=(p,b,e),p={pi|0≤i
定义9(转移矩阵).给定一个对-块图g 和对→块邻接矩阵amn,那么对→块转移矩阵qmn 为
同理,可以根据块→对邻接矩阵anm 计算得到块→对转移矩阵qnm.
用矩阵来表示p→b→p 传播,当前记录对的相似性向量为esx,块的冗余性向量为rdx.那么:
(1)p→b 传播.块冗余性更新:
(2)b→p 传播.记录对相似性更新:
根据公式(12)易知,p→b→p 传播的整体转移矩阵为qmm:
对于记录对相似性,p→p 传播与p→b→p 传播等价,进而p↔p 传播与p↔b 传播等价.
定义10(p↔p 传播).给定一个对-块图g 和p→p 转移矩阵qmm,与p↔b 传播等价的p↔p 传播中,一次p→p 传播可表示为
不动点计算的流程.
(1)利用bes 初始化记录对相似性向量为es0;
(2)利用公式(14)计算下一轮记录对相似性向量esx+1;
(3)不断迭代步骤(2),直到残差向量δ(esx+1,esx)的每一维都小于ε.ε为残差阈值,一般取一个较小常数,例如0.005;
(4)当迭代结束后,将最终的记录对相似性向量记作essp,作为基于相似性传播的相似性估计的结果输出.
代价分析:p↔p 传播的一次迭代代价为o(m2),迭代次数为x,那么总代价为o(xm2).对-块图g 实际是由多个连通分量组成,分量集合记作c={ci},|ci|>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 和acpb,可以提高最终召回率,但这样要维护多个排序列表并依次滑动,会大大增加实时的计算代价和总的计算代价,明显降低实时召回率;
(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 作为参考.
fig.7 similarity estimation test on dblp dataset
图7 在dblp 数据集上的相似性估计测试
fig.8 similarity estimation test on fb dataset
图8 在fb 数据集上的相似性估计测试
整体而言,就实时召回率而言,在两个数据集上均有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 和tcer2,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 系数的相似性估计(对应tcer1 和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 和tcer0-7.图9 和图10 分别展示了在dblp 数据集上和fb 数据集上这4 种方法的对比情况,baseline 作为参考.
fig.9 sp-es’s iteration test on dblp dataset
图9 在dblp 数据集上sp-es 的迭代测试
fig.10 sp-es’s iteration test on fb dataset
图10 在fb 数据集上sp-es 的迭代测试
整体而言,随着迭代次数的增加,预处理的时间代价接近成倍地增加;然而预处理之后的实时召回率却没有明显的提升,即相似性估计的准确性只是非常微弱地提高.取单点来对比,在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 的最好选择.
fig.11 sp-es’s hitting rate &start-up time tests on dblp dataset
图11 在dblp 数据集上sp-es 的top-n 命中率及启动时间测试
fig.12 sp-es’s hitting rate &start-up time tests on fb dataset
图12 在fb 数据集上sp-es 的top-n 命中率及启动时间测试
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 系数的记录对相似性估计方法.针对两个基本的相似性估计方法,提出了基于相似性图传播的改进.构建记录对和块组成的二分图.在二分图上运行相似性传播,在此过程中记录对的相似性动态变化,直到收敛.提出了基于不动点迭代的收敛结果计算方法,并提出了近似方法来降低计算代价.在一个真实数据集和一个合成数据集上测试提出的方法,证明其有效性,并测试了提出方法的各个方面的特点.在未来的工作中,将研究联合式实体解析在时间约束条件下的解决方案。
物联网智能技术应用协会举办智慧科技小镇的未来建设与发展的讲堂
跌涨如过山车比特币价格，扩容问题该如何顺利化解
LKT4101防抄板加密ic：开创嵌入式加密芯片市场新天地
哪种运动耳机好用、值得推荐的运动耳机
华为Mate40 Pro斩获六项大奖
时间约束的实体解析中记录对排序研究
智慧物流在应对新冠肺炎疫情当中优势凸显
锐龙7PRO 3700泄露 性价比将比锐龙7 3700X更胜一筹
什么是位置与姿态控制系统
一种可以根据应用场景灵活选择工作模式的片上RVG电路
三相断路器型号规格及其参数 浅谈三相断路器电流计算
苹果Micro-LED样品开始测试！最晚2019年Apple Watch将用上Micro-LED！
每个工程师都应该了解的有关热管理的事实
R类音频功率放大器CS8389E/CS8390E
欧洲客户来我厂考察和洽谈锡膏项目合作事宜
EDA工具应用在FPGA设计和IC设计中的应用介绍
SaaS行业风口正酣，声网容联云未来发力剑指何方？
NLP领域的难处
最大限度降低寄生电容对放大器稳定性影响的三种方案
30多名商业领袖在《纽约时报》发表，请将地球利益放在利润之上
摘 要:实体解析是数据集成和数据清洗的重要组成部分,也是大数据分析与挖掘的必要预处理步骤.传统的批处理式实体解析的整体运行时间较长,无法满足当前(近似)实时的数据应用需求.因此,研究时间约束的实体解析,其核心问题是基于匹配可能性的记录对排序.通过对多路分块得到的块内信息与块间信息分别进行分析,提出两个基本的记录匹配可能性计算方法.在此基础上,提出一种基于二分图上相似性传播的记录匹配可能性计算方法.将记录对、块及其关联关系构建二分图;相似性沿着二分图不断地在记录对结点与块结点之间传播,直到收敛.收敛结果可以通过不动点计算得到.提出近似的收敛计算方法来降低计算代价,从而保证实体解析的实时召回率.最后,在两个数据集上进行实验评价,验证了所提出方法的有效性,并测试方法的各个方面。
实体解析(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={ck|∀ri∈ck,ri∈r∧φ(ri)=ek∧∄rj∈cl∧φ(rj)=ek},其中,φ(⋅)是从记录到实体的映射函数,ek 表示分组ck 对应的实体,cl 为不同于ck 的一个分组.
如图1 所示,er 传统上是批处理操作,通常包括3 个步骤:分块、相似度计算和匹配决定,其中,前者是可选步骤,后两者是必要步骤[1].
fig.1 entity resolution model
图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(ri,rj)返回真,记录ri,rj 匹配;否则,m(ri,rj)返回假,记录ri,rj 不匹配.
(3)分块
实体解析是两两比较的运算,因此计算代价为平方级.当待处理的脏数据集规模较大时,计算代价将是巨大的,并且包含大量的无用计算.分块是er 中最常用的减小计算代价的技术[16−26],可以在不影响解析质量的前提下,有效地缩小搜索空间.分块技术将描述可能匹配的记录分到同一块内,将不可能匹配的记录分在不同的块内.分块通过分块键(blocking key,简称bk)来实现,而bk 通过记录属性来构建.当利用一个分块键对数据集进行划分后,拥有相同分块键值(blocking key value,简称bkv)的记录将进入同一块内.同一块内的任意两条记录称为候选匹配记录对或候选对.
定义2(时间约束的实体解析).给定一个脏数据集r,传统的er 处理r 的时间为ter,给定时间trd(b2)=1/3.
给定一个记录对〈ri,rj〉,将它所在块的冗余性进行聚集来估计相似性,如公式(2),记作rd-es,其中,k 是多路分块的路数,通过k来规约,保证相似性落在[0,1]范围:
2.2 基于jaccard系数的记录对相似性估计
对于一对记录〈ri,rj〉,如果两者共同出现在越多的块中,那么两者的相似性应该越大;另一方面,如果两者分别出现在越多的不同块中,那么两者的差异性应该越大.通过jaccard 系数可以表达上述思想,用一个对记录的共同出现的块的数目除以这对记录各自出现的块的并集的规模,如公式(3),记作jc-es:
3 基于相似性传播的记录对相似性估计
bes 通过静态地分析分块信息来估计记录对的相似性,没有考虑记录对相似性与块质量的潜在的相互影响.将通过记录对-块之间的相似性传播来改进bes,称为基于相似性传播的相似性估计(similarity propagation based estimated similarity,简称sp-es).显然,sp-es 是以rd-es 或者jc-es 为基础的.
例1:一个脏数据集d={r1,r2,r3,r4,r5,r6,r7},经过分块得到块集合b={b1,b2,b3,b4},b1={r1,r2,r3},b2={r2,r3},b3={r4,r5,r6},b4={r5,r7},如图2(a)所示;块集合可表示为记录对形式,b′={bp1,bp2,bp3,bp4},bp1={p12,p13,p23},bp2={p23},bp3={p45,p46,p56},bp4={p57},如图2(b)所示.关注两个候选对p12和p45,利用两个bes 方法估计相似性,得到如下结果:(1)rd-es,esrd(p12)=1/3,esrd(p45)=1/3,即esrd(p12)=esrd(p45);(2)jc-es,esjc(p12)=1/2,esjc(p45)=1/2,即esjc(p12)=esjc(p45).两个bes 方法都认为p12和p45的相似性是相等的.然而进一步分析分块情况发现:p23来自块b2的相似性可以增强块b1的冗余性,进而p12从块b1获得更大的相似性;而块b3不存在此类状况.由此可见,应该有es(p12)>es(p45).接下来,将通过相似性传播来改进bes,解决上述问题.
fig.2 an example of basic similarity estimations’ disadvantage
图2 基本的记录对相似性估计缺陷示例
3.1 相似性传播的基本思想
本文中,相似性传播的基本思想为:记录对的相似性可以促进所在块的冗余性,块的冗余性可以促进块内记录对的相似性.为了充分地表示记录对与块之间的关联关系,将分块结果表示为“记录对-块”二分图(严格描述见定义4).相似性传播是一种基于图结构的相似性计算方法[29,30],充分地挖隐藏信息,可以弥补其他相似性的不足.将通过例2 来直观地了解记录对与块之间的相似性传播.
定义4(“记录对-块”二分图,简称“对-块图”).给定一个记录对形式的块集合b,b 对应的候选对集合为p,构建一个无向的二分图g=(vp,vb,e),其中,vp={vpi|0≤i≤m}为记录对结点集合,每个记录对结点对应一个记录对;vb={vbj|0≤j≤n}为块结点集合,每个块结点对应一个块;e⊂vp×vb 是边集合,表示记录对与块的隶属关系.可以结合上方向来解读边的含义,给定一条边,从块结点到记录对结点,表示“包含”关系;而从记录对结点到块结点,则表示“出现在”关系.本文为了便于表达,将用p 同时表示记录对结点集合和记录对集合,用p 同时表示记录对结点和记录对,用b 同时表示块结点集合和块集合,用b 同时表示块结点和块.
例2:续例1.将例1 中b′表示为二分图g,如图3 所示.初始时,用rd-es 来估计记录对相似性(es),所有块冗余性(rd)初始化为0,得到表1 中第1 行的初始值.接下来,相似性通过二分图传播.
(1)p→b 传播.以图3(a)为例,记录对结点p12和p13分别传递各自当前的相似性(都是1/3)给邻接的块结点bp1,p23将当前的相似性4/3 分别传递给邻接的块结点bp1和bp2;bp1获得3 个相似性(分别为1/3,1/3,4/3),取均值为2/3 作为更新的冗余性,同理,bp2更新的冗余性为4/3,对g 所有的连通分量进行相同的操作后,得到表1 中第2 行的结果;
(2)b→p 传播.以图3(a)为例,块结点bp1将当前的冗余性2/3 传给邻接的记录对结点p12,p13和p23,bp2将当前的冗余性4/3 传给邻接的结点p23;记录对结点p12和p13分别获得一个冗余性2/3,分别作为各自最新的相似性,同理,p23获得两个冗余性2/3 和4/3,求和得到2 作为p23最新的相似性(此处为简单的计算方式,后续将给出严格的计算方式),对g 所有的连通分量进行相同的操作后,得到表1 中第3 行的结果.
经过一次p→b→p 传播后,es(p12)=2/3,es(p45)=1/3,那么es(p12)>es(p45),符合例1 中提出的预期.可见,相似性传播有助于准确地估计记录对的相似性,弥补基本的相似性估计方法的不足.
fig.3 an example of pair-block barpitite graph
图3“记录对-块”二分图示例
table 1 example of similairity propagation on bipartite graphs
表1 二分图上相似性传播示例
3.2 基于对-块图的相似性传播
接下来,严格地定义对-块图上相似性传播.首先定义两个单步传播:从记录对结点到块结点(p→b)的传播和从块结点到记录对结点(b→p)的传播.然后,在单步传播的基础上定义迭代的相似性传播.
定义5(p→b 传播).给定一个对-块图g=(p,b,e),pij∈p,bk∈b,pij 与bk 是邻接结点,pij 将当前的相似性传递给每一个邻接的块结点,bk 从每个邻接记录对结点接受相似性,并求平均值作为最新的冗余性,如公式(4)所示:
其中,n(bk)表示bk 的相邻结点的集合.
一次p→b 传播后,所有块结点的冗余性将更新,而记录对结点的相似性不变.
定义6(b→p 传播).给定一个对-块图g=(p,b,e),pij∈p,bk∈b,pij 与bk 是邻接结点,bk 将当前的冗余性传递给每一个邻接的记录对结点,pij 从每个邻接块结点接受冗余性,求和后除以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.初始时,各记录对相似性记作es0(p12),es0(p13)和es0(p23).
(1)p→b 传播.根据定义5,计算得到更新的块冗余性:
(2)b→p 传播.根据定义6,利用公式(6)的计算结果,计算得到更新的记录对相似性:
可以发现,等式组(7)是记录相似性的递推关系,它隐藏了块结点,将p→b→p 传播转化为p→p 传播.
3.3 不动点计算
p↔b 传播的收敛结果计算可以作为一个不动点计算(fixpoint computation)的问题.本文主要关注记录对相似性,因此直接使用记录对相似性的递推关系.将等式组(7)改写成向量与矩阵的运算形式,如公式(8):
其中,向量为行向量.公式(8)中的3×3 矩阵是一个马尔可夫链的转移矩阵,记作q0={qij|0≤i,j<3},qij 表示从状态i转移到状态j 的概率,q0不要求为对称阵.特别地,k 的存在确保0≤qij≤1,并进一步保证p↔b 传播的收敛性(例3 中k≥2);如果去掉k,则q0不再是转移矩阵,p↔b 传播不一定收敛.计算p↔b 传播的关键是转移矩阵,接下来讨论如何计算转移矩阵.
定义8(邻接矩阵).给定一个对-块图g=(p,b,e),p={pi|0≤i
定义9(转移矩阵).给定一个对-块图g 和对→块邻接矩阵amn,那么对→块转移矩阵qmn 为
同理,可以根据块→对邻接矩阵anm 计算得到块→对转移矩阵qnm.
用矩阵来表示p→b→p 传播,当前记录对的相似性向量为esx,块的冗余性向量为rdx.那么:
(1)p→b 传播.块冗余性更新:
(2)b→p 传播.记录对相似性更新:
根据公式(12)易知,p→b→p 传播的整体转移矩阵为qmm:
对于记录对相似性,p→p 传播与p→b→p 传播等价,进而p↔p 传播与p↔b 传播等价.
定义10(p↔p 传播).给定一个对-块图g 和p→p 转移矩阵qmm,与p↔b 传播等价的p↔p 传播中,一次p→p 传播可表示为
不动点计算的流程.
(1)利用bes 初始化记录对相似性向量为es0;
(2)利用公式(14)计算下一轮记录对相似性向量esx+1;
(3)不断迭代步骤(2),直到残差向量δ(esx+1,esx)的每一维都小于ε.ε为残差阈值,一般取一个较小常数,例如0.005;
(4)当迭代结束后,将最终的记录对相似性向量记作essp,作为基于相似性传播的相似性估计的结果输出.
代价分析:p↔p 传播的一次迭代代价为o(m2),迭代次数为x,那么总代价为o(xm2).对-块图g 实际是由多个连通分量组成,分量集合记作c={ci},|ci|>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 和acpb,可以提高最终召回率,但这样要维护多个排序列表并依次滑动,会大大增加实时的计算代价和总的计算代价,明显降低实时召回率;
(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 作为参考.
fig.7 similarity estimation test on dblp dataset
图7 在dblp 数据集上的相似性估计测试
fig.8 similarity estimation test on fb dataset
图8 在fb 数据集上的相似性估计测试
整体而言,就实时召回率而言,在两个数据集上均有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 和tcer2,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 系数的相似性估计(对应tcer1 和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 和tcer0-7.图9 和图10 分别展示了在dblp 数据集上和fb 数据集上这4 种方法的对比情况,baseline 作为参考.
fig.9 sp-es’s iteration test on dblp dataset
图9 在dblp 数据集上sp-es 的迭代测试
fig.10 sp-es’s iteration test on fb dataset
图10 在fb 数据集上sp-es 的迭代测试
整体而言,随着迭代次数的增加,预处理的时间代价接近成倍地增加;然而预处理之后的实时召回率却没有明显的提升,即相似性估计的准确性只是非常微弱地提高.取单点来对比,在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 的最好选择.
fig.11 sp-es’s hitting rate &start-up time tests on dblp dataset
图11 在dblp 数据集上sp-es 的top-n 命中率及启动时间测试
fig.12 sp-es’s hitting rate &start-up time tests on fb dataset
图12 在fb 数据集上sp-es 的top-n 命中率及启动时间测试
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 系数的记录对相似性估计方法.针对两个基本的相似性估计方法,提出了基于相似性图传播的改进.构建记录对和块组成的二分图.在二分图上运行相似性传播,在此过程中记录对的相似性动态变化,直到收敛.提出了基于不动点迭代的收敛结果计算方法,并提出了近似方法来降低计算代价.在一个真实数据集和一个合成数据集上测试提出的方法,证明其有效性,并测试了提出方法的各个方面的特点.在未来的工作中,将研究联合式实体解析在时间约束条件下的解决方案。
物联网智能技术应用协会举办智慧科技小镇的未来建设与发展的讲堂
跌涨如过山车比特币价格，扩容问题该如何顺利化解
LKT4101防抄板加密ic：开创嵌入式加密芯片市场新天地
哪种运动耳机好用、值得推荐的运动耳机
华为Mate40 Pro斩获六项大奖
时间约束的实体解析中记录对排序研究
智慧物流在应对新冠肺炎疫情当中优势凸显
锐龙7PRO 3700泄露 性价比将比锐龙7 3700X更胜一筹
什么是位置与姿态控制系统
一种可以根据应用场景灵活选择工作模式的片上RVG电路
三相断路器型号规格及其参数 浅谈三相断路器电流计算
苹果Micro-LED样品开始测试！最晚2019年Apple Watch将用上Micro-LED！
每个工程师都应该了解的有关热管理的事实
R类音频功率放大器CS8389E/CS8390E
欧洲客户来我厂考察和洽谈锡膏项目合作事宜
EDA工具应用在FPGA设计和IC设计中的应用介绍
SaaS行业风口正酣，声网容联云未来发力剑指何方？
NLP领域的难处
最大限度降低寄生电容对放大器稳定性影响的三种方案
30多名商业领袖在《纽约时报》发表，请将地球利益放在利润之上