决策树是一种基本的分类与回归方法，分类问题的决策树是基于树结构对数据进行划分，表示基于特征对实例进行分类的过程。广泛应用于金融分控、医疗辅助诊断等诸多行业。

决策树的步骤：
特征的选取 —>决策树的生成 —>决策树的修剪

决策树表示一个条件概率分布，可以用if-else规则表示，每个实例都被且只被一条路径或一个规则所覆盖。

决策树的构建过程是一个递归过程，采用递归的方式选择最优特征，并根据所选择的特征对训练数据进行分割，使各个子数据集有一个最好的分类。伪代码如下：

函数存在三种返回状态：（1）当前节点包含的样本全部属于同一类别，无需继续划分；（2）当前属性集为空或者所有样本在某个属性上的取值相同，无法继续划分；（3）当前节点包含的样本集合为空，无法划分。

进行特征选择，是希望通过一个特征所分类得结果是有分类能力得，跟随机生成得结果能够有所差别。
特征选择是决定用哪个特征来划分特征空间。通常以信息增益和信息增益比作为特征选择的准则。

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即： g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)等价于训练数据集D中类与特征的互信息。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较，选出信息增益最大的特征。
信息增益的算法如下：

使用信息增益比，可以校正信息增益中偏向选择取值较多的特征的问题。
特征A 对训练数据集D的信息增益比Gr(D,A)定义为其信息增益与训练数据集关于特征A的值的熵Ha(D)之比: g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A)=\frac{g(D,A)}{H_A(D)} gR​(D,A)=HA​(D)g(D,A)​其中， H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} HA​(D)=−∑i=1n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​,n是特征A取值的个数。
Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。

Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。

sklearn.tree——提供了决策树模型，用于解决分类和回归问题。
几个重要参数说明如下：
1.criterion
Criterion这个参数正是用来决定模型特征选择的计算方法的。sklearn提供了两种选择：输入”entropy“，使用信息熵（Entropy）输入”gini“，使用基尼系数（Gini Impurity）

2.random_state & splitter
random_state用来设置分枝中的随机模式的参数，默认None，在高维度时随机性会表现更明显。splitter也是用来控制决策树中的随机选项的，有两种输入值，输入”best"，决策树在分枝时虽然随机，但是还是会优先选择更重要的特征进行分枝（重要性可以通过属性feature_importances_查看），输入“random"，决策树在分枝时会更加随机，树会因为含有更多的不必要信息而更深更大，并因这些不必要信息而降低对训练集的拟合。

3.max_depth
限制树的最大深度，超过设定深度的树枝全部剪掉。这是用得最广泛的剪枝参数，在高维度低样本量时非常有效。决策树多生长一层，对样本量的需求会增加一倍，所以限制树深度能够有效地限制过拟合。
4.min_samples_leaf
min_samples_leaf 限定，一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生，或者，分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生。一般搭配max_depth使用，在回归树中有神奇的效果，可以让模型变得更加平滑。这个参数的数量设置得太小会引起过拟合，设置得太大就会阻止模型学习数据。

决策树的生成算法有：ID3、C4.5、CART。三种生成算法的区别是：ID3算法是采用信息增益衡量特征选取，C4.5是采用信息增益比衡量特征的选取，CART是采用基尼指数来划分。

在决策树各个结点上，根据信息增益准则进行特征选择，递归的构建决策树。
具体方法是：
1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点。
2）再对子结点递归地调用以上方法，构建决策树。
3）直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。
ID3相当于用极大似然法进行概率模型的选择。
算法步骤：
输入 ：训练数据集，特征集 A A A，阈值
输出：决策树

1若 D D D中所有实例属于同一类 C k C_k Ck​,则 T T T为单结点树，并将类 C k C_k Ck​作为该结点的标记，返回 T T T

2 若 A = ∅ A=\emptyset A=∅,则 T T T为单结点树，并将 D D D中实例数最大的类 C k C_k Ck​作为该类的标记，返回 T T T

3 否则，按照上述介绍信息增益的算法计算 A A A中各特征对 D D D的信息增益，选择信息增益最大的特征 A g A_g Ag​

4如果 A g A_g Ag​的信息增益小于阈值 ϵ \epsilon ϵ，则 T T T为单结点树，并将 D D D中实例数最大的类 C k C_k Ck​作为该结点的标记，返回 T T T

5 否则，对 A g A_g Ag​的每一个可能值 a i a_i ai​， A g = a i A_g=a_i Ag​=ai​，将 D D D进行分割成非空子集 D i D_i Di​,将 D i D_i Di​中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 T T T,返回 T T T

6 对第 i i i个子结点，以 D i D_i Di​为训练集，以 A − A g A-{A_g} A−Ag​为特征集,递归的调用上述步骤1~5，得到子树 T i T_i Ti​,返回 T i T_i Ti​

决策树的生成中，用信息增益比代替信息增益进行特征选取。

算法步骤：
输入 ：训练数据集，特征集 A A A，阈值
输出：决策树

1若 D D D中所有实例属于同一类 C k C_k Ck​,则 T T T为单结点树，并将 C k C_k Ck​作为该结点的类，返回 T T T

2 若 A = ∅ A=\emptyset A=∅,则 T T T为单结点树，并将 D D D中实例数最大的类 C k C_k Ck​作为该类的类，返回 T T T

3 否则，按照上述介绍信息增益比的算法计算 A A A中各特征对 D D D的信息增益比，选择信息增益比最大的特征 A g A_g Ag​

4如果 A g A_g Ag​的信息增益比小于阈值 ϵ \epsilon ϵ，则 T T T为单结点树，并将 D D D中实例数最大的类 C k C_k Ck​作为该结点的类，返回 T T T

5 否则，对 A g A_g Ag​的每一个可能值 a i a_i ai​， A g = a i A_g=a_i Ag​=ai​，将 D D D进行分割成非空子集 D i D_i Di​,将 D i D_i Di​中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 T T T,返回 T T T

6 对第 i i i个子结点，以 D i D_i Di​为训练集，以 A − A g A-{A_g} A−Ag​为特征集,递归的调用上述步骤1~5，得到子树 T i T_i Ti​,返回 T i T_i Ti​

CART从其名字得知，它既可以用于分类问题，也可以用于回归问题，使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树，递归的二分每个特征。
决策树的CART生成，就是递归的构建二叉决策树的过程。
回归树中采用平方误差最小化准则来选择特征并进行划分。
最小二乘回归树算法：

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
CART生成算法：

剪枝，是对过拟合的决策树进行简化。
决策树的剪枝常根据极小化决策树整体的损失函数或代价函数来实现。
假设树的叶结点个数为|T|，t是树的一个叶结点，其上有Nt个样本，其中k类的样本有Ntk个，k=1,2,3…K，Ht(T)为叶结点上的经验熵，参数大于0,那么决策树损失函数可以定义为：
C α ( T ) = ∑ t = 1 n N t H t ( T ) + α ∣ T ∣ C_{\alpha}(T)=\sum_{t=1}^nN_tH_t(T)+\alpha|T| Cα​(T)=t=1∑n​Nt​Ht​(T)+α∣T∣
而这其中经验熵为： H t ( T ) = − ∑ k N t k N t l o g N t k N t H_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t} Ht​(T)=−k∑​Nt​Ntk​​logNt​Ntk​​
将经验熵代入，可以得到公式： C ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) = − ∑ t = 1 T ∑ k = 1 K N t k l o g N t k N t C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{T}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t} C(T)=t=1∑∣T∣​Nt​Ht​(T)=−t=1∑T​k=1∑K​Ntk​logNt​Ntk​​所以有 C α ( T ) = C ( T ) + α ∣ T ∣ C_{\alpha}(T)=C(T)+\alpha|{T}| Cα​(T)=C(T)+α∣T∣

这里面 C ( T ) C(T) C(T)指的是模型对训练数据的预测误差，而 ∣ T ∣ |T| ∣T∣表示的就是模型的叶结点个数，代表了模型的复杂度。参数 α ≥ 0 \alpha\geq0 α≥0在两者之间进行平衡， α = 0 \alpha=0 α=0意味着只考虑模型对训练数据的预测误差，即只考虑模型与训练数据的你和程度。

所谓的剪枝，就是当 α \alpha α确定的时候，选择损失函数最小的模型， α \alpha α确定时候，子树越大，训练数据拟合程度越好，但是模型的复杂度就越大，相反的，子树越小，模型的复杂度就越小，对训练数据的拟合程度越差，但是泛化能力相对较好，损失函数同时考虑二者的影响，对两者进行平衡，达到一个平衡的最优！

本质上 这样的损失函数最小化原则等价于正则化的极大似然估计，利用损失函数最小化原则进行剪枝，就是利用正则化的极大似然估计进行模型的筛选！

决策树生成只考虑了通过信息增益（或信息增益比）准则对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数，还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

GBDT(Gradient Boosting Decision Tree)是一种迭代的决策树算法，由多棵决策树组成。

随机森林能够用于分类和回归问题，可以处理大量特征，并能够帮助估计用于建模数据变量的重要性。
随机森林在对决策树进行bagging的基础上，在决策树的训练过程中引入了随机属性选择。
bagging思想即：通过在训练样本集中进行有放回的采样得到多个采样集，基于每个采样集训练出一个基学习器，再将基学习器结合起来共同实现分类或者回归。

1）从样本集N中有放回地随机采样选出n个样本。
2）从所有特征中随机选择k个特征，对选出的样本利用这些特征建立决策树(一般是CART方法)。
3）重复以上两步m次，生成m棵决策树，形成随机森林，其中生成的决策树不剪枝。
4）对于新数据，经过每棵决策树投票分类。

ID3、C4.5、CART的区别对比如下表：

***相同点：
都是由多棵树组成；最终结果都是由多棵树共同决定；