本文为senlie原创，转载请保留此地址：http://www.cnblogs.com/senlie/

决策树
---------------------------------------------------------------------
1.描述：
以树为基础的方法可以用于回归和分类。
树的节点将要预测的空间划分为一系列简单域
划分预测空间的规则可以被建模为一棵树，所以这种方法也叫决策树方法
bagging，随机森林，boosting 是多棵决策树组合起来采用投票方式产生一个预测结果的方法
机制来产生预测结果

2.如何选特征：
回归树：RMSE(Root Mean Square Error)
分类树：信息增益、基尼系数

3.回归树：
RMSE ：
假设一个集合被划分为 M 部分，$c_m$ 表示第 m 部分的值，则预测值为
$$f(x) = \sum_{m = 1}{M}{c_m I(x \in R_m)}$$
$\hat{y}_{m}$是 $R_m 子$集的平均值
$$RMSE = \sum_{j = 1}^J\sum_{i \in R_j}{(y_i - \hat{y}_{R_j})^2}$$
其中 $\hat{y}_{R_j} $是落入 $R_j$的样本的平均值
建树的过程是一种自顶向下的贪心的递归二分划分方法。
自顶向下：从树的根开始不断地将预测空间划分为两个子空间
贪心：每次划分都选择当前最优的方法，而不选择那些可能在将来会导致更好划分的方法
建树的过程：
1).选择最优切分变量 j 与切分点 s。遍历变量 j，对固定的切分变量 j 扫描切分点 s ，
选择使 RMSE 达到最小值的对(j, s)
2).用选定的对(j, s) 切分区域 R1 和 R2 并决定相应的输出值 c1 和 c2
$$R_1(j, s) = \{X | X_j \le s\} , R_2(j, s) = \{X | X_j > s\}$$
$$c_1 = ave(y_i | x_i \in R_1(j, s)) , c_2 = ave(y_i | x_i \in R_2(j, s))$$
3).继续对两个子区域调用步骤1)、2)，直到满足停止条件

4.分类树：

4.1信息增益：
X的熵 $H(X) = -p_1\log p_1 - p_2\log p_2 -\cdots - p_n\log p_n = -\sum_{i=1}^n{p_i\log p_i}$
熵表示了信息的不确定性(也即混乱性)，熵越大，信息越混乱，越难预测。
比如，
如果变量 X 服从统一分布的，由于 X 的各个值出现的概率一样，很难预测 X 的值，所以 X 的熵很大
如果变量 X 的概率分布图是类似山峰形状的，在某几个点的概率很大，那么预测 X 的值为那几个点中的某一个命中的概率就很大，所以 X 的熵很小
某一具体条件熵-->在 X 的值为 v 的条件下，Y 的信息熵
$$H(Y|X = v)$$
条件熵
$$H(Y|X) = \sum_i{p(X=v_i)H(Y|X=v_i)}$$
信息增益-->如果按照某个特征划分数据，那么信息不确定性能减少多少
$$IG(Y|X) = H(Y) - H(Y|X)$$
选择信息增益最大的特征来划分数据

示例：

解释左图的计算方法，右图类似
-(9/14 * log(9/14) + 5/14 * log(5/14)) = 0.940
-(3/7 * log(3/7) + 4/7 * log(4/7)) = 0.985
-(6/7 * log(6/7) + 1/7 * log(1/7)) = 0.592
I(S|Income) --> 表示数据集合 S 按照 Income 特征划分为子集后信息不确定性减少量
= 0.940 - (7/14)*0.985 - (7/14)*0.592
= 0.151
上面的示例中因为选择特征 Income 来划分集合的信息增益最大，所以应该选择 Income

4.2基尼系数：
假充集合 T 包含 N 个类别，第 j 个类别的概率是 $P_j$，则这个集合的基尼系数为
$$Gini(T) = -\sum_{i=1}^n{p_i\log p_i}$$
按某个特征划分为 m 个子集，第 i 个子集的大小为 $N_i$，则划分后子集的基尼系数为
$$Gini_{split}(T) = \frac{N_1}{N}Gini(T_1) + \cdots + \frac{N_m}{N}$$
选择能使划分后基尼系数最小的特征来划分当前集合

建树的过程：
1).选择一个"最好"的特征A来划分节点
2).对于特征A的每一个值，创建出一个分支来划分样本
3).重复步骤1)，2)直到信息增益或基尼系数足够小

5.剪枝
todo

Bagging
------------------------------------------------------------------
算法过程：
1).从训练集中采样得到新的训练集
2).重复步骤1 B次得到B个新的训练集，针对B个不同的训练集分别训练一棵树
3).平均每一棵树的预测值或采用少数服从多数得到分类结果
$$\hat{f}_{bag} = \frac{1}{B} \sum_{b=1}^B \hat{f}^b(x)$$

Out-of-Bag Error Estimation：
可以采用步骤1过程中没有采样到的数据作为对应训练集生成的树的测试集评估训练结果

Random Forests
-------------------------------------------------------------------
算法过程：
1).从训练集中采样得到新的训练集
2).重复步骤1 B次得到B个新的训练集，针对B个不同的训练集分别训练一棵树
3).训练树的过程中，先从所有特征中随机选择 m 个特征作为候选，然后再从
这 m 个特征中选择最优的一个来划分预测空间

比较：
Bagging : m = p
Random Forests : m = $\lfloor{\sqrt{p}}\rfloor$ (分类) ， m = $\lfloor{p/3}\rfloor$ (回归)
p 为所有特征数

Boosting
------------------------------------------------------------------
回归问题算法过程：
1).设初值，设预测值 $\hat{f}(x) = 0 $， 对于训练集里的每一个样本，设残差 $r_i = y_i$
2). 对于 b = 1,2,...,B,重复以下步骤：
2.1) 对于训练集(X, r)，分裂 d 次生成一棵树 $\hat{f}^b$ --> (注意是训练集(X,r)，不是(X,y))
2.2) 用一个收缩系统 $\lambda$ 更新 $\hat{f}$ ：$\hat{f} = \hat{f} + \lambda\hat{f}^b(x)$
2.3) 更新残差： $r_i = r_i - \lambda\hat{f}^b(x_i)$
3).输出 boosted 了的模型： $\hat{f}(x)$

调节参数：
1).树的数量 B。如果 B 太大容易 overfitting
2).收缩参数 $\lambda $。这个参数控制 boosting 的学习率
3).每棵树分裂的次数 d。 这个参数控制 boosted 集成模型的复杂度。一般 d 选择 1，即生成的决策树是树桩

分类问题算法过程：

1).W(x) 是 N 个训练样本的权重分布。 $\sum{W(x_i)} = 1$
2）.初始化。对于所有样本 x ，设置其权重 W(x) 为 1/N
3）.在每一次迭代 k ：
3.1） 用权重 $W_k(x)$ 生成最优的弱分类器 $C_k(x)$
3.2） 计算错误率
$\epsilon_k$  
3.3） 计算分类器的权重
$\alpha_k$ 
3.4） 更新样本权重
$W_{k+1}(x_i)$ 
4）.最终的分类器 ： $C_{Final}(x) = sign(\sum{a_i C_i(x)})$
示例：

比较：
Bagging： 树"并行"生成
Boosting：树"串行"生成

GBDT
-----------------------------------------------------------------
boosting 是一种算法思路，它的基函数可以采用各种分类器、预测器。其中采用
决策树为基函数的 boosting 就叫 GBDT，即 Gradient Boosting Decision Tree。

使用 MPI 并行化随机森林算法
-----------------------------------------------------------------

算法过程：
输入：训练数据集 D ，建树数目 N ，进程数目 n
输出：N 棵决策树 *T
1).分配要生成 N/n 棵决策树的任务给每个进程，如果该进程为最后一个进行，则它要生产的
决策树的数目为 N/n * (1 - n) + N;
2).对于每个进程，使用随机森林算法生成 N/n (或N/n * (1 - n) + N)棵树组成的森林
3).当生成完随机森林，若该进程为从进程则发送已经生成好了的随机森林参数给主进程；若该进程
为主进程则接收其他进程传过来的随机森林参数，并合并要一个决策树数组 T
4).主进程将 N 棵决策树组成的随机森林模型参数存储起来。

Q&A：
??随机森林算法和 Adaboost 哪个比较容易过拟合
随机森林算法比较容易过拟合。
1.随机森林的决策树尝试拟合数据集，有潜在的过拟合问题，
而 boosting 的决策树则是拟合数据集的残差，然后更新残差，由新的决策树
再去拟合新的残差。这虽然学得慢，但大大地降低了过拟合的风险
2.boosting 的每棵决策树通常都很小，一般分裂次数只有 1，生成的决策树一般是树桩
3.通过收缩参数，可以放慢拟合的速度，允许更多不同的树来拟合残差。不同的树带来的是多样性，
也降低了过拟合的风险

参考：

------------------------------------------------------------------