决策树（Decision Trees）

Question

在机器学习算法中决策树和它的集成方法（随机森林,GBDT）都是很流行的分类和回归方法。决策树在很多任务上表现出的性能很好，相对容易解释和理解，可以处理类属或者数值特征，同时不要求数据归一化或标准化。决策树非常适用集成方法（ensemble method）,比如多个决策树的集成，称为决策树森林。

算法基础

决策树是一种贪婪算法，通过递归二分类特征空间。为了在下一个子树获得最大信息增益，每个分区都尽可能地选择最佳分裂点。换句话讲对于数据集 D 我们要找到一个分隔点 s 使得信息增益$\underset{s}{\operatorname{argmax}} IG(D,s)$最大。

节点混乱度（impurity）和信息增益（information gain）

节点点混乱度是衡量节点上标签点均匀度。目前 MLlib 提供了两种度量分类混乱度的方法(Gini impurity and entropy) 和一种回归混乱度的度量的方法（variance）。

Impurity	Task	Formula	Description
Gini impurity	Classification	$\sum_{i=1}^{C} f_i(1-f_i)$	$f_i$is the frequency of label ii at a node and CC is the number of unique labels.
Entropy	Classification	$\sum_{i=1}^{C} -f_ilog_2(f_i)$	$f_i$ is the frequency of label ii at a node and CC is the number of unique labels.(对于单个分类的 impurity $l(x_i)=-log_2(f_i)$,其实就是二叉树的深度（所以底数为 2）,也就是说树的越深混乱度越小（极端情况下深度为 0 也就没有分类的情况下混乱度是最大的） )
Variance	Regression	$\frac{1}{N} \sum_{i=1}^{N} (y_i - \mu)^2$	$y_i$is label for an instance, NN is the number of instances and μμ is the mean given by $\frac{1}{N} \sum_{i=1}^N y_i$
信息增益是父节点和两个子节点混乱度加权总和的差异。假设分割点 s 将大小为 N 的数据集 D 分割成两部分$D_{left}$和$D_{right}$大小分别为$N_{left}$和$N_{right}$,所以信息增益有：
$IG(D,s) = Impurity(D) - \frac{N_{left}}{N} Impurity(D_{left}) - \frac{N_{right}}{N} Impurity(D_{right})$

分割点的选择（Split candidates）

连续型特征（Continuous features）

对于在单机实现中的小数据集，每个连续特征的分割候选通常是特征的唯一值。一些实现对特征值进行排序，然后使用排序的唯一值作为更快的树计算的分割候选。 对于大型分布式数据集的排序特征值是昂贵的。实现计算的方式是通过设置分割点通过数据采样的分位数计算。有序分割点创建“bins”最大 bins 可以通过 maxBins 参数设置。

类别型特征（Categorical features）

一个分类特征有 M 种可能的值那么我们可能要进行$2^{M-1}-1$次的分割候选。

停止规则（Stopping rule）

当满足下列条件之一时，递归树的构建在节点上停止：
1) 节点的深度等于 maxDepth 训练参数。
2) 分裂的候选没有信息增益大于 mininfogain。
3) 没有分割点产生的子节点使得最小的 minInstancesPerNode 训练实例。

参数说明

详细解释参数的用途去调整参数值根据不同的问题。

• algo: Classification or Regression
• numClasses: Number of classes (for Classification only)
• categoricalFeaturesInfo: 指定每个分类有多少个特征值，通过 map 方式建立 特征->特征值 的索引。
  。比如 Map(0->2,4->10) 表示 特征 0 是一个二分类（取 0 或 1） 特征 4 有十个分类（特征值｛0，1，……，9｝）。注意索引是从 0 开始的也就 0 对于的是第一个元素，4 对应的是第五个元素。 。如果不设置 categoricalFeaturesInf 的值那么算法还是会继续运行并得出合理的解，但是，为了让性能更好我们应该制定它的值。

停止标准（Stopping criteria）

下面这些决定了树停止生长（产生新节点），调整这些参数去避免在测试集上过度拟合。

• maxDepth: 树的最大深度，深的树是更有表现力的（可能会有更高的精度），但是它们更需要昂贵的训练并且容易过度拟合。
• mininstancespernode：一个节点进一步分裂后每个字节点最小的训练样本个数。这经常用于随机森林训练比个体更深的树
• minInfoGain: 一个节点进一步分裂分裂后的信息增益值。

可调参数（Tunable parameters）

调节这些参数可以尽可能的避免过度拟合。

• maxBins:Number of bins used when discretizing continuous features.
  。Increasing maxBins allows the algorithm to consider more split candidates and make fine-grained split decisions. However, it also increases computation and communication.
  。Note that the maxBins parameter must be at least the maximum number of categories MM for any categorical feature.
• maxMemoryInMB: 设置决策树最大的内存，默认情况下是 256 MB
• subsamplingRate: Fraction of the training data used for learning the decision tree. This parameter is most relevant for training ensembles of trees (using RandomForest and GradientBoostedTrees), where it can be useful to subsample the original data. For training a single decision tree, this parameter is less useful since the number of training instances is generally not the main constraint.
• Impurity:墒用于计算分割阀值。

val PATH = "file:///Users/lzz/work/SparkML/"
import org.apache.spark.mllib.tree.DecisionTree
import org.apache.spark.mllib.tree.model.DecisionTreeModel
import org.apache.spark.mllib.util.MLUtils

// Load and parse the data file.
val data = MLUtils.loadLibSVMFile(sc, PATH+"data/mllib/sample\_libsvm\_data.txt")
// Split the data into training and test sets (30% held out for testing)
val splits = data.randomSplit(Array(0.7, 0.3))
val (trainingData, testData) = (splits(0), splits(1))

// Train a DecisionTree model.
//  Empty categoricalFeaturesInfo indicates all features are continuous.
val numClasses = 2
val categoricalFeaturesInfo = Map[Int, Int]()
val impurity = "gini"
val maxDepth = 5
val maxBins = 32

val model = DecisionTree.trainClassifier(trainingData, numClasses, categoricalFeaturesInfo,
  impurity, maxDepth, maxBins)

// Evaluate model on test instances and compute test error
val labelAndPreds = testData.map { point =>
  val prediction = model.predict(point.features)
  (point.label, prediction)
}
val testErr = labelAndPreds.filter(r => r.\_1 != r.\_2).count.toDouble / testData.count()
println("Test Error = " + testErr)
println("Learned classification tree model:\n" + model.toDebugString)

// Save and load model
model.save(sc, "myModelPath")
val sameModel = DecisionTreeModel.load(sc, "myModelPath")

Test Error = 0.08571428571428572
Learned classification tree model:
DecisionTreeModel classifier of depth 1 with 3 nodes
  If (feature 378 <= 71.0)
   Predict: 0.0
  Else (feature 378 > 71.0)
   Predict: 1.0

回归（regression）

下面这个例子演示如何加载 libsvm 数据文件，解析数据成 RDD LabeledPoint 格式然后通过计算决策树的方差作为熵（impurity）并设置决策树深度为 5.最后通过 均方根误差方法来衡量算法的拟合程度。

import org.apache.spark.mllib.tree.DecisionTree
import org.apache.spark.mllib.tree.model.DecisionTreeModel
import org.apache.spark.mllib.util.MLUtils

// Load and parse the data file.
val data = MLUtils.loadLibSVMFile(sc, PATH + "data/mllib/sample\_libsvm\_data.txt")
// Split the data into training and test sets (30% held out for testing)
val splits = data.randomSplit(Array(0.7, 0.3))
val (trainingData, testData) = (splits(0), splits(1))

// Train a DecisionTree model.
//  Empty categoricalFeaturesInfo indicates all features are continuous.
val categoricalFeaturesInfo = Map[Int, Int]()
val impurity = "variance"
val maxDepth = 5
val maxBins = 32

val model = DecisionTree.trainRegressor(trainingData, categoricalFeaturesInfo, impurity,
  maxDepth, maxBins)

// Evaluate model on test instances and compute test error
val labelsAndPredictions = testData.map { point =>
  val prediction = model.predict(point.features)
  (point.label, prediction)
}
val testMSE = labelsAndPredictions.map{ case(v, p) => math.pow((v - p), 2)}.mean()
println("Test Mean Squared Error = " + testMSE)
println("Learned regression tree model:\n" + model.toDebugString)

// Save and load model
model.save(sc, "myModelPath")
val sameModel = DecisionTreeModel.load(sc, "myModelPath")

Test Mean Squared Error = 0.05555555555555555
Learned regression tree model:
DecisionTreeModel regressor of depth 1 with 3 nodes
  If (feature 406 <= 0.0)
   Predict: 0.0
  Else (feature 406 > 0.0)
   Predict: 1.0

回归树和分类树的区别

分类树，观察值是离散变量；回归树，观察值取值是连续的。

回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个 feature 的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即（每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。

分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件（如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。