锐眼洞察 | 大规模数据管理系统Data Tamer介绍(翻译)

作者:Michael Stonebraker、Daniel Bruckner、Ihab F. Ilyas、George Beskales、Mitch Cherniack、Stan Zdonik、Alexander Pagan、Shan Xu

原文:Data Curation at Scale: The Data Tamer System

译者:TalkingData数据产品经理 张雪渊

本译文禁止商用,转载请注明来源与译者!

注:

本文翻译自MIT关于Data Tamer的一篇论文,详细信息可查看

摘要

数据管理是发现兴趣数据源,清理、转换新的数据,在语义上将其与其他本地数据源进行整合,并删除重复数据的行为。现在有很多研究内容是针对数据管理的各个组成部分(特别是数据集成和重复数据删除)。但是,甚少有人将所有数据管理组件集成到一个端到端系统。

另外,以前大部分研究都不会扩展到我们在这个领域发现问题的规模。例如,一个Web聚合器需要管理80,000个URL,一个生物技术公司则需要管理8000个电子表格。在这样的规模下,数据管理不可能是手动(人工)工作,而机器学习方法,人工只在必要时给予协助。

本文介绍Data Tamer,是我们在麻省理工(M.I.T)、布兰代斯(Brandeis)、卡塔尔计算研究所(QCRI)建立的端到端管理系统。Data Tamer将一系列数据源添加到随时间构建的复合结构中。新数据源按照机器学习算法以执行属性标识,将属性分组到表格,转换输入数据及重复数据删除。 必要时可寻求人工帮助。此外,Data Tamer还包含数据可视化组件,个人可以随意检查数据来源或者手动指定数据转换过程。

我们已经在三个真实世界的企业管理问题上运行了Data Tamer,结果显示,相比当前使用的其他生产软件,Data Tamer降低了大约90%的管理成本。

1. 介

在数据集成方面已经有相当多的,特别是在提取,转换和加载(ETL)系统,数据联邦,数据清理,数据规格集成和实体重复数据删除。然而,我们相信未来系统将需要的但是现有方法(系统)通常缺乏以下四个特征:

  • 自动化的可扩展性

我们遇到的所有数据整合问题排除了以人为本的解决方案。下一代系统必将是自动化的算法系统,只有必要时才需要人的帮助。另外,机器学习的进步和统计技术的应用可以用来自动做出许多更简单的决定。

  • 数据清理

企业数据源不可避免地很脏。属性数据可能不正确,不准确或缺失。未来的问题需要自动化解决方案,只有在必要时才需要人工帮助。

  • 非程序员方向

当前提取,转换和加载(ETL)系统具有脚本语言适用于专业程序员。下一代问题要求非专业员工能够进行数据整合任务。

  • 数据一直增加

新数据源必须在未发现时逐步集成,数据整合任务从来没有完成的概念。

这四个问题应该在一个统一的架构中解决,我们称之为数据管理系统。 本文的目的是描述Data Tamer,基于上述需求所研发数据管理系统。 在第2节中,我们首先简要介绍Data Tamer设计要解决的三个示例数据管理问题。然后,第3节继续使用DataTamer实现的语义模型,接着在第4节中对系统的主要组件进行描述。最后,第五部分介绍了一系列关于现实世界的问题的实验。我们在第六部分总结了未来可能加强的部分。

2. 应用案

2.1 Web聚合器

这个聚合器集成了大约80,000个URL,收集有关“要做的事情”和事件的信息。事件包括讲座,音乐会和酒吧的现场音乐。“要做的事情”是指远足路线,气球游乐设施,雪地汽车出租等。层级目录概念被用来组织数据,所有的信息存储到这个结构中的某个层级。

从特定URL收集数据的决定是通过与本文不相关的手动和自动组合完成的。一旦决定,离岸“包装代工厂(etl数据处理工程师)”写代码从URL中提取数据。对于在给定的URL处发送的每个实体,封装器会输出一组键值对,例如(key1-name,value-1),(key2-name,value-2),::,(keyK -name,value-K)。不幸的是,源数据很少是web表,但通常在下拉菜单,文本字段等。 因此,网站封装是有价值的。

这个聚合器需要将这8万个数据源联合成一个语义上紧密的事实集合。80,000个数据源包含大约13M本地记录,大约有200K个本地属性名称。另外还有本地的信息可能不一致,重叠,有时不正确。因此,这个聚合器面临着一个困难的数据管理问题,他们使用一个特定的集合来解决这个问题和以人为本的技术。DataTamer的目的是以比现有解决方案更低的成本在这类问题上做得更好。

2.2 生物学

一家大型制药公司拥有8000名生物学家和化学家进行实验室实验。每个人维护一个“实验室笔记本”,通常是一个电子表格,记录他们的数据和观察结果。大多数科学家使用不同的技术和收集实验特定的数据,如浓度和密度。然而,这8000名科学家中的一些可能正在研究相同的反应,或者从同一个分子开始。整合这8000个来源是非常有价值的,所以所有的科学家都可以更好地了解所有实验研究的反应结果。

不幸的是,属性名称没有标准,没有计量单位的标准,甚至没有为文本语言标准(英语,德语等)。

这8000个电子表格总共包含大约1百万行,100000个属性名称。再次申明,问题的规模使当前的数据集成工具过于昂贵。Data Tamer的目标是比目前的软件以更低的成本做更好的工作。

2.3 健康服务应

Verisk Health为索赔记录进行数据集成,共收集了300家保险公司。他们已经为这些资源手动构建了一个全局数据格式,并正在寻找用更多的自动化手段取代他们的手动流程。 另外,他们的综合数据库包含2000万条记录,他们希望统一医疗提供者的索赔数据。 换句话说,他们希望汇总所有的索赔记录,按提供者分组。实际上,他们想要使用域的一个子集重复数据库。他们目前正在通过大量的人工干预来完成这项任务,并寻找一种成本更低,自动化程度更高的解决方案。DataTamer的目的是以比现有解决方案更低的成本获得更好的结果。

3. Data Tamer语义定义

3.1 角色

Data Tamer设置了以下人员角色:

  • Data Tamer 数据管理员(DTA)

这个角色类似于传统的数据库管理员。因此,DTA负责将角色分配给其他人,并决定在数据管理过程中采取什么行动。具体而言,DTA指定DataTamer必须设法收集的数据源。

  • 领域专家(DE)

这些领域专家可以被要求回答在数据管理过程中出现的问题。每个DE都有一个或多个专业领域,他们被组织成一个创新的众包组织,这将在4.3节中解释。

3.2 Sites and Schemas

Data Tamer假设DTA指定的网站由URL或文件名称。每个网站被假定为一个集合记录,每个记录包含一个或多个键值对。上游封装可能需要构造这种格式从网站实际存储的内容 在目前的时间,Data Tamer并不关注如何降低这类包装的成本。

Data Tamer假定每个本地数据源都有关于一个实体的信息。 因此,如果源是多方面的,则必须使用两个或更多的包装来确保每个源包含仅关于一个实体的数据。 如果每个站点都描述一个不同的实体,那么就没有整合的问题。 因此,Data Tamer的目标是将本地站点分为描述同一个实体的类。 在版本1中,没有必要确定实体之间的关系(例如可能存在于RDBMS中的外键)或者处理其他完整性约束。这些扩展留待将来研究。

对于每一类实体,都有三种可能的信息等级。这取决于数据管理是以自上而下的方式进行还是以自下而上的方式进行。在自上而下的模式中,DTA具有关于他试图实现的模式的信息。 因此,目标是部分或完全指定的。 在自下而上的模式中,这样的全球知识不见了,全球模式被拼凑在一起 从当地的数据来源,可能提示从DTA提供。 任何一个模型都可以用于某个特定的类别的事实导致了以下三个层次的信息。、

  • 等级3:完整的知识

在这种情况下,DTA使用自顶向下的方法给定类实体的完整全局数据规格。通常,DTA还将每个本地数据源映射到特定类别。 但是,如果不这样做,Data Tamer将包含自动执行此任务的算法。尽管Verisk应用程序提供了这一级别的知识,但我们发现级别3是在实践中相当罕见。

  • 等级2:部分信息可用

使用自上而下或自下而上的方法,可能会有部分信息可用。某些类别可能存在已知的特定属性的实体。 Web聚合器就是这种情况,因为它需要在其分类层次结构中为每个节点提供特定的属性。或者,可能有模板可用。模板是可能在多个实体类别中的一个中一起出现的属性的集合。例如,美国地址的模板可能是(数字,街道,城市,州,邮政编码)。请注意,模板只是一个复合类型,即通常一起出现的一组属性。 模板可以由DTA指定为“提示”,或者可以通过机器学习来识别如第4节所述。

  • 等级1:没有可用的知识

在这种情况下,类的结构信息和自下而上的整合都是不知道的。这种细节可能是真实的,例如,关于随机的HTML表格,这些表格是从网上抓取的。这就是像Web表格这样的系统的世界。虽然这是生物学应用的知识水平,但我们认为在实践中也是不常见的。

3.3 其他信息

此外,在许多领域,还有标准字典,这些字典应该被Data Tamer使用。字典是一些数据类型的数据值列表,可以填充某些数据源中的属性。 例如,美国有50个州,美国约有3万个城市等。 字典用于指定这些属性的名称和合法值。 有这么多的词典DTA希望指定。

字典被推广到权威的表格。 这些是已知具有正确信息的辅助数据表。 例如,(城市名称,机场名称,机场代码)列表可以是具有三列的权威表格。

此外,数据驯服容纳的同义词表单XXX是YYY。 例如,“工资”是“工资”或“镇“是一个”城市“。 在未来的版本中,我们可以扩展这个能力转化为更一般的本体论。

3.4 管理控制台和Data Tamer操作

网站,类别,模板,词典,权威表格,同义词可以通过一个DATA管理控制台,这是一个相当传统的图形用户界面。

这个控制台的一部分专门用于允许DTA指定Data Tamer执行的操作。 这些行动是:

  • 获取新的数据源,并将传入的数据存储到Postgres数据库中。在当前版本的Data Tamer,这个数据库存在于一个节点上;然而,把这个数据库分割到的多个节点和并行化要描述的算法是非常简单的。
  • 在数据源上执行属性标识,如4.1节所述。
  • 在数据源上执行实体合并,如第4.2节所述。

在属性标识或实体合并过程中的任何时候,Data Tamer都可以请求DE的人员帮助,如4.3节所述。 最后,如第4.4节所述,任何人都可以使用Data Tamer特定接口直观地显示任何数据集。我们可以切换到更复杂的Data Tamer可视化系统[1],从而在那个系统里支持可能的手动转换这个问题将在4.4节中进一步讨论。

在任何时候,DTA可以要求在所有站点上重新进行属性标识和/或实体合并。显然,由于Data Tamer系统中存在更多的站点,这是一个耗时的任务。 但是,更好的决定可能是基于存在的更大量的信息而可用。 因此,如果上面没有指定source-i或source-j,则Data Tamer应该运行要在所有数据源上描述的算法。

最后,Data Tamer保留了所有执行操作的历史记录,DTA可以将策展过程向后回溯到任何过去的历史点,这是通过使用不覆盖更新策略来实现的。

3.5 训练数

在我们与有企业数据管理问题的人的对话中,我们看到了Data Tamer使用两种不同的情况。 第一个适用于知识水平最低或没有先进知识的情况(即第一级和第二级以上)。 在这种情况下,Data Tamer只是最开始使用。最初是非常愚蠢的,必须定期向人们寻求帮助。 后来它变得越来越聪明,所以要求的次数越来越少。而且,由于增加了知识的好处,往往在已处理的网站上返回并运行属性标识和实体解析是很有意义的,可能更好地做出决定。 增加的知识。 因此,训练数据是由Data Tamer的众包组件随着时间的推移而积累起来。

第二个场景涉及更多信息已知的应用程序(上面的第3级)。 在这种情况下,我们观察到现实世界的应用程序通常有可用的培训数据。 具体而言,它们具有“已知重复”的实体和/或属性的集合。换句话说,它们具有已知匹配的本地标识符对的集合。不能保证他们找到了所有的匹配规则。因此,他们提供了一个匹配的属性名称或实体的集合,没有误报。我们已经注意到,提供虚假肯定的危险性在真实问题上很高,所以真实世界的DTA非常谨慎。 因此,他们提供手工收集已知的匹配。

在第一种情况下,我们开始运行Data Tamer系统,适当的时候请求人帮忙。 在第二情景,我们利用已知的重复作为初始训练数据。 我们在第4.2节中提供更多细节。

3.6 数据源更新

最后,一些数据源可能是动态的,并不断更新。在这种情况下,Data Tamer可以创建之前数据源-k的新快照。在这种情况下重新处理数据源是有意义的,因为信息已经改变了。在版本1中,没有接受实时数据反馈的概念。 这样的扩展留给将来的版本。

4. Data Tamer

Data Tamer的架构图如图1所示。图中显示的是管理控制台和规格集成的组件,实体合并,DE 支持和人的转变。 这四个子系统在本节中描述。在这里大部分描述的功能目前能够正常运行运作。

4.1 数据格集成

模式集成中的基本内部循环是从数据源中提取一个属性Ai,并以成对的方式将其与其他属性的集合进行比较。 对于每一对,我们都可以使用属性名称和值的集合。 我们的方法是使用一组算法,我们称为专家,每个算法返回0到1之间的分数。之后,将这些分数与一组权重进行合并以产生合成值。 Data Tamer配备了以下四位内置专家,可以通过简单的API插入其他专家。

  • Expert-1 使用三角余弦相似度对属性名进行模糊字符串比较。
  • Expert-2 将一列数据视为一个文档,用一个标准的全文分析器标记其值。然后,测量列之间的TF-IDF余弦相似度。
  • Expert-3 这位专家使用一种称为最小描述长度(MDL)的方法,使用类似于Jaccard相似性的度量来比较两个属性。 这个度量计算了两列数据交集的大小与它们并集大小的比值。 由于它依赖于属性之间的精确匹配值,因此非常适合分类和有限域数据。
  • Expert-4 最终专家计算韦尔奇的一对包含数值的列的t检验。 给定列的均值和方差,t检验给出列从相同分布得出的概率。

要比较的属性取决于Data Tamer可用的信息级别,如下一节所述。 此外,DTA可以为建议的映射设置一个阈值,从而可以自动采用高度的信任建议,而低的信任映射进入人员审查队列。

4.1.1 属性映射

Data Tamer将要考虑的属性映射取决于手头有哪些可用于处理问题的信息,如3.2节所述。 根据正在检查的级别,使用不同的策略。

  • level3 在这种情况下,Data Tamer知道全局模式,即所有类的实体及其相关的属性。有时,Data Tamer被告知传入数据源所属的类。 在这种情况下,它只能匹配两个属性的集合。 运行规格集成组件的结果是传入属性与全局模式中类的元素的配对。 如果 Data Tamer不确定配对,即匹配得分小于阈值,那么如4.3节所述涉及人。 在其他情况下,必须确定传入实体所属的类别。 在这种情况下,Data Tamer在所有类上运行上述算法,并计算属性的总计匹配分数。 然后选择最好的一个。当然,如果没有足够高的分数,或者如果有两个分数相似的类,那么人就参与决策过程。 应该注意每个传入的属性 该算法到目前为止所看到的属性数量是线性的。 因此,总的复杂度是二次的。 本节稍后讨论可伸缩性问题。
  • level2在这种情况下,Data Tamer可以确定属性的一个子集。 如果是这样,则运行上述算法。如果属性不匹配,则将其添加到模式中 DTA指定的类或算法标识的类。未来的数据源可以匹配更大的属性集合。 复杂性与之相同 3级。 如果模板可用,则考虑任何模板中的所有属性的集合S,以及任何字典名称和同义词.Data Tamer使用两遍算法。 首先,它将所有传入的属性与S的成员进行匹配,只保留得分最高的一个。 在第二遍中,如果其他属性与所选模板中的其他属性相匹配,则将传入属性的分数向上调整。然后,如果阈值高于阈值,则保持匹配。 此外,Data Tamer还会监视传入站点是否收集通常一起出现的属性。 如果是这样,它会自动将集合定义为新模板,并将新成员添加到模板字典中。
  • level1每个传入的属性都与以前看到的所有属性,同义词和词典进行比较。 对于所有级别来说,最坏情况的复杂度是属性总数的二次方。 第一个专家在成对的属性上运行起来非常便宜,因为它不会查看数据。另外三个专家必须检查数据列,而且要昂贵得多。 到目前为止,我们的属性识别算法的运行时间并不是一个惊人的,因为它们运行是“离线”,我们的第一个改进是将它们并行在一个计算机网络的多个节点上,方法是复制Postgres数据库,然后”分割“传入的属性。 这将产生几个数量级的改善。 之后,进一步的运行时间改进将需要两步处理,其中一个属性的子集具有便宜的第一通道和更昂贵的第二通道。 这种两步法将引入额外的专家,其运行时间与属性数据集的大小无关。现在的第一个专家比较属性名称就是一个例子。其他专家将根据属性元数据或从属性数据派生的样本进行比较。可用的元数据包括类型和描述字符串等数据集中的显式字段。尽管明确的元数据可能不可用,但总是可以计算有用的属性属性并将其存储在统计表中。有用的衍生元数据包括计数以及不同值的直方图,推断的数据类型等等。这些统计数据对于为其他专家构建样本也非常有用,例如,计算两个属性的最常用k值的Jaccard相似度的专家。这些首先通过的专家将作为高昂的通行证来处理更昂贵的二次通行证,并节省浪费的时间,几乎没有共同之处。

4.2 实体合并

实体合并有效地建模为重复消除。目标是找到足够相似的实体被认为是重复的。这个模块收到一个集合的记录,R1,: ::,Rn,来自一个或多个本地数据来源增量到达。我们假设这个属性 以前已经进行过鉴定。因此,所有记录具有来自一组属性的属性值A1,:::,Am。一般来说,数据可能会很嘈杂和稀疏的。

重复数据删除过程分为多个任务,我们在下面展示。

4.2.1 导训练过

最初,系统对重复数据删除规则了解不多。我们从已知重复和非重复的训练集中学习重复数据删除规则。我们假设重复的元组通常至少有一个具有相似值的属性。我们获得一组元组对,这些元组对可能会被重复呈现给专家用户,如下所示。设Simi表示属性Ai的值的相似性度量。对于每个属性Ai,我们将Simi的范围划分为若干个等宽分类,并且对于每个分类我们选择与属于这个分类的Simi的元组对的样本。然后将获得的对按属性相似性排序,然后呈现给专家用户进行标记。由于所呈现的对按照属性相似度从大到小的顺序排列,因此专家可以选择停止低于某一相似性阈值的标记对,并将剩余的未看见的对声明为不重复。我们用TP表示被标记为重复的一组对,而我们 用TN表示标记为非重复的一组对。

为了增加候选对中发现的重复项的预期数量,我们只考虑在获得候选项(例如标题,地址和电话)时具有相对大量不同值的属性,同时丢弃其他不太显着的属性 例如城市和州)。 原因是非独特属性之间的高度相似性不会增加重复的机会。

培训数据的另一个重要来源是已知的重复数据,可以在数据集中使用,如前所述。另外,Web聚合器还提供了几个手工制定的规则,用于高精度地识别重复数据。 再次,这是已知重复的来源。 我们使用现有的信息作为正面的训练数据(即TP)。 负面训练数据(TN)更容易找到,因为非重复数据非常频繁。 给定随机的一组元组对,专家用户只需要排除任何高度相似的非匹配对,导致负面的训练数据(TN)。

4.2.2 记录分类

记录分为多个类别,每个类别代表一组具有相似非空属性和相似属性值的同质实体。 那么可能会出现这种情况,例如如果西部的滑雪场看起来不像东部的滑雪场。 例如,两类记录中的垂直落差和基础高程显然是不同的。另外,由于强风的关闭可能通常报告为一个类,而不是另一个。记录分类的好处是双重的:首先,通过学习每个类别特定的重复数据删除规则,我们实现更高质量的规则,可以准确地检测到重复的元组。 其次,我们使用元组分类来减少重复检测算法中需要考虑的元组对的数量。 性能增益与当前用于大数据集中实体分辨率的阻塞技术(例如,[7,14])所获得的性能增益类似。

记录的分类可以使用分类器来完成。 在Data Tamer中,分类分两步实现。在第一步中,我们获得一组代表每个类别的代表性特征。 我们通过对可用来源的元组样本进行聚类来获得这些特征。 我们使用基于质心的算法,如k-means ++ [6]。 类别的数量是通过在引导阶段(第4.2.1节)获得的训练数据TP中的重复数据来确定的。

在第二步中,我们将每个元组分配到最近的类别(w.r.t.到一些距离函数,如余弦相似度)。 虽然类似于实现的性能增益中的阻塞,但这种两阶段分类与先前提出的分块算法是基本不同的,通常通过分簇来执行,索引或排序整个数据集是非常昂贵的操作,我们在分类算法中避免这些操作。

新数据集可用时,元组的分类可能会随时间而改变。我们通过添加新类别和/或在需要时合并/拆分现有类别来维护分类。例如,考虑与其他类别相比,给定类别的半径(由类别的代表性特征与类别的成员之间的最大距离测量)变得非常大的情况。 在这种情况下,我们分裂了 类别分为两个或更多个较小的类别。 有效的增量分类是我们目前的研究方向之一。

4.2.3 重复数据规则

重复数据删除规则分为两种类型:(1)属性相似性的截止阈值,它帮助修剪大量的元组对,如4.2.4节所示; 和(2)重复和非重复元组对的属性相似度的概率分布。我们从收集到的训练数据TP(这样本)和TN(负样本)中学习这些规则。 例如,一个规则表明具有相似的“Title”值的两个元组的概率是相似的,因为它们是重复的。 另一个规则表明,在重复项中具有“State”属性的不同值几乎为零。请注意,学习模块将选择忽略一些对学习重复概率无用的属性(例如,由网页聚合器收集的数据中的“用户评分”)。而且,由于它们在语义上是不同的,因此重复数据删除规则区分了缺失的属性值和不相似的属性值,我们分别了解每个事件的概率。

我们使用一个朴素贝叶斯分类器来获得元组对的属性之间相似性的概率。这个分类器聚合了所有属性的条件概率,以获得重复的边际概率(假设条件对属性的独立性)。

4.2.4 相似度

两个数据集之间的相似性连接的目标是检索所有重复的元组对。一旦获得了重复数据删除规则,如4.2.3节所示,我们执行相似性连接如下。我们获得所有候选元组对,其中每一对属于同一类别,并且至少一个属性具有超过其学习阈值的相似度。然后,我们计算候选对的属性相似度,并根据4.2.3节中学到的分类器使用这些相似性来识别重复记录。相似性连接是逐步执行的,以适应不断添加的新数据源。对于每个新源,我们首先对新源中的元组进行分类,对新元组执行自相似性连接,并在新源中的元组和新元组中进行元组之间的相似性连接。当增加新的训练数据是因为要求人类帮助解决不明确的情况时,我们更新重复数据删除规则,有效识别哪些元组受到这些变化的影响并重新分类。

4.2.5 记录聚合和合

一旦我们获得被认为是重复的元组对的列表,我们需要获得元组的聚类,使得每个聚类代表不同的真实世界实体。对元组进行聚类可以确保最终的重复数据删除结果是可传递的(否则,重复数据删除结果将不一致,例如将(t1; t2)和(t2; t3)声明为重复对,而声明(t1; t3)是不重复的。 我们依赖于[13]中引入的相关聚类算法的修改版本。给定一个相似度图,其节点表示元组,并且其边连接重复的元组对,我们执行如下聚类。该算法以所有单个聚类开始,并且重复合并随机选择的具有高于某个阈值的“连接强度”的聚类。我们将两个聚类之间的连接强度量化为跨越两个聚类的边缘的数量 即,两个群集的笛卡尔乘积)。当没有更多的集群可以被合并时,该算法终止。

当基础相似性图变化时(即,新的边和/或现有的边被删除),我们更新聚类如下。 我们确定图中所有与任何修改边相关的节点。 包含任何这些节点的簇被分割成单个簇。然后,我们在新的单个簇上重新应用相同的合并操作。

每个群集中的元组使用用户定义的规则进行整合。 首先丢弃空值,然后使用标准聚合方法(如Most-Frequent,Average,Median和Longest-String)来组合每个集群中元组的属性值。

4.3人机界面

在属性识别阶段和实体整合阶段,DTA可以要求DE(领域专家)提供输入。在属性标识的情况下,任务是确定两个属性是否相同。 在实体解决的情况下,任务是确定两个实体是否重复。 Data Tamer处理的两种情况将在后面两节中介绍

4.3.1 模式

如果需要人工干预的任务很少,或者只有几个DE,那么DTA可以手动将人工任务分配给DE。他这样做是通过使用一系列规则来规定应该发给特定个人的问题类别。或者,他可以手动分配任务。 在这两种情况下,人工请求的路由由DTA以最少的基础设施完成。

但是,如果问题很多,或者由于需要时间的差异,或者如果有很多DE来处理大量的问题,那么就应该采用更复杂的人群采购模式。 Data Tamer实现了下一节讨论的模型。

4.3.2 众包模式

大规模的数据管理可能需要招募更多专业知识较少的领域专家(DE)来帮助解决工作量。这些 DE可以被要求完成“简单”的任务,或者可以被众包来产生更高的正确性的结果,而不是任何一个人都可以假设的结果。 但是,大量多样化的DE人口需要解决以下几个问题:

  • 响应质量的确定。 当一项需要人工干预的任务被转交给一位专家时,可以认为所得出的答案是准确的。 但是一个由多个DE来解决的任务 可变的专业知识可能会导致质量变化的多重反应。 因此,由一组DE返回的一组不同的响应应该伴随着一个概率分布,它反映了每个响应中的总体置信度是正确的。
  • DE领域专业知识的确定。 对任务的每一个不同的反应的意见必须是那些给出这个回答的DE的给定任务领域的专业评级的函数。 这对如何表征和确定领域专业知识带来了挑战。
  • 有用和及时的DE响应的动机。 考虑到DE人口的多样性,个人DE的反应和反应会有所不同。 这里的问题在于如何鼓励DE成为优秀的公民来应对任务。
  • DE工作量的管理。 DE不仅具有变量领域的专业知识,而且具有可变的可用性回应任务。 因此,管理工作量是必要的,因为考虑到工作量的限制,使得DEs既没有负担过重,也没有充分利用。

我们已经建立了一个工具(Data Tamer Exchange或DTX),它作为一个基于市场的专家交换,帮助将需要人力投入的任务与可以提供它的个人或众包的DE相匹配。 DTX假定属性标识或实体解析问题的集合,必须经过验证或驳斥。 对于每个这样的任务,该工具显示一个DTA有多少个DE可用 与任务域相关联的某些特定专家类中的每一个,以及响应的成本和质量将如何根据每个类的多少DE来响应。

DTX的主要特点如下:

  • DE和响应的基于信念的度量。

DTX为每个DE都保留了一个基于信心的专业评估向量 在一组指定的领域中的每一个领域都具有专业知识的程度 由DTA。每个评级是介于0和1之间的值,表示DE对关联域中的任务产生正确响应的概率。DE对特定领域的专业评级是由其他更专业的DE和来自请求应答的DTA在该领域的每个回答所作的评估计算出来的。 使用类似的基于信度的度量来度量响应的质量(即响应正确的概率)。众包产生了一系列响应(TRUE或FALSE),并且使用贝叶斯证据收集(Bayesian Evidence Gathering)从投票选择的响应者的专业评级中收集每个投票的质量评级。更具体地,给出具有专业知识的n个响应者的问题 等级〜E和响应〜R,给定响应b的累积置信度为:

使得B和B是分别表示事件的随机变量,其中响应b分别是正确的和不正确的答案,或者是随机变量(X),使得上面的子产品是正确响应者正确的组合概率(Ri = X),不正确的响应者不正确(Ri != X)。

  • 专家类。

DTX根据DE在该领域的专业知识评级将DEs动态聚类为领域特定的专家类。例如,一个给定领域中最专业的DE可能被分配到专家级别#1的专业评级为0.9或更高。 当一个任务被提交给 DTX,工具通过呈现关于任务领域中的每个专家类别的统计信息,包括DE的数量,每个DE响应的成本(专家评级更高的类别,每个响应更多的类别)以及类别内的DE的最小专业评级。 在这个基础上,一个DTA决定每个级别,他将支付多少(如果有的话)个DE。

  • 对良好公民的经济激励。

DTX假定一个经济模型,由DE获得的回报是相称的与他的专家级。答复付款来自提供完成任务预算的DTA帐户。 系统向DE(与响应相同的速率)和DTA提供对DE响应评价的付款 (他们的工资被加到他们的预算中)。

  • 动态定价来管理工作量。

DTX动态调整每个响应所支付的价格 在每个专业水平,以鼓励选择 未被充分利用的DE和阻止选择 负担过重的DEs。

经济模式有助于解决大规模的两个问题:

1、鉴于可能会审查答复,DEs是激励 提供有用和及时的回应,以获得更高的专业评级,从而获得更高的薪酬。 2、鉴于DTA被分配了一个固定的预算来完成他们所有的任务,他们被激励尽可能少地花费在DE响应上。 通过鼓励DTA根据自己的困难对任务进行分类,并且征求最不专业(因此也是最便宜的)响应具有最低限度可接受的信心的响应,这有助于减轻专家DE的责任。

此外,对于评论的支付, 有助于确保信任评级的准确性 DE的专业知识和回应。

4.4

在任何时候,DTA或DE都可以调用我们的可视化 系统并将本地数据源传递到该系统。 它在屏幕上显示数据源(或源代码示例)。 人可以检查数据源的洞察力。

我们可能会将可视化系统切换到Data Wrangler访问他们的提取,转换和加载(ETL)运营。 这样一个Data Tamer用户可以手动应用Data Wrangler转换并转换数据类型和格式。 在这种情况下,我们可以记住应用转换并将其转换为数据图类型。 如果我们看到未来的数据类型,我们可以申请自动转换。 允许DTA “跟踪”的数据,我们总是采用一个不覆盖更新Postgres数据库中的数据策略。

或者,我们可以实现一个Data Tamer特定的可视化界面。通过这种方式,屏幕组件可以根据数据控制器的需求进行调整。 例如,实体合并系统想要显示可能的匹配簇和模式匹配器想要显示列来自可能匹配感兴趣属性的多个本地数据源。 Data Wrangler中不包含任何功能。

5. 实验验证

我们在网络使用的数据上运行Data Tamer系统在第2节中描述的聚合器。对少于50个人工标记的来源进行适度的培训后,我们的自动系统在90%的时间里成功地识别了正确的属性映射。整体成功取决于个人专家的结果。在80%的时间内,属性名称匹配成功,MDL为65%,模糊值匹配为55%。 由于汇总者的数字列(邮政编码和纬度/经度)很少,T检验专家只提供少于6%的属性的结果,但其结果在65%的案例中是正确的。 专家互相恭维:至少有一位专家为95%的属性确定了正确的映射。

聚合器 Data Tamer
总记录数 146690 146690
重复数据 7668 180445
共同重复数据 5437 5437
所有的重复数据(估计) 182453 182453
准确度 97% 100%
召回率 4% 98.9%

图2:Web聚合器数据实体合并的质量结果

我们使用一套评估我们的实体合并模块的50个数据源。 平均而言,每个数据源都包含 4000条记录,需要160秒才能进行重复数据删除并集成到中央数据库(使用一台机器)。 统计有关发现重复对在50数据源总结在图2中。我们比较了我们的结果到当前重复数据删除找到的重复对网络聚合器使用的算法。 总数数据源中的记录数是146690,Data Tamer报告了180445个重复对,而聚合者的算法只报告了7668个重复对。该聚合者报告的常见对的数量算法和Data Tamer者是5437。

我们假设两个算法均对是真实的重复。另外,我们假定这两个算法都没有报告是真实的非重复的。我们通过要求领域专家检查100对样本来评估剩余对(即一个算法报告的对,而不是另一个)的准确性。根据专家的反馈,90%的网络聚合器报告但是DataTamer 没有报告的是真实的重复,另外,所有的DataTamer 报告的重复,但是网络聚合器没有报告的数据也是真实的重复。因此,汇总者报告的真实重复(估计)数量为5437+(7668-5437)* 0.9 = 7444。报告的真实重复的数量 通过Data Tamer是5437 +(180445-5437)* 1.0 = 180445。数据集中真实重复的总数是5437+ (180445-5437)* 1.0 +(7668-5437)* 0.9 = 182453。Data Tamer的精度为180445/180445 = 100%,聚合器精度为7444/7668 = 97%。Data Tamer的召回率为180445/182453 = 98.9%,而聚合器召回率为7444/182453 = 4%。这些结果清楚地表明,我们的实体合并模块能够显着提高现有重复数据删除算法的召回率,同时保持相同的精确度水平。

我们还在2.2节讨论的生物学问题上运行了模式识别系统。Data Tamer成功映射了86%的属性。最后,我们在Verisk上运行了实体合并模块 医疗索赔数据集。 图3显示了成对记录对在成对相似性上的各种截止阈值的质量。我们将阈值范围[0,1]划分为10个等宽的子范围,并且从每个子范围获得15对的样本。我们依靠领域专家将抽样对分为真实重复和真实非重复。我们计算了每个相似性阈值(图3)的精度,召回率和F1-度量。 为了对这些结果进行透视,我们计算了Verisk使用的当前重复数据删除算法的准确性。 该算法的精度为12%,召回率为30%,F分数为17%。 另一方面,我们的算法在0.8的阈值处归档65%的F分数。

图片 1

图3:Verisk数据实体合并的质量结果

为了评估用户对我们众包交换的接受程度,我们正在对生物学数据进行两步评估之前提到。 该公司计划在他们的整个生物学问题上运行Data Tamer,拥有数百位专家作为他们的群体采购部分。作为第一步,他们想要做一个“空转”,以确保系统正常工作。 因此,他们要求33位领域专家参与系统的测试。 我们使用Data Tamer对其一部分集成问题执行模式映射。 为了验证Data Tamer的映射,我们使用DTX的专家工作者分配算法为33位专家分配了总共236个模式匹配任务。 在每个任务中,用户被要求将Data Tamer的建议匹配标记为True或False,如果是False,则建议替代匹配。 平均而言,每项任务被重复分配给2名专家。 这导致每个用户平均有7个任务分配。

在这个测试中没有给予用户经济激励,测试参与是自愿的。 在我们联系的33位专家中,有18位(54%)登录了系统。 每位登录用户都执行了所分配的任务。 总共,236项任务中有113个任务被完成,64%的任务至少收到一个响应。 自愿回应率低意味着需要通过经济激励对及时的回应给予奖励。完成指定的任务后,我们要求每个参与者以1到3分的来评估系统的可用性。用户给出的平均得分是2.6。

该公司正在在数百个领域专家的帮助下进行全面的系统测试。 我们计划按域分组数据源,然后将这些数据源中的每个用户的数据录入历史记录,来确定适当的初始域专业知识水平。 例如,如果用户是特定域中的数据源的创建者,那么在确定任务的正确答案时,该用户的响应可以比在那个域中没有输入数据的用户的响应更重。 我们期望在不久的将来报告这项研究。

6. 未来增的点

我们在本节讨论的增强功能,在论文的正文中我们指出了各种各样的未来要改进的部分。首先,我们期望并行化所有的Data Tamer算法,让它们可以运行在分裂和/或复制Postgres数据库或针对其中一个并行SQL DBMS。 鉴于许多算法都是通过SQL实现或用户自定义功能,这个扩展很简单。

格式集成模块可能需要加速通过使其成为如前所述的两步算法。 另外,我们还没有有效地考虑机制重做格式集成。由于我们的格式集成算法本质上是顺序敏感的,因此完全有可能在不同的结果下观察到不同的结果网站排序,因为这样一个有效的重做将是必需的特征。

我们的实体整合方案需要增量化,因此所有的子任务都可以在每个新的数据源被整合时和/或添加新的训练数据时被有效地运行。 而且,这个资源密集型模块的并行化将是特别理想的。

到目前为止,Data Tamer中唯一的数据清理操作是在实体合并系统中。 每当有多个记录对应一个实体时,我们都可以自动或在人工协助下生成一个干净的结果。虽然这是一项有价值的服务,但我们需要实施一个特定的清洁组件。 不幸的是,数据清理往往依靠异常值检测或清理的集合规则。 离群值不一定是错误;例如-99是通常用于指示数据丢失。 因此,找到一个在这种情况下,异常值相当于找到缺失值。另外,大多数清洁规则是非常复杂的,如果他们是有用。虽然很容易陈述年龄和薪水必须是非负面的,要说明这一点要困难得多。如果是冬天,靠近窗户的温度应该低于靠近散热孔的温度。 我们期望在不久的将来能够在这个组件上开展工作,并以用户在实践中实际发挥作用为指导。

同样,我们还没有系统地处理数据转换,例如转换本地数据相同的表示法,转换单位或将属性转换为通用含义(例如,不含销售税的价格)。我们的方法是维护Data Tamer数据类型的图表。每当用户练习可视化系统进行转换时,我们计划在图形中将其记为弧。 显然,用户应该能够用相应的代码添加弧来实现转换。 这个图可以用来在可视化引擎中建议转换。

7. 结论

本文介绍了Data Tamer的主要特点,即规格集成组件、实体整合组件、组织领域专家的众包模块及可视化组件。 将来,我们将添加更多的模块来执行数据清理和重复转换。

该系统已被证明对三个企业有价值。 目前,代码已被三家公司采用。

8. 参考资料

[1] http://vis.stanford.edu/wrangler/.
[2] http://www.compositesw.com/solutions/datafederation/.
[3] http://www.ibm.com/software/data/integration/.
[4] http://www.informatica.com/etl/.
[5] http://www.talend.com.
[6] D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, pages 1027–1035, 2007.
[7] R. Baxter, P. Christen, and T. Churches. A comparison of fast blocking methods for record linkage. ACM SIGKDD, 3:25–27, 2003.
[8] M. J. Cafarella, A. Y. Halevy, D. Z. Wang, E. Wu, and Y. Zhang. Webtables: exploring the power of tables on the web. PVLDB, 1(1):538–549, 2008.
[9] S. Chaudhuri, V. Ganti, and R. Motwani. Robust identification of fuzzy duplicates. In ICDE, pages 865–876, 2005.
[10] L. Chiticariu, M. A. Hern´andez, P. G. Kolaitis, and L. Popa. Semi-automatic schema integration in clio. In VLDB, pages 1326–1329, 2007.
[11] P. Christen and T. Churches. Febrl. freely extensible biomedical record linkage, http://datamining.anu.edu.au/projects.
[12] A. K. Elmagarmid, P. G. Ipeirotis, and V. S. Verykios. Duplicate record detection: A survey. IEEE Trans. Knowl. Data Eng., 19(1), 2007.
[13] C. Mathieu, O. Sankur, and W. Schudy. Online correlation clustering. In STACS, pages 573–584, 2010.
[14] A. McCallum, K. Nigam, and L. H. Ungar. Efficient clustering of high-dimensional data sets with application to reference matching. In KDD, pages 169–178, 2000.
[15] T. M. Mitchell. Machine learning. McGraw Hill series in computer science. McGraw-Hill, 1997.
[16] E. Rahm and P. A. Bernstein. A survey of approaches to automatic schema matching. VLDB J., 10(4):334–350, 2001.
[17] V. Raman and J. M. Hellerstein. Potter’s wheel: An interactive data cleaning system. In VLDB, pages 381–390, 2001.

发表评论

电子邮件地址不会被公开。 必填项已用*标注