贝叶斯分类器（二）

上篇文章介绍了贝叶斯决策论和朴素贝叶斯分类器，这篇文章会继续介绍半朴素贝叶斯分类器和贝叶斯网。

1.半朴素贝叶斯分类器

朴素分类器的一个很大的前提条件是：各属性条件独立。半朴素贝叶斯分类器是对该条件的放宽：考虑到一部分属性间存在相互依赖关系的情况。

1.1独估计依赖（One-Dependent Estimator）

独估计依赖就是指每个属性有 ≤1 个依赖属性，此时
P(c/x)∝∏i=1dP(xi/c,pai)(1)
pai 为 xi 所依赖的属性，称为父属性。对于给定 xi ,如何确定 pai 。经典的算法例如SPODE(Super-Parent ODE)和AODE(Averaged One-Dependent Estimator)都是选择所有属性的父属性为一个属性，称之为“超父”(super parent)。

SPODE(Super-Parent ODE)是通过交叉验证等模型选择的方法来选择超父属性，你可以认为它在一个一个属性的尝试作为超父属性，比较它们的效果，来最终选择出合适的一个属性来作为超父属性。
AODE(Averaged One-Dependent Estimator),average顾名思义，要均衡的照顾到各个属性作为超父属性的权利，皇帝轮流做，每个属性都做一次超父属性。
P(c/x)∝∑i=1,|Dxi|≥mdP(c,xi)∏j=1dP(xj/c,xi)
m的默认值为30

TAN(Tree Augmented naive Bayes)

TAN算法是引入了一个叫做条件互信息（conditional mutual information）的东东来表示两两属性之间的依赖程度，其计算公式为：
I(xi,xj/y)=∑xi,xj;c∈yP(xi,xj/c)logP(xi,xj/c)P(xi/c)P(xj/c) 。这样在一副图上用点表示所有的属性，两两连线形成边，条件互信息作为对应边的权重，则应该是一副完全图，如果按照此幅图，则任意一个属性的父属性应该有 d−1 个 。这显然与我们假设的仅有一个或者0个依赖属性不符。我们利用最大带权生成树(maximum weighted spanning tree，但网上资料比较少，其实原理与最小（生成）树原理一样)，设置为有向，这样就由完全图变为连通图，每个属性的父属性就仅有一个了。

2.贝叶斯网

贝叶斯网(Bayesian network)是一种有向无环图。用 B 来表示则 B=<G,Θ> 。其中G表示的是结构信息，即属性间的边如何相连，谁与谁连。只要我们明确了G，那么也就明确了各属性的条件概率 PB(xi/πi) 中的 πi 由哪些属性构成。 Θ 其实是 Θxi/πi 该参数是指各个 PB(xi/πi) 的值。

模型的训练

模型的训练其实是根据训练样本集 D 构建一个贝叶斯网的过程，从贝叶斯网的组成可以看出

• G 的确定
• Θ 的确定

贝叶斯网络–结构的确定

G 的确定已经被证明是一个NP难的问题，但可以讨论一下结构确定的思想，思想是为贝叶斯网络定义一个评分函数，
s(B/D)=f(θ)|B|−∑i=1mlogPB(xi)
f(θ) 表示的是一个参数所需要的字节数， |B| 表示该贝叶斯网络参数的个数。
虽然为NP难问题，我们可以找到近似解也是好的，一种是贪心法，另外一种是对贝叶斯网络的形状加以限定（如必须为树形）。

贝叶斯网络参数的确定

参数可以通过事件在训练数据上出现的频率来获得

推断

贝叶斯网络确定之后就相当于分类模型确定了下来，接下来就是用这个模型去做预测或者说是推断。
感觉机器学习里面没有什么问题不是NP难得，没错，推断又被人证明了为NP难问题。近似推断的方法有吉布斯采样和变分推断。这里详细介绍利用吉布斯采样来做推断的方法。为便于理解，我们以具体的例子来说明

贝叶斯网络构建如上图所示，我们已知证据 x3=响亮，x4=青绿，x5=硬挺 来判断是否为好瓜，是否甜
我们先构建一个样本（ x1,x2,x3=响亮,x4=青绿，x5=硬挺) ， x1和x2 此时可以随意制定初始值比如所好瓜，甜。
然后构建马尔科夫链，首先求P( x1 =好瓜/ x2 =甜， x3 =响亮, x4 =青绿， x5 =硬挺)和P( x1 =坏瓜/ x2 =甜， x3 =响亮, x4 =青绿， x5 =硬挺)的概率,比较二者谁的概率比较大，若前者概率较大，则 x1 的值替换为好瓜，若后者概率较大则 x1 的值替换为坏瓜。对 x2 执行同样的操作来确定 x2 的替换值。
这为第一次确定 x1 和 x2 的替换值。如此迭代T次，统计 x1 =好瓜， x2 =甜度在这T次试验迭代值中的出现的次数 n 。 P(好瓜，甜/响亮，青绿，硬挺) ≈nT