Tamr（以前的 Data Tamer）大规模执行数据库重复数据删除。涉及朴素贝叶斯和图聚类。

我相信这些算法主要是在 SQL 中实现的，这有点奇怪，但他们白皮书的主要作者是 Michael Stonebraker，他帮助领导了 PostgreSQL 的创建。

在此处查看白皮书。

编辑：我在下面总结了他们的论文所采取的步骤。我的一些话与他们论文中的几乎相同。

Tamr 的重复数据删除系统有两个主要步骤来处理新数据源：（1）属性识别和（2）实体整合。这些大致相当于列重复数据删除和行重复数据删除。

1) 将新数据源与现有数据源进行比较，第一步是属性识别。

新源的属性（列）通过四种算法映射到现有源的属性：

• 将属性名称与模糊字符串比较（三元余弦相似度）进行比较
• 将整个列视为文档，标记化，测量该列与其他列之间的总频率/逆文档频率 (TF-IDF) 余弦相似度。
• 最小描述长度：根据它们的交集和并集的大小与精确匹配比较两列。
• 对于数值列，在新列和现有数值列之间执行 t 检验，以确定它们是否来自同一分布。

2）实体合并（行重复数据删除）

一旦执行了属性识别，我们想要对行（记录）进行重复数据删除。

聚类分类

首先根据相似性将记录分组，然后在类别级别学习重复数据删除规则。他们给出的分类示例是针对滑雪胜地的数据库，其中西部滑雪胜地应该是与东部滑雪胜地不同的类别，因为诸如基础高程之类的特征被度假村是东部还是西部强烈分开。分类是通过聚类算法完成的，以 k-means 为例。

使用朴素贝叶斯进行重复数据删除

一旦确定了属性并将记录聚类到类别中，我们就会根据重复和非重复的训练集学习每个类别的重复数据删除规则。

有两种类型的重复数据删除规则：

1. 相对于对属性有意义的距离函数的属性相似性阈值。（论文不清楚这些阈值是如何学习的。）
2. 每个属性中重复和非重复的概率分布。例如P("Title" values similar | duplicate) ~ 1和 Pr("State" values are different | duplicate) ~ 0

对于每对记录，我们使用适当的距离度量来计算它们每个属性的相似性。如果任何属性的相似度高于其阈值，则这对记录将通过朴素贝叶斯分类器进行分类，以分类为重复或非重复。

我的假设是，对于记录X1 = (a1,b1,c1,d1)，X2 = (a2,b2,c2,d2)他们计算相似度向量S = (s_a, s_b, s_c, s_d)，其中s_i该属性与正确距离度量的相似度。

我假设他们的朴素贝叶斯分类器具有以下结构：

P(dupe|S) = P(dupe)P(s_a|dupe)(s_b|dupe)(s_c|dupe)P(s_d|dupe) / P(S)

图聚类的实体解析

在分类步骤之后，我们有来自给定类别的记录子集，这些记录被认为是成对重复的。这些现在需要分解为不同的实体。这解决了传递性问题：如果记录 t1 是 t2 的副本，并且 t2 是 t3 的副本，那么 t1 也必须是 t3 的副本。这就是说 t1、t2 和 t3代表同一个实体。

此步骤使用图形结构。在该类别中，每条可能是骗子的记录都是一个节点。被怀疑相互欺骗的节点之间有边缘。然后在图中发现集群，然后根据关于一个集群与另一个集群的连接强度的阈值将它们合并在一起。以下是集群对的三个示例，它们可能会或可能不会根据它们的连通性合并在一起：

  c1        c2    

x-x-x-----y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Meets similiarity threshold
|/|\|     |/|\|
x-x-x-----y-y-y    

x-x-x     y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Does not meet similarity threshold
|/|\|     |/|\|
x-x-x     y-y-y    

    x     y
    |     |
    x-----y      Meets similarity threshold
    |     |
    x     y

当算法终止时，每个集群应代表类别中的不同实体。要完成该过程，该实体的属性必须根据其中记录的属性来确定。首先丢弃空值，然后使用包括频率、平均值、中值和最长的方法。

本文还开发了一些在算法不确定时使用领域专家提供帮助的方法，以及如何使用具有不同专业水平的多名专家。