树增强朴素贝叶斯分类算法
一、树增强朴素贝叶斯理论基础
朴素贝叶斯分类模型假设描述属性之间相互独立，这个假设在实际应用中往往是不成立的，这给正确分类带来了一定影响。
1997
年Fredman等人在朴素贝叶斯分类算法的基础上提出了树增强朴素贝叶斯分类算法（TAN），允许各个描述属性之间形成树形结构。也就是说，在贝叶斯网中，结点C（对应类别属性）和结点A1，A2，…，An（对应描述属性）由有向边相连，结点C是A1，A2，…，An的父结点，此外，A1，A2，…，An之间由有向边相连并形成树。
对每个输入变量节点，最多允许存在两个父节点，其中一个为输出变量节点，另一个为输入变量节点。节点Ai到节点Aj之间的有向弧表示输入变量Ai对输出变量C的影响作用，不仅取决于变量自身，还取决于变量Aj。
可以利用条件互信息描述在给定类别属性C时，描述属性A1、A2、…、An之间的依赖强度。
在给定离散随机变量Z时，离散随机变量X和Y之间的条件互信息定义为：
条件互信息体现了在给定Z条件下，变量X提供了多少关于变量Y的信息。条件互信息的值越小，表示变量X和变量Y的相关性越弱，值越大，相关性越强。
在树增强朴素贝叶斯分类中，如果通过分析训练样本集，得到了各个描述属性之间的树型结构，就可以估计类条件概率，从而可以得到新样本的类别。
当输入训练集S时，树增强朴素贝叶斯的计算过程，可以描述如下：
①扫描S，计算在给定类别属性C时，描述属性A1、A2、…、An之间的条件互信息；
②
构造一个无向完全图，以描述属性为结点，以条件互信息为边的权重；
④在上述最大生成树中选择一个描述属性结点为根结点，将所有边的方向设置成由根结点指向外，把无向图转换成有向树（不能含有回路）；
⑤在上述有向树中添加结点C和C到各个描述属性结点A1、A2、…、An的有向边，得到贝叶斯网。
训练集S中类别属性为“购买计算机”，描述属性个数n=4，由这些描述属性对应的结点构成一个无向完全图。再由S求得各条件互信息如下：
即，年龄与收入之间的条件互信息的值最大，贝叶斯网中由年龄这一节点指向收入，收入与学生之间的条件互信息的值最大，贝叶斯网中由收入这一节点指向学生，信誉与年龄间的条件互信息的值最大，贝叶斯网中由年龄这一节点指向信誉。最终得到如下贝叶斯图：
标签:
