名称（Tree-Based methods）的由来：
Since the set of splitting rules used to segment the predictor space can be summarized in a tree, these types of approaches are known as decision tree methods.
对于线性问题，树方法的解释性（什么叫模型的可解释性？解释性与模型的哪一个性质一般要做 trade-off？）非常好，但不如增强型线性回归预测精度高，例如第6章的 Ridge regression, LASSO，第7章的多项式和样条回归，（它们如何增强线性模型的预测准确性？）， 为了提高预测精度，在基本树方法的基础上又发展出 bagging ,random forest, boosting， 以牺牲解释性（和增加计算成本）为代价，提升预测精度。
本节首先介绍回归树，然后介绍分类树。
设一个回归树叶子节点的父节点到根节点依次是 \(A, B, C\)，则这个叶子节点的限定条件是： \(A \cap B \cap C\)，例如：\(age > 35 \cap sex = female \cap height < 175\).
图8-1：决策树从上至下解读，越上面的节点重要性（影响程度）越高。
图8-2：决策树的解释性优点。
相关概念：
terminal nodes, leaf;
internal node;
branch;
计算过程：
在 \(p\) 维空间上将所有训练观测点分割为 \(J\) 个盒子 (box);
每个盒子内观测点的预测值是此盒子内所有训练观测点相应变量的平均值。
找到让 RSS，即式 (8-1) 最小的分割方法。
确定分割方法后，取每个盒子内训练数据响应变量平均值作为测试数据的预测值；
实现算法 recursive binary splitting：
top-down: 一次确定一个分割特征；
greedy: 只考虑本次分割最优解；
一次分割过程：
在第1个特征 \(X_1\) 的值域内移动分割线 \(s\)，得到式 (8.3) 最小值 \(RSS_1\) 和对应的 \(s\)；
在第 j (\(j \in 2 .. p\)) 个特征 \(X_j\) 做同样的操作；
取 \(RSS_j\) 最小值作为本次分割的最佳 \((j, s)\) 组合；
第次分割后，在新生成的盒子中重复上述过程（是否能只选择其中一个盒子？）， 直到满足某个停止准则，例如每个分区内的观测点数都小于5。
式 (8.4) 的含义：每个盒子 (\(\sum^{|T|}_{m=1}\)) 内的 RSS值 (\(\sum_{x_i \in R_m}\)) 之和。 注意式 (8.4) 与 LASSO 的相似之处。
当所有观测不做任何划分时， 式 (8.1) 的值是 \(\sum_{i = 1}^n (y_i - \bar y) ^2\)； 当为每个观测划分一个box（整个树包含 \(n\) 个box）时， 式 (8.1) 的值为0（因为此box里的平均值就是自己）。
这二者之间，从没有划分的原始状态开始每次 split box，式 (8.1) 会有一定的下降，但 \(T_0\) 上叶子节点的 式 (8.4) 的值会高于中间分叉上响应的值，也就是式 (8.4) 的最小值会出现在某个中间节点上，此分叉点的子节点就被修剪掉了（因为子节点的式(8.4)值大于它们父节点的值）。
按照式 (8.2) 和 (8.3) 所述过程生成最大回归树 \(T_0\)，直到所有节点包含的观测数小于某个阈值时停止；
对 \(T_0\) 的每个子树，设式 (8.4) 的值为 \(RN\)，得到函数 \(RN = f(\alpha)\)（ 下面 子树示例 一节给出了包含3棵子树的例子）；
将上面确定的 \(\alpha\) 值，根据第2步中最小 \(RN\) 对应的子树作为最终结果。
问题： 下面关于步骤1生成 \(T_0\) 树的论述哪个正确？ 假设对所有训练数据进行第一次分割后生成了 \(R_1\) 和 \(R_2\) 两个盒子，现在要做第二次分割，生成 \(R_{11}\), \(R_{12}\), \(R_{21}\) 和 \(R_{22}\) 四个盒子。
A: 由于新节点只会在层数最深的节点上出现，在树的生长过程中，浅层节点中的观测数量不变，所以用“观测数小于阈值”作为算法停止的标准，可能导致算法无法结束，应该用 information gain 是否大于零作为迭代终止条件。
B: 由于 \(R1\) 和 \(R2\) 中的观测点数不同，对比 \(RSS_{R11} + RSS_{R12}\) 和 \(RSS_{R21} + RSS_{R22}\) 是没有意义的，所以任何一个盒子都可以继续分割，新节点可以出现在任何一个叶子节点上，使用最小观测点数是合理的迭代终止条件。
在回归树的生成过程中，\(\alpha\) 通过改变 \(RN\) 的值生成不同的子树，不（直接）参与此子树的 test MSE 的计算。
回归树的Python实现参考 treepredict.py。
假设回归树 \(T_0\) 包含了3棵子树，其残差 \(\sum_{m=1}^{\vert T \vert} \sum_{i: x_i \in R_m} (y_i - \hat y_{R_m}) ^ 2\) 分别为 \(R_1, \, R_2, \, R_3\)，包含的分区（box）数 \(\vert T \vert\) 分别为：3, 5, 12： \[ RN_1 = R_1 + 3 \alpha \\ RN_2 = R_2 + 5 \alpha \\ RN_3 = R_3 + 12 \alpha \]
绘制函数图像：
alpha <- seq(0, 0.8, by = 0.2)
R1 <- 5.7
R2 <- 4.6
R3 <- 2.8
RN1 <- R1 + 3 * alpha
RN2 <- R2 + 5 * alpha
RN3 <- R3 + 12 * alpha
plot(alpha, RN1, type = 'l', col = 'red', xlab = expression(alpha), ylab = 'RN', ylim = c(3, 8))
lines(alpha, RN2, col = 'blue')
lines(alpha, RN3, col = 'green')
legend('bottomright', legend = c('subtree1', 'subtree2', 'subtree3'),
lty = c(1, 1, 1), col = c('red', 'blue', 'green'))可以看到随着 \(\alpha\) 的增加，\(RN\) 最小的线依次是 subtree3, subtree2 和 subtree1， 叶子节点多的子树 subtree3 \(RN\) 上升速度最快。
对于图 8.5，首先将 Hitters 数据集随机分为两部分，其中训练集 \(S1\) 包含132个观测，测试集 \(S2\) 包含131个观测。 再将 \(S1\) 分为6份用来做 cross-validation，其中训练集 \(S3\) 包含110个观测，测试集 \(S4\) 包含22个观测，且 \(S1 = S3 \cup S4\)。 图上的3条曲线中，绿色线表示在 \(S4\) 上计算得到的 test MSE，橙色线表示在 \(S2\) 上计算得到的 test MSE，黑色线表示在 \(S1\) 上计算得到的 training MSE.
随着 \(\alpha\) 的增加，\(\vert T \vert\)不断降低，所以图 8.5 的横轴也是 \(\alpha\) 不断减小到0的过程。
分类场景中起 RSS 作用的是分类错误率 \(E\)，定义见式 (8.5)， 其中 \(\hat p_{mk}\) 表示第 m 个叶子节点中属于第 \(k\) 个分类的观测数与 \(m\) 中所有观测数的比值，例如某棵树第 3 个节点中的 \(Y\) 包含6个值：4, 5, 2, 4, 5, 5，则 \(\hat y_{31} = 2/6\)，即观测值 4 的个数（2个）与总观测数（6个）的比值，类似有 \(\hat p_{32} = 3/6, \; \hat p_{33} = 1/6\)。 所以 \(max_k (\hat p_{mk})\) 是最大成分（most commonly occurring class）所占比例数，上例中是观测值 5 对应的比例 \(\hat p_{32}\)，采用主要成分作为节点预测值规则，错误率（classification error）就是除最大成份外，其他全是错的。
Gini index 和 cross-entropy 表征某个节点的 purity，当节点中主体成分所占比重越高（越纯粹），这两个值越小。
Programming Collective Intelligence by Toby Segaran, chapter 7, section Entropy 中熵值的计算函数使用 log2() 代替了本书式 (8.7) 中的自然对数，其他部分相同（改写自 treepredict.py）：
def uniquecounts(rows):
"""Create a count dictonary
>>> uniquecounts([[0, 1], [0, 1], [3, 1], [1, 1]])
{1: 4}
>>> uniquecounts([[0, 1], [0, 2], [3, 1], [1, 2]])
{1: 2, 2: 2}
>>> uniquecounts([[0, 1], [0, 2], [3, 2], [1, 2]])
{1: 1, 2: 3}
>>> uniquecounts([[0, 1], [0, 2], [3, 3], [1, 4]])
{1: 1, 2: 1, 3: 1, 4: 1}
"""
results = {}
for row in rows:
# The result is the last column
r = row[len(row) - 1]
if r not in results:
results[r] = 0
results[r] += 1
return results
def entropy(rows):
"""Sum of p(x)log(p(x)) of all values in a dict
>>> entropy([[0, 1], [0, 1], [3, 1], [1, 1]])
0.0
>>> entropy([[0, 1], [0, 2], [3, 1], [1, 2]])
1.0
>>> entropy([[0, 1], [0, 2], [3, 2], [1, 2]])
0.8112781244591328
>>> entropy([[0, 1], [0, 2], [3, 3], [1, 4]])
2.0
"""
from math import log
def log2(x): return log(x) / log(2)
results = uniquecounts(rows)
ent = 0.0
for r in results.keys():
p = float(results[r]) / len(rows)
ent = ent - p * log2(p)
return ent
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)从docstring可知，entropy()的输入是一张二维表，计算此表最后一列（即响应变量\(Y\)）的熵值，式 (8.7) 中的 \(\hat p_{mk}\) 就是此值出现的次数与整个样本的个数的比值。\(Y\) 内部的值越多，entropy越高，比如例1完全一致，熵值最小（0），例2只有1和2两个取值，熵值为1，例4有1,2,3,4共4种取值时，熵值为2，不难算出，当 \(Y\) 包含 \(2^k\) 个取值，且每个取值出现的次数一样 时（也就是平均分布，如例1，2和4），熵值为 \(k\)；当取值的个数相同，但分布不均匀，如例3的 \(Y\) 包含1个1和3个2，熵值介于二值平均分布和单一值之间（\(0 \lt 0.8112 \lt 1.0\)），这也符合熵值的定义。
Gini index, cross-entropy 和分类错误率都可以在分类场景中作为评价分割质量的指标，前两个对节点纯度更敏感。 三者都可以作为修剪树的方法，当以预测精度为目标修剪时，分类错误率效果最好。
分类树特点：
使用树方法还是线性模型取决于实际问题中特征与响应变量的关系，见图 8.7。
优点：
解释性好；
符合人类直觉；
可以图示；
方便地处理分类特征值；
缺点：预测精度差。
原始树方法 variance 很高（具体何种表现？）
Bagging 基本思路：多个独立同分布的随即变量，取平均值可以显著降低方差。
Bagging tree 方法：对训练数据集做 \(B\) 次bootstrap，生成 \(B\) 个模型，综合考虑所有模型的预测值，作为最终预测结果。
回归问题：取平均值；
分类问题：majority vote（绝对多数）；
OOB: \(B\) 次 bootstrap 抽样中都没有被选中的观测；
对于某一个观测，一次 bootstrap 抽样大约覆盖 2/3 的样本（参考文献1），所以一次抽样中作为测试数据（未被抽中）的概率是 1/3， \(B\) 次抽样后，有 \(\frac{B}3\) 的模型将此观测作为测试数据，得到 \(\frac{B}3\) 个观测结果， 最终 OOB 预测结果是这些观测值的平均值（回归问题）或者绝对多数值（分类问题）。
为什么 OOB 比 原始 Bagging 精度高？
Bagging 使用所有 \(B\) 个模型对某个观测的预测平均值作为此观测的最终预测值， 其中2/3的模型中此观测是训练数据，预测正确率是100%，所以大幅增加了整体的过拟合倾向。 二者的分类错误率对比见图8.8。
Bagging 方法以牺牲解释性为代价提升预测精度，但仍然有办法表征各个特征的重要性。 具体实现方法： 给定一个特征 \(f\)，取每个模型对此特征分割引起的 RSS（回归问题）或者 Gini index（分类问题） 下降幅度的总和 \(RSS_f\)，再对 \(B\) 个模型所有 \(RSS_f\) 取平均值， 此值越大，说明特征 \(f\) 越重要（对响应变量影响越大），见图8.9。
每个分割只能在随机选取的 \(m\) 个特征中选择，以降低不同模型间的耦合性。 当 \(m=p\) 时，随机森林等价于 Bagging 方法，二者错误率对比见图8.8。 通常 \(m\) 取 \(\sqrt p\)。
随机森林在特征间存在关联时表现良好（线性回归是否有这个特点？）， 图8.10：对比随机森林和 Bagging 方法在500个基因表达、15个分类级别（正常，以及癌症 1 ~ 14 级） 上的分类错误率，前者略微优于后者，但都显著优于单个分类树（45.7%）。 此场景中响应变量为“正常”（主导级别）占比75.4%， 如果一个分类方法的错误率接近甚至超过此百分比，则无存在价值。
Bagging/Random forrest 通过横向分隔降低模型的过拟合倾向， Bootstrap 生成的各个训练数据集之间是彼此独立的，只在最后做预测值的平均。
Boosting 方法则依次生成多棵树，后面的树依赖于前面的树，每一步只做很少几次分割， 用前面模型的残差作为后续模型的响应变量，从而找到最有效率的分割方式。 回归树的具体计算过程如下：
设置初始模型 \(\hat f(x) = 0\)，初始训练集中的响应变量：\(r_i = y_i\)；
执行 \(B\) 轮迭代，每次生成只包含少量几次分割的小型树模型 \(\hat{f^b} (x)\)， 并用它更新当前模型 \(\hat f(x)\)；
返回最终 boosting 模型 \[\hat f(x) = \sum^{B}_{b=1} \lambda \hat{f^b}(x)\]
上述过程第2步中，每轮迭代包含如下步骤：
在训练数据集 \((X, r)\) 上做 \(d\) 次分割， 生成包含 \(d + 1\) 个叶子节点的树模型 \(\hat{f^b} (x)\)；
用此模型更新原有模型：\(\hat f(x) \leftarrow \hat f(x) + \lambda \hat{f^b} (x)\)；
更新残差，作为下一轮模型的响应变量：\(r_i \leftarrow r_i - \lambda \hat{f^b}(x)\)；
Boosting 方法包含3个参数：
模型数量 \(B\)：于随机森林不同，Boosting 的 \(B\) 参数过大时会导致过拟合；
缩减系数 \(\lambda\)：一个很小的正数，控制 boosting 的“学习速度”， 一般取 \([0.01, 0.001]\)，根据问题的特征确定具体值，当 \(\lambda\) 很小时， 往往需要比较大的 \(B\) 值才能得到较好的模型；
每个模型包含的分割数 \(d\)，控制每个之间环节模型的复杂度， 一般取 \(d=1\) 会得到不错的效果，这时每个模型只做一次分割，得到一个“树桩”模型 (stump)， 最终模型相当于一个累加模型。 \(d\) 还表征了模型的交互程度的高低（为什么？）
图8.11说明了不同 \(d\) 参数的 boosting 模型于随机森林模型在癌症预测数据集上分类错误率的对比， 可以看到 \(d=1\) 模型略好于 \(d=2\) 模型，二者明显优于随机森林模型。
Boosting 方法为什么有这样优异的表现？
将一个静态的分类问题转换为一个动态的搜索问题。
搜索目标是什么？
RSS。