7.4 半朴素贝叶斯分类器

贝叶斯公式估计后验概率P(c I x) 困难，朴素贝叶斯分类器采用了属性条件独立性假设，现实任务中，人们尝试对属性条件独立性假设进行一定程度的放松，即产生“半朴素贝叶斯分类器”。基本思想是：适当考虑一部分属性问的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系"。

常用的策略是"独依赖估计"，就是假设每个属性在类别之外最多仅依赖于一个其他属性，则后验概率为：

 如果父属性pai已知，可估计P(xi | c,pai)，于是问题转化为 确定每个属性的父属性，不同的做法产生不同的做法产生不同的独依赖分类器。

SPODE (Super-Parent ODE)方法：假设所有属性都依赖于同一个属性，称为"超父"，然后通过交叉验证等模型选择方法来确定超父属性。

TAN (Tree Augmented naÏve Bayes)，是在最大带权生成树算法基础上，通过以下步骤将属性间依赖简化上图（c）树形结构，介绍一下最大带权生成树：

先解释最小生成树，kruskal算法（克鲁斯卡尔算法）查找最小生成树的方法，举个例子对一下网络查找最小生成树，

（1）将连通网中所有的边按照权值大小做升序排序

（2）从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。此例包含 6 个顶点的连通网，选择 5条边的最小生成树：

最大生成树算法和最小生成树算法几乎一样，只需要把最小生成树算法进行一点点改变，每一次选择的边是最大的边，然后再去判断这条边是否可以加入，那么这就是最大生成树的求取方法了。

回到TAN，简化步骤如下：

• 计算任意两个属'性之间的条件互信息：