基于贝叶斯网络的分布数据挖掘模型DDMB研究

1、基于贝叶斯网络的分布数据挖掘模型DDMB研究琚春华，男，1962年生，浙江工商大学，博士教授，博士生导师，研究方向为智能信息处理、电子商务。张捷，男，1982年生，浙江工商大学，管理科学与工程，硕士研究生。联系方式： 电话春华 张捷（浙江工商大学 计算机与信息工程学院 杭州 310012）摘 要：本文针对分布环境的数据挖掘要求，提出了基于贝叶斯网络的分布数据挖掘模型DDMB。论文详细阐述了DDMB中属性多叉树的概念和通过属性多叉树来反映分布环境各数据集属性总体特征的思想，介绍了基于移动Agent访问分布数据集来构建属性多叉树的方

2、法，详细描述了由属性多叉树生成综合贝叶斯网络的算法，阐述了面向属性多叉树的贝叶斯网络结构学习和参数学习，以及属性间依赖系数最小阈值的确定方法。实验结果表明，该模型有效地解决原有分布环境贝叶斯网络学习负担重、存储开销大、执行效率低等问题。关键字：分布环境 贝叶斯网络 属性多叉树 移动AgentDistributed Data Mining Model Based on Bayesian NetworkJu Chunhua Zhang Jie(Zhejiang Gongshang University, Hangzhou 310012)Abstract: The paper presents a

3、distributed data-mining model based on Bayesian DDMB, it proposes the concept of multi-branches tree of attribute and the opinion that using multi-branches tree of attribute to reflect the characteristic of attribute in the distributed dataset. It also introduced the way of building multi-branches t

4、ree of attribute based on Agents to distributed datasets, then explains the algorithm of Bayesian network for multi-branches tree of attribute, including structure learning and parameters learning. Finally, the paper presents a prototype system P-DDMB of distributed Bayesian network on the basis of

5、Bee-gent. The experimental results showed the DDMB providing high capability and efficiency of distributed business data miningKey words: distributed data mining, Bayesian network, multi-branches tree of attribute, agent1 引言随着企业网络化信息系统的应用和发展，形成了面向连锁经营的分布式数据库和海量型数据源。通过对这类数据源的挖掘，可获得隐含、潜在和有价值的决策信息2，发现企

6、业经营的运行规律。目前，已有众多的数据挖掘算法，如关联规则挖掘、聚类、决策树等，用于商品关联度分析、客户分类、销售预测等1。特别是贝叶斯网络，由于其优良的性能，常被应用在各领域的数据预测、分类、推理等功能中。贝叶斯网络不仅能够充分利用领域知识和样本数据信息，将先验知识和样本信息巧妙地结合在一起，还能描述变量间的因果关系，具有语意清晰、可理解性强的特点，且还能利用概率测度来处理不完整数据。然而，贝叶斯网络算法是面向集中式数据处理，要求所被挖掘的数据须存放于单一和集中的数据库中。即便在数据分布存储的情况下，也要求把这些数据重新汇集，然后再从汇总的数据集中训练出贝叶斯网络346。这种处理方法不仅会大

7、量占用存储空间，增加网络负担，而且使响应时间变长，破坏数据的私有性和安全性。针对这些问题，本文提出了基于贝叶斯网络的分布数据挖掘模型。2 贝叶斯网络与分布数据处理贝叶斯网络作为不确定性问题模拟和推理的一种有效工具，具有适应信息变化的能力，以及综合专家先验知识和实例数据的分布特征，其基本思想是：给定数据样本D，样本属性A=A1、A2Ai、X，其中X为类标号属性，X的可能取值x1、x2 xi，通过对数据样本D的学习，确定属性A1、A2Ai、X的贝叶斯网络B=。B=由两部分组成： 网络结构图G: 一个有向无环图，图中各节点对应随机变量A1,An，有向边表示变量间的直接依赖关系。 局部概率分布：是每个

8、属性变量Ai的条件概率P(Ai|Val(Parent(Ai) 所形成的表。其中，Parent(Ai)表示图G中Ai的父节点集。贝叶斯网络学习的过程即是确定网络结构图G和局部概率分布的过程，其分布数据的高度抽象性和海量数据特征的综合性确保了贝叶斯网络不仅适用于集中式的挖掘，而且适用于分布环境的挖掘。然而现有研究大多是针对数据集中环境下如何建立贝叶斯网络及推理。如文9研究了基于贝叶斯网络的集中式数据挖掘；文10在常规概率统计方法的基础上，提出了基于贝叶斯分类的语句特征挖掘；文11提出了一种基于贝叶斯分类器的统计学习方法和文字类别挖掘。目前，基于贝叶斯网络的分布数据挖掘研究成果还较少，考虑到网络信息

9、系统的广泛应用，以及分布处理的有效性和快速性，分布数据挖掘研究已成为热点。对于分布的数据挖掘，多Agent技术应用较为广泛，这方面的研究也颇多。文13提出了一个用于分布式数据挖掘的多Agent原型系统，解决了分类算法如何在分布环境下完成数据挖掘任务；文15利用Agent技术构建了基于Web的空间数据挖掘框架，并针对不同Agent所获知识的不一致性问题，提出了WBSDM知识融合问题。文16扩展了关联规则、分类和聚类算法，设计了一种基于Agent的分布式数据挖掘模型。本文提出将贝叶斯网络学习算法嵌入Agent平台，构建基于贝叶斯网络的分布数据挖掘模型，以处理分布环境下数据挖掘问题。该模型是以多Ag

10、ent系统为框架，以属性多叉树为中间过程，通过移动Agent技术实现属性多叉树的创建和映射。该属性多叉树能反映各分布数据集的特征数据，通过移动Agent映射分布数据集的变化状况，并与贝叶斯网络学习算法融合，构成基于贝叶斯网络的分布数据挖掘模型。基于该模型的挖掘方法与数据汇总法相比，网络传输数据量和空间存储占有明显减少，提高了访问和存储效率。3 基于贝叶斯网络的分布数据挖掘模型DDMB针对企业分布经营所形成的网络化数据库，利用Agent对分布数据源特征属性的映射和贝叶斯网络学习方法，建立面向企业经营分析的分布数据挖掘模型，支持企业进行销售预测、价格确定、客户分类等决策活动。本文提出的DDMB模型

11、的主要思想是：应用移动Agent访问分布数据集来构建属性多叉树，分析和确定各属性间依赖系数，生成由属性多叉树与依赖系数综合形成的贝叶斯网络，图1所示为分布数据挖掘模型DDMB的体系架构。图1 DDMB模型体系架构图1中Mediation Agent为移动Agent，该Agent具有自治性、反应性和能动性的特点，其任务是从分布数据库中分析并生成属性多叉树，该属性多叉树是决策内容属性的特征值集合。DDMB模型的分析过程是：各自治Agent先定位到对应的DBi，各自访问DBi中与决策相关内容之记录，抽取出DBi属性值，然后调用多叉树生成算法以得到属性多叉树，然后再由该属性多叉树通过改进的贝叶斯结构和

12、参数学习，生成综合的贝叶斯网络。3.1 属性多叉树 属性多叉树是一棵带有头表的多叉树，树中除叶节点外每层节点对应于数据集中某个属性，属性是与决策内容相关的某个字段，如在客户分类时，其相关属性可以是性别、年龄、职业、学历、收入等。树的每条边对应于属性不同的取值，即某属性有多少种取值，就有多少条边。每个节点保存对应边的属性取值和满足取值的记录条数。图2是用贝叶斯网络进行客户分类时的部分属性多叉树的例子，第二层表示的是Age属性（年龄），对应三条边，每条边对应“=40”、“ 25”、“=40的有430条，年龄25的有611条，年龄=25的有399条。图2 属性多叉树图例属性多叉树的头表是面向节点查找

13、的索引结构，为Agent对属性多叉树的动态操纵提供支持。如图3所示，头表包含三个域：属性名称AttName，属性取值AttValue，链表的头指针Head。头表中每行记录一个属性的一种取值，并用链表将各属性所有取值相同的节点链接起来，并把头指针放在头表中。图3 属性多叉树头表图例当Mediation Agent移动到分布的数据集DBi时，每访问数据库中的一个元组，可动态在属性多叉树中保存该元组的信息，增减属性多叉树中结点及对应边的值。当每个Mediation Agent移动其对应的数据集，完成属性多叉数的边和节点值修改，即得到属性多叉树。用属性多叉树来反映分布数据源的属性特征，避免了分布数据汇

14、总所带来的网络和存储负担。该属性多叉树只是记录了分布数据源中与决策相关的属性特征值，即各属性值和满足给定属性值条件的记录条数，而无须保存整条记录的信息，所以节省了网络和存储空间，有利于运算效率的提高。基于该属性多叉树，结合贝叶斯网络学习算法，即得到反映分布数据源总体特性的贝叶斯网络，从而实现分布数据挖掘。3.2 面向属性多叉树的贝叶斯网络结构学习在Mediation Agent访问分布数据源并生成属性多叉树后，利用基于相关性分析的结构学习算法，以得到贝叶斯网络结构。该算法的关键是根据属性多叉树来计算各属性间依赖系数G（Vi,Vj），输入由经验确定的最小阈值，便可得到分布环境下的综合贝叶斯网络结

15、构。下面给出各属性间的依赖系数G（Vi,Vj）的计算方法和相关说明，其中Vi、V j对应图2所示第i层和第j层的属性。定义1：设S是s个数据样本的集合，假定Vk属性有m个不同值，定义m个不同类Ci( i=1,m)。设si是类Ci中的样本数，那么期望信息：I(Vk)=其中，Pi是任意样本属于Ci的概率，并用估计；由于信息的二进位编码，对数函数以2为底1。定义2：设属性Vk具有v个不同值a1 a2 av，属性Vk将S划分为v个子集S1,S2,Sv；其中Sj包含S中这样一些样本，它们在Vk上有值aj；设sij是子集Sj中类Cj样本数，那么：I(Vk+1|Vk)=其中，I(s1j,smj)= ，Pij

16、=是Sj中样本属于类Ci的概率1。算法1：利用属性多叉树计算相邻两个属性间的依赖系数G(Vk，Vk+1)。输入：一个属性多叉树（AttiTree）；输出：G(Vk，Vk+1)方法：运用头表中与Vk相关的信息，按序计算I(Vk+1)、I(Vk+1|Vk)、G(Vk+1,Vk)= I(Vk+1)- I(Vk+1|Vk)算法2：利用属性多叉树计算任意两个属性间的依赖系数。输入：一个属性多叉树（AttiTree）；输出：任意两个属性间依赖系数。方法：计算AttiTree中，所有相邻层表示的属性之间的依赖系数；For k=1 to n-1Begin 复制一个原始AttiTree，记作AttiTree；

17、删除AttiTree的前k-1层； For j=k+1 to n-1 Begin 删除AttiTree第2层； 计算修改后AttiTree树中第1、2层属性之间的依赖系数； EndEnd 通过算法1和算法2可得到不同属性之间的依赖系数，然后构建包含所有属性的完全图G，输入最小阈值，去掉G中所有依赖系数小于的边，得到综合贝叶斯网络的结构G。3.3 面向属性多叉树的贝叶斯网络的参数学习在确定了贝叶斯网络的结构后，采用了最大似然估计统计方法，利用属性多叉树计算贝叶斯网络结构中各节点的参数表（CPT）。其基本思想是根据数据样本与模型参数的似然程度，判断数据样本与贝叶斯网络模型的拟和程度。具体的实现过程

18、是通过属性多叉树和贝叶斯网络有向图，分别计算每个节点的CPT，查询属性多叉树中每层属性的不同取值及其对应的条数，利用该属性的取值条数除以父节点属性的取值条数，计算得到CPT中每一项取值的概率值。计算过程如算法3所示。算法3：利用属性多叉树计算网络中每一个节点对应的CPT。输入：一个属性多叉树（AttiTree）；一个贝叶斯网络有向图。输出：有向图中每个节点对应的CPT。方法：For 每一个属性VkBegin复制一个属性多叉树删除在Vk之上的，且不是Vk的父节点的属性对应的层数；For 第k层上的一个节点nodeBegin在CPT中加入一条条件概率，条件为从根节点到node路径上各属性取值，断言

19、为Vk取E的标示，概率为E上value除以指向node边上的value； EndEnd3.4 构建贝叶斯网络的过程 数据分布环境下构建贝叶斯网络的整个过程如图4所示。图4 分布环境下构建贝叶斯网络的过程图在实际应用中，应根据不同应用目的（价格确定、客户分类、客户消费量预测等等），筛选与应用目的相关的属性，然后再利用上述模型，构建分布数据源环境下综合贝叶斯网络，并利用该综合贝叶斯网络进行预测和分类。4 测试与分析原型系统P-DDMB是在DDMB模型和Bee-gent移动Agent基础上，利用Bee-gent相关类和接口来实现分布环境贝叶斯网络的构建。基于异构性和可扩展性要求，原型系统运行在Jav

20、a平台上。在贝叶斯网络的构建过程中，网络的结构受到阈值影响。利用实验数据测试阈值对网络学习的影响，以及与数据汇总法的分类准确性分析比较。测试时，使用的数据集如图5所示，其中图5(1)为数据集中数据各属性定义，图5(2)为数据集中具体数据值。 图5 (1) 部分数据头定义 图5(2) 部分数据体利用DDMB，对该数据集进行分布环境下贝叶斯网络学习，得到的贝叶斯网络结果以xml格式保存，图6(a)为该贝叶斯网络的部分xml文档。该部分数据对应的部分图形如图6(b)所示，图6(a)中xml文档的前半部分的probability标签描述了age属性对education属性的影响，其education结

21、点对应的参数值为（0.13、0.19、0.01、0.39、0.21、0.53、0.48、0.51、0.32、0.0、0.19、0.14）。同理，education属性对career属性的影响，及marriage、career、education属性对income属性的影响。 图6(a) 部分贝叶斯网络结构xml图6(b) 部分贝叶斯网络结构图4.1 依赖系数阈值的影响在确定贝叶斯网络时，需根据经验输入属性间依赖系数的最小阈值，以确定具有强依赖性的属性关系，输入阈值大小会直接影响到网络结构。根据相关性学习理论，阈值越大，确定的贝叶斯网络的边越少，网络的结构越简单。相反，阈值越小，其网络的结构越复

22、杂。图7是输入不同阈值时的网络结构图。 图7(1) =0.13 图7(2) =0.45 图7(3) =0.65由图可知，在确定贝叶斯网络时，除了要考虑网络的复杂度，还要考虑网络与数据集的拟合度，并不是网络结构越简单越好。依赖系数阈值太大，会造成过多的孤立结点；依赖系数过小，会导致过多的不合理依赖关系，不利于分类和预测。在确定依赖系数时，应根据经验从小到大，逐步找到相对合理的网络结构，图7(2)是较为合理的结构。4. 2 与数据汇总法的比较本文从分布数据集中随机抽取100条记录作为测试样本数据，用于DDMB模型测试，验证其准确性和合理性。一是采用数据集中法，通过RMI远程访问，把分布数据汇总，从

23、汇总数据中生成属性多叉树，再构建贝叶斯网络B1。二是采用原型系统P-DDM，通过移动Agent访问分布数据集来构建属性多叉树，生成综合贝叶斯网络B2。把随机抽取的100条记录用做测试样本T，将消费量（quantity）作为类标号属性，分别用贝叶斯网络B1和B2进行推理，比较B1和B2的分类准确性，其结果如表1所示。表1 DDMB与数据汇总法结果比较表如表所示，采用DDMB方法虽然准确率略微降低，但时间效率是传统集中方法的4倍，大大减少了建网的时间。5 结束语本文提出了基于贝叶斯网络的分布数据挖掘模型，通过移动Agent访问分布数据源，构建属性多叉数和贝叶斯网络，实现分布商业数据挖掘。实验表明，该模型具有较高的时间效率和分类准确率，今后将在模型的动态性和并行运算方面开展研究。参考文献1范明,孟小峰等译. 数据挖掘概念与技术M. 机械工业版社, 20052王黎明,柴玉梅,黄厚宽. 基于多Agent的分布式数据挖掘模型J. 计算机工程与应用, 2004,9:197-1993林士敏,田凤占,陆玉昌. 贝叶斯网络的建造及其在数据采掘中的应用J. 清华大学学报, 2001,41(1):49-524王纬,蔡莲红. 贝叶斯网络拓扑结构确定方法的研究J. 小型微型计算机系统, 2002,23(4):4