Truth Discovery from Conflicting Data: A Survey

With the rocketing progress of the Internet, it is easier for people to get information about the objects that they are interested in. However, this information usually has conflicts. In order to resolve conflicts and get the true information, truth discovery has been proposed and received widespread attention. Many algorithms have been proposed to adapt to different scenarios. This paper aims to investigate these algorithms and summarize them from the perspective of algorithm models and specific concepts. Some classic datasets and evaluation metrics are given in this paper. Some future directions for readers are also provided to better understand the field of truth discovery.

Cleaning of Multi-Source Uncertain Time Series Data Based on PageRank

There are errors in multi-source uncertain time series data.Truth discovery methods for time series data are effective in finding more accurate values,but some have limitations in their usability.To tackle this challenge,we propose a new and convenient truth discovery method to handle time series data.A more accurate sample is closer to the truth and,consequently,to other accurate samples.Because the mutual-confirm relationship between sensors is very similar to the mutual-quote relationship between web pages,we evaluate sensor reliability based on PageRank and then estimate the truth by sensor reliability.Therefore,this method does not rely on smoothness assumptions or prior knowledge of the data.Finally,we validate the effectiveness and efficiency of the proposed method on real-world and synthetic data sets,respectively.

Truth Discovery on Inconsistent Relational Data

In this era of big data, data are often collected from multiple sources that have different reliabilities, and there is inevitable conflict with respect to the various information obtained when it relates to the the same object.One important task is to identify the most trustworthy value out of all the conflicting claims, and this is known as truth discovery. Existing truth discovery methods simultaneously identify the most trustworthy information and source reliability degrees and are based on the idea that more reliable sources often provide more trustworthy information,and vice versa. However, there are often semantic constrains defined upon relational database, which can be violated by a single data source. To remove violations, an important task is to repair data to satisfy the constrains,and this is known as data cleaning. The two problems above may coexist, but considering them together can provide some benefits, and to the authors knowledge, this has not yet been the focus of any research. In this paper, therefore, a schema-decomposing based method is proposed to simultaneously discover the truth and to clean the data, with the aim of improving accuracy. Experimental results using real world data sets of notebooks and mobile phones, as well as simulated data sets, demonstrate the effectiveness and efficiency of our proposed method.

移动群智感知中高效可验证的安全真值发现方法

针对移动群智感知中参与者数据的真值和隐私保护问题,提出了一种高效可验证的安全真值发现方法 EVSTD,通过安全迭代更新参与者权值和评估对象真值,从而得到对象的真实数据。EVSTD中,参与者利用本地随机数和协商随机数对敏感数据进行双掩码数据扰动,使得EVSTD不仅能够保证敏感数据的隐私性,且解决了参与者因延迟发送感知数据而导致的敏感数据泄露问题。同时, EVSTD利用秘密共享协议解决了参与者掉线或失效的问题,且通过动态选择L邻居节点策略让参与者只与其关联邻居进行通信从而大大降低了参与者的计算和通信开销。此外,参与者通过计算敏感数据的同态哈希值以用于数据的验证并上传给服务器,服务器对敏感数据进行聚合和对验证信息进行乘积,并将计算结果发送给参与者,参与者再对聚合结果和证明信息进行验证,验证通过则说明聚合结果正确,进一步保证了真值发现结果的可信性,防止服务器对参与者的敏感数据进行篡改,保证了聚合结果的真实性。实验结果显示所提方法在保证数据隐私的同时获得真实可靠的数据信息,且能够有效的防止服务器篡改数据和共谋攻击。

一种基于变分多跳图注意力编码器的深层协同真值发现

大数据时代,数据价值的释放经常需要融合多源数据,数据冲突成为这一过程中无法避免的关键问题。为了从冲突数据中筛选出真实声明以及可靠数据源,研究人员提出了真值发现方法。然而,现有的真值发现大多注重数据源与声明之间的直接协同信息,忽略了更深层的间接协同与对抗信息,导致不足以表达出数据源与声明的特征。针对此问题,提出了基于变分多跳图注意力编码器的真值发现方法(TD-VMGAE),基于数据源与声明之间的包含关系构建二分图网络,采用多跳图注意力层为每个节点表征汇聚间接协同信息以及对抗信息,并设计真值发现变分自编码器,抽取节点表征中所需的分类分布,对数据源和声明进行协同分类。实验结果表明,所提方法在3个不同尺度的数据集中均有不错的表现,消融实验和可视化也验证了所提方法的有效性和泛化能力。

基于本地差分隐私的众包数据流真值发现方法

真值发现是解决多源数据冲突的手段,但在迭代计算的过程中会泄露隐私数据。因此,本地差分隐私以其强大的隐私保证在真值发现中得到了广泛应用。然而,现有多数研究均基于某一时刻对数据进行隐私保护。若对数据进行持续收集,可能忽略所要求的规模大、连续到达等特性。针对众包任务持续数据收集中的真值发现问题,文章提出了基于本地差分隐私的持续数据真值发现机制,同时考虑工人数据和真值之间的相关性,在保护用户数据隐私的同时降低了真值估计的误差。

基于多特征融合的无监督真值发现方法

真值发现是数据集成领域具有挑战性的研究热点之一。传统的方法利用数据源与观测值之间的交互关系推断真值,缺乏足够的特征信息;基于深度学习的方法可以有效地进行特征抽取,但其性能依赖于大量手工标注,而在实际应用中很难获取到大量高质量的真值标签。为克服以上问题,本文提出一种基于多特征融合的无监督真值发现方法(Unsupervised truth discovery method based on multi-feature fusion,MFOTD)。首先,利用集成学习无监督标注“真值”标签;然后,分别使用预训练模型Bert和独热编码获取观测值的语义特征和交互特征;最后,融合观测值多种特征并使用其“真值”标签构建初始训练集,通过自训练方式训练真值预测模型。在两个真实数据集上的实验结果表明,与已有方法相比,本文所提出的方法具有更高的真值发现准确性。

基于胶囊网络的文本数据真值发现

为解决传统真值发现算法无法提取文本数据关键语义信息的问题,提出一种基于胶囊网络的文本数据真值发现算法(Truth Discovery of Text Data Based on Capsule Network,Caps-Truth),对传统卷积神经网络(Convolutional Neural Network,CNN)进行改进,在神经网络模型中构造语义胶囊层替代CNN池化层表征文本语义信息。首先通过CNN卷积层获取文本数据全局特征,利用初级胶囊层将特征信息向量化,再通过语义胶囊层表征文本数据细粒度语义信息,将特征向量输入全连接神经网络挖掘文本数据可信度并获得可靠答案。上述算法在真值发现中引入胶囊网络,利用动态路由算法整合零散语义,有效提高了文本数据真值发现的效果。实验结果表明,Caps-Truth算法优于对比算法。

不一致数据最大概率子集修复算法

针对关系型数据中的不一致错误,现有子集修复方法通常以最小删除元组数量为优化目标求解最优修复方案,以减少对原始数据的更改。但当数据中的错误较多时,该方法的准确率将降低。提出了一种最大概率子集修复方法,利用属性之间的关联关系及概率统计信息对元组的正确性概率进行建模,将最小删除元组的正确性概率之和作为优化目标进行最优子集修复,并给出了高效的最大概率子集修复近似算法。真实数据集和合成数据集上的实验结果表明,最大概率子集修复方法的准确率优于当前最好方法。

基于数据依赖的数据修复研究进展

介绍了数据依赖理论及如何基于数据依赖修复不一致数据,提高数据质量。首先介绍了数据依赖理论;给出了数据修复的语义假设及对应的修复操作;总结了基于数据依赖修复不一致数据的方法;最后讨论了基于数据依赖修复不一致数据的未来发展方向。

面向Web数据集成的真值发现算法

在Web数据集成中,常出现多个数据源对同一实体对象的描述存在冲突.解决冲突,发现真值有助于提高数据集成质量或构建高质量的知识库等.已有的解决单真值数据冲突的方法存在数据源评价指标不充分,无法区分数据源的数据缺失和假真,以及无法处理数据源间传递复制、共同复制等高阶复制的局限性.因此,本文采用召回率和假真率度量数据源质量,提出能处理数据源间复杂数据复制的真值发现算法.三个真实数据集和人工数据集上的实验结果表明,本文算法能有效降低错误数据复制带来的真值计算偏差,提高真值发现的准确率.

基于数据源分类可信性的真值发现方法研究

网络的普及和电子商务的发展改变了人们信息获取以及消费的方式.Web已经成为大多数人获取信息的重要来源.与此同时,互联网信息质量问题也逐渐凸显.Web中存在大量过时、错误、虚假、片面的信息.其中,不同网站为相同对象提供冲突信息的问题尤为突出.如何从这些冲突信息中找到正确信息成为亟待解决的问题,这类问题又被称为真值发现问题.通过对现有真值发现问题解决方法的调研,发现现有方法均未考虑数据源分类可信性差异对真值发现的影响.因此,提出基于数据源分类可信性的真值发现问题.提出2种方法探测数据源分类可信性差异,并采用贝叶斯的方法迭代计算数据源分类可信性和属性值准确性.另外,通过考虑数据源覆盖率和对象难度对真值发现的影响,进一步提高真值发现算法的准确性.一个真实数据集的实验结果表明,所提方法可以显著提高真值发现的准确性.

一种高效的大数据增量真值发现算法

针对多源异构大数据中传统真值发现算法可扩展性不足、增量真值发现效果差等问题,本文将Map-Reduce框架和贝叶斯真值发现模型相结合,提出了基于Map-Reduce的并行真值发现算法;在MPTF算法基础上,引入Incoop增量框架和基于投票机制的分类器集成策略,并优化了Map过程和Reduce过程,提出了一种高效的大数据增量真值发现算法;实验表明:该算法不仅提高了分类器的准确性,而且实现了新增数据源的真值发现。通过理论分析和实验对比证明,该算法具有高效性和广泛适用性,同时可以兼顾多种现实中的复杂情形。

基于代价模型的不一致XML数据修复启发式计算

在实际应用中,为不一致的XML文档计算最优修复意义重大.但求解最优修复是一个NP完全问题,特别是在XML文档同时违反函数依赖约束和主键约束时.提出一个基于代价模型的、可以在多项式时间内完成的启发式修复求解算法.该算法首先借助索引表,在一遍扫描原始XML文档的情况下寻找不一致数据集,然后为每一类约束的不一致数据集构造候选修复,同时计算其修复代价,最后启发式地求解一个代价最小的修复方案.实验结果表明,该算法的时间复杂度不超过冲突类的3次方,即便是在不一致数据量很大、噪声比例很大以及涉及多类语义约束时,也能较快地完成修复.

利用属性集相关性与源误差的多真值发现方法研究

目前真值发现的研究主要利用数据源质量和数据之间的关系,然而实际数据的分布呈现长尾现象,传统算法在处理尾部数据时,准确率大大下降.本文对数据源进行分类,对头部数据源利用属性集相关性,给予正确集更多的置信度补偿,易于剔除错误数据;对尾部数据源,根据误差小的数据源应获得更高的权值分配的理论,将真值发现转化成全局优化问题,通过寻求数据源权值的最佳分配,获得最可能接近真值列表的属性集合.实验表明,本文提出的方法在真实的长尾数据集上,准确率和召回率方面均优于传统算法.

面向学术资源集成的真值发现算法

在构建多渠道元数据资源建设体系时,往往存在着大量的元数据冲突的问题,即对同一对象的属性存在多种描述,造成了元数据的组织与揭示的困难。本文处理的原则是遵从原文,优先选取原文的值作为唯一的真值,将数据冲突问题视为单真值冲突问题。考虑到数据提供商均需要加工数据,将数据源之间的关系视为相互独立。根据以上,本文提出了一种面向学术资源集成的真值发现算法。该算法基于贝叶斯算法,考虑了有关联关系的属性。实验证明本文方法所构造的真值发现算法在保证准确率的同时,大大节省了人力的工作时间。

基于非一致性数据库的概率查询策略与算法

完整性约束是保证关系型数据库中数据确定性的重要条件,现实中存在大量不确定、不满足完整约束条件,但仍具有使用价值。结合概率数据库理论,提出了一种新的针对非一致性数据库的查询策略,利用并、交、差、选择、投影、连接等约束方法,对非一致性数据进行修复,四元组概率计算方法和概率查询重写技术弥补了非一致性数据库查询的不足,减少了数据冲突的发生机率。

一种多源感知数据流上的连续真值发现技术

真值发现作为整合由不同数据源提供的冲突信息的一种手段,在传统数据库领域已经得到了广泛的研究.然而现有的很多真值发现方法不适用于数据流应用,主要原因是它们都包含迭代的过程.针对一种特殊的数据流——感知数据流上的连续真值发现问题进行了研究.结合感知数据本身及其应用特点,提出一种变频评估数据源可信度的策略,减少了迭代过程的执行,提高了每一时刻多源感知数据流真值发现的效率.首先定义并研究了当感知数据流真值发现的相对误差和累积误差较小时,相邻时刻数据源的可信度变化需要满足的条件,进而给出了一种概率模型,以预测数据源的可信度满足该条件的概率.之后,通过整合上述结论,实现在预测的累积误差以一定概率不超过给定阈值的前提下,最大化数据源可信度的评估周期以提高效率,并将该问题转化为一个最优化问题.在此基础上,提出了一种变频评估数据源可信度的算法——CTF-Stream(continuous truth finding over sensor data streams),CTF-Stream结合历史数据动态地确定数据源可信度的评估时刻,在保证真值发现结果达到用户给定精度的同时提高了效率.最后,通过在真实的感知数据集合上进行实验,进一步验证了算法在处理感知数据流的真值发现问题时的效率和准确率.

基于HITS的冲突Deep Web数据多真值发现算法

目前多数真值发现算法建立在真值唯一的基础上,无法处理多真值的情况。为此,针对冲突Deep Web数据的多真值发现问题,借鉴HITS算法思想,定义视图权威度与视图描述可信度,两者相互影响。在此基础上,定义视图链接关系图,提出多真值迭代发现算法MTF。当算法收敛时,权威度最大的视图就是真值。在Book-Authors数据集上进行实验,结果表明,与基准算法VOTE相比,MTF算法的精确度大幅提高。

概念聚类挖掘方法的客户交易行为分析

本文首先介绍数据挖掘的相关概念 ,再给出一个在证券行业应用的系统。该系统采用概念聚类的挖掘方法 ,从客户的交易行为中提取有价值的信息 ,发现影响客户盈亏的一般性规律。