决策树算法

一、通俗理解熵和基尼不纯度

1.信息熵

$\quad$ 熵度量事物的不确定性，越不确定的事物，它的熵就越大。随机变量 $Y$ 的熵的表达式如下：
$H(Y)= - \sum_{j=1}^m p_j\ log\ p_j$
其中 $m$ 代表了 $y$ 的 $m$ 种可能的离散取值； $p_j$ 表示随机变量 $Y$ 的概率分布，即 $p_j=P(Y=y_j)，j=1,2...m$ 。

2.联合熵

由单个变量信息熵可推广至多个变量的联合熵，即：
$H(X,Y)=\sum_{i=1}^n \sum_{j=1}^m p_{ij}\ log\ p_{ij}$
其中 $p_{ij}$ 表示随机变量 $(X,Y)$ 的联合概率分布，即 $p_{ij}=P(X=x_i,Y=y_i) ，i=1,2...n,\ j=1,2...m$ .

3.条件熵

$\quad$ 条件熵定义为：给定随机变量 $X$ 的条件下，随机变量 $Y$ 的条件概率分布的熵对随机变量 $X$ 的数学期望。
则根据定义可推导条件熵公式：
$\quad\ H(Y|X)=\sum_{i=1}^n P(X=x_i) H(Y|X=x_i)$

$=- \sum_{i=1}^n P(X=x_i) \sum_{j=1}^m P(Y=y_j|X=x_i)logP(Y=y_j|X=x_i)$

$=- \sum_{i=1}^n \sum_{j=1}^m P(X=x_i,Y=y_j)logP(Y=y_j|X=x_i)$

条件熵表示在已知随机变量 $X$ 的情况下，随机变量 $Y$ 的不确定性。

4.信息增益\互信息

信息增益 = 信息熵 - 条件熵，即
$I(X)=H(Y)-H(Y|X)$
表示在已知随机变量 $X$ 的情况下，随机变量 $Y$ 的不确定性减少的程度。ID3算法使用信息增益选择最优特征。

5.基尼不纯度

$\quad$ 基尼不纯度：指随机抽取两个样本，其类别标记不一致的概率。
$\quad$ 假设有 $k$ 个类别，选中子集为第 $k$ 个类别的概率为 $p_k$ ，则基尼系数表达式为：
$Gini(D)=\sum_{k=1}^K p_k(1-p_k)=1 - \sum_{k=1}^K p_k^2$
假设有 $k$ 个类别，随机抽取一个样本，类别 $j$ 出现的概率为 $p_j$ ；再随机抽取第二个样本，类别 $j$ 出现的概率为 $p_j^2$ ，假设 $k$ 个类别出现的概率是相互独立的，则随机抽取两个样本出现类别一致的概率为 $\sum_{k=1}^K p_k^2$ ，则类别不一致的概率为 $1 - \sum_{k=1}^K p_k^2$ 。考虑极端情况 $p_k$ =1，基尼不纯度为0，数据集不确定性为0（即固定的属于某一类别）。
CART中使用Gini不纯度做特征选择，与信息增益的理念类似，在已知某特征A分布的情况下，基尼不纯度减小的程度作为最优特征划分的标准。

二、决策树分类算法

1.ID3

决策树的生成需要考虑特征选择方法及停止条件。
停止条件为：
$\quad$ (1)子集中同属同一类标记 $y$ ，例如所有样本同属0类或1类，不纯度为0，无需继续向下划分；
$\quad$ (2)自顶而下已使用完所有特征；
$\quad$ (3)小于给定信息增益划分的阈值。

ID3使用信息增益进行特征选择。算法过程为：
$\quad$ 输入：数据集 $D=\{ (x^{(1)},y_1),(x^{(2)} , y_2),...(x^{(n)} , y_n) \}$ ，其中 $x^{(i)}=(x_1^{(i)} , x_2^{(i)} , ...x_d^{(i)})$ 。数据集 $D$ 有 $|D|$ 个样本， $d$ 个离散特征，特征集合为 $A=\{A_1,A_2...A_d\}$ 。
$\quad$ 输出：决策树 $T$

生成决策树过程：

(1)计算信息增益：
$\quad$ 首先计算数据集 $D$ 整体的信息熵 $H(D)$ ，假设样本标记共有 $K$ 个类别， $|D_k|$ 表示标记为 $k$ 的样本个数， $|D|$ 表示总样本量；则
$H(D)=-\sum_{k=1}^K P(Y=k)logP(Y=k)=-\sum_{k=1}^K \frac{|D_k|}{|D|} log\frac{|D_k|}{|D|}$

$\quad$ 接下来计算条件熵，在选择特征 $A_j$ （特征集合 $A$ 中任意一个特征）的情况下，计算数据集的信息熵，根据定义可得：
$\quad\ H(D|A_j)$
$=-\sum_a P(A_j=a) \sum_{k=1}^K P(Y=k|A_j=a)logP(Y=k|A_j=a)$
$=-\sum_a \frac{|D_a|}{|D|} \sum_{k=1}^K \frac{|D_{ak}|}{|D_a|} log\frac{|D_{ak}|}{|D_a|}$
其中 $a$ 表示属性 $A_j$ 可能的取值， $|D_a|$ 表示取值为 $a$ 的样本个数， $|D_{ak}|$ 表示特征 $A_j$ 取值为 $a$ 且标记为 $k$ 的样本个数。
$\quad$ 则信息增益为： $I(A_j)=H(D)-H(D|A_j)$

(2)分别计算特征集合 $A$ 中各个特征对数据集 $D$ 的信息增益 $I(A_j)$ ，选择其中信息增益最大的特征作为当前节点划分的特征。

(3)判断是否满足停止条件，若满足输出树 $T$ ;不满足继续(1)(2)步向下划分。

缺点

a)在分裂特征的选择中，会偏向取值个数较多的特征；
b)只考虑了分类特征；
c)没有考虑缺失值的情况。

2.C4.5

针对ID3算法的缺点，提出了C4.5算法。
1.在选取分裂特征时采用信息增益比，即信息增益和特征熵的比值：
2.对连续特征做了离散化处理：
$\quad$ 将连续特征对应的n个样本取值按照从小到大的顺序排列，取相邻两个值的均值作为一个切分点，共有n-1个切分点，分别计算以这n-1个点作为切分点进行离散化后的特征的信息增益，取信息增益最大的点为最佳切分点。
3.对缺失值的情况分别做了处理：
（1）在选择划分特征时，部分样本在某些特征上有缺失：
$\quad$ 即在计算各个特征的信息增益时，部分样本在特征上没有取值，无法确定对应的样本量。采取的方法是在计算有缺失样本的特征的信息增益时，将数据依据在该特征上是否缺失分为两部分，对每个样本赋予权重，使用无缺失的部分计算加权信息增益，并乘以系数，系数为无特征缺失样本加权后占加权总样本的比例。
（2）已经选定了划分特征，根据特征进行分枝时，样本在该特征取值上有缺失：
$\quad$ 将缺失特征取值的样本同时划分入所有的叶子节点，同时按照叶子节点的样本占比赋予权重。

3.CART分类树

CART算法在C4.5的基础上进行了优化：
1.在划分特征的选择上采用 $Gini$ 系数：
数据集 $D$ 的 $Gini$ 系数（度量数据集D的不纯度）：
$Gini(D)=\sum_{k=1}^K \frac{|D_k|}{|D|} (1-\frac{|D_k|}{|D|})$

在给定特征 $A$ 的条件下， $D$ 的 $Gini$ 系数为：

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

2.在连续特征的处理上使用 $Gini$ 系数选择最优划分点
3.CART分类树都是二叉树，特征可以重复使用
4.剪枝算法(避免过拟合)：
任意一棵树 $T_t$ ，损失函数为：
$C_\alpha(T_t)=C(T_t)+\alpha |T_t|$

$\quad$ 等式右边第二部分 $|T_t|$ 表示叶子节点的个数，代表模型复杂度，节点越多，生成的树越庞大，模型越复杂。 $\alpha$ 为超参数，平衡成本和复杂度， $\alpha$ 越大，节点数越少。
$\quad$ 仅保留根节点时， $C_\alpha(T)=C(T)+\alpha$ ；判断在子节点 $t$ 处是否需要剪枝，首先看剪枝前的损失函数为 $C_\alpha(T_t)=C(T_t)+\alpha |T_t|$ ；当 $C_\alpha (T_t)>C_\alpha(T)$ ，剪枝；当 $C_\alpha (T_t)<C_\alpha(T)$ ，保留该分枝。随着 $\alpha$ 的增大，当 $C_\alpha (T_t)=C_\alpha(T)$ 时，达到临界值，此时 $\alpha=\frac{C(T)-C(T_t)}{|T_t| -1}$ ，树 $T$ 有更小的损失函数且子节点个数更少，此时可对 $T_t$ 进行剪枝，变为叶子节点 $T$ 。

由此可以计算出每个子节点是否剪枝的 $\alpha$ 值，之后使用交叉验证选择最优的 $\alpha$ ，输出剪枝后的树 $T$ 。

三、决策树的优缺点

优点：

1.简单易于理解，可解释性强；
2.基本不需要预处理，每次进行划分时只选择一个特征，不需要进行归一化；
3.CART输入特征可以是离散的或连续的，可自动处理缺失值；
4.对于异常点不敏感，容忍度高。

缺点：

1.每次只选择一个特征进行分裂，没有考虑到特征之间的相关性；
2.容易过拟合，导致泛化能力不强；
3.样本发生一点变化，就会导致树结构发生强烈改变。

四、回归树原理

ID3和C4.5都只能用于分类，CART既可用于分类，又可用于回归。
回归问题使用均方误差度量损失，回归树在分裂过程中需要确定分裂特征及特征值点。其过程为：
假设对于任意特征 $A$ ，由划分点 $s$ 将数据集划分为 $D_1、D_2$ 两部分，划分后的损失函数为：
$\sum_{x_i \in D_1} (y_i-c_1)^2+\sum_{x_i \in D_2} (y_i-c_2)^2$
其中 $c_1、c_2$ 分别对应数据集 $D_1、D_2$ 的样本均值。
求解损失函数最小对应的特征 $A$ 及划分点 $s$ 。
回归树生成后，采用最终叶子节点的均值或中位数做预测输出。

五、决策树防止过拟合方法

1.剪枝；
2.集成方法，如随机森林；
其次，结合停止条件来看：
2.控制满足分裂条件的不纯度的阈值(min_impurity_decrease)；
3.控制叶子节点个数(max_leaf_nodes)；
4.控制继续下一次划分时叶子节点的最小样本数(min_samples_split)。

六、决策树sklearn参数

from sklearn.tree import DecisionTreeClassifier

DT参数.png

参考
https://www.cnblogs.com/pinard/p/6050306.html
https://www.cnblogs.com/pinard/p/6053344.html
https://mp.weixin.qq.com/s/v7-hhDVJUQKgNECcgab1qg
https://www.zhihu.com/question/34075616