决策树

Decision Tree

机器学习最基本模型之一,DT

决策树可以看成路径的集合,路径的集合可以看成$if-then$规则的集合,内部结点表示特征或属性,叶结点表示一个类别(结论)。决策树的$if-then$规则集合是互斥且完备的(每一个实例都被包含在DT里)

决策树也可以对应于一个条件概率分布


数据集$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$

其中$x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$为输入实例(特征向量),$n$为特征个数,$y_i∈\{1,2,\cdots,K\}$为类别标记,

$i=1,2,\cdots,N$,$N$为样本容量。

目标就是学习到这个$if-then$规则集合,同时与训练数据矛盾较小(不欠拟合),又可以很好的预测位置数据(不过拟合)。DT学习算法是对训练数据分割的过程,也是特征空间划分的过程,也是决策树的构建过程。

DT算法一般三大步骤①特征选择②决策树生成③剪枝

剪枝的目的是防止过拟合(剪掉了树上过于细分的结点,使其退回到父节点或更高的结点)

DT是一种启发式算法,求得的是近似最优解

特征选择

特征用来划分特征空间,对数据进行实际分类。我们通过信息增益信息增益比来选择特征。

$P(X=x_i)=p_i\quad,P(X=x_i,Y=y_j)=p_{ij}\quad,i=1,2,\cdots,n;j=1,2,\cdots,m$

随机变量$X$的熵

熵表达了随机变量$X$的不确定性

由于只依赖$X$的分布而与$X$的取值没关系,则也可表示为$H(p)=-\sum_{i=1}^np_i\log p_i$

(对于$X=0,1$的熵表达式可以写为$H(p)=-p\log_2p-(1-p)\log_2(1-p)$)

给定$X$下随机变量$Y$的条件熵即为条件概率分布的熵$H(Y|X=x_i)$对$X$分布的数学期望(给每个$X_i$下的熵加了一个权值):

条件熵表达了在已知条件$X$下随机变量$Y$的不确定性

信息增益(Information Gain)

信息增益(Information Gain):表示如果得知特征$X$的信息而使得类$Y$的信息不确定性减少的程度

对于决策树,特征$A$对训练数据集$D$的信息增益$g(D,A)$为:

$H(D)$为数据集的经验熵,$H(D|A)$为条件经验熵($H(Y)-H(Y|X)$叫互信息,与决策树中的信息增益等价)

很明显可以理解,某特征的信息增益越大,该特征分类能力越强(因为IG越大,就代表我能够因此获得的确定性越多,也就是分类越好)

信息增益比(Information Gain Ratio)

信息增益比(Information Gain Ratio):

其中$n$为特征$A$的取值个数,$H_A(D)$为训练数据集$D$关于特征$A$的值的熵($\frac{1}{H_A(D)}$是一个惩罚系数将特征$A$的取值作为随机变量,求的是特征$A$的熵,具体见下面-理解)

信息增益存在偏向选择取值较多的特征的问题,于是信息增益比可以对这一问题进行校正。


对于实际训练集:如果由数据估得则为经验熵经验条件熵。那么设定$D$为数据集,$C_k$是类别为第$k$的样本集(真实标签),总共有$K$个类别;根据特征$A$可以将数据集划分为$n$个子集。$D_1,D_2,\cdots,D_n$(根据特征判断的标签),第$i$个子集即为$D_i$,$D_{ik}$表示$D_{i}$中同属于类$C_k$样本集的样本即$D_{ik}=D_i∩C_k$(也就是该类别中标签打对了的样本),则:

代入信息增益即可求得特征$A$对数据集$D$的信息增益

理解

这里的$H(D)$表达了数据集整体的不确定性,随机变量为$p(第i类的样本集)$;

条件熵中求的依然是数据集的熵,只是先让特征$A$进行了划分,而不是特征的熵。我们在求被$A$划分成的第$i$个$H(D_i)$的时候,$H(D_i)=-\sum_{i=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$。注意$H(D_i)$的随机变量被$A$划分之后的条件下(这里就是条件熵多的东西)第$i$个数据集中属于$k$类的概率。

条件熵$H(D|A)$即表达了在用特征$A$对$D$进行划分为$D_1,D_2,\cdots,D_n$,所有$D_i$的不确定性之和,即每个被$A$划分为$D_i$后的熵的和。然后再在求和的时候乘了一个权值——$A$取该第$i$个划分的概率(也就是期望,此即条件熵)。

不确定性即为我们对数据分类的预测的不确定性

$P(A取第i个取值)=\frac{|D_i|}{|D|}$

特征的熵$H_A(D)$:特征$A$的取值作为随机变量。通过数据集中被$A$打为第$i$个标签的数量与总数量的比即可求得特征$A$打第$i$个标签的概率,因此可以求得特征$A$的熵;见上面的IGR的惩罚系数

注意在计算每个子数据集$D_i$的经验熵时,随机变量为$D_i$中$D_{ik}$的概率,即$D_i$中属于$k$类(真实标签)的样本的概率。凡是求数据集的熵,随机变量必然都是该数据里某类(真实标签)的概率。

基尼指数(Gini)

对于IGR,当特征取值较少时$H_A(D)$的值较小,因此其倒数较大,因而信息增益比较大。因而偏向取值较少的特征。 于是引入基尼指数。

分类问题中,假设有$K$个类,样本点属于第$k$类的概率为$p_k$,则概率分布的基尼指数定义为:

对于二分类问题,则为$Gini(p)=2p(1-p)$

于是对于样本集合:

基尼指数$Gini(D)$表示集合$D$的不确定性

若$D$被特征划分$D_1,D_2$,则在特征$A$的集合下,集合$D$的基尼指数定义为:

式子中如$\frac{|D_i|}{|D|}$与上面一样,也就是划分为$D_1$的概率(特征$A$取值为第一个的概率)。

$Gini(D,A)$表示经$A=a$划分后集合$D$的不确定性。基尼指数越大,样本集合的不确定性也越大,与熵一致。

决策树的生成

以下ID3和C4.5都是生成多叉树,且只适用分类问题

ID3算法

在决策树各个结点上用信息增益来选择特征

设置一个阈值$\epsilon$,当$D_i$的IG小于该阈值的时候,表示该数据集可认为全是同一类别,无需再继续划分

只用于分类(离散数据)


举例:

有$K$个特征

①对$D$,求$g(D,A_1),g(D,A_2),\cdots,g(D,A_K)$

②于是可以求得使得IG:$g(D,A_k)$最大的特征$A_{g_1}$

③使用$A_g$将$D$划分为$D_1,D_2,\cdots,D_n$;(假设$A_g$有$n$个取值)

已经确定特征$A_g$,则特征集$A\to A-A_g$,特征数量变为$K-1$

④对每一个$D_i$,求$g(D_i,A_1),g(D_i,A_2),\cdots,g(D_i,A_{K-1})$

⑤求使得IG最大的$A_{g_2}$

此时$A_{g_2}<\epsilon$ ,则表示$D_i$可认为全是同一类别,无需再继续划分,该结点为叶子结点;

否则:再继续对$D_i$进行划分,上一个特征节点$A_g$为中间结点

再对每个划分的划分 ,求使得对应IG最大的$A_{g_k}$,判断继续划分or停止…

⑥依次类推$\cdots\cdots$


其中第④步就是返回到了第①步,$D换成了D_i$。(不过注意这里默认$D$并不是同一类,默认要继续划分)

具体略

C4.5算法

在决策树各个结点上用信息增益比来选择特征

设置一个阈值,当IGR小于该阈值的时候,算法停止

具体略

(连续属性值算法见后记-2)

以上两种算法容易过拟合,所以要剪枝

决策树的剪枝

决策树的剪枝是从全局角度减小决策树复杂度以防止过拟合

通过极小化DT整体的损失函数来实现

设:树$T$,叶结点个数$|T|$,$t$为某叶结点,该叶结点上有$N_t$个样本点,其中$k$类样本点有$N_{tk}$个,$k=1,2,\cdots,K$,$H_t(T)$为叶结点$t$上的经验熵,$\alpha≥0$为参数。

DT学习的损失函数:

$C(T)$就是计算出每个叶子结点的已分类数据集的熵之和,熵越小,则DT整体的不确定性程度越低,就代表分类越确定。此项越小,就代表模型与训练集的拟合程度越高。

$|T|$是叶子结点的个数,它就能表征DT模型的复杂度。此项越小,模型的复杂度就越低,就越不容易过拟合。

于是$\alpha≥0$就控制了两者之间的关系;如当$\alpha=0$,就代表模型只考虑拟合度不考虑复杂度,etc。该损失函数就相当于一个正则化的极大似然估计

含有这两者的损失函数就代表了拟合度和复杂度的一个平衡关系。可以看到决策树的生成是学习局部模型的,但决策树的剪枝是学习整体的模型。该

剪枝算法的目的,就是在给定$\alpha$下,求出使得损失函数$C_\alpha(T)$最小的子树$T’$

剪枝算法:(在用前面的算法生成完决策树之后)

①计算每个结点的经验熵

②递归地从树的叶结点$t_{|T|}$向上回缩直到根节点$T$。具体地,

对于该叶结点,如果将其回缩到其父节点之后:

——如果树整体的损失函数变小,则回缩该结点;

——否则,不回缩该结点。

③以此迭代

由于回缩计算差值的时候,树上只有局部有改变,所以在计算损失函数差值的时候只需要在局部进行

CART算法

CART: classification and regression tree 分类与回归树。CART既可以用于分类也可以用于回归。

生成

CART算法生成的是二叉决策树。(二叉决策树不是哈夫曼树形式,别搞错了)

思想:使用启发式算法,不断地寻找最优特征最优切割点$(j,s)$,对数据集进行二元切分

多值/多段回归特征很明显可以重复使用,一次无法将多值的某特征从数据集分离开(二值特征使用一次就不能再使用)(多段回归特征类似于分类中的多值特征,只不过预测的连续变量可以被划分为多个段)

  1. 分类:

    (使用基尼指数来衡量最优特征和最优切分点,基尼指数越小,不确定越低,每个样本分类越相同)

    通过对数据集$D_m$求$D_m$对每个特征$A_i$的基尼系数:即遍历$i,k$,求使得$Gini(D,A_i=k)$最小的最优特征和最优特征的切分点$(j,s)$组合(对应于遍历组合的标号$i,k$)。求出一个$D_m$的$(j,s)$就能将其划分两个子数据集。再对两个子数据集重复迭代上述过程,若结点中的样本个数小于预订阈值/样本集的基尼指数低于预定阈值(样本基本属于同一类)/没有更多特征,该结点就是叶子结点。

    具体算法略

  2. 回归:【重要,是Boosting中许多模型的基础】

    CART回归树生成是先确定结构(划分),再确定回归值(CART分类树就只有前面那个步骤),以此到Boosting(GDBT XGBoost)也是这个求法

    在回归问题中,模型输出一个连续变量。

    $D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,数据集被划分为了$M$个单元$R_1,R_2,\cdots,R_M$,在每个单元上有一个固定的输出值为$c_m$

    在回归中用平方误差来替代分类中的基尼指数:使用该结点数据集的每个样本中的【每个真实输出$y_i$与模型输出$f(x_i)$的均值$c_m$】的平方误差$\sum_{x_i}(y_i-c_m)^2$来找最优特征和最优切分点$(j,s)$。平方误差越小,样本分类越准确。(这个是回归与分类不同的关键)【平方误差即是这里CART使用的损失函数,也可以用其它损失函数,比如Boosting里的损失函数就都不一样】

    与分类中一样的思路:

    ①根据损失函数选定最优特征和切割第$j$个特征和其取值$s$为切分点,将父节点数据集$R$切分成了两个子节点(子数据集):

    $R_1(j,s)=\{x|x^{(j)}≤s\}$,$R_2(j,s)=\{x|x^{(j)}>s\}$

    以$R_1$为例,$\{x|x^{(j)}≤s\}$是指数据集中第$j$个特征的取值$≤s$的样本组成的新数据集,也就是一个划分,$R_2$同理。

    这里就确定了决策树的结构,于是:

    根据损失函数选取最优回归输出值

    这里损失函数为平方误差,对其就0导容易推得最优回归输出$c$就是划分上的均值

    设$c_m=ave(y_i|x∈R_m)=\frac{1}{N_m}\sum_{x_i∈R_m(j,s)}y_i$,表示被特征与切分组合$(j,s)$切分后数据集上模型输出$y$的均值,则这个$c_m$就是该节点的最优回归输出

    于是我们想要求得能够使得平方误差最小的特征与划分选取组合$(j,s)$以及其对应的最优输出(均值$\hat c_m$):

    于是再对两个被划分的子节点重复上面的步骤,直到满足停止条件

    这样生成的树叫最小二乘回归树

    理解:

    ①【选特征与切割】:求得$(j,s)$就告诉我们决策树怎么生成,选什么特征怎么切分(同分类),遍历选择$j,s$选最优划分。即【确定了决策树的结构】【这时候计算损失就是根据左\右划分(结点)的[所有点各自的真实输出]与切割点(一个回归输出值)之间的损失之和,来选取使共损失最小的特征与切割。】

    ②【决定回归输出】:每确定一个最优结点划分(即确定一组$(j,s)$),就能根据损失函数求出该结点内的最优输出:在各自每一个划分(结点)内选择一个最优的输出(即计算结点内的各点真实输出到选择的输出回归值的损失之和),使得该划分每个样本的损失最小。

    由于这里用的损失函数是平方误差,可以求得其最优值就是样本均值,对应特征$j$在划分数据集上的均值$\hat c_{1}$(特征值$≤s$的子结点)和$\hat c_2$(特征值$>s$的子节点),所以这个均值就是特征值$j$的回归输出。

    【注意①和②在求最优切割和最优均值中求的损失都是用的[同一个损失函数计算]!看这个公式说得很明白,理解透这个公式】

    对于使用一般损失函数的形式:

(连续属性值算法见后记-2)

(注意,如果每个训练样本是一维的,就不需要选切分特征(切分变量)了,回归和分类都是。如$x∈[0.5,10.5]$,在实数轴上,特征维度为1)

剪枝

思想:尝试所有的$\alpha$对树进行剪枝,找出最佳子树

过程:

  1. 迭代$\alpha$,剪枝,求每个$\alpha$下的最小子树

    ①对一棵树$T$,令$\alpha$从0从小到大开始进行一次迭代

    一个$\alpha$,对从下到上每一个结点$t$,以$t$为单结点(即$t$以下的树结点全部剪掉)的损失函数为:

    $C_\alpha(t)=C(t)+\alpha|t|=C(t)+\alpha$

    以$t$为根节点(即不剪枝)的树$T_t$的损失函数为:$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$

    当$C_\alpha(T_t)=C_\alpha(t)$的时候,联立以上两式得:$\alpha^o=\frac{C(t)-C(T_t)}{|T_t|-1}$,这个式子即表示剪枝与不剪枝损失函数相等的时候$\alpha$的值$\alpha^o$,我们把它用$g(t)$表示

    根据上述式子推可得,$\alpha$越大,那么不剪枝的整体损失函数就会大于剪枝的整体损失函数(因为$C_\alpha(T_t)$的$\alpha$项后面跟着$|T_t|≥1$),那么就该剪(因为目的是最小化损失函数),反之就不该剪。于是$g(t)$就可以作为一个用来判断对于一个结点$t$,给定$\alpha$下该不该剪枝的阈值

    于是对于本次迭代的$\alpha$下,计算树$T$中每个结点$t$的剪枝判断阈值$g(t)$值:

    于是从下往上对树中的每个结点$t$阈值判断:如果$\alpha≥g(t),剪;\alpha<g(t),不剪$

    ②继续增大$\alpha$,选择下一个$\alpha$重复上述过程

    ③迭代结束,得到一个子树序列:$\{T_0,T_1,\cdots,T_n\}$,每个子树对应于不同的$\alpha$值,每个子树都是对应$\alpha$值的最小子树

  2. 对获取的最小子树序列进行选择最优$\alpha$和最优子树

    利用独立验证数据集测试各子树的平方误差或基尼指数,求得最优解

比较ID3/C4.5和CART来理解

  1. 划分

    在ID3和C4.5中,通过IG或IGR求出最优特征之后,直接将特征的所有可能取值作为切分点,那么就成了多分类。那么ID3/C4.5生成的是一个多叉树

    而CART要求出最优特征最优切分点的组合,以将该特征下的取值切分成二类。CART生成一个二叉树。

    举例:特征为年龄,取值为青年、中年、老年,那么ID3/C4.5就可能分成$O\{青年\}\{中年\}\{老年\}$,CART就可能分为$O\{青年\}\{中年、老年\}$ ($O$代表父节点,$\{\}代表子节点集合$)

  2. 特征变量的使用

    特征变量的使用中,多分的分类变量ID3和C4.5层级之间只单次使用,CART可多次重复使用

    举例:继续上面的例子,在ID3/C4.5中,该特征(年龄)被一次划分为三个子数据集$\{青年\}\{中年\}\{老年\}$,于是该特征被删除特征集,不再使用。继续迭代就在其它特征中来选择最优特征

    而在CART中,两个子节点为$O\{青年\}\{中年、老年\}$,对于这两个子节点进行迭代的时候,由于特征(年龄)并没有将所有年龄特征分开,则还可以再使用用过的特征(年龄)来继续二分类!(假设在右节点使用年龄的基尼系数相比其他特征和划分最低的话,那么下次就再使用年龄特征,只有二分类所以直接划分为$\{中年\}\{老年\}$)不过再次使用该特征并不一定是接着使用,这需要根据基尼指数最小/平方误差最小计算

    也因此CART一般比ID3/C4.5深

  3. 输入与输出

    ID3和C4.5只能做分类,CART可以做回归和分类

    ID3只能作用离散值属性,C4.5和CART可以作用连续值属性

    注意区别见后记-3

  4. 计算代价

    CART计算更快,消耗资源更少,因为CART不需要进行熵中的log运算(基尼指数和熵效果差不多,但没用log,这就是用基尼指数的原因)

  5. 缺失值

    ID3对缺失值敏感,而C4.5和CART对缺失值可以进行多种方式的处理 O

  6. 剪枝方法不同

    C4.5是通过枝剪来修正树的准确性,而CART是直接利用全部数据发现所有树的结构进行对比

  7. C4.5是ID3的优化 IGR替代了IG

    因为信息增益的缺点是倾向于选择取值较多的屬性,在有些情况下这类属性可能不会提供太多有价值的信息。

  8. 样本量

    只从样本量考虑,小样本建议考虑c4.5、大样本建议考虑cart。而cart本身是一种大样本的统计方法,小样本处理下泛化误差较大

后记

  1. 缺失值处理

    ①抛弃缺失值

    ②补充缺失值

    ③概率化缺失值(C4.5使用此方式, 对缺失值的样本赋予该属性所有属性值的概率分布)

    ④缺失值单独分支

  2. 属性为连续值的划分问题

    离散化技术

    C4.5用于连续值属性的算法:(于是就成了二叉树了)

    采用离散化技术(如二分法)进行处理。将属性值从小到大排序,然后选择中间值作为分割点,数值比它小的点被划分到左子树,数值不小于它的点被分到又子树,对所有可能的分割法,计算分割的信息增益率,选择信息增益率IGR最大的属性值进行分割。

    CART的连续值属性的算法:只是把IGR换成了基尼指数或平方误差,其它一样

  3. 【注意】回归预测连续值属性的区别

    回归预测输出(预测)的是一个连续变量的值,比如要求输出概率(又比如说要预测房价)

    属性为连续值指的是输入的属性是连续的,即取值无限,如输入的$x是实数$,那就得用离散化方法,C4.5采用了二分,即把$x是实数\to \{x<A_i\},\{x≥A_i\}$两个结点。(或者如输入的值是房价)

    属性就是特征,属性的值即特征的取值

  4. CART回归树的例可以见Boosting的GDBT后记

  5. 寻找最优切分和特征一般都是贪心算法,只考虑当前结点下的最优特征和最优分割

  6. 决策树以及基于Boosting的算法的优点

    ①天然对缺失值和噪音有很好的鲁棒性

    ②天然可以很好的处理各种类型的特征

    ③天然对离群值有很好的鲁棒性

    ④(对Boosting DT)数据规模影响不大,因为我们对弱分类器的要求不高

  7. 但也有缺点,就在于假设无噪音的情况下,性能不如SVM,LR等,但如果数据集有噪音的话,这个弱势就不能么明显了。而且,可以用Boosting嘛,一个DT不给力,多个DT一起干,效果就更强