数据挖掘之Boosting&AdaBoost

大纲：

Boosting介绍

AdaBoost 算法

1. 背景知识

（1）PAC学习模型（Probability Approximately Correct）

机器学习中，训练样本再大也不可能代表某类事物本身，所以从训练样本中学习得到“规则”不能对某类事物完全适用，总有失效的情况出现，所以机器学习的目标是：概率逼近正确学习。

PAC模型中有涉及两个概念：强学习和弱学习。

（2）强学习

S：包含N个样本点，格式为（xi，yi）的数据集

其中：xn 是按照某种固定的但未知的分布D（x） 随机独立抽取的；yn = f（xn）；

f属于某个已知的布尔函数集F

强学习满足条件：（学习算法生成的模型h：其准确率必须满足一定的标准，而且其模型的生成时间还满足一定的关系 ）

任意的D，任意的f∈F，任意的 0<=ε; δ<=1/2，学习算法生成一个满足 P[h(x) ≠ f(x)] ≤ε 的估计h 的概率大于 1- δ

学习算法的运行时间与 1/ε ，1/δ成多项式关系

（3）弱学习

强学习：不容易确定，生成

弱学习：容易

（4）弱学习--》强学习

理论上可行！

核心思想：通过组合使弱学习互补。

学习是不适定问题，在有限的样本上，不同的学习方法得到不同的“规则”，并在不同的情况下失效，没有一种学习算法总是在任何领域产生最好的分类效果。

实现弱学习互补：

问题A. 怎样获得不同的弱分类器？

使用不同的弱学习算法得到不同基学习器：参数估计、非参数估计

使用相同的弱学习算法，但用不同的超参数：K-Means不同的K，神经网络不同的隐含层...

相同的输入对象的不同表示：不同的表示可以凸显事物不同的特征

使用不同的训练集

装袋 bagging

提升 boosting

问题B.怎样组合弱分类器？

多专家组合：

一种并行结构，所有的弱分类器都给出各自的预测结果，通过“组合器”把这些预测结果转换为最终结果。

eg：投票（voting）及其变种、混合专家模型

多级组合：

一种串行结构。其中下一个分类器只在前一个分类器预测不够准（不够自信）的实例上进行训练或检测。

级联算法（cascading）

（5）小结

bagging 在给定样本上随机抽取（有放回）训练子集，在每个训练子集上用不稳定的学习算法训练分类不同弱分类器。

boosting 在前一个弱分类器错分的实例在后续的弱分类器上得到更大的重视

从训练子集的获取方式上看：

bagging 靠“运气”；boosting 有“依据”！

2. AdaBoost

2.1 原理

核心思想：“关注”被错分的样本，“器重”性能好的弱分类器

怎么实现？

（1）不同的训练集-->调整样本权重

（2）“关注”-->增加错分样本权重

（3）“器重”-->好的分类器权重大

（4）样本权重间接影响分类器权重

2.2 实现

原始AdaBoost：

改进版AdaBoost：