决策树及其组合算法adaboost

AdaBoost集成学习个体学习器间不存在强依赖关系、可同时生成的并行化方法，如bagging，随机森林个体学习器间存在强依赖关系、必须串行生成的序列化方法，如boostingAdaBoostAdaptiveboosting，每个新的模型都会基于前一个模型的表现结果进行调整，可以自动适应每个基学习器的准确率，迭代过程主要体现在样本权重更新和弱分类器加权组合。样本权重更新弱分类器加权组合用函数表示：设训练数据集T={(x1,y1),(x2,y2)…(xN,yN)}初始化训练数据的权值分布AdaBoost算法AdaBoost：对于m=1,2,…M使用具有权值分布Dm的训练数据集学习，得到基本分类器计算Gm(x)在训练数据集上的分类误差率计算Gm(x)的系数（分类器的权值）基学习器的分类误差率要小于0.5分类误差率越小，分类器权值越大AdaBoost：对于m=1,2,…M更新训练数据集的权值分布这里，Zm是规范化因子它使Dm+1成为一个概率分布AdaBoost构建基本分类器的线性组合得到最终分类器AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类学习方法。AdaBoost算法解释加法模型考虑加法模型其中：基函数：基函数的参数基函数的系数：前向分步算法在给定训练数据及损失函数L(y,f(x))的条件下，学习加法模型f(x)成为经验风险极小化即损失函数极小化问题：算法简化：如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近上式，即：每步只优化如下损失函数：前向分步算法的算法框架输入：训练数据集T={(x1,y1),(x2,y2)…(xN,yN)}损失函数L(y,f(x))基函数集{b(x;γ)}输出：加法模型f(x)算法步骤：前向分步算法的算法框架初始化f0(x)=0对于m=1,2,..M极小化损失函数得到参数更新当前模型：得到加法模型前向分步算法与AdaBoost算法AdaBoost算法是前向分步算法的特例，这时，模型是基本分类器组成的加法模型，损失函数是指数函数。损失函数取：损失函数是指数函数损失函数取：证明假设经过m-1轮迭代，前向分步算法已经得到fm-1(x)：在第m轮迭代得到,和目标是使前向分步算法得到的和使在训练数据集T上的指数损失最小，即证明进一步：其中：既不依赖α也不依赖G，所以与最小化无关。但依赖于fm-1(x)，所以，每轮迭代会发生变化。基本分类器G*(x)首先求分类器G*(x;γ)对于任意α>0，是上式最小的G(x)由下式得到：其中，权值的计算求权值：将G*(x)带入：求导，得到权值的计算由模型以及权值可以方便的得到：AdaBoost算法优点在AdaBoost的框架下，可以使用不同的分类或回归算法来构建弱学习器AdaBoost作为分类器时，分类精度较高，且较不同意过拟合相对于随机森林等算法，AdaBoost充分考虑了每个分类器的权重AdaBoost算法不足对异常样本敏感，容易受噪声干扰。异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。执行效果依赖于弱分类器的选择（AdaBoost只是一个算法框架）训练时间比较长THANKSAdaBoost有效性当G(xi)≠yi时，yi*f