机器学习（二十五） ——adaboost算法与实现

机器学习（二十五）——adaboost算法与实现

（原创内容，转载请注明来源，谢谢）

一、概述

当进行监督学习时，除了使用某个分类器外，还可以将各个分类器结合起来使用，或者多次使用某个分类器，也可以是数据集分给不同的分类器后进行集成。本文主要介绍基于同一种分类器多个不同实例的方法，基础算法基于单层决策树。

二、bagging

首先，先介绍bagging算法，这个算法是一种自举汇聚法，方法如下：

1）获取数据源

假设样本容量为m，则进行m次放回抽样（即每次抽到样本后再将样本放回），获取一个新的样本集，这个样本集可能用重复数据。

接着，进行S次上述操作，获取S个样本集。

2）分类器

把某种分类器（如决策树）作用于这S个样本集，得到S个分类器。

3）使用

当需要分类的时候，则把新的数据给这S个分类器进行分类，会得到S个分类结果，并返回这S个分类结果中出现次数最多的分类（又称为票数最多的分类结果）。

三、boosting

boosting和bagging非常类似，唯一的区别在于，bagging中，每个分类器的投票权重是一样的，而boosting则会根据上一次的分类结果，对下一次的分类调整分类器对不同样本的权重。

boosting集中关注被已有分类器错分的那些数据，并主要用这些数据来训练新的分类器。多种boosting版本中，最流行的就是adaboosting。

主要步骤如下：

1）权重

对于训练数据的每个样本，赋予一个权重，这个权重代表上一轮迭代的成功度，上一轮成功的降低权重，上一轮错误的增加权重。

2）在训练数据上训练一个弱分类器，并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。

3）在分类器的二次训练中，会重新调整每个样本的权重。

4）公式

错误率e=未正确分类样本数/所有样本数，α=0.5ln((1-e)/e)。

上一轮该样本正确分类，则该轮样本Di(t+1)=Di(t)e-α/sum(D)；若错误分类，则Di(t+1)=Di(t)eα/sum(D)。

四、python实现adaboost

1、获取数据

这里有两种方式，一个是固定一个数据集，用于小范围的测试；另一个是载入一个文件，从文件中获取样本和分类结果。

2、构建单层决策生成树

1）阈值比较

首先需要一个辅助函数，可以通过比较阈值，来进行预测，这里预测的分类结果不是0和1，而是-1和1。

2）构建树

这里通过三层的循环，来构建一个单层的最佳的树，第一层是遍历所有特征，第二层是遍历所有样本，第三层是遍历大于和小于。

对照之前的决策树，是通过信息熵的大小来确定选择哪个节点最好，而这里不考虑信息熵，而是通过选择单层决策树的错误率，错误率最低的作为最佳的决策树，返回构建决策树的样本的第i个特征值、阈值、大于或是小于、最低错误率、最低错误率情况下的预测分类结果。

3、完整adaboost算法

上面有了构建决策树后，就可以来实现完整的adaboost了。实现方式主要基于上面的公式，如下：

错误率e=未正确分类样本数/所有样本数，α=0.5ln((1-e)/e)。

上一轮该样本正确分类，则该轮样本Di(t+1)=Di(t)e-α/sum(D)；若错误分类，则Di(t+1)=Di(t)eα/sum(D)。

整个过程比较简单，代码如下图所示：

唯一不一样的，是α的计算，不是直接除以e，是为了防止e=0时发生除以0的异常。

测试分类结果是否正常的代码如下：

一共迭代10次，实现10层的单层决策树。

结果如下（部分）：

可以看到，虽然每次的错误率都在0.5左右，但是最终的错误率在0.35，且这里返回了每层决策树的分类依据、阈值等数据。

4、使用adaboost进行分类

使用过程，即不断的获取单层的树，并且动态的加权后，将结果进行sign的运算即可。

五、总结

adaboost算法，可以理解为一个算法的大合集，里面可以放各种的内容，这里是以单层决策树为例，实际上可以放各种函数，有点类似svm的核函数的意义。

由于每次训练完，有反馈和权重，故多层的叠加后，效果会更好。

——written by linhxx 2018.01.30