My Blog List

Monday, June 20, 2011

LIBSVM回归详细操作步骤(附图)--更新至20090806

LIBSVM回归详细操作步骤(附图)--更新至20090806

(2009-04-13 22:24:38)
P.S. 多谢“三月未央”网友的提醒,本文中的一些错误得到改正,原先的第五幅图中路径有错(估计那晚太困了,稀里糊涂的就写出来了,实为害人啊LIBSVM回归详细操作步骤(附图)--更新至20090806)!再次感谢你们的关注,希望在交流中一起进步!修改和增加部分已经用红色字体区分了,还有就是第五章图,估计以前做错的人不少,不要怪我!LIBSVM回归详细操作步骤(附图)--更新至20090806LIBSVM回归详细操作步骤(附图)--更新至20090806LIBSVM回归详细操作步骤(附图)--更新至20090806 先前的一些步骤可以参照我《科研-支持向量机(SVM)预测》中的几篇,包括文件格式等。

晚上一网友发来消息说还是不清楚怎么做,老出错,现在有点闲功夫,截了一些图按部就班的做了,希望能看懂。

其实只要修改一个文件(gridregression.py)的路径就可以了,其他网上说的两个文件(grid.py和easy.py)的路径可以不做修改,因为回归根本没有用到。修改的地方是绿色的两行路径,写成实际路径就可以了。网上下载下来的一般都是r"...svm-..."所以要改。修改后如下图。

LIBSVM回归详细操作步骤(附图)--更新至20090806

改完之后,首先把你的数据集包括data2和test2(这是原始的)放到C:\libsvm-2.88\windows下。
LIBSVM回归详细操作步骤(附图)--更新至20090806

LIBSVM做回归预测--终于弄通(转载)

LIBSVM做回归预测--终于弄通(原创)

(2009-04-07 23:31:59)
看了网上很多帖子和博客,自己琢磨了很久到现在才弄明白怎么用libsvm来做预测。因为网上的帖子一般都是转来转去的,所以第一个人感觉这样写详细了,之后的人不管懂不懂照搬不误,这就苦了我们笨的人啦。不过我研究了一天,终于有点眉目,写点体会,应该会比较详细吧,至少是过来人碰到的问题。

p.s.这里暂且不讨论分类问题,其实分类比预测简单,下载下来的libsvm-2.88早已有easy.py可以直接拿来做,所以简单,一步到位,之后如果有空就写写!

用libsvm做回归的人有的疑惑大致有这些:
1,怎么把数据整理成规定格式,我以前的帖子写了,只要用一个带有宏的excel就能搞定,话不多说。
2,有人会说svm就打几条命令就能得出结果

svm-train -s 3 -t 2 -c 1024.0 -g 0.0009765625 -p 0.0009765625 data.txt
svm-predict test.txt data.txt.model out.txt
),干嘛还要下载python和gnuplot呢,其实了解svm理论的知道最核心的问题就是参数的选择,你不可能每次都很狗屎的猜到很好的参数,做出很好的预测,所以只能用这两个软件来寻参。

Sunday, June 12, 2011

机器学习中的数学(3)-模型组合(Model Combining)之Boosting与Gradient Boosting

版权声明:
    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com

前言:
    本来上一章的结尾提到,准备写写线性分类的问题,文章都已经写得差不多了,但是突然听说最近Team准备做一套分布式的分类器,可能会使用Random Forest来做,下了几篇论文看了看,简单的random forest还比较容易弄懂,复杂一点的还会与boosting等算法结合(参见iccv09),对于boosting也不甚了解,所以临时抱佛脚的看了看。说起boosting,强哥之前实现过一套Gradient Boosting Decision Tree(GBDT)算法,正好参考一下。
    最近看的一些论文中发现了模型组合的好处,比如GBDT或者rf,都是将简单的模型组合起来,效果比单个更复杂的模型好。组合的方式很多,随机化(比如random forest),Boosting(比如GBDT)都是其中典型的方法,今天主要谈谈Gradient Boosting方法(这个与传统的Boosting还有一些不同)的一些数学基础,有了这个数学基础,上面的应用可以看Freidman的Gradient Boosting Machine。
    本文要求读者学过基本的大学数学,另外对分类、回归等基本的机器学习概念了解。
    本文主要参考资料是prml与Gradient Boosting Machine。

机器学习中的算法(2)-支持向量机(SVM)基础

版权声明:
    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com

前言:
    又有很长的一段时间没有更新博客了,距离上次更新已经有两个月的时间了。其中一个很大的原因是,不知道写什么好-_-,最近一段时间看了看关于SVM(Support Vector Machine)的文章,觉得SVM是一个非常有趣,而且自成一派的方向,所以今天准备写一篇关于关于SVM的文章。
    关于SVM的论文、书籍都非常的多,引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”。SVM对于大部分的普通人来说,要完全理解其中的数学是非常困难的,所以要让这些普通人理解,得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些数学,对学习其他的内容也是大有裨益的。我就是属于绝大多数的普通人,为了看明白SVM,看了不少的资料,这里把我的心得分享分享。
    其实现在能够找到的,关于SVM的中文资料已经不少了,不过个人觉得,每个人的理解都不太一样,所以还是决定写一写,一些雷同的地方肯定是不可避免的,不过还是希望能够写出一点与别人不一样的地方吧。另外本文准备不谈太多的数学(因为很多文章都谈过了),尽量简单地给出结论,就像题目一样-机器学习中的算法(之前叫做机器学习中的数学),所以本系列的内容将更偏重应用一些。如果想看更详细的数学解释,可以看看参考文献中的资料。

机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用

版权声明:
    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com
前言:
    上一次写了关于PCA与LDA的文章,PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。特征值和奇异值在大部分人的印象中,往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面,也很少讲任何跟特征值与奇异值有关的应用背景。奇异值分解是一个有着很明显的物理意义的一种方法,它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示,这些小矩阵描述的是矩阵的重要的特性。就像是描述一个人一样,给别人描述说这个人长得浓眉大眼,方脸,络腮胡,而且带个黑框的眼镜,这样寥寥的几个特征,就让别人脑海里面就有一个较为清楚的认识,实际上,人脸上的特征是有着无数种的,之所以能这么描述,是因为人天生就有着非常好的抽取重要特征的能力,让机器学会抽取重要的特征,SVD是一个重要的方法。
    在机器学习领域,有相当多的应用与奇异值都可以扯上关系,比如做feature reduction的PCA,做数据压缩(以图像压缩为代表)的算法,还有做搜索引擎语义层次检索的LSI(Latent Semantic Indexing)
    另外在这里抱怨一下,之前在百度里面搜索过SVD,出来的结果都是俄罗斯的一种狙击枪(AK47同时代的),是因为穿越火线这个游戏里面有一把狙击枪叫做SVD,而在Google上面搜索的时候,出来的都是奇异值分解(英文资料为主)。想玩玩战争游戏,玩玩COD不是非常好吗,玩山寨的CS有神马意思啊。国内的网页中的话语权也被这些没有太多营养的帖子所占据。真心希望国内的气氛能够更浓一点,搞游戏的人真正是喜欢制作游戏,搞Data Mining的人是真正喜欢挖数据的,都不是仅仅为了混口饭吃,这样谈超越别人才有意义,中文文章中,能踏踏实实谈谈技术的太少了,改变这个状况,从我自己做起吧。
    前面说了这么多,本文主要关注奇异值的一些特性,另外还会稍稍提及奇异值的计算,不过本文不准备在如何计算奇异值上展开太多。另外,本文里面有部分不算太深的线性代数的知识,如果完全忘记了线性代数,看本文可能会有些困难。

机器学习中的数学(4)-线性判别分析(LDA), 主成分分析(PCA)

版权声明:
    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com
前言:
    第二篇的文章中谈到,和部门老大一宁出去outing的时候,他给了我相当多的机器学习的建议,里面涉及到很多的算法的意义、学习方法等等。一宁上次给我提到,如果学习分类算法,最好从线性的入手,线性分类器最简单的就是LDA,它可以看做是简化版的SVM,如果想理解SVM这种分类器,那理解LDA就是很有必要的了。
   谈到LDA,就不得不谈谈PCA,PCA是一个和LDA非常相关的算法,从推导、求解、到算法最终的结果,都有着相当的相似。
   本次的内容主要是以推导数学公式为主,都是从算法的物理意义出发,然后一步一步最终推导到最终的式子,LDA和PCA最终的表现都是解一个矩阵特征值的问题,但是理解了如何推导,才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础,比如说特征值、特征向量的概念,空间投影,点乘等的一些基本知识等。除此之外的其他公式、我都尽量讲得更简单清楚。

机器学习中的数学(2)-线性回归,偏差、方差权衡

版权声明:
    本文由LeftNotEasy所有,发布于http://leftnoteasy.cnblogs.com。如果转载,请注明出处,在未经作者同意下将本文用于商业用途,将追究其法律责任。如果有问题,请联系作者 wheeleast@gmail.com
前言:
    距离上次发文章,也快有半个月的时间了,这半个月的时间里又在学习机器学习的道路上摸索着前进,积累了一点心得,以后会慢慢的写写这些心得。写文章是促进自己对知识认识的一个好方法,看书的时候往往不是非常细,所以有些公式、知识点什么的就一带而过,里面的一些具体意义就不容易理解了。而写文章,特别是写科普性的文章,需要对里面的具体意义弄明白,甚至还要能举出更生动的例子,这是一个挑战。为了写文章,往往需要把之前自己认为看明白的内容重新理解一下。
    机器学习可不是一个完全的技术性的东西,之前和部门老大在outing的时候一直在聊这个问题,机器学习绝对不是一个一个孤立的算法堆砌起来的,想要像看《算法导论》这样看机器学习是个不可取的方法,机器学习里面有几个东西一直贯穿全书,比如说数据的分布、最大似然(以及求极值的几个方法,不过这个比较数学了),偏差、方差的权衡,还有特征选择,模型选择,混合模型等等知识,这些知识像砖头、水泥一样构成了机器学习里面的一个个的算法。想要真正学好这些算法,一定要静下心来将这些基础知识弄清楚,才能够真正理解、实现好各种机器学习算法。
    今天的主题是线性回归,也会提一下偏差、方差的均衡这个主题。

机器学习中的数学(1)-回归(regression)、梯度下降(gradient descent)

版权声明:
   本文由LeftNotEasy所有,发布于http://leftnoteasy.cnblogs.com。如果转载,请注明出处,在未经作者同意下将本文用于商业用途,将追究其法律责任。
前言:
   上次写过一篇关于贝叶斯概率论的数学,最近时间比较紧,coding的任务比较重,不过还是抽空看了一些机器学习的书和视频,其中很推荐两个:一个是stanford的machine learning公开课,在verycd可下载,可惜没有翻译。不过还是可以看。另外一个是prml-pattern recognition and machine learning, Bishop的一部反响不错的书,而且是2008年的,算是比较新的一本书了。
   前几天还准备写一个分布式计算的系列,只写了个开头,又换到写这个系列了。以后看哪边的心得更多,就写哪一个系列吧。最近干的事情比较杂,有跟机器学习相关的,有跟数学相关的,也有跟分布式相关的。
   这个系列主要想能够用数学去描述机器学习,想要学好机器学习,首先得去理解其中的数学意义,不一定要到能够轻松自如的推导中间的公式,不过至少得认识这些式子吧,不然看一些相关的论文可就看不懂了,这个系列主要将会着重于去机器学习的数学描述这个部分,将会覆盖但不一定局限于回归、聚类、分类等算法。

Logistic Regression:从另外一个角度理解

Although the linear regression model is simple and used frequently it's not adequate for some purposes. For example, imagine the response variable y to be a probability that takes on values between 0 and 1. A linear model has no bounds on what values the response variable can take, and hence y can take on arbitrary large or small values. However, it is desirable to bound the response to values between 0 and 1. For this we would need something more powerful than linear regression.

Another problem with the linear regression model is the assumption that the response y has a constant variance. This can not be the case if y follows for example a binomial distribution (y ~ Bin(p,n)). If y also is normalized so that it takes values between 0 and 1, hence y = Bin(p,n)/n, then the variance would then be Var(y) = p*(1-p), which takes on values between 0 and 0.25. To then make an assumption that y would have a constant variance is not feasible.

In situations like this, when our response variable follows a binomial distribution, we need to use general linear regression. A special case of general linear regression is logistic regression, which assumes that the response variable follows the logit-function shown in Figure 4.

Figure 4 The logit function

Note that it's only defined for values between 0 and 1. The logit function goes from minus infinity to plus infinity. The logit function has the nice property that logit(p) = -logit(1-p) and its inverse is defined for values from minus infinity to plus infinity, and it only takes on values between 0 and 1.

However, to get a better understanding for what the logit-function is we will now introduce the notation of odds. The odds of an event that occurs with probability P is defined as

odds = P / (1-P).

Figure 5 shows how the odds-function looks like. As we can see, the odds for an event is not bounded and goes from 0 to infinity when the probability for that event goes from 0 to 1.

However, it's not always very intuitive to think about odds. Even worse, odds are quite unappealing to work with due to its asymmetry. When we work with probability we have that if the probability for yes is p, then the probability for no is 1-p. However, for odds, there exists no such nice relationship.

To take an example: If a Boolean variable is true with probability 0.9 and false with probability 0.1, we have that the odds for the variable to be true is 0.9/0.1 = 9 while the odds for being false is 0.1/0.9 = 1/9 = 0.1111… . This is a quite unappealing relationship. However, if we take the logarithm of the odds, when we would have log(9) for true and log(1/9) = -log(9) for false.

Hence, we have a very nice symmetry for log(odds(p)). This function is called the logit-function.

logit(p) = log(odds(p)) = log(p/(1-p))

As we can see, it is true in general that logit(1-p)=-logit(p).

logit(1-p) = log((1-p)/p) = – log(p/(1-p)) = -logit(p)

Figure 5 The odds function

The odds function maps probabilities (between 0 and 1) to values between 0 and infinity.

The logit-function has all the properties we wanted but did not have when we previously tried to use linear regression for a problem where the response variable followed a binomial distribution. If we instead use the logit-function we will have p bounded to values between 0 and 1 and we will still have a linear expression for our input variable x

logit(p) = a + beta * x.

If we would like to rewrite this expression to get a function for the probability p it would look like

 

转:决策树模型组合之随机森林与GBDT

前言:

决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示(容易将得到的决策树做成图片展示出来)等。但是同时, 单决策树又有一些不好的地方,比如说容易over-fitting,虽然有一些方法,如剪枝可以减少这种情况,但是还是不够的。

模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大 大的减少单决策树带来的毛病,有点类似于三个臭皮匠等于一个诸葛亮的做法,虽然这几百棵决策树中的每一棵都很简单(相对于C4.5这种单决策树来说),但 是他们组合起来确是很强大。

在最近几年的paper上,如iccv这种重量级的会议,iccv 09年 的里面有不少的文章都是与Boosting与随机森林相关的。模型组合+决策树相关的算法有两种比较基本的形式 – 随机森林与GBDT((Gradient Boost Decision Tree),其他的比较新的模型组合+决策树的算法都是来自这两种算法的延伸。本文主要侧重于GBDT,对于随机森林只是大概提提,因为它相对比较简单。

在看本文之前,建议先看看机器学习与数学(3)与其中引用的论文,本文中的GBDT主要基于此,而随机森林相对比较独立。

基础内容:

这里只是准备简单谈谈基础的内容,主要参考一下别人的文章,对于随机森林与GBDT,有两个地方比较重要,首先是information gain,其次是决策树。这里特别推荐Andrew Moore大牛的Decision Trees Tutorial,与Information Gain Tutorial。Moore的Data Mining Tutorial系列非常赞,看懂了上面说的两个内容之后的文章才能继续读下去。

决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,比如说下面的决策树:

image

就是将空间划分成下面的样子:

image

这样使得每一个叶子节点都是在空间中的一个不相交的区域,在进行决策的时候,会根据输入样本每一维feature的值,一步一步往下,最后使得样本落入N个区域中的一个(假设有N个叶子节点)

随机森林(Random Forest):

随机森林是一个最近比较火的算法,它有很多的优点:

  • 在数据集上表现良好
  • 在当前的很多数据集上,相对其他算法有着很大的优势
  • 它能够处理很高维度(feature很多)的数据,并且不用做特征选择
  • 在训练完后,它能够给出哪些feature比较重要
  • 在创建随机森林的时候,对generlization error使用的是无偏估计
  • 训练速度快
  • 在训练过程中,能够检测到feature间的互相影响
  • 容易做成并行化方法
  • 实现比较简单

随机森林顾名思义,是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输 入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本 为那一类。

在建立每一棵决策树的过程中,有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程,random forest对输入的数据要进行行、列的采样。对于行采样,采用有放回的方式,也就是在采样得到的样本集合中,可能有重复的样本。假设输入样本为N个,那 么采样的样本也为N个。这样使得在训练的时候,每一棵树的输入样本都不是全部的样本,使得相对不容易出现over-fitting。然后进行列采样,从M 个feature中,选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树,这样决策树的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一 个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝,但是这里不这样干,由于之前的两个随机采样的过程保证了随机性,所以就算不剪枝,也不会出现over-fitting。

按这种算法得到的随机森林中的每一棵都是很弱的,但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法:每一棵决策树就是一个精通于某一个窄领域 的专家(因为我们从M个feature中选择m让每一棵决策树进行学习),这样在随机森林中就有了很多个精通不同领域的专家,对一个新的问题(新的输入数 据),可以用不同的角度去看待它,最终由各个专家,投票得到结果。

随机森林的过程请参考Mahout的random forest 。这个页面上写的比较清楚了,其中可能不明白的就是Information Gain,可以看看之前推荐过的Moore的页面。

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次迭代(由用户指定),将会得到N个简单的分类器(basic learner),然后我们将它们组合起来(比如说可以对它们进行加权、或者让它们进行投票等),得到一个最终的模型。

而Gradient Boost与传统的Boost的区别是,每一次的计算是为了减少上一次的残差(residual),而为了消除残差,我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说,在Gradient Boost中,每个新的模型的简历是为了使得之前模型的残差往梯度方向减少,与传统Boost对正确、错误的样本进行加权有着很大的区别。

在分类问题中,有一个很重要的内容叫做Multi-Class Logistic,也就是多分类的Logistic问题,它适用于那些类别数>2的问题,并且在分类结果中,样本x不是一定只属于某一个类可以得到 样本x分别属于多个类的概率(也可以说样本x的估计y符合某一个几何分布),这实际上是属于Generalized Linear Model中讨论的内容,这里就先不谈了,以后有机会再用一个专门的章节去做吧。这里就用一个结论:如果一个分类问题符合几何分布,那么就可以用Logistic变换来进行之后的运算

假设对于一个样本x,它可能属于K个分类,其估计值分别为F1(x)…FK(x),Logistic变换如下,logistic变换是一个平滑且将数据规范化(使得向量的长度为1)的过程,结果为属于类别k的概率pk(x),

image

对于Logistic变换后的结果,损失函数为:

image

其中,yk为输入的样本数据的估计值,当一个样本x属于类别k时,yk = 1,否则yk = 0。

将Logistic变换的式子带入损失函数,并且对其求导,可以得到损失函数的梯度

image

上面说的比较抽象,下面举个例子:

假设输入数据x可能属于5个分类(分别为1,2,3,4,5),训练数据中,x属于类别3,则y = (0, 0, 1, 0, 0),假设模型估计得到的F(x) = (0, 0.3, 0.6, 0, 0),则经过Logistic变换后的数据p(x) = (0.16,0.21,0.29,0.16,0.16),y – p得到梯度g:(-0.16, -0.21, 0.71, -0.16, -0.16)。观察这里可以得到一个比较有意思的结论:

假设gk为样本当某一维(某一个分类)上的梯度:

gk>0时,越大表示其在这一维上的概率p(x)越应该提高,比如说上面的第三维的概率为0.29,就应该提高,属于应该往“正确的方向”前进

越小表示这个估计越“准确”

gk<0时,越小,负得越多表示在这一维上的概率应该降低,比如说第二维0.21就应该得到降低。属于应该朝着“错误的反方向”前进

越大,负得越少表示这个估计越“不错误 ”

总的来说,对于一个样本,最理想的梯度是越接近0的梯度。所以,我们要能够让函数的估计值能够使得梯度往反方向移动(>0的维度上,往负方向移动,<0的维度上,往正方向移动)最终使得梯度尽量=0),并且该算法在会严重关注那些梯度比较大的样本,跟Boost的意思类似

得到梯度之后,就是如何让梯度减少了。这里是用的一个迭代+决策树的方法,当初始化的时候,随便给出一个估计函数F(x)(可以让F(x)是一个随机的值,也可以让F(x)=0),然后之后每迭代一步就根据当前每一个样本的梯度的情况,建立一棵决策树。就让函数往梯度的反方向前进,最终使得迭代N步后,梯度越小。

这里建立的决策树和普通的决策树不太一样,首先,这个决策树是一个叶子节点数J固定的,当生成了J个节点后,就不再生成新的节点了。

算法的流程如下:(参考自treeBoost论文)

image

0. 表示给定一个初始值

1. 表示建立M棵决策树(迭代M次)

2. 表示对函数估计值F(x)进行Logistic变换

3. 表示对于K个分类进行下面的操作(其实这个for循环也可以理解为向量的操作,每一个样本点xi都对应了K种可能的分类yi,所以yi, F(xi), p(xi)都是一个K维的向量,这样或许容易理解一点)

4. 表示求得残差减少的梯度方向

5. 表示根据每一个样本点x,与其残差减少的梯度方向,得到一棵由J个叶子节点组成的决策树

6. 为当决策树建立完成后,通过这个公式,可以得到每一个叶子节点的增益(这个增益在预测的时候用的)

每个增益的组成其实也是一个K维的向量,表示如果在决策树预测的过程中,如果某一个样本点掉入了这个叶子节点,则其对应的K个分类的值是多少。比如 说,GBDT得到了三棵决策树,一个样本点在预测的时候,也会掉入3个叶子节点上,其增益分别为(假设为3分类的问题):

(0.5, 0.8, 0.1),  (0.2, 0.6, 0.3),  (0.4, 0.3, 0.3),那么这样最终得到的分类为第二个,因为选择分类2的决策树是最多的。

7. 的意思为,将当前得到的决策树与之前的那些决策树合并起来,作为新的一个模型(跟6中所举的例子差不多)

GBDT的算法大概就讲到这里了,希望能够弥补一下上一篇文章中没有说清楚的部分:)

实现:

看明白了算法,就需要去实现一下,或者看看别人实现的代码,这里推荐一下wikipedia中的gradient boosting页面,下面就有一些开源软件中的一些实现,比如说下面这个:http://elf-project.sourceforge.net/

参考资料:

除了文章中的引用的内容(已经给出了链接)外,主要还是参考Friedman大牛的文章:Greedy function approximation : A Gradient Boosting Machine

本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com

Google Blogger使用技巧

Blogger是Google提供的免费博客服务,提供中文界面,是一个很成熟的中文博客发布平台。

  Blogger一个突出的特点就是简洁但功能强大,没有多余而花哨的功能,必要的功能一个都不差。Bloger自由性最大的地方在于其模板可以自定义,也就是说你可以修改模板里的任何内容,包括Google的广告,这给那些懂Html和CSS的Blogger提供了很大的自由度。Blogger默认把用户的网志发布到免费提供的Blogspot.com主机上。可惜的是Blogspot.com从中国是无法访问。好在Blogger.com提供了一种很独特的服务,可以将博客的静态页面通过FTP发布到用户选择的服务器上。

  通过FTP发布到其他主机

  用户在Blogger.com上的默认Blog地址显然无法从国内访问,但是如果你有一个虚拟主机空间,或者其他支持FTP的空间,那么Blogger.com可以将这个地址上的日志文件全部发布到你的虚拟主机空间上去。

  具体的方法是:登陆你的Blogger帐号,进入控制面板,更改设置,在"发布"选项卡中点击FTP的超级链接,然后录入FTP服务器地址,FTP用户名和密码。点保存设置后,就可以发布了,这时Blogger.com会将你的整个站发布到你指定的主机上。

  至于这个FTP服务器,我推荐一个国内GFans提供的免费Blogger Spaces空间,支持FTP发布,最重要的是支持域名绑定,其服务器在广州,速度很快,希望大家不要滥用其服务。

  通过电子邮件发布日志

  在Blogger中写日志麻烦?告诉你一个技巧,你可以不登录Blogger网站,只要发送一封电子邮件就可以发表文章了。

  具体的方法是:登陆你的Blogger帐号,进入控制面板,更改设置,在"电子邮件"中,在Mail-to-Blogger地址中可以自定义一个邮件地址,发送到此地址的邮件会自动张贴,BlogSend地址是另外一个电子邮件地址,只要一发布文章,系统会将其邮寄文章到此地址。

  这里再介绍一个小技巧,就是在更新Blogger的同时也更新MSN Space。因为MSN Space也是支持邮件发布的,因此将Blogger发布后发送邮件的BlogSend地址修改为MSN Space的发布邮件地址,这样在Blogger上发布一篇文章后,系统就会自动将文章内容发送到Msn Spaces里,这样就同时更新了两个博客。

  有一点值得注意的是,Blogger默认的编码是UTF-8编码,因此发送邮件的时候要将邮件编码设置为UTF-8的格式,建议登陆GMail发送邮件。一来GMail默认就是UTF-8格式的,编码全兼容,二来GMail支持自动保存功能,不怕电脑死机后丢失文章,三来GMail还可以自动备份发出去的文章,以免文章丢失。

  使用第三方软件发布文章

  Zoundry是一个第三方的日志发布软件,可以做到不用登陆Blogger即可发布日志,使用它来编辑和发布,速度和效率都非常理想。

  添加Google Adsense广告

  Google Blogger用户可以很快捷方便地申请加入Google Adsense广告服务。Google本身也推荐博客们使用Blogger的广告来为自己和Google赚钱。

  Google工具栏的应用

  Google工具栏有一个按钮是"发送到Blogger",可以快速将当前网页发送到自己的Blogger空间上。

  Google Picasa的应用

  Picasa是Google的图像管理软件,在Picasa中点图片,再点"Blog This",可以将选定图片发送到自己的Blogger空间上。

  Blogger的申请地址是: http://www.blogger.com

Gradient Boosted Decision Tree(GBDT)

Gradient Boosted Decision Trees are an additive classification or regression model consisting of an ensemble of trees, fitted to current residuals, gradients of the loss function, in a forward step-wise manner. In the traditional boosting framework, the weak learners are generally shallow decision trees consisting of a few leaf nodes. GBDT ensembles are found to work well when there are hundreds of such decision trees. Gradient Boosted Decision Trees was introduced by Jerome Friedman in 1999. Salford Systems' Treenet and the GBM package in R are implementations of GBDT.

In machine learning, understanding how one's model succeeds or fails for a particular dataset or sample is important to building better models. For Naive Bayes classifiers, a list of frequency counts and a confusion matrix is generally informative enough to understand what went wrong. For traditional decision trees, understanding how a sample traverses the tree is highly informative about which features caused a sample to be classified a particular way.

For GBDT models, since there are hundreds of decisions trees, we can not realistically expect a researcher to be able to look at all the decision trees and the individual path the sample traverses each tree. Our proposal is to work on visualizations of ensembles of GBDT for error analysis. Of particular focus will be generating a single representative tree from the ensemble and visualizations of the paths that a particular sample traverses and what features impacted the final results the most.


References
  • Mulvaney R, Phatak DS. A Method to Merge Ensembles of Bagged or Boosted Forced-Split Decision Trees. IEEE Trans on PAMI. 2003
  • Barlow, T., Neville, P. Case study: visualization for decision tree analysis in data mining. IEEE Symposium on Information Visualization, 2001.
  • Soon Tee Teoh, Kwan-Liu Ma, PaintingClass: interactive construction, visualization and exploration of decision trees. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

From:http://vis.berkeley.edu/courses/cs294-10-fa07/wiki/index.php/FP-Jerry_Ye_and_Jimmy_Chen