一种基于贝叶斯网络的函数依赖并行挖掘方法

本发明涉及数据库挖掘与数据库，具体地，涉及一种基于贝叶斯网络的函数依赖并行挖掘方法。

背景技术：

1、函数依赖（functional dependency, fd）是关系数据库理论的核心概念，在数据质量管理、模式设计、数据清洗、异常检测及查询优化等任务中发挥关键作用，其挖掘目标是从数据集中自动发现属性间的确定性约束关系，为数据建模与知识抽取提供依据。

2、现有fd挖掘方法主要包括逐层搜索方法（如tane、fun、fd_mine 和 depminer等）、深度优先搜索方法（如dfd、fastfds）、混合式方法（如hyfd）、近似函数依赖发现方法（如cords）、基于学习的fd发现方法（如fdx、fdmc）、基于贝叶斯网络的规则发现方法及并行规则挖掘方法等。然而，这些方法普遍存在以下缺陷：在高维或大规模数据集上计算复杂度高、可扩展性差，属性数量超过60个时运行时间与内存消耗难以接受；基于支持度的剪枝策略易遗漏低支持度但高置信度的关键依赖；对数据噪声敏感，鲁棒性不足，结构学习失真、误检率上升；缺乏统一的统计建模框架，难以刻画属性间因果与条件独立关系；并行化设计不完善，无法充分利用多核或分布式资源。其中，与本发明最接近的hyfd和fdx方法，分别存在漏检稀有重要依赖、高维噪声数据下精度下降的问题。

3、因此，本领域迫切需要一种能够在大规模、含噪声数据环境下，高效、准确地发现函数依赖，特别是低支持度高置信度依赖的新方法。

技术实现思路

1、本发明的目的在于提供一种基于贝叶斯网络的函数依赖并行挖掘方法，克服现有方法在大规模、含噪声数据下计算复杂度高、漏检关键依赖、鲁棒性不足的技术问题，降低大规模数据下函数依赖挖掘的计算与空间复杂度，实现低支持度高置信度依赖的有效识别，提升噪声数据环境下的鲁棒性，同时为函数依赖挖掘提供统计理论支撑。

2、为了实现上述目的，本发明的技术方案如下：

3、一种基于贝叶斯网络的函数依赖并行挖掘方法，包括以下步骤：

4、s1.贝叶斯网络视角下的函数依赖建模：建立贝叶斯网络结构学习与函数依赖挖掘之间的数学对应关系，以条件熵作为属性依赖关系的量化指标，当属性x关于属性y的条件熵h(y|x)趋于零时，判定属性x对属性y的函数依赖具有高置信度；

5、s2.分层采样与搜索空间缩减：获取原始关系表，基于分层采样策略从所述原始关系表中获取样本数据集，基于样本数据集构建星型贝叶斯网络并提取目标属性的相关属性集合，再将原始关系表垂直划分为多个子表；

6、s3.并行依赖发现与结果合并：采用并行函数依赖挖掘算法 pfminer，在多个子表上同时执行传统顺序算法，并对挖掘结果进行合并与去重，生成最小函数依赖集。

7、进一步的，所述s1包括以下步骤：

8、s11.给定一个属性集合，任取其中两个属性x与 y，若在贝叶斯网络中存在一条由x指向y的有向边，则表示属性 x对 y的取值具有显著的条件约束作用；若该边不存在，则说明两者在统计上独立；

9、s12.基于贝叶斯网络结构学习方法都以条件熵趋于0为目标进行训练，即当条件熵趋于0时，贝叶斯网络结构学习方法才会建立x与 y两个属性之间的有向边；

10、s13.以条件熵作为属性依赖关系的量化指标，通过判断条件熵的收敛性实现fd的自动推断：

11、

12、因此，当条件熵趋于零时，说明 x几乎唯一确定 y，此时函数依赖成立。

13、进一步的，所述s12中的贝叶斯网络结构学习方法通常采用两类实现方法如下：

14、s121.基于评分的学习方法：通过定义网络结构的评分函数并利用搜索算法寻找最优结构；

15、s122.基于约束的学习方法：通过条件独立性检验确定节点间的因果方向关系。

16、进一步的，所述s2中的基于分层采样策略从所述原始关系表中获取样本数据集，具体包括以下步骤:

17、从所述原始关系表中选择取值类别最多的属性作为代表属性；

18、根据所述代表属性的取值范围将所述原始关系表划分为多个层；

19、在每个层中按固定比例进行随机采样，将各层采样结果组合形成所述样本数据集，样本分布的经验估计与总体分布一致。

20、进一步的，所述s2中构建星型贝叶斯网络具体包括：对于每个属性a，在贝叶斯网络结构学习过程中，定义约束集以禁止除a之外的其他属性之间建立边连接，从而形成以a为中心的星型贝叶斯网络。

21、进一步的，所述s2中的提取目标属性的相关属性集合具体包括： 从所述星型贝叶斯网络中提取所述目标属性a的马尔可夫毯，将所述马尔可夫毯中的属性作为所述目标属性a的相关属性集合。

22、进一步的，所述s3包括以下步骤：

23、s31.将所有子表分配给多个处理线程；

24、s32.每个线程在其分配的子表上独立运行tane或dfd中的一种函数依赖挖掘算法；

25、s33.所有线程完成后，系统自动合并各线程输出，去除重复和冗余规则，生成最终的最小函数依赖集。

26、进一步的，所述s33中的系统自动合并各线程输出，去除重复和冗余规则具体包括以下步骤：

27、s331.当所有线程完成计算后，系统进入结果整合阶段,所有线程输出的结果集合被合并为全局集合；

28、s332.对重复或相互包含的依赖项执行去重操作，仅保留最小函数依赖集；

29、s333.去除重复和冗余规则包括：

30、若存在两条函数依赖规则fd1: x1→y和fd2: x2→y，且x1是x2的子集，则删除fd2。 采用上述技术方案，本发明具有以下优点：

31、1.本发明提供了一种基于贝叶斯网络的函数依赖并行挖掘方法，理论创新性强，首次建立函数依赖与贝叶斯网络的数值等价性，以条件熵趋于0为高置信度依赖判定准则，填补了低支持度高置信度规则挖掘的技术空缺，提升了依赖检测的理论可解释性。

32、2.本发明提供了一种基于贝叶斯网络的函数依赖并行挖掘方法，搜索效率显著提升，通过分层采样降低数据规模，结合星型贝叶斯网络与马尔可夫毯提取相关属性，将原始关系表垂直划分子表，将全局指数级搜索空间转化为多个局部子空间，大幅降低计算复杂度，计算效率高。

33、3.本发明提供了一种基于贝叶斯网络的函数依赖并行挖掘方法，并行加速效果突出，通过设计pfminer并行挖掘框架，在多核或分布式环境中实现多子表并行处理，整体加速比可达数十倍至上百倍，同时保证结果一致性与最小化，具备良好的可扩展性和工程实用价值。

34、4.本发明提供了一种基于贝叶斯网络的函数依赖并行挖掘方法，鲁棒性更强，分层采样保证了数据统计特性，贝叶斯网络建模降低了噪声数据对依赖检测的影响，有效提升了噪声环境下依赖发现的置信度与准确性。

1.一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，包括以下步骤：

2.根据权利要求1所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s1包括以下步骤：

3.根据权利要求2所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s12中的贝叶斯网络结构学习方法通常采用两类实现方法如下：

4.根据权利要求1所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s2中的基于分层采样策略从所述原始关系表中获取样本数据集，具体包括以下步骤:

5.根据权利要求1所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s2中构建星型贝叶斯网络具体包括：对于每个属性a，在贝叶斯网络结构学习过程中，定义约束集以禁止除a之外的其他属性之间建立边连接，从而形成以a为中心的星型贝叶斯网络。

6.根据权利要求1所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s2中的提取目标属性的相关属性集合具体包括： 从所述星型贝叶斯网络中提取所述目标属性a的马尔可夫毯，将所述马尔可夫毯中的属性作为所述目标属性a的相关属性集合。

7.根据权利要求1所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s3包括以下步骤：

8.根据权利要求7所述的一种基于贝叶斯网络的函数依赖并行挖掘方法，其特征在于，所述s33中的系统自动合并各线程输出，去除重复和冗余规则具体包括以下步骤：