支持向量机算法

1支持向量机算法和软件ChemSVM介绍陆文聪1，陈念贻1，叶晨洲2，李国正2（1.上海大学化学系计算机化学研究室，上海，200436）（2.上海交通大学图象及模式识别研究所，上海，200030）摘要VladimirN.Vapnik等提出的统计学习理论（statisticallearningtheory，简称SLT）和支持向量机（supportvectormachine，简称SVM）算法已取得令人鼓舞的研究成果。本文旨在对这一新理论和新算法的原理作一介绍，并展望这一计算机学界的新成果在化学化工领域的应用前景。“ChemSVM”软件提供了通用的支持向量机算法，并将其与数据库、知识库、原子参数及其它数据挖掘方法有机地集成起来。关键词模式识别；支持向量机；支持向量分类；支持向量回归中图分类号：O06-04IntroductiontotheAlgorithmofSupportVectorMachineandtheSoftwareChemSVMLUWen-cong1,CHENNian-yi1,YEChen-zhou2,LIGuo-zheng2(1.LaboratoryofChemicalDataMining,DepartmentofChemistry,ShanghaiUniversity,Shanghai,200436,China)(2.InstituteofImageandPatternRecognition,JiaotongUniversity,Shanghai,200030,China)Abstracts:Thegreatachievementshavebeenapproachedinthedevelopmentofstatisticallearningtheory(STL)andsupportvectormachine(SVM)aswellaskerneltechniques.ThispaperaimedatintroducingtheprincipleofSLTandSVMalgorithmandprospectingtheirapplicationsinthefieldsofchemistryandchemicalindustry..KeyWords:Statisticallearningtheory,Supportvectormachine,Supportvectorclassification,Supportvectorregression众所周知，统计模式识别、线性或非线性回归以及人工神经网络等方法是数据挖掘的有效工具，已随着计算机硬件和软件技术的发展得到了广泛的应用[1-4]，我们亦曾将若干数据挖掘方法用于材料设计和药物构效关系的研究[5-12]。但多年来我们也受制于一个难题：传统的模式识别或人工神经网络方法都要求有较多的训练样本，而许多实际课题中已知样本较少。对于小样本集，训练结果最好的模型不一定是预报能力最好的模型。因此，如何从小样本集出发，得到预报（推广）能力较好的模型，遂成为模式识别研究领域内的一个难点，即所谓“小样本难题”。最近我们注意到：数学家VladimirN.Vapnik等通过三十余年的严格的数学理论研究，提出来的统计学习理论（statisticallearningtheory，简称SLT）[13]和支持向量机（supportvectormachine，简称SVM）算法已得到国际数据挖掘学术界的重视，并在语音识别[14]、文字识别[15]、药物设计[16]、组合化学[17]、时间序列预测[18]等研究领域得到成功应用，该新方法从严格的数学理论出发，论证和实现了在小样本情况下能最大限度地提高预报可靠性的方法，其研究成果令人鼓舞。张学工、杨杰等率先将有关研究成果引入国内计算机学界，并开展了SVM算法及其应用研究[19]，但国内化学化工领域内尚未见SVM的应用报道。收稿日期：2002-06-10；修回日期：2002-09-10资金资助：国家自然科学基金委和美国福特公司联合资助，批准号：9716214作者简介：陆文聪（1964—），男，教授。研究方向：计算机化学。2本文是本论文系列的第一篇，主要介绍Vapnik等在SLT基础上提出的SVM算法，包括支持向量分类（supportvectorclassification，简称SVC）算法和支持向量回归（supportvectorregression，简称SVR）算法，并展望这一计算机学界的新成果在化学化工领域的应用前景。1统计学习理论（SLT）简介[13]1.1背景现实世界中存在大量我们尚无法准确认识但却可以进行观测的事物，如何从一些观测数据（样本）出发得出目前尚不能通过原理分析得到的规律，进而利用这些规律预测未来的数据，这是统计模式识别（基于数据的机器学习的特例）需要解决的问题。统计是我们面对数据而又缺乏理论模型时最基本的（也是唯一的）分析手段。Vapnik等人早在20世纪60年代就开始研究有限样本情况下的机器学习问题，但这些研究长期没有得到充分的重视。近十年来，有限样本情况下的机器学习理论逐渐成熟起来，形成了一个较完善的SLT体系。而同时，神经网络等较新兴的机器学习方法的研究则遇到一些重要的困难，比如如何确定网络结构的问题、过拟合与欠拟合问题、局部极小点问题等。在这种情况下，试图从更本质上研究机器学习的SLT体系逐步得到重视。1992－1995年，Vapnik等在SLT的基础上发展了SVM算法，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其它机器学习问题。很多学者认为，它们正在成为继模式识别和神经网络研究之后机器学习领域中新的研究热点，并将推动机器学习理论和技术有重大的发展。神经网络研究容易出现过拟合问题，是由于学习样本不充分和学习机器设计不合理的原因造成的，由于此矛盾的存在，所以造成在有限样本情况下：1)经验风险最小不一定意味着期望风险最小；2)学习机器的复杂性不但与所研究的系统有关，而且要和有限的学习样本相适应。SLT体系及其SVM算法在解决“小样本难题”过程中所取得的核函数应用等方面的突出进展令人鼓舞，已被认为是目前针对小样本统计估计和预测学习的最佳理论。1.2原理Vapnik的SLT的核心内容包括下列四个方面：1)经验风险最小化原则下统计学习一致性的条件；2)在这些条件下关于统计学习方法推广性的界的结论；3)在这些界的基础上建立的小样本归纳推理原则；4)实现这些新的原则的实际方法（算法）。设训练样本集为RyRxxyxymnn,11,,,,,，其拟合（建模）的数学实质是从函数集中选出合适的函数f(x)，使风险函数：dxdyyxPxfyfRYX),())((][2(1)为最小。但因其中的几率分布函数),(yxP为未知，上式无法计算，更无法求其极小。传统的统计数学遂假定上述风险函数可用经验风险函数][fRemp代替：niiempxfynfR12))((1][(2)根据大数定律，式(2)只有当样本数n趋于无穷大且函数集足够小时才成立。这实际上是假定最小二乘意义的拟合误差最小作为建模的最佳判据，结果导致拟合能力过强的算法的预报能力反而降低。为此，SLT用结构风险函数][fRh代替][fRemp，并证明了][fRh可用下列函数求极小而得：nhnhfRempSh)4/ln()1/2(ln][min(3)3此处n为训练样本数目，Sh为VC维空间结构，h为VC维数，即对函数集复杂性或者学习能力的度量。1-为表征计算的可靠程度的参数。SLT要求在控制以VC维为标志的拟合能力上界（以限制过拟合）的前提下追求拟合精度。控制VC维的方法有三大类：1〕拉大两类样本点集在特征空间中的间隔；2〕缩小两类样本点各自在特征空间中的分布范围；3〕降低特征空间维数。一般认为特征空间维数是控制过拟合的唯一手段，而新理论强调靠前两种手段可以保证在高维特征空间的运算仍有低的VC维，从而保证限制过拟合。对于分类学习问题，传统的模式识别方法强调降维，而SVM与此相反。对于特征空间中两类点不能靠超平面分开的非线性问题，SVM采用映照方法将其映照到更高维的空间，并求得最佳区分二类样本点的超平面方程，作为判别未知样本的判据。这样，空间维数虽较高，但VC维仍可压低，从而限制了过拟合。即使已知样本较少，仍能有效地作统计预报。对于回归建模问题，传统的化学计量学算法在拟合训练样本时，将有限样本数据中的误差也拟合进数学模型了。针对传统方法这一缺点，SVR采用“不敏感函数”，即对于用f(x)拟合目标值y时bxwxfT，目标值yi拟合在bxwyTi时，即认为进一步拟合是无意义的。这样拟合得到的不是唯一解，而是一组无限多个解。SVR方法是在一定约束条件下，以2w取极小的标准来选取数学模型的唯一解。这一求解策略使过拟合受到限制，显著提高了数学模型的预报能力。2支持向量分类（SVC）算法2.1线性可分情形SVM算法是从线性可分情况下的最优分类面（OptimalHyperplane）提出的。所谓最优分类面就是要求分类面不但能将两类样本点无错误地分开，而且要使两类的分类空隙最大。d维空间中线性判别函数的一般形式为bxwxgT，分类面方程是0bxwT，我们将判别函数进行归一化，使两类所有样本都满足1xg，此时离分类面最近的样本的1xg，而要求分类面对所有样本都能正确分类，就是要求它满足nibxwyiTi,,2,1,01)(。（4）式（4）中使等号成立的那些样本叫做支持向量（SupportVectors）。两类样本的分类空隙（Margin）的间隔大小：Margin=w/2(5)因此，最优分类面问题可以表示成如下的约束优化问题，即在条件（4）的约束下，求函数)(21221(6)的最小值。为此，可以定义如下的Lagrange函数：]1)([21),,(1bxwywwbwLiTiniiT(7)其中，0ia为Lagrange系数，我们的问题是对w和b求Lagrange函数的最小值。把式（7）分别对w、b、i求偏微分并令它们等于0，得：iiniixywwL104001iniiybL0]1)([0bxwyLiTiii以上三式加上原约束条件可以把原问题转化为如下凸二次规划的对偶问题：0,,1,0.max111121iniiijTijijninjiniiyaniatsxxyya(8)这是一个不等式约束下二次函数机制问题，存在唯一最优解。若*i为最优解，则niiiixyaw1**(9)*i不为零的样本即为支持向量，因此，最优分类面的权系数向量是支持向量的线性组合。b*可由约束条件0]1)([bxwyiTii求解，由此求得的最优分类函数是:)sgn())sgn((*1****bxxyabxwxfniiiiT(10)sgn()为符号函数。2.2非线性可分情形当用一个超平面不能把两类点完全分开时（只有少数点被错分），可以引入松弛变量i（i≥0,ni,1），使超平面0bxwT满足：iiTibxwy1)((11)当0i1时样本点xi仍旧被正确分类，而当i≥1时样本点xi被错分。为此，引入以下目标函数：niiTC),((12)其中C是一个正常数，称为惩罚因子，此时SVM可以通过二次规划（对偶规划）来实现：0,,1,0.max111121iniiijTijijninjiniiyaniCatsxxyya(13)53支持向量机（SVM）的核函数若在原始空间中的简单超平面不能得到满意的分类效果，则必须以复杂的超曲面作为分界面，SVM算法是如何求得这一复杂超曲面的呢？首先通过非线性变换将输入空间变换到一个高维空间，然后在这个新空间