[人工智能]机器学习强基计划4-4：详解半朴素贝叶斯分类AODE原理(附Python实现)

0 写在前面

机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。

🚀详情：机器学习强基计划(附几十种经典模型源码合集)

1 独依赖假设

在机器学习强基计划4-3：详解朴素贝叶斯分类原理 | 例题分析 | Python实现中我们介绍了朴素贝叶斯之所以“朴素”，是因为其给定了很强的属性独立性假设。然而，属性独立性假设在实际上很难成立，因此引入半朴素贝叶斯分类器(Semi-Na?ve Bayes Classifier)，其核心思想是：适当考虑部分属性的相互依赖，从而既简化了联合概率计算，又不至于彻底忽略属性间的强依赖关系。

半朴素贝叶斯分类器最常见的建模策略是独依赖估计(One-Dependent Estimator, ODE)，即假设每个属性在类别外最多依赖于一个属性

$$f^{?}\left(\mathbf{x}\right)=\underset{C\in \mathcal{Y}}{\mathrm{argmax}}P\left(C\right)\prod _{i=1}^{d}P\left(x_i|C,p{a}_i\right)$$

其中$p{a}_i$为属性$x_i$所依赖的父属性。若对$?x_i$确定了其$p{a}_i$，则可按朴素贝叶斯的方式进行贝叶斯分类，因此问题的核心转换为如何确定$p{a}_i$。

另一个问题是，可以假设属性依赖多个父属性吗？答案是：高阶依赖估计的准确性要求训练样本随指数级增加，在有限样本条件下，一般不适合采用。

2 AODE原理

先介绍一个比较直接的想法——假设所有属性都依赖于同一个父属性，称该属性为超父(super-parent)，这种半朴素贝叶斯分类器称为SPODE(Super-Parent ODE)算法。

$$f^{?}\left(\mathbf{x}\right)=\underset{C\in \mathcal{Y}}{\mathrm{argmax}}P\left(C\right)\prod _{i=1}^{d}P\left(x_i|C,pa\right)$$

建立在SPODE的基础上，AODE(Averaged ODE)算法是一种基于集成学习机制、更为强大的ODE分类器，其将每个属性作为超父构造SPODE，再加权计算各属性间的平均依赖，即

$$f^{?}\left(\mathbf{x}\right)=\underset{C\in \mathcal{Y}}{\mathrm{argmax}}\sum _{i=1,|{\mathbf{D}}_{x_i}|?m}^{d}P\left(C,x_i\right)\prod _{j=1}^{d}P\left(x_j|C,x_i\right)$$

其中${\mathbf{D}}_{x_i}$为第$i$属性上取值为$x_i$的样本子集，$m$默认设为30。类似地，AODE的拉普拉斯平滑修正为

$$?\begin{array}{l}P\left(C,x_i\right)=\frac{|{\mathbf{D}}_{C,x_i}|+1}{|\mathbf{D}|+N\times N_i}\\ P\left(x_j|C,x_i\right)=\frac{|{\mathbf{D}}_{C,x_i,x_j}|+1}{|{\mathbf{D}}_{C,x_i}|+N_j}\end{array}$$

简单说，AODE就是SPODE的加权平均版本

接下来基于上述原理开始编程，并和朴素贝叶斯分类做个比较，看性能有没提升

3 Python实现

3.1 计算类先验概率

'''
* @breif: 计算类先验概率P(C, xi)
* @param[in]: None
* @retval: None

{
    C1: { 
            超父属性(只能是离散属性)
            pa1: {
                    超父属性值
                    px1: {
                            p: p(C1, x1)
                            N: n(C1, x1)
                        }
                    ...
                    pxn: ...
                    num(pa1): int 属性a1的可取值数
                }
            ...
            pan: ...
        }
    ...
    Cn: ...
    num: 类别数
}

'''    
def calPrior(self):
    # 可选的类别数
    label = np.unique(self.y)
    self.prior['num'] = len(label)

    # 计算先验概率
    for _label in label:
        self.prior[_label] = {}
        # 获取标签取值_label的样本集
        labelIndex = np.squeeze(np.argwhere(np.squeeze(self.y)==_label))
        labelX = self.X[:, labelIndex]           
        # 超父特征层
        for i in range(self.d):
            # 属性i的可选属性值列表
            attr = np.unique(self.X[i, :])
            # 可选属性数
            attrNum = len(attr)
            # 离散属性(只有离散属性能作为超父属性)
            if attrNum <= 0.85 * self.m:
                self.prior[_label][str(i)] = {}
                self.prior[_label][str(i)]['num'] = attrNum
                # 计算每个取值的联合先验概率
                for a in attr:
                    self.prior[_label][str(i)][a] = {}
                    n = int(sum(labelX[i, :] == a))
                    self.prior[_label][str(i)][a]['p'] = (n + self.laplace) / (self.m + self.prior['num'] * attrNum)
                    self.prior[_label][str(i)][a]['N'] = n

3.2 计算属性后验概率

'''
* @breif: 计算属性后验概率P(xj|C, xi)
* @param[in]: None
* @retval: None

{
    C1: { 
            超父属性(只能是离散属性)
            pa1: {
                    超父属性值
                    px1: {
                            常规属性
                            a1: {
                                    type: discrete 离散属性
                                    x1: p(x1)
                                    ...
                                    xn: p(xn)
                                    num(a1): int 属性b1的可取值数
                                }
                            a2: {
                                    type: continous 连续属性
                                    mean: 样本均值
                                    std: 标准差
                                }
                        }
                    ...
                    pxn: ...
                }
            ...
            pan: ...
        }
    ...
    Cn: ...
    num: 类别数
}

'''
def calPosterior(self):
    if not self.prior:
        raise ValueError("please calculate prior first!")
    # 可选的类别数
    label = np.unique(self.y)
    self.posterior['num'] = len(label)

    # 标签层
    for _label in label:
        self.posterior[_label] = {}
        # 获取标签取值_label的样本集
        labelIndex = np.squeeze(np.argwhere(np.squeeze(self.y)==_label))
        labelX = self.X[:, labelIndex]
        
        # 超父特征层
        for pa, paDict in self.prior[_label].items():
            self.posterior[_label][pa] = {}

            # 超父属性值层
            for paVal, paValDict in paDict.items():
                if isinstance(paValDict, dict):
                    self.posterior[_label][pa][paVal] = {}

                    # 常规属性层
                    for i in range(self.d):
                        # 常规属性为超父属性则跳过
                        if i == pa:
                            continue

                        # 获取超父属性值为paVal的样本子集
                        paIndex = np.squeeze(np.argwhere(labelX[int(pa), :]==paVal))
                        paLabelX = labelX[:, paIndex].reshape(self.d, -1)
                        _, mpa = paLabelX.shape

                        self.posterior[_label][pa][paVal][str(i)] = {}
                        # 属性i的可选属性值列表
                        attr = np.unique(self.X[i, :])
                        # 可选属性数
                        attrNum = len(attr)
                        # 离散属性
                        if attrNum <= 0.85 * self.m:
                            self.posterior[_label][pa][paVal][str(i)]['num'] = attrNum
                            self.posterior[_label][pa][paVal][str(i)]['type'] = 'discrete'
                            # 计算每个取值的后验概率
                            for a in attr:
                                n = int(sum(paLabelX[i, :] == a))
                                self.posterior[_label][pa][paVal][str(i)][a] = \
                                    (n + self.laplace) / (self.prior[_label][pa][paVal]['N'] + attrNum)
                        # 连续属性
                        else:
                            self.posterior[_label][pa][paVal][str(i)]['type'] = 'continous'
                            # 发生的概率足够大，才会产生足够的样本
                            if mpa > 1:
                                self.posterior[_label][pa][paVal][str(i)]['std'] = paLabelX[i, :].std(ddof=1)
                                self.posterior[_label][pa][paVal][str(i)]['mean'] = paLabelX[i, :].mean()
                            else:
                                self.posterior[_label][pa][paVal][str(i)]['std'] = self.sigmaEpi
                                self.posterior[_label][pa][paVal][str(i)]['mean'] = 0

3.3 预测

采用机器学习强基计划2-3：图文详解决策树预剪枝、后剪枝原理+Python实现的数据集训练，获得准确率如下

model = AODE(X, y)
# 训练模型
model.train()
# 模型预测
predictY = model.predict(X)
print("错误:", np.sum(predictY!=y.T), "个\n准确率为:", np.sum(predictY==y.T)/y.size)

>>> 错误: 0 个
>>> 准确率为: 1.0

而在机器学习强基计划4-3：详解朴素贝叶斯分类原理 | 例题分析 | Python实现中准确率只有83.2%，可见适当的依赖性假设有助于提高分类准确率

完整代码联系下方博主名片获取

🔥 更多精彩专栏：

• 《ROS从入门到精通》
• 《机器人原理与技术》
• 《机器学习强基计划》
• 《计算机视觉教程》
• …