Adaboost算法流程和证明.doc

"Adaboost算法流程和证明" TITLE: Adaboost算法流程和证明 Adaboost算法是Freund和Schapire根据在线分配算法提出的，它详细分析了Adaboost算法错误率的上界，以及为了使强分类器达到错误率，算法所需要的最多迭代次数等相关问题。 Adaboost算法基本原理 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。 Adaboost算法具体步骤 1. 初始化每个样本的权重； 2. 对每个（为弱分类器的个数）： * 把权重归一化为一个概率分布 * 对每个特征，训练一个弱分类器计算对应所有特征的弱分类器的加权错误率 * 选取最佳的弱分类器（拥有最小错误率） * 按照这个最佳弱分类器，调整权重 3. 最后的强分类器为：，其中表示被正确地分类。，表示被错误地分类。 Adaboost算法应用 随着Adaboost算法的发展，目前Adaboost算法广泛的应用于人脸检测、目标识别等领域，其中有在人脸识别、汽车识别、驾驶员眨眼识别的方面的应用和研究。 Discete-Adaboost算法 1. 给定训练集：，其中，表示的正确的类别标签，，表示第副图像的第个特征值 2. 训练集上样本的初始分布： 3. 寻找弱分类器() * 对于每个样本中的第个特征，可以得到一个弱分类器，即可得到阈值和方向，使得达到最小，而弱分类器为： * 将所有特征()中挑选出一个具有最小误差的弱分类器。 4. 对所有的样本权重进行更新 5. 经过轮训练得到个最优的弱分类器，此时组成一个强分类器； 在Adaboost算法的弱学习中，将产生错误率为的弱分类器。如果每个错误率，则强分类器的总错误率一切都从强分类器的错误率开始首先权值更新，然后强分类器的错误率使这个错误率快速下降？ 证明 为了证明Adaboost算法的正确性，我们可以使用贪心算法求出的一个局部最小值对中的求导。令导数为零解出此时绘制关于的曲线图。从这幅图上我们可以看出，当错误率越小或者越大（只要不在中点处徘徊）的时候快速收敛到0。 弱分类器的选择 找弱分类器？决策树ID3，C4.5，C5.0ID3生成树用（CIG类别属性增益法）C4.5生成树用（Gain Ratio增益比率法）修剪树用（Rule post-pruning规则修剪）C5.0生成树用（Gini指数）修剪树用（CRAT回归树修剪）然后给出Yoav Freund论文中给出的寻找方法排序令阈值。