Spark-MLlib学习日记7：初探梯度提升决策树

发表于 | 分类于 | 阅读数

前言

嗯。。怎么说呢，本来见识到随机森林的强大之后，觉得分类算法里面，另一个集成算法——梯度提升决策树(GBDT)看不看都那样了，看各类书和spark官网对他的介绍也是一笔带过，所以抱着轻视的态度，顺手训练了下模型，结果识别率居然高达99.763593%！！！用的还是官方给的默认参数。。。而且训练速度贼快。我随机森林要跑15分钟，这个几分钟就好了。所以决定单独写一篇日记，来深入地去学习一下这个算法。

比较可惜地是，该算法目前还不支持多分类，不过找了下资料貌似挺多大神在一点点改进这个算法了，比如陈天奇的xgboost。总而言之，不能以一份数据来衡量机器学习算法的好坏，应该根据数据特点，选择最适合这个数据的算法，这也是我这个系列学习希望达成的目标之一。

什么是梯度提升决策树

梯度提升决策树简称 GBDT ，是 Gradient Boosting Decision Tree 的缩写，也有文章称之为 MART（Multiple Additive Regression Tree），是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。注意这里的决策树算法用的并不是随机森林提到的分类树，而是回归树，而且梯度提升树目前不支持多分类问题。

梯度提升树依次迭代训练一系列的决策树。在一次迭代中，算法使用现有的集成来对每个训练实例的类别进行预测，然后将预测结果与真实的标签值进行比较。通过重新标记，来赋予预测结果不好的实例更高的权重。所以，在下次迭代中，决策树会对先前的错误进行修正。

对实例标签进行重新标记的机制由损失函数来指定。每次迭代过程中，梯度迭代树在训练数据上进一步减少损失函数的值。spark.ml为分类问题提供一种损失函数（Log Loss），为回归问题提供两种损失函数（平方误差与绝对误差）。

算法原理

GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 $f_{t-1}(x)​$，损失函数是 $L(y, f_{t-1}(x))​$， 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器$h_t(x)​$，让本轮的损失函数$L(y, f_{t}(x) =L(y, f_{t-1}(x)+ h_t(x))​$最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

构造过程

这里只给出网上找到的算法步骤，里面很多推导以及公式我还没弄懂，实在有些惭愧，后续闲下来会针对这个再进一步学习。

算法如下步骤，截图来自《The Elements of Statistical Learning》：

算法步骤解释：

  • 1、初始化，估计使损失函数极小化的常数值，它是只有一个根节点的树，即ganma是一个常数值。
  • 2、
    （a）计算损失函数的负梯度在当前模型的值，将它作为残差的估计
    （b）估计回归树叶节点区域，以拟合残差的近似值
    （c）利用线性搜索估计叶节点区域的值，使损失函数极小化
    （d）更新回归树
  • 3、得到输出的最终模型 f(x)

GBDT的优缺点及应用场景

优点：

  • 相对少的调参时间情况下可以得到较高的准确率。
  • 可灵活处理各种类型数据，包括连续值和离散值，使用范围广。
  • 可使用一些健壮的损失函数，对异常值的鲁棒性较强，比如Huber损失函数。

缺点：

  • 弱学习器之间存在依赖关系，难以并行训练数据。

应用场景：
GBDT几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。

而在实际应用中呢，多是作为一种预测分析算法，用在各行各业的领域，如：

  • 故障预测分析
  • 欺诈预测分析
  • 搜索引擎用户体验提升
  • 视频流媒体服务体验提升
  • 个人征信

GBDT重要参数介绍

  • lose：损失函数。

    ​ spark mllib一共提供3种，注意每一种都只适合一类问题，要么是回归，要么是分类。分类只可选择Log Loss，回归问题可选择平方误差(Squared Error)和绝对值误差(Absolute Error)。分别又称为L2损失和L1损失。绝对值误差（L1损失）在处理带有离群值的数据时比L2损失更加具有鲁棒性。分别如下表格：

    Loss Task Formula Description
    Log Loss Classification 2∑Ni=1log(1+exp(−2yiF(xi))) Twice binomial negative log likelihood.
    Squared Error Regression ∑Ni=1(yi−F(xi))2 也称为L2损失。回归任务的默认损失。
    Absolute Error Regression ∑Ni=1|yi−F(xi)| 也称为L1损失。对于异常值比Squared Error更强大。

  • numIterations：迭代次数。

    ​ GBDT迭代次数，每一次迭代将产生一棵树，因此这个numIterations也是算法中所包含的树的数目。增加numIterations会提高训练集数据预测准确率（注意是训练集数据上的准确率哦）。但是相应的会增加训练的时间。

  • learningRate：学习率。

    ​ 官方建议是不需要调整此参数。如果算法行为看起来不稳定，则降低此值可以提高稳定性。小的学习率（步长）肯定会增加训练的时间。

  • algo：使用的算法。

    ​ 初始化的时候直接给出这个树的算法类型,像这样：BoostingStrategy.defaultParams("Classification") 。一共就两种,分类(Classification) 或者是 回归(Regression）。

  • treeStrategy.numClasses：分类数量。

    ​ 由于分类只能做二分类，所以这个参数填2就可以了，多了会报错。

  • treeStrategy.maxDepth：树深度。

    ​ 和随机森林的一样，树越深，训练时间越长。

这里面主要用到的就是这几个参数，较为有用的就是迭代次数了，为了防止过拟合，这个迭代次数也得调整下，随着迭代次数的增加，一开始在验证集上预测误差会减小，迭代次数增大到一定程度后误差反而会增加，那么通过准确度vs.迭代次数曲线可以选择最合适的numIterations。

在MNIST手写数字集上使用GBDT做分类

由于这一系列暂时用的都是同一份数据集，我就不重复讲怎么处理数据了，有需要的同学可以看下前面的数据集介绍，对比上一篇随机森林的代码呢，其实差别只是换了一个训练函数，以及因为GBDT只能做二分类所以把数据过滤了下，只取了0和1的数据来做判断，下面贴出主函数，完整代码请点击这里：前往GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package SparkMLlib.Classification

import SparkMLlib.Base.MNIST_Util
import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.mllib.regression.LabeledPoint
import org.apache.spark.mllib.tree.{GradientBoostedTrees}
import org.apache.spark.mllib.tree.configuration.BoostingStrategy
import org.apache.spark.{SparkConf, SparkContext}

object GBDT_Example {

  def main(args: Array[String]): Unit = {
    // 获取当前运行路径
    val userPath = System.getProperty("user.dir")
    val trainLabelFilePath = userPath + "/src/main/resources/data/train-labels.idx1-ubyte"
    val trainImageFilePath = userPath + "/src/main/resources/data/train-images.idx3-ubyte"

    val testLabelFilePath = userPath + "/src/main/resources/data/t10k-labels.idx1-ubyte"
    val testImageFilePath = userPath + "/src/main/resources/data/t10k-images.idx3-ubyte"
//        val testLabelFilePath = "C:\\Users\\42532\\Desktop\\test-labels.idx1-ubyte"
//        val testImageFilePath = "C:\\Users\\42532\\Desktop\\test-images.idx3-ubyte"


    val conf = new SparkConf().setMaster("local[*]").setAppName("NaiveBayesExample")
    val sc = new SparkContext(conf)

    val trainLabel = MNIST_Util.loadLabel(trainLabelFilePath)
    val trainImages = MNIST_Util.loadImages(trainImageFilePath)
    val testLabel = MNIST_Util.loadLabel(testLabelFilePath)
    val testImages = MNIST_Util.loadImages(testImageFilePath)

    // Train a GradientBoostedTrees model.
    // The defaultParams for Classification use LogLoss by default.
    val boostingStrategy = BoostingStrategy.defaultParams("Classification")
    boostingStrategy.numIterations = 3 // Note: Use more iterations in practice.
    boostingStrategy.treeStrategy.numClasses = 2
    boostingStrategy.treeStrategy.maxDepth = 5
    // Empty categoricalFeaturesInfo indicates all features are continuous.
    boostingStrategy.treeStrategy.categoricalFeaturesInfo = Map[Int, Int]()

    //处理成mlLib能用的基本类型 LabeledPoint
    if(trainLabel.length == trainImages.length) {
      //标签数量和图像数量能对上则合并数组  Array[(labe,images)]

      val data = trainLabel.zip(trainImages)
        .filter(d => {d._1.toInt == 0 || d._1.toInt == 1}) //梯度树不能处理多分类问题，这里处理成判断0和1
        .map( d =>
        LabeledPoint(d._1.toInt, Vectors.dense(d._2.map(p => (p & 0xFF).toDouble)))
      )

      val trainRdd = sc.makeRDD(data)

      println("开始计算")

      val model = GradientBoostedTrees.train(trainRdd, boostingStrategy)
      model.save(sc,userPath + "/src/main/resources/model/GBDT")

      println("检验结果")
      val testData = testLabel.zip(testImages)
        .filter(d => {d._1.toInt == 0 || d._1.toInt == 1}) //梯度树不能处理多分类问题，这里处理成判断0和1
        .map(d =>( d._1.toInt,Vectors.dense(d._2.map(p => (p & 0xFF).toDouble )) ))
      val testRDD = sc.makeRDD(testData.map(_._2))
      val res = model.predict(testRDD).map(l => l.toInt).collect()

      //res.foreach(println(_))

      val tr = res.zip(testData.map(_._1))

      val sum = tr.map( f =>{
        if(f._1 == f._2.toInt) 1 else 0
      }).sum

      println("准确率为："+ sum.toDouble /tr.length.toDouble)

    }
  }
}

我们运行一下看看，用他默认的参数居然就有99.76% 的识别率！因为只是0和1，所以训练样本也少了五分之一，光看准确率可能并不能说明什么，不过也可以看出，对于二分类问题它是非常厉害的，而且训练时间也比随机森林快很多（可能随机森林调的参数树比较多，而且样本数据比较少）。

相关术语

泛化能力（generalization ability）：
​ 是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据对背后的规律，对具有同一规律的学习集以外的数据，经过训练的网络也能给出合适的输出，该能力称为泛化能力。

鲁棒性（Robustness）：
​ 从英文翻译而来-健壮是体质强壮健康的特性。当它被转换到系统中时，它指的是容忍可能影响系统功能体的扰动的能力。在同一行中，鲁棒性可以定义为“系统抵抗变化而不适应其初始稳定配置的能力”。

后记

其实梯度提升决策树最适合的用处并不是在分类上，而是处理一些回归问题，在今后的学习中我肯定也会遇到类似的问题，到时候在拿相关的数据集来进一步学习和尝试吧，今天这篇只能算是初探梯度提升决策树，一些推导和理论我也还不是太清楚明白，这些也都是有待以后补充了。

参考链接

0%