欢迎访问一起赢论文辅导网
SCI期刊论文
当前位置:首页 > SCI期刊论文
基于多路分块的Pay-as-you-go实体识别方法
来源:一起赢论文网     日期:2019-12-01     浏览数:1615     【 字体:

 s in blocking redundancy,which is helpful for computing match probabilities of candidateobject pairs.Intuitively,the more blocks a pair shares,the more matchable the pair is.Yet differentblocks usually offer different contributions to match probability of a pair,so it is necessary toevaluate the redundancy of each block.Meanwhile,blocking redundancy has to be eliminatedefficiently before pair comparisons.We propose a blocking based Pay-as-you-go ER(BPER)approach.BPER utilizes multi-pass blocking instead of perfect blocking/sorting keys basedtechniques.Redundancy of each block is evaluated dynamically,and the evaluation result is calledblock credit.Block credits are used for real-time pair match probability computing.Also,anefficient graph based method is proposed to eliminate blocking redundancy.BPER consists of twostages:the initialization stage and the iterative stage.In the initialization stage,generatecandidate data object pairs,and sort them according to match probabilities in a candidate queue.In the iterative stage,each time choose the front candidate pair(the most matchable pair)of thecandidate queue for processing;dynamically update candidate pairs’match probabilities accordingto the real-time ER result,and then update the candidate queue.Candidate pairs resolution andblock credits computation proceed interactively,and promote each other.As a result,the mostmatchable pairs are selected and resolved in real time.In such a way,the proposed ER approachreduces useless data object comparisons,and optimizes the real-time ER result.Finally,weexperimentally evaluate the proposed Pay-as-you-go ER approach over real datasets and syntheticdatasets.The experiment results show that BPER improves existing works greatly.We alsoevaluate the contribution of each component to progressiveness in BPER.Keywords entity resolution;Pay-as-you-go;multi-pass blocking;candidate pair selection;dataintegration;data cleaning1 引 言实体识别(Entity Resolution,ER)是数据集成和数据清洗的一个关键方面,是数据挖掘和数据分析的一个必要的预处理步骤[1-9].传统的实体识别方法将整个脏数据集作为输入,处理完成后输出识别结果[1,8].然而,当前出现了很多新的应用,要求(近似的)实时数据分析,传统的实体识别技术无法满足这一需求[10-12].在给定较短时间时(远小于识别完整个数据集所需的时间),Pay-as-you-go实体识别可以尽最大可能地优化识别结果,从而解决前面的需求.例如,金融新闻的信息流应用通常很强调实时性,以便于客户及时地进行相应的金融业务处理.股票市场的金融数据变化特别快,每隔一段时间就会生成新的数据;金融数据会涉及大量公司和个人的名字,而短时间内,不可 能将 这些数据全部识别出来.信息流应用在发布金融新闻之前,需要在较短的时间内识别出大量的公司和个人的名字[10].为了解决这类应用需求,新的实体识别方法应该在给定的短时间内处理得到尽量多的重复(匹配)数据对象对(简称为“重复对”或“匹配对”).定义1. Pay-as-you-go实体识别.相对于传统的实体识别,Pay-as-you-go实体识别需要额外满足以下两个条件[12]:(1)早期的识别结果更好.给定任意一个较短的运行时间t,Pay-as-you-go实体识别方法能够比传统的实体识别方法识别出更多的重复对.时间段t远小于完全的实体识别运行时间.(2)相同的最终识别结果.如果传统的实体识别方法和 Pay-as-you-go实体识别方法都运行到自然终止,两者应该产生相同的识别结果.本文将研究 Pay-as-you-go实体识别,这类方法以 Pay-as-you-go的形式逐渐优化实体识别结果,也称为渐近式实体识别.在给定的短时间内,当一个实体识别方法识别出的数据对象越多,那么它的渐近性越高;反之,它的渐近性越低.传统的实体识别方法可分为两类:基于聚类的方法(即无监督的,对应图1中传统方法1)和基于分类的方法(即监督的,对应图1中传统方法2).如8期 孙琛琛等:基于多路分块的 Pay-as-you-go实体识别方法5071基于聚类的方法首先要计算所有候选数据对象对(简称为“候选对”)的相似度,然后再通过聚类算法得到识别结果,它需要在整个执行时间的后期才输出识别结果;在不考虑训练过程的前提下,基于分类的方法将逐个地处理候选对,在执行过程中逐步地输出识别结果,但它并没考虑候选对的优先级.与前两类 方法相反,Pay-as-you-go方法花费较短时间进行预处理,估计候选对的匹配可能性,将候选对按优先级进行处理,从而在给定较短执行时间内识别出尽量多的重复对.因此,如果只给定有限的执行时间,Pay-as-you-go实体识别方法必将比传统的实体识别方法得到更多的重复对.需要指出的是,如果运行到 自然终止,Pay-as-you-go实体识别方法可能比传统方法花费更长时间,因为预处理也有一定的时间开销.图 1 Pay-as-you-go实体识别与传统方法对比正如已有工作[10,12]所说,Pay-as-you-go实体识别的核心是,根据候选对匹配的可能性,高效地选择最有可能匹配的数据对象对优先进行比较,从而保证高的实体识别渐近性.Whang等人首次提出 Pay-as-you-go实体识别的概念,并基于排序或分块技术提出三个 Pay-as-you-go实体识别“线索(hints)”方法,这些方法的前提是给定了最优的排序或分块的键[10].Papenbrock等人提出了渐近式滑动窗口方法(Progressive Sorted Neighborhood Method,PSNM)和渐近式分块方 法 (Progressive Blocking,PB),这两个方法都是基于排序的数据对象列表,即需要给定最优的排序键[12].Papenbrock等人的方法要优于Whang等人的方法,然而 PSNM 和 PB方法都需要运行全局 的 滑 动 窗 口,从 而 很 有 可 能 会 降 低 渐 近性.比如,利用 PSNM 和 PB 方法来解决例 1 中的Pay-as-you-go实体识别任务.如图 2 所示,将表 1中的数据对象按照姓进行排列,得到一个从左到右的数据对象列表.在该列表中存在两个区域:区域a是一个低冗余的区域,不存在重复数据对象;区域b是一个高冗余的区域,每两个数据对象都彼此重复(〈r1,r4〉,〈r1,r3〉,〈r4,r3〉),一共 有 三 个 重复对.PSNM 和PB方法都要对图2中的数据对象列表进行从左到右的遍历,因此这两个方法都会先处理区域a、然后才处理区域b,推迟了重复对的发现,降低了渐近性.由此可 见,Pay-as-you-go实体识别的一个大挑战是,如何准确定位出数据集中冗余度最高的区域.另外,Whang等人和 Papenbrock等人的方法都假定最优的排序或者分块的键已经得到.然而,找出最优的排序或分块的键,需要有丰富的领域知识以及对每个数据集的非常的熟悉程度.普通的用户无法达到这样的要求,因此难以得到最优的排序或分块的键.此外,一些数据集 的 最优的键 并不存在.如何克服键的选择问题是 Pay-as-you-go实体识别的另一个挑战.图 2 将表1中的记录根据姓进行排序,得到了从左往右的列表;该列表存在一个稀疏区域a(r6,r5,r7)和一个稠密区域b(r1,r4,r3)表 1 样例脏数据集(包含7条个人记录,属性有姓名、年龄、工作和所在城市)ID 姓名 年龄 工作 城市r1John Young  29 Waiter  Postonr2John Joung  29 Waiter  Bostonr3Jon Young - Waiter  Bostonr4John Young  29 Waiter  Bostonr5Bob Brown  27 Waiter  Austinr6Jeff Allen  29 - Bostonr7Will Green  29 Teacher  Boston例1. 如表1所示,有一个包含7条记录的样例数据集.这是一个脏数据集,对应的真实识别结果是{{r1,r2,r3,r4},{r5},{r6},{r7}}.当前要求渐近地识别这个脏数据集,也就是说,给定较短的运行时间,尽量 识 别出最多的重复记 录 对.在随 后的 第 5节,将利用本文提出的 Pay-as-you-go实体识别方法逐步地来解决本例提出的问题.本文 将 研 究 如 何 在 最 优 的 分 块 或 排 序 的 键未知的情况 下,实 现 高 效 的 Pay-as-you-go 实 体 识别.Papenbrock等 人 利 用 一 个 属 性 并 行 (AttributeConcurrency,AC)技术将PSNM 和 PB方法拓展得到 AC-PSNM 和 AC-PB方法,这两个新方法可以用于解 决 本 文 研 究 的 问 题[12].但 是,AC-PSNM 和AC-PB方法要交替地处理 K (不同的排序的键的总数目)个按不同键排序的数据对象列表,并且没有6071 计  算  机  学  报 2019年到冗余度最高的区域,这样会严重影响渐近性.Pay-as-you-go实体识别的关键是,找出最可能匹配的候选对.候选对选择的常用技术是分块[13-19].本文设定最优的分块的键是未知的,因此将利用多路分块来解决 Pay-as-you-go实体识别的问题.一方面,多路分块会产生大量的分块冗余;另一方面,可以利用分块冗余来估计候选对的匹配可能性.直观来说,一个候选对同时出现在越多的块中,该数据对象对的匹配可能性越大.如果一个数据对象对出现在一个块中,那么这个块是这个数据对象对的共现块;同一数据对象对,可能会出在多个块中,从而对应多个共现块.通过不同的共现块来估计同一数据对象对,得到的匹配可能性很可能是不同的.为了综合地估计一个数据对象对的匹配可能性,需要先评估该数据对象对的每个共现块.同时,为了保证渐近性,在比较候选对之前,必须快速地去除掉分块冗余.本文提出一个基于分块的Pay-as-you-go实体识别方法BPER(Blocking based Pay-as-you-go EntityResolution).BPER可以精确地定位脏数据集中最冗余的区域,给予这样的区域内的候选对高优先级,从而解决了本节第3段提出的第一个挑战,保证了高渐近性.随后第5节将通过例2到例4来示例说明,BPER 方法如何在给定的较短时间内识别出尽量多的重复对.BPER 利用多路分块来解决最优的分块键的选择问题.动态地评估每个块的冗余度,然后利用块的冗余度来实时地计算候选对的匹配可能性.候选对的比较和块冗余度估计交互地进行和彼此影响对方,从而在实体识别过程中实时地选择最可能匹配的数据对象对.与此同时,为了保证渐近性,提出一个基于图的方法来快速地去除由于多路分块导致的分块冗余.通过在两个真实的数据集和一组合成的数据集上的对比实验,证明 BPER 方法要优于已有方法.本文的主要贡献总结如下:(1)提出两个块冗余度估计方法:基于静态的块信用度的块冗余度估计方法和基于动态的块信用度的块冗余度估计方法.块冗余度估计对于 Pay-as-you-go实体识别中的候选对的选择至关重要.(2)提出一个基 于 多路分 块 的 Pay-as-you-go实体识别方法 BPER.该方法基于有交叠(冗余)的分块,随着实体识别的进行,动态地估计候选对的匹配可 能 性.同 时,高 效 地 去 除 分 块 冗 余,保 证 高 渐近性.(3)在两个真实的数据集和一组合成的数据集上评估了 本 文 提 出 的 BPER 方 法.评 估 结 果 说 明BPER方法要明显优于已有的 Pay-as-you-go实体识别方法.另外,分 别测试了 BPER 方法的不同组成部分对渐近性的影响.本文第2节介绍相关工作;第3节介绍准备工作,包括多路分块和方法概述;第4节介绍块冗余度估计,包括静态的块信用度、动态的块信用度和候选对的信 用 度;第 5 节详细阐 述基于分 块 的 Pay-as-you-go实体识别方法BPER,包括Pay-as-you-go实体识别模型、初始化阶段和迭代阶段;第6节进行实验评价与分析,包括实验设置、综合测试和关键组成部分测试;最后,对全文进行总结.2 相关工作大部分已有的实体识别研究,要么聚焦于提高最终的识别结果的精确性,要么致力于降低实体识别运行的总时间.近些年,随着数据增长得更快和数据演化得更频繁,Pay-as-you-go数据管理方法逐渐流行,并得到研究者的重视[20-23].文献[23]提出了针对海量 Web数据的 Pay-as-you-go数据集成方法,文献[22]提出了面向数据空间系统的 Pay-as-you-go数据清洗方法.在实体识别研究领域,同样存在一些Pay-as-you-go的实体识别方法[10-12],这些工作与本文的研究最相关.Whang等人最早研究了 Pay-as-you-go实体识别,提出了 三 个 启 发 式 的 Pay-as-you-go 实 体 识 别“线索”方法,这些方法需要与已有的实体识别方法结合使用[10].一个“线索”可以帮助传统的实体识别方法优先选择匹配可能性高的数据对象对来进行识别.第一个“线索”方法,根据候选对的匹配的可能性生成一个排好序的数据对象对列表.第二个“线索”方法,对数据集进行不同层级的划分,每一层的划分代表实体识别结果的一种可能.第三个“线索”方法,根据某个数据对象与其他数据对象重复的可能性对数据对象进行排序,得到一个排序的数据对象列表.所有的“线索”方法都生成固定的序列或划分,不能动态地调整,限制了其渐近性.另外,这三个“线索”方法基于最优的排序或者分块的键,因此无法解决本文研究 的 问 题.Papenbrock 等 人 提 出 一 组 Pay-as-you-go实体识别方法[12].渐近式滑动窗口方法(Progressive Sorted Neighborhood Method,PSNM)8期 孙琛琛等:基于多路分块的 Pay-as-you-go实体识别方法7071期:2018-07-04;在线出版日期:2019-03-14.本课题得到国家“九七三”重点基础研究计划基金项目(2012CB316201)、国家自然科学基金项目(U1435216,61672142,61472070,61602103)、国家重点研发计划项目(2018YFB1003404)资助.孙琛琛,博士研究生,主要研究方向为实体识别、数据质量.E-mail:dustinchenchen_sun@163.com.申德荣,博士,教授,博士生导师,中国计算机学会(CCF)高级会员,主要研究领域为分布式数据管理、数据集成.寇 月,博士,副教授,中国计算机学会(CCF)会员,主要研究方向为实体搜索、数据挖掘.聂铁铮,博士,副教授,中国计算机学会(CCF)会员,主要研究方向为数据质量、数据集成.于 戈,博士,教授,博士生导师,中国计算机学会(CCF)会士,主要研究领域为数据库、大数据管理.基于多路分块的Pay-as-you-go实体识别方法孙琛琛 申德荣 寇 月 聂铁铮 于 戈(东北大学计算机科学与工程学院 沈阳 110169)摘 要 实体识别是数据集成和数据清洗的一个重要方面.针对 Pay-as-you-go数据管理需求,本文提出一个基于多路分块的 Pay-as-you-go实体识别方法.该方法不要求提供最优的分块或排序的键,并且可以直接找出脏数据集中冗余度最大的区域.分为两个阶段,初始化阶段和迭代阶段.在初始化阶段,初步地生成候选数据对象对,并按匹配可能性排序后加入到候选队列.在迭代阶段,每次选择候选队列队首的候选对(即最可能匹配的)来处理,并且根据实时的实体识别结果,动态地更新候选对的匹配可能性,调整候选队列.这样减少了无用的数据对象比较,使得实时的识别结果最优化.通过在真实数据集和合成数据集上的实验对比,说明本文提出的基于多路分块的 Pay-as-you-go实体识别方法显著地优于已有工作中提出的方法.关键词 实体识别;Pay-as-you-go;多路分块;候选对选择;数据集成;数据清洗中图法分类号 TP391   DOI号 10.11897/SP.J.1016.2019.01704A Multi-Pass Blocking Based Pay-as-you-go Entity Resolution ApproachSUN Chen-Chen SHEN De-Rong KOU Yue NIE Tie-Zheng YU Ge(School of Computer Science and Engineering,Northeastern University,Shenyang 110169)Abstract  Entity resolution(ER)is a key aspect of data integration and data cleaning,and is anecessary pre-processing step of data analytic and data mining.Traditional ER approaches take awhole dirty dataset as input,and output the complete ER result after a batch based process.However,nowadays many new applications emerge,demanding(nearly)real-time data analytic,but traditional batch based ER approaches cannot satisfy such requirements.For instance,a financenews feed tries to resolve as many companies and persons as possible within limited time,fromfinancial data generated frequently.In order to fulfill such requirements,Pay-as-you-go ER triesto maximize number of resolved duplicate data objects given limited time(far shorter than overallrunning time).Pay-as-you-go ER is also called progressive ER,since it resolves data objectsprogressively.The more data objects an ER approach resolve within limited time,the higher itsprogressiveness is.The core challenge of Pay-as-you-go ER is to effectively select the mostmatchable object pairs for comparison with high priorities.Existing Pay-as-you-go ER solutionsrely upon perfect blocking keys or sorting keys for pair selection.However,the best blocking/sorting keys cannot be got without deep domain knowledge and fully understanding of eachdataset.It is impossible for common users.Worse still,perfect blocking/sorting keys do notalways exist.We try to work out an effective Pay-as-you-go ER solution without perfect blocking/sorting keys.We resolve data objects progressively with multi-pass blocking.Multi-pass blocking的滑动窗口方法(Sorted NeighborhoodMethod,SNM),PSNM 方法迭代地将滑动窗口从小到大变化,同时通过预测函数来动态地改变识别顺序.渐 近式分块 方 法 (Progressive Blocking,PB)基于排序的数据对象列表与等距分块.PB 首先 生成一个分块集合,然后逐渐地扩展这个分块集合.PSNM 和PB方法都是基于排序的数据对象列表.然而,在本文的问题设定中,最优的排序键是未知的.Papenbrock等人提出两个基于多路技术的扩展方法:属性同步 (Attribute Concurrency)的 PSNM(AC-PSNM)方法和属性同步的 PB(AC-PB)方法.AC-PSNM 和 AC-PB 方法交替地处理多个排序列表,并根据已有的识别结果动态地选择列表进行处理.这两个方法并不需要给出最优的排序键,因此可以解决本文提出的问题.然而,AC-PSNM 和 AC-PB方法需要交替地处理同一数据集的不同排序列表,存在严重冗余,限制了其渐近性.Papenbrock 等人的方法是基于硬盘的,可以处理规模超出内存大小的数据集.Altowim 等人提出一个渐近的联合式实体识别方法[11].该方法定义了“收益-开销”模型,然后根据这样的模型生成联合式实体识别执行计划.Altowim 等人的方法针对多类型关联数据,如引文数据和电影数据,但不能用于处理单类型的数据集.Pay-as-you-go实体识别的核心是选择最可能匹配的数据对象对,以便在给定的较短时间内得到尽量多的重复对.已有的数据对象对选择方法通常有基于分块的方法和基于滑动窗口的方法[13-19],这些方法的目标都是降低总的实体识别时间.由此可见,不同的目标将 Pay-as-you-go实体识别与传统的分块或滑动窗口方法区分开来.Papadakis等人针对高度异构的数据空间提出一系列的分块技术,旨在不影响精确性的前提下减少实体识别总时间[16-17].Papadakis等人的一些方法在一定程度上是 Pay-as-you-go的,如分块调度、块删除、比较调度[16]和基于元的分块[17].3 准备工作3.1 多路分块分块是实体识别中一种常见的数据对象对选择技术.本文将利用有交叠的分块来选择最可能匹配的数据对象对.直观来讲,两个数据对象共同出现在越多的块中,这两个数据对象匹配的可能性越大.定义2. 分块.给定一个脏数据集 R={r}和一个分块的键k,一个分块方法根据一个数据对象r的键值r.k将r 分到一个块b=d(r.k).d(*)是一个分配函数.分块 结果集 合 B 是不 交 叠 的,bi∩bj=,bi,bj∈B.特别地,如果一个数据对象在给定的键对应的属性值是缺失的话,该数据对象将不被分配到任何一个块中.块中的一对数据对象称 为候选数据 对象对或候选对,记作〈ri,rj〉,ri,rj∈b.〈ri,rj〉和〈rj,ri〉是相同的,称为对称性.如果一个候选对已经 被识别过了,称为 已 识 别 的 候 选 对;否 则,就 是 未 识 别 的候选对.一个块是一个数据对 象的集 合,块b的势(Cardinality)是b中不同数据对象对的总数目,记作b =b( )2=(b ×(b -1))/2,其中 b 表示块b的对象个数.一个块b中所有候选对组成的集合,记作 Γ(b),即 Γ(b) = b .在 实 体 识 别 过 程中,一个块b中所有已识别的数据对象对组成已识别的集合,记作Ξ(b)Γ(b);所有未识别的数据对象对组成未识别的集合,记作(Γ(b)-Ξ(b))Γ(b).Ξ(b)中所有重复对组成的集合,记作Ξ+(b);Ξ(b)中所有不重复对组成的集合,记作 Ξ-(b);Ξ(b)=Ξ+(b)+Ξ-(b).然而,最优的分块的键不易找出,甚至有时候是不存在的.对于一个数据集,一些键能够探测出一些重复数据对象,而另外一些键可能找出别的重复数据对象.特别地,给定的一个分块的键,一些数据对象的对应属性值可能是缺失的.多路分块能够提高实 体 识 别 精 确 性,不 必 进 行 最 优 的 分 块 键 的 选择[14,18].多路分块给予重复数据对象更多机会,以便每个重复对至少出现在一个块中;同时,多路分块使得同一候选对可能同时出现在多个块中,即块之间存在交叠,导致了分块冗余.分块冗余可以用于估计候选对的匹配可能性.如果一个候选对出现在一个块中,称这个块是这个候选对的共现块.如果两个数据对象共同出现在了较多的共现块中,那么这两个数据对象很有可能是匹配的.定义3.  多 路 分 块.给 定 一 个 脏 数 据 集 R={r}和一个分块的键的集合 K={ki|0i K },多路分块的结果集合是 Bm=B1∪B2∪…∪B|K|.Bm是一个有交叠的块集合,每个数据对象最多可能出现在 K 个不同块中.候选对匹配的可能性来源于该候选对所在的共现块(一个或多个),然而不同的共现块给同一候选8071 计  算  机  学  报 2019年配可能性是不同的.第4节将提出块冗余度估计方法,进而计算候选对匹配的可能性.本文中,块的冗余度和块集合的冗余(也称为分块冗余)是不同的概念.块的冗余度是指某一块中重复对相对于该块的势(即候选对总数目)的比例.分块冗余则是指,同一候选对出现在块集合内多个块中,即不同的块有交叠.单路分块生成没有冗余的块集合,而多路分块会生成有冗余的块集合.3.2 方法概述Pay-as-you-go实体识别的核心问题是,在实体识别过程中如何优先选择最有可能匹配的候选对进行识别.整体而言,BPER 方法以多路分块为基础,通过块冗余度来估计候选对的匹配可能性.具体地,BPER方法提出块信用度来估计块的冗余度;基于块信用度,又提出候选对信用度来计算候选对的匹配可能性(第4节).BPER 方法根据候选对的信用度对所有的候选对进行排序;在实体识别过程中,根据实时的匹配结果更新候选对信用度,动态地调整候选对排序,每次都选择排序最靠前的候选对进行识别;因此,BPER 方法实时地选择最可能匹配的候选对来进行识别,保证了高渐近性.图3描绘了 BPER 方法的整体工作流程.虚线绘制的图形表示数据和数据结构,实体绘制的图形表示操作.带箭头的虚线线条表示数据和操作的交互,带箭头的实线线条表示操作的先后顺序.总体而言,BPER 方法由两个阶段组成:初始化阶段和迭代阶段(第5节).图 3 本文提出的 Pay-as-you-go实体识别方法的工作流程  初始化阶段为迭代阶段准备候选对.首先,利用多路分块构建有交叠的块集合,并通过构建分块图来快速去除冗余的数据对象对;接着,初始化候选对的信用度,将候选对的信用度作为分块图中相应的边的权重;最后,将所有候选对根据其信用度进行排序,并依次加入到一个优先队列 Q 中,称 Q 为候选队列.迭代阶段是 BPER 的核心,包括三个迭代的步骤.首先,从候选队列Q 队首取得一个候选对,调用一个实体识别匹配函数来处理该候选对;接着,根据前一步的结果,对一部分候选对的信用度进行重新计算;最后,根据重新计算的候选对的信用度,调整候选队列.将候选对的信用度重新计算和候选队列的调整合起来称为更新期.上述迭代过程一直持续,直到时间预算用完或者候选队列为空.本文聚焦于实体识别的渐近性,关注核心是候选对的识 别 顺 序,而 实 体 识 别 匹 配 函 数 的 准 确 性与识别 顺 序 是 正 交 的,因 此 将 匹 配 函 数 当 作 黑盒[12].m(〈ri,rj〉)表示一个实体识别匹配函数,如果〈ri,rj〉匹配,m(〈ri,rj〉)返回真;否则,m(〈ri,rj〉)返回假.本文假定 m(〈ri,rj〉)的精确性为1,即永远返回正确的识别结果.4 块冗余度估计本节将介绍如何估计一个块的冗余度.不同块8期 孙琛琛等:基于多路分块的 Pay-as-you-go实体识别方法9071常是不同的.用块信用度来估计块的冗余度.块冗余度的估计是候选对的信用度的计算的基础,如图3所示,涉及初始化阶段的候选对的信用度初始化和迭代阶段的候选对的信用度的更新.首先,定义块信用度;然后,提出两种块信用度;最后,介绍如何利用共现块的信用度来计算候选对的信用度,即匹配可能性.定义4. 块信用度.给定一个块b,块b的信用度是,块 内 未 识 别 的 候 选 对 从 该 块 获 得 的 匹 配 可能性,    σ(b)=Pr(m(〈ri,rj〉)=true|〈ri,rj〉∈(Γ(b)-Ξ(b))) (1)4.1 静态的块信用度本小节提出静态的块信用度(Static Block Credit,SBC),只需要在进行实体识别之前进行一次计算.如果一个块中包含的数据对象越多,那么该块内的任意一个候选对匹配的可能性越小.较大的块中的候选对所拥有的信息量很小,不足以保证该候选对的匹配.比如,一个个人信息数据集(美国)中,很可能许多人来自同一个州,而没有那么多人拥有相同的姓.平均来讲,通过键“州”生成的块要比通过键“姓”生成的块要大.后者块内的候选对匹配的可能性要平均大于前者块内的候选对匹配的可能性.基于上述想法,静态的块信用度给予小块更高的优先级.定义5. 静态的块信用度.给定一个块b,该块的静态的信用度与它的势成负相关,σs(b)=1/b (2)4.2 动态的块信用度静态的块信用度的一个缺点是,如果数据集中真实存在一些大的簇(即描述相同实体的数据对象组成的集合),那么给予所有大块较小的信用度并且一成不变是不合理的.为了克服这个缺点,可以在实体识别过程中动态地调整块的信用度,称之为动态的块信用度(Dynamic Block Credit,DBC).直观 来讲,如果一个块中当前的重复数据对象所占的比例比较大,那么该块的真实的冗余度很可能是比较高的,即该块的信用度很可能是比较大的.简言之,给定一个块,根据当前的实体识别结果计算出的当前的冗余度可以估计该块真实的冗余度.基于这样的思想,提出动态的块信用度.定义6. 动态的块信用度.给定一个块b,该块的动态的信用度与该块当前的匹配的集合大小成正相关,与该块的势成负相关,σd(b)= Ξ+(b)( +1)/ b( +1)(3)与静态的块信用度相似,动态的块信用度给予小块较大的初始信用度.初始时,所有候选对都还未被识别,σd(b)=1/(b +1),与静态的块信用度非常相近.随着实体识别的进行,如果一个块内被识别出一些重复对,那么该块的动态的块信用度会变大,这样就克服了静态的块信用度的缺点.动态调整过程中,动态的块信用度同样偏好小块.分析式(3),分母是平方级的,而分子是一次方级的,因此,大块需要获得大量的重复对才能拥有较大的动态的块信用度,而小块只需要相对较少量的重复对就可以拥有相同的动态的块信用度.4.3 候选对的信用度本小节将介绍如何利用共现块的信用度来估计候选对的匹配可能性.有交叠的块集合中的分块冗余可以用来估计候选对的匹配可能性.简单来讲,如果一个候选对共同出现在越多的块中,那么该候选对匹配的可能性越大.然而,不同的共现块给相同的候选对提供的匹配可能性通常是不同的.定义候选对的信用 度 来 估 计 候 选 对 的 相 似 性,即 匹 配 的 可能性.定义7.  候 选 对 的 信 用 度.给 定 一 个 候 选 对〈ri,rj〉,它的信用度估计该候选对的匹配可能性.候选对的信用度是将该候选对的共现块提供的匹配可能性进行聚集,并利用键总数进行归约,σ(〈ri,rj〉)=∑ri,rj∈b,b∈Bσ(b( )) K (4)特别地,如果某些数据对象在一个键对应的属性值缺失,那么这些数据对象在本次分块中将不被分到任何一个块中.因此根据式(4),包含这样的数据对象的候选对无法从按该键分块的结果集合中获得块信用度.5 基于多路分块的 Pay-as-you-go实体识别本节详述基于多路分块的 Pay-as-you-go实体识别方法 BPER.首先,5.1小节提出一个两阶段的Pay-as-you-go实体识别模型;然后,5.2小节介绍初始化阶段;最后,5.3小节介绍迭代阶段.5.1 Pay-as-you-go实体识别模型如图4所示,整个 Pay-as-you-go实体识别过程划分为两个连续的阶段:初始化阶段和迭代阶段.定义8. 初始化阶段.初始化阶段依次包括多路分块、分块图构建、候选对信用度初始化和候选对0171 计  算  机  学  报 2019年 4 Pay-as-you-go实体识别阶段划分排序.本阶段的输入是一个脏数据集,输出是候选队列 Q,该队列是一个优先队列,包含了所有候选对,并按候选对信用度排序.定义9. 迭代阶段.迭代阶段包括三个迭代的步骤:候选对比较、候选对信用度更新和候选队列调整.本阶段的 输入是候选 队列 Q,逐渐地输出识别结果.Pay-as-you-go实体识别的关键是,在实体识别过程中找出最可能匹配的候选对,因此需要将候选对根据其信用度进行非升序排序.在初始化阶段,BPER方法初始地对候选对进行排序;在迭代阶段,根据实时的实体识别结果,动态地调整候选对顺序.其中,候选对的信用度基于块 信用度.由第 4 节可知,动态的块信用度随着实体识别的进行,动态地更新块信用度,这使得它比静态的块信用度可以更精确地估计块冗余度.BPER 方法将默认地采用动态的块信用度来计算候选对的信用度.5.2 初始化阶段作为一个预备步骤,初始化阶段为迭代阶段提供初始排序的候选对.初始化阶段依次包括多路分块、分块图构建、候选对的信用度初始化和候选对排序.5.2.1 分块图因为多路分块会产生大量的分块冗余,所以提出一个高效的、基于分块图的分块冗余去除方法.这里的分块冗余是指分块集合中多个块有交叠,而不是单一个块中的重复数据对象.定义10. 分块图.给定一个多路分块的结果集合Bm,存在一个带权、无向图G=(V,E),称为分块图.V 是结点集合,任意结点v∈V 对应Bm中的一个数据对象.E 是边集合,对于任意边e(vi,vj)∈E(记作eij),数据对象vi,vj至少共同出现在Bm中一个块内.边eij的权重wij是候选对〈vi,vj〉的信用度.本文中r和v 都可以表示数据对象,R 和V 都可以表示数据集.算法1描述了如何构建分块图.外层循环遍历给定的多路分块的结果集合(行5),在内层循环遍历每个块(行6),并作如下处理(行7到15).如果一个候选对〈vi,vj〉对应的边eij不存在,生成新边eij,并将eij加入到边的集合E(行7、14);如果结点集合V 不包含数据对象vi或vj,则将未包含的数据对象加入到结点集合中(行8到13).最后,得到一个分块图G=(V,E).算法1. BlockingGraphConstruction.1.输入:多路分块集合Bm2.输出:分块图G=(V,E)3.V={};//结点集合4.E={};//边集合;5.For b∈Bm6. For〈vi,vj〉∈Γ(b)7.  If eij!∈E8.   If vi!∈V9.    V=V∪{vi};10.   Endif11.   If vj!∈V12.    V=V∪{vj};13.   Endif14.   E=E∪{eij};15.  Endif16. Endfor17.Endfor18.输出分块图G;算法1复杂度分析:将未消除冗余的多路分块集合Bm的候选对集合表示为表示为BPmR,那么算法1的复杂度为O(|BPmR|).通过遍历分块图的边生成候选对集合,每条边对应的两个数据对象对应一个唯一的候选对.根据4.3节中的定义7计算候选对的信用度,然后根据信用度来给分块图赋权重.通过构建分块图,可以快速去除掉多路分块带来的分块冗余.接下来,通过例2来举例说明如何进行多路分块以及如何利用分块图来去除分块冗余.例2. 续例1.对于表1中的脏数据集,分别把姓名、年龄、工作和城市作为键进行多路分块,得到如下结果集合,  Bm=Bsurname∪Bage∪Bjob∪Bcity,Bsurname={bs1={r1,r3,r4},bs2={r2},bs3={r5},bs4={r6},bs5={r7}}Bage={ba1={r1,r2,r4,r6,r7},ba2={r5}},Bjob={bj1={r1,r2,r3,r4,r5},bj2={r7}},Bcity={bc1={r2,r3,r4,r6,r7},bc2={r1},bc3={r5}}.上述块集合Bm中共有33个候选对,存在冗余.8期 孙琛琛等:基于多路分块的 Pay-as-you-go实体识别方法1171第8、9行之间调用算法4,执行更新操作.重复上述过程(行4~9),直到时间预算用完或候选队列 Q 为空.在此过程中,实体识别结果被逐渐地输出.例4将说明 BPER 方法如何迭代地、动态地选择最可能匹配的候选对来进行识别.算法3. Iteration.1.输入:分块集合 Bm,候选队列 Q,实体识别时间预算 BGT2.输出:Pay-as-you-go实体识别结果3.Repeat4. 从Q 队首取一个候选对〈vi,vj〉;5. If m(〈vi,vj〉)==true//m(*,*)为实体识别匹配函数6.  Update(Bm,Q,{〈vi,vj〉});//调用算法47.  Look-around(〈vi,vj〉);//调用算法68.  输出本轮识别结果;9. Endif10.Until(执行时间>BGT)or(候选队列Q 为空)算法3复杂度分析:此处分析一轮迭代的复杂度.一次实体识别匹配函数调用的开销记作O(Cm);Look-around函数的开销为 O(La),后文5.3.3节将给出具体分析;更新操作的开销为 O(Cupdate),将在算法4的介绍中给出具体分析;那么一次迭代的复杂度为O(Cm+La+Cupdate).算法4描述了更新操作.根据最新识别的重复对的集合S,找出最新识别出的重复对所在的块,称为受影响的块baf,受影响的块的集合记作 Baf={baf}(行3~7).由于这些受影响的块中被识别为重复数据对象的比例提高了,根据S 利用 DBC定义来更新这些受影响的块的信用度(行8~10).这些受影响的块所包含的未识别的候选对称为受影响的候选对,利用新的块信用度来更新这些受影响的候选对的信用度,Baf中未识别的候选对的集合记作 BPafu(行11~15).根据新的候选对的信用度来调整候选队列Q(行16).算法4. Update.1.输入:分块集合 Bm,候选队列 Q,最新识别的重复对的集合S2.输出:更新的分块集合Bm,更新的候选队列Q3.Baf={};4.For〈vi,vj〉∈S5. Bij=findAffectedBlocks(〈vi,vj〉);6. Baf=Baf∪Bij;7.Endfor8.For baf∈Baf9. σd(baf);//更新块baf的信用度10.Endfor11.For baf∈Baf12. For〈vi,vj〉∈(Γ(baf)-Ξ(baf))13.  wij=σ(〈vi,vj〉);//更新候选对〈vi,vj〉的信用度14. Endfor15.Endfor16.根据上述更新结果调整候选队列Q;算法4复杂度分析:查找受影响块的集合 Baf的开销为O(S ×K×log|Bm|);块信用度更新的开销为O(Baf);每个受影响的候选对对应的更新块的数目平均值为 KafK,那么未识别的候选对的信用度更新的开销为O(BPafu×Kaf×log Bm );当前候选队列的规模为 Enow,候选队列调整的开销为O(BPafu×logEnow);那 么 算 法 4 的 复 杂 度 为O(S ×K×log Bm + Baf + BPafu ×(Kaf×log Bm +logEnow)).例4. 续例3.利用算法3处理从例3得到的候选队列.为了更直观地说明动态的块信用度对渐近性的作用,本例 将 略去 算 法 3 中的 Look-around函数(行7).逐轮观察 BPER 的迭代阶段.表2呈现了算法3处理表1中脏数据集的前6轮迭代.根据定义7中式(4)和表2,第2~6轮迭代中,候选对按信用度非升序排列如下(每一轮队首的候选对被处理,将不出现在下一轮):第2轮,σd(〈r3,r4〉)=0.193,σd(〈r1,r3〉)=0.170,σd(〈r2,r4〉)=0.114,σd(〈r1,r2〉)=0.091,σd(〈r2,r3〉)=0.068,σd(〈r6,r7〉)=0.068,σd(〈r2,r7〉)=0.068,…第3轮,σd(〈r1,r3〉)=0.256,σd(〈r2,r4〉)=0.159,σd(〈r1,r2〉)=0.114,σd(〈r2,r3〉)=0.114,σd(〈r6,r7〉)=0.091,σd(〈r2,r7〉)=0.091,σd(〈r4,r7〉)=0.091,…第4轮,σd(〈r2,r4〉)=0.182,σd(〈r1,r2〉)=0.136,σd(〈r2,r3〉)=0.136,σd(〈r6,r7〉)=0.091,σd(〈r2,r7〉)=0.091,σd(〈r4,r7〉)=0.091,…第5轮,σd(〈r1,r2〉)=0.182,σd(〈r2,r3〉)=0.182,σd(〈r6,r7〉)=0.136,σd(〈r2,r7〉)=0.136,σd(〈r4,r7〉)=0.136,…第6轮,σd(〈r2,r3〉)=0.227,σd(〈r6,r7〉)=0.159,σd(〈r2,r7〉)=0.159,σd(〈r4,r7〉)=0.159,…根据真实识别结果{{r1,r2,r3,r4},{r5},{r6},{r7}},前6轮中每轮都识别出一个重复对.因此,假如实体识别预算设定为6次数据对象对比较的话,本文提出的 BPER 方法可以在预算 范 围内识别出8期 孙琛琛等:基于多路分块的 Pay-as-you-go实体识别方法3171对〈r1,r4〉同时出现在块bs1,ba1和bj1中.利用算法1 来构建分块图,从而 去除 Bm的分块冗余.如图5所示,得到 Bm对应的分块图GB,图GB中的每条边对应一个唯一的候选对.由图5可知,去除掉分块冗余后,候选对数目从33降至19.图 5 例2中的块集合对应的分块图GB5.2.2 初始化阶段算法2描述了初始化阶段.首先,利用一组键 K对给定的脏数据集V 进行多路分块,生成一个带冗余的块集合Bm(行3).然后,调用算法1构建Bm对应的分块图,以此来去除 Bm的分块冗余(行 4);计算Bm中块的信用度,调用定义6中式(3)来计算每个块b的 DBC,此时重复对的集合规模|Ξ+(b)|为0(行5~7).接着,调用定义7中式(4),利用块信用度初始化候选对〈vi,vj〉的信用度,进而给分块图中对应边eij赋 权 重 wij(行 8~10).最后,将所有候选对加入到候选队列 Q,并按照信用度非升序排列(行11).候选队列Q 是一个优先队列,通过堆(Heap)来实现,它的插入开销为 O(logn),初始构建(包含排序)的开销为O(nlogn).例3将说明,如何初始化块信用度 和 候 选 对 的 信 用 度,以 及 如 何 对 候 选 对排序.算法2. Initialization.1.输入:脏数据集V,一组分块键 K2.输出:候选队列Q3.利用V 和K 构建一个带冗余的块集合Bm;4.G=BlockingGraphConstruction(Bm);//调用算法1构建分块图G=(V,E)5.For b∈Bm6. σd(b);//初始化块b的信用度7.Endfor8.For eij∈E //eij对应候选对〈vi,vj〉9. wij=σ(〈vi,vj〉);10.Endfor11.根据初始的候选对的信用度,将候选对加入到一个候选队列 Q;12.输出候选队列Q;算法2 复杂度分析:构建块集合 Bm的开销为O(K× V );用 Bm表示Bm中块的数目,初始化块信用度的 开 销 为 O(Bm);将消除冗余后的多路分块集合Bm的候选对集合表示为BPmC,实际就是分块图的边的集合 E,那么初始化候选对的信用度的开销为 O(E ×K×log Bm);将所有候选对在候选 队 列 Q 中 按 初 始 信 用 度 排 序 的 开 销 为O(E ×log E );那么算法2的复杂度为O(K×V + Bm + BPmR + E × (K×log Bm +log E )).例3. 续例2.利用算法2处理表1中的脏数据集,得到初始的块信用度和候选对的信用度,如下,块信用度:σd(bs1)=1/4,σd(ba1)=1/11,σd(bj1)=1/11,σd(bc1)=1/11.候选对的信用度(非升序):σd(〈r1,r4〉)=0.108,σd(〈r3,r4〉)=0.108,σd(〈r1,r3〉)=0.085,σd(〈r2,r4〉)=0.068,σd(〈r6,r7〉)=0.045,σd(〈r2,r3〉)=0.045,σd(〈r1,r2〉)=0.045,…根据上 述 候 选 对 的 信 用 度,后 续 应 该 先 处 理〈r1,r4〉或〈r3,r4〉.根据真实识别结果{{r1,r2,r3,r4},{r5},{r6},{r7}}可知,这两个候选对都是重复的.由此可见,初始的候选对的排序是有效的.5.3 迭代阶段迭代阶段是 BPER 方法的核心部分.迭代阶段主要由三个迭代步骤组成:候选对比较、部分候选对的信用度更新和候选队列调整;在此过程中,将逐渐地输出最新被识别出的重复对.将部分候选对的信用度更新和候选队列调整合称为更新期.针对更新期,提出两个更新策略:朴素的更新策略和延迟的更新策略.另外,还将利用数据对象匹配的传递性来提高渐近性.5.3.1 迭代阶段算法3描述了迭代阶段.算法3在更新期采用了朴素的更新策略(行5、6),也可以采用5.3.2小节中提出的延迟的更新策略.从候选队列Q 队首取一个候选对〈vi,vj〉,用实体识别匹配函数对〈vi,vj〉进行比较(行4、5).如果〈vi,vj〉被判定为重复的,那么执行如下操作:首先,执行更新操作(行6),根据当前识别结果,更新块信用度、候选对信用度以及调整候选队列顺序,详情见算法4;其次,如果已经存在重复对象对〈vi,vk〉(或〈vk,vj〉),那么 Look-around函数将直接处理〈vk,vj〉(或〈vi,vk〉),从而提高渐近性(行7),此函数利用了数据对象匹配的传递性,将在5.3.3小节中介绍.特别地,算法3在调用 Look-around函数(算法6)时,需要对算法6进行微小修改,即在算法62171 计  算  机  学  报 2019年

[返回]
上一篇:基于双记忆注意力的方面级别情感分类模型
下一篇:多自由度3D打印技术研究进展综述