XGBoost浅入浅出

XGBoost风靡Kaggle、天池、DataCastle、Kesci等国内外数据竞赛平台,是比赛夺冠的必备大杀器。我在之前参加过的一些比赛中,着实领略了其威力,也因此取得不少好成绩。如果把数据竞赛比作金庸笔下的武林,那么XGBoost可谓屠龙刀,号令天下,莫敢不从!倚天不出,谁与争锋?

貌似有点扯远了…..因为最近有人说我很文艺,所以允许我开篇装一下逼

XGBoost工具很多人都会用,但却很少有人知道其原理,在我写这篇文章之前,我也是一知半解,前阵子假期就抽空看了一下XGBoost的论文,了解了更多的细节,当然我不敢保证自己的理解完全正确,也有一些细节还没搞明白,特别是XGBoost工具的工程实现方面的内容,读的时候大多略过了。

这篇文章还在初稿中,本来没打算写的,但是前几天在知乎上看到一个相关的问题“机器学习算法中GBDT和XGBOOST的区别有哪些?”,就手痒回答了一下。这篇文章就先记录一下该问题下我的回答,以及过去我总结的对XGBoost的使用经验。等之后有空了,系统地总结GBDT以及XGBoost。

xgboost相比传统gbdt有何不同?xgboost为什么快?xgboost如何支持并行?

看了陈天奇大神的文章和slides,略抒己见,没有面面俱到,不恰当的地方欢迎讨论:

  • 传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。
  • 传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。
  • xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。
  • Shrinkage(缩减),相当于学习速率(xgboost中的eta)。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把eta设置得小一点,然后迭代次数设置得大一点。(补充:传统GBDT的实现也有学习速率)
  • 列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。

  • 对缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。

  • xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的?注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

  • 可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。

=============

回复 @肖岩在评论里的问题,因为有些公式放正文比较好。评论里讨论的问题的大意是 “xgboost代价函数里加入正则项,是否优于cart的剪枝”。其实陈天奇大神的slides里面也是有提到的,我当一下搬运工。
决策树的学习过程就是为了找出最优的决策树,然而从函数空间里所有的决策树中找出最优的决策树是NP-C问题,所以常采用启发式(Heuristic)的方法,如CART里面的优化GINI指数、剪枝、控制树的深度。这些启发式方法的背后往往隐含了一个目标函数,这也是大部分人经常忽视掉的。xgboost的目标函数如下:

其中正则项控制着模型的复杂度,包括了叶子节点数目T和leaf score的L2模的平方:

那这个跟剪枝有什么关系呢???
跳过一系列推导,我们直接来看xgboost中树节点分裂时所采用的公式:

这个公式形式上跟ID3算法(采用entropy计算增益) 、CART算法(采用gini指数计算增益) 是一致的,都是用分裂后的某种值 减去 分裂前的某种值,从而得到增益。为了限制树的生长,我们可以加入阈值,当增益大于阈值时才让节点分裂,上式中的gamma即阈值,它是正则项里叶子节点数T的系数,所以xgboost在优化目标函数的同时相当于做了预剪枝。另外,上式中还有一个系数lambda,是正则项里leaf score的L2模平方的系数,对leaf score做了平滑,也起到了防止过拟合的作用,这个是传统GBDT里不具备的特性。

xgboost使用经验总结

  • 多类别分类时,类别需要从0开始编码
  • Watchlist不会影响模型训练。
  • 类别特征必须编码,因为xgboost把特征默认都当成数值型的
  • 调参:Notes on Parameter Tuning 以及 Complete Guide to Parameter Tuning in XGBoost (with codes in Python)
  • 训练的时候,为了结果可复现,记得设置随机数种子。
  • XGBoost的特征重要性是如何得到的?某个特征的重要性(feature score),等于它被选中为树节点分裂特征的次数的和,比如特征A在第一次迭代中(即第一棵树)被选中了1次去分裂树节点,在第二次迭代被选中2次…..那么最终特征A的feature score就是 1+2+….

参考文献

朴素贝叶斯理论推导与三种常见模型

朴素贝叶斯(Naive Bayes)是一种简单的分类算法,它的经典应用案例为人所熟知:文本分类(如垃圾邮件过滤)。很多教材都从这些案例出发,本文就不重复这些内容了,而把重点放在理论推导(其实很浅显,别被“理论”吓到),三种常用模型及其编码实现(Python)。

如果你对理论推导过程不感兴趣,可以直接逃到三种常用模型及编码实现部分,但我建议你还是看看理论基础部分。

另外,本文的所有代码都可以在这里获取

KMeans聚类算法思想与可视化

1.聚类分析

1.0 概念

聚类分析简称聚类(clustering),是一个把数据集划分成子集的过程,每一个子集是一个簇(cluster),使得簇中的样本彼此相似,但与其他簇中的样本不相似。

聚类分析不需要事先知道样本的类别,甚至不用知道类别个数,因此它是一种无监督的学习算法,一般用于数据探索,比如群组发现和离群点检测,还可以作为其他算法的预处理步骤。

下面的动图展示的是一个聚类过程,感受一下:

这里写图片描述

当Python装饰器遇上递归函数

不久前我在参加某比赛时,写了一些处理数据的代码,当时并没有采用SQL,而是用Python去实现。为了计算监测处理数据所耗费的时间,当时写了这样code:

1
2
3
4
5
import time
t_start = time.time()
func()
t_end = time.time()
print "run time %.5f" %(t_end-t_start)

流形学习-高维数据的降维与可视化

1.流形学习的概念

流形学习方法(Manifold Learning),简称流形学习,自2000年在著名的科学杂志《Science》被首次提出以来,已成为信息科学领域的研究热点。在理论和应用上,流形学习方法都具有重要的研究意义。

假设数据是均匀采样于一个高维欧氏空间中的低维流形,流形学习就是从高维采样数据中恢复低维流形结构,即找到高维空间中的低维流形,并求出相应的嵌入映射,以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质,找到产生数据的内在规律。

深度学习框架Keras的使用-进阶

上一篇文章总结了Keras的基本使用方法,相信用过的同学都会觉得不可思议,太简洁了。十多天前,我在github上发现这个框架的时候,关注Keras的人还比较少,这两天无论是github还是微薄,都看到越来越多的人关注和使用Keras。所以这篇文章就简单地再介绍一下Keras的使用,方便各位入门。

主要包括以下三个内容:

  • 训练CNN并保存训练好的模型。
  • 将CNN用于特征提取,用提取出来的特征训练SVM。
  • 可视化CNN卷积层后的特征图。

仍然以Mnist为例,代码中用的Mnist数据到这里下载
http://pan.baidu.com/s/1qCdS6,本文的代码在我的github上:dive_into _keras

易用的深度学习框架Keras简介

之前我一直在使用Theano,前面五篇Deeplearning相关的文章也是学习Theano的一些笔记,当时已经觉得Theano用起来略显麻烦,有时想实现一个新的结构,就要花很多时间去编程,所以想过将代码模块化,方便重复使用,但因为实在太忙没有时间去做。最近发现了一个叫做Keras的框架,跟我的想法不谋而合,用起来特别简单,适合快速开发。

1. Keras简介

Keras是基于Theano的一个深度学习框架,它的设计参考了Torch,用Python语言编写,是一个高度模块化的神经网络库,支持GPU和CPU。使用文档在这:http://keras.io/,这个框架貌似是刚刚火起来的,使用上的问题可以到github提issue:https://github.com/fchollet/keras 

下面简单介绍一下怎么使用Keras,以Mnist数据库为例,编写一个CNN网络结构,你将会发现特别简单。

libsvm和liblinear的使用总结

0.安装方法

unix系统下的安装方法:到官网下载源包(目前最新版本为libsvm-3.20、liblinear-1.96),解压后,打开终端进入makefile所在的目录,键入make即可。

以下为一些基本的使用命令,ubuntu系统下。

1.生成符合要求的数据格式,以图像数据为例

(1). 从图像库得到csv文件 (csv文件里每一行存储一张图:label,feat1,feat2,…..),在终端下键入:

python gen_datafile.py 

Kaggle比赛-Otto Group Product Classification

简介

Otto Group Product Classification Challenge是Kaggle上目前正在进行的一个比赛,目前已1000+队伍参赛,由Otto公司赞助1W美刀,数据也是来自于该公司的产品,提供了train.csv、test.csv、samplesubmission.csv三份数据。train.csv里包含了6万多个样本,每个样本有一个id,93个特征值feat_1~feat_93,以及类别target,一共9种类别:class_1~class_9。test.csv里有14万多测试样本,只有id以及93个特征,参赛者的任务是对这些样本分类。

机器学习算法中如何选取超参数:学习速率、正则项系数、minibatch size

本文是《Neural networks and deep learning》概览 中第三章的一部分,讲机器学习算法中,如何选取初始的超参数的值。(本文会不断补充)


学习速率(learning rate,η)

运用梯度下降算法进行优化时,权重的更新规则中,在梯度项前会乘以一个系数,这个系数就叫学习速率η。下面讨论在训练时选取η的策略。

  • 固定的学习速率。如果学习速率太小,则会使收敛过慢,如果学习速率太大,则会导致代价函数振荡,如下图所示。就下图来说,一个比较好的策略是先将学习速率设置为0.25,然后在训练到第20个Epoch时,学习速率改为0.025。

正则化方法:L1和L2 regularization、数据集扩增、dropout

本文是《Neural networks and deep learning》概览 中第三章的一部分,讲机器学习/深度学习算法中常用的正则化方法。(本文会不断补充)


正则化方法:防止过拟合,提高泛化能力

在训练数据不够多时,或者overtraining时,常常会导致overfitting(过拟合)。其直观的表现如下图所示,随着训练过程的进行,模型复杂度增加,在training data上的error渐渐减小,但是在验证集上的error却反而渐渐增大——因为训练出来的网络过拟合了训练集,对训练集外的数据却不work。

交叉熵代价函数

本文是《Neural networks and deep learning》概览 中第三章的一部分,讲machine learning算法中用得很多的交叉熵代价函数。

1.从方差代价函数说起

代价函数经常用方差代价函数(即采用均方误差MSE),比如对于一个神经元(单输入单输出,sigmoid函数),定义其代价函数为:

其中y是我们期望的输出,a为神经元的实际输出【 a=σ(z), where z=wx+b 】。

在训练神经网络过程中,我们通过梯度下降算法来更新w和b,因此需要计算代价函数对w和b的导数:

SQL

SQL简介

  • SQL指结构化查询语言
  • SQL是一种ANSI的标准计算机语言,存在不同的版本,但不同版本都支持一些共同的关键词。

OpenCV人脸检测(C++代码)

这篇文章简单总结一下人脸检测的代码实现,基于OpenCV,C++版本。之所以强调C++版本是因为OpenCV有很多其他语言的接口,之前我也写过人脸检测的Python实现《Python-OpenCV人脸检测(代码)》,这篇文章则讲C++实现,其实大同小异,C++相比于Python实现代码写起来会繁琐一点,这也是语言本身决定的吧。

为了保持代码风格一致,C++实现与之前的Python实现一样,都将人脸检测、眼睛检测、框出人脸、框出眼睛、截取保存人脸各个功能封装为函数,方便移植。


1、OpenCV中人脸检测采用的算法

在安装OpenCV的路径中(window系统),我们可以发现”…\opencv\sources\data”目录下有如下三个文件夹:

这正是OpenCV采用的算法。haarcascades文件下存放的是采用Haar特征的级联分类器(Cascade Classfier),hogcascades下存放采用HOG特征(梯度方向直方图)的级联分类器,lbpcascades下存放的是采用LBP特征的级联分类器。关于图像的Haar、LBP、HOG、SIFT等特征我将写另外的博文进行总结,这里就不详细展开。图中三个文件夹下存放了很多xml文件,这些是预先训练好的特征,用于构造分类器的,有人脸检测的、眼睛检测的、smile检测的、行人检测的等等。

在这篇文章中,仅以haarcascas下的”haarcascade_frontalface_alt.xml”和”haarcascade_eye.xml”作为例子。主要代码在下文讲解,更多代码也可以到我的github获取:here

2、代码实现

这个demo以下图为输入:

  • 图像预处理

    • 转化为灰度图
    • 直方图均衡化
1
2
3
4
Mat img = imread("obama.jpg");
Mat img_gray;
cvtColor(img,img_gray,COLOR_BGR2GRAY );
equalizeHist(img_gray,img_gray);

Python对象

1、Python对象

Python使用对象模型来存储数据,构造任何类型的值都是一个对象。所有的对象都有三个特性:

  • 身份,可通过内建函数id()查看,这个值即该对象的内存地址。
  • 类型,可通过内建函数type()查看。
  • 值,对象表示的数据项。
1
2
3
4
5
6
7
8
>>> p = 12
>>> id(p)
31108092
>>> type(p)
<type 'int'>
>>> p
12
>>>

2、标准类型

整型Integer,长整型Long integer,浮点型float,复数型complex number,布尔型bool,字符串string,列表list,元组tuple,字典dictionary。

3、其他内建类型

  • type类型对象

    type类型本身就是一个对象,它的类型为‘type’。

1
2
3
4
>>> type(1)
<type 'int'>
>>> type(type(1))
<type 'type'>
  • None——Python的Null对象

    Python有一个特殊的类型,称作Null对象或者NoneType,它只有一个值:None,None的布尔值为False。

  • 文件

  • 集合
  • 函数/方法
  • 模块

《Python核心编程》数字类型

1、数字类型简介

  • Python中数字类型包括:整型、长整型、布尔型、双精度浮点型、十进制浮点型、复数。这些数字类型都是不可变类型,也就是说,改变了数字的值会生成新的对象。
  • 在Python中删除数字对象,可以用语句:del aInt,aLong,aFloat,aComplex

《Python核心编程》笔记 基础

春节终于over了,回归充实的学习研究生活。打开久违的CSDN博客,看到官方推送的 『博客Markdown编辑器上线啦』,让我顿时有了写作的欲望,真是程序员的福利。之前阅读各种文章书籍,都是用MarkDownPad做的笔记,喜欢以及习惯于MarkDown简洁的语法。

总之各种方便。为了试试效果,将以前阅读《Python核心编程》的手记整理发上来,也当温习一遍。

第三章 Python基础

1、语句和语法

  • 注释

    Python中注释用符号“#”,也可以用三引号:’’’ 注释内容 ‘’’

  • 继续

    过长的语句,可以用反斜杠\,将一行分解为几行:

1
2
if a==1 and \
b==0 :
  • Python缩进风格

    Pyhton使用缩进来分隔代码组,缩进可以为空格、制表符Tab(另:推荐使用4个空格来缩进,并且尽量不要用tab键,因为不同平台tab键的代表的空白宽度不一样。)

  • 多个语句写在同一行上

    把多个语句写在同一行上是不推荐的,因为可读性会大大降低。如果非要这么做,也是允许的。

    1
    import sys; x  = 'foo'; sys.stdout.write(x)
  • 模块

    通过import导入

《Python核心编程 》笔记-快速入门

春节终于over了,回归充实的学习研究生活。打开久违的CSDN博客,看到官方推送的 『博客Markdown编辑器上线啦』,让我顿时有了写作的欲望,真是程序员的福利。之前阅读各种文章书籍,都是用MarkDownPad做的笔记,喜欢以及习惯于MarkDown简洁的语法。

总之各种方便。为了试试效果,将以前阅读《Python核心编程》的手记整理发上来,也当温习一遍。

第二章 快速入门

  • print语句中使用字符串格式操作符,实现字符替换功能。
1
print "%s is %d" %("one",1)
%s%d%f分别用字符串、整型、浮点类型数据来替换。
  • print语句重定向

    1
    2
    3
    logfile = open('/tmp/mylog.txt','a')
    print &gt;&gt; logfile,'something....'
    logfile.close()

    符号>>是用来重定向的,上面的代码将输出添加到日志文件mylog.txt中。

  • raw_input内建函数,读取键盘输入,返回值类型是字符串。

    1
    s = raw_input('some tips:')