一种适合大数据环境具有抗噪声能力的实体解析方法

摘要

本发明公开了一种适合大数据环境具有抗噪声能力的实体解析方法，所述方法是在传统相关性聚类方法的基础上进行改进，通过引入邻居关系和核概念，由两层算法实现。上层算法基于邻居关系对数据进行粗糙的、允许重叠的预分块处理；下层算法通过引入核的概念，精确地定义了节点与类之间的关联程度，以便准确地判断节点的归属，进而提高相关性聚类的准确度。

说明书

技术领域

本发明属于数据集成系统领域，具体涉及一种适合大数据环境具有抗噪声 能力的实体解析方法。

背景技术

随着信息技术的发展，数据获取途径呈现多样化的趋势，数据质量问题成 为人们面临的最大挑战。如何从海量数据中快速有效地获取有用信息，已经成 为人们研究的焦点。数据集成不仅可以丰富单一数据的内容，还能够提高数据 的准确性。实体解析是数据集成的一个重要步骤，它的任务是从不同的数据源 中找出指代现实世界中同一实体的记录。已有的实体解析算法通常是基于特征 匹配的，这不仅需要很大的计算开销，而且严重依赖于数据模式的存在。另一 方面，实体解析算法最终的结果常常不具备传递闭包的性质，即会出现类似于A 和B属相同实体，B和C属相同实体，而A和C却属于不同实体的情况，即出现冲 突（conflicts）。为解决该问题，有些实体解析算法会对结果进行传递性闭包分 析（transitive closure analysis，记为Trans），即对上述情况，即使A和C的判别 结果为不同，而最终的分析结果会认为A和C相同。如果B和C被算法判别相同的 依据很弱，而A和C被算法判别为不同的依据又很强的话，简单地进行传递性闭 包分析显然会得出错误的结论。

数据质量问题在大数据环境下显得更为突出。大数据具备四个特点：数据 量大（Volume）、数据更新速度快（Velocity）、数据源多样（Variety）和数据 存在噪声（Veracity），即4Vs特点。数据量大的特点使得我们不能选用计算开 销比较大的方法，数据源多样使得我们的算法不能过度依赖模式，数据存在噪 声使得算法解析的结果存在冲突的可能性变大。

因此，实体解析算法的计算开销大、模式依赖性强、抗噪声能力弱的技术 问题亟待解决。

相关性聚类是实体解析的一个标准方法，由Bansal等人提出，目标是找到一 个能够消除冲突的聚类结果，同时使得该结果尽可能与实体解析算法的判断一 致。

给定一个无向完全图G=(V,E),其中每一条边(i,j)都有一个概率p_i,_j，表示 将节点i和j归到一个类中的概率。如果用表示切断边(i,j)的代价，表示 保留边(i,j)的代价，x_i,j表示二值变量，当节点i和j被分到同一个类中时，x_i,j＝1； 否则，x_i,j＝0。相关性聚类的目标函数可以写成：

$\min \underset{\mathrm{ij},:i<j}{\Sigma }{x}_{\mathrm{ij}}{w}_{i,j}^{-}+(1-x_{\mathrm{ij}})w_{i,j}^{+},$

其中，简记为

相关性聚类算法是一个NP-hard问题，因此很多启发式算法被提出，其中， Pivot和Vote是最具代表性的两个算法。Pivot算法按照一个节点序列，每次选取 一个未被归类的节点作为中心，简单地将与之相邻且未被归类的节点j 归到同一个类中。Vote算法按照投票的方式决定节点的归属，算法每次选择一 个未被归类的节点i，计算每一个已生成的类对该节点的投票情况，将节点i放到 投票最多的类c中，即类c满足其中C为已经生成的类。如果没有已 生成的类，或所有已生成的类对节点i都持中立或反对票，我们就将该节点单独 作为一个新的类，加入到C中。

传递性闭包分析和相关性聚类均是消除实体解析算法结果冲突的方法。传 递性闭包分析仅依赖于positive evidences（实体解析算法判断为相似的节点对）， 而忽略了negative evidences（实体解析算法判断为不相似的节点对），这样很容 易将错误传递，特别在噪声数据较多的大数据环境下，算法的准确率和召回率 都很低。相关性聚类虽然考虑了positive evidences和negative evidences的成立支 持度，以及违背这些evidences所要付出的代价，但Pivot和Vote均依赖于一个随 机的节点序列。Pivot简单地考虑节点与节点之间的直接关系，而忽略其邻居关 系，不仅准确率较低，且不能很好地容忍噪声数据。Vote对每个节点归类的时 候，都会进行代价计算，并将节点归到代价最小的类中。在进行代价计算时， 类中的每一个节点都会起到投票的作用，投票权的分散导致聚类结果的准确率 和召回率降低。

实体解析（entity resolution）用于确定指代现实世界中同一实体的记录。

噪声数据（noisy data）就是无意义的数据（meaningless data）。这个词通 常作为损坏数据（corrupt data）的同义词使用。

发明内容

针对现有技术的缺点，本发明的目的是设计能适用于大数据环境的计算开 销小、不依赖于模式，且具有良好的抗噪声能力的实体解析算法。

为了实现上述目的，本发明采取的技术方案是：

本发明是在传统相关性聚类方法的基础上进行改进，通过引入邻居关系和 核概念，提高方法的抗噪声能力，同时获得高质量的实体解析结果。方案由两 层算法实现：上层算法基于邻居关系对数据进行粗糙的、允许重叠的预分块处 理；下层算法通过引入核的概念，更加精确地定义了节点与类之间的关联程度， 以便准确地判断节点的归属，进而提高相关性聚类的准确度。

本申请对未归类的记录，首先使用粗糙的相似度函数计算每个节点对之间 的相似程度。这里考虑到降低计算开销和淡化模式依赖的原则，我们选用了 Jaccard相似度。一般来说，对于两个集合S和T，Jaccard定义如公式1所示：

$\mathrm{Jaccard}(S,T)=\frac{|S\cap T|}{|S\cup T|}.---\left(1\right)$

本申请在相关性聚类问题中引入邻居关系，采用两层算法进行实体解析， 其流程图如图1所示。

两层相关性聚类算法基于邻居关系实现。为了方便定义，我们称满足条件 的边为正边，否则为负边。

定义1.对于节点i，其邻居定义为与其有正边的节点集合，包含其本身， 简记为

定义2.对于节点i和j，我们定义其公共邻居(common neighborhood)为其 邻居的交集，简记为定义节点i相对于节点j的非公共邻居(non-common  neighborhood)为属于节点i的邻居但不属于节点j的邻居的节点集合，简记为

上层预分块算法

本申请的技术方案是：如果两个节点可以归为一类，那么它们应该和同样 的节点有尽可能相同的匹配概率，即概率相当。基于这个想法，我们提出邻居 向量(neighborhood vector)的概念。

定义3.对于节点i，其邻居向量简记为其 中n为节点i的邻居个数，（k）为节点i的第k个邻居节点且1≤k≤n，p_i,(k)为节 点i和第k个邻居节点所在边的概率；如果当（k）=i时，即节点（k）为节点 i本身时，p_i,(k)＝1。

如果节点i和j由一条正边相连，其邻居向量分别为将这两 个向量对齐，即在空白位置补上相应的概率后，可以使用余弦相似度来计算节 点i和j的邻居相似度(neighborhood similarity)，简记为sim(i,j):

显然，两个节点对的邻居相似度越大，它们就越有可能归到一个类中，并 且该节点对的公共邻居的邻居都有可能属于这一个类。因此，预分块算法每次 选择当前邻居相似度最大的节点对，将该节点对的公共邻居的邻居作为一个类。 假设当前邻居相似度最大的节点对为节点i和j，由其形成的类应该包含两层节 点，内层为节点i和j的公共邻居，外层为节点i和j的公共邻居的邻居，其中，内 层节点，即节点i和j的公共邻居，称之为类的核。预分块算法依赖于一个节点对 的序列（即边的序列），算法每一次迭代之后，都会将当前节点的公共邻居所 在的边从边序列中移除。当边序列为空时，算法终止。预分块算法的流程如图2 所示。

下层调整块算法

下层调整块算法主要是为了解决上层预分块算法带来的分块重叠问题。该 算法旨在将重叠节点归到和其具有最大关联程度的类中。对于节点i以及某个包 含该节点的类c，我们从类c的核内找到与节点i邻居相似度最大的节点j，我们认 为如果节点i属于类c，那么它应该和节点j落在核内的邻居有很强的关联。这种 关联就称为节点i与类c的关联程度，简记为R_i(c,j):

其中，j＝x|max_x∈c.kernelsim(i,x)。

下层调整块算法的流程图如图3所示。算法的输入是上层预分块算法的分 块结果C。对于集合V中的每一个重叠节点i，计算i与C中每一个包含它的 类的关联程度。如果存在这样一个类，它与i的关联程度最大且大于0，算法 将i归入该类，同时将它从其它类中移除。如果i与所有包含它的类的关联程 度都不大于0，就将其单独作为一个类，并从所有包含它的类中移除。

实体解析是数据集成的一个重要步骤，在学术网络、信息检索领域有着广 泛的应用。实体解析算法不仅可以去除冗余，还能够丰富单一数据的内容。本 发明技术方案能够适应大数据环境的要求，弱化数据噪声的影响，大大提高了 实体解析的质量。

有益效果

与现有的技术相比，本发明具有实体解析质量高和抗噪声能力强的优点。

1）方法在相关性聚类问题中引入邻居关系以及核的概念，提高了实体解析 的质量

我们在Cora数据集上运行Pivot、Vote和Two-Tiered三个算法以对比实体 解析的质量。实验分为有权和无权两种情况。

图4a-4d显示，本方法Two-Tiered整体上优于现有的方法Pivot和Vote。在准 确率方面，Pivot只是简单地考虑节点之间的直接关联，而忽略邻居关系，准确 率最低；Vote让类中所有节点享有投票权，投票权的分散导致聚类结果的准确 率降低；Two-Tiered不仅考虑了邻居关系，而且引入核的概念，只有核中节点享 有投票权，因此准确率最高。在召回率方面，Pivot随机选择一个中心节点，简 单地将所有与该节点相连而未分类的节点归为一类，没有直接联系的节点只能 纳入其他类，自然会影响召回率；Vote将类中的所有节点都视为核节点，都能 起到判断一个节点是否属于该类的作用，很容易将新的节点拒之门外，导致召 回率较低；Two-Tiered算法分为两层，第一层的初分块算法在考虑节点之间直接 联系的同时还考虑了邻居关系，尽可能将有邻居关系的节点纳入同一类，第二 层的调整算法仅让部分有代表性的节点享有投票权，在提高准确率的同时也保 持了较高的召回率。F度量和调整后的兰德指数指标从整体上衡量算法的质量， 我们的算法具有明显的优势。

2)方法由于考虑邻居关系和采用粗糙的相似度函数，抗噪声能力显著提高， 更能适应大数据环境

为评估Two-Tiered算法的抗噪性，我们将其和传统的传递性闭包分析算法 （Trans）和相关性聚类算法Pivot进行对比。实验数据的产生方式如下：我们 首先在Cora数据集上获得理想的聚类结果，即知道任意两个节点是否归属于 同一个类的判断；然后随机地改变其中一定比例的节点对的判断，来达到添加 噪声的效果。我们的实验针对两种噪声比例：6%和10%，它们分别对应50000 和80000个节点对判断的改变。

表1 抗噪声性能对比

表1中的实验结果表明我们的Two-Tiered算法在抗噪声性能方面表现出绝 对的优势，其主要原因在于Two-Tiered算法充分考虑了节点之间的邻居关系， 邻居关系的引入可以明显降低噪声数据对聚类结果的影响。

此外，在对图4a-4d的观察中，我们发现Pivot和Vote在有权和无权时的表现 结果有很大的区别，并且在有权情况下的表现优于无权，而我们的Two-Tiered 算法在两种情况下的表现几乎是一致的。在大数据环境下，由于数据异构性和 噪声数据的存在，我们很难准确地获得两条记录的匹配概率，也即很难获得准 确的权重信息，这要求实体解析算法的解析结果不能过度地依赖权重。我们的 算法在无权的情况下依然表现出良好的结果，证明我们的Two-Tiered算法比Pivot 和Vote更能适用于大数据环境。

附图说明

图1两层相关性聚类算法总的流程；

图2上层预分块算法的流程；

图3下层调整块算法的流程；

图4a三种算法在有权和无权情况下准确率的对比;

图4b三种算法在有权和无权情况下召回率的对比;

图4c三种算法在有权和无权情况下F度量的对比；

图4d三种算法在有权和无权情况下调整后的兰德指数的对比。

具体实施方式

一种适合大数据环境具有抗噪声能力的实体解析方法，所述方法是在传统 相关性聚类方法的基础上进行改进，通过引入邻居关系和核概念，由两层算法 实现，上层算法基于邻居关系对数据进行粗糙的、允许重叠的预分块处理；下 层算法通过引入核的概念，精确地定义了节点与类之间的关联程度，以便准确 地判断节点的归属，进而提高相关性聚类的准确度，其中，所述方法具体包括 如下步骤：

（1）对未归类的记录，首先使用粗糙的相似度函数计算每个节点对之间的 相似程度，选用Jaccard相似度，对于两个集合S和T，Jaccard定义为公式1所示：

$\mathrm{Jaccard}(S,T)=\frac{|S\cap T|}{|S\cup T|}.---\left(1\right)$

（2）在两层相关性聚类问题中引入邻居关系，采用两层算法进行实体解析； 所述两层相关性聚类算法基于邻居关系实现；

（3）满足条件的边为正边，否则为负边；其中，对于节点i，其邻 居定义为与其有正边的节点集合，包含其本身，简记为

对于节点i和j，它们的公共邻居为其邻居的交集，简记为定义节 点i相对于节点j的非公共邻居为属于节点i的邻居，但不属于节点j的邻居的 节点集合，简记为

（4）上层预分块算法

如果两个节点可以归为一类，那么它们应该和同样的节点有尽可能相同的 匹配概率，即概率相当，即拥有相似的邻居向量；

其中，对于节点i，其邻居向量简记为其 中n为节点i的邻居个数，（k）为节点i的第k个邻居节点且1≤k≤n，p_i,(k)为节 点i和第k个邻居节点所在边的概率；如果当（k）=i时，即节点（k）为节点 i本身时，p_i,(k)＝1；

如果节点i和j由一条正边相连，其邻居向量分别为将这两 个向量对齐，即在空白位置补上相应的概率后，使用余弦相似度来计算节点i 和j的邻居相似度，简记为sim(i,j):

（5）下层调整块算法

下层调整块算法主要是为了解决上层预分块算法带来的分块重叠问题，该 算法可以将节点i归到和其具有最大关联程度的类中，对于节点i以及某个类c的 核内与节点i邻居相似度最大的节点j，如果节点i属于类c，那么它应该和节点j落 在核内的邻居有很强的关联，这种关联为节点i与类c的关联程度，简记为R_i(c,j):

其中，j＝x|max_x∈c.kernelsim(i,x)。

在步骤（4）中，预分块算法每次选择当前邻居相似度最大的节点对，将该 节点对的公共邻居的邻居作为一个类，预分块算法依赖于一个节点对的序列即 边的序列，算法每一次迭代之后，都会将当前节点的公共邻居所在的边从边序 列中移除，当边序列为空时，算法终止。如果预分块算法产生的类是由节点i和 节点j的公共邻居及其公共邻居的邻居形成的，那么节点i和节点j的公共邻居为该 类的核，预分块算法形成的类由两层节点组成，内层为i和j的公共邻居，外层为 i和j的公共邻居的邻居，内层节点，即节点i和j的公共邻居，称之为类的核。

所述步骤（5）中，下层调整块算法，所述算法的输入是上层预分块算法的 分块结果C，对于集合V中的每一个重叠节点i，计算i与C中每一个包含它的 类的关联程度，如果存在这样一个类，它与i的关联程度最大且大于0，算法将 i归入该类，同时将它从其它类中移除，如果i与所有包含它的类的关联程度都 不大于0，就将其单独作为一个类，并从所有包含它的类中移除。

最后应说明的是：显然，上述实施例仅仅是为清楚地说明本申请所作的举 例，而并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说 明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的 实施方式予以穷举。而由此所引申出的显而易见的变化或变动仍处于本申请型 的保护范围之中。