机器学习大作业

张燕 2014E8001061081

一、背景介绍

我们现在处在一个大数据时代，随着科技的进步，各种各样的信息随之而来，面对这些五花八门的信息，我们需要对它进行分类处理，而由于数量的庞大，信息更新速度快等因素，人脑的分类速度已经远不能解决这些问题，因而分类器的研究问题应运而生。直接找到一个强分类器是一件很困难的事，然而大家都知道三个臭皮匠赛过诸葛亮，弱分类器是一个很容易搞定的问题，所以我们只要对弱分类器加以一定的加工，就可以构造出一个强分类器，这样分类问题便得以解决。关于弱分类器构造为强分类器问题，有一系列算法，此次大作业由于时间与空间的有限，只介绍几种分类器算法，分别为boosting、bagging和bootstraping。下面我对这些算法分别做一下简单介绍。 二、分类器算法介绍

分类是数据挖掘的一种非常重要的方法。分类是指在已有数据的基础上学会一个分类函数或构造出一个分类模型（即我们通常所说的分类器(Classifier)）。该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测。总之，分类器是数据挖掘中对样本进行分类的方法的统称，包含决策树、逻辑回归、朴素贝叶斯、神经网络等算法[1]。

1、boosting算法

1990年, Schapire最先构造出一种多项式级的算法 ,对弱学习转化为强学习问题做了肯定的证明 ,这就是最初的 Boosting算法。

i)从样本整体集合D中，不放回的随机抽样n1 < n个样本，得到集合 D1训练弱分类器C1

ii)从样本整体集合D中，抽取 n2 < n个样本，其中合并进一半被C1 分类错误的样本。得到样本集合D2,训练弱分类器C2

iii)抽取D样本集合中，C1 和 C2 分类不一致样本，组成D3训练弱分类器C3 iv)用三个分类器做投票，得到最后分类器 2、adaboost算法

1995年,Freund和schapire改进了Boosting算法 ,提出了 AdaBoost (Adaptive Boosting)算法,该算法效率和Freund于1991年提出的Boosting算法几乎相同,但不需要任何关于弱学习器的先验知识,因而更容易应用到实际问题当中。之后,Freund和schapire进一步提出了改变Boosting投票权重的AdaBoost.M1,AdaBoost.M2等算法,在机器学习领域受到了极大的关注[4]。Adaboost算法是boosting算法的一种，其余的boosting算法也是在adaboost算法基础上发展起来的。所以对adaboot算法做简单介绍。

Adaboost的整体框架为：首先循环迭代多次，更新样本分布，寻找当前分布下的最优分类器，计算误差率。接着根据不同弱分类器的权值不同进行叠加，形成强分类器。具体的实现过程是首先形成一个弱分类器，该弱分类器只比随机分类好一点点即可，接着根据该分类器可以找到判错的类，然后使得误判的权值增大，让正确的权值变低，再形成一个分类器，最后正如之前说的，进行分类器加权求和。这里我们需要注意一下，我们并不是重复采样，而是不断改变样本分布的权值，也是同以往分类器的不同之处。

Adaboost方法的优点

一adaboost是一种有很高精度的分类器。

二、可以使用各种方法构建子分类器，Adaboost算法提供的是框架。

三、当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单。 四、简单，不用做特征筛选。

五、不用担心overfitting也就是过学习。 Adaboost方法的缺点 对噪声敏感。

3、bagging和bootstraping算法

bagging和bootstraping都是采用又放回的采样得到样本，因而我们放在一起共同研究。但是二者的核心不同，bootstraping是对采样样本分别进行学习，形成不同的弱分类器，接着对这些弱分类器进行组合，形成最终的强分类器，bagging也是对这些样本进行学习，得到分类器，只是最后采用投票的方式选择最终的分类器。 它们的学习步骤为：

1）bootstrapping方法的主要步骤：

i)重复地从一个样本集合D中采样n个样本

ii)针对每次采样的子样本集，进行统计学习，获得假设Hi iii)将若干个假设进行组合，形成最终的假设Hfinal iv)将最终的假设用于具体的分类任务

2）bagging方法的主要过程 -----bagging可以有多种抽取方法 主要思路： i)训练分类器

从整体样本集合中，抽样n* < N个样本 针对抽样的集合训练分类器Ci ii)分类器进行投票，最终的结果是分类器投票的优胜结果

上述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。 三、Adaboost算法实现二分类 完整的adaboost算法如下：

初始分布给定所有样本的权值一样,即𝐷1=(𝑊11,𝑊12,…,𝑊1𝑁),𝑊1𝑖=,𝑖=1,2,…,𝑁,接

𝑁1

下来设定循环迭代的次数为K，则接下来要训练分类器K次，首先我们根据最初的均匀分布可以选定一个分类器𝐶1，该分类器不需要太强，只要比随机分类好一点即可，这是很容易实现的，根据这个分类器，我们可以得到该分类器的误判概率以及求得该分类器的权值，权值选定特定的函数a𝑘=ln⁡(

21

1−𝑒𝑘𝑒𝑘

（公式中)k为循环迭代的次数，e为误判概率，） (1)，

根据第一次的划分，增大误判的样本权值，减小正确划分的权值，改变后的样本分布集合为𝐷2=(𝑊2,1,𝑊2,2,…,𝑊2,𝑁)，继续产生一个弱分类器𝐶2，计算此时的错误概率，并用此时的错误概率更新此时分类器的权值，由此计算下去，迭代第k+1次时，𝐷𝑘+1=(𝑊𝑘+1,1,𝑊𝑘+1,2,…,𝑊𝑘+1,𝑁),⁡𝑊𝑘+1,𝑖=

𝑊𝑘,𝑖𝑍𝑘

exp⁡(−𝑎𝑘𝑦𝑖𝐶𝑘(𝑥𝑖)),𝑖=1,2,…,𝑁 (2)其中𝑧𝑘

的作用是用来保证权重之和为1，使得的分布是一个概率分布，𝑧𝑘的计算公式为𝑧𝑘=

∑𝑁(−𝑎𝑘𝑦𝑖𝐶𝑘(𝑥𝑖)) (3)这样一𝑖=1𝑊𝑘𝑖exp⁡

步步迭代最终可以得到一系列（共K个）的分类器以及它们对应的权值，将这些分类器加

权求和形成最终的强分类器，这里不难理解权值为何使用这个函数，因为里面的自变量就是误判的概率，误判的可能性越大，则e越大，计算出来的权值就越小，这样最终形成强分类器时它所占的比重就越小，因而形成强分类器结果很精确[5][6]。

运用python软件使用adaboost方法与bagging方法得到的二分类结果如下

Bagging方法 adaboost方法

图一：bagging方法与adaboost方法对比图

下面为python改变adaboost参数后的效果图

图二：两样本数都是250，弱分类器个数为200

图三：样本数仍为250，将弱分类器个数增加到600时的分类效果如下

图四：样本数仍为增加到600，弱分类器数目为200的分类效果如下

参考文献

[1]http://baike.baidu.com/link?url=jIx5Axo6XEGpPHD1-DALnXxlOzq4FTVsmcTfe5wOG8wPiRGCfZkjRK4PLJILwq40wz300lBeeny5z97XSdJgPK

[2] http://www.doc88.com/p-86115936291.html

[3] 哈明虎，王熙照.不确定统计学习理论基础及SVM的泛化能力研究[D].河北.河北大学研究生硕士论文

[4]http://baike.baidu.com/link?url=iSQ9qmyIxCp1M5Vu-6ENe0zMHAHE2HuN97R1nYUSYaHEKksevA5Q4XzxlAK63HawRommPo64CTPaDD9U8x7vrq

[5] http://blog.csdn.net/haidao2009/article/details/7514787 [6]http://doc.okbase.net/suipingsp/archive/116882.html