中国人工智能学会通讯——一种基于众包的交互式数据修复方法 3 给定质量约束下的交互式算法-阿里云开发者社区

开发者社区> 人工智能> 正文

中国人工智能学会通讯——一种基于众包的交互式数据修复方法 3 给定质量约束下的交互式算法

简介:

3 给定质量约束下的交互式算法

为了生成一个有效的交互式方案,我们提出了自己的算法,其中的关键问题是在众包修复过程中如何选择被众包修复的值。

首先,我们倾向于选择引起数据冲突最多的值进行众包修复,这样就会有更多的值在下一步的基于规则的修复过程中可以被推导。为了找出引起数据间冲突最多的值,先评估每个值的不和谐度disharmonious degree(简称为dScore),表示这个值和数据集中其他所有值之间的不和谐度。将在3.1节中介绍如何计算每个值的dScore。

image

虽然是在一个动态情况下安排冲突的修复顺序,仍可以根据冲突之间的依赖关系,决定修复哪些值。在这一过程中,面临的挑战就是如何解决冲突间的依赖循环问题,我们将在3.2节中讨论这个问题。

3.1 dScore: 衡量值的不和谐度

一个值的不和谐度可以粗略地由它所引起的冲突的个数来表示。首先用一个简单的例子介绍一下如何计算每个值的dScore。首先,假设除了某个位置上的值,整个数据集都是一致的,即数据集上的其他所有值都是和谐的。然后,当该位置上的值出现后,可能会引起两种冲突:①该值本身和一些值发生了冲突;②该值使得某个冲突里的其他值发生了冲突。通常一个值带来的冲突越多,这个值越有可能是一个错误的值。换句话说,在这种简单的假设下,一个值的dScore就是它所引起的冲突的个数。

现在开始考虑实际情况,即数据集中已经存在错误的值和冲突。当一个新值出现时,不管它是否错误,都会带来一些改变,如产生新的冲突或者加剧已有的冲突。在这种情况下,一个值的dScore由以下两部分组成:

image
image

3.2 使用冲突之间的依赖关系

在安排冲突的修复顺序时,我们会考虑冲突间的依赖关系。首先要获得所有冲突之间的依赖关系,然后根据这些关系建立一个冲突依赖关系图。

image
image
image
image

正如之前介绍的,一个冲突只有在它所依赖的所有冲突都被解决之后,这个冲突才可以被解决。但是对于那些在同一个节点里面相互重叠的冲突,需要考虑冲突里的值被检测的优先顺序。同样,我们根据这些值的dScore来确定检测的顺序。一个值的dScore越高,这个值越先被检测。每次当有一个值被修改了,整个关系图就需要随之更新。

3.3 解决依赖环

image
image
image
image
image

3.4 考虑依赖关系的交互式算法

交互式算法如算法1所示。首先要为数据集建立一个冲突依赖关系图。不考虑其他因素,只选择每个节点中dScore最高的值进行众包修复,直至节点中的所有冲突都被解决。当没有这样的节点只有环时,计算这些环中所有节点的gbScore,选择gbScore最高的节点进行处理从而分裂环。每次只要有一个值被修改,关系图、所有节点的bScore和gbScore都需要及时更新。当整个依赖关系图中没有一个节点时,算法就会结束。算法1的时间复杂度是O(mlogm+n),m是依赖关系图中所有环中的节点个数,n指图中不在环内的节点个数。

image
image
image
image
image

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章