十分钟算法小故事之Adaboost算法

编辑：AI小迷妹

引言

高二（1）班的小明同学为了能够识别小区中的常见的两种不同类型的小鸟(麻雀和燕子)，想设计一个分类器。首先，分类器有一些输入的特征，比如鸟的外形类型的特征，颜色类型的特征，纹理（羽毛）类型的特征。小明用SVM分类器来分类这两种鸟，发现效果不是很好，于是小明想到，我能不能训练多个分类器，也就是三个臭皮匠赛过诸葛亮的策略。这就是本章要讲的Adaboost (Adaptive Boosting) 算法，它属于集成学习的范畴。下图显示了集成学习的示意图。

什么是集成学习

集成学习通过将多个弱的学习器进行结合，常可获得比单一学习器更好的性能。首先需要产生一组“个体学习器”，再用一个策略将它们结合起来。

1）个体学习器：可以选择决策树，神经网络。集成时可以所有个体学习器属于同一类算法（全是决策树，或全是神经网络），也可以来自不同的算法。

2）结合的策略：例如分类问题，可以用投票法，即少数服从多数。

假设小明训练了三个分类器，然后拿这三个分类器在三个测试样本上进行实验，其中√表示分类正确，×表示分类错误。在这里我们结合的策略选择投票法，也就是集成学习的结果服从“少数服从多数”。

在图（a）中，每个分类器都不错，有66%的分类精度， 而且三个分类起有所不同，集成之后的结果达到了100%。

在图（b）中，每个分类器也都有66%的分类精度，但是三个分类器没有差别，集成之后性能没有提高。

在图（c）中，每一个分类器精度比较差，只有33.3%，集成学习的结果变得更糟。

从这个例子我们得知：要获得好的集成结果，个体学习器应该要“好”并且要有差异性。也就是个体学习器本身不能效果太差（臭皮匠技术不能太差），同时要有多样性（每个臭皮匠要有不同于其他人的一技之长）。

Adaboost算法

Boosting算法是一种将弱学习器提升为强学习器的算法，这种算法的工作机制就是先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本进行调整，使得先前基学习器做错的训练样本在后续得到更多的关注，然后在调整后的训练样本分布下训练下一个基学习器，如此重复，直到分类器的个数到达一个指定的阈值N就停止，然后将这N个基学习器加权结合。最著名的代表就是Adaboost算法。

我们以麻雀和燕子分类的例子来了解如何实现Adaboost算法。下图中“+” 和 “-”分别表示燕子和麻雀两种类别，我们在实现分类的过程就是使用水平或者垂直的直线作为分类器将“+” 和 “-”区分开，从而实现分类。

图1 初始的样本分布

第一步，我们先训练第一个基分类器h1，图2。很明显经过h1的分类，有三个样本（“+”）分错了。所以这三个点的权重要变大一些。然后形成一个新的样本分布。

图2 经过h1的分类

第二步，基于这个新的分布再训练一个基分类器，获得一个新的样本分布以及第二个基分类器h2，如图3。

图3 经过h2的分类

我们可以看到，有三个红色的”-”是分错的，这是我们需要重点照顾的对象，因此要把权重加大。同时靠近分类边界的蓝色的”+”是上次分错的，也要重点关注。

于是样本的分布就变成了下面的样子：

图4 经过h1,h2分类后的样本分布

第三步，基于这个新的样本分布，我们需要训练新的分类器h3。

图5 经过h3的分类

于是最后的分类器，是三个基分类器的线性组。如下图所示：

Adaboost算法实现

实战练习

【问题定义】

利用scikit-learn库的Adaboost算法来以对Iris数据集进行分类，Iris数据集分为3类（图5），每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属。

【解题思路】

1）首先从sklearn中导入模块：

from sklearn.model_selection import cross_val_score

from sklearn.ensemble import AdaBoostClassifier

2）然后准备数据

from sklearn.datasets import load_iris

iris = load_iris()

iris数据集包含两部分，一部分是iris.data是一个150*4维的矩阵，表示150个样本，每一个样本的特征维度是4.另外是对应的标签，维度是150*1.

3）因为该问题是个分类问题，所以创建一颗分类树AdaBoostClassifier，调用Scikit-Learn中的相关函数：

clf = AdaBoostClassifier(n_estimators=100) #迭代100次，等价于创建100个基分类器

4）上面创建好的clf是一颗分类器，必须给它喂数据进行训练，然后进行测试。我们随机选取100个样本做训练，余下的测试

import numpy as np

population=np.arange(iris.data.shape[0])

np.random.shuffle(population)

#将数据进行shuffle

N = 100

ind = population[0:N]

ind1 = population[N:]

train_data = iris.data[ind,]

test_data = iris.data[ind1,]

train_label = iris.target[ind,]

test_label = iris.target[ind1,]

clf.fit(train_data,train_label)

clf.score(test_data, test_label)

训练好之后余下的进行测试

clf.score(test_data, test_label)

1.0

说明Adaboost在测试集上完全分对了

总的程序如下：

-----------------------------------------------------------------

from sklearn.model_selection import cross_val_score

from sklearn.ensemble import AdaBoostClassifier

from sklearn.datasets import load_iris

import numpy as np

iris = load_iris()

clf = AdaBoostClassifier(n_estimators=100)

population =np.arange(iris.data.shape[0])

np.random.shuffle(population)#将数据进行shuffle

N = 100

ind = population[0:N]

ind1 = population[N:]

train_data = iris.data[ind,]

test_data = iris.data[ind1,]

train_label = iris.target[ind,]

test_label = iris.target[ind1,]

clf.fit(train_data,train_label)

clf.score(test_data, test_label)

------------------------------------------------------------------

想学习了解人工智能知识的小伙伴们，请关注：