网站 会员系统 织梦,网页设计与制作简历,网站广告图片设计教程,洛阳霞光网络建站关注数学#xff0c;关注AI#xff0c;关注我们公众号ID#xff1a;Math-AI阅读目录1. 决策树的模型2. 决策树的基本知识3. ID3、C4.5CART4. Random Forest5. GBDT6. 参考内容今天我们来谈一谈机器学习算法中的各种树形算法#xff0c;包括ID3、C4.5、CART以及基于集成… 关注数学关注AI关注我们公众号IDMath-AI阅读目录1. 决策树的模型2. 决策树的基本知识3. ID3、C4.5CART4. Random Forest5. GBDT6. 参考内容 今天我们来谈一谈机器学习算法中的各种树形算法包括ID3、C4.5、CART以及基于集成思想的树模型Random Forest和GBDT。本文对各类树形算法的基本思想进行了简单的介绍重点谈一谈被称为是算法中的“战斗机”机器学习中的“屠龙刀”的GBDT算法。1决策树的模型 决策树是一种基本的分类与回归方法它可以被认为是一种if-then规则的集合。决策树由节点和有向边组成内部节点代表了特征属性外部节点(叶子节点)代表了类别。 下图为决策树的一个图例 决策树根据一步步地属性分类可以将整个特征空间进行划分从而区别出不同的分类样本如下图所示 根据上图其实我们不难可以想到满足样本划分的决策树有无数种什么样的决策树才算是一颗好的决策树呢 性能良好的决策树的选择标准是一个与训练数据矛盾较小的决策树同时具有很好的泛化能力。言外之意就是说好的决策树不仅对训练样本有着很好的分类效果对于测试集也有着较低的误差率。2决策树的基本知识 一个完整的决策树学习算法包含有三大步骤分别为 1) 特征的选择 2) 决策树的生成 3) 决策树的剪枝。 在介绍决策树学习算法之前我们先简单谈几个基本的概念 1) 熵(entropy) 在信息论和概率统计中熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量其概率分布为P(Xxi)pi, i1,2, ... , n则随机变量X的熵定义为H(X)- ∑ pi * logpi, i1,2, ... , n 熵只依赖X的分布和X的取值没有关系熵是用来度量不确定性当熵越大概率说Xxi的不确定性越大反之越小在机器学期中分类中说熵越大即这个类别的不确定性更大反之越小当随机变量的取值为两个时熵随概率的变化曲线如下图 当p0或p1时H(p)0,随机变量完全没有不确定性 当p0.5时H(p)1,此时随机变量的不确定性最大。 条件熵(conditional entropy)表示在一直随机变量X的条件下随机变量Y的不确定性度量。 设随机变量(X, Y)其联合概率分布为 P(X, Y) pij(i1,2, ... , n; j1,2, ... , m)随机变量X给定的条件下随机变量Y的条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望H(Y|X)∑ pi*H(Y|Xxi)这里piP(Xxi), i1,2, ... , n. 2) 信息增益(information gain) 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。 特征A对训练数据集D的信息增益g(D, A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差即g(D, A)H(D)-H(D|A) 信息增益大的特征具有更强的分类能力。 3) 信息增益比(information gain ratio) 信息增益比gR(D, A)定义为其信息增益g(D, A)与训练数据集D关于特征A的值的熵HA(D)之比即gR(D, A)g(D, A)/HA(D)其中HA(D)-∑|Di|/|D|*log2|Di|/|D|, n是特征A取值的个数。 4) 基尼指数(gini index) 分类问题中假设有K个类样本属于第k类的概率为pk则概率分布的基尼指数定义为Gini(p)∑pk(1-pk)1-∑pk2 对于二分类问题若样本点属于第1个类的概率是p则概率分布的基尼指数为Gini(p)2p(1-p) 对于给定的样本集合D其基尼指数为Gini(D)1-∑(|Ck|/|D|)2 这里Ck是D中属于第k类的样本子集k是类的个数。 如果样本集合D根据特征A是否取到某一可能值a被分割成D1和D2两部分则在特征A的条件下集合D的基尼指数定义为Gini(D,A)|D1|/|D|*Gini(D1)|D2|/|D|*Gini(D2) 基尼指数Gini(D)表示集合D的不确定性基尼指数越大样本集合的不确定性也就越大这一点与熵相似。3ID3、C4.5CART 其实不同的决策树学习算法只是它们选择特征的依据不同决策树的生成过程都是一样的(根据当前环境对特征进行贪婪的选择)。 ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征每一次都选择使得信息增益最大的特征进行分裂递归地构建决策树。 ID3算法以信息增益作为划分训练数据集的特征有一个致命的缺点。选择取值比较多的特征往往会具有较大的信息增益所以ID3偏向于选择取值较多的特征。 针对ID3算法的不足C4.5算法根据信息增益比来选择特征对这一问题进行了校正。 CART指的是分类回归树它既可以用来分类又可以被用来进行回归。CART用作回归树时用平方误差最小化作为选择特征的准则用作分类树时采用基尼指数最小化原则进行特征选择递归地生成二叉树。 决策树的剪枝我们知道决策树在生成的过程中采用了贪婪的方法来选择特征从而达到对训练数据进行更好地拟合(其实从极端角度来看决策树对训练集的拟合可以达到零误差)。而决策树的剪枝是为了简化模型的复杂度防止决策树的过拟合问题。具体的决策树剪枝策略可以参见李航的《统计学习方法》。4Random Forest 随机森林是一种集成学习决策树的分类模型它可以利用集成的思想(投票选择的策略)来提升单颗决策树的分类性能(通俗来讲就是“三个臭皮匠顶一个诸葛亮”)。 集集成学习和决策树于一身随机森林算法具有众多的优点其中最为重要的就是在随机森林算法中每棵树都尽最大程度的生长并且没有剪枝过程。 随机森林引入了两个随机性——随机选择样本(bootstrap sample)和随机选择特征进行训练。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入使得随机森林不容易陷入过拟合并且具有很好得抗噪能力(比如对缺省值不敏感)。5GBDT 迭代决策树GBDT(Gradient Boosting Decision Tree)也被称为是MART(Multiple Additive Regression Tree))或者是GBRT(Gradient Boosting Regression Tree)也是一种基于集成思想的决策树模型但是它和Random Forest有着本质上的区别。不得不提的是GBDT是目前竞赛中最为常用的一种机器学习算法因为它不仅可以适用于多种场景更难能可贵的是GBDT有着出众的准确率。这也是为什么很多人称GBDT为机器学习领域的“屠龙刀”。 这么牛叉的算法到底是怎么做到的呢说到这里就不得不说一下GBDT中的“GB”(Gradient Boosting)。Gradient Boosting的原理相当的复杂但是看不懂它也不妨碍我们对GBDT的理解和认识有关Gradient Boosting的详细解释请见wiki百科。 在这里引用另外一个网友的解释来说明一下对GBDT中的Gradient Boosting的理解 以下一段内容引自《GBDT(MART) 迭代决策树入门教程 | 简介》。 “Boosting迭代即通过迭代多棵树来共同决策。这怎么实现呢难道是每棵树独立训练一遍比如A这个人第一棵树认为是10岁第二棵树认为是0岁第三棵树认为是20岁我们就取平均值10岁做最终结论当然不是且不说这是投票方法并不是GBDT只要训练集不变独立训练三次的三棵树必定完全相同这样做完全没有意义。之前说过GBDT是把所有树的结论累加起来做最终结论的所以可以想到每棵树的结论并不是年龄本身而是年龄的一个累加量。GBDT的核心就在于每一棵树学的是之前所有树结论和的残差这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁但第一棵树的预测年龄是12岁差了6岁即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习如果第二棵树真的能把A分到6岁的叶子节点那累加两棵树的结论就是A的真实年龄如果第二棵树的结论是5岁则A仍然存在1岁的残差第三棵树里A的年龄就变成1岁继续学。这就是Gradient Boosting在GBDT中的意义。” 其实从这里我们可以看出GBDT与Random Forest的本质区别GBDT不仅仅是简单地运用集成思想而且它是基于对残差的学习的。我们在这里利用一个GBDT的经典实例进行解释。 假设我们现在有一个训练集训练集只有4个人A,B,C,D他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练会得到如下图1所示结果图1 现在我们使用GBDT来做这件事由于数据太少我们限定叶子节点做多有两个即每棵树都只有一个分枝并且限定只学两棵树。我们会得到如下图2所示结果图2 在第一棵树分枝和图1一样由于A,B年龄较为相近C,D年龄较为相近他们被分为两拨每拨用平均年龄作为预测值。此时计算残差(残差的意思就是A的预测值 A的残差 A的实际值)所以A的残差就是16-151(注意A的预测值是指前面所有树累加的和这里前面只有一棵树所以直接是15如果还有树则需要都累加起来作为A的预测值)。进而得到A,B,C,D的残差分别为-1,1,-1,1。然后我们拿残差替代A,B,C,D的原值到第二棵树去学习如果我们的预测值和它们的残差相等则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的第二棵树只有两个值1和-1直接分成两个节点。此时所有人的残差都是0即每个人都得到了真实的预测值。 最后GBDT的预测结果为 A: 14岁高一学生购物较少经常问学长问题预测年龄A 15 – 1 14 B: 16岁高三学生购物较少经常被学弟问问题预测年龄B 15 1 16 C: 24岁应届毕业生购物较多经常问师兄问题预测年龄C 25 – 1 24 D: 26岁工作两年员工购物较多经常被师弟问问题预测年龄D 25 1 26。 那么哪里体现了Gradient呢其实回到第一棵树结束时想一想无论此时的cost function是什么是均方差还是均差只要它以误差作为衡量标准残差向量(-1, 1, -1, 1)都是它的全局最优方向这就是Gradient。 注图1和图2 最终效果相同为何还需要GBDT呢答案是过拟合。过拟合是指为了让训练集精度更高学到了很多“仅在训练集上成立的规律”导致换一个数据集当前规律就不适用了。只要允许一棵树的叶子节点足够多训练集总是能训练到100%准确率的。在训练精度和实际精度(或测试精度)之间后者才是我们想要真正得到的。我们发现图1为了达到100%精度使用了3个feature(上网时长、时段、网购金额)其中分枝“上网时长1.1h” 很显然已经过拟合了这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时但用上网时间是不是1.1小时来判断所有人的年龄很显然是有悖常识的相对来说图2的boosting虽然用了两棵树 但其实只用了2个feature就搞定了后一个feature是问答比例显然图2的依据更靠谱。 可见GBDT同随机森林一样不容易陷入过拟合而且能够得到很高的精度。 补充实例(2015-10-7) 在此引用李航博士《统计学习方法》中提升树的实例来进一步阐述GBDT的详细流程。 一直认为李航博士讲的机器学习更加贴近算法的本质我们先来看一下他是如何对GBDT进行定义的(在《统计学习方法中》GBDT又被称为是提升树boosting tree)。 提升方法实际采用了加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提升方法称为提升树对分类问题决策树是二叉分类树而对于回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型其中表示决策树表示决策树的参数M为树的个数。 针对不同问题的提升树(GBDT)其主要区别在于使用的损失函数不同包括用平方误差损失函数的回归问题用指数损失函数的分类问题以及用一般损失函数的一般决策问题。 提升树的流程 下面我们通过一个实例来透彻地来看一下提升树(GDBT)到底是怎样一步一步解决问题的。 6参考内容 [1] 李航《统计学习方法》 [2] GBDT(MART) 迭代决策树入门教程 | 简介
