毕业论文final-金雨欢

上海大学硕士学位论文 2008年5月

习算法产生的预测函数将发生较大的变化。

Bagging与Boosting的区别在于Bagging对训练集的选择是随机的，各轮训练集之间相互独立，而Boosting对训练集的选择不是独立的，各轮训练集的选择与前面各轮的学习结果有关; Bagging的各个预测函数没有权重，而Boosting是有权重的; Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于像神经网络这样极为耗时的学习方法，Bagging可通过并行训练节省大量的时间开销。 2.2.3.2 Bagging算法描述

给定一个数据集L?{(x1,y1),...,(xm,ym)}，基本学习器为h(x,L)。如果输入为

x，就通过h(x,L)来预测y。

现在，假定有一个数据集序列{Lk}，每个序列都由m个与L从同样分布下得来的独立实例组成。任务是使用{Lk}来得到一个更好的学习器，它比单个数据集学习器h(x,L)要强。这就要使用学习器序列{h(x,Lk)}。

如果，y是数值的，一个明显的过程是用{h(x,Lk)}在k上的平均取代h(x,L)，即通过hA(x)?ELh(x,L)，其中EL表示L上的数学期望，h的下标A表示综合。如果h(x,L)预测一个类j?{1,...,J}，于是综合{h(x,Lk)}的一种方法是通过投票。设Mj?#{k,h(x,Lk)?j}，使hA(x)?argmaxMj。

jBagging的算法流程如下：

1．给定训练样本集S?{(x1,y1),...,(xn,yn)}。 2．对样本集进行初始化；

3．循环t=1,...T,在循环中的每一次：

a． 从初始训练样本集S中用bootstrap方法抽取m个样本，组成新的训练集S'?{(x1,y1),...(xm,ym)}；

b． 在训练集S’上用基本分类器进行训练，得到t轮学习器ht, c． 保存结果模型ht；

18

上海大学硕士学位论文 2008年5月

4．通过投票法，将各个弱学习器h1,h2,...,ht通过投票法集合成最终的强学习器hA(x)?sign??hi(x)?。

Brieman指出，Bagging所能达到的最大正确率为：

??rA??maxP(j|x)Px(dx)????I(hA(x)?j)P(j|x)?Px(x)

j'?x?Cx?C?j (2.2.2.5)

中C为序正确的输入集，C’为C的补集，I(?)为指示函数。

2.3 SVM算法

早在上世纪60年代，以数学家Vladimir N. Vapnik等为代表的学派就注意到了经典统计数学的这一弱点，并开始努力建立一套能保证从有限样本得出预报能力最强的数学模型。通过三十余年的严谨数学理论研究，提出了“统计学习理论”（Statistical Learning Theory，简称SLT）。在SLT理论研究的基础上，又于1992年和1995年先后提出支持向量机（Support Vector Machine，简称SVM）算法--支持向量分类（Support Vector Classification，简称SVC）算法和支持向量回归（Support Vector Regression，简称SVR）算法。2001年，Burbidge在“Computer and Chemistry”首次发表了将SVM算法用于药物设计和QSAR方面的论文，这是该新算法在化学领域应用的开始。现今，SVM算法已经得到了国际数据挖掘学术界的重视，并在语音识别、文字识别、药物设计、组合化学、时间序列预测、蛋白质研究等多个研究领域取得了成功的应用，该方法从严谨的数学理论出发，论证和实现了在小样本情况下能最大限度地提高预报可靠性的方法，其研究成果令人鼓舞。

2.3.1 统计学习理论

Vapnik等人早在20世纪60年代就开始研究有限样本情况下的机器学习问

题，但这些研究长期没有得到充分的重视。近十年来，有限样本情况下的机器学习理论逐渐成熟起来，形成了一个较完善的统计学习理论体系。而同时，神经网络等较新兴的机器学习方法的研究则遇到一些重要的困难，比如如何确定网络结构的问题、过拟合与欠拟合问题、局部极小点问题等。在这种情况下，试图从更

19

上海大学硕士学位论文 2008年5月

本质上研究机器学习的统计学习理论体系逐步得到重视。1992—1995年，Vapnik等在统计学习理论的基础上发展了SVM算法，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其它机器学习问题。

统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之

间的关系，即推广性的界。关于两类分类问题，指出了对指示函数集中的所有函数，经验风险Remp(w)和实际风险R(w)之间以至少的概率满足如下关系:

R(w)?Remp(w)?h(ln(2n/h)?1)?ln(?/4)n (2.3.1)

其中h是函数集的VC维，n是样本数。

这一结论从理论上说明了学习机器的实际风险由两部分组成:一部分是经验风险;另一部分称为置信范围，它和学习机器的VC维h及训练样本数n有关。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，从而对未来样本有较好的推广性。由此可见，经验风险最小化(Empirical Risk Minimization, ERM)原则在样本有限时是不合理的。事实上，在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如果模型比较适合现有的训练样本，则可以取得比较好的效果。但因为缺乏理论指导，这种选择主要依赖先验知识和经验，造成了如神经网络等方法对使用者“技巧”的过分依赖。

统计学习理论提出了一种新的策略，即结构风险最小化((Structural Risk Mininimation, SRM)原则，把函数集构造为一个函数子集序列，使各个子集按照VC维的大小排列，在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，以取得实际风险的最小。实现SRM原则有两种思路，一种是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至无穷时不可行。第二种思路是设计函数集的某种结构使每个子集中都能取得最小的经验风险，然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现。

20

上海大学硕士学位论文 2008年5月

2.3.2 支持向量分类算法

2.3.2.1 最优分类面

支持向量机方法是从线性可分情况下的最优分类面提出的。考虑图2.1所示

的二维两类线性可分情况，图中空心圆点和实心圆点分别表示两类训练样本，H为把两类没有错误地分开的分类线，H1和H2分别表示两类样本中距离分类线最近的点且平行于分类线的直线，H1和H2之间的距离叫作两类的分类空隙或分类间隔。所谓最优分类线就是要求分类线不仅能将两类无错误地分开，而且要使两类空隙最大。前者是保证经验风险最小，而后者是使真实风险最小。推广到高维空间，最优分类线就成为最优分类面。

H2 H H1 margin?2/||w||

图2.2最优分类面示意图

2.3.2.2线性可分的情况

首先从最为简单的线性可分的情况入手。d维空间中线性判别函数的一般形式为g?x??wTx?b，分类面方程是wTx?b?0，将判别函数进行归一化，使两类所有样本都满足g?x??1，此时离分类面最近的样本g?x??1，而要求分类面对所有样本都能正确分类，就是要求它满足

yi(wxi?b)?1?0,i?1,2,?,nT (2.3.2)

式(4-7)中使等号成立的那些样本叫做支持向量（Support Vectors）。两类样本的分

21