Pattern-Based Entity Resolution

《Pattern-Based Entity Resolution》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Pattern-BasedEntityResolutionPattern-BasedEntityResolutionHuipingLiuHpliu1990@gmail.comAbstractEntityResolution（ER）旨在从大量的数据集中找出那些对应于现实世界中的同一个实体的数据记录。目前有两种基本思路来解决这个问题，一种是exhaustiveentityresolution，通过对所有数据集中的记录进行两两比较来确定哪些的相似度比较高的记录属于同一个实体。这种方法的复杂度比较高2（O(n)），在处理数据集较大

2、的情况下时间代价很大，不适宜使用。另一种思路是blocking-based的ER，其首先将数据集通过特定的哈希函数大致将比较相似的记录分到同一个block中，然后对每一个block中的记录进行类似exhaustiveER的两两比较。这种思路大大提升了运行时间，但是牺牲了结果准确度，因为同一个实体记录可能没有被分到同一个block中。本文创造性的提出了一种pattern-basedentityresolution，通过将同一个实体对应的记录生成pattern，然后进行pattern之间的两两比较来判断他们是否属于同一个实体。

3、这种exhaustiveER的方法避免了传统方法中的数据记录之间的两两比较，显著的提升了exhaustiveER的运行时间，同时对结果的准确度又不会造成任何影响。1IntroductionEntityResolution一般有两种基本操作：Match和Merge。Match：匹配操作。利用相似度算法（编辑距离、Jaccard等）和一个给定的阀值（Threshold）来判断两个记录（record）是否相似，即对应于同一个Entity。这里的记录（record）可以指单条记录，也可以指多条记录所形成的一个聚集记录（cluste

4、r)。下面我们对match给出一个形式化的定义：1Pattern-BasedEntityResolution定义1：给定相似度算法S和阀值�∈[�,�]，对于记录r1和r2，若S(r1,r2)>=�,则r1和r2匹配，记为r1≈r2。对于单条记录若他们之间的相似度超过阀值，即认为他们匹配（match），对于聚集若他们中至少有一对记录匹配（match）才认为他们可能匹配。显然聚集之间的匹配比单条记录之间的匹配要复杂的多，通常认为聚集之间只要找到一对记录匹配即认为这两个聚集匹配，这种策略需要对两聚集进行join操作，复杂度为O

5、(mn)（其中m、n分别指每一个聚集里的记录个数）。显然我们有下面的命题1：命题1：对于两个记录r1和r2，若∃ri∈r1，rj∈r2，且ri≈rj，则可能有r1≈r2。命题1可以从反面来考虑，显然如果两个记录之间没有一对单条记录是匹配的，那么这两个记录也不可能匹配。也可以利用图来进行记录之间的匹配判断。Merge：融合操作。对于两个匹配记录，我们需要对他们进行融合操作形成一个记录来表示他们对应于同一个实体。一般融合操作的策略是采用连通图规则，即两个记录只要有一条联通边（即匹配），就将该记录进行融合合并成新记录直到找不到与

6、新记录联通的记录为止。这种策略一般不会将合成的新记录进行分割，因为这样可能会使融合操作陷入一个死循环。对于任意记录r中单条记录的个数，记为

7、r

8、。显然对于单条记录

9、r

10、=1，对于聚集

11、r

12、>1。下面我们对Merge进行形式化定义：定义2：对于两个记录r1和r2，若r1≈r2，需要对他们进行融合操作合并成一个新记录r12，记为。且r12=r1∪r2，

13、r12

14、=

15、r1

16、+

17、r2

18、。现在，我们可以对ER进行如下定义：2Pattern-BasedEntityResolution定义3：给定一个数据集I，I的一个ER

19、结果是一个记录（单条记录或聚集）的集合I’，I’中的元素满足如下条件：1)∀r∈I,有r∈I’且

20、I’

21、=

22、I

23、。2)∀r1∈I’，r2∈I’,有r1∩r2=∅。3)∀r1∈I’，r2∈I’,有r1≉r2。对于条件1）保证ER结果集I’是对源数据集I的一个划分且不存在冗余数据。条件2）保证对于任意单条记录只能属于唯一记录，对应唯一实体。条件3）保证结果集I’中不存在能够匹配的记录，每一个记录都对应一个不同的实体，确保结果集的完备性。通过上面的定义我们可以对数据集按照某种算法进行match和merge操作，生成满足定义3的E

24、R结果集。显然match操作是复杂度最高的操作，他需要对两个记录中的每一对单条记录进行一次匹配操作。这样如果记录中的数据集很大，这种匹配操作就会消耗大量的时间，成为整个算法中的瓶颈。而根据我们的了解，现在在这一方面还没有很突出工作发表。为了解决这个问题，我们创造性的提出了一种基于pattern的ER模型