ML学习笔记(四)

CART-GBDT基础

Posted by QIY on June 5, 2020

Machine Learning 的学习需稳扎稳打

1 CART

ID3中使用了信息增益选择特征,增益大优先选择。C4.5中,采用信息增益比选择特征,减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(比)相反。

  假设K个类别,第k个类别的概率为pk,概率分布的基尼系数表达式:

  如果是二分类问题,第一个样本输出概率为p,概率分布的基尼系数表达式为:

  对于样本D,个数为|D|,假设K个类别,第k个类别的数量为|Ck|,则样本D的基尼系数表达式:

  对于样本D,个数为|D|,根据特征A的某个值a,把D分成|D1|和|D2|,则在特征A的条件下,样本D的基尼系数表达式为:

  比较基尼系数和熵模型的表达式,二次运算比对数简单很多。尤其是二分类问题,更加简单。

    和熵模型的度量方式比,基尼系数对应的误差有多大呢?对于二类分类,基尼系数和熵之半的曲线如下:

基尼系数和熵之半的曲线非常接近,仅在45度角附近误差稍大。因此,基尼系数可以做为熵模型的一个近似替代。

1.思想: 一种采用基尼信息增益作为划分属性的二叉决策树。基尼指数越小,表示纯度越高。

2.回归:每个节点都有一个预测值,预测值等于属于该节点的所有样例的平均值,分支时,选择每个属性的每个阈值的最好分割点,衡量的标准是最小化均方差。

训练:对训练样本的第i(1<=i<=n)个属性,穷举每个分割点,找到均方差最小的分割点进行分割,该节点的值设为落到该节点的训练样本的平均值,直到不可分或者到一定高度或者属性使用完或者均方差不下降。

测试:对测试样本按照训练时的分割点进行下落,落到叶节点,叶节点的平均值即为预测值。

CART分类树算法每次仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。

2 GBDT

2.1 基本思想

GBDT 模型可以表示为决策树的加法模型:

其中,T(x;θm)表示决策树;θm 为决策树的参数; M为树的个数。

采用前向分布算法, 首先确定初始提升树 fo(x) = 0, 第 m 步的模型是:

通过经验风险极小化确定下一棵树的参数:(其实就是让残差尽可能的小找到最优划分点)

这里的 L() 是损失函数,回归算法选择的损失函数一般是均方差(最小二乘)或者绝对值误差;而在分类算法中一般的损失函数选择对数函数来表示。

GBDT 既可以做回归也可以做分类,下面先描述一下做回归的算法流程:

已知一个训练数据集 T = {(x1,y1),(x2,y2),…,(xn,yn)}, 如果将训练集分为不同的区域 R1,R2,…,Rn,然后可以确定每个区域输出的常识 c,c 的计算是将每个区域的 y 值相加再除以 y 的个数,其实就是求一个平均值。树可以表示为:

然后通过下图方式来确定具体分割点:

## 2.2 例子1

我将李航的统计学方法里面的例子粘出来,就知道提升树是如何计算的了:

 

 

以上就是 GBDT 选择分割点的过程, 如果特征有多个的话也是一样的道理,选择特征和特征值使得误差最小的点,作为分割点。所以其实 GBDT 也可以用作特征选择,通过GBDT 可以将重要的特征选择出来,当特征非常多的时候可以用来做降维。然后再融合类似逻辑回归这样的模型再进行训练。

2.3 例子2

多分类举例说明

   上面的理论阐述可能仍旧过于难懂,我们下面将拿Iris 数据集中的六个数据作为例子,来展示gbdt 多分类的过程。

样本编号 花萼长度(cm) 花萼宽度(cm) 花瓣长度(cm) 花瓣宽度 花的种类
1 5.1 3.5 1.4 0.2 山鸢尾
2 4.9 3.0 1.4 0.2 山鸢尾
3 7.0 3.2 4.7 1.4 杂色鸢尾
4 6.4 3.2 4.5 1.5 杂色鸢尾
5 6.3 3.3 6.0 2.5 维吉尼亚鸢尾
6 5.8 2.7 5.1 1.9 维吉尼亚鸢尾

这是一个有6个样本的三分类问题。我们需要根据这个花的花萼长度,花萼宽度,花瓣长度,花瓣宽度来判断这个花属于山鸢尾,杂色鸢尾,还是维吉尼亚鸢尾。具体应用到gbdt多分类算法上面。我们用一个三维向量来标志样本的label。[1,0,0] 表示样本属于山鸢尾,[0,1,0] 表示样本属于杂色鸢尾,[0,0,1] 表示属于维吉尼亚鸢尾。

gbdt 的多分类是针对每个类都独立训练一个 CART Tree。所以这里,我们将针对山鸢尾类别训练一个 CART Tree 1。杂色鸢尾训练一个 CART Tree 2 。维吉尼亚鸢尾训练一个CART Tree 3,这三个树相互独立。

我们以样本 1 为例。针对 CART Tree1 的训练样本是[5.1,3.5,1.4,0.2],label 是 1,最终输入到模型当中的为[5.1,3.5,1.4,0.2,1]。针对 CART Tree2 的训练样本也是[5.1,3.5,1.4,0.2],但是label 为 0,最终输入模型的为[5.1,3.5,1.4,0.2,0]针对 CART Tree 3的训练样本也是[5.1,3.5,1.4,0.2],label 也为0,最终输入模型当中的为[5.1,3.5,1.4,0.2,0]。

下面我们来看 CART Tree1 是如何生成的,其他树 CART Tree2 , CART Tree 3的生成方式是一样的。CART Tree的生成过程是从这四个特征中找一个特征做为CART Tree1 的节点。比如花萼长度做为节点。6个样本当中花萼长度 大于5.1 cm的就是 A类,小于等于 5.1 cm 的是B类。生成的过程其实非常简单,问题 1.是哪个特征最合适? 2.是这个特征的什么特征值作为切分点? 即使我们已经确定了花萼长度做为节点。花萼长度本身也有很多值。在这里我们的方式是遍历所有的可能性,找到一个最好的特征和它对应的最优特征值可以让当前式子的值最小。

我们以第一个特征的第一个特征值为例。R1 为所有样本中花萼长度小于 5.1 cm 的样本集合,R2 为所有样本当中花萼长度大于等于 5.1cm 的样本集合。所以 R1={2},R2={1,3,4,5,6}。

节点分裂示意图

y1 为 R1 所有样本的label 的均值 1/1=1。y2 为 R2 所有样本的label 的均值 (1+0+0+0+0)/5=0.2。

  下面便开始针对所有的样本计算这个式子的值。样本1 属于 R2 计算的值为 (1−0.2)2, 样本2 属于R1 计算的值为 (1−1)2, 样本 3,4,5,6同理都是 属于 R2的 所以值是 (0−0.2)2. 把这六个值加起来,便是 山鸢尾类型在特征1 的第一个特征值的损失值。这里算出来(1-0.2)\^2+ (1-1)\^2 + (0-0.2)\^2+(0-0.2)\^2+(0-0.2)\^2 +(0-0.2)\^2= 0.84。

  接着我们计算第一个特征的第二个特征值,计算方式同上,R1 为所有样本中 花萼长度小于 4.9 cm 的样本集合,R2 为所有样本当中 花萼长度大于等于 4.9 cm 的样本集合.所以 R1={},R1={1,2,3,4,5,6} y1 为 R1 所有样本的label 的均值 = 0。y2 为 R2 所有样本的label 的均值 (1+1+0+0+0+0)/6=0.3333。

第一个特征的第二个特侦值的节点分裂情况

我们需要针对所有的样本,样本1 属于 R2, 计算的值为 (1−0.333)2, 样本2 属于R2 ,计算的值为 (1−0.333)2, 样本 3,4,5,6同理都是 属于 R2的, 所以值是 (0−0.333)2. 把这六个值加起来山鸢尾类型在特征1 的第二个特征值的损失值。这里算出来 (1-0.333)\^2+ (1-0.333)\^2 + (0-0.333)\^2+(0-0.333)\^2+(0-0.333)\^2 +(0-0.333)\^2 = 2.244189. 这里的损失值大于 特征一的第一个特征值的损失值,所以我们不取这个特征的特征值。

所有情况说明

这样我们可以遍历所有特征的所有特征值,找到让这个式子最小的特征以及其对应的特征值,一共有24种情况,4个特征*每个特征有6个特征值。在这里我们算出来让这个式子最小的特征花萼长度,特征值为5.1 cm。这个时候损失函数最小为 0.8。

        于是我们的预测函数此时也可以得到:

\[f(x) = \sum_{\text{xϵ}R_{1}}^{}{}y_{1}*I(x\epsilon R_{1}) + \sum_{\text{xϵ}R_{2}}^{}{}y_{2}*I(x\epsilon R_{2})\]

 此处 R1 = {2},R2 = {1,3,4,5,6},y1 = 1,y2 = 0.2。训练完以后的最终式子为

\[f_{1}(x) = \sum_{\text{xϵ}R_{1}}^{}{}1*I(x\epsilon R_{1}) + \sum_{\text{xϵ}R_{2}}^{}{}0.2*I(x\epsilon R_{2})\]

借由这个式子,我们得到对样本属于类别1 的预测值 f1(x)=1+0.2∗5=2。同理我们可以得到对样本属于类别2,3的预测值f2(x),f3(x).样本属于类别1的概率 即为 

\[p_{1} = exp(f_{1}(x))/\sum_{k = 1}^{3}{}exp(f_{k}(x))\]

参考:

https://www.cnblogs.com/Ph-one/p/12751886.html

https://www.cnblogs.com/Ph-one/p/12793805.html

https://www.cnblogs.com/keye/p/10564914.html

https://www.cnblogs.com/ModifyRong/p/7744987.html