决策树
基本流程
决策数是一个受欢迎的机器学习方法。用二分类问题举例，我们可以认为任务是决定问题的回答：“这个例子是阳性的吗？”顾名思义，决策树让决策基于树的结构，这也尝尝是人类使用的决策机制。例如，为了回答这个问题：“这是个好瓜吗？”我们首先考虑他的颜色是什么，如果是绿色的然后考虑他的根部怎么样。如果根部是螺旋形的，那么要它敲击的声音如何？最后基于观察到的，我们决定那个西瓜是好瓜或者不是。这个决策过程如图4.1所示
决策过程结束时得到的结论代表着可能的分类，即好瓜和生瓜蛋子。在决策中的每个问题都是对特性的测试，比如颜色，和根部。例如，如果当前的决定是color =绿色，下一个测试根=?只考虑绿色西瓜。
典型的， 决策树由一个根节点，多个内部节点构成。由多个叶子节点。叶子节点对应着输出其他节点对应着特性测试。每个节点中的样本被根据拆分特征的结果被划分为子节点。每个从根节点到叶子节点的路径是决策序列。目标是产生一棵树来泛化预测位置的样例。决策树的结构遵循分而治之的策略（divide-and-conquer ）如图4.2
树是递归生成的，递归会在三种情况下停止。
- 当前节点的所有样例是一个类，无需进一步拆分
- 当前的特征集是空的，或者所有的样本有意义的特征，无法分割。
- 使用父类节点的概率作为当前节点的先验概率
划分选择
划分决策树的关键是第8行，选择一个最优的划分特性。一般来说，在划分处理过程中，我们希望每个节点中有更多的样例属于一个类，即增加每个节点的纯度（purity）。
信息增益
一种最常用度量信息纯度的方法是使用信息熵（information entropy,）或者样本熵，设pk代表着当前数据集D中的第k个类别，当k=1,2,3,4,|y|，那么，熵被定义为
信息熵是用来衡量随机变量不确定的一种方法.
公式中log2表示以2为敌的对数，因为在信息论中，信息通常用比特做单位。|Y|就是这些结果的总数，对每个类别k，pk表示类别的概率，也就是数据集中属于k类的数据占总数据比重.
这里，D 是一个数据集，而Y是这个数据集中所有可能的结果或类别的集合∣Y∣ 就是这些结果的总数,对于每个类别k,pk表示类别的概率,也就是数据集中k类数据占总数的比例.
$$ \text{Ent}(D) = -\sum_{k=1}^{|Y|} p_k \log_2 p_k.（4.1） $$
Ent(D)越低,D的纯度就越高。
假设离散特性a有v个可能的值$\{a^1, a^2,....a^V\}$。那么按特征a拆分数据集D，产生V个子节点。其中第v个子节点$D^v$包括了所有特征样值取为a值的$a^v$个样本，我们可以根据4.1计算出$D_v$的熵，因为在子节点有不同数量的样本，权重$|D^v|/|D|$是分配来反应每个节点的重要性，即，样本数越多，分支节点的影响越大。于是，可以计算出用于属性a对样本集D进行划分所获得的信息增益(information gain)
减号右边这部分表示，在使用特征a对数据集D进行划分后，所有子集的信息熵加权平均值
信息增益反应了特征的对于数据分类的贡献程度。特征A对数据集D进行划分后，不确定性（熵）的减少量。信息增益越大，表示特征A对数据集D的分类效果越好，因此在构建决策树时，通常会选择信息增益最大的特征作为分割点。
$$ Gain(D, a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v).（4.2） $$
一般来说，信息增益越高，则意味着使用属性a来进行划分所得的纯度提升越大。所以信息增益可以用于拆分选择，使用$a_*=\arg \max{a \in A Gain(D,a)}$。著名的决策树算法将信息增益作为选择分割的特征准则。
我们使用表4.1中具体的数据集为例。这个数据集包括了17个训练样本，它们被用来训练决策树分类器来预测未切西瓜的成熟度。
起初根节点包括了D中所有的样本，p1=8/17是正例，p2=9/17是反例，根据4.1根节点的熵为
$$ \text{Ent}(D) = -\sum_{k=1}^{2} p_k \log_2 p_k=-(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17})=0.998 $$
然后，我们需要计算当前特征集中{颜色，根，声音，纹理，脐，表面}中每个特征的信息增益。假设我们已经选择了颜色，它有三种可能的值{绿色，乌黑，浅白}如果D根据颜色切分，那么会有三个子集：D1(颜色=绿色)，D2(颜色=五黑),D3(颜色=浅白)
子集D1包括了6个样例{1,4,6,10,13,17}，p1中有3/6个正例，再p2汇总有3/6个反例。子集D2有6个样例{2, 3, 7, 8, 9, 15}p1=4/6个正例，p2=2/6个反例。子集D3中包括了五个样例{5, 11, 12, 14, 16}，p1=1/5个正例，p2=4/5个反例。根据1.4这三个子节点的熵为
$$ Ent(D^1) = -\left( \frac{3}{6} \log_2{\frac{3}{6}} + \frac{3}{6} \log_2{\frac{3}{6}} \right) = 1.000 \\ Ent(D^2) = -\left( \frac{4}{6} \log_2{\frac{4}{6}} + \frac{2}{6} \log_2{\frac{2}{6}} \right) = 0.918.\\ Ent(D^3) = -\left( \frac{1}{5} \log_2{\frac{1}{5}} + \frac{4}{5} \log_2{\frac{4}{5}} \right) = 0.722. $$
然后，利用式(4.2)计算颜色分割的信息增益为
$$ \begin{align} Gain(D, color) &= Ent(D) - \sum_{v=1}^{3} \frac{|D^v|}{|D|} Ent(D^v) \\ &= 0.998 - \left( \frac{6}{17} \times 1.000 + \frac{6}{17} \times 0.918 + \frac{5}{17} \times 0.722 \right) \\ &= 0.109. \end{align} $$
同样的，我们可以计算其他属性的信息增益
Gain(D, 根部) = 0.143; Gain(D, 敲声) = 0.141;
Gain(D, 纹理) = 0.381; Gain(D, 脐部) = 0.289;
Gain(D, 触感) = 0.006.
显然纹理对信息增益 最大，选择这个作为划分属性。图4.3展示了根据纹理作为根节点划分后的结果
然后使用决策树算法对于每个子节点做进一步的拆分。例如，第一个子节点（即纹理=清晰）包括了9个样例D1={1, 2, 3, 4, 5, 6, 8, 10, 15}，可选的资源集合为{颜色，根部，敲声，脐部，触感}
Gain(D1, 颜色) = 0.043; Gain(D1, 根部) = 0.458;
Gain(D1, 纹理) = 0.331; Gain(D1,脐部) = 0.458;
Gain(D1, 触感) = 0.458.
由于根，脐部，触感的增益最多，它们中的任何一个都可以被作为拆分特性。对每个节点重复这个流程，我们可以获得最终的决策树如图4.4所示
增益率
上述的过程有意的忽略了ID这一列。如果我们考虑将ID加入候选资源，那么根据4.3我们知道了信息增益是0.998，他比任何其他已知的特性都要大。这是合理的因为17产生17个节点，每个节点每个节点只有一个样例最为纯度最高的样品。然而这样的决策树没有泛化能力，不能有效的预测新样本。
结果表明，信息增益规则偏向那些有更多值的属性。为了减少这个偏差，我们使用了著名的决策树算法C4.5，它使用增益率(gain ratio)进行属性的选择而不是直接使用增益。采用与4.2相同的符号来表示属性的增益率被定义为
$$ Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}（4.3） $$
其中
$$ \begin{equation} IV(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}（4.4） \end{equation} $$
成为属性a的"固有值（intrinsic value）"当a有许多特征值是，IV可能会很大。以西瓜数据集2.0为例，我们有
IV(触感) = 0.874 (V = 2), IV(颜色) = 1.580 (V = 3), 还有IV(ID) = 4.088 (V = 17).
要注意的是，与信息增益相反，增益比偏向于具有较少可能值的特征。而是使用了一个启发式的方法：从信息增益高于平均值的候选特征集中选择增益比最高的特征。
基尼指数
CART决策树使用基尼指数来选择划分属性。使用的符号同4.1，数据集D的基尼值定义为
CART全称是分类回归树，他是著名的决策树算法，适用于分类和回归
$$ \begin{equation} Gini(D) = \sum_{k=1}^{|Y|}\sum_{k'\neq k}p_kp_{k'} = 1 - \sum_{k=1}^{|Y|}p_k^2.（4.5） \end{equation} $$
直觉上，Gini(D)代表了我们从数据集D中随机选择俩个样本属于不同类别的可能性。基尼指数越低，则数据集D纯度越高。使用类似4.2的表示法，特征a的基尼指数定义为：
简单来说俩个样本是同一种可能性的概率越高，数据集纯度就越高
$$ \begin{equation} Gini\_index(D, a) =\sum\limits_{v=1}^{V} \frac{{|D^v|}}{|D|} Gini(D^v)（4.6） \end{equation} $$
给定候选属性集A，我们选择最低的基尼指数的属性宅分数据集，即$\ a_*=\arg \min_{a \in A} \operatorname{Gini\_index}(D,a)$
减枝处理
减枝是策略树学习算法中处理过拟合的的主要策略。对于正确的分类俩个训练样本，学习器重复分割过程。然而如果他的分支过多，学习器可能会被训练样本的特性误导，错误的认为他们是潜在的真理，因此我们么可以减掉一些分支去防止过拟合。
基础的剪枝策略包括预剪枝和后剪枝（pre-pruning and post pruning）预剪枝评估每个切分的泛化能力的提升如果提升很小，则取消减枝，即该节点被标记为一个叶子节点。相比之下，后剪枝重新检查整个决策树的非叶子节点，如果替换节点可以提高泛化能力，那么则替换该节点。
我们如何知道节点的繁华能力有没有提升呢？我们可以使用2.2节介绍的绩效评估方法。例如我们可以用留出法留出一部分数据作为验证集进行性能的验证。给定的西瓜数据集2.0如表4.1所示。我们将样本随机划分为俩组，{1, 2, 3, 6, 7, 10, 14, 15, 16, 17}和验证集{4, 5, 8, 9, 11, 12, 13}如图4.2所示
假设我们使用4.2.1的信息增益标准去决定分类属性，图4.5展示了表4.2上数据集训练的决策树。为了便于讨论，我们对图中节点做了编号。
预减枝
让我们首先来看看预减枝。根据信息增益的准则，脐部可能成为划分训练集的三个分支，如图4.6，然而是否进行这个划分呢？预减枝是根据比较减枝前后的泛化能力来的。
在切分之前，所有的数据集都在根节点，当切分执行，根据算法4.2这个节点的第六行标记为叶子结点，其类别标记为训练样例最多的类别（即好瓜）。为了评估单个节点的决策树，使用表4.2中的验证集，我们有了样例{4,5,8}是正确的分类，其他是错误分类的。那么验证正确率是3/7x100%=42.9%。
在根据脐部划分根节点之前，样例要放置再三个子节点，如图4.6所示：节点2的样本为{1, 2, 3, 14},节点3的样本为{6, 7, 15, 17},节点4的样本为{10, 16}。我们标记这3个节点作为叶子节点，并将标签设置为多数类，即2是好瓜3是好瓜，4是坏瓜。那么验证准确率5/7x100%=71.4%>42.9。由于验证精度得到了提高，采纳使用脐部作为划分。
那之后，决策树算法继续拆分节点2基于信息增益准则选择颜色。然而，因为样例{5}在验证集中被错误分类，验证准确率下降到了57.1%。因此预减枝直接停止了切分节点2。对于节点3，最好的属性是根据根部切分。然而，因为验证正确率在切分之后还是一样的71.4%。预训练集停止切分了节点3。对于节点4，不需要切分，因为所有样例都属于一个类别。
最后，预减枝决策树基于表4.2的数据给出了图4.5，他的验证正确率是71.4%。因他只切分了一次，这样的决策树也叫决策树桩（decision stump.）
对比4.5和4.6的图，我们可以看到使用了预减枝减少了决策树的分支，我们减少的不只是过拟合风险还有训练和测试的计算代价。另一方面，虽然由于对泛化能力提高很小甚至是负提高的，一些分支被减枝阻止了，但是他们随后的分支仍然有可能造成显著的改变。这些树脂被剪枝是因为预先剪枝的贪婪性，这就可能引入了欠拟合的风险。
后剪枝
后剪枝通过让决策树先长大成为一颗完整的树，即图4.5展示了完全长大的决策树基于4.2的验证正确率为42.9%。
再图4.5，根据后剪枝节点6是第一个被检查的，如果以节点6为首的子树被剪枝替换为叶子节点，那么包括样例{7,15}和他们的标签都会被多数类设置为好瓜。由于验证精度提高到57.1%，所以进行剪枝，得到决策树，结果如。图4.7。
然后后剪枝检查节点5，如果由节点5为首的字数被替换成叶子结点，那么包括样例{6,7,15}和他们的标签会被设置成大多数的好瓜。因为验证正确率还是保持在57.1%， 不进行剪枝。
如果以节点2为首的子节点被替换成叶子节点，那么包括样例{1,2,3,14}它们的标签被设置为多数类的好瓜。因为验证集的准确率增加到了71.4%，执行减枝。
对于简洁点3和1替换它们验证准确率分别是71.4%和42.9%，俩种情况都没有导致提高，所以节点保持不变。
最后，后减枝决策树的结构使用了4.2数据集，给定了图4.7的结果，他的验证正确率提升到了71.4%
根据比较4.5和4.7，我们可以看到后剪枝相对于预减枝保留了更多的分支。事实上，与预减枝相比后剪枝不容易产生欠拟合，具有更好的泛化能力。然而训练时间后剪枝明显更长，因为他采用自底向上的策略来检查一颗生长完全的决策树中每一个没有叶子的节点
连续值和缺失值
连续值的处理
离散值：色子点数，血型（有有限集合中的成员）
连续值：体温，身高，温度（可以无限精确下去的值）
到目前为止我们的讨论仅限于离散属性，连续特征在现实也很常见，必须要知道如何将连续特征合并仅决策树。
我们不可以直接根据连续特征切分节点，因为他们值是无限的。离散化技术在这种情况下会派上用场。最简单的离散化策略是使用二分法，这正是c4.5决策树使用的机制。给定数据集D和连续属性a，假设在D中观测到n个a，我们升序排序这些值，记为{a1,a2,a3,...,an}.切分点为t，d被分割为俩个子集$D^-_t和D^+_t$，当$D^-_t$包括的样本不大于t，$D^+_t$包括的样本大于t。对于相邻的特征值$a^i和a^{i+1}$，t在区间$[a^i,a^{i+1})$中任意值所产生的划分结果相同。因此，对于连续属性a，在以下候选分裂点集合中有n-1个元素
$$ T_a = \left\{ \begin{array}{l l} \frac{a^i + a^{i+1}}{2} | 1 \leq i \leq n-1\\ \end{array} \right\} $$
当中心点$\frac{a^i + a^{i+1}}{2}$选择区间$[a^i,a^{i+1})$作为划分点。然后，我们就可以像离散值属性一样来考察这些分割点，选取最优的分割点进行样本集合的划分。例如我们可以重新定义4.2
$$ Gain(D, a) = \max_{t \in T_a} Gain(D, a, t) \\ = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}} \frac{|D_t^\lambda|}{|D|} Ent(D_t^\lambda)（4.8） $$
其中Gain(D,a,t)将D根据t进行二分后的信息增益，分割点的选择是Gain(D,a,t)最大的地方。
为了说明我们创建了西瓜数据集3.0，在西瓜数据集2.0上添加了糖分，现在我们使用新数据集发布决策树。
一开始17个训练样本都有不同的密度值。根据式4.7，分割点的候选几个有16个值Tdensity = {0.244, 0.294, 0.351, 0.381,0.420, 0.459, 0.518, 0.574, 0.600, 0.621, 0.636, 0.648, 0.661,0.681, 0.708, 0.746}根据4.8，密度的信息增益是0.262，相应的切分点是0.381
对于属性糖份，相应的分割点候选值有16个{0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418},同样的，糖份的信息增益是0.349，相应的切分点是0.126。
结合4.21节的结果，表4.3属性的信息增益分别为
所以纹理被当做最大的信息增益，被选择来划分根节点的属性。分割过程递归进行，最终生成如图4.8所示的决策树
不像离散特征，连续特征可以在决策序列中多次用作分割特征。（例如在父节点上使用了密度<=0.381，不会禁止在子节点上使用密度》<=0.294）
缺失值处理
再实践中，数据通常是缺失的，即一些属性在一些样例中缺失了。以医学诊断为例，例如数值艾滋病测试结果可能由于设计隐私是无法获得的。一些时候我们可能有大量的不完整样例，特别是当我们有很多属性的时候。虽然我们可以简单的丢弃掉不完整的样例，这是对数据集的巨大浪费。例如表4.4展示了一个缺失数据的西瓜数据集。
如果我们丢掉不完整的样例，那么我们只有4个样例{4,7,14,16}遗留在训练集中。显然，我们需要方法利用不完整样本。
从不完全的样本中学习有俩个问题：
- 当他们属性值丢失的时候，如何选择切分属性
- 给定划分属性，当属性值缺失，如何对样本进行划分
给定训练集D和属性a，让$\tilde D$中的a样本为D中的子集，对于问题1，我们可以简单的使用$\tilde D$去评估a，设{a1,a2,a3,av}是v个a的可能值，$\tilde D^v$表示$\tilde D$中在属性a上取值为$a^v$的样本集，$\tilde D_k$表示$\tilde D$中属于k类(k=1,2,...|y|)的样本子集，则显然有$\tilde{D} = \bigcup_{k=1}^{|\mathcal{Y}|}\tilde{D}_k , \hat{D} = \bigcup_{v=1}^V\hat{D}_v.$我们为样本x赋予一个权重$w_x$并定义
$$ \rho = \frac{\sum_{x \in \tilde{D}} w_x}{\sum_{x \in D} w_x}（4.9） $$
$$ \tilde{p}_k = \frac{\sum_{x \in \tilde{D}_k} w_x}{\sum_{x \in \tilde{D}} w_x} \quad (1 \leqslant k \leqslant |\mathcal{Y}|),（4.10） $$
$$ \tilde{r}_v = \frac{\sum_{x \in \hat{D}^v} w_x}{\sum_{x \in \hat{D}} w_x} \quad (1 \leq v \leq V).（4.11） $$
直观的看，对于属性a，ρ代表没有缺失样本的比例，$\tilde p_k$代表第第k个类在所有没有缺失值的样本中所占的比例。$\tilde r_v$代表特征值为$a^v$的样本中所占的比例，最后我们有$\sum_{k=1}^{|y|} \tilde{p}_k = 1$和$\sum^V_{v=1}=1$
根据以上定义我们，可以将信息增益的公式推广为
$$ \begin{equation} Gain(D, a) = \rho \times Gain(\tilde{D}, a) = \rho \times \left( Ent\left(\tilde{D}\right) - \sum_{v=1}^{V} \tilde r_v\left(\tilde{D}^v\right) \right),（4.12） \end{equation} $$
其中由4.1有
$$ Ent(\tilde{D}) = - \sum_{k=1}^{|Y|} \tilde{p}_k \log_2 \tilde{p}_k. $$
对于问题2，档a是已知的，我们将样本呢放置到相应的子节点中，而不改变其权重wx。若样本x在划分属性a上取值未知，则将x同时划入所有子节点，且样本权值在属性值$a^v$对应的子节点中调整为$\tilde r_v\times w_x$，直观的看，这就是让同一个样本以不同的概率划入到不同的子节点中去。
上述方案被用在c4.5算法中，我们将用它来构造一个决策树。
最开始根节点包括了17个样例在D中，所有的样例权重都是1，以颜色为例，该特征值不缺失的样本包括14个样本{2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15,16, 17}代表$\tilde D$，$\tilde D$的熵计算为
$$ Ent(\tilde{D}) = - \sum_{k=1}^{2} \tilde{p}_k \log_2 \tilde{p}_k\\ ={\displaystyle -{\bigg (}{\frac {6}{14}}\log _{2}{\frac {6}{14}}+{\frac {8}{14}}\log _{2}{\frac {8}{14}}{\bigg )}=0.985} $$
设$\tilde D^1,\tilde D^2，\tilde D^3$，分别表示属性在颜色上取值为，青绿，乌黑以及浅白的样本集
$$ \begin{align*} \text{Ent}(\tilde{D}^1) &= -\left( \frac{2}{4}\log_2\frac{2}{4} + \frac{2}{4}\log_2\frac{2}{4} \right) = 1.000, \\ \text{Ent}(\tilde{D}^2) &= -\left( \frac{4}{6}\log_2\frac{4}{6} + \frac{2}{6}\log_2\frac{2}{6} \right) = 0.918, \\ \text{Ent}(\tilde{D}^3) &= -\left( \frac{0}{4}\log_2\frac{0}{4} + \frac{4}{4}\log_2\frac{4}{4} \right) = 0.000. \end{align*} $$
$\tilde D$子集颜色的信息增益为
$$ \begin{aligned} \text{Gain}(\tilde{D}, color) &= \text{Ent}(\tilde{D}) - \sum_{v=1}^{3} \tilde r_v \text{Ent}(\tilde{D}^v) \\ &= 0.985 - \left( \frac{4}{14} \times 1.000 + \frac{6}{14} \times 0.918 + \frac{4}{14} \times 0.000 \right) \\ &= 0.306. \end{aligned} $$
数据集D的颜色的信息增益为
$$ \begin{aligned} \text{Gain}(D, color) &= \rho \times \text{Gain}(\tilde{D}, color) = \frac{14}{17} \times 0.306 = 0.252. \end{aligned} $$
类似的我们可以计算所有属性的信息增益
根据纹理划分可以有最大的信息增益。具体来说样本被放在纹理为清晰的子节点，编号{7, 9, 13, 14, 17}被放入纹理=稍糊的子节点，样例{11, 12, 16}被放在纹理=模糊的子节点。这些样本的权重（即1）在子节点中保持不变。然而由于纹理的值在样本中缺失了，样本被放置到三个具有不同权重的子节点中7/15,5/15,3/15。样例{10}的处理方式类似，划分方式递归进行，最终的决策树如图4.9所示
多变量决策树
如果我们把每个属性当做空间中的坐标轴，样本有d个特征对应于d维空间中的一个点。分类是找到一个空间中的决策边界，以分开不同类型的样本。对于决策树，决策边界有明显的特征，轴平行（axis-parallel），即，分类边界由若干个于坐标轴平行的分段组成。
例如图4.10展示了决策树在西瓜 数据集表4.5中的3.0a的训练,对应的决策边界如4.11所示
从4.11中，我们可以观察到每个分段。每个分段对应特殊的属性值，这样的分类边界使得学习结果更易于解释。事实上，分类边界通常需要许多分段才能得到很好的近似，如图4.12
然而这种复杂决策树的决策通常很慢，因为他们包含许多属性测试。
如果我们可以绘制斜的分类曲线，如4.12所示，那么决策树可以被大大简化。多变量决策树使用了斜的划分区域，甚至更复杂的分类边界。每个非叶子节点不再是测试特定的属性，而是特征的线性组合。换句话说，每个非叶子节点是在$\sum^d_{i=1}w_ia_a=t$中线性分类器，其中$w_i$是属性$a_i$的权重，wi和t在节点的数据集和属性集中进行学习。不同于传统的单变量决策树，多变量决策树的学习过程不看最优的拆分属性，而是尝试建立一个线性分类器。
图4.13展示了多变量决策树在西瓜数据集3.0中的学习，对应的分类边界如图4.14所示