目录

决策树算法

ID3决策树

C4.5决策树

CART决策树

决策树剪枝

决策树学习是根据数据的属性采用树状结构建立的一种决策模型，可以用此模型解决分类和回归问题。常见的算法包括 ,ID3, C4.5，CART(Classification And Regression Tree)等。我们往往根据数据集来构建一棵决策树，他的一个重要任务就是为了数据中所蕴含的知识信息，并提取出一系列的规则，这些规则也就是树结构的创建过程就是机器学习的过程。

决策树算法

决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: 将无序的数据变得更加有序。

决策树生成过程是一个递归过程。在决策树算法中，有三种情形导致递归返回：

（1）、当前结点包含的样本全属于同一类别，无需划分；

（2）、当前属性集为空、或是所有样本在所有属性上的取值相同，无法划分；

（3）、当前结点包含的样本集合为空，不能划分；

经典的属性划分依据：

我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

ID3决策树

信息增益 计算方法

    ID3算法是最早提出的一种决策树算法，ID3算法的核心是在决策树各个节点上应用信息增益准则来选择特征，递归的构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点：再对子节点递归的调用以上方法，构建决策树：直到所有的特征信息增益均很小或没有特征可以选择为止。 

C4.5决策树

增益率 计算方法

C4.5算法与ID3算法决策树的生成过程相似，C4.5算法对ID3算法进行了改进。它是用信息增益率（比）来 选择特征。

这里的改进主要是针对样本特征来作。 
（1）基本决策树要求特征A取值为离散值，如果A是连续值，假如A有v个取值，则对特征A的测试可以看成是对v-1个可能条件的测试，其实可以把这个过程看成是离散化的过程，只不过这种离散的值间隙会相对小一点；当然也可以采用其他方法，比如将连续值按段进行划分，然后设置亚变量； 
（2）特征A的每个取值都会产生一个分支，有的时候会导致划分出来的子集样本量过小，统计特征不充分而停止继续分支，这样在强制标记类别的时候也会带来局部的错误。针对这种情况可以采用A的一组取值作为分支条件；或者采用二元决策树，每一个分支代表一个特征取值的情况（只有是否两种取值)。 
（3）某些样本在特征A上值缺失，针对这种空值的情况，可以采用很多方法，比如用其他样本中特征A出现最多的值来填补空缺，比如采用均值、中值等，甚至在某些领域的数据中可以采用样本内部的平滑来补值，当样本量很大的时候也可以丢弃这些有缺失值的样本。 
（4）随着数据集的不断减小，子集的样本量会越来越小，所构造出的决策树就可能出现碎片、重复、复制等总是。这时可以利用样本的原有特征构造新的特征进行建模； 
（5）信息增益法会倾向于选择取值比较多的特征（这是信息熵的定义决定了的），针对这一问题，人们提出了增益比率法（gain ratio），将每个特征取值的概率考虑在内，及gini索引法，χ2χ2条件统计表法和G统计法等。

CART决策树

基尼指数 计算方法

既可以做分类，也可以做回归。只能形成二叉树。

分支条件：二分类问题

分支方法：对于连续特征的情况：比较阈值，高于某个阈值就属于某一类，低于某个阈值属于另一类。对于离散特征：抽取子特征，比如颜值这个特征，有帅、丑、中等三个水平，可以先分为帅和不帅的，不帅的里面再分成丑和中等的。

得分函数（y）：就是上面提到的gt(x)，对于分类树取得是分类最多的那个结果（也即众数），对于回归树取得是均值。

损失函数：其实这里的损失函数，就是分类的准则，也就是求最优化的准则

对于分类树（目标变量为离散变量）：同一层所有分支假设函数的基尼系数的平均。

对于回归树（目标变量为连续变量）：同一层所有分支假设函数的平方差损失

分裂准则：

对于分类树（目标变量为离散变量）：使用基尼系数作为分裂规则。比较分裂前的gini和分裂后的gini减少多少，减少的越多，则选取该分裂规则

对于回归树（目标变量为连续变量）：使用最小方差作为分裂规则。只能生成二叉树。

决策树剪枝

       由于噪声等因素的影响，会使得样本某些特征的取值与样本自身的类别不相匹配的情况，基于这些数据生成的决策树的某些枝叶会产生一些错误；尤其是在决策树靠近枝叶的末端，由于样本变少，这种无关因素的干扰就会突显出来；由此产生的决策树可能存在过拟合的现象。树枝修剪就是通过统计学的方法删除不可靠的分支，使得整个决策树的分类速度和分类精度得到提高。

为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据
（想象一下，如果树足够庞大，每个叶子节点不就一个数据了嘛）

     2. 剪枝策略：预剪枝，后剪枝

树枝修剪包括预剪枝和后剪枝两种方法： 
（1）预剪枝：边建立决策树边进行剪枝的操作（更实用）

        在决策树生成分支的过程，除了要进行基础规则的判断外，还需要利用统计学的方法对即将分支的节点进行判断，比如统计χ2或统计信息增益，如果分支后使得子集的样本统计特性不满足规定的阈值，则停止分支；但是阈值如何选取才合理是比较困难的。 

（2）后剪枝：当建立完决策树后来进行剪枝操作

        在决策树充分生长后，修剪掉多余的分支。根据每个分支的分类错误率及每个分支的权重，计算该节点不修剪时预期分类错误率；对于每个非叶节点，计算该节点被修剪后的分类错误率，如果修剪后分类错误率变大，即放弃修剪；否则将该节点强制为叶节点，并标记类别。产生一系列修剪过的决策树候选之后，利用测试数据（未参与建模的数据）对各候选决策树的分类准确性进行评价，保留分类错误率最小的决策树。 

决策树算法的优点：

　　1）简单直观，生成的决策树很直观。

　　2）基本不需要预处理，不需要提前归一化，处理缺失值。

　　3）使用决策树预测的代价是O(log2m)。 m为样本数。

　　4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

　　5）可以处理多维度输出的分类问题。

　　6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

　　7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

　　8） 对于异常点的容错能力好，健壮性高。

决策树算法的缺点:

　　1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

　　2）决策树会因为样本发生一点点的改动（特别是在节点的末梢），导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

　　3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

　　4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

　　5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。