0x00 内容
决策树：决策树、信息熵、基尼系数、CART
实践：代码实现决策树
0x01 决策树
决策树的建模思路是尽可能模拟人做决策的过程。几乎没有任何抽象，完全通过生成决策规则来解决分类和回归问题。它的运行机制能很直接地被翻译成人类语言，因此在学术上被归为白盒模型（white box model）。
1.1 决策树
决策树的思想，类似于利用选择做决策的过程。它是类似流程图的结构，其中每个内部节点表示一个测试功能，即类似做出决策的过程（动作），每个叶节点都表示一个类标签，即在计算所有特征之后做出的决定（结果）。标签和分支表示导致这些类标签的功能的连接。从根到叶的路径表示分类规则。
用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。
1.2 决策树与条件概率
决策树表示给定特征条件下，类的条件概率分布，这个条件概率分布表示在特征空间的划分上，将特征空间根据各个特征值不断进行划分，就将特征空间分为了多个不相交的单元，在每个单元定义了一个类的概率分布，这样，这条由根节点到达叶节点的路径就成了一个条件概率分布。
假设X表示特征的随机变量，Y表示类的随机变量，那么这个条件概率可以表示为P(Y|X)，其中X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点（单元）上的条件概率往往偏向某一个类。根据输入的测试样本，由路径找到对应单元的各个类的条件概率，并将该输入测试样本分为条件概率最大的一类中，就可以完成对测试样本的分类。
0x02 决策树的学习
2.1 学习本质
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能是0个或多个。我们需要找到一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好地拟合，而且对未知数据有很好地预测。
2.2 决策树损失函数
决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。（关于极大似然函数：极大似然法是属于数理统计范畴，旨在由果溯因。把“极大似然估计”拆成三个词：极大（最大的概率）、似然（看起来是这个样子的）、估计（就是这个样子的），连起来就是：大概率看起来是这样的，那就是这样。）
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。
0x03 决策树的构建
决策树通常有三个步骤：
特征选择
决策树的生成
决策树的修剪
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
这一过程对应着对特征空间的划分，也对应着决策树的构建。
1.开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2.如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶子节点去。
3.如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如此递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4.每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
以上方法就是决策树学习中的特征选择和决策树生成，这样生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使其具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点，从而使得模型有较好的泛化能力。
决策树生成和决策树剪枝是个相对的过程，决策树生成旨在得到对于当前子数据集最好的分类效果(局部最优)，而决策树剪枝则是考虑全局最优，增强泛化能力。
0x04 小结&问题
决策树是一个非参数的决策算法，决策树可以解决分类问题，且天然支持多分类问题。决策树也可以解决回归问题，按照树的路径追踪到叶子结点，最终叶子节点对应一个数值，且回归问题的结果是一个具体的数值，就可以落在叶子结点的所有样本的平均值，作为回归的预测结果。
并且决策树具有非常好的可解释性。在构建决策树，首先找到一个维度，然后在维度上找到一个阈值。然后以这个维度的这个阈值为依据进行划分。
0x05 信息熵
5.1信息熵
信息熵表示随机变量的不确定度。对于一组数据来说，越随机、不确定性越高，信息熵越大；不确定性越低，信息熵越小。信息熵表示随机变量的不确定度。对于一组数据来说，越随机、不确定性越高，信息熵越大；不确定性越低，信息熵越小。
计算熵，需要计算所有类别所有可能值所包含的信息期望值，著名的香农公式：
0x06 条件熵
条件熵与信息熵不同，条件熵是数学期望，而不是变量的不确定性。
条件熵意思是按一个新的变量的每个值对原变量进行分类。然后在每一个小类里面，都计算一个小熵，然后每一个小熵乘以各个类别的概率，然后求和。
所谓小类，就是不包含当前所选特征的其他维度，即当前的特征是给定的条件，在其他维度下求熵，是条件下的。各类别的概率，是当前这个小类别下的样本量除以总的样本量。
0x07 信息增益
在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择。
信息增益就是：以某特征划分数据集前后的熵的差值。
（在计算过程中，使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益（列表）。从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。对于待划分的数据集D，其经验熵H(D)是不变的，但是划分之后得到的条件熵H(D|A)是变化的（特征A的选择不同）。）
条件熵H(D|A)越小，说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因为得到的信息增益就越大。说明在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。
信息增益偏向取值较多的特征。
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。
0x08 信息增益率
选取信息增益大的特征，可以得到更好的划分。但因为信息增益偏向于选择取值较多的特征，容易过拟合。
在信息增益的基础之上乘上一个惩罚参数，对树分支过多的情况进行惩罚，抵消了特征变量的复杂程度，避免了过拟合的存在。
8.1 信息增益率
信息增益比本质：是在信息增益的基础之上乘上一个惩罚参数。
信息增益比 = 惩罚参数 * 信息增益
惩罚参数，是数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）。
信息增益比的缺点是：偏向取值较少的特征。原因：当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
基于以上特点，在使用增益信息比时，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
0x09 基尼系数
9.1 基尼系数的定义
基尼系数（Gini），也被称为基尼不纯度，表示在样本集合中一个随机选中的样本被分错的概率。
9.2 基尼指数
一般来说，我们在使用中，用某个特征划分样本集合只有两个集合（CART）：
1.等于给定的特征值的样本集合D1
2.不等于给定的特征值的样本集合D2
这样就可以对拥有多个取值的特征的二值处理。对于上述的每一种划分，都可以计算出基于划分特征=某个特征值将样本集合D划分为两个子集的纯度。因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中Ai表示特征A的可能取值)。然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。
0x10 特征选择
特征选择也就是选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。代码参考（3.决策树3: 特征选择之寻找最优划分 ）
10.1 信息增益最优划分
10.2 信息增益率最优划分
10.3 基尼系数最优划分
0x11 ID3算法
ID3算法是一种分类预测算法，算法以信息论中的“信息增益”为基础。核心是通过计算每个特征的信息增益，每次划分选取信息增益最高的属性为划分标准，递归地构建决策树。
11.1 构造
ID3相当于用极大似然法进行概率模型的选择。具体方法是：
1.从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。
2.由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；
3.最后得到一个决策树。
从ID3的构建树过程而言，它可以看成使用贪心算法得到近似最优的一颗决策树，它无法保证是最优的。
11.2 优缺点
相对于其他数据挖掘算法，决策树在以下几个方面拥有优势：
1.决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。
2.对于决策树，数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
3.能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
4.是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
5.易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
6.在相对短的时间内能够对大型数据源做出可行且效果良好的结果
ID3算法可用于划分标准称型数据，但存在一些问题：
1.没有剪枝过程，为了去除过渡数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点;
2.信息增益的方法偏向选择具有大量值的属性，也就是说某个属性特征索取的不同值越多，那么越有可能作为分裂属性，这样是不合理的；
3.只可以处理离散分布的数据特征
4.ID3算法只考虑了树的生成，即尽可能的是模型拟合当前训练数据集，所以该算法生成的树容易过拟合。
0x12 C4.5算法
C4.5算法是数据挖掘十大算法之一，它是对ID3算法的改进，相对于ID3算法主要有以下几个改进
1.用信息增益比来选择属性
2.在决策树的构造过程中对树进行剪枝
3.对非离散数据也能处理
4.能够对不完整数据进行处理
C4.5算法与ID3算法过程相似，仅在特征选择时，使用信息增益比作为特征选择准则。
0x13 小结
一、ID3：
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
二、C4.5：
C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。
C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。
三、信息增益 vs 信息增益比：
之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。
0x14 剪枝
当训练数据量大、特征数量较多时构建的决策树可能很庞大，这样的决策树用来分类是否好？答案是否定的。
决策树是依据训练集进行构建的，为了尽可能正确地分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多。这就可能会把训练样本学的“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此可主动去掉一些分支来降低过拟合风险。
决策树非常容易产生过拟合，实际所有非参数学习算法，都非常容易产生过拟合。因此，对于决策树的构建还需要最后一步，即决策树的修剪。两个目的：降低复杂度，解决过拟合。
决策树的修剪，也就是剪枝操作，主要分为两种：
预剪枝（Pre-Pruning）
后剪枝（Post-Pruning）
14.1 预剪枝
预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
那么所谓的“决策树泛化性能”如何来判定呢？这就可以使用性能评估中的留出法，即预留一部分数据用作“验证集”以进行性能评估。
预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛化性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
14.2 后剪枝
后剪枝是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树完全替换为叶节点能带来决策树繁花性的提升，则将该子树替换为叶节点。
14.3 总结
对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
（代码参考：5.决策树5：剪枝与sklearn中的决策树 0x04 sklearn中的剪枝处理）
0x15 CART算法
15.1 CART算法
CART算法：Classification And Regression Tree。顾名思义，CART算法既可以用于创建分类树（Classification Tree），也可以用于创建回归树（Regression Tree）、模型树（Model Tree），两者在建树的过程稍有差异。既可以解决分类问题，也可以解决回归问题。根据某一个维度d和某一个阈值v进行二分，得到的决策树是二叉树。
ID3中使用了信息增益选择特征，增益大优先选择。C4.5中，采用信息增益比选择特征，减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。
15.2 CART作为分类树
CART作为分类树时，特征属性可以是连续类型也可以是离散类型，但观察属性(即标签属性或者分类属性)必须是离散类型。
15.2.1 对离散特征和连续特征的处理
15.2.1.1 离散特征
CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树。
CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合。
比如{A2}和{A1,A3}，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。**由于这次没有把特征A的取值完全分开，各分支下的子数据集必须依旧包含该特征，该连续特征在接下来的树分支过程中可能依旧起着决定性作用。后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。
15.2.1.2 连续特征
CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。
具体思路：m个样本的连续特征A有m个，从小到大排列a1,a2,......,am，则CART取相邻两样本值的平均数做划分点，一共取m-1个，其中第i个划分点Ti表示为：Ti=(ai+ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。另外，对于连续属性先进行排序（升序），只有在决策属性（即分类发生了变化）发生改变的地方才需要切开，这可以显著减少运算量。
注意的是，与ID3、C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性在后面还可以参与子节点的产生选择过程。
15.3 CART作为回归树
15.3.1 回归问题思路
当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了，也略显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。一种可行的方法是将数据集切分成很多份易建模的数据，然后利用线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树结构和回归法就相当有用。
回归树的目标是连续数据，树被用来预测目标变量的值是多少。
CART回归树和CART分类树的建立类似，区别在于样本的输出，如果样本输出是离散值，这是分类树；样本输出是连续值，这是回归树。分类树的输出是样本的类别，回归树的输出是一个实数。
并且分类树采用基尼系数的大小度量特征各个划分点的优劣。而回归树采用最小化均方差和进行最优划分特征的选择，对于划分特征A，划分点s两边的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小，对应的特征和特征值划分点。
其中：C1为D1数据集的样本输出均值，C2为D2数据集的样本输出均值。
对于决策树建立后做预测的方式，CART分类树采用该叶子节点里概率最大的类别作为当前节点的预测类别。回归树输出不是类别，采用叶子节点的均值或者中位数来预测输出结果。
15.3.2 CART剪枝
由于决策树算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，来增加决策树的泛化能力。CART采用的办法是后剪枝法。
CART树的剪枝算法可以概括为两步：
1.从原始决策树生成各种剪枝效果的决策树
2.用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的树作为最终的CART树。
可以采用交叉验证策略，上面我们计算出了每个子树是否剪枝的阈值α，如果我们把所有的节点是否剪枝的值α都计算出来，然后分别针对不同的α所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的α，有了这个α，我们就可以用对应的最优子树作为最终结果。
参考阅读：
7.
