spark源码分析之随机森林(Random Forest)（二）
spark源码分析之随机森林(Random Forest)（三）
spark源码分析之随机森林(Random Forest)（四）
spark源码分析之随机森林(Random Forest)（五）

Spark在mllib中实现了tree相关的算法，决策树DT（DecisionTree），随机森林RF（RandomForest），GBDT（Gradient Boosting Decision Tree），其基础都是RF，DT是RF一棵树时的情况，而GBDT则是循环构建DT，GBDT与DT的代码是非常简单明了的，本文将分成五部分分别对RF的源码进行分析，介绍spark在实现过程中使用的一些技巧。

1. 决策树与随机森林

首先对决策树和随机森林进行简单的回顾。

1.1. 决策树

在决策树的训练中，如上图所示，就是从根节点开始，不断的分裂，直到触发截止条件，在节点的分裂过程中要解决的问题其实就2个

• 分裂点：一般就是遍历所有特征的所有特征值，选取impurity最大的分成左右孩子节点，impurity的选取有信息熵（分类），最小均方差（回归）等方法
• 预测值：一般取当前最多的class（分类）或者取均值（回归）

1.2. 随机森林

随机森林就是构建多棵决策树投票，在构建多棵树过程中，引入随机性，一般体现在两个方面，一是每棵树使用的样本进行随机抽样，分为有放回和无放回抽样。二是对每棵树使用的特征集进行抽样，使用部分特征训练。
在训练过程中，如果单机内存能放下所有样本，可以用多线程同时训练多棵树，树之间的训练互不影响。

2. spark RF优化策略

spark在实现RF时，使用了一些优化技巧，提高训练效率。

2.1. 逐层训练

当样本量过大，单机无法容纳时，只能采用分布式的训练方法，数据是在集群中的多台机器存放，如果按照单机的方法，每棵树完全独立访问样本数据，则样本数据的访问次数为数的个数k*每棵树的节点数N，相当于深度遍历。在spark的实现中，因为数据存放在不同的机器上，频繁的访问数据效率非常低，因此采用广度遍历的方法，每次构造所有树的一层，例如如果要训练10棵树，第一次构造所有树的第一层根节点，第二次构造所有深度为2的节点，以此类推，这样访问数据的次数降为树的最大深度，大大减少了机器之间的通信，提高训练效率。

2.2. 样本抽样

当样本存在连续特征时，其可能的取值可能是无限的，存储其可能出现的值占用较大空间，因此spark对样本进行了抽样，抽样数量

val requiredSamples = math.max(metadata.maxBins * metadata.maxBins, 10000)

最少抽样1万条，当然这样会降低模型精度。

2.3. 特征装箱

其实没什么神秘的，每个离散特征值(对于连续特征，先离散化)称为一个Split，上下限[lowSplit, highSplit]组成一个bin，也就是特征装箱，默认的maxBins是32。对于连续特征，离散化时的bin的个数就是maxBins，采用等频离散化；对于有序的离散特征，bin的个数是特征值个数+1；对于无序离散特征，bin的个数是2^(M-1)-1，M是特征值个数

3. 源码分析

我们从官方给出的分类demo开始，逐层分析其实现

3.1. 训练数据的解析

主要是LabelPoint的构造，官方demo中要求训练数据是LibSVM格式的

parsed.map { case (label, indices, values) =>
      LabeledPoint(label, Vectors.sparse(d, indices, values))
    }

可以看到LabelPoint有两个成员，第一个是样本label，第二个是稀疏向量SparseVector，d是其size，在这里其实是特征数，indices是实际非0特征的index，values里面是实际的特征值，这里需要注意的是，SVN格式的特征index是从0开始的，这里进行了-1，变成从0开始了。

3.2. demo中训练参数说明

官方demo中只设置了部分参数

val model = RandomForest.trainClassifier(trainingData, numClasses, categoricalFeaturesInfo,
      numTrees, featureSubsetStrategy, impurity, maxDepth, maxBins)

• categoricalFeaturesInfo：Map[Int, Int]，key是特征的index，value为特征值的个数（或者说几种），这里值得注意的是，因为LabelPoint中进行了index-1的变换，这个里面的key也需要-1（参见后面metadata的numBins的计算）。例如性别这个特征在样本中的index为1，特征值男/女两种，则0->2
• featureSubsetStrategy：特征子集的抽取方法，支持”auto”, “all”, “sqrt”, “log2”, “onethird”
• impurity：不纯度，其实就是节点分裂时的衡量准则，例如信息熵，均方差等，这里支持三种，gini（基尼指数），entripy（信息熵），variance（均方差）
• maxDepth：树的最大深度
• maxBins：最大装箱数，或者说是特征的最大可能切分数+1。这个值必须大于等于最大的离散特征值数

3.3. 参数封装

spark根据用户提供的参数值，进行实际训练参数的计算，并且将这些参数封装成类，方便传递。

3.3.1. Strategy

class Strategy @Since("1.3.0") (
    @Since("1.0.0") @BeanProperty var algo: Algo,
    @Since("1.0.0") @BeanProperty var impurity: Impurity,
    @Since("1.0.0") @BeanProperty var maxDepth: Int,
    @Since("1.2.0") @BeanProperty var numClasses: Int = 2,
    @Since("1.0.0") @BeanProperty var maxBins: Int = 32,
    @Since("1.0.0") @BeanProperty var quantileCalculationStrategy: QuantileStrategy = Sort,
    @Since("1.0.0") @BeanProperty var categoricalFeaturesInfo: Map[Int, Int] = Map[Int, Int](),
    @Since("1.2.0") @BeanProperty var minInstancesPerNode: Int = 1,
    @Since("1.2.0") @BeanProperty var minInfoGain: Double = 0.0,
    @Since("1.0.0") @BeanProperty var maxMemoryInMB: Int = 256,
    @Since("1.2.0") @BeanProperty var subsamplingRate: Double = 1,
    @Since("1.2.0") @BeanProperty var useNodeIdCache: Boolean = false,
    @Since("1.2.0") @BeanProperty var checkpointInterval: Int = 10)

• algo：classification/regression
• quantileCalculationStrategy：分位点（Split）策略，目前只支持Sort，对于连续型特征值，先把特征值进行排序，然后按次序取分位点。从代码中可以看到原来可能打算实现的MinMax和ApproxHist目前没有实现。
• minInstancesPerNode：每个树节点中最小的样本数，低于将不再对节点进行分裂，默认为1，可作为提前截止条件
• minInfoGain：最小增益，节点分裂后的增益如果小于它，将不再进行分裂，可作为提前截止条件
• subsamplingRate：样本抽样率，默认为1，每棵树都使用全部样本
• isMulticlassClassification：是否是多分类，判断条件为Classification 并且类别>2
• isMulticlassWithCategoricalFeatures：是否是带类别特征的多分类，判断条件再上面的基础上加categoricalFeaturesInfo的size大于0

3.3.2. metadata

在buildMetadata中根据strategy计算得到DecisionTreeMetadata的参数。

class DecisionTreeMetadata(
    val numFeatures: Int,
    val numExamples: Long,
    val numClasses: Int,
    val maxBins: Int,
    val featureArity: Map[Int, Int],
    val unorderedFeatures: Set[Int],
    val numBins: Array[Int],
    val impurity: Impurity,
    val quantileStrategy: QuantileStrategy,
    val maxDepth: Int,
    val minInstancesPerNode: Int,
    val minInfoGain: Double,
    val numTrees: Int,
    val numFeaturesPerNode: Int)

部分参数同Strategy，对额外参数和区别说明

• numClasses：如为Regression，设为0
• maxPossibleBins：取maxBins和样本数量中较小的；必须大于categoricalFeaturesInfo中的最大的离散特征值数
• numBins：所有特征及其特征值数，Int数组，维数是特征数，默认大小是maxPossibleBins。对于连续特征，其值就是默认值maxPossibleBins。对于离散特征，如为二分类或回归，此处将categoricalFeaturesInfo中的key特征index作为数组index，value特征个数写入数组中（这里有疑问，SVM格式的index是从1开始的，因此对numBins的index应该是categoricalFeaturesInfo的key-1，这里没有-1，当最大值等于maxBins的时候访问数组会抛异常）；如果是多分类，先计算其当做当UnorderedFeature（无序的离散特征）的bin，如果个数小于等于maxPossibleBins，会被当成UnorderedFeature，否则被当成orderedFeatures（为了防止计算指数溢出，实际是把maxPossibleBins取log与特征数比较），因为UnorderedFeature的bin是比较大，这里限制了其特征值不能太多，这里仅仅根据特征值的特殊决定是否是ordered，不太好。每个split要将所有特征值分成2部分，bin的数量也就是2*split，因此bin的个数是2*(2^(M-1)-1)
• numFeaturesPerNode：由featureSubsetStrategy决定，如果为“auto”，且为单棵树，则使用全部特征；如为多棵树，分类则是sqrt，回归为1/3；也可以自己指定，支持”all”, “sqrt”, “log2”, “onethird”。
  如果仅对RF的使用感兴趣，了解上述训练参数也就可以了，后面的文章将对其训练代码进行分析。