决策树
非形式化地，决策树（这里考虑的是二叉决策树）是一棵二叉树，每个内部节点对应一个对数据集某一维度的划分规则，叶子节点则对应一个具体的输出值。如果树只有一个输出规则，那么这棵树称为决策树桩 (decision stump)
决策树一般的学习策略是一种自顶向下的贪心算法：从一个包含了所有数据的叶子节点开始，循环
- 寻找一个叶子节点进行分裂，使得该分裂能够最大限度地减少不确定性
- 指定具体的分裂规则
直到算法终止
对于回归决策树，对样本空间中的\(M\)个区域\(R_1, \ldots, R_M\)，预测函数是 \[ f(x) = \sum_{m=1}^M c_m 1\{x \in R_m\} \] 其中\(c_m\)是对区域\(R_m\)中所有点的计算方法。我们的目标是最小化 \(\sum_i (y_i - f(x_i))^2\)。这里我们采用的\(c_m\)是求该区域内所有点\(x_i \in R_m\)所对应的的响应变量\(y_i\)的均值。因此核心问题是如何找到划分区域。假设我们要在维度\(j\)在值\(s\)对\(R\)进行划分，定义 \[ R^-(j, s) = \{x_i \in R|x_i(j) \le s\}, R^+(j,s) = \{x_i \in R|x_i(j) > s\} \] 那么可以对每个\(j\)计算一个最好的划分点\(s\)。对每个区域重复上面的过程，选择一个对损失函数减小最大的区域+维度进行划分
对于分类决策树，对所有\(x \in R_m\)，令\(p_k\)为这些点中类别为\(k\)的点所占的比例，则可以有三种方法度量\(R_m\)
- 分类误差 $ 1- _kp_k$
- 基尼系数 (Gini index) $ 1- _k p_k^2$
- 熵 \(-\sum_k p_k \ln p_k\)
这些值都在对所有\(k \in K\)满足\(p_k\)是均匀分布时取到最大，在对某个\(k\)，\(p_k=1\)时取得最小
以基尼系数为例，对\(R_m\)，假设划分以后得到\(R_m^-\)和\(R_m^+\)，需要考察划分以后降低了多少基尼系数，即计算 \[ u(R_m) - \left(p_{R_m^-} \cdot u(R_m^-) + p_{R_m^+} \cdot u(R_m^+)\right) \] 其中
- \(u(R_m)\)是原始区域的基尼系数
- \(p_{R_m^+}\)是划分以后落入到\(R_m^+\)的点的比例
- \(u(R_m^+)\)是\(R_m^+\)这一新区域的基尼系数
分隔的维度需要能最大化这个差值
Bootstrap、Bagging与随机森林
Bootstrap通俗讲就是有放回的抽样（重采样）。假设要对数据集\(x_1, \ldots, x_n\)的某个统计量\(S\)做估计\(\hat{S}\)，其大致算法为：
- 生成bootstrap样本集\(\mathcal{B}_1, \ldots, \mathcal{B}_B\)。每个样本集\(\mathcal{B}_b\)通过从原始样本有放回随机采样\(n\)次生成。因此任意数据点\(x_i\)都可以在\(\mathcal{B}_b\)中出现多次，也有可能不出现
- 对每个\(\mathcal{B}_b\)，把它当做完整数据集，计算估计值，即\(\hat{S}_b := \hat{S}(\mathcal{B}_b)\)
- 计算\(\hat{S}\)的期望和方差 \[ \mu_B = \frac{1}{B}\sum_{b=1}^B \hat{S}_b,\ \sigma^2_B = \frac{1}{B}\sum_{b=1}^B (\hat{S}_b - \mu_B)^2 \]
Bagging实际上是Bootstrap aggregation的缩写，其思路为，对所有\(b = 1, \ldots, B\)
- 从训练集生成大小为\(n\)的bootstrap样本集\(\mathcal{B}_b\)
- 在\(\mathcal{B}_b\)上训练分类/回归模型\(f_b\)
- 对新的数据\(x_0\)，计算 \[ f_{\rm avg}(x_0) = \frac{1}{B}\sum_{b=1}^B f_b(x_0) \] 对于回归模型，\(f_{\rm avg}(x_0)\)是预测结果；对于分类问题，\(f_{\rm avg}(x_0)\)可以看做是对\(B\)张投票的计票，少数服从多数
Bagging中每个分类器实际上效果都比较平庸，但是组合起来整体效果不错。当\(X\)和\(y\)之间是非线性关系时，效果能尤其得到改进。但是学到的树之间都高度相关，所以当树的数量增长到一定程度以后，再加树效果不明显。随机森林做的进一步修改试图减少这种相关性：每次分裂节点的时候只考虑所有维度中的一个子集。即算法会多用到一个输入变量\(m, m<d\)（通常\(m\approx \sqrt{d}\)）。对所有\(b=1,\ldots, B\)
- 从训练集生成大小为\(n\)的bootstrap样本集\(\mathcal{B}_b\)
- 在\(\mathcal{B}_b\)上训练分类器。但是在分裂时，只随机选择\(m\)个维度（这\(m\)个维度对每个\(b\)都是重新选择的）。然后在这个子集上做最优选择
