决策树是一种树状结构模型，可以进行基本的分类与回归，决策树也是集成学习经常采用的基模型。
    决策树有多种类型，常用的ID3决策树、C4.5决策树、CART决策树等，不同决策树之间总体思想大同小异，主要涉及三个要素：特征选择、决策树生成和决策树剪枝。

1 特征选择

在实际建立决策树的过程中，每次特征选择都要遵循对应的标准，比如信息增益、信息增益比、基尼系数等。

1.1 信息增益

熵:

在信息论中，用熵来度量随机变量的不确定程度，随机变量的不确定性越大，熵值越大。

如果一个随机变量$Y$的可能取值为$Y=\left \{ c_1,c_2,…,c_k \right \} $，其概率分布为$P(Y=c_i)=p_i,i=1,2,…,K$。则随机变量$Y$的熵定义为$H(Y)$，即：

log为以2或者e为底的对数。

联合熵：

当有两个随机变量$X$和$Y$时，同理可以定义它们的联合熵$H(X,Y)$，即：

条件熵：

有了联合熵，就可以得到条件熵的表达式了，在随机变量$X$发生的前提下，随机变量$Y$发生，新带来的的熵，用$H(Y|X)$表示：

条件熵用来衡量在已知随机变量$X$的条件下，随机变量$Y$的不确定性。

信息增益:

随机变量$Y$的熵$H(Y)$与$Y$的条件熵$H(Y|X)$之差就是信息增益，记为$g(Y,X)$，即：

实际上，熵与条件熵的差也称为互信息。ID3决策树使用信息增益作为特征选择标准，信息增益依赖于特征，不同特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。

1.2 信息增益比

用信息增益作为划分训练集特征的标准时，有一个潜在的问题，那就是相比之下其会倾向于选择类别取值较多的特征，因此人们提出使用信息增益比来对这一问题进行校正。

特征$X$对训练集的信息增益比定义为特征$X$的信息增益$g(Y,X)$与特征$X$的取值的熵$H(X)$的比值，记为$g_R(Y,X)$，即：

1.3 基尼系数

基尼系数可以用来度量任何不均匀分布，且介于0~1之间的数(0指完全相等，1指完全不相等)。分类度量时，总体包含的类别越杂乱，基尼系数就越大（与熵的概念类似）。

基尼系数主要用来度量数据集的不纯度，基尼系数越小，表明样本只属于同一类的概率越高，即样本纯净度越高，在计算出数据集某个特征所有的基尼系数之后，就可以得到利用该特征进行样本产生的基尼系数增加值(GiniGain)，决策树模型在生成的过程中就是递归选择GiniGain最小的节点作为分叉点，直至子数据集都属于同一类或者所有特征用光。

在分类问题中，假设有K个类别$c_1,c_2,…,c_k$，样本点属于第k类的概率为$p_k$，则该概率分布的基尼系数定义为：

对于给定的样本集合D，其基尼系数为：

其中，$c_k$是属于第k类的样本子集，K是类别的个数。

2 决策树生成

2.1 ID3决策树

ID3决策树使用信息增益作为特征选择标准。

输入：

假设训练数据集D包含M个样本，样本一共包含有K个类别，类别集合为C；每个样本含有N个特征，特征集合为F，停止分裂的阈值为$\varepsilon $。

输出：决策树T。

步骤如下：

第1步：如果训练集D中的M个样本不属于同一类别，但是特征集合只含有单个特征，则直接返回单节点树T，且该样本集合D中实例数最大的类作为该树节点的类别。

第2步：如果训练集D中的M个样本不属于同一类别，但是特征集合只含有单一特征，则也直接返回单节点树T，且该样本集合D中实例数最大的类作为该数节点的类别。

第3步：如果非以上两种情况，则分别计算特征集合F中的N个特征的信息增益，选择信息增益最大的特征$F_n$，如果该信息增益小于阈值$\varepsilon$，则返回上述单节点树T，其将该样本集合D中实例数最大的类作为该树节点的类别。

第4步：否则，按照特征$F_n$的不同取值种类，将对应的样本D分成不同的子类别$D_i$，每个字类别产生一棵树的子节点。

第5步：对于每个子节点，令$D=D_i,F=F-F_n$，递归调用第1步到第4步，直到得到满足条件的ID3决策树。

2.2 C4.5决策树

使用信息增益来选择特征的一个缺点就是容易偏向于优先选取取值种类较多的特征，除此之外，ID3决策树还有两个缺点：1）不能处理连续值的特征；2）容易过拟合。

针对以上3个缺点，C4.5决策树给出了解决办法。

针对缺点1：ID3决策树容易偏向于优先选取取值种类较多的特征。

解决办法是使用信息增益比来替代信息增益进行特征选择。

针对缺点2：ID3决策树不能处理连续值的特征。

C4.5决策树的思路是先将连续的特征离散化，比如，年收入特征是一个连续特征，我们可以先对训练样本中年收入特征下的所有取值进行排序，找出类别标签有变化的地方，作为阈值进行划分。

针对缺点3：ID3决策树容易过拟合

决策树的过拟合问题主要是由于树的分叉过细造成的，决策树分叉过细会导致最后生成的决策树模型对训练集中的数据拟合很好，但是对新的预测数据拟合得较差。

C4.5决策树引入了正则化项进行初步的剪枝来缓解过拟合问题。

除了以上三点改进外，C4.5决策树和ID3决策树几乎一样。

2.3 CART决策树

C4.5决策树虽然在ID3决策树的基础上做了一些改进，但是还是存在一些不足，主要表现在以下三点：

第一，C4.5决策树使用了熵模型，以信息增益比作为特征的选择标准，每次划分子树的过程中会涉及很多的对数计算，计算复杂度较高。

第二，ID3决策树和C4.5决策树采用的都是多叉树形式，每次分叉成子树时都是按照其所选择特征包含的所有种类数来划分的，也就是说，一旦按照某个特征切分后，该特征在之后的算法执行过程中将不再起作用，但事实证明，这样划分特征是过于粗糙的，特征信息的利用率低。另外C4.5决策树对连续值的处理方式是按照区间将其离散化，这样或多或少会损失一部分信息。

第三，当我们面对的不是一个类别的预测问题，而是一个连续结果预测的回归问题时，ID3决策树和C4.5决策树都无法处理。

针对问题1：ID3决策树和C4.5决策树特征选择过程对数计算复杂度高。

当CART决策树用于分类任务时，采用基尼系数作为特征选择的标准，当CART决策树用于回归任务时，采用平方误差最小化准则进行特征选择，可以减少大量的对数运算问题。

针对问题2：ID3决策树和C4.5决策树对特征划分过于迅速

与ID3决策树和C4.5决策树采用多叉树进行特征划分不同，CART分类树与回归树采用二叉树来对每个特征进行划分。

针对问题3：ID3决策树和C4.5决策树不能处理回归问题。

回归问题的结果取值是很多个连续的值，因此不能像分类问题一样采取信息增益或基尼系数等特征选择标准，那怎么办？很简单，直接使用均方误差就行，即计算每一次特征划分后的结果与实际结果值之间的均方误差，采用均方误差最小的划分作为最优划分。

解决了特征选择问题，还剩另外一个结果处理的问题，所以决策树采用的结果处理方式是对每一个叶子节点里面包含的样本类别进行统计，然后选择样本类别占多数的类别标签作为该叶子结点的类别标签。对于回归问题，稍作变化，即每个叶子节点对应的结果就取该叶子节点中所有样本点标签值的均值。

2.3.1 CART分类树

CART分类树的生成过程以基尼系数最小准则来选择特征。

输入:假设训练数据集D包含M个样本，样本一共有K个类别，类别集合为C，每个样本含有N个特征，特征集合为F。

输出：CART分类树T。

步骤如下：

第1步：如果训练集D中的M个样本已经属于同一类别，则直接返回单节点树T，并将该唯一类$C_k$作为该树节点的类别。

第2步：否则，分别计算特征集合F中N个特征下面各个切分点的基尼系数，选择基尼系数最小的划分点将训练集D划分为$D_1$和$D_2$两个子集，分别对应二叉树的两个子节点上。

第3步：令左右节点的数据集$D_1=D,D2=D$，分别递归调用第1步和第2步，直到得到满足条件的CART分类树。

2.3.2 CART回归树

前面说过，CART回归树和CART分类树的生成过程基本相似，差别主要体现在特征选择标准和结果输出处理方式两点上。

差别1：特征选择标准不同

对于CART分类树，在选取特征的最优划分点时，使用的是某一特征的某个划分点对应的基尼系数值，而对于CART回归树，我们使用了均方误差来衡量。

差别2：决策树结果输出处理方式不同

对于分类情况，CART分类树对结果的处理方式是对每一个叶子节点里面包含的所有样本的类别进行统计，然后选择样本类别占多数者对应的类别标签作为该叶子节点的类别标签；CART回归树的输出结果不是类别，因而把最终各个叶子结点中所有样本对应结果值的均值或者中位数当做预测的结果输出。

3 决策树剪枝

决策树算法很容易对训练集过拟合，从而导致泛化能力较差，为了解决这个问题，一般需要对CART决策树进行剪枝。

剪枝有先剪枝和后剪枝两种，先剪枝是在生成决策树的过程中就采取一定措施来限制某些不必要的子树的生成。后剪枝就是先使用训练集中的大部分数据去尽可能生成一棵最大的树，然后从决策树的底端开始不断剪枝，直到形成一棵只有一个根节点的子树$T_0$，得到一个剪枝后的子树序列${T_0,T_1,…,T_K}$，最优利用余下的数据进行交叉验证，选出其中的最优子树。实际使用较多的是后剪枝。