决策树算法原理

1、决策树分类原理 　　

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。

2、决策树的学习过程

一棵决策树的生成过程主要分为以下3个部分:

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

3、基于信息论的三种决策树算法 　　

划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值-分裂值：特征值大于分裂值就走左子树，或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低，具体到C4.5和CART算法则有不同的定义方式。

ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

4、决策树优缺点

决策树算法的优点：

（1）便于理解和解释，树的结构可以可视化出来

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

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

（4）能够处理数值型数据和分类数据

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

（6）可以通过数值统计测试来验证该模型，这使解释验证该模型的可靠性成为可能

（7）即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好

决策树算法的缺点:

（1）决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。

（2）决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解。

（3）在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

（4）有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

（5）如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

5. 决策树在sklearn中的一些建议

（1）当数据的特征维度很高而数据量又很少的时候，这样的数据在构建决策树的时候往往会过拟合。所以我们要控制样本数量和特征的之间正确的比率；

（2）在构建决策树之前，可以考虑预先执行降维技术（如PCA，ICA或特征选择），以使我们生成的树更有可能找到具有辨别力的特征；

（3）在训练一棵树的时候，可以先设置max_depth=3来将树可视化出来，以便我们找到树是怎样拟合我们数据的感觉，然后在增加我们树的深度；

（4）树每增加一层，填充所需的样本数量是原来的2倍，比如我们设置了最小叶节点的样本数量，当我们的树层数增加一层的时候，所需的样本数量就会翻倍，所以我们要控制好树的最大深度，防止过拟合；

（5）使用min_samples_split（节点可以切分时拥有的最小样本数） 和 min_samples_leaf（最小叶节点数）来控制叶节点的样本数量。这两个值设置的很小通常意味着我们的树过拟合了，而设置的很大意味着我们树预测的精度又会降低。通常设置min_samples_leaf=5；

（6）当树的类比不平衡的时候，在训练之前一定要先平很数据集，防止一些类别大的类主宰了决策树。可以通过采样的方法将各个类别的样本数量到大致相等，或者最好是将每个类的样本权重之和(sample_weight)规范化为相同的值。另请注意，基于权重的预剪枝标准（如min_weight_fraction_leaf）将比不知道样本权重的标准（如min_samples_leaf）更少偏向主导类别。

（7）如果样本是带权重的，使用基于权重的预剪枝标准将更简单的去优化树结构，如mn_weight_fraction_leaf，这确保了叶节点至少包含了样本权值总体总和的一小部分；

（8）在sklearn中所有决策树使用的数据都是np.float32类型的内部数组。如果训练数据不是这种格式，则将复制数据集，这样会浪费计算机资源。

（9）如果输入矩阵X非常稀疏，建议在调用fit函数和稀疏csr_matrix之前转换为稀疏csc_matrix，然后再调用predict。 当特征在大多数样本中具有零值时，与密集矩阵相比，稀疏矩阵输入的训练时间可以快几个数量级。