摘要
　　支持向量机(Support Vector Machine,SVM)是当今机器学习中解决分类问题的重要方法之一。基于统计学习理论、最优化算法和核方法的支持向量机具有全局优化、泛化能力强、避免“维数灾难”等优点。目前已成功应用于人脸识别、生物信息、故障诊断、网络安全、文本分类等领域中。
　　支持向量机的优势在于小样本、高维数据的模式识别,面对现今普遍的海量数据,由于占用内存大、训练时间长等缺陷,还有待完善与拓展。本文立足于SVM的理论基础、分析了其几何特点,对在大规模数据中的应用进行了初步的研究。
　　论文通过分析分类超曲面关于支持向量(Support Vectors, SVs)的几何位置结构,提出了分步训练的策略。首先用网格的形式将样本较多的原始数据聚类为较少的数据,同时根据数据分布情况选择核函数及参数,对归类后的数据使用SVM训练得到潜在的支持向量和初步的决策函数,进一步对以上结果再次训练,从而得出最终的决策函数。
　　对于初步训练得出的潜在支持向量或原数据集的标称属性(Nominal Attribute)较多的情况,提出了分段处理的思想,综合局部训练得到的结果给出最终的决策函数。
　　最后通过常用的测试数据,将本文的策略与原有SVM算法在训练速度、准确度和泛化能力方面进行比较,验证了其学习速度和有效性。
　　关键词:支持向量机;聚类;核技巧;数据挖掘;大数据

绪论 1
l.i支持向量机模型的研究现状与进展 1
1.2现有的支持向量机软件或程序 3
1.3 本文研究内容与组织结构 4
1.3.1 本文的研究内容 4
1.3.2 本文结构的安排 4
支持向量机理论基础和模型 6
2.1统计学习理论 6
2.1.1分类问题的统计学提法和经验风险最小化 6
2.1.2 Vapnik-Chervonenkis 维 7
2.1.3 结构风险最小化原则 7
2.2 支持向量机 8
2.2.1 SVM中的数学优化模型 8
2.2.2 最大间隔超平面 10
2.2.3 非线性支持向量机 13
2.2.4 SYM是SRM的一个算法实现 14
2.2.5 核理论 16
2.2.6支持向量 18
2.3 本章小结 18
核技巧与模型参数的选择 20
3.1 核技巧 20
3.2 核函数的选择 21
3.2.1常用的核函数介绍 21
3.2.2 核函数的构造 22
3.3分类器性能评估指标 24
3.3.1 单个分类器的评价 24
3.3.2 两个分类器的比较 25
3.4参数的选择 26
3.5实验结果及分析 27
3.5.1 实验平台和数据 27
3.5.2 实验结果分析 28
3.6 本章小结 30
数据预处理和聚类分析 31
4.1数据质量和预处理方法 31
4.1.1数据清洗 31
4.1.2 数据归约 32
4.1.3数据变换 32
4.2聚类算法 33
4.2.1 划分法 34
4.2.2层次法 34
4.2.3 密度法 34
4.2.4 网格法 34
4.2.5 模型法 35
4.3大规模数据集支持向量机 35
4.3.1 选块算法 36
4.3.2聚类算法与SVM结合 36
4.4网格化聚类的支持向量机 37
4.4.1网格化支持向量机算法 38
4.4.2 网格化支持向量机流程 39
4.5 分段支持向量_儿 40
4.5.1 分段支持向量机算法 40
4.5.2 分段支持向量机流程 41
4.6 实验结果及分析 42
4.6.1 实验平台和数据 42
4.6.2 实验结果分析 43
4.7 本章小结 44
总结与展望 45
5.1 本文总结 45
5.2 未来工作展望 45

                              第1章绪论
　　由于信息化处理在商业、政府、科研等各行各业的普及,每天都会产生规模庞大的数据。这些大规模的数据通常以数据库的形式储存起来。人们希望从中找到有用的规律或知识,以供商业分析决策、科学探索、生产检测,从而诞生了数据挖掘技术(DataMining)。数据挖掘技术不同于传统的数据库技术和联机分析处理技术(On-LineAnalytical Processing, OLAP),它可以发现未知的,潜在的信息。就像著名的沃尔玛超市发现的啤酒-尿布的例子中,人们很难事先预测啤酒和尿布之间会有什么联系。数据挖掘技术可用于有噪音的、稀疏的、冗余的数据集,且拥有运算复杂性低、易理解、人工参数少等特点,凭借着这些优点迅速在数据库的分析方面占据重要地位。
　　数据挖掘技术集合了数据库技术、人工智能、机器学习、数据可视化、统计学等多门学科的理论和方法。数据挖掘的主要功能包括分类、估计预测、聚类、时序分析、相关性分析、描述和可视化。其中分类分析也称为模式识别(Pattern Recognition),算法有决策树(Decision Tree Model)、朴素贝叶斯(Naive Bayes)、关联规则(AssociationRules)、A:-近邻(炎-Nearest Neighbor,KNN)、支持向量机(Support Vector Machine, SVM)、神经网络(Artificial Neural Networks,ANN)。而分类问题又可分为有监督的分类和无监督的分类,无监督的分类指训练集中样本的类别未知的情况,而有监督分类指训练集样本的类别己知,本文主要研究有监督分类学习中的SVM算法。SVM由瓦普尼克(Vladimir Naumovich Vapnik)等人在统计学习理论(Statistical Learning Theory, SLT)⑴上发展出来的一种较新的分类算法,因为该算法结构风险最小(Structural RiskMinimization, SRM),所以对于有限样本可以比其它数据挖掘算法取得更好的样本学习能力和泛化能力,同时对数据的维数没有限制,在基因工程的DNA序列数据库、图像、声音、文本、金融等高维数据中都有出色的表现。但在训练大规模数据时需要很大的内存和时间,使其在当今海量数据下无法体现其优势,对于大规模样本集中改进应用SVM必定是其研究的重要方向之一。
　　1.1支持向量机模型的研究现状与进展
　　在众多的数据挖掘分类算法中,比较常用的有朴素贝叶斯、人工神经网络和支持向量机,SVM拥有坚实的理论基础和漂亮的几何结构,让其越来越受到研究人员的关注。自从瓦普尼克等人从六十年代开始研究统计学习理论,并于九十年代提出了 SVM算法,随后,SVM受到重视并迅猛发展起来,对于算法的运行效率改进、模型的假设与解释、模型的参数选择方面提出了许多新的结果[2】。
　　由于传统的标准SVM在大样本下,对于硬件的运算速度和存储大小都有较苟刻的要求,所以对大规模样本需要改进才可方便应用,国内外已有算法来解决此类问题,主要使用选块算法(Chunking )、分解算法(Decomposition )、序列最小最优化算法(Sequential第2页 华东理工大学硕士学位论文Minimal Optimization, SMO),先聚类后 SVM,启发式找支持向量(Support Vectors,SVs)以及光滑化等方法和技巧,减少运行时间和内存占用。
　　Cortes和Vapnik[3]提出的选块算法(Chunking)以迭代方式不断排除训练集的某一子集中非支持向量对应的训练样本,保留支持向量,利用是否违反库恩-塔克(Karush-Kuhn-Tucker, KKT)条件等停机准则来作为判断选取添加训练样本的依据。算法的计算规模由SVs的个数决定,在一定程度上减少了内存的需求,但当SVs的个数很多时,算法运行效率并未提高很多,甚至在个别情况下有所下降。
　　1997年,Osuna[4]针对SVs较多时提出了分解算法(Decomposition),将训练集分为工作集和非工作集两个子集,每次迭代只添加删除同样数量的工作集中的样本,使工作集大小不变。Joachiins[5]继续改进了选块算法的更新策略,并通过收缩法减少非支持向量和边界上的支持向量缩减核矩阵,得到了高效的算法SVMlight[6]。Platt[7]使用最小工作集即两个训练样本,利用解析方法直接得出二次规划的解称为序列最小最优化算法(Sequential Minimal Optimization, SMO), Liii[8]等证明分解算法 SVMlight 的收敛性,同时1^11[9]和Keerthi_证明了 Piatt提出的SMO算法在一定条件下的线性收敛速度。Zanghiratitn]等人还提出了并行学习算法,将训练集分割求解后分别计算,之后合并各个结果达到快速训练的目的,但对计算机的硬件要求较高。
　　SVM算法在模型上也有许多变形,例如为了放松超平面分划训练集的要求,添加松弛变量,形成C-SVC。为定量解释说明参数的实际意义,将C-SVC改成了等价的V-SVC,使V成为间隔错误率的上界和支持向量占总训练集比例的下界,对于参数的选择给出了参照。由于训练集中个别样本的偏差可能对总体决策函数有较大波动,Suyk:eiis[i2]等人提出了最小二乘支持向量机(Least Squares-Support Vector Machine,LS-SVM),不仅使用了整体训练样本共同产生决策函数还简化计算,舍去了不等式约束,以的形式替换原目标函数的HiA.,同时删除原有的约束A 20,最终的对偶问题也只有等式约束,可以简化求解凸二次规划的难度。另外,有学者利用对偶问题之间目标函数最优值之间的相等关系,替换目标函数中的二次函数成变量的线性函数,得到线性规划形式的支持向量机。面对预测问题,SVM主要通过将原有样本集z) = |(jcf,y,f ,/ = 1,---,/| 修改为两类样本点 = + = 和zr 其中给定f >0,之后利用支持向量分类机的思路解得的决策函数就是支持向量回归机(Support Vector Regression,SVR)的决策函数,对于上面介绍的推广和改进,SVR也有相应的变形。
　　Yuh-Jye Lee和Mangasarian[i3]很多方法利用光滑技巧将模型中的函数可微化后,采用最优化理论中成熟的迭代搜索方法求得最优解,他们在2001年将sigmoid函数y=\l[\+exp{-kxy\, k>0的积分引入用作示性函数,利用Newton算法求解此无约束的光滑支持向量机模型(Smooth Support Vector Machine, SSVM)。袁玉波[i4】等人于2005年釆华东理工大学硕士学位论文 第3页用多项式(示性函数的Taylor展开)近似拟合,提出一类多项式光滑支持向量机(Polynomial Smooth Support Vector Machine, PSSVM)。2007 年,熊金志[丨‘]等人使用插值法推广了 PSSVM,得出了一个可产生一系列插值函数的递推公式,已证明该函数逼近效果优于PSSVM。
　　面对多分类问题SVM方法也进行了相应的探索,主要通过以下方法:
　　一一区分(one against one) [i6],对M个分类中的每两类样本都进行分类训练和判定,选取得票数较多者作为最终决策,此方法需要训练M(M+l)/2个两分类SVM。
　　一类对其余类(one against rest) [i7],先把某一类样本取出,训练集中剩余的其它类归为一个虚拟的类,需求解M个两分类SVM问题,决策时分别使用M个决策函数判断,取其中决策函数值最大的一个类别作为最终分类,或者使用编码方法先将各个类别通过某种策略编码后再进行M次训练。
　　改进SVM分类原理来适应多分类的情形,Crammer和Singer[i8]利用过原点的M个超平面把特征空间分成M个区域,使训练集的每个类分别在其中一个区域中,由于其中变量的增加,训练速度相对转化为两分类SVM的方法要慢很多,故还有待继续完善。
　　多分类问题中还包含有序多类问题,即这M个类别中的类与类之间存在某种顺序关系,从而可知有些类之间相邻,而另一些类之间不相邻,所以可以使用M-1个平行超平面分划,引入顺序支持向量回归机方法来求解有序多分类问题。
　　针对训练集中只有部分或者没有样本类别信息的半监督和无监督问题,学者Chapelle、Keerthi和Sindhwani[i9_2e]引入连续优化和确定退火法,得到了不错的训练效果。在许多领域,训练集不同类别数量的差异很大,例如在网络安全方面,接收的正常信息数目远远大于入侵的个数,机械故障的样本也明显少于正常情况。对数据不均衡的情形,Osuna[2i]等研究人员对各类别样本的数量比例确定参数C;另一方面从抽样角度上,对原始样本通过复制少数类样本的过抽样(Over Sampling)方法和删除多数类样本的欠抽样(Under Sampling)方法,以及提高算法分类准确率的Boosting算法[22】。
　　SVM在训练速度的提高和大样本、时间序列、变量缺失等数据的应用还有待进一步研究,对模型参数的解释和选择等方面也需要完善。
　　1.2现有的支持向量机软件或程序
　　LIBSVM软件是在中国使用最为普遍的SVM算法实现程序之一,主要由台湾大学的林智仁教授等学者使用C语言开发和维护,他实现了常用的几种SVM的变形模型,包括了多分类支持向量分类机和支持向量回归机等,核函数提供了线性核(原空间的内积)、多项式核、Sigmoid核函数、高斯径向基核函数及它们的参数和自定义核矩阵调整方法。林智仁[23】在其网站(http://www.csie.ntu.edu.tw/~cjlin/libsvm/)上不仅提供 C++的算法源代码和各种其它编程语言的接口,还有许多数据处理、结果可视化、交叉验证参数选择和相关教程,这方便了 LIBSVM的应用和推广。第4页 华东理工大学硕士学位论文LS-SVM工具箱是由Johan Suykens等人在修改传统的SVM中的松弛变量后得到的最小二乘支持向量机(LS-SVM),实现其算法的C和matlab工具箱,可以上其网站(http://www.esat.kuleuven.be/sista/lssvmlab/)获得算法的详细资料和程序包。支持向量机matlab工具箱由Steve Gurm[24】开发用于教学目的,加入了规划问题的内点法求解程序,对于学习SVM算法的编写具有早期的学习用途,但实践中由于matlab程序的制约,相对于其它语言的代码其运行速度缓慢,不适合于规模较大的数据集。SVMLIGHT[6]由Thorsten Joachims使用C语言实现其提出的SVMlight算法得到的软件工具,还用到了核缓存和向量的稀疏表示等方法减少内存的占用,分别给出了适用于多个操作系统的程序和对于规划问题求解程序的修改接口。Weka[25]由新西兰的Waikato大学的研究人员使用Java语言开发的开源数据挖掘软件,包括了 SVM在内的众多数据挖掘算法和实例数据,还提供了用户图形界面环境。
　　1.3本文研究内容与组织结构
　　1.3.1本文的研究内容本文的研究内容主要为以下几个方面:
　　讨论了 SVM的理论模型和现有的研究进展,详细地分析比较了已有的大规模数据集SVM改进模型。
　　2、分析了支持向量对整个决策函数的影响后,针对大规模SVM现有模型的缺陷,提出了用网格的形式聚合网格内的点以减少样本规模,而计算出的决策函数仅平移网格宽度的倍距离,其中/?为输入空间变量的个数。通过上述方法可找到几乎所有的支持向量后,再利用SVM算法得出最终决策函数,由于只对支持向量进行训练学习,大大地优化了运行时间和内存的占用。
　　3、对于初次训练后支持向量较多或者原数据集中标称属性较多的情况,关于数据集中某个变量分段训练,通过分段函数的形式给出最终的决策函数。
　　4、基于著名的机器学习测试数据网站University of California 11乂丨116(1]0)[26]的数据,使用其中规模较大的常用数据挖掘或机器学习的数据,将本文的策略与原有SVM算法在训练速度、准确度和泛化能力进行比较,验证论文所提出支持向量机算法的准确度和有效性。
　　1.3.2 本文结构的安排
　　论文从理论和实际出发,围绕SVM展开,对大规模数据集的训练学习提出了一些想法。论文结构安排如下:
　　为绪论,阐述了课题的背景和意义,研究进展和趋势,以及本文主要内容和架构。
    第二章为理论基础介绍,描述了 SLT中的VC维、SRM,详细描述了 SVM中的数学优化模型、核函数的理论及性质、SVM算法的复杂性,并对比经验风险最小化原则算法后,分析了 SVM具有的特点。
　　第三章为数据预处理和聚类介绍,例举了常用的数据分析前的清洗方法、归约方法和变换方法,包括缺失值处理、归一化、标准化。聚类分析主要分为划分法、层次法、密度法、网格法、模型法。
　　第四章分析比较了各常用核函数之间的区别,以及每个核函数关于参数变化引起性质的改变,并由此分析核函数及其参数的选择原则,作图说明参数引起的函数值几何形状变化,我们简述了核技巧与核理论,给出了常用的核函数和其构造方法,提供了现有的一些选择核参数方法。
　　第五章简要地介绍了几种用于大规模数据的SVM改进算法,分析其中的缺陷并说明了非SVs与决策函数无关后,提出了网格聚类SVM和分段训练SVM,详细地介绍这两个算法的步骤和优点,最后通过实例与其它算法对比验证算法的学习速度。
　　第六章对全文的主要工作进行总结和有待进一步改进的方向给出展望。