现实中的决策树模型之日常吃饭

决策树

决策树是一种基本的分类与回归方法，决策过程中提出的每一个判定问题都是对某一个属性的“测试”，每个测试结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围在上次决策结果的限定范围之内。决策树学习的目的是 为了产生一颗泛化能力强，即处理未见示例能力强的决策树。决策树图形如下图所示决策树在分类问题中，表示基于特征对实例进行分类的过程，可以认为它是if-then规则，也可以认为他是定义在特征空间与类空间上的条件概率分布

假设给定训练数据集 $$\mathbf{D}=\{({\mathbf{x}}_1,{\mathbf{y}}_1),({\mathbf{x}}_2,{\mathbf{y}}_2),\cdots ,({\mathbf{x}}_{\mathbf{N}},{\mathbf{y}}_{\mathbf{N}})\}$$ 其中，${\mathbf{x}}_{\mathbf{i}}=({\mathbf{x}}_{\mathbf{i}}^{(1)},{\mathbf{x}}_{\mathbf{i}}^{(2)},\cdots ,{\mathbf{x}}_{\mathbf{i}}^{(\mathbf{n})}{)}^{\mathbf{T}}$ 为输入实例，也叫做特征向量，$\mathbf{n}$ 为特征个数，${\mathbf{y}}_{\mathbf{i}}\in \{1,2,\cdots ,\mathbf{K}\}$ 为类标记，$\mathbf{i}=1,2,\cdots ,\mathbf{N}$，$\mathbf{N}$为样本容量。

以去食堂吃饭为例：

它的特征空间分布如下图：

在上例中特征向量的维数为2，也就是只有两个判断特征，那么它的特征空间就是二维平面的，类别数也只有两个：去吃饭和吃nm，其中 ${\omega }_1,{\omega }_2$ 为实例的两个类别（去吃饭和吃nm），假定特征 ${\mathbf{x}}_1$ 的阈值为 ${\mathbf{ϵ}}_1$ ，特征 ${\mathbf{x}}_2$ 的阈值为 ${\mathbf{ϵ}}_2$ ，根据阈值将特征空间划分为几个部分

上图就是本人每天去食堂的心理决策图，可以看出先进行决断的指标是在我看来最重要的，也就是在我心中占比最大的，之后的指标的重要程度一层层降低。这在决策树中也是一样的，这些指标在决策树中被称为规则。

特征选择

计算机通过一些特别的算法能理解数据中所蕴含的知识信息，这些数据被称为特征，划分数据集中实例的规则就是从这些特征中选出来。那么在数据集中实例的特征会有一些对划分实例有比较重要的作用，有一些特征对于划分实例没什么作用，那么就会产生一些问题。

数据集哪个特征在划分数据分类时起决定作用？

为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征，使杂乱无章的数据变得更加有序，原始数据集被划分为几个数据子集。

这些数据子集会分布在第一个决策点的所有分支上，如果某个分支下的数据属于同一个类型，则无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复分割数据子集的过程，划分数据子集的算法和划分原始数据集的算法相同，直到所有具有相同类型的数据均在一个数据子集。

如何判断划分的子集属于父集？

首先引入一个概念信息增益（在划分数据集之前之后信息发生的变化），可以使用信息论量化度量信息的内容。

信息熵

一条信息的信息量与其不确定性有着直接的联系。例如：我们要搞清楚一件不确定的的事，一无所知的事，就需要大量的信息，相反如果对某件事了解较多，则不需要太多的信息就能把它搞清楚。从这个角度来看，可以认为，信息量等于不确定性的多少。系统不确定性越多，信息熵就越大。信息熵表示为：$$\mathbf{E}\mathbf{n}\mathbf{t}(\mathbf{D})=-\sum _{\mathbf{k}=1}^{\mathbf{K}}{\mathbf{p}}_{\mathbf{k}}{\log }_2({\mathbf{p}}_{\mathbf{k}})$$单位是比特（bit） $\mathbf{K}$ 表示数据集中有 $\mathbf{K}$个类别，${\mathbf{p}}_{\mathbf{i}}$表示第 $\mathbf{i}$ 类样本在样本集合 $\mathbf{D}$ 中所占比例为

信息论中的冗余度：表示信息重复的指标，重复的信息越多，信息量就越小，冗余度就越高。

条件熵

在阅读的过程中，我们联系上下文去理解某段话的深层次的含义，这是个寻找相关信息的过程。事实证明，“相关的”信息也能够消除不确定性

现在假设X和Y是两个随机变量。Y是我们想要了解的，它的熵是$$\mathbf{H}(\mathbf{X})=-\sum _{\mathbf{i}=1}^{\mathbf{n}}\mathbf{p}({\mathbf{x}}_{\mathbf{i}})\log \mathbf{p}({\mathbf{x}}_{\mathbf{i}})$$

而且我们还知道Y和X一起出现的概率，也就是X，Y的联合概率分布$$\mathbf{p}(\mathbf{X}={\mathbf{x}}_{\mathbf{i}},\mathbf{Y}={\mathbf{y}}_{\mathbf{i}})={\mathbf{p}}_{\mathbf{i}\mathbf{j}},\mathbf{i}=1,2,...,\mathbf{n};\mathbf{j}=1,2,...,\mathbf{n}$$以及在X取不同值的情况下Y的概率分布，在数学上称为条件概率分布，则定义在X的条件下的条件熵为：$$\begin{array}{rl}H(Y\mid X)& =\sum _{x\in X}p(x)H(Y\mid X=x)\\ & =-\sum _{x\in X}p(x)\sum _{y\in Y}p(y\mid x)\log p(y\mid x)\\ & =-\sum _{x\in X}\sum _{y\in Y}p(x,y)\log p(y\mid x)\end{array}$$

互信息

互信息是两个随机事件“相关性”的量化度量，即判断两个随机事件是否存在相关性

互信息定义：$$\begin{array}{rl}I(X;Y)& =H(X)-H(X\mid Y)\\ & =H(X)+H(Y)-H(X,Y)\\ & =\sum _{x}p(x)\log \frac{1}{p(x)}+\sum _{y}p(y)\log \frac{1}{p(y)}-\sum _{x,y}p(x,y)\log \frac{1}{p(x,y)}\\ & =\sum _{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}\end{array}$$

相对熵（交叉熵）

相对熵也用来衡量相关性，但与互信息不同，它是用来衡量两个取值为正数的函数的相似性

结论：

对于两个完全相同的函数，它们的相对熵等于零相对熵越大，两个函数差异越大：反之，相对熵越小，两个函数差异越小对于概率分布或概率密度函数，如果取值均大于零，相对熵需要指出的是相对熵是不对称的

信息增益（ID3的做法）

在划分数据集之后信息发生的变化称为信息增益，注意：信息熵只与样本类别有关，与样本特征无关。

定义：$$\mathbf{E}\mathbf{n}\mathbf{t}(\mathbf{D})=-\sum _{\mathbf{k}=1}^{\mathbf{K}}\frac{|{\mathbf{C}}_{\mathbf{k}}|}{|\mathbf{D}|}{\log }_2(\frac{|{\mathbf{C}}_{\mathbf{k}}|}{|\mathbf{D}|})$$ $$\begin{array}{rl}Gain(D,a)& =Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\\ & =-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2(\frac{|C_k|}{|D|})+\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_I|}\end{array}$$

${\mathbf{C}}_{\mathbf{k}}$表示 $\mathbf{k}$ 个类，$|{\mathbf{C}}_{\mathbf{k}}|$表示类${\mathbf{C}}_{\mathbf{k}}$的样本个数

特征属性 $\mathbf{a}$ 的 $\mathbf{n}$ 个可能的取值：$\{{\mathbf{a}}^1,{\mathbf{a}}^2,\cdots ,{\mathbf{a}}^{\mathbf{n}}\}$

根据特征 $\mathbf{a}$的取值将集合 $\mathbf{D}$ 划分为$\{{\mathbf{D}}_1,{\mathbf{D}}_2,\cdots ,{\mathbf{D}}_{\mathbf{n}}\}$

${\mathbf{D}}_{\mathbf{i}\mathbf{k}}$ 表示子集 ${\mathbf{D}}_{\mathbf{i}}$ 中属于类 ${\mathbf{C}}_{\mathbf{k}}$ 的样本个数

$|\mathbf{D}|$ 表示样本空间的个数，$|{\mathbf{D}}_{\mathbf{i}\mathbf{k}}|$ 表示对于集合 $\mathbf{D}$中取值为

一般地，熵与条件熵的差就是互信息，也就说互信息就是信息增益

增益率（C4.5的做法）

实际上，信息增益准则对可取值数目较多的特征属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优化分属性。 $$增益率=\frac{特征属性的信息增益}{该特征属性的香农熵}$$

ID3算法实现

我们将对每个特征划分数据集的结果计算一次信息增益，然后判断哪个特征划分数据集是最好的划分方式。

训练数据集 $\mathbf{D}$，特征集 $\mathbf{A}$ 以及阈值为$\mathbf{ϵ}$

先遍历取出训练集中的特征计算出所取出的特征的每种取值下划分出的子集的条件熵用全集的信息熵减去所取出特征计算出的条件熵就可以得到该特征的信息增益（互信息）最后将所有特征计算出来的信息增益排序，选取信息增益最大的那个特征 ${\mathbf{A}}_{\mathbf{g}}$如果这个信息增益最大的特征的信息增益小于阈值$\mathbf{ϵ}$，则将数据集中的所有实例划分为一个结点，将数据集实例数最多的类作为该节点的类标记如果这个特征的信息增益大于阈值，就根据该特征下的几种不同的取值，对数据集进行划分，将数据集分为若干个非空子集 ${\mathbf{D}}_{\mathbf{i}}$ ，将 ${\mathbf{D}}_{\mathbf{i}}$ 中实例数最大的类作为标记，构建子节点对第 $\mathbf{i}$ 个子节点，以 ${\mathbf{D}}_{\mathbf{i}}$ 为训练集，以 $\mathbf{A}-\{{\mathbf{A}}_{\mathbf{g}}\}$ 为特征集，递归地调用1~6步骤，得到子树

注意： 如果训练集 $\mathbf{D}$ 中所有实例属于同一类则将该训练集中的实例归结的单个节点，并将该类作为该节点的类标记；

递归结束条件：$\mathbf{A}=\varnothing$ 当特征集为空时将训练集中的所有实例归结为一个节点，并将训练集中实例数最多的类作为该节点的类标签

剪枝处理

剪枝(pruning)是决策树学习算法对付 “过拟合” 的主要手段

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会导致决策树分支过多，这时就会导致因训练样本学习得“太好”，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合，因此，可通过主动去掉一些分支来降低过拟合的风险。

预剪枝（prepruning）

是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化能力的提升，则停止划分并将当前节点标记为终止节点。

预剪枝会导致决策树很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间的开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝（post-pruning）

是先从训练集中生成一颗完整的决策树，然后自底向上地对特征判断节点进行判断，若该结点对应的子节点能带来决策树的泛化能力提升，则将该子树替换为终止节点。

一般情形下，后剪枝决策树欠拟合的风险很小，泛化能力往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树后进行的，并且要自底向上地对树中所有非终止节点进行逐一考查，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

决策树的剪枝

决策树递归产生的二叉树，对训练数据的分类非常准确，但是对于未知的测试数据的分类却没有那么准确，即出现过拟合的现象，为了解决这个问题就要考虑决策树的复杂度，对已生成的决策树进行简化，因此要对递归生成的决策树进行剪枝处理。

决策树的剪枝一般通过最小化决策树整体的损失函数或代价函数来实现

设决策树 $T$ 的终止节点个数为 $\left|T\right|$ ，$t$ 为树 $T$ 的终止节点，该终止节点上有 $N_t$ 个样本点，其中 $k$ 类样本点有 $N_{tk}$ 个，$k=1,2,\cdots ,K$，$H_t(T)$ 为终止节点 $t$ 上的经验熵，$\alpha \ge 0$ 为参数

经验熵是熵和条件熵中的概率由数据估计（如：极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵 计算公式为：$$H_{\alpha }(T)=-\sum _K\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$

决策树的损失函数：$$\begin{array}{rl}{C}_{\alpha }(T)& =\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\alpha \left|T\right|\\ & =-\sum _{t=1}^{|T|}\sum _{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}+\alpha \left|T\right|\end{array}$$ 记：$$C(T)==-\sum _{t=1}^{|T|}\sum _{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}$$ 则：$$C_{\alpha }(T)=C(T)+\alpha \left|T\right|$$

其中$C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$\left|T\right|$表示模型复杂度，参数$\alpha \ge 0$ 的作用是控制两者（模型复杂度和模型与训练数据的拟合程度）之间的影响，较大的 $\alpha$会促使选择较简单的模型（树），较小的 $\alpha$会促使选择较复杂的模型（树）。$\alpha =0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当 $\alpha$ 确定的条件下，选择损失函数最小的模型。当 $\alpha$ 确定时子树越大，往往与训练数据的拟合程度越好，但模型的复杂度就越高；子树越小，模型的复杂度就越小，但往往和训练数据的拟合程度就越差

剪枝函数的最小化相当于正则化的极大似然估计

剪枝的过程：

计算每个终止节点的经验熵递归地从决策树的终止节点向上回缩。假如一个父节点下的终止节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 和 $T_A$ ，其对应的损失函数值分别为 $C_{\alpha (T_B)}$ 和 $C_{\alpha (T_A)}$ ，如果$$C_{\alpha (T_A)}\le C_{\alpha (T_B)}$$ 则说明终止节点回缩到其父节点之后的模型（树）比未回缩前的模型（树）更好回到2，直到不能继续为止，得到损失函数最小的子树$T_{\alpha }$

决策树的剪枝算法可以由一种动态规划的算法实现

连续值与缺失值

现实学习任务中常会遇到连续属性，连续属性可能是一系列没有明确意义的字，因此连续属性的可取值数目不再有限，所以不能直接根据连续属性的可取值来对结点进行划分。现实任务中常会遇到不完整的样本，即样本的某些属性值缺失，尤其是当属性数目较多的情况下，往往会有大量的样本出现缺失值。如果简单地放弃不完整的样本，仅使用无缺失值的样本来进行学习，显然是对数据极大的浪费。

连续值的处理

此时连续属性离散化的技术就派的上用场了，最简单的方法就是采用二分法(bi-partition)对连续属性的可取值范围进行处理，给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，找到这些值的中点，以中值为基础将这些值划分为两个部分，一部分在中值的左边，一部分在中值的右边，因为在这些值中，对相邻的取值来说，在相邻取值区间内取任意值所产生的划分结果相同。因此我们可考查这些相邻点的之间区间内的点，对于连续属性的可取值范围可以将其划分为n-1个小区间，这样就可以像离散属性值一样来考察这些细分的小区间。

二分法处理连续值：有 $n$ 个连续值就会划分为 $n-1$ 个小区间

缺失值的处理

在遇到含缺失值的样本数据的时候，有必要考虑利用有缺失属性值的样本数据来进行学习。 这时，我们需要解决两个问题： 1.如何在特征值缺失的情况下进行划分特征值的选择？（在选择结点的情况下面对含缺失值的样本的处理方式） 2.给定划分特征，若样本在该特征上的值缺失，如何对样本进行划分？（即究竟要把含缺失值的样本划分到哪个结点里）

比较发现，“纹理”在所有属性中的信息增益值最大，因此，“纹理”被选为划分属性，用于对根节点进行划分。划分结果为：“纹理=稍糊”分支：{7,9,13,14,17}，“纹理=清晰”分支：{1,2,3,4,5,6,15}，“纹理=模糊”分支：{11,12,16}。如下图所示：

那么问题来了，编号为{8,10}的样本在“纹理”这个属性上是缺失的，该被划分到哪个分支里？前面讲过了，这两个样本会同时进入到三个分支里，只不过进入到每个分支后权重会被调整（前面也说过，在刚开始时每个样本的权重都初始化为1）。编号为8的样本进入到三个分支里后，权重分别调整为5/15，7/15 和 3/15；编号为10的样本同样的操作和权重。因此，经过第一次划分后的决策树如图所示：

我们都知道构造决策树的过程是一个递归过程，原来不打算继续介绍递归过程了，但是因为权重发生了变化，所以继续介绍下递归过程。接下来，递归执行“纹理=稍糊”这个分支，样本集D = {7，8，9，10，13，14，17}，共7个样本。如下图所示：

下面来看具体的计算过程：

对比能够发现属性“敲声”的星系增益值最大，因此选择“敲声”作为划分属性，划分后的决策树如下图所示：

结点{9,14,17}因为包含的样本全部属于同一类别，因此无需划分，直接把结点{9,14,17}标记为叶结点，如下图所示：

根据递归过程，接下来对分支“敲声 = 浊响”即结点{7，8，13}进行划分，计算过程和上面一样，虽然我也算过了，但是不再贴出来了，需要注意的是样本的权重是1/3。计算完比较能够知道属性“脐部”的信息增益值最大，因此选择“脐部”作为划分属性，划分完的决策树如下图所示：

接下来，继续，对于结点{13}，因为就一个样本了，直接把该结点标记为叶结点，类别为“坏瓜”；递归到结点{7，8}，因为样本类别相同，所以也标记为叶结点，类别为“好瓜”；递归到结点“脐部=平坦”，因为这个结点不包含任何样本为空集，因此，把该结点标记为叶结点，类别设置为父节点中多数类的类别，即为“好瓜”。因此“纹理=稍糊”这颗子树构造完毕，如下图所示：

接下来，只需递归的重复上述过程即可，即能训练出一颗完整的决策树，最终的决策树如下图所示:

多变量决策树

若把样本中的每个特征看作是坐标空间中的一个坐标轴，则 $n$ 个特征描述的样本就对应了 $n$ 维空间中的一个数据点，对样本分类则意味着在这个特征空间中找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个特征取值。但在学习任务的真实分类边界比较复杂时，必须使用很多段才能获得较好的近似。