机器学习算法总结_决策树(含代码)..doc

第六章 提升算法 6.1 引言 当做重要决定时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost算法进行介绍，并对提升树以及简单的基于单层决策树的Adaboost算法进行讨论。 提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据，这时就称为该分类器出现了过拟合（overfitting）。提升算法能够有效地防止过拟合现象的发生。 图1 过拟合现象示意图 提升算法是一种为了拟合自适应基函数模型（adaptive basis-function models, ABM）的贪心算法，自适应基函数模型可表达为： （6-1） 其中，是一种分类算法或者回归算法，被称为弱分类器（weak learner）或者基分类器（base learner）。也可以表达为如下形式： （6-2） 提升算法的目的是对以下公式的优化： （6-3） 其中，称为损失函数（loss function），是ABM模型。不同的损失函数有着不同的性质，对应不同的提升算法，如表1所示。 将(2)式代入(3)式可得如下表达式： （6-4） 因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那么就可以简化优化的复杂度，具体推导过程如下所示： （6-5） 表1 常见损失函数以及相应提升算法 名称 损失函数 导数 算法 平方误差 L2Boosting 绝对误差 Gradient boosting 指数损失 AdaBoost 对数损失 LogitBoost （6-6） （6-7） （6-8） 算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。 6.2 AdaBoost算法 AdaBoost（Adaptive boosting）算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D。一开始，这些权重都初始化为相等值，首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。 图2 AdaBoost算法示意图 给定一个二类分类的训练数据集，其中，每个样本点由实例与标记组成，实例，标记，是实例空间，是标记集合。损失函数可以表达为： （6-9） 其中，，，则可以有如下推导： （6-10） 其中，，，称为分类误差率。则可以得到第m个分类器： （6-11） 计算第m+1个分类器的参数可以通过下式得到： （6-12） 总结起来Adaboost算法主要有以下7步。 1 2 for do 3 Fit a classifier to the training set using weights w 4 Compute 5 Compute 6 Set 7 Return 算法结束条件是训练错误率为0或者弱分类器数目达到用户指定的值。在具体应用AdaBoost算法时，可以将其总结为以下的一般流程： 收集数据：可以使用任意方法； 准备数据：依赖于所使用弱分类器的类型，这里k-近邻、决策树、朴素贝叶斯、逻辑回归、支持向量机等任意分类算法都可以作为本部分弱分类器； 分析数据：可使用任意方法； 训练算法：AdaBoost算法大部分时间都用在训练上，分类器将多次在同