决策树高精准预测森林植被

决策树高精准预测森林植被

作者/Sandy Ryza等

Cloudera公司资深数据科学家,Apache Spark项目的活跃代码贡献者。最近领导了Cloudera公司的Spark开发工作。他还是Hadoop项目管理委员会委员。

决策树算法家族能自然地处理类别型和数值型特征。决策树算法容易并行化,它们对数据中的离群点(outlier)具有鲁棒性(robust),这意味着一些极端或可能错误的数据点根本不会对预测产生影响。算法可以接受不同类型和量纲的数据,对数据类型和尺度不相同的情况不需要做预处理或规范化。

如果进一步推广决策树,可以得到更为强大的决策森林(random decision forest)算法。由于决策森林算法的灵活性,我们有必要在这里介绍它。

基于决策树的算法还有一个优点,那就是理解和推理起来相对直观。实际上,日常生活中我们大概都无意间用过决策树所体现的推理方法。举个例子,早上我正要坐下来喝杯加奶咖啡,决定往咖啡中加牛奶之前,我会预测:牛奶有没有变质呢?我不确定牛奶是否变质。于是我会检查一下牛奶的建议食用期。如果建议食用期没过,我会预测牛奶没有坏。如果已经超过建议食用期三天,我认为牛奶已经变坏。如果超过建议食用期 3 天之内,我会闻一下。如果牛奶的气味有点儿异常,我会预测牛奶已经坏了,否则就没坏。

这一系列的“是 / 否”判断就是决策树算法所体现的预测过程。每个判断会走到两个分支中的一个,非此即彼,如图所示。

{%}

图:决策树:牛奶坏了吗?

前面提到的规则是我在上大学期间学会的,很直观。这些规则不但简单而且能有效地帮我区分牛奶是否已经坏了。这些都是一棵好的决策树的特点。

上面是一棵简化的决策树,构造过程非常灵活。为了更详细地说明决策树,我们来看看另外一个例子。在一个新奇的宠物店,一个机器人正忙于工作。在宠物店开门营业之前,它要学会什么动物适合孩子。最开始,店长给出了 9 种动物,其中有的适合做宠物,有的不适合。经过一番检查,机器人把这些信息编撰成一张表格,如表所示。

表:新奇宠物店的“特征向量”

{%}

数据中已经给定了名字,但名字并不能作为一个特征。我们没有道理认为名字本身具有预测性:就机器人所知,“Felix”可能是只猫的名字,也可能是只有毒的狼蛛。因此,这里所剩的特征有:两个数值型特征(重量、腿数),一个类别型特征(颜色),这三个特征用来预测一个类别型目标(是否适合做小孩的宠物)。

机器人可能会用一个简单的决策树拟合训练数据集,这棵决策树只根据“重量”做决策,如图所示。

{%}

图:机器人的第一棵决策树

可见,决策树的逻辑很好理解,而且有一定的道理:500 公斤的动物肯定不适合作宠物。这条规则能对 9 个样本中的 5 个作出正确预测。快速看一下训练数据,我们就能发现把重量的阈值降低为 100 公斤能够改进决策规则。这样我们就能正确预测 6 个样本。现在重量大的动物都能预测正确了,但重量轻的动物只能部分预测正确。

因此,为了进一步提高对体重小于 100 公斤的动物的预测准确度,机器人进行了第二次决策。如果能找到一个特征,通过这个特征将错误的“是”预测纠正为“否”预测,那就太好了。比如,训练集中有一种小型的绿色动物,听起来有点儿像条蛇,不适合做宠物,机器人就可以根据颜色对此作出正确判断,如图所示。

{%}

图:机器人的第二棵决策树

现在 9 个样本中有 7 个可以正确预测。当然,我们可以一直增加决策规则,直到对所有 9 个样本都能全部正确地作出预测。但这样得出的决策树很可能不合理,如果翻译成常用语,决策树可能是:“如果动物的重量小于 100 公斤,并且颜色是棕色而不是绿色,并且腿的数量少于 10,那么它适合做宠物。”虽然能完美拟合给定样本,但这样的决策树不能预测出棕色有四条腿的小型豹熊不合适做宠物。看来,为避免这种被称为过度拟合的现象,还是需要继续改进啊。

不过到目前为止,对决策树算法的介绍已经足够我们在 Spark 中使用决策树算法了。接下来的内容将描述怎样选择决策规则,何时停止决策过程以及怎样通过创建决策森林来提高准确度。

Covtype数据集

著名的数据集 Covtype 数据集,可以在线下载(http://t.cn/R2wmIsI),里面包含一个 CSV 格式的压缩数据文件 covtype.data.gz,附带一个描述数据文件的信息文件 covtype.info。

该数据集记录了美国科罗拉多州不同地块的森林植被类型(也就是现实中的森林,这仅仅是巧合!)每个样本包含了描述每块土地的若干特征,包括海拔、坡度、到水源的距离、遮阳情况和土壤类型,并且随同给出了地块的已知森林植被类型。我们需要总共 54 个特征中的其余各项来预测森林植被类型。

人们已经用该数据集进行了研究,甚至在 Kaggle 大赛(https://www.kaggle.com/c/forest-cover-type-prediction)中也用到过。之所以研究这个数据集,原因在于它不但包含了数值型特征而且包含了类别型特征。该数据集共有 581 012 个样本,虽然还称不上大数据,但作为一个范例来讲已经足够大,能够反映出一些数据上的问题。

准备数据

幸运的是,数据已经是简单的 CSV 格式了。在开始用 Spark 的 MLlib 之前,我们不需要进行大量的清洗或其他准备工作。

解压 covtype.data 文件并复制到 HDFS。我们假定文件放在 /user/ds/ 目录下。请启动spark-shell

Spark MLlib 将特征向量抽象为LabeledPoint,它由一个包含多个特征值的 Spark MLlibVector和一个称为标号(label)的目标值组成。该目标为Double类型,而Vector本质上是对多个Double类型值的抽象。这说明LabeledPoint只适用于数值型特征。但只要经过适当编码,LabeledPoint也可用于类别型特征。

其中一种编码是 one-hot(http://en.wikipedia.org/wiki/One-hot)或 1-of-n 编码。在这种编码中,一个有 N 个不同取值的类别型特征可以变成 N 个数值型特征,变换后的每个数值型特征的取值为 0 或 1。在这 N 个特征中,有且只有一个取值为 1,其他特征取值都为 0。比如,类别型特征“天气”可能的取值有“多云”“有雨”或“晴朗”。在 1-of-n 编码中,它就变成了三个数值型特征:多云用1,0,0表示,有雨用0,1,0表示,晴朗用0,0,1表示。可以为这三个数值型特征分别取名:is_cloudyis_rainyis_clear

另一种可能的编码方式是为类别型特征的每个可能取值分配一个不同数值,比如多云 1.0,有雨 2.0 等。

在编码过程中,将类别型特征当成数值型特征时要小心。类别型特征值原本是没有大小顺序可言的,但被编码为数值之后,它们就“显得”有大小顺序了。被编码后的特征若被视为数值,算法在一定程度上会假定有雨比多云大,而且大两倍,这样就可能导致不合理的结果。当然,只要算法不把数字编码当作数值来用也没什么问题。

虽然 Covtype 数据集所有列都是数值,但从本质上讲,该数据集并不是完全由数值型特征组成。covtype.info 文件显示,有 4 列是由同一个类别型特征Wilderness_Type经过 one-hot 编码生成的,它被赋予了 4 个可能的取值。同样,还有 40 列也是同一个类别型特征Soil_Type。目标本身也是类别型值,用 1 到 7 编码。其余的才是由不同单位度量的数值型特征,比如米、度或某个定性的指标值。

在 Covtype 数据集中,我们看到它同时使用了前面提到的类别型变量的两种编码方法。如果对类别型特征不用这两种编码方式,而是直接使用类似“Rawah Wilderness Area”这样的值,有可能会更简单更直接。这可能是历史的产物:Covtype 数据集在 1998 年发布。基于性能方面的考虑,或者为了满足当时处理工具要求的格式(当时工具更多是面向回归问题的),数据集往往用这样的方式进行编码。

第一棵决策树

开始时我们原样使用数据。决策树(DecisionTree)的实现,以及 Spark MLlib 中其他几个实现,都要求输入必须是LabeledPoint对象格式:

import org.apache.spark.mllib.linalg._
import org.apache.spark.mllib.regression._

val rawData = sc.textFile("hdfs:///user/ds/covtype.data")

val data = rawData.map { line =>
  val values = line.split(',').map(_.toDouble)
  val featureVector = Vectors.dense(values.init) 1
  val label = values.last - 1 2
  LabeledPoint(label, featureVector)
}

1init 返回除最后一个值之外的所有值;最后一列是目标。

2决策树要求 label 从 0 开始,所以要减 1。

虽然我们不知道怎样用 54 个特征来描述科罗拉多州的一个从未见过的地块,也不知道如何预测地块上的森林植被类型。我们可以直接从数据集中取出部分数据,用以评估所得到的模型。之前,为了评测保留的收听数据和模型预测之间的一致性,我们采用 AUC 指标。这里我们采用同样的原理,不过评价指标改为精确度指标。我们现在将数据分成完整的三部分:训练集、交叉检验集(CV)和测试集。在下面的代码中你会看到,训练集占 80%,交叉检验集和测试集各占 10%:

val Array(trainData, cvData, testData) =
  data.randomSplit(Array(0.8, 0.1, 0.1))
trainData.cache()
cvData.cache()
testData.cache()

和 ALS 实现一样,DecisionTree 实现也有几个超参数,我们需要从训练集和 CV 集中为它们选择合适的值。第三个数据集,也就是测试集,用于对基于选定超参数的模型期望准确度做无偏估计。模型在交叉检验集上的准确度往往有点儿过于乐观,不是无偏差的。因此,我们决定在测试集上评估最终模型。

现在我们还是先来试试在训练集上构造一个 DecisionTreeModel 模型,参数采用默认值,并用 CV 集来计算结果模型的指标:

import org.apache.spark.mllib.evaluation._
import org.apache.spark.mllib.tree._
import org.apache.spark.mllib.tree.model._
import org.apache.spark.rdd._

def getMetrics(model: DecisionTreeModel, data: RDD[LabeledPoint]):
    MulticlassMetrics = {
  val predictionsAndLabels = data.map(example =>
    (model.predict(example.features), example.label)
  )
  new MulticlassMetrics(predictionsAndLabels)
}

val model = DecisionTree.trainClassifier(
  trainData, 7, Map[Int,Int](), "gini", 4, 100)

val metrics = getMetrics(model, cvData)

这里用 trainClassifier,而不用 trainRegressortrainClassifier 指示每个 LabeledPoint 里的目标都应该当作不同的类别标号,而不是数值型特征值。(对于回归问题 trainRegressor 情况类似,这里不再单独讨论。)

示例代码中,我们必须指明数据集中目标的取值个数,也就是 7。Map 保存类别型特征的信息,后面在解释参数值 gini、最大深度 4 和最大桶数 100 的含义时我们一并讨论。

MulticlassMetrics 以不同方式计算分类器预测质量的标准指标,这里分类器运行在 CV 集上。理想情况下,分类器对 CV 集中每个样本的目标类别应该都能做出正确预测。这里的指标以不同方式度量这种正确性。

MulticlassMetrics 一起,Spark 还提供了 BinaryClassificationMetrics。它提供类似 MulticlassMetrics 的评价指标实现,不过仅适用常见的类别型目标只有两个可能取值的情况。由于这里目标类别的可能取值有多个,所以我们不能直接使用 BinaryClassificationMetrics

我们有必要先看看混淆矩阵:

metrics.confusionMatrix

...
14019.0  6630.0   15.0    0.0    0.0  1.0   391.0
5413.0   22399.0  438.0   16.0   0.0  3.0   50.0
0.0      457.0    2999.0  73.0   0.0  12.0  0.0
0.0      1.0      163.0   117.0  0.0  0.0   0.0
0.0      872.0    40.0    0.0    0.0  0.0   0.0
0.0      500.0    1138.0  36.0   0.0  48.0  0.0
1091.0   41.0     0.0     0.0    0.0  0.0   891.0

你得到的值可能稍有不同。构造决策树过程中的一些随机选项会导致分类结果存在偏差。

因为目标类别的取值有 7 个,所以混淆矩阵是一个 7×7 的矩阵,矩阵每一行对应一个实际的正确类别值,矩阵每一列按序对应预测值。第 i 行第 j 列的元素代表一个正确类别为 i 的样本被预测为类别为 j 的次数。因此,对角线上的元素代表预测正确的次数,而其他元素则代表预测错误的次数。对角线上的次数多是好的。但也确实出现了一些分类错误的情况,比如分类器甚至没有将任何一个样本类别预测为 5。

将准确度用一个数字概括是有帮助的。显然,我们可以想到用预测正确的样本数占整个样本数的比例来计算准确度:

metrics.precision

...
0.7030630195577938

大约 70% 样本的分类是正确的。这个比例通常被称为准确度(accuracy),在 Spark 的 MulticlassMetrics 指标中称为精确度(precision),意思差不多。

实际上精确度(precision)是二元分类问题中一个常用的指标。二元分类问题中的目标类别只有两个可能的取值,而不是多个取值,其中一个类代表正,另一类代表负,精确度就是被标记为“正”而且确实是“正”的样本占所有标记为“正”的样本的比例。和精确度一起出现的还有另一个指标召回率(recall)。召回率是被分类器标记为“正”的所有样本与所有本来就是“正”的样本的比率。

比如,假设数据集有 50 个样本,其中 20 个为正。分类器将 50 个样本中的 10 个标记为“正”,在这 10 个被标记为“正”的样本中,只有 4 个确实是“正”(也就是 4 个分类正确),所以这里的精确度为 4/10=0.4,召回率为 4/20=0.2。

我们可以把这些概念应用到多元分类问题,把每个类别单独视为“正”,所有其他类型视为“负”。比如,要计算每个类别相对其他类别的精确度,请看如下代码:

(0 until 7).map( 3
  cat => (metrics.precision(cat), metrics.recall(cat))
).foreach(println)

...
(0.6805931840866961,0.6809492105763744)
(0.7297560975609756,0.7892237892589596)
(0.6376224968044312,0.8473952434881087)
(0.5384615384615384,0.3917910447761194)
(0.0,0.0)
(0.7083333333333334,0.0293778801843318)
(0.6956168831168831,0.42828585707146427)

3DecisionTreeModel 模型的类别标号从 0 开始。

由此可以看到每个类型的准确度都各不相同。就本例而言,我们没道理认为某个类型的准确度要比其他类型的准确度更重要,因此用一个多元分类的总体精确度就可以较好地度量分类准确度。

虽然 70% 的准确度听起来还不错,但我们还不能立马看出这个准确度是优秀还是糟糕。作为基准,一个朴素方法的准确度是多少呢?即使是一个坏了的时钟,每天也会有两次显示的时间是正确的。类似地,为每个样本随便猜一个类别,偶尔也能得到正确答案。

按照类别在训练集中出现的比例来预测类别,我们来构建一个“分类器”。每次分类的正确度将和一个类型在 CV 集中出现的次数成正比。比如,一个类别在训练集中占 20%,在 CV 集中占 10%,那么该类别将贡献 10% 的 20%,即 2% 的总体准确度。通过按 20% 的时候将样本猜测为该类,CV 集样本中有 10% 的样本会被猜对。将所有类别在训练集和 CV 集出现的概率相乘,然后把结果相加,我们就得到了一个对准确度的评估:

import org.apache.spark.rdd._

def classProbabilities(data: RDD[LabeledPoint]): Array[Double] = {
  val countsByCategory = data.map(_.label).countByValue() 4
  val counts = countsByCategory.toArray.sortBy(_._1).map(_._2) 5
  counts.map(_.toDouble / counts.sum)
}

val trainPriorProbabilities = classProbabilities(trainData)
val cvPriorProbabilities = classProbabilities(cvData)
trainPriorProbabilities.zip(cvPriorProbabilities).map { 6
  case (trainProb, cvProb) => trainProb * cvProb
}.sum

...
0.37737764750734776

4计算数据中每个类别的样本数:(类别,样本数)。

5对类别的样本数进行排序并取出样本数。

6把训练集和 CV 集中的某个类别的概率结成对,相乘然后相加。

随机猜测的准确度为 37%,所以前面得到 70% 的准确度看起来还不错。但是 70% 的准确度是在 DecisionTree.trainClassifier() 中用默认参数的条件下取得的。如果在决策树构建过程中试试超参数的其他值,准确度还可以提高。

决策树的超参数

ALS 算法可以提供几个超参数。我们先构造超参数取不同值时的不同组合的模型,然后用某个指标评估每个组合结果的质量,通过这种方式来选择超参数值。这里我们采用相同的过程,但指标由 AUC 改为多元分类准确度。这里控制决策树选择过程的超参数为最大深度、最大桶数和不纯性度量。

最大深度只对决策树的层数作出限制,它是分类器为了对样本进行分类所作的一连串判断的最大次数。限制判断次数有利于避免对训练数据产生过拟合。

决策树算法负责为每层生成可能的决策规则,比如在宠物店示例中,决策规则类似“重量≥ 100”或者“重量≥ 500”。决策总是采用相同形式:对数值型特征,决策采用特征≥值的形式;对类别型特征,决策采用特征在(值 1, 值 2,…)中的形式。因此,要尝试的决策规则集合实际上是可以嵌入决策规则中的一系列值。Spark MLlib 的实现把决策规则集合称为“桶”(bin)。桶的数目越多,需要的处理时间越多但找到的决策规则可能更优。

什么因素促使好的决策规则产生?直观上讲,好的决策规则应该通过目标类别值对样本作出有意义的划分。比如,如果一个规则将 Covtype 数据集划分为两个子集,其中一个子集的样本全部属于类别 1~3,第二个子集中的样本则都属于和类别 4~7,那么它就是一个好规则,因为这个规则清楚地把一些类别和其他类别分开。如果样本集用一个决策规则划分,划分前后每个集合各类型的不纯性程度没有改善,那么这个规则就没什么价值。沿着该决策规则的分支走下去,每个目标类别的可能取值的分布仍然是一样的,因此实际上它在构造可靠的分类器方面没有任何进步。

换句话说,好规则把训练集数据的目标值分为相对是同类或“纯”(pure)的子集。选择最好的规则也就意味着最小化规则对应的两个子集的不纯性(impurity)。不纯性有两种常用的度量方式:Gini 不纯度(http://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity)或熵(http://en.wikipedia.org/wiki/Entropy_(information_theory))。

Gini 不纯度直接和随机猜测分类器的准确度相关。在每个子集中,它就是对一个随机挑选的样本进行随机分类时分类错误的概率(随机挑选样本和随机分类时要参照子数据集的类别分布)。这就是用 1 减去每个类别的比例与自身的乘积之和。假设子数据包含 N 个类别的样本,pi 是类别 i 的样本所占比例,于是可以得到如下 Gini 不纯度公式:

{%}

如果子数据集中所有样本都属于一个类别,则 Gini 不纯度的值为 0,因为这个子数据集完全是“纯”的。当子数据集中的样本来自 N 个不同的类别时,Gini 不纯度的值大于 0,并且在每个类别的样本数都相同时达到最大,也就是最不纯的情况。

熵是另一种度量不纯性的方式,它来源于信息论。解释熵的本质更困难,但熵代表了子集中目标取值集合的不确定程度。如果子集只包含一个类别,则是完全确定的,熵为 0。熵可以用以下熵计算公式定义:

{%}

有意思的是,不确定性是有单位的。由于取自然对数(以 e 为底),熵的单位是纳特(nat)。相对于以 e 为底的纳特,我们更熟悉它对应的比特(以 2 为底取对数即可得到)。它实际上度量的是信息,因此在使用熵的决策树中,我们也常说决策规则的信息增益。

不同的数据集上对于挑选好的决策规则方面,这两个度量指标各有千秋。Spark 的实现默认采用 Gini 不纯度。

有些决策树实现会对候选决策规则设定最小信息增益,或最小不纯度降低。在改善子集合的不纯性方面不达标的决策规则将不被采用。与通过减少最大深度一样,这也有利于避免过拟合,因为对训练集没有什么区分度的决策规则实际上对区分将来的数据也没什么帮助。然而,Spark MLlib 目前还没有实现最小信息增益之类的规则。

决策树调优

采用哪个不纯性度量所得到的决策树的准确度更高,或者最大深度或桶数取多少合适,从数据上看,回答这些问题是困难的。幸运的是,我们可以让 Spark 来尝试这些值的许多组合并报告结果:

val evaluations =
  for (impurity 7
    yield {
      val model = DecisionTree.trainClassifier(
        trainData, 7, Map[Int,Int](), impurity, depth, bins)
      val predictionsAndLabels = cvData.map(example =>
        (model.predict(example.features), example.label)
      )
      val accuracy =
        new MulticlassMetrics(predictionsAndLabels).precision
      ((impurity, depth, bins), accuracy)
    }

evaluations.sortBy(_._2).reverse.foreach(println) 8

...
((entropy,20,300),0.9125545571245186)
((gini,20,300),0.9042533162173727)
((gini,20,10),0.8854428754813863)
((entropy,20,10),0.8848951647411211)
((gini,1,300),0.6358065896448438)
((gini,1,10),0.6355669661959777)
((entropy,1,300),0.4861446298673513)
((entropy,1,10),0.4861446298673513)

7看成是三重 for 循环。

8根据第二个值(准确度)降序排序并打印。

很显然最大深度为 1 太小,得到的结果比较差。桶数多有点儿帮助,但帮助也不大。在合理的最大深度下,两个不纯性度量的结果也差不多。我们可以继续这个过程来探寻更好的超参数。桶数应该越多越好,但会减慢模型构造过程且增加内存的使用量。在所有情况下我们都应该试试两种不纯性度量。增加最大深度能提高准确度,但这里有个拐点,超过它之后增加深度也没有用了。

到目前为止,所有示例代码都没用到占数据集 10% 的保留测试集。如果说 CV 集的目的是评估适合训练集的参数,那么测试集的目的是评估适合 CV 集的超参数。也就是说,测试集保证了对最终选定的超参数及模型准确度的无偏估计。

前面的测试表明,目前为止超参数的最佳选择是:不纯性度量采用熵,最大深度为 20,桶 数为 300,这时得到的准确度为 91.2%。但是,模型在构建过程中还有一个随机元素。最 好的模型和评估结果可能还需要一点儿运气的成分,因此准确度评估可能有一些乐观。换 句话说,超参数也可能有过拟合现象。

要想真正评估这个最佳模型在将来的样本上的表现,当然需要在没有用于训练的样本上进行评估。但是,我们也需要避免使用在评估环节中用过的 CV 集样本。这也就是需要把第三个子集即测试集保留在一边的原因。最后一步,用得到的超参数同时在训练集和 CV 集上构造模型并且像前面那样进行评估:

val model = DecisionTree.trainClassifier(
  trainData.union(cvData), 7, Map[Int,Int](), "entropy", 20, 300)

结果准确度为 91.6%,基本上没变。因此,开始的估计看来是可靠的。

现在该重新回顾一下过拟合的问题了。如前所述,我们可能构造这样一棵决策树:它的深度非常深,非常复杂,它能很好地甚至是完美拟合给定的训练样本,但却不能把这种准确度推广到其他样本上,因为它过于紧密地拟合了训练样本中的细微特质和噪声。过拟合问题不只是在决策树算法中存在,而是大多数机器学习算法普遍存在的问题。

当决策树有过拟合问题时,在与模型拟合相同的训练数据上它的准确度很高,但在其他样本上准确度很低。最终模型在其他新样本上的准确度大约为 91.6%。当然,通过 trainData.union(cvData),我们就能轻易在训练数据上评估准确度。这时的准确度大约为 95.3%。

差别不是很大,但也显示决策树在一定程度上存在对训练数据的过拟合。减小最大深度可能会使过拟合问题有所改善。

重谈类别型特征

到目前为止我们还没有对示例代码中的参数 Map[Int,Int]() 作出解释。这个参数值,比如 7,指明了输入数据中每个类别型特征预期的不同取值的个数。这个 Map 中元素的键是特征在输入向量 Vector 中的下标,Map 中元素的值是类别型特征的不同取值个数。目前 Spark MLlib 实现中要求事先给定这些信息。

参数取为空 Map(),则表示算法不需要把任何特征作为类别型,也就是说所有特征都是数值型的。实际上,Spark MLlib 实现中所有特征都是数值,但概念上其中某些是类别型特征。如前所述,如果简单地把类别型变量当作数值型对待,将其映射到不同的数字,这种做法是错误的,原因在于算法会试图从一个没有意义的大小顺序中学习。

好在,这里的类别型特征已经用 one-hot 方式编码成了多个二元的 0/1 值。把这些单个的特征当作数值型来处理并没有什么问题,因为任何基于数值型特征的决策规则都需要选择 0 或 1 作为其阈值。所有的阈值都是 0 或 1,所以都是等价的。

当然,这种编码迫使决策树算法在底层要单独考虑类别型特征的每一个值。如果用一个类别型变量就不会有这个方面的限制。如果某个类别型特征有 40 个取值,决策树可以在一次决策中对多个类别组进行判断。这样的方式更直接更优。另一方面,用 40 个数值型特征表示一个有 40 个取值的类别型特征会增加内存使用量并且减慢决策速度。

如果取消数据集已经完成的 one-hot 编码,情况会怎样?下面我们试试解析输入,将 one-hot 编码所得到的两个类别型特征转换回一系列不同的数值型值:

val data = rawData.map { line =>
  val values = line.split(',').map(_.toDouble)
  val wilderness = values.slice(10, 14).indexOf(1.0).toDouble 9
  val soil = values.slice(14, 54).indexOf(1.0).toDouble 10
  val featureVector =
    Vectors.dense(values.slice(0, 10) :+ wilderness :+ soil) 11
  val label = values.last - 1
  LabeledPoint(label, featureVector)
}

9“wilderness”对应的 4 个二元特征中哪一个取值为 1。

10类似地,“soil”对应 40 个二元特征。

11将推导出的特征加回到前 10 个特征中。

数据集可以重复拆分成训练集 /CV 集 / 测试集和模型评估的过程。这里,我们指定两个新的类别型特征的不同取值个数,这样这两个特征就会被当作类别型而不是数值型特征处理。由于地块(soil)特征有 40 个不同的取值,DecisionTree 需要桶数目最少增加到 40。考虑前面的结果,增加决策树的深度直至 30,30 是当前 DecisionTree 能支持的最大深度。最后,在训练集和 CV 集上的准确度报告如下:

val evaluations =
  for (impurity  4, 11 -> 40),
        impurity, depth, bins) 12
      val trainAccuracy = getMetrics(model, trainData).precision
      val cvAccuracy = getMetrics(model, cvData).precision
      ((impurity, depth, bins), (trainAccuracy, cvAccuracy)) 13
    }

...
((entropy,30,300),(0.9996922984231909,0.9438383977425239))
((entropy,30,40),(0.9994469978654548,0.938934581368939))
((gini,30,300),(0.9998622874061833,0.937127912178671))
((gini,30,40),(0.9995180059216415,0.9329467634811934))
((entropy,20,40),(0.9725865867933623,0.9280773598540899))
((gini,20,300),(0.9702347139020864,0.9249630062975326))
((entropy,20,300),(0.9643948392205467,0.9231391307340239))
((gini,20,40),(0.9679344832334917,0.9223820503114354))
((gini,10,300),(0.7953203539213661,0.7946763481193434))
((gini,10,40),(0.7880624698753701,0.7860215423792973))
((entropy,10,40),(0.78206336500723,0.7814790598437661))
((entropy,10,300),(0.7821903188046547,0.7802746137169208))

12指定类别型特征 10 和 11 的取值个数。

13返回在训练集和 CV 集上的准确度。

如果在集群上运行以上代码,会发现决策树构建过程比之前快了好几倍。

在深度为 30 的时候,训练集几乎完美拟合。这时虽然存在一定程度的过拟合,但是在交叉检验集上的准确度是最高的。选择熵作为不纯性度量和更多的桶数目,再一次看起来有助于提高准确度。在本次测试集上,准确度为 94.5%。通过把类别型特征真正作为类别型,分类器的准确度提高了将近 3%。

随机决策森林

如果一步一步运行所有的示例代码,你可能已经注意到运行结果和文章中给出的结果稍有不同。这是由决策树构建过程中的随机因素造成的,在决定采用什么数据和尝试哪些决策规则时都有随机因素的影响。

在决策树的每层,算法并不会考虑所有可能的决策规则。如果在每层上都要考虑所有可能的决策规则,算法的运行时间将无法想象。对一个有 N 个取值的类别型特征,总共有 2N – 2 个可能的决策规则(除空集和全集以外的所有子集)。即使对于一个一般大的 N,这也将创建数十亿个候选决策规则。

相反,如果决策树使用一些启发式策略,就能够聪明地找到需要实际考虑的少数规则。在选择规则的过程中也涉及一些随机性;每次只考虑随机选择少数特征,而且只考虑训练数据中一个随机子集。在牺牲一些准确度的同时换回了速度的大幅提升,同时每次决策树算法构造的树都不相同。这是件好事。

因为集体的智慧常常比个体预测要更准确。

为了说明问题,我们来做个快速测验:伦敦运营的黑色的士数量有多少?

请猜一下,先不要偷看答案。

正确答案是约 19 000,我猜 10 000,这离正确答案差了很多。因为我猜的数比较小,所以你有可能猜的比我大,这样我们平均一下就可能更准确了。这里貌似又有点儿“趋均值回归”的味道了。我随便问了办公室里的 13 个人,大家的平均值是 11 170,这个答案确实要更接近正确答案。

要取得这种效应,关键是每个人猜的时候要独立,互不影响。(你没偷看答案,是吧?)如果大家事先都已经统一过意见并用同一个方法猜,这个练习就没有意义了,因为大家猜的答案都一样,而且这个相同的答案可能错得离谱。如果在你猜之前,我把我的情况告诉你,这会影响你的猜测,那么咱俩的平均数可能并不会更准确,甚至会更糟。

基于上述考虑,树最好不只是一棵,而应该有很多棵,每一棵都能对正确目标值给出合理、独立且互不相同的估计。这些树的集体平均预测应该比任一个体预测更接近正确答案。正是由于决策树构建过程中的随机性,才有了这种独立性,这就是随机决策森林的关键所在。

通过 RandomForest,Spark MLlib 可以构建随机决策森林。顾名思义,随机决策森林是由多个决策树独立构造而成。

val forest = RandomForest.trainClassifier(
  trainData, 7, Map(10 -> 4, 11 -> 40), 20,
  "auto", "entropy", 30, 300)

DecisionTree.trainClassifier() 相比,这里出现了两个新参数。第一个代表要构建多少棵树,这里是 20。由于要构造 20 棵决策树,而之前我们只构造了一棵决策树,因此这里模型构建过程耗时可能比之前长得多。

第二个新参数是特征决策树每层的评估特征选择策略,这里设为 "auto"(自动)。随机决策森林在实现过程中决策规则不会考虑全部特征,而只考虑全部特征的一个子集。特征选择策略参数控制算法如何选择该特征子集。只检查少数特征速度明显要快,并且由于速度快,随机决策森林才得以构造多棵决策树。

但是,只考虑全部特征的一个子集,这种做法也使个体决策树的决策更加独立,因此决策森林作为整体往往更不会产生过拟合问题。如果某个特征包含噪声数据,或只针对训练集有预测性,则这种预测性是有误导性质的。采用随机森林后大多数树在大多数时候将因此不会考虑这个问题特征。大多数的树将不会拟合噪声,因此它们的“票数”将超过那些拟合噪声的树。

实际上在构造决策森林的时候,每棵树甚至都没必要用到全部训练数据。同理,每棵树的输入数据可以随机选择。

随机决策森林的预测只是所有决策树预测的加权平均。对于类别型目标,这就是得票最多的类别,或有决策树概率平均后的最大可能值。随机决策森林和决策树一样也支持回归问题,这时森林作出的预测就是每棵树预测值的平均。

RandomForestModel 模型的准确度立刻变为 96.3%——提高了约 2%。换个角度看,比之前我们得到的最好决策树的错误率降低了 33%,错误率由 5.5% 降到了 3.7%。

在大数据的背景下,随机决策森林非常有吸引力,因为决策树往往是独立构造的,诸如 Spark 和 MapReduce 这样的大数据技术本质上适合数据并行问题。也就是说,总体答案的每个部分可以通过在部分数据上独立计算来完成。随机决策森林中决策树可以并且应该只在特征子集或输入数据子集上进行训练,基于这个事实,决策树构造的并行化就很简单了。

由于决策树通常在全体训练数据的一个子集上构造,可以用剩余数据对其进行内部交叉验证,因此随机决策森林也可以顺便评估其准确度,尽管 Spark MLlib 还没有对该功能提供直接支持。这意味着随机决策森林甚至能知道其内部哪棵决策树是最准确的,因而可以增加其权重。

这个特点也用于评估哪些输入特征对预测目标最有帮助,因此它有助于解决特征选择问题。

进行预测

构建分类器有趣又简单,但它不是最终目的。我们的目的是利用它进行预测。之前的辛苦努力在这里都将得到回报,做起来也相对容易。训练集由 LabeledPoint 类型实例组成,每个实例包含一个 Vector 和目标值,它们分别是输入和已知的输出。波尔先生说,当进行预测时,特别是预测未来时,输出当然是未知的。

现在我们已经展现了 DecisionTreeRandomForest 训练的结果,它们分别是 DecisionTreeModelRandomForestModel 对象。这两个模型对象本质上都只有一个方法 predict()。 和 LabeledPoint 的特征向量部分一样,predict() 方法接受一个 Vector。因此通过把每个新样本转换成一个特征向量,我们同样可以对它进行分类并预测它的目标类别:

val input = "2709,125,28,67,23,3224,253,207,61,6094,0,29"
val vector = Vectors.dense(input.split(',').map(_.toDouble))
forest.predict(vector) 14

14同样我们可以一次性对整个 RDD 做预测。

结果应该为 4.0,对应原始 Covtype 数据集中的类别 5(原始特征从 1 开始)。显然,算法预测示例中讨论的地块植被类型为“山杨”(Aspen)。

通过使用 Covtype 数据集和 Spark MLlib 中实现的决策树和决策森林算法,我们演示了如何根据位置和土壤类型等信息预测森林植被的类型。构建的分类器结果也相当准确。一般情况下,准确度超过 95% 是很难达到的。通过包括更多特征,或将已有特征转换成预测性更好的形式,可以进一步提高准确度。在分类器模型的迭代式改进过程中,我们常常这样反复尝试。比如,对数据集,距离地表水的水平和垂直距离这两个特征可以生成第三个特征:离地表水的直线距离。或者,如果能收集到更多数据,为了提高准确度,我们可能会尝试增加更多特征,比如土壤湿度。

当然,用 Covtype 数据集预测森林植被类型只是预测问题的一种类型,现实中我们还有其他的预测问题。比如,有些问题要求预测连续型的数值,而不是类别型值。再者,Spark MLlib 实现的算法也不限于决策树和决策森林。对分类问题,Spark MLlib 提供的实现包括:

是的,你没看错,逻辑回归是一种分类技术。逻辑回归底层通过预测类别的连续型概率函数来进行分类。

这些算法与决策树和决策森林很不相同。但是,其中许多元素还是一样的:它们接受一个 LabeledPoint 类型的 RDD 作为输入,需要通过将输入数据划分为训练集、交叉检验集和测试集来选择超参数。对这些其他算法,我们可以用相同的通用原理为分类和决策问题建模。

本文选自《Spark高级数据分析》

 

{%}

《Spark高级数据分析》首先介绍了Spark及其生态系统,接着详细介绍了将分类、协同过滤及异常检查等常用技术应用于基因学、安全和金融领域的若干模式。如果你对机器学习和统计学有基本的了解,并且会用Java、Python或Scala编程,这些模式将有助于你开发自己的数据应用。