1.什么是决策树？

    决策树是监督学习算法。是机器学习算法中一种依靠对条件进行判断来进行分类(针对离散数据生成分类树)和回归(针对连续数据生成回归树)的算法。是直观运用概率分析的一种图解法。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。

    树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有负数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来做预测。

2.决策树的工作原理

    决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛化能力。从另一个角度看，学习也是基于训练数据集估计条件概率模型。在面对多个属性的数据时，决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够"肯定地"判断出结果或者是上述属性都已经使用完毕。

2.1如何构建决策树

    那么问题来了，如何构建一棵决策树呢?决策树的构建是数据逐步分裂的过程，构建的步骤如下：

步骤1：将所有的数据看成是一个节点，进入步骤2；

步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3；

步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2；

步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。

从上述步骤可以看出，决策生成过程中有三个重要的问题：

如何选择分裂的特征

数据如何分割

什么时候停止分割

2.2决策树的特征选择算法

    决策树学习的关键在于如何选择最优的划分属性，所谓最优的划分属性，对于二元分类而言，就是尽量使划分的样本属于同一类别，即“纯度”最高的属性。那么如何来度量特征(features)的纯度，这时候就要用到“信息熵”和“信息增益”，“信息增益率”以及”基尼系数“等概念。

信息增益的理解：

    对于待划分的数据集D，其entroy(前)是一定的，但是划分之后的熵entroy(后)是不定的，entroy(后)越小使用此特征划分得到的子集的不确定性越小(也就是纯度越高)，因此entroy(前)-entroy(后)差异越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能够快速到达纯度更高的集合，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

缺点：信息增益偏向取值较多的特征。

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，一次划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较倾向取值较多的特征。

信息增益率

    信息增益比 = 惩罚系数*信息增益

信息增益比本质：是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

惩罚系数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一子集中(之前所说数据集的熵是依据类别进行划分的)

缺点：信息增益比偏向取值较少的特征

原因：当特征取值较少时的值较小，因此其倒数较大，因而信息增益比较大，所以偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征值再选择信息增益率最高的特征。

GINI指数：

    定义：基尼指数(基尼不纯度)：表示在样本集合中一个随机选择的样本被分错的概率。

    注意：Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。即基尼系数(基尼不纯度)=样本被选中的概率*样本被分错的概率。

    因而对于一个具有多个取值(超过2个)的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中AI表示特征A的可能取值)。然后从所以的可能划分的Gini指数最小的划分，这个划分的划分点，便是使用特征A对于样本集D进行划分的最佳划分点。

C4.5

    C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了以下几点改进。

1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂熟悉的不足。

2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理。

3）构造决策树之后进行剪枝操作；

4）能够处理具有缺失属性值的训练数据。

CART

    CART树里面对C4.5中存在的问题进行了改进。CART假设决策树是二叉树，并且可以分类也可以回归，而且用基尼指数代替了熵模型进行特征选择，也提供了优化的剪枝策略。

回归树：划分的准则是平方误差最小化。

分类树：划分的准则是基尼指数最小化。

3.决策树何时停止分裂

    决策树不可能无限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时总动结束分裂，但这种情况下树过于复杂，而且预测的精度不高。一般情况下为了降低决策树度复杂度和提高预测的精度，会适当提前终止节点的分裂。

    以下是决策树节点停止分裂的一般性条件：

1）最小节点数

    当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。

2）熵或者基尼值小于阈值

    由上述可知，熵或基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的初度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。

3）决策树的深度达到指定的条件

    节点的深度可以理解为节点与决策树跟节点的距离，如果根节点的子节点的深度为1，因为这些节点与根节点的距离为1，子节点的深度比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。

4）所有特征已经使用完毕，不能继续进行分裂

    被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

4.决策树的优化

    决策树生成之后，我们就可以用来对分类未知的样本进行预测，这时决策树的泛化性能就显得很重要了。一棵生成之后不加任何操作的决策树往往不是泛化性能非常好的，常用的解决办法是剪枝。决策树的剪枝分为两种，一种是预剪枝，另一种是后剪枝，下面分别来介绍。

预剪枝

    预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。具体在什么时候停止决策树的生长有很多种不同的方法：

        1）一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长。

        2）到达此结点的实例个数小于某一个阈值也可停止树的生长。

        3）到达此结点的实例个数小于某一个阈值也可停止树的生长。

        4）还有一种更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。

优缺点：

    优点：由于预剪枝不必生成整颗决策树，且算法相对简单，效率很高，适合解决大规模问题。但是尽管这一方法看起来很直接，但是怎样精确地估计何时停止树的增长是相对困难的。

    缺点：预剪枝有一个缺点，即视野效果问题。也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。

后剪枝

后剪枝的通常做法是极小化决策树整体的损失函数。

4.处理缺失数据

决策树模型还有一个很大的优势，就是可以容忍缺失数据。如果决策树中某个条件缺失，可以按一定的权重分配继续往以后的分支走，最终的结果可能有多个，每个结果有一定的概率，即：

    最终结果=某个分支的结果*该分支的权重(该分支下的结果数/总结果数)

5.sklearn中决策树的使用

    5.1决策树的参数：

1）criterion{''gini","entropy"},default='gini'确定决策树是基于基尼指数还是信息熵。

2）max_depth：树的层数，限制树的最大深度，超过设定深度的树枝全部剪掉，这是用的最广泛的剪枝参数，在高维度低样本量时非常有效。决策树多生长一层，对样本量的需求会增长一倍，所以限制树深度能够有效地限制过拟合。在集成算法中也非常实用。实际使用时，建议从=3开始尝试，看看拟合的效果再决定是否增加设定深度。实际层数为max_depth+1考虑。

3）min_impurity_decrease：限制决策树的生长，如果节点的不纯度(Gini,Gain)小于这个阈值，就不在生成子节点。

4）min_impurity_split：不纯度必须大于这个值，不然不分裂。

5）class_weight：可以用来定义某一个类别的权重，让这一个类在计算的时候，信息增益变得稍微大一些。

6）random_state：随机数种子，固定种子之后，训练的模型是一样的。

7）splitter：用来控制决策树中的随机选项的，有两种输入值，输入”best"，决策树在分枝时虽然随机，但是还是会优先选择更重要的特征进行分枝（重要性可以通过属性feature_importances_查看），输入“random"，决策树在分枝时会更加随机，树会因为含有更多的不必要信息而更深更大，并因这些不必要信息而降低对训练集的拟合。这也是防止过拟合的一种方式。当你预测到你的模型会过拟合，用这两个参数来帮助你降低树建成之后过拟合的可能性。当然，树一旦建成，我们依然是使用剪枝参数来防止过拟合。所以要想泛化好，最好splitter设置成random。

和剪枝相关的参数：

1）min_samples_leaf：一个节点在分支后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生，或者，分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生。

2）一般搭配max_depth使用，在回归树中有神奇的效果，可以让模型变得更加平滑。这个参数的数量设置得太小会引起过拟合，设置得太大就会阻止模型学习数据。一般来说，建议从=5开始使用。如果叶节点中含有的样本量变化很大，建议输入浮点数作为样本量的百分比来使用。同时，这个参数可以保证每个叶子的最小尺寸，可以在回归问题中避免低方差，过拟合的叶子节点出现。对于类别不多的分类问题，=1通常就是最佳选择。

3）min_weight_fraction_leaf：有了权重之后，样本量就不再是单纯地记录数目，而是受输入的权重影响了，因此这时候剪枝，就需要搭配min_ weight_fraction_leaf这个基于权重的剪枝参数来使用。另请注意，基于权重的剪枝参数（例如min_weight_ fraction_leaf）将比不知道样本权重的标准（比如min_samples_leaf）更少偏向主导类。如果样本是加权的，则使用基于权重的预修剪标准来更容易优化树结构，这确保叶节点至少包含样本权重的总和的一小部分。

分类决策树score函数返回的是预测的准确率

回归树的接口score返回的是R2

注意在sklearn中实现的决策树都是二叉树。

    5.2 决策树的可视化

        可以使用graphviz安装包：pip install graphviz

    feature_name = ["A","B","C"]

    importgraphvizdot_data = tree.export_graphviz(clf ,feature_names= feature_name ,class_names=["1","2","3"]                                                                               ,filled=True,rounded=True,out_file=None)

     graph = graphviz.Source(dot_data)graph

6.算法的优缺点总结

来看看决策树算法作为一个大类别的分类回归算法的优缺点。

    优点：

1）简单直观，生成的决策树很直观。对于异常点的容错能力好，健壮性高。

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

3）使用决策树预测的代价是，m为样本数。

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

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

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

    缺点：

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

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

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

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

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