机器学习中的算法:决策树模型组合之机器学习中的算法:决策树模型组合之GBDT
前言
决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示(容易将得到的决策
树做成图片展示出来)等。但是同时,单决策树又有一些不好的地方,比如说容易over-fitting,虽然有一些方法,如剪枝可以
减少这种情况,但是还是不够的。
模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以
上)棵树,这样可以大大的减少单决策树带来的毛病,有点类似于三个臭皮匠等于一个诸葛亮的做法,虽然这几百棵决策树中
的每一棵都很简单(相对于C4.5这种单决策树来说),但是他们组合起来确是很强大。
在最近几年的paper上,如iccv这种重量级的会议,iccv 09年的里面有不少的文章都是与Boosting与随机森林相关的。模型组
合+决策树相关的算法有两种比较基本的形式 - 随机森林与GBDT(Gradient Boost Decision Tree),其他的比较新的模型组合
+决策树的算法都是来自这两种算法的延伸。在看本文之前,建议先看看机器学习与数学(3)与其中引用的论文,本文中的
GBDT主要基于此,而随机森林相对比较独立。
基础内容
有两个概念比较重要:首先是information gain,其次是决策树。推荐Andrew Moore的Decision Trees Tutorial,与Information
Gain Tutorial,以及Moore的Data Mining Tutorial系列。决策树可分为分类树与回归树,一个用于分类,一个用于回归。对于
决策树的分类功能,简单的讲是通过每一个特征(属性),对样本进行粗略的分类,可能只是分成2类。但是运用的特征多
了,分类的结果就细了,所以最终会有较正确的分类效果。
决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,例如图1所示的决策树,
其属性的值都是连续的实数:首先先根据特征x,将特征x的值小于3和大于等于3的分为2类,再根据特征y对样本再次细分,
如此循环,这样使得每一个叶子节点都是在空间中的一个不相交的区域。分割后的空间如图2所示。在进行决策的时候对于新
来的样本,从根结点开始判断,根据输入样本每一维feature的值,一步一步往下,最后使得样本落入N个区域中的一个(假设
有N个叶子节点)。
GBDT(Gradient Boost Decision Tree)
GBDT是一个应用很广泛的算法,可以用来做分类、回归。在很多的数据上都有不错的效果。GBDT这个算法还有一些其他的
名字,比如说MART(Multiple Additive Regression Tree),GBRT(Gradient Boost Regression Tree),Tree Net等,其实它们都
是一个东西(参考自wikipedia – Gradient Boosting),发明者是Friedman
Gradient Boost其实是一个框架,里面可以套入很多不同的算法,可以参考一下机器学习与数学
(3)中的讲解。Boost是"提升"的意思,一般Boosting算法都是一个迭代的过程,每一次新的训练都是为了改进上一次的结果。
原始的Boost算法是在算法开始的时候,为每一个样本赋上一个权重值,初始的时候,大家都是一样重要的。在每一步训练中
得到的模型,会使得数据点的估计有对有错,我们就在每一步结束后,增加分错的点的权重,减少分对的点的权重,这样使得
某些点如果老是被分错,那么就会被“严重关注”,也就被赋上一个很高的权重。然后等进行了N次迭代(由用户指定),将会
评论0