概率数据库中近似函数依赖挖掘算法

摘要：

一个近似函数依赖（approximate functional dependency ，AFD）是一个几乎成立的函数依赖，目前大部分工作仅限于从一般数据上挖掘近似函数依赖。有时数据是被组织成概率数据的形式，为了从挖掘概率数据中挖掘出可用的近似函数依赖，定义了概率近似函数依赖，它不同于任何一种以往的定义，并给出了在不确定数据中，置信概率的动态规划求解算法，由于动态规划算法复杂度较高，导出了候选依赖的概率下界来进行剪枝，随后给出了基于字典序的挖掘方法以及相应的剪枝策略，最后，在真实和合成的数据集上进行充分的实验，说明了挖掘算法的可扩展性和剪枝策略的高效性，并展示了有趣的挖掘结果。

关键词：近似函数依赖、数据挖掘、概率数据库、数据质量、不一致性

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家“九七三”重点基础研究发展计划基金项目2012CB316200，2012CB316202；国家自然科学基金项目61402130

在线出版日期：2016-03-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2857-2865