之前我们实现了一个 Node 基类CvDNode和一个 Tree 基类CvDBase；为了评估决策树模型的表现、我们需要先在这两个基类的基础上根据不同的算法实现出各种具体的决策树。由于我们在基类里面已经完成了绝大部分工作、所以在其上进行扩展是平凡的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class ID3Node(CvDNode):
    def __init__(self, *args, **kwargs):
        CvDNode.__init__(self, *args, **kwargs)
        self.criterion = "ent"
class C45Node(CvDNode):
    def __init__(self, *args, **kwargs):
        CvDNode.__init__(self, *args, **kwargs)
        self.criterion = "ratio"
class CartNode(CvDNode):
    def __init__(self, *args, **kwargs):
        CvDNode.__init__(self, *args, **kwargs)
        self.criterion = "gini"
        self.is_cart = True

在CvDBase的基础上定义三种算法对应的 Tree 结构的方法是类似的：

1
2
3
4
5
6
7
8
9
10

class ID3Tree(CvDBase, ID3Node, metaclass=CvDMeta):
    pass
class C45Tree(CvDBase, C45Node, metaclass=CvDMeta):
    pass
class CartTree(CvDBase, CartNode, metaclass=CvDMeta):
    pass

其中

1
2
3
4
5
6
7
8
9
10
11
12

class CvDMeta(type):
    def __new__(mcs, *args, **kwargs):
        name, bases, attr = args[:3]
        _, _node = bases
        def __init__(self, whether_continuous=None, max_depth=None, node=None, **_kwargs):
            tmp_node = node if isinstance(node, CvDNode) else _node
            CvDBase.__init__(self, whether_continuous, max_depth, tmp_node(**_kwargs))
            self._name = name
        attr["__init__"] = __init__
        return type(name, bases, attr)

接下来就是具体的评估与相应的可视化

本篇文章会叙述琴生不等式（Jensen’s Inequality）及其一个简单的应用，为此我们需要知道凸函数的概念：

• 若函数$f(x)$对$\forall p\in [0,1]$、都满足： $$pf\left( x_{1} \right) + \left( 1 - p \right)f\left( x_{2} \right) \leq f\left( px_{1} + \left( 1 - p \right)x_{2} \right)$$ 则称$f(x)$为凸函数（有时又叫上凸函数）

琴生不等式是针对凸函数提出的，下面就具体说一下其内容与证明

• 决策树是从直观上很好理解的模型，可以把它理解为一个划分规则的序列
• 决策树常用的生成算法包括：
  • ID3 算法，它使用互信息作为信息增益的度量
  • C4.5 算法，它使用信息增益比作为信息增益的度量
  • CART 算法，它规定生成出来的决策树为二叉树、且一般使用基尼增益作为信息增益的度量
• 决策树常用的剪枝算法有两种，它们都是为了适当地降低模型复杂度、从而期望模型在未知数据上的表现更好
• 决策树的代码实现从始到终都贯彻着递归的思想，可以说是递归的一个经典应用

朴素贝叶斯（Naive Bayes）是贝叶斯分类器的一种，而后者是一个相当宽泛的定义，它背后的数学理论根基是相当出名的贝叶斯决策论（Bayesian Decision Theory）。贝叶斯决策论和传统的统计学理论有着区别，其中最不可调和的就是它们各自关于概率的定义。因此，使用了贝叶斯决策论作为基石的贝叶斯分类器，在各个机器学习算法所导出的分类器中也算是比较标新立异的存在

由于朴素贝叶斯这一块能够扯到的理论还是相当多的，我们会把内容分成数学理论部分与程序实现部分，观众老爷们可以按需阅读 ( σ’ω’)σ

以下是目录：

• 贝叶斯决策论
• 参数估计
• 朴素贝叶斯算法
• 框架的实现
• MultinomialNB 的实现
• GaussianNB 的实现
• MergedNB 的实现
• 推导与推广
• “朴素贝叶斯”小结

贝叶斯决策论是在概率框架下进行决策的基本方法之一、更是统计模式识别的主要方法之一。从名字也许能看出来，贝叶斯决策论其实是贝叶斯统计学派进行决策的方法。为了更加深刻地理解贝叶斯分类器，我们需要先对贝叶斯学派和其决策理论有一个大致的认知

无论是贝叶斯学派还是频率学派，一个无法避开的问题就是如何从已有的样本中获取信息并据此估计目标模型的参数。比较有名的“频率近似概率”其实就是（基于大数定律的）相当合理的估计之一，本章所叙述的两种参数估计方法在最后也通常会归结于它

首先要叙述朴素贝叶斯算法的基本假设：

• 独立性假设：假设单一样本$X_i$的 n 个维度$X_i^{(1)},...,X_i^{(n)}$彼此之间在各种意义上相互独立

这当然是很强的假设，在现实任务中也大多无法满足该假设。由此会衍生出所谓的半朴素贝叶斯和贝叶斯网，这里先按下不表

然后就是算法。我们打算先只叙述它的基本思想和各个公式，相关的定义和证明会放在后面的文章中。不过其实仅对着接下来的公式敲代码的话、就已经可以实现一个朴素贝叶斯模型了：

• 基本思想：后验概率最大化、然后通过贝叶斯公式转换成先验概率乘条件概率最大化
• 各个公式（假设输入有 N 个、单个样本是 n 维的、一共有 K 类：$c_1,...,c_K$）
  • 计算先验概率的极大似然估计： $$\hat p(y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N},k=1,2,...,K$$
  • 计算条件概率的极大似然估计： $$\hat p(x^{(j)}=a_{jl}|y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}$$ 其中样本$x_i$第 j 维$x_i^{(j)}$的取值集合为$\{a_{j1},...,a_{jS_j}\}$
• 得到最终的分类器： $$y=f(x^*)=\arg\max_{c_k}\hat p(y=c_k)\prod_{i=1}^n\hat p(x^{(i)}=x^{*(i)}|y=c_k)$$

在朴素贝叶斯算法思想下、一般来说会衍生出以下三种不同的模型：

• 离散型朴素贝叶斯（MultinomialNB）：所有维度的特征都是离散型随机变量
• 连续型朴素贝叶斯（GaussianNB）：所有维度的特征都是连续型随机变量
• 混合型朴素贝叶斯（MergedNB）：各个维度的特征有离散型也有连续型

接下来就简单（并不简单啊喂）讲讲朴素贝叶斯的数学背景。由浅入深，我们会用离散型朴素贝叶斯来说明一些普适性的概念，连续型和混合型的相关定义是类似的

（本文会用到的所有代码都在这里）

对于我个人而言、光看这么一个框架是非常容易摸不着头脑的
毕竟之前花了许多时间在数学部分讲的那些算法完全没有体现在这个框架中、取而代之的是一些我抽象出来的和算法无关的结构性部分……
虽然从逻辑上来说应该先说明如何搭建这个框架，但从容易理解的角度来说、个人建议先不看这章的内容而是先看后续的实现具体算法的章节
然后如果那时有不懂的定义、再对照这一章的相关部分来看
不过如果是对朴素贝叶斯算法非常熟悉的观众老爷的话、直接看本章的抽象会引起一些共鸣也说不定 ( σ’ω’)σ

（本文会用到的所有代码都在这里）

本文主要介绍离散型朴素贝叶斯——MultinomialNB 的实现。对于离散型朴素贝叶斯模型的实现，由于核心算法都是在进行“计数”工作、所以问题的关键就转换为了如何进行计数。幸运的是、Numpy 中的一个方法：bincount就是专门用来计数的，它能够非常快速地数出一个数组中各个数字出现的频率；而且由于它是 Numpy 自带的方法，其速度比 Python 标准库collections中的计数器Counter还要快上非常多。不幸的是、该方法有如下两个缺点：

• 只能处理非负整数型中数组
• 向量中的最大值即为返回的数组的长度，换句话说，如果用bincount方法对一个长度为 1、元素为 1000 的数组计数的话，返回的结果就是 999 个 0 加 1 个 1

所以我们做数据预处理时就要充分考虑到这两点

（本文会用到的所有代码都在这里）

本文主要介绍连续型朴素贝叶斯——GaussianNB 的实现。在有了实现离散型朴素贝叶斯的经验后，实现连续型朴素贝叶斯模型其实只是个触类旁通的活了