决策树模型

决策树模型概述

决策树模型是表示基于特征对实例进行分类的树形结构，决策树可以转换为一个if-then规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。

但是直接从可能的决策树中直接选取最优的决策树是NP完全问题现实中利用启发式方法学习次优的决策树。

决策树学习算法包括三部分 * 特征选择：选取对训练数据能够分类的特征 * 树的生成：通常用特征选择准则(信息增益，信息增益率，基尼指数), 从根节点开始，递归的产生决策树。这相当于用上述指标不断地选取局部最优特征，或将训练集分割为能够基本正确分类的子集。 * 树的剪枝：由于生成的决策树存在过拟合问题，需要对其进行剪枝，

常用的决策树算法有ID3，C4.5，CART ## 特征选择准则 ### 信息增益 #### 熵

首先引入熵(entropy)和条件熵的定义，在信息论和概率统计中熵为表示随机变量不确定性的度量，设X是一个取有限值的离散速记变量，其概率分布为 \[ P(X=x_i)=p_i\quad i = 1,2\dots n \] 则随机变量的熵可定义为: \[ H(X)= -\sum\limits_{i=1}^n p_i \log p_i \] 当\(p_i=0\),定义\(0\log 0= 0\), 当对数以2为底或以\(e\)为底时，熵的单位为称为比特bit, 或nat纳特.因为熵只依赖于\(X\)的分布，而与\(X\)的取值无关，所以可以将\(X\)的熵记作\(H(P)\): \[ H(p)= -\sum\limits_{i=1}^n p_i \log p_i \] 熵越大，随机变量的不确定性就越大，范围为： \[ 0\leq H(p)\leq \log n \] 当随机变量只取两个值（1，0）时 \[ p(X=1)=p \quad P(X=0)=1-p \quad 0\leq p\leq 1 \] 熵表示为： \[ H(p) = -p\log_2 p -(1-p)\log_2 (1-p) \]

当有随机变量(X,Y)时，联合概率分布为 \[ P(X= x_i, Y=y_i) = P_{ij},\quad i = 1,2\dots n;\quad j = 1,2\dots m \] 条件熵\(H(Y|X)\) 表示在已知随机变量\(X\)的条件下随机变量\(Y\)的不确定性。随机变量\(X\)给定条件下随机变量\(Y\)的条件熵\(H(Y|X)\) 定义为\(X\)给定条件下\(Y\)的条件概率分布的熵对\(X\)的数学期望。 \[ H(Y|X)=\sum\limits_{i=1}^n p_iH(Y|X=x_i)\quad p_i=P(X=x_i),i=1,2\dots n \] 熵和条件熵中概率由数据估计（极大似然估计）得到时，其命名分别为经验熵和经验条件熵。

信息增益表示得知特征\(X\)的信息而使类\(Y\)的信息不确定性减少的程度

信息增益定义

特征\(A\)对训练数据集\(D\)的信息增益\(g(D,A)\),定义为集合\(D\)的经验熵\(H(D)\)与特征\(A\)给定条件下\(D\)的经验条件熵\(H(D|A)\)之差。 \[ g(D,A) = H(D)-H(D|A) \] 通常熵\(H(Y)\)与条件熵\(H(Y|X)\)之差称为互信息，决策树学习中的信息增益等价于训练数据集中类和特征的互信息，且信息增益大的特征具有更强的分类能力。

信息增益率

以信息增益作为划分训练数据集的特征，存在偏向选择取值较多特征的问题 若某一列数据没有重复，ID3算法倾向于把每一列数据自成一类，此时信息增益极大。 \[ H(D|A) = \sum\limits_{i=1}\frac{1}{n}\log_2(1)=0 \] 使用信息增益率可以对这一问题进行校正。

信息增益率定义

特征\(A\)对训练数据集D的信息增益比\({\large g}_{R}(D,A)\)定义为其信息增益\(g(D,A)\)于训练数据集\(D\)关于特征\(A\)的值的熵之比，即 \[ {\large g}_R(D,A) = \frac{g(D,A)}{H_A(D)} \] 式中，\(H_A(D) = -\sum\limits_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}\), \(n\)为特征\(A\)取值的个数.

基尼指数

分类问题中，假设有\(K\)个类，样本点属于第\(k\)类的概率为\(p_k\), 则概率分布的基尼指数定义为 \[ Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k)=1-\sum\limits_{k=1}^{K}p_k^2 \]

对于二分类问题，样本点属于第一个类的概率为\(p\)，则概率分布的基尼指数为 \[ Gini(p) = 2p(1-p) \]

对于给定的样本集合\(D\), 其基尼指数为 \[ Gini(D) =1- \sum\limits_{k=1}^{K}\left ( \frac{|C_k|}{|D|}\right) \] 此时 \(C_k\)是\(D\)中属于第\(k\)类的样本子集，\(K\)为类的个数.

如果样本集合\(D\)根据特征\(A\)是否取某一可能值\(a\)被分割为\(D_1\)和\(D_2\)两部分 \[ D_1 =\{ (x,y) \in D|A(x) = a\}, \quad D_2 = D- D_1 \] 即在特征\(A\)的条件下，集合\(D\)的基尼指数定义为 \[ Gini(D,A) = \frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2) \] 基尼指数\(Gini(D)\)表示集合\(D\)的不确定性，基尼指数\(Gini(D,A)\)表示经\(A=a\)分割后集合D的不确定性，基尼指数值越大，样本集合的不确定性也越大，与熵类似。

ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树，具体来说：从根结点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同的取值来建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树，ID3相当于用极大似然法进行概率模型的选择。队训练数据集或子集\(D\)，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

ID3 算法缺点

不适合应用于特征连续数据，和缺失值数据。该算法只有树的生成，容易过拟合

## C4.5 算法

C4.5算法于ID3算法相似，C4.5算法是对ID3算法进行了改进，在树的生成过程中应用信息增益比来选择特征。由于信息增益对可取值数目较多的属性有所偏好；而信息增益率对可取值数目较少的属性有所偏好所以C4.5决策树先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。而不是大家常说的直接选择信息增益率最高的属性

C4.5 算法优点

可以处理连续性特征，因为可以采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到又子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。
C4.5还可以处理缺失值数据，对于缺失特征可以不被应用于信息增益和熵的计算。
可以在树构造过程中进行剪枝，在构造决策树的时候，尽量不考虑挂着稀少元素的节点，减少过拟合。

C4.5 算法缺点

C4.5会构造许多无助于分类任务的零值或接近零的空节点。
当算法模型选取的数据具有不常见的特征时，特别是在有噪声的情况下，会发生过拟合。

CART

分类与回归树，是应用广泛的决策树学习算法。 CART同样由特征选择，树的生成，剪枝组成，既可以应用于分类也可以用于回归。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法，CART假设决策树为二叉树，内部节点特征取值为“是”和“否”。左分支为“是”的分支，右分支为“否”分支。这样的决策树等价于递归的二分每个特征，将输入空间（特征空间）划分为有限个单元，并在这些单元上确定预测的概率分布，即在输入给定的条件下输出的条件概率分布。

CART算法由两步组成

决策树的生成：基于训练数据集生成决策树，生成的决策树要尽量大
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失最小函数来作为剪枝的标准。

决策树的生成就是递归地构建二叉决策树的过程，对于回归树用平方误差最小化准则，对于分类树应用基尼指数最小化准则进行特征选择生成二叉树. cart算法为什么选用gini指数？

CART对于连续特征思想与C4.5类似，都是将连续特征离散化，但CART应用的是基尼系数，C4.5应用的是信息增益比， CART分类处理离散特征思路是不断地二分离散特征。

#### CART回归树和CART分类树的区别 * 连续值的处理方法不同 * 决策树建立后做预测的方式不同

对于连续值的处理

CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型，但是对于回归模型，我们使用了常见的和方差的度量方式，CART回归树的度量目标是，对于任意划分特征\(A\)，对应的任意划分点s两边划分成的数据集\(D_1\)和\(D_2\)，求出使\(D_1\)和\(D_2\)各自集合的均方差最小，同时\(D_1\)和\(D_2\)的均方差之和最小所对应的特征和特征值划分点。 \[ min_{A,s}\left[\underbrace{min}_{c_1}\sum\limits_{x_i\in D_1(A,s)}(y_i-c_1)^2+\underbrace{min}_{c_2}\sum\limits_{x_i\in D_2(A,s)}(y_i-c_2)^2\right] \]

其中，\(c_1\)为\(D_1\)数据集的样本输出均值，\(c_2\)为\(D_2\)数据集的样本输出均值。

决策树建立后做预测的方式

CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

CART算法的剪枝

CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用均方差，一个使用基尼系数。

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

也就是说，CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二部是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

CART 优点

是非参数模型，不依赖数据的特定分布
CART不受输入变量中的异常值的显著影响。
可以使决策树“过度生长”，然后将树修剪回最佳大小。这种方法降低由于过早停止而忽略数据集中重要结构的可能性。
CART将测试与测试数据集和交叉验证结合起来，以更准确地评估拟合的优劣。
CART可以在树的不同部分多次使用同一特征。这样可以揭示变量集之间复杂的相互依赖关系。
CART可以与其他预测方法结合使用来选择变量的输入集。

CART 缺点

模型是一个阶跃函数，而不是一个连续的值。
需要一个足够大的树来得到比较好的结果。
模型稳定性不足，随机数据波动可能导致完全不同的树。
CART在建模线性结构方面做得很差。

决策树算法总结

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持	支持
CART	分类，回归	二叉树	基尼系数，均方差	支持	支持	支持

决策树算法优点

简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化，处理缺失值。
使用决策树预测的代价是O(log2m)。 m为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树可解释性强
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。

决策树算法缺点

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。