基于捕食逃逸PSO的贝叶斯网络分类器

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于捕食逃逸PSO的贝叶斯网络分类器范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要:

构造精确的贝叶斯网络分类器已被证明为NP难问题,提出了一种基于捕食逃逸粒子群优化(pso)算法的通用贝叶斯网络分类器,能有效避免数据预处理时的属性约简对分类效果的直接影响,实现对贝叶斯网络结构的精确学习和搜索。另外,将所提出的分类器应用于高职院校就业预测分析,并在Weka平台上实现对该分类器的构建和验证,与其他几种贝叶斯网络分类器的对比实验结果表明,该分类器具有更好的性能。

ス丶词:

捕食逃逸;粒子群优化;贝叶斯网络分类器;Weka;就业预测

ブ型挤掷嗪:

TP301; TP18

文献标志码:A

英文标题

Bayesian network classifier based on PSO with predatory escape behavior

び⑽淖髡呙

KONG Yuyan1, YAO Jintao2,LI Qiang1, ZHU Shenglin2, ZHANG Mingwu2

び⑽牡刂(

1. Department of Computer, Nanhai Neusoft Institute of Information Technology, Foshan Guangdong 528225, China;

2.College of Information, South China Agricultural University, Guangzhou Guangdong 510642, China

英文摘要)

Abstract:

Bayesian network classifier with precise structure has been proven to be NPhard problem. A Bayesian network classifier based on Particle Swarm OptimizationPredatory Escape (PSO_PE) algorithm was proposed in this paper, which could effectively avoid the direct influence of feature reduction on the performance of classification and complete the precise learning Bayesian network. In addition, the proposed classifier was exploited in employment predication of vocational college and was experimentally tested on Weka. The experimental results show that compared with other Bayesian classifiers, the new classifier is more effective and precise to learn Bayesian network.

英文关键词Key words:

predatory escape; Particle Swarm Optimization (PSO); Bayesian Network Classifier(BNC); Weka; employment predication

0 引言

贝叶斯网络分类器(Bayesian Network Classifier, BNC)[1]是建立在贝叶斯概率论基础上的基于统计方法的分类模型,可以预测类成员关系的可能性,即计算给定样本属于一个特定类的概率。贝叶斯网路分类器的一个主要优点是在用于大型数据库时，表现了高准确率与高速度。应用贝叶斯网络分类器进行分类主要分成两阶段:1)贝叶斯网络分类器的学习，即从样本数据中构造分类器,包括结构学习和条件概率表(Conditional Probability Table, CPT)学习;2)贝叶斯网络分类器的推理，即计算类节点的条件概率,对分类数据进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度,甚至可以是NP完全问题,因而在实际应用中,往往需要对贝叶斯网络分类器进行简化。根据对特征值间不同关联程度的假设,可以得出各种贝叶斯网络分类器,如朴素贝叶斯(Naive Bayes, NB)、树扩展的朴素贝叶斯(Tree Augmented Naive Bayes, TANB)、增强的贝叶斯网络分类器(Bayesian Network NaiveBayes，BAN)、一般贝叶斯网络(General Bayesian Network, GBN）是其中较典型且研究较深入的贝叶斯网络分类器[2]。

粒子群优化(Particle Swarm Optimization, PSO)算法[3]是一种模拟简化社会模型的迭代优化方法,其基本思想是将每个粒子看成问题解空间中的候选解,然后通过更新粒子的速度和位置来改变粒子在解空间中的位置,迭代探索最优解。与遗传算法比较,PSO没有如交叉和变异等遗传操作,而是通过所有粒子在解空间追随最优粒子进行搜索,只有gBestО研畔⒌ハ蛄鞫给其他粒子,即整个搜索更新是跟随当前最优解的过程,因此在大多数情况下,所有粒子则可能更快地收敛于最优解。因其概念简单、易于实现、无需梯度信息、参数少、能有效解决复杂优化问题等特点而引起学术界的广泛重视,成为国际上智能优化领域研究的热点,目前已被成功应用于多目标优化、模式识别、信号处理和决策支持等领域,具有良好的应用前景。

目前,构造精确的贝叶斯网络分类器已被证明为NP问题[4],因此可以将PSO算法引入贝叶斯网络分类器中,通过在训练集上随机属性选取生成若干属性子集,并以这些子集构建相应的贝叶斯网络分类器,然后用PSO算法对分类器进行优选,能有效避免数据预处理时的属性约简对分类效果的直接影响。但是,早熟收敛、收敛效率低、全局收敛性差依然是PSO算法面临的一大难题,其主要原因是群体最优gBestУ奈ㄒ恢配性信息共享模式无法对称调整社会认知能力, 因此,通过在群体中引入捕食粒子来增大逃逸粒子的捕食风险,使各逃逸粒子根据捕食风险和自身能量状态的权衡结果产生相应逃逸行为,提高了粒子群对称调整社会认知能力,进而有效地保持群体多样性,平衡群体的探索和开发能力,使群体避免陷入早熟收敛。利用改进后的捕食逃逸PSO算法提出一种基于捕食逃逸粒子群优化(Particle Swarm Optimization with Predatory Escape, PSO_PE)算法的贝叶斯网络分类器,则能更加有效完成对贝叶斯网络分类器模型的精确构建。

为了进一步验证基于PSO_PE的贝叶斯网络分类器的分类预测效果,本文将其具体应用于高职院校就业预测分析,结果表明采用该分类器所构造的就业预测模型能较准确地预测某毕业生能否就业或某一年整个学校的就业率,对学校和毕业生个人来说都是一个很有价值的信息。可见,本文所提出的贝叶斯网络分类器是有效的。

1 贝叶斯网络分类器

贝叶斯网络又称为信念网络(Belief Network, BN), 其详细的定义为[1]:

设V={X1,X2,…,Xn}是值域U上的n个随机变量,则值域U上的贝叶斯网络定义为BN(BS,BP),其中：BS是一个定义在V上的有向无环图(Directed Acyclic Graph, DAG)Γ,V是该有向无环图Γ的节点集,E是Γ的边集。如果存在一条节点Xj到节点Xi的有向边,则称Xj是Xi的父节点,Xi是Xj的子节点，记的所有父节点为πi；而BP=P(Xi/πi[0,1]}Xi∈V)}。对于V中每个节点,定义了一组条件概率分布函数P(Xi/πi[0,1])。贝叶斯网络是概率理论和图形理论的结合,主要由以下两部分构成。И

1)有向无环图Е,通常称为贝叶斯网络结构。由若干个节点和连接这些节点之间的有向边组成,节点代表问题领域的随机变量,每个节点对应一个变量。变量的定义可以是问题中感兴趣的现象、部件、状态或属性等,具有一定的物理和实际意义。连接节点之间的有向边代表节点之间的依赖或因果关系,连接边的箭头代表因果关系影响的方向性(由父节点指向子节点),节点之间缺省连接则表示节点所对应的变量之间条件独立。

2)局部概率分布集,通常称为条件概率表。概率值表示子节点与其父节点之间的关联强度或置信度,没有父节点的节点概率为其先验概率。贝叶斯网络结构是将数据实例抽象化的结果,是对问题领域的一种宏观描述；而概率参数是对变量(节点)之间关联强度的精确表达,属于定量描述的部分。

GBN分类器与NB、TAN、BAN分类器的较大区别是,后者3类分类器中均将类变量所对应的节点作为一个特殊的节点,即是各特征节点的父节点,而GBN将分类节点当成和其他节点一样的属性节点来对待。这种结构学习需要获得一个完整的贝叶斯网络,它把分类问题看做一种特殊的推理过程或决策问题，本文主要讨论GBN分类器。

2 基于捕食逃逸PSO的贝叶斯分类器

2.1 捕食逃逸PSO

2.1.1 PSO_PE算法的基本原理

捕食与被捕食在生物界普遍存在,捕食风险的影响涵盖了几乎所有动物性的决策方式,被捕食者必须在自身能量状态和捕食风险间进行权衡,并最终做出行为上的改变。一般来说,被捕食者会回避捕食风险较高的搜寻区域，从而始终与捕食者保持一定的逃逸开始距离[5] (Flight Initiation Distance, FID),即允许捕食者靠近的最大距离。当双方距离等于或接近FID时,被捕食者将根据自身的能量状态做出不同反应,能量状态越大则逃逸速度越快；能量状态越小将承受越大的捕食风险缓慢移动或静止不动,被捕食概率加大。本文受捕食逃逸现象启发而提出的捕食逃逸粒子群优化算法把原单一粒子群分成捕食粒子群(Predator Swarm, PS)和逃逸粒子群(Escaping Swarm, ES)两个子群体。PS粒子和ES粒子的行为将依据各自定义的简单规则加以约束,其中PS粒子追捕ES的gBestЯW,因而对ES粒子造成不等的捕食风险,即gBestЯW右材艽PS粒子获取信息,实现了群体的对称社会认知。当ES粒子与PS粒子的距离接近FID时产生逃逸,逃逸速度依赖于自身的能量状态(适应度),能量越大逃逸能力越强;若ES粒子与PS粒子的距离小于FID,则对ES粒子进行确定性变异,变异前后的ES粒子优胜劣汰。因而,在进化前期,算法具有较好的全局搜索能力。随着迭代增加,将逐步降低PS粒子对ES粒子的影响,以增加群体的局部搜索能力,进而平衡算法的局部和全局搜索能力,最终实现算法的全局性收敛。

2.1.2 相关定义

定义1 捕食风险也称为捕食压力是指在一定时间内ES粒子被捕食的概率,即：

PESi(t)=exp(-αikt′)(1)

其中：Е联iП硎ES粒子iвPS粒子相遇的概率,取决于它们之间的距离和当前PS粒子的密度,即Е联i=exp(-distancen1×β)；β为控制参数；n1为PS的规模；distance为ES粒子iв胱罱PS粒子之间的距离;k表示PS粒子攻击ES粒子的概率(固定为1);t′=（t+T）/T，Иt为当前代数,T为最大代数,迭代会逐步降低捕食粒子对被捕食粒子的影响。

定义2 能量状态指ES粒子当前饥饿状态,表现为该粒子的适应度(考虑最小化问题)与ES平均适应度的比值,即:

EESi(t) = fESi(t)fESavg(t)(2)オ

定义3 警觉距离(Alert Distance, AD)反映了ES粒子对PS粒子的警惕能力,是一种普遍的社群现象,其大小随群体密度和群体规模增加而减小,即:

D┆ES= FID×(1 + n1 ρ×n2 )(3)お

其中:Е血П硎镜鼻叭禾寰植棵芏;n1、n2Х直鸨硎PS粒子和ES粒子的规模。

┑2期

孔宇彦等：基于捕食逃逸PSO的贝叶斯网络分类器

┆扑慊应用 ┑31卷

2.1.3 算法描述

1)随机产生并初始化n1ЦPS粒子和n2ЦES粒子,Иm=n1+n2,设置t=0, β,FID控制参数。オ

2)计算每个粒子的适应度。

3)对每个粒子i,Ы其适应度值与其历史最好位置pBestiЫ行比较,更新pBestiШ酮gBest。オ

4)对每个PS粒子i,О凑帐(4)更新其速度和位置：

VPSid(t + 1)=ωVPSid(t) + c1 r1 (pBestPSid(t) - XPSid(t))+ c2 r2 (gBestESd(t)-XPSid(t))

XPSid(t + 1) = XPSid (t) + VPSid(t + 1)(4)

5)对每个ES粒子i：

①若distanced≥FID,О凑帐(5)更新其速度和位置:

VESid(t + 1)=ωVESid(t)+c1 r1 (pBestESid(t)-XESid(t))+c2 r2 (gBestESd(t)-XESid(t))+c3r3sign(DES-distanced)×EESi(t)X┆max(1-PESi(t))

XESid(t+1)=XESid(t)+VESid(t+1)(5)

其中:disancedП硎ES粒子iв氲讵d维最近PS粒子之间的距离;sign()为01阈值函数;X┆maxП硎疚恢玫淖畲笕≈;c3为捕食影响因子;r3为[0,1]范围内均匀分布的随机数。

②若distanced

6)判断是否满足终止条件，若未满足,则t=t+1,转2)。オ

2.2 基于捕食逃逸PSO的贝叶斯分类器

利用PSO_PE算法对GBN分类器进行学习,首先要解决以下几个问题:1)确定位置与编码方式,即如何将GBN网络结构编码到粒子的位置;2)设定初始群体;3)构建适应度函数来度量粒子的位置所代表的贝叶斯网对训练数据的“匹配”程度;4)确定粒子的运动模式;5)选取各种控制参数。

2.2.1 编码方法以及网络结构的限制

GBN将分类节点当成和其他节点一样的属性节点来对待，这种结构学习需要获得一个完整的贝叶斯网络。因此可认为每一种粒子位置状态对应一个网络结构,状态空间是所有可能结构的集合。对于网络结构的编码,由贝叶斯网的定义知道网络结构是有向无环图,所以可将网络中每一个变量的编码用其父节点集合来表示。整个网络的编码就是按一定顺序排列的节点的父节点集合。图1为一个简单的贝叶斯网络,其中A0是类节点(在图中未将它作为特殊阶段),A1至A4是属性节点。按照上面的编码规则,图1的编码为:[A0:A│(0);A1:A│(1);A2:A│(2);A2:A│(2);A3:A│(3);A4:A│(4)],Ai的父节点用A│(i)表示,其中A│(0)=[A4];A│(1)=[A0,A2];A│(2)=[A0];A│(3)=[A2,A4];A│(4)=[];可以将每个节点的局部结构(该节点和父节点集)表示成位置的一个分量的形式。

图片

图1 一个简单的GBN分类器结构

nЦ鼋诘隳芄钩捎邢蛭藁吠嫉谋匆端雇络数目可由式(6)得到:

f(n)=∑ni=1(-1)i+1Cni2i(n-i)f(n-i)(6)

由式(6)可知,当节点个数增长时,需要搜索的贝叶斯网络模型的个数将呈指数级增长。为了尽量地减少搜索空间,最有效地找到最优解,可采取以下解决方案:

1)限制每个节点的父节点数目,为所有的节点设置一个最大父节点个数m(m

2)通过计算节点间的相关性,根据阈值确定没有依赖关系的节点不能成为父子节点:

I(Xi,Xj)=∑xi,xjP(xi,xj)lbP(xi,xj)P(xi)P(xj)(7)

根据式(7)计算出节点间相关性,当相关性小于设定的阈值Е氖,就认定节点Xi和Xj之间没有依赖关系,从而不能成为父子节点关系。通过相关性的计算,又可以进一步减少搜索空间。И

2.2.2 初始群体的设定

PSO_PE算法中有两种类型的粒子群,被捕食粒子群和捕食粒子群,其中被捕食粒子群用来获得GBN分类器结构的最优解。被捕食粒子群可以随机生成，或专家先验知识给出，或由领域专家给出想象数据集；然后通过一个程序帮助用户创建一个假想的完备数据集,在完备数据集条件下选择出一定数量的较好的网络结构作为初始群体。本文随机生成被捕食粒子群和捕食粒子群,捕食粒子群是为了增加被捕食粒子群的局部搜索能力,所以捕食粒子群个数不能太多,取值为1~3较为恰当。对于所有的初始粒子群,都要进行有向无环形、父节点个数限制和计算出节点间相关性等处理。

2.2.3 适应度函数

适应度通常用来度量群体中各个个体在优化计算中有可能达到或接近于找到最优解的优良程度。适应度函数是用来评估个体的适应度,即区分群体中个体好坏的标准。本文是将PSO_PE算法封装在Weka平台上,用Weka自带的适应度函数(封装在.search.global.GlobalScoreSearchAlgorithm类calcScore方法里),更易实现PSO_PE算法。

2.2.4 速度算子的确定

1)速度[6]。表示一个集合的形式,该集合中每一个元素为一个节点及其父节点集。v表示速度,v表示该速度所包含的元素个数,N为网络中节点的个数,则该速度可表示为:И

v={(Ai1:πAi1),(Ai2:πAi2)…(Aiv:πAiv)

ij∈{1,2,…,N},j=1,2,…v}(8)

其中:Ф杂谌我jm、jn,如果jm≠jn,那么ijm≠ijn；空速度为一个空表,表示不做任何替换操作。И

2)速度的加法。设v1和v2为两速度,速度的加法v1+v2为两个速度的并集。И

3)速度的乘法。Уc≥1时,c*v=v;当c

4)速度与位置的加法。P′=PЙ┆v,即用速度v中各节点的父节点集替换原位置P所表示的网络中相应节点的父节点集。得到新位置P′后,它所表示的网络结构中很可能出现环路的情况,这时需要打破这些环路,使网络结构合法化。И

5)位置与位置的减法。设P1、P2分别代表2个粒子的位置,则P1Й擢P2=v，速度v是由P1中那些节点的局部适应度高于P2中相应节点局部适应度的节点及其父节点集构成的集合。И

2.2.5 其他参数的设定

1)全局极值。只有一个全局极值即被捕食粒子全局极值gBestESd,П徊妒沉W尤局极值记录了目前为止最佳的合法网络结构,当算法结束时,该值就是所得到的最优网络结构。

2)个体极值。捕食粒子个体极值为pBestPSid,被捕食粒子个体极值为pBestESid,在粒子运动过程中,通过个体极值记载每个粒子的历史最佳位置,即粒子形成的最佳贝叶斯网络结构。オ

3)被捕食粒子位置突变。当捕食粒子和被捕食粒子iЪ涞木嗬氇distanced

4)FID捕食距离。FID捕食距离决定被捕食粒子在什么范围内将被捕食,本文中FID设定为捕食粒子和被捕食粒子贝叶斯网络结构的相似度。本文设定当相似度大于90%时被捕食。

5)粒子群的个数和迭代的次数。被捕食粒子用来获得最优贝叶斯网络结构。根据本文整理出来的高职院校毕业生数据,学习GBN分类器网络结构时,被捕食粒子的个数设定为40,捕食粒子的个数为1。迭代的次数为80,停止条件为计算到最大的迭代次数为止。

3 实验结果

3.1 PSO_PE算法在Weka平台上的实现

Weka[7]作为一个公开的数据挖掘工作平台,集合了大量能承担数据挖掘任务的机器学习算法,包括对数据进行预处理、分类、回归、聚类、关联规则以及在新的交互式界面上的可视化。Weka提供了贝叶斯网络分类器搜索算法的抽象父类供实验者继承,在这个抽象类的基础上,很容易能实现自己的算法。该类在包.seareh下,类名为SearchAlgorithm,该类是一个抽象的类。该类有一个抽象子类在包.seareh.global下,类名为GlobalScoreSearchAlgorithm,PSO_PE搜索算法就是继承了这个GlobalScoreSearchAlgorithm抽象子类。PSO_PE算法能够设置相应的参数,设置参数的方法是固定的,Weka平台已经做好了相应的接口,继承并实现该接口就行,接口的名称为OPtionHandler,该接口有setoptions、getoptions、listoptions 3个方法,其作用分别是设置分类器参数、获取当前分类器设置的参数以及给出当前分类器所有能设置的参数列表。下面列出关键的成员变量和成员方法。PSO_PE算法与遗传算法类似,是一种迭代搜索算法,PSO_PE算法的终止条件是满足最大迭代次数。