【作者】 梁锦锦；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2009， 博士

【摘要】 支持向量机(Support Vector Machine, SVM)是基于统计学习理论提出的一种新型有监督模式识别方法.采用结构风险最小化原则,SVM在最大化分类间隔和最小化分类误差之间取得折衷,以控制分类器的泛化能力.SVM较好地解决了小样本、高维数及非线性等实际问题,具有拟合精度高、选择参数少、推广能力强和全局最优等特点.SVM成为机器学习领域新的研究热点,并被广泛应用到模式识别、函数拟合和密度估计等领域.本文针对大规模样本集的SVM训练问题、SVM的集成学习问题、变形SVM问题、支持向量域描述(Support Vector Domain Description,SVDD)的快速训练问题等进行研究,主要研究工作如下:1.研究了大规模样本集的SVM训练算法.SVM在训练大规模样本集时面临着占用内存多、计算代价大的问题,这也成为实际应用的瓶颈问题.基于并行学习中“分而治之”的理念和“支持向量与全体训练样本等价”的结论,提出一种同心超球面支持向量机(Hypersphere Support Vector Machine, HSVM).HSVM以相同层数的两组同心超球面组对正负两类样本进行分割,对分层间隔内的样本采用SVM训练,合并所有分层间隔中支持向量的并集以参与最终的SVM训练.HSVM既保持了SVM的分类精度又降低了SVM的训练时间.2.研究了SVM的集成学习算法.运用集成学习的理念构造了一种空间支持向量域分类器(Space Support Vector Domain Classifier,SSVDC).选取支持向量域分类器(Support Vector Domain Classifier,SVDC)和K近邻(K Nearest Neighbor,KNN)作为子分类器,SSVDC以选择集成的策略对两者的预测结果进行集成.SSVDC首先采用SVDD求得两类样本的最小包围超球,并以超球的描述边界将训练样本划分为互不相交的几个区域;其次计算待测样本到两个最小包围超球球心的距离,根据其与两个最小包围超球半径的大小关系判断待测样本所处区域;最后选择相应的子分类器得到最终的分类结果.由于子分类器均针对样本的某个子集进行训练,SSVDC具有较短的训练时间.由于根据样本的分布选取相应的子分类器,SSVDC具有较高的分类精度且其分类精度受核参数变化的影响不大.数值实验验证了SSVDC的有效性以及对比SVM和SVDC的优越性.3.研究了变形SVM算法.通过改变原始优化问题的函数项、变量或系数得到了一系列变形SVM算法,这在一定程度拓宽了SVM的应用范围.针对变形SVM中的二次损失函数SVM,构造一种光滑对角加权支持向量机(Smooth Diagonal Weighted Support Vector Machine,SDWSVM).在线性空间中,直接运用光滑技术得到光滑模型,也即采取Sigmoid函数的积分函数来逼近正号函数形式的松弛.在非线性空间中,先分别利用Lagrange乘子向量来代替分类超平面的权值向量和原-对偶规划隐含的分类超平面的权值向量表达式对原规划的目标函数进行转换,再利用光滑技术构造光滑模型.对线性空间和非线性空间中得到的光滑模型,均采用Newton法求解,具有较高的效率.4.提出了一种约简支持向量域描述算法(Reduced Support Vector Domain Description,RSVDD).SVDD的训练即为求解一个所含未知数个数等于全体训练样本个数的凸二次规划.为了提高SVDD的训练速度,RSVDD对每个样本定义一种自中心距离比值,定义此值为该样本到中心的距离与所有样本的平均中心距离的比值,并以此值作为判断该样本成为支持向量的可能性度量.RSVDD选取自中心距离比值较大的部分样本参与SVDD训练,从而减少了待解QP的规模.该算法引入参数少,易于实现且保持了目标类精度.5.提出了一种信赖支持向量域描述算法(Confidence Support Vector Domain Description,CSVDD).由于支持向量往往分布在SVDD的描述边界附近,基于这个几何特性,定义了一种信赖抽样方法以提取部分样本参与SVDD训练.依次以每个样本为中心,做一个以某定长为半径的超球.统计落入该超球中的训练样本数目,并将该值作为判断中心样本属于支持向量的信赖度量(Confidence Measure).根据信赖度量的值将训练样本升序排列,CSVDD提取排在前面的部分样本作为边界向量集参与最终的SVDD训练,缩短了SVDD的训练时间并保持了SVDD的目标类精度.更多还原

【Abstract】 Support Vector Machine (SVM) is a new supervised pattern recognition method based on Statistical Learning Theory (SLT). SVM adopts Structural Risk Minimization (SRM) principle; it makes compromise between the margin maximization and the error minimization, so as to control the generalization ability of the obtained classifier. SVM can better deal with problems, such as small sample, high dimension and nonlinearity. SVM has advantages such as high classification accuracies, few parameters, global optimums and strong generalization performances; it becomes a new research area in the field of machine learning research and it has been widely applied into various areas, such as pattern recognition, function regression and density estimation. Focusing on the existing problems, such as SVM training for large-scale samples, SVM ensemble learning, reformation of SVM, Support Vector Domain Description (SVDD), etc, detailed studies are made and all the researches can be summarized into the following five parts:1.The research on the algorithms of SVM training for large-scale samples. The training of SVM becomes difficult in practical applications for large-scale samples; it takes up large memory and enormous computation time. Based on the ideology of“divide and conquer”in parallel learning and the conclustion of“the equivalence between support vectors and the whole training samples”, concentric hypersphere support vector machine is proposed and is called HSVM for short. Dividing the positive and negative samples using groups of concentric hyperspheres with the same layers, HSVM trains the samples between the margins using SVM and takes the combination of the obtained support vectors in corresponding margins to participate in the final SVM training. HSVM guarantees the classification accuracies of SVM while it reduces the training time of SVM.2.The research on ensemble learning of SVM. Ensemble learning ideology is utilized to construct a Space Support Vector Domain Classifier (SSVDC). Taking SVDC (Support Vector Domain Classifier) and KNN (K Nearest Neighbor) as the sub classifiers, SSVDC uses selective ensemble strategy to obtain the final classification results. Firstly, SSVDC uses SVDD to obtain the minimal enclosing hyperspheres of the positive and negative samples, and divides the training samples into several disconnected regions using boundaries of the two hyperspheres; then SSVDC calculates the distances of one test sample to the centers of the two minimal enclosing spheres of the positive and negative samples, and specifies the region that the test sample belongs to based on the relationship between the distances and the radiuses of the two minimal enclosing spheres; finally SSVDC takes the corresponding sub classifier to judge its label. Since sub classifiers are carried out on subsets of the data, SSVDC has short training times. Since different sub classifiers are erected based on the sample distribution, SSVDC has high target accuracies which vary little with kernel parameters. Numerical experiments demonstrate the effectiveness of SSVDC and the superiority over SVM and SVDC.3.The research on reformation of SVM. Reformation of SVM broadens the application areas of SVM, which can be obtained by changing the terms, variables or coefficients in the objective function in the original optimization problem. Based on quadratic loss function SVM, smoothing technique is adopted to construct Smooth Diagonal Weighted Support Vector Machine (SDWSVM). In the linear space, smooth model is directly obtained by using smoothing technique, which takes the integral function of sigmoid function to approximate the slack in the plus function form. In the kernel space, two methods are used to transform the original objective function before applying smoothing technique. One uses the method adopted by traditional SSVM which takes the Lagrange multiplier vector to substitute the weight vector of the separating hyperplane; the other uses dual technique between the primal and dual program to find the expression of the weight vector of the separating hyperplane. For the obtained smooth models in the linear and kernel space, Newton method is proposed to find the global optimums which guarantees high efficiency.4.Reduced Support Vector Domain Description (RSVDD) is presented. The training of SVDD involves solving a convex quadratic program, whose number of variables is equal to the number of training samples. To accelerate the training speed, RSVDD defines a self central distance ratio for each sample, which is the ratio of the central distance divided by the mean central distance, and takes it as a probability measure to judge whether one sample is a support vector or not. RSVDD selects some samples with high self central distance ratios to participate in the final SVDD training, thus reducing the training scale. RSVDD is easy to implement, has few parameters and maintains high target accuracies and short training time.5.Confidence Support Vector Domain Description (CSVDD) is proposed. Based on the geometry characteristic that support vectors usually distribute around the description boundary, a confidence sampling strategy is proposed so as to select some samples to participate in the SVDD training. Centered at each sample, a sphere with fixed radius is drawn. Counting the number of samples in the user-defined sphere, CSVDD takes this number as a confidence measure to judge whether the center sample is one support vector or not. Ranking the training samples in ascending order according to the confidence measure, CSVDD extracts a certain portion of those former ranked samples as boundary vectors to participate in the SVDD training. The training time of CSVDD are shorter than that of SVDD, while the target accuracies of the former are identical with those of the latter.更多还原