支持向量机分类与回归方法研究

介绍支持向量机和支持向量回归的用法 简单易懂 以支持向量机理论为基础，对分类与回归的基本方法及其应用进行了系统的研究。全文共分七章，第四章对支持向量机回归模型进行了一些扩展研究,具体内容分四部分:一、提岀一种单参数约束下的回归模型,并证明了该模型与标准回归模型的等价性;二、针对实际回归问题中经常出现异方差性,提出一种加权支持向量回归算法。仿真实验表明,当数据中存在异方差性时,所给方法的预测结果更接近真实值;三、针对支持向量回归模型中只有点输出而没有概率输出这一缺点,根据局部预测思想,在回归模型中定义了一种预测信任度的概念,从而为预测值提供了一个可信度评判。另外,通过对可信度的观测,还能在一定程度上判别数据中的噪声含量;四、研究了回归与分类之间的关系,为快速分类算法应用于回归模型中提供了一定的理论依据。第五章对异常值检测进行了探讨。利用支持向量回归算法中结构风险函数较好的平滑性以及KKT条件,提出一种回归中的异常值检测方法。另外,结合一类分类方法和相空间重构理论,提出一种时间序列中的异常值检测方法。第六章讨论了支持向量机与神经网络之间的关系,同时将支持向量回归的各种版本及RF网络应用于混沌时间序列预测中,并通过加入不同水平的噪声来比较分析它们的预测性能。第七章总结全文并对今后研究工作提出展望关键词支持向量机,结构风险最小化原则,核函数,分类,回归IABSTRACTRecently statistical learning theory has received considerableattention proposed based on small sample data, which is an importantcomplementarity and development of traditional statistics. SupportVector Machines (SVMs) algorithms based on the foundations ofstatistical learning theory show excellent leaning performance, whichhave been successfully extended from basic classification tasks toregression, density estimation, novelty detection, etc. Unlike traditionalmethods, which minimize the empirical training error sVms make use ofthe structure risk minimization principle, which may bring on a goodgeneralization performance.Additional advantages of SvMs can be appreciated in comparison toneural networks. For SVMs there are only a small number of tunableparameters and training amounts to solving a convex quadraticprogramming problem hence giving solutions that are global, and usuallyunique.This thesis consists of seven chapters which studies the problems ofpattern classification, regression and their applications.The basic methods about classification and regression aresummarized in the first chapter which include bayesian method neuralnetworks, support vector machines, etcChapter 2 introduces the algorithms of one-class support vectormachine binary classification and regression, and then a new multi-classclassification algorithm is proposed based on one-class classification ideawhich can largely reduce computation complexity and syncretize themethods of one-class. two-class and multi-class classification. At thesame time a decomposition algorithm of multi-class classification isproposed, which can provide a feasible approach for solving theclassification problem of large-scale dataIn chapter 3, support vector machine algorithms based on linearprogramming are summarized firstly. Secondly, three new regressionmodels are proposed based on linear programming, which can reduce thecomplexity of models and keep the good performance of predictionFinally, a new multi-class classification algorithm and its form ofdecomposition are proposed based on linear programming, which canobtain good recognition precision, and largely shorten the training timeAt the same time a new method of face recognition is proposed, which isbased on kernel Principal Component Analysis(KPCA) and multi-classclassification algorithm. The results of experiments at orl face imagedatabase show that the proposed method is feasible and effective.The contents of chapter 4 consist of three parts. Firstly, anewSupport Vector Regression(SVR) algorithm is proposed by introducing asingle parameter, and then the equivalence between the proposedalgorithm and standard support vector regression is proved. Secondly, akind of weighting support vector regression method is proposedcontraposing heterogeneity of variance in regression models. Thirdly, anotion of predicting credibility is proposed in support vector regression,which can make predicting value have a credible measure, and thenrelationship between predicting credibility and noise is discussed. Finallthe connection between regression and classification Is studied whichcan provide definite theory foundation for fast classification algorithmapplying to regression modelsIn chapter 5 outlier detection is discussed. A method of outlierdetection in regression is proposed making use of the character ofstructure risk function and KKT condition in support vector regression. Inaddition, a new method of outlier detection in time series is proposed bycombination of phase space theory and one-class classification methodChapter 6 discusses the relationship between neural networks andsupport vector machines, and then applies different versions of supportvector regression and RBF networks to the prediction of noise chaotictime series and compares their capability of predictionChapter 7 is the summarization of whole thesis and expectation forthe futureKEY WORDS support vector machine, structure risk minimizationprinciple, kernel function, classification, regression原创性声明本人声明,所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。作者签名:如1山日期:20年月2日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定,即:学校有权保留学位论文,允许学位论文被查阅和借阅;学校可以公布学位论文的全部或部分内容,可以采用复印、缩印或其它手段保存学位论文;学校可根据国家或湖南省有关部门规定送交学位论文。作者签名;3德业一。导师签天今日期,2年生月2日博士学位论文第一章导论第一章导论1.1课题背景及意义随着科学技术的飞速发展以及计算机、 Intemet的日益普及,越来越多的复杂非线性高维数据需要分析、处理,这也给传统的统计学方法提出了严峻挑战。从数据中发现知识是分析复杂数据、建立决策系统的基石。模式分类和回归分析是知识发现中的重要内容,也是处理许多其它问题的核心。用于分类与回归的方法很多,如传统的统计分析方法以及神经网络方法2等。这些方法虽然在实际应用中占据主导地位,但人们也发现它们还存在着许多不足之处。比如,传统的统计方法一般需要事先知道样本的先验分布,并要求有足够多的样本数据,而这些要求在实际应用中往往难以达到,这就使其在实际应用中效果往往并不理想。神经网络方法虽然很好地解决了非线性问题但由于其自身存在着结构不易确定、易陷入局部极小等固有的缺陷,从而限制了其实际应用。另外,神经网络的学习算法仅仅试图使经验风险最小化,并没有使期望风险最小化,与传统的最小二乘法相比,在原理上缺乏实质性的突破,这也是神经网络过拟合现象产生的原因,从而导致了其推广能力的下降。Vapnik等人提出的统计学习理论( Statistical Learning Theory,SLT)B是种针对小样本情况研究统计学习规律的理论,该理论的核心思想是通过引入结构风险最小化准则来控制学习机器的容量,从而刻画了过度拟合与泛化能力之间的关系。在这一理论基础上产生的支持向量机( Support Vector MachinesSwM学习方法近来受到广泛重视,该方法不但引入了结构风险的概念,还采用了核映射的思想,与传统方法相比,支持向量机所具有的优势体现在,即克服了传统方法的大样本要求,还有效地克服了维数灾难及局部极小问题,并在处理非线性问题时显示了其卓越的优越性作为一门新兴的学科,有关支持向量机方面的很多研究在国外也是刚刚起步,国内的有关研究只是在近几年才逐渐引起人们的注意。虽然支持向量机方法有比较完善的理论基础,但有关其应用研究还有很多亟待解决的问题,并且随着其应用领域的不断扩大,其理论也有待进一步完善和发展本文正是在这一理论背景下,以支持向量机方法为主线,在二次规划和线性规划的框架下对分类与回归中的基本方法进行研究,讨论了分类与回归之间的关系,并提出了一些新的分类及回归方法,同时探讨了支持向量机在异常值博士学位论文第一章导论检测以及在时间序列预测中的具体应用。该课题的研究将扩展支持向量机的应用空间。1.2目前发展状况模式分类是模式识别中的一项重要内容,分类也是人们认识一切事物的基础,许多优秀的学习算法都是以分类为基础发展起来的,如神经网络、支持向量机等。目前,用于模式分类的方法很多,传统的方法有 Bayesian方法、距离判别、 Fisher判别、k近邻分类以及分段线性分类等,现代的方法如模糊分类阿、粗糙分类以及神经网络分类等,还有刚刚兴起的支持向量机分类方法11模式分类方法已经在医学诊断、机械故障诊断、语音识别、人脸识别等领域得到了广泛的应用。回归分析发展和完善的根本动力在于其在生产实践中的广泛应用。从高斯提出的最小二乘法算起,回归分析的历史已有190多年。从经典的回归分析方法到近代的回归分析方法,它们所研究的内容已非常丰富。基于最小二乘法的模型回归方法由于简单且模型具有很好的解释性,在实际中被广泛采用。随着应用的不断深入,人们发现经典的最小二乘估计结果并不总是令人满意的,于是人们从多方面进行努力试图克服经典方法的不足,从而产生了岭估计、压缩估计、主成分估计、 Stein估计,以及特征根估计、偏最小二乘法等多种有偏估计。另外,为了克服最小二乘法估计对异常值的敏感性,人们提出了各种稳健回归方法;为了分析和处理高维数据,产生了投影寻踪回归、切片回归等为了解决非线性问题,人们还提出了许多非线性回归模型虽然分类与回归具有许多不同的研究内容,但它们之间却有许多相同之处,简单地说,它们都是研究输入输出变量之间的关系问题,分类的输出是离散的类别值,而回归的输出是连续的数值。有很多学习方法既可以用于分类又可以用于回归中,如贝叶斯方法、神经网络方法和最近刚刚兴起的支持向量机方法等。由于这三种方法在分类与回归研究中具有广泛的代表性,下面分别综述如下1.2.1贝叶斯学习理论贝叶斯(1702-1761)的论文“论有关机遇问题的求解”是贝叶斯学派产生的重要基础,由于其最初在理论和实际应用中存在很多不完善的地方,因此长时间未被广泛接受。20世纪初,B. de finetti与 Jeffreys H对贝叶斯学派的理论博士学位论文第一章导论做出了重要贡献。20世纪40年代末,Wald建立了以贝叶斯理论为核心的统计决策理论。随后,以 Robbins h.为代表,提出了经验贝叶斯方法与经典方法相结合1.12,引起了统计界的广泛重视20世纪90年代可学习的贝叶斯网络3的出现,为贝叶斯理论赋予了新的内涵。贝叶斯网络已经广泛地用于数据挖掘和机器学习中。有关贝叶斯分类与回归方法的研究也层出不1565贝叶斯学习理论利用概率的形式来表示变量间的依赖关系,通过先验信息和样本数据来获得对未知样本的估计。先验概率既可以借助人的经验、专家的知识来指定,也可以通过分析样本数据的特点直接获得。后者要求有足够多的数据才能真正体现数据的真实分布。贝叶斯方法的优点是可以利用人的先验知识,而缺点是当假设模型与样本实际分布情况不相符时,就难以获得较好的效果1.2.2神经网络学习理论神经网络2的产生起源于20世纪40年代,心理学家 McCulloch和数学家Pits合作提出了形式神经元的数学模型,成为人工神经网络研究的开端。1949年,心理学家 D.O. Hebb提出神经元之间突触联系强度可变的假设,并据此提出神经元的学习准则,为神经网络的学习算法奠定了基础1958年, Rosenblatt提出的感知器模型在神经网络的发中有着重要的作用,由于其只有一层的权值可调,因此它只能解决线性可分问题。虽然 Minsky在1969年出版的专著《 Perceptrons》中指出,在感知器中加入隐层神经元有可能解决非线性可分问题,但他对加入隐层神经元后能否给出一个有效的算法持悲观态度。1986年, Rumelhart等人提出了误差反向传播算法,即BP算法,才使神经网络的研究获得了新的生机。另外,著名的 kolmogorov连续性定理从数学上证明了神经网络可以以任意精度逼近任意非线性函数17,这为神经网络解决非线性问题提供了重要保证,也是神经网络在许多领域得到广泛应用的重要基础。目前常用的神经网络模型有BP网络、RBF( Radial basis Function)网络、Hopfield网络、自组织映射 Self-Organising Map,SOM神经网络等,这些网络在分类与回归研究中都有广泛的应用182。另外,神经网络同模糊理论以及遗传算法等软计算方法相结合产生了模糊神经网络、遗传神经网络等许多研究成果虽然神经网络在很多领域得到了成功的应用,但其得到的理论成果并没有对一般的学习理论带来多大贡献,也就是说神经网络还缺乏严密理论体系的指博士学位论文第一章导论导,其应用效果往往取决于使用者的经验。为了克服神经网络结构不易确定以及泛化能力差等缺点,1990年, Hansen和 Salamon首次提出了神经网络集成( neural network ensemble)的概念四,并证明了可以简单地通过训练多个神经网络而将其结果进行合成,可以显著地提高神经网络系统的泛化能力。1996年,Sollich和 Krogh给出神经网络集成的一个定义1,“神经网络集成是用有限个神经网络对同一个问题进行学习,集成在某输入示例下的输出有构成集成的各神经网络在该示例下的输出共同决定”。由于神经网络集成方法易于实现且效果明显,因此吸引了大批学者从事这方面的研究工作,其中 Boosting28和Bng29集成技术是用得最多的方法1.23统计学习理论Vapnik等人从20世纪六、七十年代就开始致力于小样本情况下的机器学习研究工作,并建立了统计学习理论4的基本体系。由于当时这些研究还不十分完善,且没有提出将理论付诸实践的较好的算法,一度使这些研究没有得到充分的重视。直到九十年代中期,随着统计学习理论体系的逐步完善,加之支持向量机的产生,人们才开始迅速重视起这一早在20年前就应该重视的学术方向。统计学习理论的核心思想是通过控制学习机器的容量实现对推广能力的控制。下面给出其中的一些重要概念。ˉV维统计学习理论中的一个重要概念是C维( Vapnik-Chervonenkisdimension),VC维反映了函数集的学习能力。定义1.1一个函数集的VC维是p,当且仅当存在p个样本点{x},函数集能够将该样本点按所有可能的2种形式分开,且不存在集合{x}1(其中g>p)满足这个性质。VC维的直观意义就是函数集能够打散的最大样本数目,若对任意数目的样本都有函数能将它们打散,则函数集的VC维是无穷大。一般而言,VC维越大则学习机器越复杂,学习容量就越大。目前尚没有通用的关于任意函数集VC维计算的理论,只对一些特殊的函数集知道其C维。例如在n维实数空间中线性分类器和线性实函数的VC维是n+1,f(x,a)=sin(ax)的VC维为无穷大。而对于一些比较复杂的学习机器(如神经网络),其VC维的确定非常困难。经验风险