具有重叠集合约束的实体解析问题研究

Entity Resolution Algorithm Based on Locality Sensitive Hash and Fuzzy Join

摘要: 本文研究了具有重叠集合约束的实体解析集合相似性连接问题。给定两个集合内元素为集合的集合以及一个常数c，找到数据集当中至少共享了c个共同元素的所有集合对。这一问题是许多领域诸如信息检索、数据挖掘和实体解析当中的基本操作。现有的方法都受到了O(n²)的限制，其中n是数据集总的大小。本文提出了一种算法复杂度为 的集合大小感知算法。集合大小感知算法根据集合大小将所有集合分为大集合与小集合并分别进行处理。本文通过现有的方法来处理大集合，对于小集合本文提出了集中启发式算法来提高算法性能。由于大集合与小集合的大小边界对于效率至关重要，本文还提出了一种有效的大小边界的选择方法来选择合适的大小边界。本文通过在真实数据集上的实验结果证明了该方法的有效性。

Abstract: In this paper, the entity resolution set similarity connection problem with overlapping set constraints is studied. Given two sets whose elements are sets of sets and a constant c, find all sets that share at least c common elements in the data set. This problem is a fundamental operation in many fields such as information retrieval, data mining, and entity resolution. Existing methods are limited by O(n²), where n is the total size of the dataset. This paper presents a set size awareness algorithm with complexity. The set size sensing algorithm divides all sets into large sets and small sets according to the set size and processes them separately. In this paper, the existing methods are used to deal with large sets. For small sets, a centralized heuristic algorithm is pro-posed to improve the algorithm performance. Since the size boundary of large sets and small sets is very important for efficiency, this paper also proposes an effective size boundary selection method to select the appropriate size boundary. Experimental results on real data sets demonstrate the ef-fectiveness of the proposed method.

1. 引言

判断相似实体作为实体解析的主要任务之一，对于模式未知或具有多值属性的实体，我们可以通过令牌化的方式将实体转换成是一个(令牌)标记集合，实体属性值的标记看作是集合当中的元素 [1] ，这样一来，通过判断集合的相似性来判断实体是否为相似实体。

具有重叠约束的集合相似性连接，给定两个集合(例如文档的主题集合)和一个常量c，找到所有共享至少c个公共元素的集合对，我们可以认为这些共享有c个公共元素的集合对之间是相似的。

给定一组文档，其中每个文档都包含多组字符串，对于每个词，我们可以获得一组包含该词的文档。许多词嵌入模型均利用一对单词同时出现的文档数量，例如基于深度学习的模型GloVe [2] 和Word2Vec [3] 以及基于经典矩阵分解的模型HAL [4] 和PPMI [5] 。重叠集相似度连接可以为这些模型构建单词共现矩阵，因为两个单词的共现与其对应文档集的重叠大小相同。此外，推荐系统 [6] 经常使用重叠集合来解释推荐，以获得更好的透明度和用户体验。

在算法设计方面，有一个简单解决方案，即简单地比较所有的集合对，并在O(n²)时间内完成，其中n是数据集总的大小。

现有方法 [7] [8] [9] 利用各种启发式方法来提高效率。然而，不幸的是，所有这些解决方案仍然受到O(n²)限制，即渐近地与暴力的解决方案一样糟糕。

本章研究了具有重叠约束的集合相似性问题。给定两个集合以及一个常数c，在数据集中找到至少共享c个公共元素的所有集合对。该问题是诸如数据挖掘、信息检索和机器学习等诸多领域的基本操作。现有方法的时间复杂度都是O(n²)，n是所有集合的总的大小。在本章中提出了一种大小感知算法，其算法复杂度为： $O\left(n^{2-\frac{1}{c}}{k}^{\frac{1}{2c}}\right)$ ，其中k指的是结果的数量。大小感知算法根据集合的大小将所有集合分为大集合与小集合并对它们进行分别处理。然后使用现有的方法对大集合进行处理，在本节中重点关注被划分为小集合的集合。本节中为小集合提出了几种启发式算法，来显著提高其处理效率。由于大集合与小集合之间的大小边界对于处理效率至关重要，因此本章中还提出了一种大小边界的选择方法。本章的主要贡献如下：

本章研究了具有重叠约束下的集合相似性连接问题，设计了一种集合大小尺寸感知算法，将所有集合分为大集合与小集合，分别进行处理。对于小集合我们枚举他们所有大小为c的子集，并选取至少共享一个大小为c的子集的集合作为结果。为了避免小集合枚举不必要的大小为c的子集，我们还设计了两种优化方案。针对大小集合选择的尺寸边界，提出了一种有效的方法来寻找理论上最佳的尺寸边界。实验结果证明该边界是较优的解。

2. 问题定义

输入：集合R、集合S以及常量c，其中集合R与集合S当中的元素均为集合

输出： $\left\{\langle R^{\prime },S^{\prime }\rangle |\langle R^{\prime },S^{\prime }\rangle \in R\times S,且\left|R^{\prime }\cap S^{\prime }\right|\ge c\right\}$

给定两个元素均为集合的集合R与S，并给定常量C。这里的常量C定义了集合相似的标准。问题就是如何在R × S空间中找到所有相似的集合对 $\langle R^{\prime },S^{\prime }\rangle$ ，其中R'和S'是相似的。并且为了接下来叙述的简洁在这里定义，任意一组从集合R与集合S中获取的元素c称之为c-subset。基于两个集合相似当且仅当他们共享一个任意的c-subset。这一发现促使我们在所有的c-subset上建立倒排索引，找出那些共享公共c-subset的集合，并依次通过检查每一个倒排索引来计算连接结果。因我们避免枚举不同的集合对，即不共享任何公共c-subset的集合对。但是这种方法仅适用于小尺寸的集合，因为小尺寸的集合具有少量的c-subset。另一方面，大集合的数量也不能太大，因为我们对大集合采用的是暴力的方法。

下面对这个问题进行举例说明：

$R=\left\{R_1,R_2,R_3\right\}$

$R_1=\left\{e_1,e_2\right\}$ ， $R_2=\left\{e_1,e_3,e_4,e_6\right\}$ ， $R_3=\left\{e_2,e_5,e_7\right\}$

$S=\left\{S_1,S_2\right\}$ ，

$S_1=\left\{e_2,e_5,e_6\right\}$ ， $S_2=\left\{e_1,e_2,e_4,e_5,e_6,e_7,e_8\right\}$

给定常量c = 2

则仅当两个集合R'，S'交集大小 $\left|R_1\cap S_1\right|\ge 2$ 时认为R'和S'相似

$R\times S=\left\{\langle R_1,S_1\rangle ,\langle R_2,S_1\rangle ,\langle R_3,S_1\rangle ,\langle R_1,S_2\rangle ,\langle R_2,S_2\rangle ,\langle R_3,S_2\rangle \right\}$ 其中相似集合对有 $\langle R_3,S_1\rangle$ ， $\langle R_1,S_2\rangle$ ， $\langle R_2,S_2\rangle$ ， $\langle R_3,S_2\rangle$ ，因此输出的结果应该为这四个集合对。

暴力方法通过枚举R × R中的每个集合并计算他们的重叠部分大小。暴力方法的时间复杂度为O(n²)。

3. 集合大小感知算法

3.1. 算法主要思想

1) 将所有的集合元素进行划分，根据他们的大小将他们划分为大集合R_l以及小集合R_s，选定边界x，大集合即为集合大小大于x的集合，小集合为集合大小小于x的集合。将R × R笛卡尔积空间划分为R_l × R与R_s × R_s。(R_s × R_l的集合已经被包含在R_l × R当中，只是当中的顺序并不相同，因此在这里不做考虑)。

2) 对于R_l × R，可以采用现有的方法进行处理，在本节中采用暴力搜索，即遍历大集合当中的每一个元素R_i，再遍历R中的每一个集合，直接进行 $\left|R_i\cap R\right|$ ，看大小是否 ≥ c。

3) 对于R_s × R_s，为每个c-subset建立倒排索引L[r]。这样使得L[r]中的每个不同集合都至少包含这个c-subset子集，满足相似性阈值c。而从L [r]中不同集合所组成的集合对也满足相似性阈值c。

3.2. 算法框架

该算法囊括了R_l × R笛卡尔积空间的所有元素，对于R_s × R_s部分，对于其中任意两个集合R₁、R₂满足相似性阈值c，则他们的交集大于等于c，取该交集的一个子集r，r的大小为c，则必有R₁、R₂均在L[r]中；而若L[r]中有两个集合R₁、R₂中，则说明R₁、R₂的交集中至少有一个c-subset，因此 $\left|R_1\cap R_2\right|\ge c$ 。由此可以得出结论R_s × R_s算法是找到小集合中所有满足条件的集合对的充要条件。又因为R_s × R_l的集合已经被包含在R_l × R当中，所以R_s × R_l和R_s × R_s已经囊括了解空间，因此一定能够生成所有的解。这就是整个算法的框架，针对该算法框架还提出了对于小集合处理方法的优化以及划分边界X的确定。

Table 1. Data set R

表1. 数据集R

Table 2. Rl × R

表2. R_l × R

示例：调用表1中的数据集R，并且假设阈值c为2，大小边界x为5。根据大小边界x我们将集合划分为大集合与小集合，得到 $R_s=\left\{R_1,R_2,R_3,R_4,R_5\right\}$ 以及 $R_l=\left\{R_6,R_7,R_8\right\}$ 。第一步我们首先枚举R_l × R中的所有集合对，并对它们的交集大小进行计算得到的结果如表2所示，符合阈值c条件的有 $\langle R_1,R_6\rangle$ $\langle R_2,R_6\rangle$ $\langle R_3,R_6\rangle$ $\langle R_4,R_6\rangle$ $\langle R_5,R_6\rangle$ $\langle R_7,R_8\rangle$。然后我们为小集合当中找到的所有大小为2的子集构建倒排索引。该倒排索引如表3所示，倒排索引L{e₁e₂}有两个集合R₁与R₂，根据该倒排列表我们可以得到相似对 $\langle R_1,R_2\rangle$ 。类似地还能从倒排列表L{e₁e₃}L{e₁e₅}L{e₂e₃}……等获得相似对。

Table 3. The c-subset inverted index for small sets

表3. 小集合c-subset倒排索引

集合大小感知算法划分大小集合灵感来源：现有方法为集合中的元素构建倒排索引I。每个倒排列表I[e]都要被扫描|I[e]|次，其中|I[e]|指的是倒排列表的长度。因此现有方法需要O(|I[e]|²)来处理每个倒排列表I[e]。然而在集合大小感知算法中，因为总共有n个元素，且大集合内包含的元素大于X，所以大集合的数量不超过n/x个。因此大集合对于倒排列表长度的贡献最多为n/x。相反，因为小集合的大小没有限制，所以小集合最多可以为倒排列表长度的贡献为n，从而导致时间复杂度为O(n²)。这就是现有方法无法在小集合上执行，但是我们在大集合上执行现有办法的原因。

3.3. 小集合处理法方法的优化

枚举每一个小集合中的所有c-subset成本十分巨大，尤其是当小集合具有大尺寸的时候。对于每个小集合，大小感知算法需要枚举其所有c-subset子集r以构建完整的倒排索引L[r]并基于它生成结果。如果一个L[r]只有单一的集合，即它在所有小的集合中只出现一次，我们可以避免生成它并获得一个可以生成所有结果的精简倒排索引，因为唯一的L[r]不能产生任何结果。

由于存在大量唯一的c-subset子集，因此避免通过他们生成L[r]很重要。例如在表3当中有诸如e₁e₃、e₁e₄、e₁e₇等c-subset。他们都是唯一的c-subset，因此并不需要生成他们。将这一优化命名为Heapskip。

我们给出的跳过c-subset的方法如下：

首先对所有小集合中的c-subset进行一个全局的顺序。我们按照升序的方式来访问c-subset，并将最小的未访问的c-subset表示为min-subset。最小堆H用来管理所有最小的min-subset。每次通过堆顶获得一个当前最小的c-subset集合r，假定r来自小集合R，设r₂是剔除r之后的堆顶元素，则r₂可以表示为来自R₂的R_s\R集合中最小的c-subset。

R中的c-subset集合r'满足 $r<r^{\prime }<r_2$ 。由于r₂代表了R_s\R中最小的c-subset，因此R\R_s中一定不存在集合R₃，使得R₃包含r'，否则应有r₂ = r'为更小的c-subset。从而r'子集是无需建立倒排索引的，因为其中只可能包含集合R而不会出现集合对。

由此，因为每个集合的c-subset已经被我们排序了，我们可以在R中使用二分搜索，找到R中第一个“不小于”r₂的c-子集r₃，将其加入堆H，从而跳过r和r₃之间的所有c-subset。

我们的优化除了去除唯一的c-subset还有去除掉冗余的c-subset。我们将这一优化命名为HeapDedup。

具体优化算法如下：

对R_s中所有小集合中的所有元素e进行全局标号(标号规则任意选取，如随机生成下标)，标号小，则认为该元素“更小”，同时利用这种标号新定义集合间的“大小关系”：对集合R₁，R₂，若R₁中“最小”(标号)的元素比R₂中“最小”的元素“更小”，则R₁小于R₂，若相等，则比较“次小”元素···；据此，将每个小集合中的c-subset按照这种“大小关系”进行排序。

对于每个小集合，将每个小集合的“最小”(依据标号)的c-subset拿出来建立一个最小堆H，入堆的同时记录每个子集来自哪一个小集合R_i。

提出该优化的主要是基于如下的思想：

$L\left[r_1\right]\subseteq L\left[r_2\right]$ ，则r₁是冗余的，因为L[r₁]产生的集合对一定包含在L[r₂]的集合对中。

②对于r₁和L[r₁]，设r₂为R_s\L[r₁]的集合中min-subset，则满足： $r_1<r<r_2$ 的集合r是冗余的。首先r一定是L[r₁]中集合的某个c-subset，否则应有r₂ = r。其次 $L\left[r\right]\cap \left(R_s\backslash L\left[r_1\right]\right)=\cancel{c}$ .否则在R_s\L[r₁]中存在集合R包含集合r，由①可知，R应在L[r₁]中，矛盾。从而 $L\left[r\right]\subseteq L\left[r_1\right]$ ，r是冗余的。

每次循环时若min = top，直接continue实现lazy处理，从而下次选取时将top所在集合R'加入L[min]中

每次循环时若min ≠ top，由于top是当前min-subset，只有两种可能：

① top为R_s\L[min]的min-subset。则由上面的分析，所有位于min和top之间的c-子集都是冗余的，可以跳过。

② top为L[min]的最小c-subset (除min之外)，设r为R_s\L[min]的min-subset，则有r大于等于top。故位于min和r之间的所有c-subset都是冗余的，但由于r未知，我们转而利用top，因为top小于等于r，必有min和top之间的c-subset都是冗余的。

无论如何，min和top之间的c-子集均是冗余的，从而我们对于L[min]中的每个集合都利用二分搜索找到第一个大于等于top的c-subset，插入到堆H中，将那些冗余子集跳过。同时由于min = top时的lazy处理，我们在min ≠ top时的处理是针对L[min]中一组集合的操作，包含了Heapskip的功能。

3.4. 边界X的选择

我们用x来表示算法的时间复杂度，然后找到最佳的x以最小化成本。

① 首先计算大集合R_l × R的时间复杂度。我们为所有的大集合建立哈希表，从而可以在常数时间内判断元素e是否属于该集合。并且由于大集合的大小大于等于x，所以大集合的数量至多为n/x个。通过R'中的每一个元素检索R的哈希表。所以对于一个大集合R₁，计算交集 $\left|R_1\cap R^{\prime }\right|$ 的时间是 $O\left(\left|R^{\prime }\right|\right)$ ，因此大集合的时间复杂度为：

${\displaystyle {\sum }_{R^{\prime }\in R}O\left(\left|R^{\prime }\right|\cdot \frac{n}{x}\right)}=O\left(\frac{n^2}{x}\right)$ (1)

② 然后计算R_s × R_s小集合的时间复杂度。第一步枚举所有c-subset以构建倒排索引；第二步从倒排索引中生成相似的对。一个小集合R有 $\left(\begin{array}{c}\left|R\right|\\ c\end{array}\right)$ 个，由于 $\left|R\right|\le x$ (因为R是一个小集合)，所以小集合c-subset的总数最多为：

${{{\displaystyle \sum }}^{\text{}}}_{R\in {\mathcal{R}}_s}\left(\begin{array}{c}\left|R\right|\\ c\end{array}\right)\le {{{\displaystyle \sum }}^{\text{}}}_{R\in {\mathcal{R}}_s}{\left|R\right|}^c\le x^{c-1}{{{\displaystyle \sum }}^{\text{}}}_{R\in {\mathcal{R}}_s}\left|R\right|\le x^{c-1}n$ (2)

第一步的枚举成本趋近于上述的公式结果。即第一步的成本以 $O\left(x^{c-1}n\right)$ 为界限。

第二步的成本来自生成每个倒排索引的集合对。因此第二步的时间复杂度为 $\left({\displaystyle {\sum }_{i=1}^l{\left|{\mathcal{L}}_i\right|}^2}\right)$ 。由于所有倒排索引的总的长度是所有小集合中c-subset的个数，所以 ${\displaystyle {\sum }_{i=1}^l\left|{\mathcal{L}}_i\right|}\le x^{c-1}n$ 。因为k是R × R相似集合对的总数，因此 ${\mathcal{L}}_i$ 中生成的相似集合对的数量不能超过k，即对于任意的 ${\mathcal{L}}_i$ ，都有 $\frac{\left|{\mathcal{L}}_i\right|\left(\left|{\mathcal{L}}_i\right|-1\right)}{2}\le k$ 。因此第二步的复杂度为：

$O\left({\displaystyle {\sum }_{i=1}^l{\left|{\mathcal{L}}_i\right|}^2}\right)=O\left(\sqrt{k}{\displaystyle {\sum }_{i=1}^l\left|{\mathcal{L}}_i\right|}\right)=O\left(x^{c-1}n\sqrt{k}\right)$ (3)

假设k已知的时候，算法的复杂度为：

$O\left(\frac{n^2}{x}+x^{c-1}n\sqrt{k}\right)$ (4)

我们取 $x={\left(n/\sqrt{k}\right)}^{1/c}$ 使得时间复杂度最低。在这种情况下时间复杂度为：

$O\left(n^{2-\frac{1}{c}}{k}^{\frac{1}{2c}}\right)$ (5)

例如按照表1的数据集，当阈值c = 2时， $n={\displaystyle {\sum }_{i=1}^7\left|R_i\right|}=40$ ，k = 5，因此设置 $x={\left(40/\sqrt{5}\right)}^{1/2}\approx 5$ 。

但k往往是未知的，因此我们使用“doubling Trick”，用k'猜测k，从k' = 1开始尝试，如果正确，则应该执行的步骤个数为 $\alpha \cdot n^{2-\frac{1}{c}{\hat{k}}^{\frac{1}{2c}}}$ ( $\alpha$ 是总复杂度中隐含的常量)。当执行的步骤为 $1+\alpha \cdot n^{2-\frac{1}{c}}{\hat{k}}^{\frac{1}{2c}}$ 时，我们知道了 $k^{\prime }<k$ ，重复操作直到 $k^{\prime }\ge k$ ，每一轮的时间为 $O\left(n^{2-\frac{1}{c}}{k}^{\frac{1}{2c}}\right)$ 。为了达到所需要的复杂度，我们从k' = 1开始。在其终止时，k'的值最多为2k，否则算法将会在前一轮终止。因此所有轮次的总的运行时间为：

$O\left({\displaystyle {\sum }_{i=0}^{{\log }_2\left(2k\right)}{n}^{2-\frac{1}{c}}{\left(2^i\right)}^{\frac{1}{2c}}}\right)=O\left(n^{2-\frac{1}{c}}{k}^{\frac{1}{2c}}\right)$ (6)

4. 实验

4.1. 数据集

本节使用了从“面向领域Web数据抽取”项目所抽取的多个数据源的房地产数据进行实验。每个楼盘、楼栋都是一个集合，绿化率、建筑面积、总户数、楼栋数、房屋面积等等楼盘、楼栋的属性都是元素。

第一组实验旨在确定处理小集合的最佳的基于堆的处理方案。为此使用了两组来自不同城市的楼盘、楼栋、户型数据，如表4所示：

Table 4. Data sets

表4. 数据集

4.2. 优化方案评估

我们使用了以下的三种方法：1)：naive，枚举每一个小集合的c-subset；2)：headship，利用最小堆跳过唯一的c-subset；3)：heapdedup，利用最小堆跳过唯一的c-subset以及相邻的冗余c-subset。我们通过改变阈值并就不同阈值下c-subset的数量(即堆弹出操作的数量)进行比较如下图1所示：

(a) (b)

Figure 1. Comparison of the number of c-subset enumerated by each method

图1. 各方法枚举出的c-subset数量的比较

首先我们观察到随着阈值c的增大，使用navie方法枚举出的c-subset的数量指数级的往上增加，headship与heapdedup两种优化方法都显著的减少了枚举的c-subset的数量。我们还发现了一个现象随着阈值c的增大，采用headship优化后枚举的c-subset的数量还是在缓慢增加，而采用heapdedup优化后枚举的c-subset随着阈值c的增大而减小。该对比试验验证了headship与heapdedup两种优化的有效性，并且heapdedup方案优于headship方案。

4.3. 尺寸边界选择评估

本小节的实验集中在对于尺寸边界的选择上。我们试验了在不同阈值c下边界x对于实验时间的影响。评估了尺寸感知算法对于大小集合的处理时间。如下图2所示。

(a) (b)

Figure 2. The influence of boundary X on the running time of small sets under different thresholds

图2. 不同阈值下边界X对于大小集合运行时间的影响

Figure 3. The influence of boundary X on the total time of the set under different thresholds

图3. 不同阈值下边界X对于集合总共运行时间的影响

Table 5. 不同大小边界花费的时间

表5. Time spent on different size boundaries

图2给出了处理小集合所需要的花费的时间，图3给出了处理大集合所需要的花费的时间，图3给出了总共需要花费的时间。我们发现随着尺寸边界的增加，大集合时间成本的下降最初是相当显著的，但是后来变得微不足道。对于小集合一开始时间成本增长缓慢，之后时间成本急剧增加。

表5展示了由我们尺寸感知算法选出的最佳的x以及实际情况下最佳的x，此外还展示了每个尺寸边界下运行的时间。可以看出我们尺寸边界感知算法非常有效给出的最佳边界是接近最佳值的较好的值。

5. 总结

本节中提出了一个在具有重叠约束的集合相似性连接问题中算法复杂度为 $O\left(n^{2-\frac{1}{c}}{k}^{\frac{1}{2c}}\right)$ 的算法。其中n是所有集合的总的大小，常数c是相似度阈值，k是结果中相似集合对的数量。将所有集合按照边界x分成大集合与小集合，分别进行处理。对于小集合，我们枚举其所有的c-subset，为了避免不必要的c-subset，还提出了两种优化方案，一种是对无法生成任何结果的唯一的c-subset进行删减。另一种对仅生成重复结果的冗余c-subset进行删减。并且设计了一种选择边界x的方法并验证了其有效性。实验发现随着尺寸边界的增加，大集合时间成本的下降最初是相当显著的，但是后来变得微不足道。对于小集合一开始时间成本增长缓慢，之后时间成本急剧增加。由尺寸感知算法选出的最佳的边界x是接近最佳值的较好的值。