前言

HUAHUA暑假自学西瓜书顺手写的学习笔记，偏向入门科普型QAQ，建议配合西瓜书观看。如有不当之处还请大佬指正。而在了解决策树之前，先回顾一下线性模型。了解了其与决策树模型的区别之后，了解决策树的基本概念与用法。

一、线性模型

首先来简单回顾一下线性模型的公式。针对西瓜书中的例子，对一个瓜的属性赋予权重，来计算并判断这个瓜是不是个好瓜。值得注意的是，线性模型的运算时对所有的属性一同进行操作的，这往往加大了其运算过程的可视化难度。
线性模型基本可以解决三类问题。

1. 回归任务 简单算法——最小二乘法；
2. 二分类任务 线性判别分析；
3. 多分类任务 将一个多分类问题转化为多个二分类问题进行解答；

二、决策树

• 相对于线性模型，决策树模型更接近人的思维方式，例如，我们要判定“这是好瓜吗？”首先会进行一系列的子决策：先看是什么颜色？如果是青绿色，再看是根蒂是什么形态？如果是蜷缩，再听敲击声清不清脆？最后，我们得到了结论—>这是个好瓜。
  
• 以这个简单的决策树为例，可以看到，树内部的每一个节点代表对一个特征的测试，树的分支代表该特征的每一个测试结果，而叶子节点代表一个类别。可以发现，树形模型可以产生可视化的分类规则，产生的模型具有可解释性。树模型拟合出来的其实是分区间的阶梯函数。

接下来介绍决策树的基本算法的伪代码：

可以看到决策树其实在实现过程中，以递归的形式来不断进行判断并生成子结点。其中递归返回的条件可总结成三类：

1. 当前结点的样本全都是一个类别。此时样本就已经分类完毕了，这次分类就结束了，可以进行下一阶段的分类了。
2. 当前结点的样本没有属性来分了 OR 样本在所有的属性上取值都一样。在这种情况，我们将这个结点设置为叶子结点，且将其类别设定为该结点所含样本最多的类别，相当于利用当前的样点分布作为后验分布。
3. 当前结点没有样本。这种情况下，我们也会将其设置为叶子结点。与第2个条件不同的地方在于，这个结点的类别设置为其父结点所含样本最多的类别，相当于将父结点的样点分布作为当前结点的先验分布。

三、划分选择

• 在前面的学习中，如果有细心的同学会发现决策树算法中比较关键的一点是伪代码中的第8行，就是如何选择最优的划分属性。随着划分过程的进行，当然希望决策树的分支所包含的样本尽可能属于同一类别，也就是结点的“纯度”越来越高。

而在如何选择最优属性上，决策树也是有很多i算法的。下面介绍3个最基本的算法。

1. 信息增益

• 要了解信息增益，首先要了解信息熵是啥东西。信息熵：1948年由数学家香农借用热力学的熵的概念提出，用来描述信息的不确定性。简单来说就是信息熵越大，就越不稳定，样本就越不纯。定义样本集合为D、信息熵为Ent（D），Ent越小D的纯度就越高。
  
• 假定离散属性值a有V个可能的取值，若使用a对D进行划分，则会产生V个分支结点，每个分支的样本分支记做D^v。而考虑到不同结点的结点包涵的样本数不同，给每个分支结点赋予权重|D^v|/|D|。简单来说就是样本数越多的分支结点影响越大。记信息增益为Gain(D,a)，公式如上。一般而言，信息增益越大意味着用属性a来作为划分属性所获得的样本“纯度提升”越大。在著名的ID3决策树学习算法【Quinlan，1986】就是以信息增益为准则来选择划分属性的。**具体方法是：**从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点。由此递归指导所有的特征信息增益均很小或没有特征可以选择时，停止递归。
  
• 信息增益很直接地（甚至是有些固执地）找到了当前的最优划分属性。但这样做也是存在一些问题的，很容易陷入类似局部最优解的困境中。举个例子，如上图所示，如果选择ID作为特征，信息增益最大，每一类的“纯度”最高。但这样划分的实际意义不大。可以看到，信息增益很偏爱选择取值比较多的属性，于是引进了增益率的概念进行改进。

2. 增益率

• 针对信息增益偏爱取值数目较多的属性的问题，增益率则会对多分支项进行惩罚。如公式所示，增益率Gain_ratio(D,a) 就是信息增益 Gain(D,a) 除以属性信息熵 IV(a)（这个名字是我自己取的）而属性a的值，数目越多（也就是V越大）IV(a)通常会越大。那么就会导致相对于信息增益算法，增益率会对可取值数目较少的属性有所偏爱。
  
• 那么有些小伙伴会问，这两个算法都很任性、都有自己的偏爱对象。那么是不是会存在同一个问题呢？在决策树的C4.5算法中给出了一个很好的解答，它并没有直接选择增益率作为最大的候选划分属性，而是使用了一个启发式算法：先从候选的划分属性中找出信息增益高于水平的属性，再从总选择增益率最高的。这样就较好地中和了两种选择的缺点。

3. 基尼指数

• 相对于信息增益来说，Gini指数生成的决策树的层数更多。在划分属性时，会优先将分类最频繁的属性分离下来。在CART算法(Classification and Regression Tree)中，就是运用基尼指数作为划分依据。在程序运行过程中也发现基尼指数的运算速度相对更快。如公式中，可以发现基尼指数实际上是在计算每个分支的错误概率，所以需要选择基尼值最小的分支进行划分。
• PS：如果对于3个算法想了解更多，可以跳转到决策树算法，这篇博客讲解更加细致。

四、剪枝处理

• 剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。为了尽可能正确分类训练样本，结点划分过程会不断重复。那么就会导致一个问题：可能导致决策树分支太多，样本训练“太好了”，以至于把样本自身的某些特点当作一般性质来拟合了。那么这样就会导致算法复杂度的升高、以及划分准确率的降低等众多问题。以西瓜为例，根据信息表训练出普通的决策树，之后根据不同的剪枝规则来观察效果。
  

1.预剪枝

• 在基于信息增益准则，我们会选取属性“脐部”来对训练集进行划分，并产生3个分支，但是如果分类后反而使得划分效果变差了呢？那么预剪枝就会对划分前后的泛化性能进行估计。以下图为例，在结点2的位置，选择最优划分属性为“色泽”。而在划分之后的准确率为57.1%，，反而不如划分之前的准确率71.4%。所以这里的策略是不进行划分。对于结点3号、4号也是同样的道理。如果划分效果更好，那么就进行划分，反之就禁止划分。
  
• 需要注意的是，预剪枝确实会减少运算量，但是每次的结点划分中还是会有运算来确定是否划分。并且会导致该结点后面的子结点所产生的分类效益消失，就会导致欠拟合的问题。那么在后剪枝中会解决这个问题。

2.后剪枝

• 对比上图可以看出，后剪枝决策树首先在经过完整的决策树生成树流程后，从底层非叶子节点往上回溯。如果这里的划分对于准确性是负增益，那么就会删除该结点。
  

• 分析可得，相对预剪枝来说，后剪枝决策树保留了更多的分支，并且欠拟合的风险很小，也有效地减少了无效分支，有效消除了过拟合的问题。但是由算法过程可知，后剪枝决策树的训练时间开销会比未剪枝决策树和预剪枝决策树都要大得多。

五、连续与缺失值

1.连续值

• 目前为止，我们仅仅讨论了离散属性生成决策树，儿在以上提到的多个算法以及现实生活中，都是有连续变量作为属性。那么如何对连续属性进行处理，在C4.5算法中采用了相关的机制。也就是连续属性离散化。最简单的策略就是采用二分法来建立分界点。在连续的属性中，样本D在该属性上有n个取值，在排序后可以提取n-1个特征值。
• 就是把区间[aⁱ,aⁱ⁺¹)的中位点作为候选划分点。之后就可以像离散值一样来考察这些划分点。如下图中，密度>0.381就是好属性，某些情况下可以用其判断为好瓜。需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

2.缺失值

• 由于任务中经常会遇到不完整样本，由于某些属性值缺失而导致该样本的其他属性所携带的信息浪费。那么为了解决这个现象，我们需要解决两个问题：
  （1）如何在属性缺失的情况下进行划分属性选择？
  （2）给定了划分属性，若该样本在这个属性上的值不见了，如何对这个样本进行划分？
• 带着这个问题，我们在训练集D和属性a上进行分析。假定d表示样本D在属性a上没有缺失值的样本子集，且属性a有V个可取值{a¹,a²,…,a^V}，d_k表示d中属于第k类的样本子集。假定w_x为每个样本的权重，ρ为无缺失值样本所占的比例，p_k表示无缺失值样本第k类的比例，r_v表示无缺失值样本中在属性a上取值的a^v的样本所占的比例。列出公式如下：
  
  由此，可以讲信息增益计算式推广为：
  

其中，信息值的计算公式为：

• 而针对问题（2），若样本x在当前划分属性a上的取值已知，那么可以正常分类，讲x划入取值对应的子结点，且样本权值继续保持为w_x。但当取值未知时，x无法正常划分到某一特定子结点里。那么算法C4.5中的解决方法是将x同时以不同的概率分配到不同子结点中。实际操作是，将x同时划分到所有子结点中，特别的是改变其样本权值，调整为r_v·w_x，这样就实现了前面的想法。

六、总结

• 终于，写完了这篇不太专业的决策树科普类别的博客。最后给大家做一个简单的总结。特别提出，决策树是一种基本的分类与回归的方法，本文讲解的是分类部分的基本思路，如果大家想看回归树，决策树—回归这篇博客写得十分清楚。
  接下来还是简单说一下决策树的优缺点吧。

优点	缺点
简单直观可以清晰看到生成过程	很容易过拟合，导致泛化能力不强
基本无需归一化、缺失值处理等预处理操作	树结构很容易因为样本很小的改变而产生很大的变动
可以处理离散值和连续值	寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善
对异常点容错能力好，健壮性高	有些比较复杂的关系，决策树很难学习，比如异或
用决策树预测的代价是O(log2m)，m为样本数	如果某些特征的样本比例过大，生成决策树容易偏向于这些特征

参考资料：
https://blog.csdn.net/qq_20412595/article/details/82048795
机器学习·[周志华]，清华大学出版社