贝叶斯网络 1

贝叶斯网络

一、贝叶斯网络

贝叶斯网络是用来表示变量之间概率依赖关系的图形模型，它描述的是一组随机变量

X={X1, ,Xn}所遵从的联合概率分布，并通过一组条件概率来指定一组条件独立性假设。贝

叶斯网络可以表示为B

=，它由两部分组成：

(1) 网络结构图G：是一个有向无环图DAG，图中的所有节点分别对应随机变量

X1, ,Xn，有向边

Xi的父结

表示变量间的直接依赖关系，体现了领域知识定性方面的特征。在有向无环图G中，给定点，每个

Xi独立于它的非后继结点；

(2) 局部概率分布

Θ：是与每个变量Xi关联的局部概率分布的集合，Θ中的元素是给定每个变量Xi

|Val(Parent(Xi)))表(CPT)，其中，Parent(Xi)表

的父节点，该节点取不同值的条件概率P(xi示图G中

Xi的父节点集。CPT体现了领域知识定量方面的特征。

图

给出其双亲节点FamilyHistory(FH)和Smoke(S)

的每个可能值组合的条件概率

图2.1给出医疗诊断的贝叶斯网络示意图。在图2.1的六个节点中，FamilyHistory和Smoker表示可

能引起疾病的两个原因，LungCancer和Emphysema代表两种疾病，PositiveXRay 和Dyspnea代表疾病可能产生的症状。两个节点之间的有向边表示两个节点存在依赖关系，如Smoker可能是患LungCancer的原因。

由上可见，贝叶斯网络是一种表示数据变量间潜在关系的定性与定量相结合的方法，它采用图形结构表示一组条件独立声明，并用条件概率表的数据值刻画变量间的依赖强度。

由概率的链规则可得：

P(X1, ,Xn)=∏P(Xi|X1,X2, ,Xi-1)

i=1

n

(1)

对于任一变量使得

Xi，通常可以找到一个与Xi都不独立的最小子集Parent(Xi)⊆{X1,X2, ,Xi-1}，

P(Xi|X1,X2, ,Xi-1)=P(Xi|Parent(Xi))

因此，当网络变量元组

n

n

X1, ,Xn>赋予具体数据值时，贝叶斯网络的联合概率

P(x1, ,xn)=∏P(xi|Val(Parent(Xi)))=∏θxi|Val(Parent(Xi))

i=1

i=1

(2)

为了在某个应用领域建立贝叶斯网络，通常需要完成以下3个内容：

(1) 确定领域变量及其所有可能值：在领域专家的指导下，确定应用问题中所有可能的观测值，并选择其

中值得建立模型的观测值子集，最后将观测值子集组织成互不相交的变量。

(2) 确定贝叶斯网络的结构：通过专家指定或数据学习确定变量之间的依赖关系，建立一个表示条件独立

断言的有向无环图。由于对于任意变量

Xi

，都可以找到一个最小子集

Parent(Xi)⊆{X1,X2, ,Xi-1}，Parent(Xi)中的变量与变量Xi之间存在依赖关系，因此，

为了决定贝叶斯网络的结构，需要完成：①将所有变量足式(2)的父节点集

X1,X2, ,Xn按某种次序排序；②确定满

Parent(Xi) (i=1 ,2 ,… ,n)。

|Parent(Xi))：

(3) 确定贝叶斯网络的参数：指定或学习得到局部概率P(xi

显然，第(2)和第(3)步是构造贝叶斯网络的关键，以上各步可能会交叉进行，而不是简单的顺序进行可以完成的。

通常，确定贝叶斯网络的结构和参数有以下三种方式：

①由领域专家根据经验知识确定贝叶斯网络的结构和参数，早期的贝叶斯网络构造大多采用这种方式。这种方式适合于问题领域的复杂性不高，变量很少且关系清晰的应用领域；

②由领域专家根据经验知识确定贝叶斯网络的结构，而网络的参数通过机器学习算法从大量训练数据中学习得到。这种方式适合于领域变量之间的依赖关系比较明显，但对领域变量之间依赖关系的依赖程度不是特别清楚的情况。

③贝叶斯网络的结构和参数都是通过机器学习算法从大量训练数据中学习得到。这种方法是由数据驱动的，特别适合于可利用的领域数据量较大，而对领域知识难以完全掌握的情况。

二、贝叶斯网络参数学习

从数据中学习已知网络结构的参数，实质上是学习网络结构中每个节点的概率分布表。根据样本数据的观测情况，参数学习可分两种情况：完整数据的参数学习和不完整数据的参数学习。完整数据集中的每个实例都具有完整的观测数据，不完备数据集是指对某些实例的观测有部分缺值或观测异常的情况。

完整数据的参数学习主要有最大似然估计、贝叶斯统计方法。

不完整数据的参数学习，一般需要采用一些近似的方法，如Monte-Carlo方法，Gaussian逼近，以及用梯度下降方法和EM算法求ML或MAP等。

最大似然估计MLE采用传统的统计方法，其基本思想是根据数据样本与模型参数的似然程度来判断数据样本与贝叶斯网络模型的拟和程度，似然程度通过似然函数来度量。

定义 似然函数

N个随机样本

x1,x2, ,xN

的似然函数是N个随机样本的联合概率

l(θ)=P(D|θ)=P(x1,x2, ,xN|θ)

，这个概率可以看成是

θ

的函数。具体地说，若

x1,x2, ,xN是独立地抽自某个分布的样本，那么，似然函数表示为：

l(θ)=P(x1,x2, ,xN|θ)=P(x1|θ)p(x2|θ) p(xN|θ)

最大似然估计就是已知一组数据样本x1,x2, ,xN，估计该样本集最可能来自于哪个分布函数，即在参数空间中

Θ

ˆ)或似然函数的对数logl(中找到一个θ值(用θˆ表示)，它能使似然函数l(θ

ˆ)极θ

大化。

已知贝叶斯网络的结构，根据似然函数的公式，贝叶斯网络似然函数的对数可以表示为：

log(PD|Θ,G)=

xi,∏xi

∑

xi,Va(Parentl(iX))

Nloθg

i

x|ParentVa(l

i( X

如果令

∏xi=Val(Parent(Xi))，则上式中的Nxi,∏xi

的实例个数，

表示样本数据中

Xi=xi

以及

Parent(Xi)=Val(Parent(Xi))

θx|∏

i

xi

是

Xi

的局部分布的参数。显然，

当

θx,∏=Nx,∏

i

xi

i

xi

N∏x

i

时，上式取得最大值，其中

N∏x

i

是样本集中

Parent(Xi)=Val(Parent(Xi))的实例个数。

三、贝叶斯网络结构学习

贝叶斯网络的结构学习是从由n个节点组成的所有网络结构中，利用可得到的领域数据，选择最准确地逼近数据集潜在概率分布的网络结构。

根据观察贝叶斯网络的视角不同，可以将学习贝叶斯网络结构的方法分为两类：基于计分的方法和基于相关性分析的方法。下面主要介绍基于计分的学习方法

基于计分的学习方法把贝叶斯网络看成是对属性变量的联合概率分布进行编码的结构，学习的目的是在贝叶斯网络空间，搜索与训练数据集拟合最好的网络结构。目前，人们常常采用启发式方法来确定最佳网络结构。一般的方法是给出评价网络结构的计分函数，使用启发式搜索方法构造一个模型，然后用计分函数评估该模型，搜索和评估过程一直进行到新模型的计分值不是明显地比前一个模型的计分值更好为止。因此，基于计分的结构学习算法主要由两部分组成：计分函数和相应的搜索算法。

1．评分函数

评分函数是给出具体网络结构下，联合分布的一种概率度量，常用的计分函数有

: 基于贝叶斯统计的BDe计分方法

基于Kullback-Leibler熵的方法

基于最小描述长度原则MDL的方法 2．搜索算法

搜索算法是在众多的可选网络结构中，找出计分值最高的网络结构。Robinsin推导出包含n个节点的贝叶斯网络可能个数的递推计算公式：

⎛n⎫i(n-i)

f(n)=∑(-1) ⎪2f(n-i)

i=1⎝i⎭

n

i+1

当n=2时，可能的网络个数是3；n=3时，可能的网络个数是25；n=5时，可能的网络个数是29000；n=10时，可能的网络个数近似为4.2⨯10

18

。一般地，当n增加时，可能的网络结构以超指数的速度

增长。

因此，无法采用穷举法来确定最佳贝叶斯网络的结构，一般需要使用启发式搜索算法。常用的启发式搜索方法有迭代爬山法、首次最优搜索、模拟退火以及Gibb抽样等。

启发式搜索算法主要包括以下步骤： (1) 选定初始的网络模型；

(2) 用选定的计分函数评估网络模型的每一个可能的变化，并选出使数据集和网络模型的取最大值的变化；

(3) 用选出的变化对网络模型进行修正。

(4) 重复步骤(2)(3)，直至联合概率分布不能继续增加为止。

步骤(1)中网络的初始模型可以是空网、随机网络、先验网络等。步骤(2)(3)是搜索算法的核心，不同搜索算法的区别主要体现在这两个步骤。

K2是典型的基于计分的学习算法，计分函数采用贝叶斯计分。K2算法假定所有节点按一定要求排

4

O(mnr)（m是实例序，并且所有结构的先验概率是相等的。在这两个假设下，K2的时间复杂度是

数，n是节点数，r是每个节点可能取值的最大个数）。

四、贝叶斯网络分类器

1、朴素贝叶斯分类器

朴素贝叶斯模型是一种简单的概率模型，该模型假设：给定一个实例的类值，实例中每个属性的出现独立于实例中其它属性的出现。这个独立性假设，使朴素贝叶斯方法相对于其它方法有一个独特之处，即：它不需要搜索，只需简单地计算训练例中各个属性值发生的频率数，就可以估计出模型中每个属性的参数。因此，朴素贝叶斯最大的特点是高效性和健壮性。由于该模型这一突出特点，使得朴素贝叶斯受到广泛地重视，并成功地应用于分类、聚类以及模型选择等数据挖掘的任务中。

令U

={X1,X2, ,Xn,C}是离散随机变量的有限集，其中X1,X2, ,Xn是属性变量，类

xi=(x1,x2, ,xn)属于类cj

的概率，可由贝叶斯定理表

变量C的取值范围为{c1,c2, ,cl}。实例

示为：

P(cj|x1,x2, ,xn)=

其中α

P(x1,x2, ,xn|cj)⋅P(cj)

P(x1,x2, ,xn)

n

=α⋅P(cj)⋅∏P(xi|x1,x2, ,xi-1,cj)

i=1

=P(x1,x2, ,xn)是独立于类值的常数。由于朴素贝叶斯的属性独立性假设，每个属性类条件

P(cj|x1,x2, ,xn)=α⋅P(cj)⋅∏P(xi|cj)

i=1n

独立于其它属性，只有一个类节点作为其父节点，因此，

根据最大后验准则MAP，贝叶斯分类器选择使后验概率P(cj

的类标签。所以，朴素贝叶斯分类器可表述为

|x1,x2, ,xn)最大的类作为新实例

CNaive=argmaxP(cj)⋅∏P(xi|cj)

cj∈C

i=1

n

因此，要对一个实例分类，不需要任何搜索过程，只需要根据某种策略，从训练数据集中学习两组参数值：先验概率P

(cj)

属性变量

朴素贝叶斯分类器的模型结构图

2、TAN分类器

TAN是一种树增强的朴素贝叶斯网络模型，其基本思想是在朴素贝叶斯模型的基础上，在属性之间添加若干增强弧，并且保持增强弧连同属性节点构成树状结构。TAN将贝叶斯网络表示依赖关系的能力与朴素贝叶斯的简易性相结合，是学习的效率与准确地描述属性间相关性之间一个很好的折衷。

对于TAN模型结构，具有以下的限定条件：

类变量是根，没有父结点，即Parent(C)=φ；

类变量是每个属性变量的父结点，即C∈Parent(Xi) (i 属性变量

=1,2, ,n)；

Xi除了类变量C

作为其父结点外，最多有一个其它属性变量作为其父结点，即

Parent(Xi)≤2。

因此，实例

x=(x1,x2, ,xn)属于类cj的概率，可由TAN分类器表示为：

c

*TAN

=argmaxP(cj)⋅∏P(xi|Val(Parent(Xi)))

cj∈{c1, ,cl}

i=1

n

上式中的

Val(Parent(Xi))

或者是

P(xi|cj)

或者是

P(xi|xk,cj)

，其中

xk∈{x1,x2,

,xi-1

TAN分类器的模型结构图

与朴素贝叶斯分类器不同，TAN分类器需要有构造模型结构的学习算法，目前有两种典型的TAN学习算法：

利用条件互信息构造TAN分类器的算法；

选择使分类正确率改进最大的弧作为TAN的增强弧。

算法 Distribution_Based算法

(1) 计算每一对属性之间的条件互信息，I(Xi;Xj

属性变量

|C)，i≠j。

P(xi,xj|c)

i

j|c)

I(Xi,Xj|C)=

xi,xj,c

∑P(x,x,c)logP(x|c)P(x

i

j

(2) 构造一个完全无向图，图中每个顶点是属性

权值为I(Xi;Xj

X1,X2, ,Xn，在连接Xi和Xj的边上标记

|C)。

(3) 构造最大加权生成树。

(4) 通过选择一个根变量，在每条边上添加方向，将由此生成的无向树转换为有向树。 (5) 增加一个节点C，增加从C到每个

算法 Classification_Based算法

(1) 将贝叶斯网络初始化为朴素贝叶斯分类器。 (2) 评估当前分类器。

(3) 在当前分类器中添加每条合法的弧。

(4) 如果存在可以改进分类器分类性能的弧，则选择使分类性能改进最大的弧，添加到当前分类器

Xi的弧，构造一个TAN模型。

中，并转向(2)；否则返回当前分类器。

在现有的限定性贝叶斯网络分类器中，从分类性能、效率以及时空复杂度等方面综合考虑，TAN分类器是目前公认的适用范围较广且综合性能较好的贝叶斯分类器。 3、贝叶斯网络分类器

令U

={X1,X2, ,Xn,C}是离散随机变量的有限集，其中X1,X2, ,Xn是属性变量，类

变量C的取值范围为{c1,c2, ,cl}。用贝叶斯网络分类器对实例最可能的类值为

n

x=(x1,x2, ,xn)分类，x

CBN=argmaxP(cj)⋅∏P(xi|parent(xi),cj)

cj∈C

i=1

对贝叶斯网络分类器的参数学习问题而言，其目标函数并不是与似然估计直接相关，而是与条件似然估计紧密相关，因此，为了得到准确的分类器，应该使条件对数似然函数取最大值。根据文(Friedman et al. 1997)，对数似然函数LL与条件对数似然函数CLL的关系如下：

j

LLG(θ|D)=CLLG(θ|D)+∑logPθ(x)

j=1N

其中

jCLLG(θ|D)=∑logP(c|x) θ

j=1N

ˆ(c,x)logP(c|x)=N∑PDθ

x∈X

c∈C

(3)

如果贝叶斯网络结构能够描述数据的真实结构，那么使LLG最大的参数必然也使CLLG最大。但是，在实际中，得到的贝叶斯网络结构可能是不正确的，ML学习不能保证使CLL取最优值，这将导致次优的分类决策。

因此，为了得到准确的分类器，应该直接优化条件似然度，即直接对式(3)进行最优化，当下式成立时式(3)取最大值。

θcθx|pa(x)

ˆ(c|x)P=Pθ(c|x)=D

θθccx|pa(x)

但是，对于贝叶斯网络分类器，上式无法表示为对数线性形式，没有闭型解。直接最优化需要的计算

量非常大。因此，经常采用最优化技术进行求解。

梯度法和共轭梯度法是传统的最优化方法，（Greiner and Zhou 2002）提出的ELR方法采用梯度下降和线性搜索来直接使CLL计分最大；（Grossman and Domingos 2004）采用共轭梯度法使CLL计分最大，来学习贝叶斯网络的参数。与梯度下降法相比，共轭梯度法具有更好的收敛性能。

（Jing et al. 2008）集成方法也可以看作是一种优化方法，尽管它的优化原理尚没有理论上公认的解释。Jing等人将AdaBoost技术用于贝叶斯网络参数学习，其基本思路是通过基分类器的集成，实现贝叶斯网络参数的优化。

五、应用 1、推理 2、文本分类

贝叶斯网络

一、贝叶斯网络

贝叶斯网络是用来表示变量之间概率依赖关系的图形模型，它描述的是一组随机变量

X={X1, ,Xn}所遵从的联合概率分布，并通过一组条件概率来指定一组条件独立性假设。贝

叶斯网络可以表示为B

=，它由两部分组成：

(1) 网络结构图G：是一个有向无环图DAG，图中的所有节点分别对应随机变量

X1, ,Xn，有向边

Xi的父结

表示变量间的直接依赖关系，体现了领域知识定性方面的特征。在有向无环图G中，给定点，每个

Xi独立于它的非后继结点；

(2) 局部概率分布

Θ：是与每个变量Xi关联的局部概率分布的集合，Θ中的元素是给定每个变量Xi

|Val(Parent(Xi)))表(CPT)，其中，Parent(Xi)表

的父节点，该节点取不同值的条件概率P(xi示图G中

Xi的父节点集。CPT体现了领域知识定量方面的特征。

图

给出其双亲节点FamilyHistory(FH)和Smoke(S)

的每个可能值组合的条件概率

图2.1给出医疗诊断的贝叶斯网络示意图。在图2.1的六个节点中，FamilyHistory和Smoker表示可

能引起疾病的两个原因，LungCancer和Emphysema代表两种疾病，PositiveXRay 和Dyspnea代表疾病可能产生的症状。两个节点之间的有向边表示两个节点存在依赖关系，如Smoker可能是患LungCancer的原因。

由上可见，贝叶斯网络是一种表示数据变量间潜在关系的定性与定量相结合的方法，它采用图形结构表示一组条件独立声明，并用条件概率表的数据值刻画变量间的依赖强度。

由概率的链规则可得：

P(X1, ,Xn)=∏P(Xi|X1,X2, ,Xi-1)

i=1

n

(1)

对于任一变量使得

Xi，通常可以找到一个与Xi都不独立的最小子集Parent(Xi)⊆{X1,X2, ,Xi-1}，

P(Xi|X1,X2, ,Xi-1)=P(Xi|Parent(Xi))

因此，当网络变量元组

n

n

X1, ,Xn>赋予具体数据值时，贝叶斯网络的联合概率

P(x1, ,xn)=∏P(xi|Val(Parent(Xi)))=∏θxi|Val(Parent(Xi))

i=1

i=1

(2)

为了在某个应用领域建立贝叶斯网络，通常需要完成以下3个内容：

(1) 确定领域变量及其所有可能值：在领域专家的指导下，确定应用问题中所有可能的观测值，并选择其

中值得建立模型的观测值子集，最后将观测值子集组织成互不相交的变量。

(2) 确定贝叶斯网络的结构：通过专家指定或数据学习确定变量之间的依赖关系，建立一个表示条件独立

断言的有向无环图。由于对于任意变量

Xi

，都可以找到一个最小子集

Parent(Xi)⊆{X1,X2, ,Xi-1}，Parent(Xi)中的变量与变量Xi之间存在依赖关系，因此，

为了决定贝叶斯网络的结构，需要完成：①将所有变量足式(2)的父节点集

X1,X2, ,Xn按某种次序排序；②确定满

Parent(Xi) (i=1 ,2 ,… ,n)。

|Parent(Xi))：

(3) 确定贝叶斯网络的参数：指定或学习得到局部概率P(xi

显然，第(2)和第(3)步是构造贝叶斯网络的关键，以上各步可能会交叉进行，而不是简单的顺序进行可以完成的。

通常，确定贝叶斯网络的结构和参数有以下三种方式：

①由领域专家根据经验知识确定贝叶斯网络的结构和参数，早期的贝叶斯网络构造大多采用这种方式。这种方式适合于问题领域的复杂性不高，变量很少且关系清晰的应用领域；

②由领域专家根据经验知识确定贝叶斯网络的结构，而网络的参数通过机器学习算法从大量训练数据中学习得到。这种方式适合于领域变量之间的依赖关系比较明显，但对领域变量之间依赖关系的依赖程度不是特别清楚的情况。

③贝叶斯网络的结构和参数都是通过机器学习算法从大量训练数据中学习得到。这种方法是由数据驱动的，特别适合于可利用的领域数据量较大，而对领域知识难以完全掌握的情况。

二、贝叶斯网络参数学习

从数据中学习已知网络结构的参数，实质上是学习网络结构中每个节点的概率分布表。根据样本数据的观测情况，参数学习可分两种情况：完整数据的参数学习和不完整数据的参数学习。完整数据集中的每个实例都具有完整的观测数据，不完备数据集是指对某些实例的观测有部分缺值或观测异常的情况。

完整数据的参数学习主要有最大似然估计、贝叶斯统计方法。

不完整数据的参数学习，一般需要采用一些近似的方法，如Monte-Carlo方法，Gaussian逼近，以及用梯度下降方法和EM算法求ML或MAP等。

最大似然估计MLE采用传统的统计方法，其基本思想是根据数据样本与模型参数的似然程度来判断数据样本与贝叶斯网络模型的拟和程度，似然程度通过似然函数来度量。

定义 似然函数

N个随机样本

x1,x2, ,xN

的似然函数是N个随机样本的联合概率

l(θ)=P(D|θ)=P(x1,x2, ,xN|θ)

，这个概率可以看成是

θ

的函数。具体地说，若

x1,x2, ,xN是独立地抽自某个分布的样本，那么，似然函数表示为：

l(θ)=P(x1,x2, ,xN|θ)=P(x1|θ)p(x2|θ) p(xN|θ)

最大似然估计就是已知一组数据样本x1,x2, ,xN，估计该样本集最可能来自于哪个分布函数，即在参数空间中

Θ

ˆ)或似然函数的对数logl(中找到一个θ值(用θˆ表示)，它能使似然函数l(θ

ˆ)极θ

大化。

已知贝叶斯网络的结构，根据似然函数的公式，贝叶斯网络似然函数的对数可以表示为：

log(PD|Θ,G)=

xi,∏xi

∑

xi,Va(Parentl(iX))

Nloθg

i

x|ParentVa(l

i( X

如果令

∏xi=Val(Parent(Xi))，则上式中的Nxi,∏xi

的实例个数，

表示样本数据中

Xi=xi

以及

Parent(Xi)=Val(Parent(Xi))

θx|∏

i

xi

是

Xi

的局部分布的参数。显然，

当

θx,∏=Nx,∏

i

xi

i

xi

N∏x

i

时，上式取得最大值，其中

N∏x

i

是样本集中

Parent(Xi)=Val(Parent(Xi))的实例个数。

三、贝叶斯网络结构学习

贝叶斯网络的结构学习是从由n个节点组成的所有网络结构中，利用可得到的领域数据，选择最准确地逼近数据集潜在概率分布的网络结构。

根据观察贝叶斯网络的视角不同，可以将学习贝叶斯网络结构的方法分为两类：基于计分的方法和基于相关性分析的方法。下面主要介绍基于计分的学习方法

基于计分的学习方法把贝叶斯网络看成是对属性变量的联合概率分布进行编码的结构，学习的目的是在贝叶斯网络空间，搜索与训练数据集拟合最好的网络结构。目前，人们常常采用启发式方法来确定最佳网络结构。一般的方法是给出评价网络结构的计分函数，使用启发式搜索方法构造一个模型，然后用计分函数评估该模型，搜索和评估过程一直进行到新模型的计分值不是明显地比前一个模型的计分值更好为止。因此，基于计分的结构学习算法主要由两部分组成：计分函数和相应的搜索算法。

1．评分函数

评分函数是给出具体网络结构下，联合分布的一种概率度量，常用的计分函数有

: 基于贝叶斯统计的BDe计分方法

基于Kullback-Leibler熵的方法

基于最小描述长度原则MDL的方法 2．搜索算法

搜索算法是在众多的可选网络结构中，找出计分值最高的网络结构。Robinsin推导出包含n个节点的贝叶斯网络可能个数的递推计算公式：

⎛n⎫i(n-i)

f(n)=∑(-1) ⎪2f(n-i)

i=1⎝i⎭

n

i+1

当n=2时，可能的网络个数是3；n=3时，可能的网络个数是25；n=5时，可能的网络个数是29000；n=10时，可能的网络个数近似为4.2⨯10

18

。一般地，当n增加时，可能的网络结构以超指数的速度

增长。

因此，无法采用穷举法来确定最佳贝叶斯网络的结构，一般需要使用启发式搜索算法。常用的启发式搜索方法有迭代爬山法、首次最优搜索、模拟退火以及Gibb抽样等。

启发式搜索算法主要包括以下步骤： (1) 选定初始的网络模型；

(2) 用选定的计分函数评估网络模型的每一个可能的变化，并选出使数据集和网络模型的取最大值的变化；

(3) 用选出的变化对网络模型进行修正。

(4) 重复步骤(2)(3)，直至联合概率分布不能继续增加为止。

步骤(1)中网络的初始模型可以是空网、随机网络、先验网络等。步骤(2)(3)是搜索算法的核心，不同搜索算法的区别主要体现在这两个步骤。

K2是典型的基于计分的学习算法，计分函数采用贝叶斯计分。K2算法假定所有节点按一定要求排

4

O(mnr)（m是实例序，并且所有结构的先验概率是相等的。在这两个假设下，K2的时间复杂度是

数，n是节点数，r是每个节点可能取值的最大个数）。

四、贝叶斯网络分类器

1、朴素贝叶斯分类器

朴素贝叶斯模型是一种简单的概率模型，该模型假设：给定一个实例的类值，实例中每个属性的出现独立于实例中其它属性的出现。这个独立性假设，使朴素贝叶斯方法相对于其它方法有一个独特之处，即：它不需要搜索，只需简单地计算训练例中各个属性值发生的频率数，就可以估计出模型中每个属性的参数。因此，朴素贝叶斯最大的特点是高效性和健壮性。由于该模型这一突出特点，使得朴素贝叶斯受到广泛地重视，并成功地应用于分类、聚类以及模型选择等数据挖掘的任务中。

令U

={X1,X2, ,Xn,C}是离散随机变量的有限集，其中X1,X2, ,Xn是属性变量，类

xi=(x1,x2, ,xn)属于类cj

的概率，可由贝叶斯定理表

变量C的取值范围为{c1,c2, ,cl}。实例

示为：

P(cj|x1,x2, ,xn)=

其中α

P(x1,x2, ,xn|cj)⋅P(cj)

P(x1,x2, ,xn)

n

=α⋅P(cj)⋅∏P(xi|x1,x2, ,xi-1,cj)

i=1

=P(x1,x2, ,xn)是独立于类值的常数。由于朴素贝叶斯的属性独立性假设，每个属性类条件

P(cj|x1,x2, ,xn)=α⋅P(cj)⋅∏P(xi|cj)

i=1n

独立于其它属性，只有一个类节点作为其父节点，因此，

根据最大后验准则MAP，贝叶斯分类器选择使后验概率P(cj

的类标签。所以，朴素贝叶斯分类器可表述为

|x1,x2, ,xn)最大的类作为新实例

CNaive=argmaxP(cj)⋅∏P(xi|cj)

cj∈C

i=1

n

因此，要对一个实例分类，不需要任何搜索过程，只需要根据某种策略，从训练数据集中学习两组参数值：先验概率P

(cj)

属性变量

朴素贝叶斯分类器的模型结构图

2、TAN分类器

TAN是一种树增强的朴素贝叶斯网络模型，其基本思想是在朴素贝叶斯模型的基础上，在属性之间添加若干增强弧，并且保持增强弧连同属性节点构成树状结构。TAN将贝叶斯网络表示依赖关系的能力与朴素贝叶斯的简易性相结合，是学习的效率与准确地描述属性间相关性之间一个很好的折衷。

对于TAN模型结构，具有以下的限定条件：

类变量是根，没有父结点，即Parent(C)=φ；

类变量是每个属性变量的父结点，即C∈Parent(Xi) (i 属性变量

=1,2, ,n)；

Xi除了类变量C

作为其父结点外，最多有一个其它属性变量作为其父结点，即

Parent(Xi)≤2。

因此，实例

x=(x1,x2, ,xn)属于类cj的概率，可由TAN分类器表示为：

c

*TAN

=argmaxP(cj)⋅∏P(xi|Val(Parent(Xi)))

cj∈{c1, ,cl}

i=1

n

上式中的

Val(Parent(Xi))

或者是

P(xi|cj)

或者是

P(xi|xk,cj)

，其中

xk∈{x1,x2,

,xi-1

TAN分类器的模型结构图

与朴素贝叶斯分类器不同，TAN分类器需要有构造模型结构的学习算法，目前有两种典型的TAN学习算法：

利用条件互信息构造TAN分类器的算法；

选择使分类正确率改进最大的弧作为TAN的增强弧。

算法 Distribution_Based算法

(1) 计算每一对属性之间的条件互信息，I(Xi;Xj

属性变量

|C)，i≠j。

P(xi,xj|c)

i

j|c)

I(Xi,Xj|C)=

xi,xj,c

∑P(x,x,c)logP(x|c)P(x

i

j

(2) 构造一个完全无向图，图中每个顶点是属性

权值为I(Xi;Xj

X1,X2, ,Xn，在连接Xi和Xj的边上标记

|C)。

(3) 构造最大加权生成树。

(4) 通过选择一个根变量，在每条边上添加方向，将由此生成的无向树转换为有向树。 (5) 增加一个节点C，增加从C到每个

算法 Classification_Based算法

(1) 将贝叶斯网络初始化为朴素贝叶斯分类器。 (2) 评估当前分类器。

(3) 在当前分类器中添加每条合法的弧。

(4) 如果存在可以改进分类器分类性能的弧，则选择使分类性能改进最大的弧，添加到当前分类器

Xi的弧，构造一个TAN模型。

中，并转向(2)；否则返回当前分类器。

在现有的限定性贝叶斯网络分类器中，从分类性能、效率以及时空复杂度等方面综合考虑，TAN分类器是目前公认的适用范围较广且综合性能较好的贝叶斯分类器。 3、贝叶斯网络分类器

令U

={X1,X2, ,Xn,C}是离散随机变量的有限集，其中X1,X2, ,Xn是属性变量，类

变量C的取值范围为{c1,c2, ,cl}。用贝叶斯网络分类器对实例最可能的类值为

n

x=(x1,x2, ,xn)分类，x

CBN=argmaxP(cj)⋅∏P(xi|parent(xi),cj)

cj∈C

i=1

对贝叶斯网络分类器的参数学习问题而言，其目标函数并不是与似然估计直接相关，而是与条件似然估计紧密相关，因此，为了得到准确的分类器，应该使条件对数似然函数取最大值。根据文(Friedman et al. 1997)，对数似然函数LL与条件对数似然函数CLL的关系如下：

j

LLG(θ|D)=CLLG(θ|D)+∑logPθ(x)

j=1N

其中

jCLLG(θ|D)=∑logP(c|x) θ

j=1N

ˆ(c,x)logP(c|x)=N∑PDθ

x∈X

c∈C

(3)

如果贝叶斯网络结构能够描述数据的真实结构，那么使LLG最大的参数必然也使CLLG最大。但是，在实际中，得到的贝叶斯网络结构可能是不正确的，ML学习不能保证使CLL取最优值，这将导致次优的分类决策。

因此，为了得到准确的分类器，应该直接优化条件似然度，即直接对式(3)进行最优化，当下式成立时式(3)取最大值。

θcθx|pa(x)

ˆ(c|x)P=Pθ(c|x)=D

θθccx|pa(x)

但是，对于贝叶斯网络分类器，上式无法表示为对数线性形式，没有闭型解。直接最优化需要的计算

量非常大。因此，经常采用最优化技术进行求解。

梯度法和共轭梯度法是传统的最优化方法，（Greiner and Zhou 2002）提出的ELR方法采用梯度下降和线性搜索来直接使CLL计分最大；（Grossman and Domingos 2004）采用共轭梯度法使CLL计分最大，来学习贝叶斯网络的参数。与梯度下降法相比，共轭梯度法具有更好的收敛性能。

（Jing et al. 2008）集成方法也可以看作是一种优化方法，尽管它的优化原理尚没有理论上公认的解释。Jing等人将AdaBoost技术用于贝叶斯网络参数学习，其基本思路是通过基分类器的集成，实现贝叶斯网络参数的优化。

五、应用 1、推理 2、文本分类