决策树
目录
1. 决策树思维
决策树(decision tree)是一类常见的机器学习方法。以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新的示例进行分类，这个把样本分类的任务，可以看作对“当前样本属于正类吗？”这个问题的“决策”或“判别”过程。顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。
例如，假设我们有表1中的数据集
表1 贷款申请样本数据表
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
我们要对“是否同意贷款申请？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”：我们先看看“申请人的年龄是青年还是老年”，如果是“青年”，我们看他是否“有工作”，如果“有工作”，再看他是否“有自己的房子”，如果“没有自己的房子”，我们在判断他“信贷情况”，最后，我们得出最终的决策：同意申请人的贷款申请。决策过程如图1所示：
图1 贷款申请问题的一个决策树
显然，决策过程最终结论对应了我们所希望的判定结果，例如“同意”或“不同意”申请人的贷款申请；决策过程中提出的每个判定问题都是对某个属性的"测试"，例如“年龄=？”、“有工作=？”；"每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范维是在上次决策结果的限定范围之内，例如若在"年龄=青年"之后再判断"有工作=?"，则仅在考虑青年是否有工作。
很自然的，我们会想到，图1中我们首先考虑的属性是“年龄”，那么如果我们首先考虑的属性是“有工作”结果会怎样呢？显然，我们会得到另一棵不同的决策树。问题是：究竟选择哪一个属性更好些？这就需要确定选择划分属性的准则。直观上，如果一个属性具有更好的分类能力，或者说，按照这一个属性将训练数据集分成子集，使得各子集在当前条件下有最好的分类，那么就更应该选择这个属性。
那么，决策树中常用的确定选择划分属性的准则有哪些呢？
2. 划分属性准则
决策树学习的关键是如何选择最优属性划分。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，即节点的“纯度”(purity)越来越高。
2.0 预备知识
前面的一篇笔记中我们学习了信息熵与条件熵相关内容，它们是决策树选择最优划分属性过程中很重要的概念。
2.1 信息增益
“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合\(D\)中第\(k\)类样本所占的比例为\(p_k(k=1,2,\dots,|\mathcal{Y}|)\)，则\(D\)的信息熵定义为
\(Ent(D)\)的值越小，则\(D\)的纯度越高。
计算信息熵时约定：若\(p=0\)，则\(plog_2p=0\)
\(Ent(D)\)的最小值为0，最大值为\(log_2|\mathcal{Y}|\)，证明可以看这里
假定离散属性\(a\)有\(V\)个可能的取值\(\{a^1,a^2,\dots,a^V\}\)，若使用\(a\)来对样本集\(D\)进行划分，则会产生\(V\)个分支结点，其中第\(v\)个分支结点包含了\(D\)中所有在
属性\(a\)上取值为\(a^v\)的样本，记为\(D^v\)。我们可根据式\((1)\)计算出\(D^v\)的信息熵
再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重\(|D^v|/|D|\)，即样本数越多的分支结点的影响越大，于是可计算出用属性\(a\)对样本集\(D\)进行划分所获得的"信息增益" (information gain)
决策树学习应用信息增益划分属性。给定数据集\(D\)和属性\(a\)，信息熵\(Ent(D)\)表示对数据集\(D\)进行分类的不确定性。而\(\sum_{v=1}^V \cfrac{|D^v|}{|D|}Ent(D^v)\)是条件熵，表示在属性\(a\)给定的条件下对数据集\(D\)进行分类的不确定性。那么它们的差，即信息增益，就表示由于属性\(a\)而使得对数据集\(D\)的分类的不确定性减少的程度。显然，对于数据集\(D\)而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。
综上，信息增益越大，说明在知道属性\(a\)的取值后样本集的不确定性减小的程度越大，也就是划分后所得的“纯度提升”越大。因此，我们可以根据信息增益进行划分属性的选择，方法是：对数据集（或子集）\(D\)，计算其每个属性的信息增益，并比较它们的大小，选择信息增益最大的特征。
2.2 信息增益率
以信息增益作为划分数据集的准则，存在偏向于选择取值较多的属性的问题。举个极端的例子，假设我们某个属性的可能取值\(V\)与数据集\(D\)的样本数相等，如果将其作为一个划分属性，计算出来的信息增益将远大于其他属性。这很容易理解：这个属性产生的分支结点中将仅包含一个样本，这些分支结点的纯度已经达到最大。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。
信息增益率(information gain ratio)可以对这一问题进行校正，可以作为选择最优划分属性的另一种准则。定义为属性\(a\)对数据集\(D\)的信息增益与数据集\(D\)关于属性\(a\)的信息熵之比，即
其中
称为属性\(a\)的“固有值”(intrinsic value)。属性\(a\)的可能取值数目越多(即\(V\)越大)，\(IV(a)\)的值通常越大。
需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
2.3 基尼指数
基尼指数(Gini index)是决策树选择最优划分属性的准则之一。数据集\(D\)的纯度用基尼值来度量：
直观来说，\(Gini(D)\) 反映了从数据集\(D\)中随机抽取两个样本，其类别标记不一致的概率。因此，\(Gini(D)\)越小，则数据集\(D\)的纯度越高。
同样的，在属性\(a\)的条件下，数据集\(D\)的基尼指数定义为
于是，我们在候选属性集合\(A\)中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
3. 决策树的生成
基于不同的属性划分准则，决策树有不同的生成算法。常见的有ID3、C4.5、CART。
3.0 决策树生成基本算法
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;叶结点对应于决策结果，其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的基本流程遵循简单且直观的"分而治之" (divide-and-conquer) 策略，如下
输入：训练数据集\(D=\{(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)\}\)，属性集\(A=\{a_1,a_2,\dots,a_d\}\)
过程：决策树生成，函数\(TreeGenerate(D, A)\)
- 生成结点node
- 如果\(D\)中样本全属于同一类别\(C\)，将node标记为\(C\)类叶结点，返回决策树
- 如果\(A = \emptyset\)或者\(D\)中的样本在\(A\)上取值相同，将node标记为叶结点，其类别标记为\(D\)中样本数最多的类，返回决策树
- 否则，从\(A\)中选择最优划分属性\(a_*\)
- 遍历\(a_*\)中的每一个值\(a_*^v\)，为node生成一个分支，令\(D_v\)表示\(D\)中在\(a_*\)上取值为\(a_*^v\)的样本子集
- 如果\(D_v\)为空，将分支结点标记为叶结点，其类别标记为\(D\)中样本最多的类，返回决策树
- 否则，以\(TreeGenerate(D_v, A \{a_*\})\)为分支结点，其中\(A \{a_*\})\)表示从\(A\)中去除掉\(a_*\)。
- 重复过程4-7
输出：以node为根结点的一棵决策树。
显然，决策树的生成是一个递归过程。在决策树生成算法中，有3种情形会导致递归返回：
1）当前结点包含的样本全属于同一个类别，无需划分；
2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
3）当前结点包含的样本集合为空，不能划分。
3.1 ID3
ID3算法的核心是在决策树各个结点上应用信息增益准则进行最优划分属性选择，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的属性的信息增益，选择信息增益最大的属性作为结点的属性，由该属性的不同取值建立子结点；在对子结点递归地调用以上方法，构建决策树；直到所有属性的信息增益均很小或没有属性可以选择为止。最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择。
利用表1中的训练数据集\(D\)，通过上一节描述的决策树生成过程，使用ID3算法建立决策树。
1）根据式\((1)\)计算数据集\(D\)的经验熵\(Ent(D)\)，其中，类别“是”(9)，“否”(6)，则
2）根据式\((2)\)计算各属性对数据集\(D\)的信息增益。分别以\(a_1\)，\(a_2\)，\(a_3\)，\(a_4\)表示年龄、有工作、有自己的房子、和信贷情况4个属性，则
类似的，我们计算得到其他属性对数据集\(D\)的信息增益：
3）比较个属性的信息增益值。由于属性\(a_3\)（有自己的房子）的信息增益值最大，所以选择属性\(a_3\)作为根结点。
4）属性\(a_3\)将训练数据集\(D\)划分为两个子集\(D_1\)(\(a_3\)取值为“是”)和\(D_2\)(\(a_3\)取值为“否”)。此时，由于\(D_1\)中只有同一类的样本点，所以它成为一个叶结点，结点类标记为“是”。
5）对于子集\(D_2\)，需要从除属性\(a_3\)之外的其他3个属性中选择新的属性，按照上面的方式继续划分。\(D_2\)子集中类别“是”(3)，类别“否”(6)，则
计算信息增益：
注意：属性\(a_3\)已经使用过，不再重复使用。
使用信息增益最大的属性\(a_2\)（有工作）作为结点的属性。由于\(a_2\)有两个可能的取值，从这一结点引出的两个子结点：一个对应“是”（有工作），包含3个样本，它们属于同一类，所以这是一个叶结点，类别标记为“是”；另一个对应“否”（无工作），包含6个样本，它们也属于同一类，所以这也是一个叶结点，类别标记为“否”。
至此，我们只用了两个属性（有两个内部结点）就生成了一个决策树，如图2所示。
图2 ID3算法决策树的生成
ID3算法的不足
-
ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
-
ID3采用信息增益大的属性优先建立决策树的结点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的属性信息增益大。
-
ID3算法对于缺失值的情况没有做考虑
-
没有考虑过拟合的问题
ID3算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢?那是因为决策树太火爆，他的ID3一出来，别人二次创新，很快 就占了ID4， ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。下面我们就来聊下C4.5算法
3.2 C4.5
决策树C4.5算法对ID3算法的不足之处进行了改进，具体来说：
1）连续值处理
现实学习任务中常会遇到连续属性，所以有必要讨论如何在决策树学习中使用连续属性。
由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法(bi-partition) 对连续属性进行处理，这正是C4.5 决策树算法中采用的机制。
给定样本集\(D\)和连续属性\(a\)，假定\(a\)在\(D\)上出现了\(n\)个不同的取值，将这些值从小到大进行排序，记为\(\{a^1, a^2,\dots,a^n\}\)。基于划分点\(t\)可将\(D\)分为子集\(D_t^{-}\)和\(D_t^+\)，其中\(D_t^{-}\)包含那些在属性\(a\)上取值不大于\(t\)的样本，而\(D_t^+\)则包含那些在属性\(a\)上取值大于\(t\)的样本。显然，对相邻的属性取值\(a^i\)与\(a^{i+1}\)来说，\(t\)在区间\([a^i,a^{i+1})\)中取任意值所产生的划分结果相同。因此，对连续属性\(a\)我们可考察包含\(n-1\)个元素的候选划分点集合
即把区间\([a^i,a^{i+1})\)的中位点\(\cfrac{a^i+a^{i+1}}{2}\)作为候选划分点。然后，我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。例如，可对式\((2)\)稍加改造：
其中，\(Gain(D,a,t)\)是样本集\(D\)基于划分点\(t\)二分后的信息增益。于是，我们就可以选择使\(Gain(D,a,t)\)最大的划分点。
注：可将划分点设为该属性在训练集中出现的不大于中位点的最大值，从而使得最终决策树使用的划分点都在训练集中出现过
举个例子说明一下，假设我们有如下的属性\(a\)：
共有17个取值，与之对应的标签类别是：
计算属性\(a\)对数据集\(D\)的信息增益：首先，对属性\(a\)进行排序，有
根据式\((7)\)计算划分点，如下
根据\((7)\)计算每个划分点对应的信息增益，并选择产生最大信息增益的划分点，下面我们只计算其中一个划分点的信息增益值作为说明，假设选取\(0.382\)作为划分点，对应的两个子集\(D_1\)（属性\(a\)取值小于\(0.382\)）包含4个样本，对应类别均为“否”，显然，该子集的信息熵为0；另一个子集\(D_2\)（属性\(a\)取值大于\(0.382\)）包含13个样本，其中类别“是”（8个），类别“否”（5个），则属性\(a\)对数据集\(D\)的信息增益为：
如上，依次计算其他划分点即可。如果要计算信息增益率，可以根据式\((3)\)进行类似计算。
需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
2）ID3算法以信息增益作为划分数据集的准则，存在偏向于选择取值较多的属性的问题。
这个问题我们在前面描述信息增益率的时候解释过了，C4.5算法使用信息增益率作为最优划分属性选择的准则。
3）缺失值处理
现实任务中常会遇到不完整样本，即样本的某些属性值缺失.例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值(如 HIV 测试结果)未知；尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。
对于缺失值的处理问题，主要有两方面：
- 如何在属性缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
给定训练集\(D\)和属性\(a\)，令\(\tilde{D}\)表示\(D\)中在属性\(a\)上没有缺失值的样本子集。
对于问题(1)，显然我们仅可以通过\(\tilde{D}\)来判断属性\(a\)的优劣。假定属性\(a\)有\(V\)个可能的取值\(\{a^1,a^2,\dots,a^V\}\)，令\(\tilde{D}^v\)表示\(\tilde{D}\)中属性\(a\)上取值为\(a^v\)的样本子集，\(\tilde{D}_k\)表示\(\tilde{D}\)中属于第\(k\)类\((k=1,2,\dots,|\mathcal{Y}|)\)的样本子集，则显然有\(\tilde{D}=\cup_k^{|\mathcal{Y}|}\tilde{D}_k\)，\(\tilde{D}=\cup_{v=1}^{V}\tilde{D}^v\)。 假定我们为每个样本 \(x\) 贼予→个权重\(w_x\)，并定义
在决策树学习开始阶段，根结点中各样本的权重初始化为1
直观地看，对属性\(a\)，\(\rho\)表示无缺失值样本所占的比例，\(\tilde{p}_k\)表示无缺失值样本中第\(k\)类所占的比例，\(\tilde{r}_v\) 则表示无缺失值样本中在属性\(a\)上取值\(a^v\)的样本所占的比例，显然，\(\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_k = 1\)，\(\sum_{v=1}^{V}\tilde{r}_v = 1\)。
基于上述定义，我们可将信息增益的计算式\((2)\)推广为
其中根据式\((1)\)，有
对问题(2)，若样本\(x\)在划分属性\(a\)上的取值己知，则将\(x\)划入与其取值对应的子结点，且样本权值在子结点中保持为\(ω_x\)。 若样本\(x\)在划分属性\(a\)上的取值未知，则将\(x\)同时划入所有子结点，且样本权值在与属性值\(a^v\)对应的子结点中调整为凡\(\tilde{r}_v \dot w_x\)，直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。
这一部分如果看定义比较混乱，可以结合《机器学习-周志华》第4.4节的例子
4）过拟合
C4.5引入了正则化系数进行初步的剪枝。具体方法这里不讨论。之后我们详细学习决策树剪枝方法。
除了上面的4点，C4.5和ID3的思路区别不大。
注意：信息增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
C4.5算法的不足
- 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。
- C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
- C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
- C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
参考来源：
1）机器学习-周志华
2）统计学习方法 - 李航
3）https://www.cnblogs.com/pinard/p/6050306.html
