1.10树（tree）
1.10 树（tree）
1.10.1 决策树（Decision Tree）
首先，Mllib认为，决策树时随机森林（Random Forest）的一种特殊情况，也就是只有一棵树并且不采取特征抽样的随机森林。所以在训练决策树的时候，其实是训练随机森林，最后从随机森林中抽出一棵树。
决策树时一个数结构（可以是二叉树或非二叉树），由节点和有向边组成。决策树学习的本质是从训练数据集上归纳出一组分类规则，通常采用启发式的方法，即局部最优。具体的做法就是，在每次选择feature时，都挑选当前条件下最优的那个feature作为划分规则，即局部最优的feature。决策树学习通常分为3个步骤：特征选择、决策树生成和决策树的剪枝。
特征选择：特征选择的标准是找出局部最优的特征，判断一个特征对于当前数据集的分类效果，也就是按照这个特征进行分类后数据集是否更加有序（不同类的数据被尽量分开）。当前节点用哪个特征作为判断进行切分（也称分裂规则），取决于切分后节点数据集合中类别的有序程度，划分后的分区数越纯，那么当前分裂规则就越合适。衡量节点数据集合的有序性（纯度）有：熵、基尼和方差。
其中b是对数的底，b的取值决定信息熵的单位。
条件熵公式：
下面介绍三种衡量节点数据集合有序性的方法，分别对应三种生成决策树的算法：
信息增益（ID3算法）：
定义： 特征A对训练数据集D的信息增益g(D, A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
信息增益比（C4.5算法）：
单纯的信息增益只是个相对值，因为这依赖于H(D)的大小，所以信息增益比更能客观地反映信息增益。信息增益比的定义为：特征A对训练数据集D的信息增益比gR(D, A)定义为其信息增益g(D, A)与分裂信息熵HA(D)之比：
基尼指数（CART算法）：
定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯
即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率：
样本集合D的Gini指数：假设集合有K个类别：
决策树生成：决策树生成就是在每次需要分裂时计算每个属性的增益率，然后选择属性进行分裂，ID3算法生成树根据信息增益进行判断分裂，C4.5算法生成树根据信息增益比进行判断分裂，CART算法根据基尼指数进行判断分裂。生成过程如下：
输入：训练数据集D，特征集A，阈值ζ；输出：决策树T。
- 若D中所有实例属于同一个类Ck，则T为单节点树，并将类Ck作为该节点的类标记，返回T；
- 若A = ∅，则T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；
- 否则，按照特征选择算法（熵、Gini、方差等）计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
- 对第i个子节点，以Di为训练集，以A - {Ag}为特征集，递归地调用1 ~ 3，得到子树Ti，返回Ti。
决策树剪枝：决策树生成算法对于训练集是很准确的，但是这样会过拟合，所以需要通过剪枝（简化过程）来提高泛化能力。剪枝的思路很简单，就是在决策树对训练数据的预测误差和树复杂度之间找到一个平衡。
预测误差就是所有叶节点的经验熵的和，树复杂度与调节参数α负相关，α越大表示选择的树越简单。所以，剪枝的标准就是极小化损失函数：Cα(T) = C(T) + α|T|。树的剪枝的算法就是从叶节点往上回溯，比较剪掉该叶节点前后的损失函数的值。如果剪掉该叶节点后，损失函数更小就剪掉，具体流程如下：
输入：生成算法产生的整个树T，参数α；输出：修剪后的子树Tα。
- 计算每个节点的经验熵。
- 递归地从树的叶节点向上回溯。
设一组叶节点回溯到其父节点之前与之后的整体树分别为TB和TA，其对应的损失函数值分别是Cα(TA)和Cα(TB)。如果Cα(TA)≤Cα(TB)，则进行剪枝，即将父节点变为新的叶节点。
- 返回2，直至不能继续为止，最终得到损失函数最小的子树Tα.
1.10.2 梯度上升树（Gradient Boosted Tree）
集成算法是将其他基础模型进行组合的一种算法。Spark.MLlib支持两种主要的集成算法：Gradient Boosted Tree和Random Forest，二者都使用决策树作为基础模型。但训练过程是不同的：
- GBT一次训练一棵树，因此它们比随机森林需要更长时间的训练。 随机森林可以并行训练多棵树。另一方面，使用具有GBT训练较小（较浅）树比使用随机森林更有优势，并且训练较小树需要的时间更短。
- 随机森林可能不太容易过度拟合。在随机森林中训练更多树可以降低过拟合的可能性，但是使用GBT训练更多树会增加过拟合的可能性。（在统计语言中，随机森林通过使用更多树来减少方差，而GBT通过使用更多树来减少偏差。）
- 随机森林更容易调整，因为性能随树数量增加而改善（对于GBT来说，如果树木数量增长太大，性能可能会开始降低）。
简而言之，应基于特定数据集来选择合适的算法。
梯度提升树（GBT）是决策树的集成算法。GBT迭代地训练决策树以最小化损失函数。与决策树一样，GBT处理分类特征，扩展到多类分类设置，不需要特征缩放，并且能够捕获非线性和特征交互。spark.mllib支持使用连续和分类特征进行二分类和回归的GBT。spark.mllib使用现有的决策树实现来实现GBT。
注意：GBT尚不支持多类分类。 对于多类问题，请使用决策树或随机森林。
梯度提升迭代地训练一系列决策树。在每次迭代时，算法使用当前集合来预测每个训练实例的标签，然后将预测与真实标签进行比较。重新标记数据集以更加重视预测较差的训练实例。因此，在下一次迭代中，决策树将帮助纠正先前的错误。重新标记实例的具体机制由损失函数定义。 每次迭代，GBT进一步减少训练数据的这种损失函数。损失函数如下：
N=实例数。 yi =实例i的标签。 xi=实例i的特征。 F（xi）=模型的预测标签。
1.10.3 随机森林（Random Forest）
随机森林是机器学习模型中用于分类和回归的最成功的模型之一。通过组合大量的决策树来降低过拟合的风险。与决策树一样，随机森林处理分类特征，扩展到多类分类设置，不需要特征缩放，并且能够捕获非线性和特征交互。
spark.mllib支持使用连续和分类特征的二分类和多类分类以及回归的随机森林。spark.mllib使用现有的决策树实现随机森林。随机森林分别训练一组决策树，因此训练可以并行完成。该算法将随机性注入训练过程，以使每个决策树略有不同。结合每棵树的预测可以减少预测的方差，提高测试数据的性能。
1）训练
注入训练过程的随机性包括：
在每次迭代时对原始数据集进行二次采样，以获得不同的训练集（例如，bootstrapping）。
考虑在每个树节点处分割的不同随机特征子集。
除了这些随机化之外，决策树训练的方式与单个决策树的方式相同。
2）预测
要对新实例进行预测，随机森林必须整合各个决策树的预测。对于分类和回归，这种整合的方式不同。
分类：多数票原则。 每棵树的预测都算作一个类的投票。预计该标签是获得最多选票的类别。
回归：平均。 每棵树预测一个真实的值。 预测标签是各个树预测的平均值。
1.10.4 待定
tree.impurity包内熵（Entropy）、基尼（Gini）、不纯度（Impurities）、方差（Variance）用于求有序度的方法。
1.10.5 待定
tree.loss包内绝对误差（Absolute Error）、对数损失函数（Log Loss）、平方误差（Squared Error）用于求损失函数的方法。