CN105022798A - 一种基于预测关系的离散贝叶斯网络分类数据挖掘方法 - Google Patents

Abstract

公开了一种基于预测关系的离散贝叶斯网络分类数据挖掘方法。本方法采用了在Hadoop平台上运行相应的MapReduce程序，利用相关系数分析初选预测因子和目标因子之间的相关性来选取预测因子，利用因子(预测因子和目标因子)之间的预测能力确定初始贝叶斯网络的结构，根据变量组对单一变量的预测能力，增加丢失的路径、删除多余的路径，并进行环路检验，获得几个相对较优的贝叶斯网络分类器，再在此基础上进行精度评估，获得满足期望的最优贝叶斯网络分类器。结合了Hadoop平台处理海量数据的优势，通过现有数据集去构建贝叶斯网络分类器，同时对选取的预测因子和目标因子进行相关分析，不仅实现了训练贝叶斯网络模型的灵活性，而且大大提高了预测精度和算法效率。

Description

一种基于预测关系的离散贝叶斯网络分类数据挖掘方法

技术领域

本发明涉及海量数据挖掘领域，适用于特征属性之间具有相关性、特征属性具有不确定性的数据挖掘。特别涉及在数据挖掘中利用海量数据根据实际需要训练贝叶斯网络分类模型的方法。

背景技术

贝叶斯网络是在不确定性环境下有效的知识表示和概率推理模型，是一种流行的图形化决策分析工具。现有的贝叶斯网络分类数据挖掘方法主要是利用专家知识获得初始的贝叶斯网络结构，然后基于一定的规则不断迭代对该结构进行优化，获得最终的贝叶斯网络结构。即在已知的初始贝叶斯网络结构的情况下，根据现有数据推断出相对最优的贝叶斯网络结构。贝叶斯网络分类数据挖掘方法已经被广泛地应用于文本分类、经济预测、医疗诊断等领域。

这一方法的问题是，当用户根据专家知识事先选取的初始贝叶斯网络结构中的路径和最终获得的贝叶斯网络结构相差很大时，对初始贝叶斯网络结构进行迭代优化的过程必然会计算繁琐、耗时，最终的精度评估也可能无法达到令人满意的结果。同时各行业产生海量的数据也在不断产生新的特征属性，特征属性之间的关联性也在不断发生变化，现有的贝叶斯网络分类数据挖掘方法难以满足人们的需求。

由此可见，在海量数据挖掘中，根据实际需要训练贝叶斯网络分类模型的方法有着现实的需要。

发明内容

本发明要解决的技术问题是提供一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，使得在海量数据挖掘中，能够根据实际需要训练贝叶斯网络分类模型，从而进行高效率、高精度的分类预测。

本发明解决现有技术的问题，所采用的技术方案是：提供一种利用相关系数选取预测因子，利用因子(预测因子和目标因子)之间的预测能力确定贝叶斯网络结构的分类数据挖掘方法，其包括以下步骤：

1、选取预测因子。初步选定一些可能与目标因子具有相关性的预测因子，计算各个预测因子和目标因子之间的相关系数γ_i，并设定临界值α，若γ_i≥α，保留该预测因子，否则去掉该预测因子；

2、训练贝叶斯网络模型。根据保留的预测因子，基于预测因子之间的预测能力确定初始贝叶斯网络结构，调整贝叶斯网络的结构并进行环路检验；

3、进行精度评估。不满足精度时，重新训练贝叶斯网络模型，直至获得最优的贝叶斯网络结构。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的进一步技术方案是该方法在Hadoop平台上利用其分布式文件系统HDFS和MapReduce并行编程模型来实现。

1、Hadoop分布式文件系统(HDFS)。HDFS是分布式计算的存储基础，它具有高容错性,可以部署在廉价的硬件设备上,适合那些有大数据集的应用,并提供了对数据读写的高吞吐率。

2、MapReduce编程模型。它将运行在大规模集群上的复杂并行计算抽象为两个函数:Map函数和Reduce函数。首先将一个大任务分割为多个并行的Map任务块,然后将Map分别给集群中的各个节点进行运算,最后Reduce把分解后的多个任务块的处理结果汇总起来,从而得到最终的结果。因此，MapReduce可处理的任务应满足:待处理的任务(或数据集)可以分割成许多个小任务(或小数据集),并且每一个小任务(或小数据集)都可以完全的并行计算。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的进一步技术方案是对原始数据进行预处理，以去掉不正确或被损坏的无效数据和离散化原始数据。预处理又可分为三个部分：

1、数据的选取。其目的是确定挖掘的操作对象；

2、数据的预处理。海量的原始数据一般都存在偏差和缺失的情况，这些数据若被用于数据挖掘，则在进行数据挖掘之前必须进行数据的预处理，去除数据中的噪声、冗余以及对缺省值进行填充等；

3、数据的转换。数据转换的方式也有所不同，针对特定的挖掘算法，将数据转换成相应的分析模型，建立的适合挖掘算法的分析模型是数据挖掘成功的关键。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法进一步技术方案将原始数据分成三部分训练集、验证集和测试集。训练集用于创建贝叶斯网络分类器；验证集用于优化分类器的参数或选择最优贝叶斯网络结构；测试集用于计算最终经过优化的分类器的精度。三个数据集必须保持独立性。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的进一步技术方案是基于训练集运行相应的MapReduce程序获得初步选定的各个预测因子和目标因子之间的相关系数γ_i，并设定临界值α，若γ_i≥α，保留该预测因子，否则去掉该预测因子，得到所选的预测因子，从而得到待用的预测因子集。计算相关系数的理论依据：

随机变量X与Y的协方差为Cov(X,Y)＝E(X-EX)(Y-EY),相关系数为γ_XY＝Cov(X,Y)/取值在-1到1之间。当γ_XY＝0时,称X,Y不相关；当|γ_XY|＝1时，称X,Y完全相关，此时，X,Y之间具有线性函数关系；当|γ_XY|<1时，X的变动引起Y的部分变动，|γ_XY|的绝对值越大，X的变动引起Y的变动就越大，|γ_XY|>0.8时为高度相关，当0.5<|γ_XY|<0.8时为显著相关，当0.3<|γ_XY|<0.5时为低度相关，当|γ_XY|<0.3时为不相关。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的进一步技术方案是基于训练集运行相应MapReduce程序计算任意两个因子之间(预测因子和目标因子)的预测能力，根据条件预测能力确定弧的存在性和方向，确定初始贝叶斯网络结构，在此基础上调整初始贝叶斯网络结构,增加丢失的路径、删除多余的路径，并进行环路检验，获得几个相对较优的贝叶斯网络分类器。训练贝叶斯网络模型的理论依据：

定义1记 $F_1=F(X_{m_1},...,X_{m_t}\&RightArrow;X_i)$ 为变量组对X_i的预测能力， $F_1={\mathrm{\&Sigma;}}_{X_{m_1}}...{\mathrm{\&Sigma;}}_{X_{m_t}}P(X_{m_1},...,X_{m_t}){\max }_{X_i(X_{m_1},...,X_{m_t})}\left\{P\right(X_i|X_{m_1},...,X_{m_t}\left)\right\},m_j\&NotEqual;i,j=1,...,t.$

定义2记 $F_2=F^{^}(X_{m_1},...,X_{m_t}\&RightArrow;X_i)$ 为 $F(X_{m_1},...,X_{m_t}\&RightArrow;X_i)$ 的估计值， $F_2={\mathrm{\&Sigma;}}_{X_{m_1}}...{\mathrm{\&Sigma;}}_{X_{m_t}}P\left(X_i\right){\max }_{X_i(X_{m_1},...,X_{m_t})}\left\{P\right(X_{m_1},...,X_{m_t}|X_i\left)\right\},m_j\&NotEqual;i,j=1,...,t.$

1、确定初始贝叶斯网络结构

令 $M=\frac{F^{^}(X_j\&RightArrow;X_i)}{F^{^}\left(X_i\right)},N=\frac{F^{^}(X_i\&RightArrow;X_j)}{F^{^}\left(X_i\right)},$ 则

M>N，且max{M，N}>ρ_入，添加弧X_j→X_i；

Q>P，且max{M，N}>ρ_入，添加弧X_i→X_j；

M<ρ_出且N<ρ_出，随机定向。

2、调整初始贝叶斯网络结构

设变量组X_m1,…,X_mt是X_i和X_j的最小割端集，令 $P=\frac{F^{^}(X_{m_1},...,X_{m_t},X_j\&RightArrow;X_i)}{F^{^}(X_{m_1},...,X_{m_t}\&RightArrow;X_i)},Q=\frac{F^{^}(X_{m_1},...,X_{m_t},X_i\&RightArrow;X_j)}{F^{^}(X_{m_1},...,X_{m_t}\&RightArrow;X_j)},$

P>Q，且max{P，Q}>ρ_入，添加弧X_j→X_i；

Q>P，且max{P，Q}>ρ_入，添加弧X_i→X_j；

P<ρ_出且Q<ρ_出,删除X_j→X_i之间的弧。

3、环路检验

删除没有父节点和子节点的节点及与其相连的弧，在剩下的子图中再删除没有父节点和子节点的节点及与其相连的弧，如此下去，如果存在每一个节点都是有父节点和子节点的子图，那么存在环路，否则不存在环路。

本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的进一步技术方案是利用测试集对已经得到的几个贝叶斯网络分类器进行精度评估。实际应用中对分类器性能的精度评估指标主要有三个：

1、预测精度：预测精度越高的分类器，分类预测能力也就是越准确的，本发明中采用分割一部分数据集作为测试集的方法测试分类模型的精度；

2、计算效率：由于数据量非常巨大，导致算法的时间和空间复杂度也非常高，高效的计算式分类效率的保证；

3、模型描述的简洁度：对模型的描述应易于被研究人员理解和使用。

相较于现有技术，本发明提供的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法的有益效果是：结合Hadoop平台处理海量数据的优势，利用海量数据根据实际需要训练贝叶斯网络分类模型，对初选预测因子和目标因子进行相关性分析，只有判定两者相关时才被作为预测因子，这样不仅可以使分类预测结果更加可靠，而且可以节约资源，提高预测精度算法的效率。

附图说明

图1是本发明基于Hadoop构建贝叶斯网络分类器的数据挖掘方法的步骤示意图。

图2是本发明基于Hadoop构建贝叶斯网络分类器的数据挖掘方法的具体程序流程图。

具体实施方式

下面将结合附图对本发明的实施方式进行详细描述。

请参阅图1，是本发明基于Hadoop构建贝叶斯网络分类器的数据挖掘方法的步骤示意图。主要步骤为：获取原始数据对它进行去除无效数据和离散化等处理后，分为训练集、验证集和测试集三部分，且这三部分是相互独立的，对训练集运行相关分析算法和贝叶斯网络分类算法得到初始分类模型，利用验证集对初始分类模型进行修剪路径优化，得到相对较优的分类模型，利用测试集对得到的相对较优的贝叶斯网络分类器进行精度评估，如果精度没有达到期望值，仍需重新优化分类模型。

请参阅图2，是本发明基于Hadoop构建贝叶斯网络分类器的数据挖掘方法的具体程序流程图。预处理、相关分析、模型训练和精度评估四大过程，它们是顺序执行的，后一次过程都依赖于前一次执行的结果，一次MapReduce过程无法完成任务。因此将四大过程任务串起来，将预处理MapReduce和模型训练MapReduce后的结果分别存储为中间数据，四个过程顺序组合的MapReduce作业共同完成任务。具体过程包括：

1、对原始数据进行预处理，以去掉不正确或被损坏的无效数据和离散化原始数据，将数据分为训练集、验证集和测试集三部分；

2、根据1中的训练集，初步选定一些可能与目标因子具有相关性的预测因子，在Hadoop平台上运行相应的MapReduce程序，计算各个预测因子和目标因子之间的相关系数γ_i，并设定临界值α，若γ_i≥α，保留该预测因子，否则去掉该预测因子；

3、根据2中保留的预测因子，在Hadoop平台上运行相应的MapReduce，计算任意两个因子(预测因子和目标因子)之间的预测能力，根据预测能力确定初始贝叶斯网络结构；

4、根据3中初始贝叶斯网络结构以及验证集，在Hadoop平台上运行相应的MapReduce程序，计算预测因子组与目标因子之间的预测能力，不断迭代修剪路径，调整贝叶斯网络的结构，并进行环路检验，获得相对较优的几个贝叶斯网络结构；

5、根据4中相对较优的几个贝叶斯网络结构以及测试集，在Hadoop平台上运行相应的MapReduce程序，进行精度评估，不满足精度返回执行4，直到获得满足精度的最优贝叶斯网络结构；

虽然结合附图描述了本发明的实施方式，但是本领域内熟练的技术人员可以在所附权利要求的范围内做出各种变形或修改。

Claims (7)

1.一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，采用了在Hadoop平台上运行相应的MapReduce程序，从海量数据中计算属性变量之间的预测能力来确定贝叶斯网络的初始结构，不断迭代优化进而得到最优贝叶斯网络分类器，其特征在于，包括以下步骤：

步骤S1：对原始数据进行预处理，以去掉不正确或被损坏的无效数据和离散化原始数据，将数据分为训练集、验证集和测试集三部分；

步骤S2：根据步骤S1中的训练集，初步选定一些可能与目标因子具有相关性的预测因子，在Hadoop平台上运行相应的MapReduce程序，计算各个预测因子和目标因子之间的相关系数γ_i，并设定临界值α，若γ_i≥α，保留该预测因子，否则去掉该预测因子；

步骤S3：根据步骤S2中保留的预测因子，在Hadoop平台上运行相应的MapReduce，计算任意两个因子(预测因子和目标因子)之间的预测能力，根据预测能力确定初始贝叶斯网络结构；

步骤S4：根据步骤S3中初始贝叶斯网络结构以及验证集，在Hadoop平台上运行相应的MapReduce程序，计算预测因子组与目标因子之间的预测能力，不断迭代修剪路径，调整贝叶斯网络的结构，并进行环路检验，获得相对较优的几个贝叶斯网络结构；

步骤S5：根据步骤S4中相对较优的几个贝叶斯网络结构以及测试集，在Hadoop平台上运行相应的MapReduce程序，进行精度评估，不满足精度返回执行步骤S4，直到获得满足精度的最优贝叶斯网络结构。

2.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法在Hadoop上利用其分布式文件系统HDFS和MapReduce并行编程模型来实现。

3.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法对原始数据进行预处理，以去掉不正确或被损坏的无效数据和离散化原始数据，将数据分为训练集、验证集和测试集三部分，三个数据集必须保持独立性。

4.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法判断初选预测因子与目标因子之间的相关性来确定预测因子集。

5.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法对训练集运行MapReduce程序，获得任意两个因子(预测因子和目标因子)之间的预测能力，得到初始贝叶斯网络分类模型。

6.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法对训练集运行MapReduce程序，获得预测因子组与目标因子之间的预测能力，不断迭代修剪路径，调整贝叶斯网络的结构，并进行环路检验，获得相对较优的几个贝叶斯网络结构。

7.根据权利要求1所述的一种基于预测关系的离散贝叶斯网络分类数据挖掘方法，其特征在于，该方法对测试集运行MapReduce程序，进行精度评估，不断迭代，直到获得满足精度的最优贝叶斯网络结构。