集成学习1——理论

所谓集成学习就是综合多人的意见来进行决策会比一个人的决策来的更好。集成学习的关键是：如何选择、生成弱分类器和如何对它们进行提升。三种思路：

将不同类型的弱分类进行提升
将相同类型但是参数不同的弱分类器进行提升
- 分类器之间依赖性不强，能够同时进行
- 并行方法，Bagging，扩展应用：随机森林Random Forest
将相同类型但是训练数据不同的弱分类器进行提升
- 分类器之间依赖性很强，只能序列生成
- 串行方法，Boosting，扩展应用：提升树AdaBoost

常见的集成学习方法有两种：Bagging和AdaBoost。

随机森林源自于Bootstrap理论（自举）：通过模拟的方法来逼近样本的概率分布。假设有包含$N$个样本的数据集$X={x_1,x_2,…,x_N}，$Bootstrap的做法：

Bootstrap是有放回的随机抽样过程

一个样本在N次采样中不始终不被采到的概率$(1-\frac1N)^N$,且有结
$$
\lim \limits_{N\to \infty}(1-\frac 1 N)^N \to \frac 1 e \approx0.368
$$
果表明：原样本中约有$\frac 1 3$的数据抽不到。

经验分布函数的数学表达式
$$
F_N(x)=\frac 1 N\sum_{i=1}^{N}I_{-\infty,x}(x_i)
$$

Bagging的全称是Bootstrap Aggregating，其思想是：

随机森林思想：

提升方法使用常用的统计学习方法。提升方法的基本思想：对于一个复杂的任务，将多个专家的判断进行适当地综合得到的判断，要比其中任何一个的结果都要好。将弱学习算法生成的弱模型，提升成和强学习算法所生成的强模型性能差不多的模型的方法。

从给定的数据集中，学习得到一系列弱分类器，组合弱分类，构成强分类器。通常进行的处理是

给定样本$T={(x_1,y_1),…,(x_N,y_N)},y_i\in {+1, -1}$，$\chi$是实例空间，$Y$是标记组合。算法过程

输入：训练数据集合T，包含实例空间和标记组合；输出：最终分类器G(x)
（1）初始化数据的权值分布：
$$
D_1=(w_{11},…,w_{1i},…,w_{1N})
$$
其中$w_{1i}=\frac{1}{N}，i=1,2,…,N$
（2）对于m=1,2,…,M
- 使用具有权值分布$D_m$的训练数据集来学习，得到基本分类器
  $$
  G_m(x):X \to {-1, +1}
  $$
- 计算$G_m(x)$在训练数据集上的分类误差率：
  $$
  e_m=\sum^N_{i=1}P(G_m(x_i)\neq y_i)=\sum w_{mi}I(G_m(x_i)\neq y_i)
  $$
- 计算$G_m(x)$的系数
  $$
  \alpha_m = \frac{1}{2}log \frac{1-e_m}{e_m}
  $$
（3）更新训练数据的权值分布
$$
D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N})
$$

$$
w_{m+1,i}=\frac {w_{mi}}{Z_m}exp(-\alpha_m y_i G_m(x_i)), i=1,2,…,N
$$
（4）$Z_m$是规范化因子
$$
Z_m=\sum^N_{i=1}w_{mi}exp(-\alpha_m y_i G_m(x_i))
$$
（5）构建基本分类器的线性组合
$$
f(x)=\sum^M_{m=1}\alpha_m G_m(x_i)
$$
（6）得到最终的分类器
$$
G(x)=sign(f(x))=sign(\sum^M_{m=1}\alpha_mG_m(x))
$$

（1）中假设数据具有均匀的权值分布，每个训练样本在基本分类器上的作用是相同的
（2）反复学习基本分类器，每轮进行$m=1,…,M$次操作
- 使用当前分布的$D_m$加权的训练数据集，学习基本分类器$G_m(x)$
- 计算基本分类器在加权训练数据集上的分类误差率
  $$
  e_m=\sum^N_{m=1}P(G_m(x_i)\neq y_i)
  $$
  
  $$
  e_m=\sum_{G_m(x_i)\neq y_i}w_{mi}
  $$
说明几点
- $w_{mi}$表示的是第m轮中第i个实例的权值，$\sum^N_{i=1}w_{mi}=1$
- 分类误差率是被$G_m(x)$误分类样本的权值之和
计算基本误分类器的系数$\alpha_m$。$\alpha$表示$G_m(x)$在最终分类器中的重要性