[人工智能]从决策树到xgboost(未完)

1 决策树

1.1决策树定义

决策树的基本组成：决策节点、分支、叶子。

决策树表示给定特征条件下的概率分布。
条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元。并在每个单元上定义一个类的概率分布，就构成了一个条件概率分布。
决策树的一条路径对应于划分中的一个单元。

决策树的本质是在特征空间上的切割。

1.2信息增益

熵：设X是一个取有限个值的离散随机变量，其概率分布为：$P(X=x_i)=p_i,i=1,2,3...n$
那么X的熵为：$H(X)=?{\sum }_{i=1}^n{p}_{i}log{p}_i$
对数以2为底或者以e为底，这时熵的单位称为比特或者纳特。熵只依赖于X的分布，而与X的具体取值无关。
熵的理论解释：熵越大，随机变量的不确定性越大。$0<=H(X)<=logn$.
例如，一个骰子6个面全是1，那么$H(X)=?1?log1=0$。因为结果是确定的。
如果6个面分别为1,2,3,4,5,6，并且每个面的概率相同，都是$\frac{1}{6}$。那么$H(X)=?(\frac{1}{6}log(\frac{1}{6})+\frac{1}{6}log(\frac{1}{6})+\frac{1}{6}log(\frac{1}{6})+\frac{1}{6}log(\frac{1}{6})+\frac{1}{6}log(\frac{1}{6})+\frac{1}{6}log(\frac{1}{6}))=?(0.17?(?2.58)?6)=2.58$，这个时候的不确定性就比刚才要高。

设有随机变量(X,Y)，其联合概率分布为$P(X=x_i,Y=y_i)=p_{i,j},i=1,2,3...n;j=1,2,3...m$
条件熵H(Y|X)：表示在已知随机变量X的条件下，Y的不确定性。定义为X给定条件下Y的条件概率分布的熵对X的数学期望：$H(Y|X)={\sum }_{i=1}^n{p}_{i}H(Y|X=x_i)$

当熵和条件熵，由数据估计得到时，分别称为经验熵与经验条件熵。

信息增益：特征A对训练数据集D的信息增益g(D,A)定义为：集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差：$g(D,A)=H(D)?H(D|A)$
这表示了特征X的引入，使得分类Y的不确定性减少的程度。
互信息=信息熵H(Y)-条件熵H(Y|X)

1.3 信息增益的算法

设训练数据集为D
|D|表示其样本容量，即样本个数
设有K个类$C_k$,k=1,2,3…K
$|C_k|$表示属于类$C_k$的样本数
特征A有n个不同的取值{$a_1,a_2,...a_n$}。根据特征A的取值，将D划分为n个子集$D_1,D_2...D_n$。
$|D_i|$为子集$D_i$的样本个数
子集$D_i$中属于类$C_k$的样本集合为$D_{ik}$
$|D_{ik}|$为集合$D_{ik}$的样本数

输入：数据集D，以及特征A
输出：特征A对数据集的信息增益g(D,A)
1 计算数据集D的经验熵H(D)：$H(D)=?{\sum }_{k=1}^K\frac{|C_k|}{|D|}lo{g}_2\frac{|C_k|}{|D|}$
2 计算特征A对数据集D的经验条件熵H(D|A):$H(D|A)={\sum }_{i=1}^n\frac{|D_i|}{|D|}H(D_i)={\sum }_{i=1}^n\frac{|D_i|}{|D|}{\sum }_{k=1}^K\frac{|D_{ik}|}{|D_i|}lo{g}_2\frac{|D_{ik}|}{|D_i|}$
3 计算信息增益g(D,A):$g(D,A)=H(D)?H(D|A)$

1.4 信息增益比

以信息增益来选择特征，会倾向于选择特征取值多的特征。可以使用信息增益比来解决这个问题。

特征A对数据集D的信息增益比定义为信息增益与训练数据集D关于特征A的值的熵的比：$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
$H_A(D)=?{\sum }_{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$，n为特征A的取值个数

2 决策树ID3

2.1 ID3树的构建

按照信息增益选择特征，形成的决策树称为ID3树。

输入：训练数据集D、特征集合A、阈值$?$
输出：决策树T
1 若D中所有实例属于同一类$C_k$，则T为单节点树，并将类$C_k$作为该节点的类标签，返回T；
2 若$A=?$，则T为单节点树，并选择D中实例数最大的类$C_k$作为该节点的类标签，返回T；
3 按照信息增益的算法，计算特征集合A中每个特征对D的信息增益，选择信息增益最大的特征$A_g$;
4 如果$A_g$的信息增益小于阈值$?$，则T为单节点树，并选择D中实例数最大的类$C_k$作为该节点的类标签，返回T；
5 否则，对$A_g$的每一个可能的值$a_i$，依$A_g=a_i$将D分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为节点标记，构建子节点。由节点及其子节点构成树T，返回T；
6 对第i个子节点，以数据集$D_i$作为训练集，以A-{$A_g$}为特征集，递归地调用步骤1-5，得到子树$T_i$，返回$T_i$。

2.2 决策树的剪枝

2.2.1 损失函数定义与计算

通过极小化 决策树整体的损失函数 来实现。
设树|T|的叶子节点个数为|T|，t是树T的叶子节点，该叶子节点有$N_t$个样本。其中k类的样本量为$N_{tk}$，k=1,2,3…K。
说明：一棵树T的叶子节点不一定只包含一类数据。例如在上述步骤2和5，就可能一个节点中实际存在多个类别的数据。只是因为再细分特征的信息增益太小了，不再划分。

$H_t(T)$为叶子节点t上的经验熵，$\alpha >=0$为参数，
损失函数：$C_{\alpha }(T)={\sum }_{i=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$
说明：树的损失函数对所有叶子节点的遍历。每一个叶子节点计算：当前叶子节点个数$N_t$，以及叶子节点的熵$H_t(T)$。它们的乘积表示当前叶子节点不确定的度量，也就是损失。对所有叶子节点不确定性的度量，就称为树的损失。
$\alpha |T|$是为了防止树过拟合。

${\sum }_{i=1}^{|T|}{N}_t{H}_t(T)$熵越小，说明叶子节点越来越多，这一部分会使得模型越来越复杂。$\alpha |T|$是为了对抗模型过渡复杂。

经验熵：$H_t(T)=?{\sum }_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$

$C(T)={\sum }_{i=1}^{|T|}{N}_t{H}_t(T)=?{\sum }_{i=1}^{|T|}{\sum }_{k=1}^K{N}_{tk}log\frac{N_{tk}}{N_t}$

那么 $C_{\alpha }(T)=C(T)+\alpha |T|$

2.2.2 剪枝过程

输入：决策树T，参数$\alpha$
输出：剪枝后的子树$T_{\alpha }$
1 计算每个节点的经验熵
2 递归地从树的叶子结点向上缩
设一组叶子节点回缩到其父节点之前与之后的孙淑函数分别为：$C_{\alpha }(T_B)$，$C_{\alpha }(T_A)$
如果：$C_{\alpha }(T_A)$<=$C_{\alpha }(T_B)$,则进行剪枝。
3 返回2，直至不能继续为止，得到损失最小的子树$T_a$。

以上过程将信息增益，换成信息增益比，那么得到的树就是C4.5。