多源数据的真值发现算法Python实现
摘要：随着互联网技术的发展，信息的传播和访问变得更加方便。万维网带来越来越多的信息源，同时也带来信息源的真实性和及时性问题，其中，不同网站为相同对象提供冲突信息的问题尤为突出，例如，不同图书网站为同一本书提供了不同的作者信息，不同网站对珠穆朗玛峰的高度值不一致等等这类问题，这些冲突信息可能由于输入错误，信息过期，语义理解不一致，抽取程序错误等各种原因造成，给用户带来误导甚至造成巨大损失。如何从这些冲突信息中找到正确信息成为亟待解决的问题，这类问题被称为真值发现问题。为了解决多数据源冲突的数据真值发现，近年来许多研究者提出相关算法。本文对典型的TruthFinder[1]、CRH[2],KDE[3]、KDEm[4]等进行分析，然后通过实验对它们的准确性进行比较，继而得出相关的性能趋势图。为相关的真值发现应用，比如无线传感器应用、移动群智感知等，打下良好的基础。
关键词：TruthFinder、KDE、KDEm、CRH、真值发现、数据冲突、数据源分类可信性
一、引言：
- 研究目的和意义：
冲突是组织程序过程中经常出现的一种普遍现象, 实质上是两个或两个以上的相互依赖的个体间的一种互动关系。信息冲突指拥有信息所有权和信息使用权的双方因对信息占有、使用、销售、转让等信息运行过程存在的认知和诠释差异而构成的冲突行为。有差异就有冲突。随着知识超越物质和能量成为生产力发展最重要因素这一变化的出现, 现代社会的文明和可持续发展几乎可以说是知识的认知、使用、占有、生产和制造的循环过程。因而参与知识循环过程的各方为了充分保护既得信息、并利用既得信息创造比物质生产利润更大的收益, 在对信息的认知和诠释出现差异, 而这种差异又使自身现时或未来收益损失扩大时, 不得不直面信息引起的冲突，则要进一步分析真值发现问题，研究真值发现算法，获取最有效的信息源。为了解决多数据源冲突的数据真值发现，近年来许多研究者提出相关算法。本文对典型的TruthFinder、KDE、KDEm、CRH等算法，用Python进行实现，然后通过实验对它们的准确性进行比较分析，得出相关的性能趋势图，为相关的真值发现应用，比如无线传感器应用、移动群智感知等，打下良好的基础。
- 国内外同类研究概况：
在2008年， Yin X, Han J, Yu P S在《Truth discovery with multiple conflicting information providers on the web》中给定多了数据源提供的对于多个真实对象的大量的冲突描述信息，如何从这些信息冲突中为每一个真是对象找出最准确的描述，并给出了一个解决方案 TruthFinder，该方案，通过迭代计算数据源的准确度和值的信心度来达到真值发现的目的。
TruthFinder：针对“真实性”问题，即“符合事实”，研究了如何从各种网站提供的大量相互冲突的信息中找出真实的事实，设计了一个一般的真实性问题框架，并提出了一种利用关系的“真实性查找”算法。网站与其信息之间的HIPS，即如果一个网站提供了许多真实的信息，那么它是值得信赖的；如果一个信息是由许多值得信赖的网站提供的，那么它很可能是真实的。实验表明，TruthFinder成功地发现了真相事实之间的冲突信息，并确定值得信赖的网站比流行的搜索引擎。TruthFinder的输入是关于特定类型对象属性的大量事实。事实是由许多网站提供的。对于每个对象，通常有来自不同网站的多个相互冲突的事实，TruthFinder的目标是识别其中的真实事实。
2014年，Li Q, Li Y, Gao J等人，在《Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation》文章中就真实天气、库存和飞行数据这些实例提出了CRH算法。
CRH :一个通用优化框架来模拟异构类型数据上的冲突解决问题，该框架无缝地集成了各种数据类型上的求真过程。在这个模型中，真值被定义为从多个源输入中产生最小加权偏差的值，其中权重表示源可靠性程度。通过导出了一个两步迭代过程，包括计算真值和源权重，作为优化问题的解决方案。该框架的优点在于它能够利用各种损失函数和正则化函数来有效地描述不同的数据类型和权重分布。可以推导了与观测次数成线性关系的有效计算方法，该方法可以很容易地在MapReduce模型中实现。作者对从多个平台收集的天气、库存和飞行数据集以及由UCI机器学习数据集生成的模拟多源数据进行了实验。结果显示了效率和与现有的冲突解决方法相比，CRH方法在从异构数据中寻找真理方面具有优势。
