4 决策树

4.1 决策树/判定树

决策树（Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。
决策过程的每一次判定都是对某一属性的“测试”，决策最终结论则对应最终的判定结果。一般一颗决策树包含：一个根节点、若干个内部节点和若干个叶子节点，易知：
1. 每个非叶节点表示一个特征属性测试。
2. 每个分支代表这个特征属性在某个值域上的输出。
3. 每个叶子节点存放一个类别。
4. 每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集。
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的分治策略。
显然，决策树的生成是一个递归过程.在决策树基本算法中，有三种情形会导致递归返回
1. 当前结点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
3. 当前结点包含的样本集合为空，不能划分。
4. 在第2种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第3种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同：情形2是在利用当前结点的后验分布，而情形3则是把父结点的样本分布作为当前结点的先验分布。
决策树学习的关键是第8行，即如何选择最优划分属性。一般而言，我们希望决策数的分支结点的“纯度”越来越高。

4.2 决策树的构造

前置知识

信息熵：信息熵(information entropy)是度量样本结合纯度的常用指标，假定当前样本集合D中第k类样本所占比例为pk，则样本集合D的信息熵定义为：

Ent (D) = - \sum_{k = 1}^{| y |} p_{k} \log_{2} p_{k}

这里，值越大表示越混乱，而易知只有一个类别时，信息熵为0。（约定：当 $p = 0$ 时， $\log_{2} p = 0$ ）

条件信息熵：条件信息熵 $H (X | Y)$ 是在已知随机变量 $Y$ 的条件下，随机变量 $X$ 的不确定性：

H (X | Y) = - \sum_{y \in Y} P (y) \sum_{x \in X} P (X | Y) \log P (X | Y)

这里，p(x|y) 是在已知 Y 的值的情况下 X 取特定值的条件概率，而 p(y) 是 Y 取值的概率。这个公式考虑了所有 Y 的可能值，以及在每个 Y 的值下 X 的所有可能值。

信息增益：假定离散属性 $a$ 有 $V$ 个可能的取值，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支节点，其中第v个分支节点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^{v}$ 的样本，记为 $D^{v}$ 。信息增益是知道了某个条件后，事件的不确定性下降的程度。

Gain (D, a) = Ent (D) - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} Ent (D^{v})

信息增益越大，说明使用属性 $a$ 划分样本集 $D$ 所获得的纯度提升越大。

信息增益比：信息增益比（Gain Ratio）是一种用于选择最优划分属性的准则。它是对信息增益（Information Gain）的一种改进，解决了信息增益倾向于选择取值多的属性的问题。其计算公式如下：

GainRatio (D, a) = \frac{Gain (D, a)}{IV (a)}

其中，IV(a) 是属性 a 的固有值（Intrinsic Value），定义为：

IV (a) = - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} \log_{2} \frac{| D^{v} |}{| D |}

信息增益比的优点是对可取值数目较少的属性有所偏好，因此可以用来减小信息增益的倾向。

基尼指数：基尼指数（Gini index）是另一种常用的选择最优划分属性的准则。基尼指数是指在样本集合D中，随机抽取两个样本，其类别标记不一致的概率。基尼指数越小，样本集合纯度越高。

Gini (D) = \sum_{k = 1}^{| y |} \sum_{k^{'} \neq k} p_{k} p_{k^{'}} = 1 - \sum_{k = 1}^{| y |} p_{k}^{2}

属性a的基尼指数定义为：

GiniIndex (D, a) = \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} Gini (D^{v})

基尼指数越小，说明使用属性 $a$ 划分样本集 $D$ 所获得的纯度提升越大。于是，我们可以通过最小化基尼指数来选择最优划分属性。

4.3 剪枝

**过拟合 (Over-Fitting) **：从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合，即太依赖于训练样本。
**剪枝 (Pruning) **：决策树算法对付过拟合的主要手段。剪枝的策略有两种如下：
1. 预剪枝（pre-pruning）：在构造的过程中先评估，再考虑是否分支。
2. 后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。
评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。

上图分别表示不剪枝处理的决策树、预剪枝决策树和后剪枝决策树。预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。

4.4 连续与缺失值

连续值处理

现实学习任务中常会遇到连续属性，因此有必要讨论如何在决策树中使用连续属性。对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法，基本思想为：给定样本集 $D$ 与连续属性 $a$ ，二分法试图找到一个划分点t将样本集 $D$ 在属性 $a$ 上分为两个子集 ${D_{t}^{+}}, {D_{t}^{-}}$ 。其中， ${D_{t}^{+}}$ 包含那些在属性a上取值大于t的样本， ${D_{t}^{-}}$ 包含那些在属性a上取值不大于t的样本。
对于相邻属性取值的 $a^{i}, a^{i + 1}$ ，t在其左闭右开区间上取任意值所划分的结果相同。所以，我们可考察包含n-1个元素的候选划分点集合（取其中位点进行划分）。具体操作如下：
1. 首先将α的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1个，n为α所有的取值数目）。
2. 计算每一个划分点划分集合D（即划分为两个分支）后的信息增益。
3. 选择最大信息增益的划分点作为最优划分点。
我们有：

\begin{aligned} Gain (D, a) & = max_{t \in T_{a}} Gain (D, a, t) \\ = max_{t \in T_{a}} Ent(D) - \sum_{λ \in {-, +}} \frac{| D_{t}^{λ} |}{| D |} Ent (D_{t}^{λ}) \end{aligned}

需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理

现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需要解决两个问题：
1. 如何选择划分属性：若样本在属性a上的值缺失，我们如何选择划分属性？
2. 给定划分属性，若某样本在该属性上缺失值，如何划分到具体的分支上？
给定训练集D和属性a，并令 $\bar{D}$ 表示D中在属性a上没有缺失值的样本子集。假定为样本集中的每一个样本都赋予一个权重，根节点中的权重初始化为1，则定义
样本子集所占比例（无缺失值样本所占的比例）

ρ = \frac{\sum_{x \in \bar{D}} w_{x}}{\sum_{x \in D} w_{x}}

样本子集每个类别的比例（无缺失值样本中第k类所占的比例）

{\tilde{p}}_{k} = \frac{\sum_{x \in \bar{D}} w_{x}}{\sum_{x \in D} w_{x}}, (1 \leq k \leq | y |)

每个分支所含样本的比例（无缺失值样本中在属性a上取值 $a^{v}$ 的样本所占的比例）

{\tilde{r}}_{v} = \frac{\sum_{x \in {\bar{D}}_{v}} w_{x}}{\sum_{x \in D} w_{x}}, (1 \leq v \leq V)

其中， ${\tilde{p}}_{k}$ 和 ${\tilde{r}}_{v}$ 的总和均为1。

对于问题1，显然我们可以根据 $\bar{D}$ 来判断属性a的优劣。通过在样本集D中选取在属性a上没有缺失值的样本子集，计算在该样本子集上的信息增益，最终的信息增益等于该样本子集划分后信息增益乘以样本子集占样本集的比重。即：

\begin{aligned} Gain (D, a) & = ρ Gain (\bar{D}, a) \\ = ρ (Ent (D) - \sum_{v = 1}^{V} {\tilde{r}}_{v} Ent (D_{v})) \end{aligned}

对于问题2，若样本在划分属性上的取值已知，则划入相应的分支，样本权值不变；若样本在划分属性上的取值未知，则将该样本同时划入所有分支，并变更该样本的权重。

w_{x} \leftarrow w_{x} {\tilde{r}}_{v}

4.5 多变量决策树

多变量决策树：在决策树的构造过程中，我们通常是选择一个属性进行划分，但有时候多个属性的组合可能更好地划分数据集。多变量决策树就是考虑多个属性的组合来划分数据集的决策树。多变量决策树的构造过程与单变量决策树类似，只是在选择划分属性时，需要考虑多个属性的组合。
多变量决策树的构造：多变量决策树的构造过程与单变量决策树类似，只是在选择划分属性时，需要考虑多个属性的组合。具体地，我们可以考虑所有属性的组合，然后选择最优的属性组合进行划分。但是，由于属性组合的数量可能很大，因此我们通常采用启发式方法来选择属性组合。常用的启发式方法有：前向选择、后向选择和双向选择。
1. 前向选择：从空集开始，逐步添加属性，直到不能再添加属性为止。具体地，我们首先计算每个属性的信息增益，然后选择信息增益最大的属性作为第一个属性，然后逐步添加属性，直到信息增益不再增加。
2. 后向选择：从所有属性开始，逐步删除属性，直到不能再删除属性为止。具体地，我们首先计算每个属性的信息增益，然后选择信息增益最大的属性作为第一个属性，然后逐步删除属性，直到信息增益不再增加。
3. 双向选择：前向选择和后向选择的结合。具体地，我们首先计算每个属性的信息增益，然后选择信息增益最大的属性作为第一个属性，然后逐步添加属性，直到信息增益不再增加，然后逐步删除属性，直到信息增益不再增加。
多变量决策树的优缺点：多变量决策树的优点是可以更好地划分数据集，提高决策树的泛化性能。但是，多变量决策树的缺点是计算复杂度较高，因为需要考虑多个属性的组合。因此，多变量决策树通常用于数据集较小的情况。
多变量决策树的应用：多变量决策树在实际应用中有很多场景，例如：金融风控、医疗诊断、工业生产等。在这些场景中，多变量决策树可以更好地划分数据集，提高决策树的泛化性能。
其与传统的单变量决策树不同的是，在多变量决策树的学习过程中，不是为每一个非叶节点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

4 决策树 ​

4.1 决策树/判定树 ​

4.2 决策树的构造 ​

前置知识 ​

相关算法 ​

4.3 剪枝 ​

4.4 连续与缺失值 ​

连续值处理 ​

缺失值处理 ​

4.5 多变量决策树 ​