支持向量机方法论文（精选12篇）
支持向量机方法论文 篇1
0.引言
统计学习理论起源于20世纪60年代晚期[1],在其后的20多年里,涉足这一领域的人不多。这期间,前苏联人Vapnik和Chervonenkis做了大量开创性、奠基性的工作,这些工作主要是纯理论性的,故当时未引起人们的重视。到了90年代中期,人们提出了理论严谨的结构风险最小化原理,并在此基础上创造性地产生了一种新的机器学习算法--SVM[2,3],基于统计学习理论的SVM方法是现代智能技术的一个重要分支。支持向量机算法是一个凸二次优化问题,保证找到的解是全局最优解;能较好在解决小样本,非线性和高维数,局部极小点等实际问题。SVM采取折中考虑经验风险和置信范围以取得实际风险最小化的思想,实现了结构风险最小化(SRM),从而避免了过学习现象的出现。在保证分类精度的前提下,提高了分类器的泛化能力。基于结构风险最小化原理的思想同样被成功地应用于函数回归,出现了理论依据更好的回归方法。
1. 支持向量机分类介绍
支持向量机是从求解线性可分情况下的最优超平面发展而来的,这个平面可通过采取平分最近点法和最大间隔法得到。引入对偶问题可证得这两种方法得到的是同一个超平面,或者得到的超平面具有平行的法方向[4],所以本文采用的是由最大间隔分类法导出的支持向量回归机的仿真实验来说明问题。
1.1 平分最近点法
设训练集T={(x1,y1),…,(xl,yl)},其中xi∈Rn,yi∈{1,-1}。对于线性可分(二分类)情形,通过找到T中两个凸壳的最近点c和d而采取平分最近点法求出唯一的分划超平面能将训练集中的两类点完全正确的分开。而正类点集的凸壳中的任一点和负类点集凸壳的任一点可分别表示为。其中α1,…αl满足(1)所以要找到c和d,只需在约束(1)下,求解以u=(α1,α2,…,al)T为变量的函数的极小点,这样便可得到两个凸壳的最近点。c和d连线中点且与这条直线垂直的直线就是所求的分类超平面,可用点法式求得。对应于中非零的向量称为相应分类问题的支持向量。
对于线线性不可分问题,通过引入参数D<1,使0≤αi≤D,使两类相交的凸壳缩小不再相交。这时就可以对缩小后的两个凸壳进行“平分最近点”了[5]。
1.2 最大间隔法
这种方法的基本思想可用图1的情况来说明。设样本为n维向量,某区域的k个样本及其所属类别表示为:(xi,yi),i=1,2,…,xi∈Rn,yi∈{+1,-1}。图中三角形和圆分别代
表两类样本,H为分类面。H1、H2平行于分类面,且过各类中离分类面最近的样本,其上的训练样本点称作支持向量(SV),它们之间的距离叫做分类间隔(margin)。所谓最大间隔法就是要求分类线不但能将两类正确分开,而且使分类间隔最大。设样本满足yi[(w·xi)+b]≥1,i=1,2,…k,则样本间分类间隙为2/‖w‖,使分类间隙最大等价于使‖w‖最小,因此满足此条件且使最小的分类面就是最优分类面,即最优超平面。这样,构造最优超平面的问题就转化为以下带约束条件的极小值求解问题:
通过求解得最优解。因此所求的决策函数为:
对于线性不可分问题,只要引入惩罚参数C和松弛变量ξi就可得到不可分情形下的线性分类器,这正是软边缘算法[6]。
对于非线性分类器的设计问题,可引入核函数通过输入空间到特征空间的非线性映射将其转化为高维问题加以解决,在这个高维空间中寻找输入变量和输出变量之间的一种非线性关系,其基本结构如图2所示。而决定非线性分类器的优化问题正是线性可分情形时的适当变形,即将输入空间的欧氏内积变为核函数。
对于分类问题,一般都是采取求解最大间隔法的对偶问题来获得最优超平面,因为由该法得到的决策函数仅依赖于输入(xigxj),(xigx),i,j=1,…k和K(xi,xj),K(xi,x),i,j=1,…k。
2. 基于分类的回归方法
回归问题的数学描述:设给定训练集T={(x1,y1),…,(xl,yl)}∈(X×Y)l,其中xi∈X=Rn,yi∈Y=R,i=1,…l寻找Rn上的一个实函数f(x),以便用y=f(x)来推断任一模式x对应的y值。假定训练集是按X×Y上的某个概率分布P(x,y)选取的独立同分布的样本点,又设给定损失函数c(x,y,f),试寻求一个函数f(x),使得期望风险R[f]=∫c(x,y,f)dP(x,y)达到极小。
不难看出,回归问题和分类问题的结构相同,不同之处仅在于它们的输出yi和Y的取值范围不同,在分类问题中,输出只允许取两个值(或有限个值),而在回归问题中,输出可取任意实数。对于回归问题,我们通常选取ε-不敏感损失函数[7]c(x,y,f(x))=|y-f(x)|ε,其中|y-f(x)|ε=max{0,|y-f(x)|-ε},ε是事先给取定的一个正数。损失函数可用图3表示。为研究分类与回归的关系,将训练集T中每个训练点的y值分别增加ε和减少ε,得到正类点和负类点,可表示为:
其中:这时就可对变换后训练集进行分类了,从而得到回归函数。可以看出当ε充分大时,分类超平面总是存在的,而最小的能使超平面存在的ε值εmin就是最优值。
2.1 基于平分最近点法分类的回归方法
当ε>εmin时,两类凸壳线性可分,得到下列最优化问题:
ui≥0,vi≥0,i=1,…l(7)。在求得其最优解后,便可得到两凸壳的最近点:。并取,得分划超平面为,整理后可得线性回归函数:y=(wgx)+b,其中。
当ε>εmin的线性不可分时,可选取合适的参数D,使两类凸壳适当缩小不再相交,转变为线性可分问题。这时(7)式变为D≥ui≥0,D≥vi≥0,i=1,…l。
2.2 基于最大间隔法分类的回归方法
对于由式(4)所示的线性分类问题的训练集,可采用最大间隔法得到分类函数,从而转化为回归函数,于是得到如下优化问题:
其中求得到该问题的最优解后,便可得到分划超平面。整理后得到线性回归函数:y=(wgx)+b,其中。对于线性不可分问题,可对每个训练样本引入松弛变量ξl≥0和惩罚参数C。从而(8)式加上约束条件(9)式左面加上ξl。可以证明通过选择合适的ε,(8)和(9)等价于:
(10)(11)把上式转化为对偶问题得到支持向量回归机算法:
(13)αi,,i=1,2,…,l.(14)。解以上式子,可得最优解:,如果或就称训练集中的输入xi为支持向量。计算;选择的一个正分量,并据此计算,这时可得到回归函数y=(wgx)+b。对于线性不可分问题,只需把引入惩罚参数C使。对于非线性不可分问题,选择适当的正数ε和C,使,并选择适当的核K(x,x'),使(12)式转化为如下形式:(15)
这时可以得到回归函数:
3. 方法应用举例
设训练集T={(x1,y1),…(x50,y50)}是根据单变量函数:
Ys=(1-x+2x2)gexp(-0.5x2)在受到随机噪声干扰下产生的。确切地说,x1,…,x50是在[-4,4]上均匀分布的50个点,而Y1=Ys1+0.2|Ysj|maxg(2ζt-1)/2,i=1,…,50,j=1,…,50其中ζl服从均匀分布的随机数,数值范围(0,1)。下面根据按上述方式构造的训练集计算回归函数。我们用(15)式所示的支持向量回归机求解回归问题,选取Gauss径向基核函数。参数选ε=0.2,C=100,仿真结果如图(4)。关于参数的选取,理论上可以得出越小,支持向量个数越多,但计算复杂。惩罚因子C越大,要求学习机越精确的学习该样本,训练时间也越长,所以C不宜过大。
多项式拟合选8阶,如图5所示。由于受到澡声的污染,多项式拟合得到的回归函数图5存在的误差明显比图4 大,又由于多项式拟合选取的是左除,拟合的阶次受到限制,所以本文提出的回归方法优于多项式拟合得到的回归函数。
4. 结束语
SVM在近几十年里越来越受到人们的重视,在本文采用的将回归问题转化为SVM分类问题求解而得到的支持向量回归机具有很好的可靠性,但如何结合结实际问题构造核函数是极其重要也是最困难的问题,构造更紧的误差的界及给出其技术理论上的证明也是急待解决的问题。
参考文献
[1]Vapnik,V.An overview of statistical learning theory(J).IEEE Transactions on Neural Networks,1999,10(5):988-999.
[2]Vapnik,V.The nature of statistical learning theory[M].Berlin:Springer-Verlag,1995.
[3]Cortes,C.Vapnik,V.Support vector networks. Machine learning(J),1995,20(1):1-25.
[4]Bennett K,Bredensteiner E.Duality and Geometry in SVM Classifiers.In:Proc.of Seventeenth Intl.Conf.on Machine Learning, Morgan Kaufmann,a Francisco:2000:57～64.
[5]陶卿，孙德敏，范劲松，等．基于闭凸包收缩的最大边缘线性分类器(J)．软件学报，2002，13(3)：404-409
[6]Cortes,C.Prediction of generalization ability in learning machines[D].Department of Computer Science,University of Rochester,1995.
[7]Gunn,S.Support vector machine for classification and regression[R].ISIS Report,Image Speech & Intelligent Systems Group,University of Southampton,1998.
支持向量机方法论文 篇2
随着油田油气勘探的深入,低阻油层的勘探开发具有重要的意义.由于低阻油层的测井响应特征不明显,导致常规的测井解释方法识别低阻油层的正确率较低.低阻油层的.识别其实质是一个复杂的模式识别问题,研究采用支持向量机分类理论,选取多种相对独立的测井参数对低阻油层进行识别分析.以工区试油已证实含油气性类型的层位作为训练样本进行训练,建立其油层、油水同层和水层的分类器相应支持向量机和分类面.通过已建立分类器的分类函数,可对待识别的层位进行识别分析.实例分析结果表明,基于支持向量机的低阻识别方法对数据量没有太高的要求,且操作简单,识别效果良好.
作 者：连承波 赵永军 钟建华 渠芳 蔡福龙 张军涛 LIAN Cheng-bo ZHAO Yong-jun ZHONG Jian-hua QU Fang CAI Fu-long ZHANG Jun-tao 作者单位：连承波,赵永军,钟建华,渠芳,LIAN Cheng-bo,ZHAO Yong-jun,ZHONG Jian-hua,QU Fang(中国石油大学地球资源与信息学院,山东,东营,257061)
蔡福龙,CAI Fu-long(中国科学院地质与地球物理研究所,北京,100029)
张军涛,ZHANG Jun-tao(南京大学地球科学系,江苏,南京,210093)
支持向量机方法论文 篇3
关键词：经济预测模型；支持向量机；加函数；光滑函数；Newton-Armijo算法
1.引言
一种半监督支持向量机优化方法 篇4
目前, 半监督学习在机器学习领域发展迅速, 主要是由于无标签样本的获得较容易并且经济。半监督学习就是通过少量的有标签样本和大量的无标签样本来学习分类机, 从而获得更好的推广能力。半监督支持向量机是采用支持向量机来解决半监督问题的方法, 已经有大量的学者从事这方面的研究, 并取得了很好的效果。首次相近的研究是Vapnik[1]提出的直推式支持向量机。Joachims[2]首次编码实现了支持向量机软件包svmlight (其中包括直推式支持向量机) 后, 大量解决半监督支持向量机的非凸问题的研究随后出现。相关的研究包括局部组合搜索[2]、梯度下降[3]、连续优化技术[4]、凸凹过程[5,6]、半正定编程[7,8]、不可微方法[9]、决定退火[10]、分枝界定法[11,12]。与支持向量机不同的是半监督支持向量机的原始问题是非凸的, 上面所提到的方法都是为解决这个非凸问题提出的。
分布估计算法是进化计算领域新兴的一类随机优化算法, 是当前国际进化计算领域的研究热点。它是遗传算法和统计学习的结合, 通过统计学习的手段建立解空间内个体分布的概率模型, 然后对概率模型随机采样产生新的群体, 如此反复进行, 实现群体的进化[13]。
因为半监督支持向量机的原始问题最终可归结为一个组合优化的问题, 而分布估计算法是可以解决组合优化问题的一种方法。本文的目的就是采用分布估计算法来解决半监督支持向量机的组合优化问题, 基于该原理, 提出了一种基于分布估计算法的半监督支持向量机优化方法EDA_S3VM, 给出了理论分析和实验结果。实验结果表明, EDA_S3VM与其它一些半监督支持向量机算法相比有更高的分类准确率。
1 半监督支持向量机
半监督支持向量机是采用间隔最大化思想对少量的有标签样本和大量无标签样本进行分类。与支持向量机不同, 除了确定ω和b (ω为垂直于分类超平面的向量, b为一个分类阈值) 外, 半监督支持向量机把无标签样本的标签作为需要优化的参数。从而得到一个在标准支持向量机上的组合优化问题。下面给出了半监督支持向量机的工作原理, 这里只考虑二分类问题。
训练样本包括l个有标签样本{ (xi, yi) }
式中:yu=[yl+1…yn]T, 为无标签样本的标签;C、C*分别为有标签样本和无标签样本上的征罚参数;ξi为样本xi对应的松弛变量, ξi≥0, 1≤i≤n;p为ξi上的指数级。
由式 (1) 可知
其中:
则问题转化为
取p=2, 并且令C=C*, 问题进一步转化为
令函数:
原问题变为最小化函数I, 注意到I有3个变量ω、b和yu。
解决思路有2种:
(1) 连续优化
将原问题中的yu用sgn (ωxi+b) 来代替, 这样原问题就转化为一个在ω和b上的连续优化问题。采用这种方法的有参考文献[3,4,5,6]。
(2) 组合优化
对于给定的一个yu, 在ω和b上的优化就是一个标准的支持向量机。定义
原问题变为在一组有限空间中求最小化J的组合优化问题, 对于每个J的求解都是一个标准支持向量机。采用这个思路的方法有参考文献[2]、[7,8,9,10]。本文采用的方法就是基于这一思路。
为了防止不平衡结果的发生, 需要考虑平衡约束:
式中:r为有标签样本中正标签所占的比例。
2 分布估计算法
分布估计算法采用类似遗传算法中的种群进化模式, 通过概率模型的学习和采样来对问题进行求解。它通过一个概率模型描述候选解在空间的分布, 采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型, 然后对概率模型随机采样产生新的种群, 如此反复进行, 实现种群的进化, 直到终止条件[13]。
分布估计算法的基本步骤如下:
(1) 基于图的群体初始化
考虑到样本的分布, 在进行群体初始化时采用聚类假设, 即距离近的样本具有相同的类别标签。这样给每个样本赋一个标签, 每个基因位置的概率值是通过计算它周围相应标签的比例而产生的。例如通过Dijkastra求得所有样本的距离矩阵E, 得到概率向量p= (p1, p20, …, pu0) , 根据该概率模型产生初始群体。
(2) 选择优势群体, 更新概率模型
通过适应值函数J (yu) 计算各个个体的适应值, 如果符合终止条件, 输出结果, 否则继续执行。适应值函数是采用间隔最大化思想的函数, 因此, 选择适应值最大的N个个体组成优势群体D
(3) 随机采样
根据概率模型p采样M次, 得到新一代群体, 返回步骤 (2) 继续执行。
3 半监督支持向量机优化方法EDA-S3VM
式 (7) 为目标函数, yu∈{-1, 1}u, 描述解空间的概率模型用简单的概率向量p= (p1, p2, …, pu) 表示, p表示群体的概率分布, pi∈[0, 1], 表示基因位置i取1的概率, 1-pi表示基因位置i取0的概率。
基于分布估计算法的半监督支持向量机优化方法EDA-S3VM的伪代码如图1所示。
输入:l个有标签的样本{ (xi, yi) }
输出:ω、b和yu
1 t=0
2 do {
3 if t=0
4 初始化群体D0
5 利用标准支持向量机求解每个个体的适应值
6 else
7 通过概率模型抽样得到DSampled
8 利用标准支持向量机求解每个个体的适应值
9 利用更新方法通过Dt-1、DSampled和D
10 根据选择方法选择集合D
11 根据学习方法计算D
12 t=t+1
13 } until终止标准成立
图1 基于分布估计算法的半监督支持向量机
优化方法EDA-S3VM的伪代码
4 实验结果及分析
4.1 数据集
实验的目的是检验采用分布估计算法进行半监督支持向量机优化后在不同数据集上的分类效果。数据集包括2个人工数据集和3个公共数据集。其中人工数据集包括一个线性可分的点集 (下面用Point表示) 和一个“Two moons”数据集, 公共数据集包括g50c、Ciol20和Uspst。表1给出了实验数据集的特征描述, 其中, c表示样本类别的个数, d表示样本的特征数, l表示有标签的样本数, n表示所有样本总数。
4.2 实验结果及分析
对于Point数据集, 在2个样本集上进行, 其中一个数据集包括2个有标签样本 (正负类各一个) 、100个无标签样本, 另外一个数据集包括2个有标签样本 (正负类各一个) 、200个无标签样本, 结果如图2所示, 其中右上方的“+”表示正类有标签样本, 左下方的“+”表示负类有标签样本, 右上方的“·”表示正类无标签样本, 右下方的“*”表示负类无标签样本。图2 (a) 中, EDA-S3VM找到了2类样本的最优分类面, 而图2 (b) 中, EDA-S3VM的分类效果较差, 并未找到最优解, 原因是分布估计算法采用的概率模型的学习和采样方法可能导致算法陷入局部最优。
然后, 通过实验来验证EDA-S3VM算法在4种真实数据集上对无标签样本的分类错误率, 并与cS3VM、∇S3VM和S3VMlight算法进行比较。由于这些算法的效果都会受参数σ与C取值的影响, 对每个数据集, 每一种算法在同样参数设置下采用交叉验证的方式取实验结果的平均值。在实验中进行如下设置:粒子的种群规模对算法的运行速度有直接影响, 一般可取10～40, 本实验取20;算法的终止条件为达到最大迭代次数或连续10次解不发生变化。表2给出了不同算法的分类错误率。
从表2可看出, EDA_S3VM与其它几种算法相比, 在测试样本上的分类错误率都有所降低。
5 结语
针对分布估计算法可解决半监督支持向量机的组合优化问题, 提出了一种基于分布估计算法的半监督支持向量优化方法EDA_S3VM。在人工数据集和公共数据集上的实验结果表明, EDA_S3VM与其它一些半监督支持向量机算法相比有更高的分类准确率。该方法可以推广到多分类问题与非线性问题, 对于多分类的问题采用一对多的策略变为二分类问题, 对于非线性的问题采用核方法来解决。由于分布估计算法在解决非线性、变量耦合的优化问题上的优势, 其在非线性支持向量机优化上的应用能得到较好的效果, 但由于进化算法的迭代过程导致了算法计算效率的下降, 如何加快算法的收敛速度是进一步研究的方向。
支持向量机方法论文 篇5
基于支持向量机的航空发动机故障诊断
支持向量机学习方法以结构风险最小化原则取代传统机器学习方法中的经验风险最小化原则,在有限样本的学习中显示出优异的.性能.本文将这一新的统计学习方法应用到航空发动机故障诊断的研究中,并通过某型航空发动机故障诊断的实验结果表明了本文方法的有效性.
作 者：杨俊 谢寿生 于东军 作者单位：空军工程大学工程学院,西安,710038刊 名：机械科学与技术 ISTIC PKU英文刊名：MECHANICAL SCIENCE AND TECHNOLOGY年，卷(期)：24(1)分类号：V23关键词：支持向量机 航空发动机 故障诊断
支持向量机方法论文 篇6
关键词：学生评价；支持向量机算法；聚类策略
中图分类号：G647 文献标识码：A 文章编号：1671-864X（2015）10-0088-02
引言
高校的学生评价不仅仅是评定学生，另外还具有引导和有助于学生的发展。在今天素质教育的倡导下，学生的发展应当是全面综合的发展，包括专业知识与技能、道德修养、身体素质等各方面在内的发展。传统的学生评价模式泰勒模式[1]以及CIPP模式[2]不是存在评价目标单一的缺陷就是过于注重结果评价，这样的评价模式皆不能适应现在的素质教育要求。因此特别需要一种更加恰当的评价方法对上述学生评价中存在的问题加以解决。
本文针对学生样本数据的特点，利用支持向量机分类算法对其进行分类研究。支持向量机（Support Vector Machine），简称SVM[3]，是建立在统计学习理论的结构风险最小化原理上的一种分类技术，对于解决小样本、非线性、高维数问题，比其他分类算法具有更好的泛化性。它避免了神经网络中的局部最优解的问题，并有效地克服了“维数灾难”和“过学习”等传统困难[4]。
一、支持向量机理论
支持向量机的最初应用是线性可分的二分类问题，最优分类面也是由此而来的。基本思想如图1所示，其中，H是分类线，实心方块和实心圆分别代表样本的正负两类，H1和H2分别是过各类样本中离分类线最近且平行于H的分类间隔。支持向量机要求，H能将训练样本完全分开，并且保证分类间隔最大。
在实际应用中遇到的很多情况都是多分类问题，比如本文中根据学生信息对学生进行的分类。构造多分类的方法目前主要有“一对多”SVM分类、“一对一”SVM分类、“有向无环图”[5]SVM分类等。
二、支持向量机的学生评价实例
利用山东省某高校计算机学院学生专业课信息，包括学生的基本信息，学生的行为特征（包括出勤率，学习态度，作业提交情况，素质得分）和学生成绩（笔试成绩，上机成绩）。取200个同学的信息作为训练集样本，那么对每一个同学来说，其数据规模是16维，如果所有样本维数都参与计算，其数据规模高达3200个多，而这仅仅是对于同一所学校某年级来说，如果对一个地区高校学生进行分析呢，计算量更是相当之大。利用自组织特征映射网络聚类方法对200个学生样本进行聚类。
首先，根据同一个班中的学生基本情况大体都是类似的，我们暂且忽略掉，只考虑学生的行为特征和学生的成绩，根据学生行为特征将该样本集聚为3类（90<优<100，70<良<90，60<中<70），据学生成绩将学生聚为4类（90<优<100分，80<良<90，60<中<70，0<差<60），那么这200个样本就被聚为34=12类。聚类结果如表1所示：
表中的两位数字中，首位代表学生行为特征，次位代表学生成绩。比如类别号00，代表学生行为得分是优，成绩得分也是优。通过表1可以看出各子类聚集的样本数差别比较大，具体说明如下：
（1）样本数为0或者很少。如03类型，出现的概率为0，说明学生行为特征得分在90分以上而学生成绩不及格的同学不存在；
（2）样本数多。如11类型出现的概率大，说明学生行为特征得分在80分以上90分以下的同学，其学习成绩也不会太低。
样本数多的子类客观上反映了学生的行为特征和学生成绩有一定的联系，应作为典型的子类模式。而又考虑到训练样本集的等级全面性，因此我们将类别号23也作为一个子类模式，由此从12类聚类结果中筛选出6个子类模式如表1所示（类别1到类别6）。
三、实例分析验证
为分析上述6个子类模式之间的显著性差异，利用160个学生样本（6个子模式涉及的样本数）使用SPSS软件进行方差检验，表2为方差检验结果（取默认值0.05）。
检验结果表明6个子类模式间具有显著性差异。这说明具有200个数据的样本用7维特征描述之后，子类间的差异被显著性的体现出来，每个子类都具有鉴别度，进一步验证了前面聚类策略及聚类结果的合理性。
以下给出了采用不同算法得到的预测分类准确率和训练时间比较结果：
实验结果显示，利用聚类之后的训练样本建训练模型，对未知样本训练精度有所提高，并且训练时间也相对提高，这说明本文提出的方法是可行的。
四、总结
在当今素质教育体制下要求学生德智体全面发展，对学生的评价如果单纯考虑考试成绩，那就是片面的，并不能真正起到帮助学生的目的。因此要想使学生的能力得到有效的提高，教师除了要教好书本知识之外，更不能忽视对学生心理活动的指导，只有这样才能达到双赢的效果。而对于学生数据比较多的情况，如果所有的数据都一一分析势必会费时费力，效率也不高。本文提出的这种基于聚类策略的支持向量机分类方法，不仅能对学生评价做到合理的分类，更能简化数据样本，提高效率提高分类预测率，对日后学校的教学工作将会起到很大的帮助作用。
参考文献：
[1]李倩.美国大学教师教学评价研究—以MIT为例[J].大连理工大学，2008：3-5.
[2]肖远军.CIPP教育评价模式探析[J].教育科学，2003，03：42-45.
[3]中译本，李国正等译.《支持向量机导论》[M].北京电子工业出版社，2003：1-139.
[4]邓乃扬，田英杰.数据挖掘中的新方法-支持向量机[M].北京：科学出版社，2004.
[5]Platt J.C.，Cristianini N.，and Shawe-Taylor J.，”Large margin DAGs for multiclass classification，”in Advance in Neurua Information Processing Systems.Cambridge，MA：MIT Press，2000，vol.12，PP.547-553.
支持向量机方法论文 篇7
统计学习理论是一种专门研究小样本情况下机器学习规律的理论, 在统计学习理论基础之上发展起来的支持向量机 (Support Vector Machine, SVM) 是统计学习理论中最年轻的内容。
1.1 统计学习理论
统计学习理论的一个核心概念就是VC维, 它是描述函数集或学习机器的复杂性或者说学习能力的一个重要指标, 在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、推广性能等的重要结论。统计学习理论为解决有限样本学习问题提供了一个统一的框架, 它能将很多现有方法纳入其中, 有望帮助解决许多原来难以解决的问题;同时, 在这一理论基础上发展了一种新的通用学习方法--支持向量机, 它已表现出很多优于己有方法的性能。
1.2 支持向量机 (SVM)
支持向量机的重要理论基础是统计学习理论的VC维理论和结构风险最小化原理。SVM根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷, 以期获得最好的推广能力。SVM可以自动寻找对分类有较好区分能力的支持向量, 由此构成的分类器可以最大化类与类之间的间隔。
支持向量机主要优点包括:
(1) 它是专门针对有限样本情况的, 其目标是得到现有信息下的最优解, 而不仅仅是样本数目趋于无穷大时的最优值;
(2) 算法最终转化为一个二次型寻优问题。从理论上说, 得到的将是全局最优点, 解决了在神经网络方法中无法避免的局部极值问题;
(3) 算法将实际问题通过非线性变换到高维的特征空间, 在高维空间中构造线性判别函数以替换原空间中的非线性判别函数, 这样能保证机器有较好的推广能力, 同时它巧妙地解决了维数问题, 算法复杂度与样本维数无关。
SVM算法有很多成功的应用领域, 如人脸识别、手写体识别、指纹识别等。这些应用都说明了基于VC维理论和结构风险最小化原理而发展起来的结构化学习方法的潜在优势。
2 SVM训练算法
V.Vapnik等人首先提出来的是chunking算法:从训练样本中任意选择一个小的子集, 求此子集的最优解, 保留此子集的支持向量, 从剩余的样本中启发式地加入新的子集, 再求解新子集的最优, 反复迭代直至收敛。但chunking算法需求的内存空间受所解决问题的支持向量数目的限制, 当问题的支持向量数过大时, 子问题的求解也很困难。
Osuna提出一种新的分解算法———固定工作样本集方法克服了上述限制:选择一个固定大小的工作集B, 求解B上的 (quadratic problem) QP问题, 考察所有不满足KKT条件的样本, 启发式地选择一些样本与集B中对应优化变量的样本交换, 反复迭代直到所有的样本都满足KKT条件, 每一个QP子问题仍然使用迭代数值优化算法求解。Osuna证明每次迭代使目标函数单调递增, 因为目标函数有上界, 所以经过有限次迭代后算法将收敛并得到最优解, 但最优解在一般情况下并不唯一。
针对Osuna提出的分解算法的收敛速度慢的不足, Joachims提出了几点改进:第一, 对工作集B的选择进行了改进, 它采用基于Zoutendijk的方法, 利用目标函数的一阶近似信息来找到仅包含|B|个非0元素的目标函数的最速下降方向, 从而在当前迭代中取得最大的进展, 进而加快收敛速度。第二, 针对许多问题中支持向量数远远小于训练样本数以及对于训练样本集被噪声污染后, 存在很多的支持向量, Joachims提出了Shrinking方法, 该方法是基于这样的事实:在优化过程中, 某个变量最终不能够成为支持向量或者成为边界支持向量在很早就能够清楚。因此, 该方法通过提前估计哪些变量最终可能成为非支持向量或边界支持向量, 从而在进一步优化过程中删除这些变量, 使优化规模减少, 进而提高优化速度。第三, 针对每次迭代中最耗时的是Hessian矩阵Q中行的计算, 为了避免重复计算, Joachims提出了Caching方法来减少每次迭代中的计算量。这是一种在内存耗费和训练时间上的折衷方法。
3 支持向量机的研究现状
对Platt的SVM算法, S.S.Keerthi等通过对SVM算法的分析提出了重大改进, 即在判别最优条件时用两个阈值代替一个阈值, 从而使算法更加合理快捷, 并给出了收敛性的证明。通过实际数据库的对比, 证明确实比传统SMO算法快。同时也指出SMO算法应用于回归时类似的问题。R.Cooloberetc将上述改进的SMO算法应用于分类和回归问题, 实现了比SVMcight更强的软件包。
有些方法是考虑训练样本顺序加入, 同时考虑其对支持向量有何影响。Ahme提出基于感知机中的Adatron算法, 采用梯度法对Lagrange系数进行改变。Poggio提出了另一种梯度顺序算法, 特点是将SVM原问题中的偏置b也看作系数, 从而使该梯度算法适合软间隔 (Softmar-gin) 和回归情形。
另一种对算法的研究方向是在线训练, 即支持向量机的训练是在训练样本单个输入的情况下的训练。它和训练样本顺序加入的方法的区别是训练样本的总的个数是未知的。最典型的应用是系统的在线辨识。Keerthi S提出了在线训练的精确解, 即增加一个训练样本或减少一个样本对Lagrange系数和支持向量机的影响, 实验表明算法是有效的, 特别是减少一个样本时, 对模型选择算法LOO (Leave one out) 的形象解释。缺点是当样本无限增多时, 必须抛弃一些样本, 使其能够实用。
由于统计学习理论和支持向量机建立了一套较好的有限样本下机器学习的理论框架和通用方法, 既有严格的理论基础, 又能较好地解决小样本、非线性、高维数和局部极小点等实际问题, 因此成为20世纪90年代末发展最快的研究方向之一, 其核心思想就是学习机器要与有限的训练样本相适应。目前SVM研究中仍需要解决的一些难点, 包括如下的一些方面:
(1) 核函数和参数的构造和选择缺乏理论指导。核函数的选择影响着分类器的性能, 如何根据待解决问题的先验知识和实际样本数据, 选择和构造合适的核函数、确定核函数的参数等问题, 都缺乏相应的理论指导。
(2) 训练大规模数据集的问题。如何解决训练速度与训练样本规模间的矛盾, 测试速度与支持向量数目间的矛盾, 找到对大规模样本集有效的训练算法和分类实现算法, 仍是未很好解决的问题。
(3) 多类分类问题的有效算法与SVM优化设计问题。尽管训练多类SVM问题的算法已被提出, 但用于多类分类问题时的有效算法、多类SVM的优化设计仍是一个需要进一步研究的问题。
参考文献
[1]Vapnik V N.The nature of statistical learning theory[M].New York:Spring, 1995.
[2]V.Vapnik and A.Chervonenkis.The Necessary and Sufficient Condi-tions for the Uniforms Convergence of Averages to Excepted Values.1971.
[3]邓乃扬, 田英杰.数据挖掘中的新方法——支持向量机[M].北京:科学出版社, 2004.
支持向量机方法论文 篇8
本课题通过对m i R N A生物学规律的分析以及对现有研究成果进行总结的基础上,把支持向量机方法引入到miRNA预测中来,避免现有方法中人为设置参数,提高了利用计算机方法预测miRNA的准确率,在基于支持向量机的miRNA预测模型的特征选择、向量表示、核函数选择和参数选择方面展开研究。
1 样本的选择与生成
样本选取不仅要能使预测模型正确反映miRNA的特征,而且还要能使预测模型具有良好的计算性能。课题选择水稻、拟南芥、玉米的miRNA进行数据实验。实验验数据由训练集和测试集组成,训练集和测试集均由正样本和负样本两部分组成,其中,正样本是经过生物学实验验证,已知的m i R N A序列及其前体;负样本为非miRNA序列,课题中是由计算机程序随机产生的序列。
本文训练集的正样本由水稻(Oryza sativa)和拟南芥(Arabidopsis thaliana)的m i R N A基因及其前体组成,共选取了132条水稻miRNA基因及其前体、218条拟南芥miRNA基因及其前体,同时利用计算机程序,随机产生了300条序列作为训练集的负样本。测试集的正样本由96条已知的玉米(Zea mays)miRNA基因及其前体组成,负样本由随机产生的300条序列组成。以上所有已知的miRNA基因及其前体均从miRNA研究网站miRBase[4]上获得。
利用计算机程序随机产生负样本的依据和规则是:所有已报道的成熟miRNA长度在17～29nt,其中大多数在21～25nt,成熟miRNA茎环结构前体长度基本在80～290nt之间,其中植物miRNA前体长度一般在250nt左右,miRNA前体中配对的核苷酸数目在35～125对之间。课题为使样本更具一般性,利用随机数方法生成长度位于19～25nt之间的mi RNA序列负样本。同时,计算机程序随机产生的是miRNA负样本,该序列不存在前体,本文中为了使样本的长度和真实序列的长度更相近,利用随机数方法产生配对核苷酸数目位于35～125对之间的miRNA前体二级结构信息的负样本。
2 miRNA样本序列的编码和归一化
通常在ncRNAs的基因中只有微弱保守的启动子和终止子信号[5],为使用计算方法预测m i R N A前体,需要定义能把已知miRNA序列和随机基因序列区别开来的序列和结构属性,并使用这些属性作为约束在目标基因序列中检测候选miRNA。对于miRNA计算识别难点在于已知的miRNA基因数量较少,miRNA序列只能在核苷级别上比较,而且miRNA序列非常短。当搜索miRNA弱保守基因时,即便对于那些存在大RNA族的情形,序列保守性也通常在二级结构这一级,也就是说,所保守的是碱基配对而不是单个碱基序列。因此,仅进行序列比对无法识别在初级序列上差异很大,而碱基配对结构相似性较大的miRNA。基于此,在特征提取时应当考虑m i R N A前体的二级结构信息,预测时将miRNA一级结构信息和二级结构信息融合起来,以提高预测的准确率。
由于课题中面对的是字符串序列(RNA序列),为了利用支持向量机方法,一个重要的任务是对样本数据进行合适的特征映射,将字符串序列映射为数字序列,以满足支持向量机的要求。下面探讨如何对miRNA及其前体进行特征映射,以及在特征映射过程中的R T L碱基配对识别算法。
本文对miRNA初级序列做如下编码:
A---1 C---2
G---3 U---4
同时,为了捕捉二级结构的信息,首先使用RNAFold[6]预测miRNA前体的二级结构。为了将miRNA前体二级结构的信息从字符串序列映射为数字序列,对二级结构中可能存在的碱基配对作如下编码:
A:U---5 U:A---6 G:C---7
C:G---8 G:U---9 U:G---0
错配的核苷酸不予考虑。
由于miRNA前体经过RNAFold计算输出的结果是如图1所示的左右括号序列,从该序列中,不能直接得到miRNA前体二级结构的碱基配对信息,必须设计碱基配对识别算法,从RNAFold的输出序列中获取miRNA前体二级结构的碱基配对信息,并按照上述碱基配对编码将其映射为数字序列。本文设计了RTL(Right to Left)碱基配对识别算法,获取miRNA前体二级结构的碱基配对信息,具体算法描述如下:
a)定义两个字符变量,分别为左游标和右游标
b)左游标从序列的结尾开始,自右向左扫描,直至遇到“(”停止
c)将当前左游标地址值加1赋给右游标
d)右游标开始扫描,直至遇到“)”停止,并删除扫描到的“)”
e)左游标继续向左扫描,直至遇到“(”停止
f)将当前左游标地址值加1赋给右游标
g)右游标开始扫描,直至遇到“)”停止,并删除扫描到的“)”
h)左游标从上次停止继续向左扫描,直至遇到“(”停止
i)回到步骤e,直至左游标到达序列的首字符,算法结束
例如,利用RNAFold预测水稻的osaMIR156h miRNA前体的二级结构如图1所示,经过RTL算法解析后,对应的二级结构编码如表1所示。
在图1中忽略环和茎部起始失配部份,因为它们变化大且保守性低。经过对初级序列的编码映射和对二级结构碱基配对解析后,得到了一个如图2所示的输入序列的概念视图,图中每个输入有2个成分:miRNA初级序列、miRNA前体二级结构编码序列,其中向量x11,x12,……,x1n是mi RNA初级序列的编码,向量x21,x22,……,x2n是miRNA前体二级结构信息的编码,这样,输入信息既包含了m i R N A的初级结构的信息又包含了其前体的二级结构信息。
最后将处理后的样本数据封装成支持向量机能够识别的数据格式:
其中,label为分类标记,本文为两类分类问题,以+1标记证样本,-1标记负样本;index是特征向量的编号,本文中为连续的整数1,2,3……;value为特征值,本文中为miRNA及其前体二级结构碱基配对的编码。对封装后数据使用svmscale进行归一化,具体命令如下:
其中,-l:数据下限标记;lower:缩放后数据下限;-u:数据上限标记;upper:缩放后数据上限;-y:是否对目标值同时进行缩放;y＿lower为下限值,y＿upper为上限值,缺省值:lower=-1,upper=1,表示没有对y进行缩放;-s save＿filename:表示将缩放的规则保存为文件save＿filename;-r restore＿filename:表示将缩放规则文件restore＿filename载入后按此缩放;filename:待缩放的数据文件。
3 基于支持向量机的miRNA预测模型
3.1 支持向量机的miRNA预测模型
支持向量机(S V M)的基本思想就是:通过某种非线性映射,将输入空间的输入向量映射到一个高维特征空间,在这个高维特征空间中,构造最优分类超平面或者线性拟合函数。课题结合m i R N A生物学特征,给出了基于支持向量机的m i R N A预测过程模型。模型由样本选择、样本归一化、特征选择、特征的向量表示、S V M预测、预测结果评估六个模块组成。其中样本选择是依据有些物种间的m i R N A具有高度保守性;样本预处理是按照支持向量机输入序列的要求,对所选样本进行归一化;特征选择即根据现有研究成果以及对m i R N A特征的分析,选择对预测结果贡献大的m i R N A特征;特征的向量表示是把所选m i R N A特征,映射为支持向量机能够识别的输入向量;SVM预测即选择合适的核函数及参数对输入序列进行预测;预测结果评估是对模型采用不同核函数及参数预测的结果进行分析、评估。各个模块的功能下面将详细介绍,模型的总体结构图如图3所示。
3.2 miRNA预测模型的训练
本文采用LIBSVM利用第一节所述的训练集样本,对模型进行训练,具体语法为:
其中,options表示支持向量机的操作参数,例如“-s”代表支持向量机的类型,默认值为0;“-n”:设置n-SVC、oneclass-SVM与n-SVR中参数n,默认值0.5;“-t”代表核函数的类型,1代表多项式核,2代表RBF核,3代表Sigmoid核等。training＿set＿file是要进行训练的数据集;model＿file是训练结束后产生的模型文件,该参数如果不设置将采用默认的文件名,也可以设置成自己惯用的文件名。
3.3 miRNA预测模型对测试集的预测
基于支持向量机m i R N A预测模型可利用训练结果模型对测试集进行预测,具体命令为:
其中,options为操作参数,例如,“-b”表示是否需要进行概率估计预测,可选值为0或者1,默认值为0,即不对预测的结果进行概率估计预测,本文取0值。model＿file是由svmtrain训练产生的模型文件;test＿file是要进行预测的数据文件;output＿file是svmpredict的预测结果输出文件,记录预测的结果值。
4 miRNA预测模型核函数的选择
目前主要的核函数形式有线性函数、多项式函数、径向基函数(R B F函数)、Sigmoid函数四类。线性核是RBF核的特例,如果模型选择RBF核,就没有必要再考虑线性核了。采用sigmoid核函数的矩阵不一定会正有界,而且通常它的准确性也不如RBF核[7]。本课题中选择RBF核函数和多项式核函数,关于它们的预测准确率及相互比较将在后续章节介绍。多项式核函数和RBF核函数的公式表示如下所示:多项式函数:式中d是多项式的阶次。
径向基函数(RBF函数):
5 miRNA预测实验结果分析
5.1 多项式核函数预测结果
采用第一节所述样本,训练集样本总数分别为400、500、600,训练集正负样本比例为1:1、1:2、1:3、3:2时,对第一节所述测试集预测的准确率如图4所示,其中对样本的归一化以及对模型进行训练、测试的过程如前面章节所述。
从以上的数据可以看出:在使用多项式核为SVM核函数时,不同参数d下多项式核函数的支持向量机对样本的预测准确率与训练集中正负类样本的比例相关,与训练集样本总数量关系不大。在正负样本比例为1:2、1:3,d=1时,有较高的预测准确率,并且预测准确率很相近,由此可以看出本文所建模型对负样本具有良好的识别能力。
5.2 多项式核有无偏移量r的预测结果比较
对第一节所述样本,在核函数为多项式核,样本数为500时,正负样本的比例及预测准确率的比较如表2所示。
从上面的比较可以看出,采用多项式核函数的预测结果与其偏移量参数r有很大相关性。在本模型中,当训练集中负样本多于正样本时,应取r为非零值;反之,则应取r为零值。
5.3 RBF核函数与多项式核函数预测准确率比较
从第一节所述的训练集正样本中随机选取实验所需正样本,负样本利用程序随机产生,正负样本比例均为2::1,训练集按增量进行方式训练学习,样本总数分别为300、450、600、750、900,得到的各情况下RBF核与多项式核学习机预测结果比较如图5所示。
从图5的比较可以看出,在本模型中,RBF核函数比多项式核函数具有更高的预测准确率。
6 结束语
本文通过对m i R N A现有预测方法和支持向量机相关理论的研究,利用miRNA及其前体的生物学特征,构建了基于支持向量机的miRNA预测过程模型,使用拟南芥和水稻的miRNA及其前体对核函数和参数进行训练,利用已训练的核函数和参数预测了玉米的miRNA,当采用RBF核函数和多项式核函数时,预测准确率均达到了95%以上。
摘要：本文从miRNA及其前体的生物学特征出发,在对支持向量机理论及其应用特点进行研究的基础上,构建了基于支持向量机的miRNA预测过程模型,在miRNA特征的向量表示、miRNA特征选择、预测模型核函数及参数选择方面进行了研究。以水稻、拟南芥、玉米的miRNA为实例,对基于支持向量机的miRNA预测方法的预测准确率进行了验证,实验结果表明该方法预测准确率达95%以上。
关键词：支持向量机,miRNA,机器学习
参考文献
[1]WANG X J,REYES J L,et al.Prediction and identification of Arabidopsis thaliana microRNAs and their mRNA targets[J]Genome Biology.2004,5(9):R65.1-15
[2]纪虹,孙开采,miRNA的研究现状[J].国际遗传学杂志.2006,29(1):30-34
[3]LAI E C,TOMANCAK P,WILLIAMS R W,et al.Computational identification of Drosophila microRNA genes[J].Genome Biology.2003,4(7):R42.2-20
[4]http://microrna.sanger.ac.uk/sequences/ftp.shtml
[5]Barciszewski J,Erdmann V A.Noncoding RNAs:Molecular Biology and Molecular Medicine[J]New York:Kluwer Academic.2004.33-48
[6]Hofacker I L,Fontana W,Stadler P F,et al.Fast folding and comparison of RNA secondary structures[J].Monatshefte fir Chemie.1994,125(2):167-188
支持向量机方法论文 篇9
关键词：支持向量机,贝叶斯判别,分类,消费者行为分析
0 引言
消费者行为学在20世纪60年代中后期是一个相对较新的领域。随着“大数据”时代的到来, 越来越多的学者意识到通过沉淀数据进行消费者行为分析的重要性。目前来讲, 用于客户消费行为分析的主要方法有:层次分析法, 聚类, 贝叶斯网络等。
本次研究通过广东烟草的实地调研数据, 利用支持向量机方法, 区分低档品牌的购买群体行为模式、普通品牌的购买群体行为模式、高档品牌的购买群体行为模式。在研究过程中, 首先是计算商品的价格分布, 判断区分低档、普通、高档品牌, 再利用二叉树多类分类方法与并行计算方法帮助提高支持向量机运算精度, 利用Matlab构建一个平台进行支持向量机的训练与预测, 并将该方法与贝叶斯判别的分类效果进行比较, 判断支持向量机的分类精度。
1 基于支持向量机的烟草消费行为分类模型
支持向量机 (SVM) 是Cortes等人于1995年提出的, 它在解决小样本、非线性以及高维模式识别中表现出许多特有的优势, 并能推广应用到函数拟合等其它机器学习问题中。多分类支持向量机是众多算法中的一种。多分类支持向量机是将SVM从两分类算法推广到多分类的算法。常用的算法有一对多, 一对一, 二叉树, 有向无环图四种。
1.1 模型设计
由于将烟草客户分类为:普通品消费者、低档品消费者、高档品消费者三类, 所以选择合适的多类分类方法能有效地提高支持向量机。支持向量机的多分类问题往往由几个两分类问题来解决。商品品牌的分类结构示意如图1所示。
所以本论文选取一对一的多类分类方法结合二叉树分类来解决烟草消费者行为分析的分类问题, 根据投票确定最后的分类结果。操作流程为:①收集到某个消费者的相关信息;②利用低档与非低档的支持向量机作为第一层SVM进行分类;③若分类结果为低档, 则其低档的分类结构投一票;④若分类结果为非低档, 利用普通与高档支持向量机继续为其分类, 得到的普通或高档结果投一票;⑤将高档与非高档, 普通与非普通作为第一层SVM重复②-④步骤;⑥根据最终投票结果, 确定这个消费者的分类归属。
本次烟草消费者行为研究的数据规模较大, 所以在这种大规模数据的条件下, 必须采取有效的数据策略加快运算速度。所以在模型中并行计算方法为将总问题切割成小规模问题, 利用计算机的并行技术进行求解。
所以为了使得支持向量机能更好地学习与区分消费者行为, 针对消费者的这种行为模式引入商品分类策略。在广东烟草市场上, 我们搜集到各种不同品牌旗下最低商品的价格, 计算其总体价格分布函数F (x) 。
根据历史数据和经验设定相应的高低分位数阀值α1和α2。当然阀值是依靠经验给出来的, 并没有理论上的必然的理由。一个模型的表现, 有很大一部分决定于参数选取是否合理, 是否表现了市场的真实状况。因此, 我们选取参数时会结合相关的行业经验从历史经验的角度来观察。借助阀值就可以帮助我们清晰地判别商品所处的种类。
具体过程如下:①收集市场中的烟草商品, 对其价格求分布函数F (X) ;②根据历史数据和经验确定商品状态的高低阀值α1和α2;③根据求得的价格走势强度和所设定的阀值确定此时的商品状态:
当F (X≤x) <α1时, 则可定义为低档商品;
当1-F (X≤x) <α2时, 则可定义为高档商品;
当a1≤F (X≤x) <α1时, 则可定义为普通商品。
这样我们就可对商品市场有个清晰的研判, 然后根据不同的商品属性进行消费者行为的划分。
本文分别针对低档商品、普通商品、高档商品训练得到相应的支持向量机, 这样在判断出当时所处的市场状态后, 就可采用相应的消费行为模式识别。
1.2 支持向量机的操作过程
本论文选取一对一的多类分类方法结合二叉树分类来解决烟草消费者行为分析的分类问题。
在支持向量机模型的操作过程中, 要重点讨论的是核函数与惩罚函数。
常用的核函数包括以下三种:
①多项式核函数:
K (x, xi) = (x·xi+1) d其中d是多项式的阶次。
②Gaussian核函数:
其中σ是核宽度参数。
③Sigmoid函数:
其中, v为一阶常数, c为偏置顶。
除去上面三种核函数以外, 特殊场合还可以编写特殊的核函数。在解决烟草用户行为分析的案例中, 对核函数的选择是一个重要的问题。解决方法为将各个核函数遍历一遍后, 选择能最优拟合样本数据的核函数。
现实世界中的消费者行为, 受到复杂的个人性格、成长环境、年龄、社会阶层等各个方面的影响。是个高维度, 高噪音, 不确定的系统。所以整个数据集中的各类数据受到的干扰很大, 可能导致各类数据不能完全地被超平面分开。
为了衡量SVM网络的分类精度的高低, 根据一般的原则, 本位采用测定分类正确率作为评定指标:e=正确分类值数量/测试样本总数。并选取不同的核函数进行比较。
另外, 本次试验也将选取贝叶斯判别方法与SVM的分类精度进行比较, 从而更好的观察支持向量机的分类效果。
2 基于贝叶斯判别 (Bayes) 的模型
贝叶斯 (Bayes) 判别首先会利用一个先验概率来描述对研究现象已有的认识, 然后通过样本来修正先验概率, 得到后验概率, 最后基于后验概率进行分类与判别。贝叶斯判别方法具体如下:
设有k个p维总体G1, G2, …, Gk, 概率密度函数分别为f1 (x) , f2 (x) , …, fk (x) 。假设样本品x来自总体Gi的先验概率为pi (i=1, 2, …, k) , 则有p1+p2+…+pk=1。根据贝叶斯理论, 样品x来自总体Gi的后验概率 (即x是已知时, 样品x来自总体Gi的概率) 为:
在不考虑误判代价的情况下, 有以下的判别规则:
若考虑误判代价, 表示根据某种判别规则可能判归Gi (i=1, 2, …, k) 的全体样品的集合, 用c (j|i) (i, j=1, 2, …, k) 表示将来自Gi的样品x误判给Gj的代价, 则有c (j|i) =0。将来自Gi的样品x误判给Gj的条件概率为:
可得任一判别规则的平均误判代价为:
使得平均误判达到最小的判别规则为:
以上判别规则可以这样理解:若样品判归Gi的平均误判代价比判归其他总体平均误判代价都要小, 这样就将样品归于Gi组。
3 实证数据分析
本实验的数据来自对广东省17个地市 (不含深圳) 城镇、农村两个层面消费群体的烟草消费调研, 较真实地了解广东省卷烟消费者对卷烟的品牌、包装、口味、价格、购买动机等影响卷烟消费行为的因素以及相关市场情况。经过数据收集、数据录入、数据预处理、卷烟品牌分类、基于支持向量机的多类分类分析等步骤进行实证数据分析。
4 实验结果
支持向量机的多类分类依靠几个二分类模型才能实现, 在本次试验的多类分类模型设计中, 共需要训练6个SVM, 整个支持向量机的分类结构, 已经在图1中阐述。
低档与非低档分类中, 准确分类的精度达到了96%。普通与非普通分类中, 准确分类的精度达到了86%。高档与非高档分类中准确分类的精度达到了88%。低档与高档分类中准确分类的精度达到了96%。低档与高档分类中, 只选取训练集中的低档品牌消费者和普通档品牌消费者各作为一类, 分类的精度达到了95%。普通与高档分类中, 只选取训练集中的普通品牌消费者和高档品牌消费者各作为一类, 分类的精度达到了88%。
从上面所有的支持向量机训练期分类结果可以发现, 所有支持向量机训练期的精度都较高。一方面, 作为机器学习的算法可能存在过拟合的现象;另一方面, 也说明了作为消费者而言, 不同档次的消费者的差异可区分度较大。根据模型设计, 支持向量机在分类总体完成后, 预测期内对模型的预测效果进行检验。不同参数与模型的比较结果如表1所示。
从表1中可以看到, 支持向量机在预测期分类的预测准确率达到64.98%, 大于贝叶斯判别的分类准确率45.23%, 体现了其在分类上的先进性。
我们再将所有的调研数据按区域 (地级市为单位) 划分, 得到的分类如图2所示, 将两种方法得出结果分别求算术平均值, 结果如表2所示。
从图2和表2, 我们可以看到, 在按城市区分之后, SVM的分类准确率有一个提升, 平均分类准确率达到了77%, 远远高于贝叶斯判别的准确率45%。进行城市区分之后分类准确率更高, 这个一方面更加确保支持向量机在分类上的一个有效性;另一方面也说明, 不同城市的烟民在购买卷烟的行为也有着不同模式。
5 总结与展望
本文的研究, 希望利用支持向量机模型在分类上的天然优势, 可以将不同的行为模式区分开来。由于消费者行为的产生取决于多方面不同的因素, 而消费者对品牌的敏感性一直是学术研究中的一个重点与难点。
本文利用并行计算, 二叉树多类分类方法提高支持向量机的运行效率。从研究的结果来看, 运用该方法的广东省内的分类准确率明显的优于贝叶斯判别的分类。这说明支持向量机模型在烟草消费行为分析中有一定的有效性。另外, 将不同城市区分开后单独用支持向量机进行消费者行为分析, 更加进一步的确定了支持向量机的分类确实比其他分类更有优势。当然, 本研究在以下几个方面仍需要更深度的挖掘:
①如何有效地将两类问题的解决办法推广至多类问题, 一直是支持向量机研究的一个重要方向。在未来的研究中, 需要一种能直接多类的模型, 以防止二分类时出现不可分现象是十分必要的。
②消费者偏好与测量方法是比较复杂的。本文的由于消费者行为影响因素很难量化, 如何将定性化与定量化的指标结合, 共同利用支持向量机方法进行数据挖掘, 也是下一步需要研究的方向。
参考文献
[1]范秋英, 方醒.基于层次分析法的网上消费者行为分析[J].物流工程与管理, 2013, 01:121-122.
[2]郭磊, 陈进, 朱义, 肖文斌.小波支持向量机在滚动轴承故障诊断中的应用[J].上海交通大学学报, 2009, 04:678-682.
[3]汪海燕, 黎建辉, 杨风雷, 等.支持向量机理论及算法研究综述[J].计算机应用研究, 2014, 31 (5) .
[4]王孟磊.基于模糊聚类-ABC控制法的百货企业市场细分研究[J].价值工程, 2014, 16:198-199.
[5]B.Baesens, S.Viaene, D.Van den Poel, J.Vanthienen, G.Dedene, Bayesian neural network learning for repeat purchase modeling in direct marketing[M].European Journal of Operational Research, 2002 (138) :191-211.
[6]G.Cui, M.L.Wong, H.-K.Lui, Machine learning for direct marketing response models:Bayesian networks with evolutionary programming[J].Management Science, 2006 (52) :597-612.
支持向量机方法论文 篇10
隧道围岩分级是针对爆破、开挖、支护、编制定额等工程要求,而对隧道围岩按照其工程地质条件进行的稳定性分级,以满足隧道设计、施工以及编制定额的需要。
隧道围岩具有以下特点:1)由于隧道岩体经历不同期次的构造作用以及浅、表生作用,岩体中存在大量软弱结构面,从而使岩体具有各向异性、非均质性[3]。2)隧道岩体通常赋存于地应力、地下水等复杂地质环境中,不同地应力环境中岩体的力学响应不同,而地下水渗流场和岩体应力场二者耦合共同决定了岩体的复杂空间应力状态。3)隧道围岩在施工中要经历开挖、爆破、卸荷、回填等工程处理,这些扰动使得围岩的力学性质表现出更加复杂的时间和空间形态。
综上所述,隧道围岩本质上是一个非线性非平衡开放系统,表现为结构的无序、不稳定、不平衡以及时空的不可逆和非对称,从而使隧道围岩的工程地质性质及其力学行为具有不确定性,面临“参数给不准”和“模型给不准”两大瓶颈问题,而这是传统的基于经验的围岩分级方法暂时无法解决的[4]。
面对隧道围岩的高度复杂性和非线性特点,使得隧道围岩稳定性评价的确定性理论在准确性和可靠性方面受到一定限制。而作为智能科学领域的支持向量机具有对高度非线性和复杂性系统无限逼近能力的优点,使得支持向量机可以成为隧道围岩分级的强有力工具。
1 支持向量机网络模型结构及算法原理
支持向量机网络(Support Vector Mochine)的数学理论基础是统计学习理论的VC维理论和结构风险最小原理,主要理论内容是1995年由Vpnik提出的[3]。其基本思想就是通过事先选择好的某一个非线性变换,将输入向量映射到高维特征空间中,在特征空间中构造一个最优分类超平面,使不同类别之间的隔离边缘最大化,而这个分类超平面由支持向量决定。支持向量机网络模型的最大优点是在有限样本的情况下仍能得出精确的预测结果(见图1)。
BP神经网络和RBF神经网络的理论基础都是传统统计学,只有在训练样本数据足够多甚至趋近于无穷大时,经验风险才有可能趋近于期望风险,但实际上训练样本数据都是有限的,有时甚至是不足的,所以BP神经网络和RBF神经网络经常出现过学习现象,模型的泛化能力不高。基于传统统计学理论的学习机器,如BP神经网络和RBF神经网络,模型的泛化能力与样本数目和研究系统的复杂性有关,而且始终存在学习精度和泛化能力之间的矛盾。
2 隧道围岩工程地质特征定量化
建立基于支持向量机网络的隧道围岩分级模型,首要一步是建立起围岩分级指标体系并予以向量化。本文主要从隧道围岩的岩块强度、岩体结构、岩体完整性、岩体受地质构造影响程度、岩体结构面发育情况、控制性结构面与隧道轴线的关系以及地下水状态等方面建立分级指标体系。
由于这些数据大部分都是定性的描述,为了建立定量模型的需要同时也要符合工程地质分析的习惯,需要对分级指标数据作定量化处理。具体操作方法是采用“1”和“0”的组合向量来分别表示某一工程地质属性的有无,如极硬岩可用(0,0,0,0,1)表示,硬岩可用(0,0,0,1,0)表示,较软岩(0,0,1,0,0)表示,软岩(0,1,0,0,0)表示,极软岩(1,0,0,0,0)表示,其他分类指标的定量化以此类推。
依据以上建立的围岩分级指标体系,在充分调研文献资料和隧道施工设计资料的基础上,收集整理了93组具有代表性的隧道围岩分级数据作为基于人工神经网络的围岩分级模型的样本数据,向量化后为93组44维数据。
由于定性数据的测量误差较大,所以选定83组数据作为训练样本建立分类模型,最后用10组数据作为预测样本用来评价分级模型的分级准确性。
3 支持向量机网络设计过程
1)核函数类型的选择。
支持向量机网络的核函数类型一般有线性核函数、多项式核函数、径向基核函数和Sigmoid核函数。研究表明核函数的选择对支持向量机网络的性能影响不大。但是选择合适的核函数可以减小分类模型的计算量。综合考虑核函数的核参数数目、特征空间的非线性变换以及维数灾难,最终选取高斯径向基核函数。
2)核参数的选择。
高斯径向基核函数的核参数主要有中心向量和宽度系数,支持向量机网络模型要求解的支持向量就是中心向量,由算法自定选定;而宽度系数σ2表征神经元的感知阈,影响改变样本特征空间的复杂程度,过大过小都不合适而且与惩罚因子C共同决定分类模型的结构风险,本文通过网格搜索寻找最优宽度系数和惩罚因子。
3)惩罚因子C的选择。
惩罚因子C用来控制错分样本的惩罚程度,在错分样本的比例和模型算法复杂性二者之间寻求折中,其值大小最终影响分类预测模型的复杂程度。同样,惩罚因子C的选择也存在一个优化问题,过大过小皆不合适,而且与宽度系数σ2共同决定分类模型的结构风险,需要对二者同时协调优化,详细过程见图2。
4)数据的处理。
数据的处理包括对输入数据的处理即前处理和输出数据的处理即后处理。由于多分类支持向量机本是基于二分类支持向量机发展而成,所以本文支持向量机网络模型的样本数据采用1～5五个数字分别代表五个围岩级别,而且不做归一化处理。
基于以上所述,本文采用网格搜索法先粗搜后细搜,对宽度系数和合惩罚因子同时协调优化,最终选择宽度系数和合惩罚因子的最优组合值作为分类模型的参数(见图3),采用训练样本数据的分类正确率和预测样本的分类正确率分别表征网络模型的经验误差和泛化能力。
4 支持向量机网络模型围岩分级结果
通过一系列优化设计,最终确定:支持向量机网络的核函数采用高斯径向基核函数,宽度系数取0.015 625,惩罚因子取181.019 3;样本数据一共93个,训练数据83个,仿真预测数据10个。最终预测结果见表1和图4。
通过上面的围岩分级结果分析可知,支持向量机模型分级模型对10个预测样本的分级正确率为90%,唯一一个误判的是样本89,将Ⅳ级误判为Ⅲ级,但是误差不超过一级;表明支持向量机模型基本能完全正确的进行围岩分级。
5结论与建议
支持向量机模型对围岩分级结果能够进行很好的预测,正确率达到90%,预测精度也基本满意,收敛速度明显变快。如何进一步对定量实测的工程地质指标进行建立分级模型是本文的不足,是以后需要进一步深入的工作。其次是扩散系数和惩罚系数需要通过不断试算确定最优值,虽然采用了粗细网格结合的搜索方法,但是仍然增加了建模时间,如何改进参数的寻优方法也是接下来需要解决的问题。
参考文献
[1]冯夏庭.智能岩石力学导论[M].北京:科学出版社,2000.
[2]杜时贵,周庆良.公路隧道围岩定量分类系统研究设想和建议[J].西安公路交通大学学报,1996,16(4):32-37.
[3]沈中其,关宝树.铁路隧道围岩分级方法[M].成都:西南交通大学出版社,2000.
[4]Vapnik V.Statistical Learning Theory[M].Wiley,New Yorw,NY,1998.
支持向量机方法论文 篇11
关键词：支持向量机；SVM；PRP-SVM；CGM-OC-SVM
中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)15-30814-02
A Algorithm of SVM for any Kernel
TAO Mei, Wushour·Silamu
(School of Information and Engineering Xinjiang University，Wulumuqi 830046, China)
Abstract: Taking support vector machines (SVM) and the traditional statistics classification method as the research object, introduces the classification method theory of SVM algorithms，and based on PRP-SVM，then puts forward the orthogonal adjustment conjugate gradient iteration algorithm of support vector machines (CGM-OC-SVM), meanwhile the CGM-OC-SVM algorithm is carried out by the C programming language，and doing a graphic simulation using Matlab.
Key words: Support vector machine; SVM; PRP-SVM; CGM-OC-SVM
1 引言
数据挖掘中，数据的分类与回归问题是其重要的研究对象。常用于分类和回归的方法，如Bayes 分类、Logistic 回归、神经元网络等在实现机器学习时，都是基于经验风险最小化原则的。然而，一般在有限样本的情况下，经验风险最小不一定意味着期望风险最小，在有些情况下会出现“过学习”和推广性不好等情况，得到的实验结果并不是很理想。
Vapnik 于上世纪90年代初提出的支持向量机（SVM），是数据挖掘中的一项新技术。它是在统计学习理论的基础上，借助于最优化方法解决机器学习问题的新工具。该算法是一个凸优化问题，即局部最优解就是全局最优解，这是其他学习算法所不及的。SVM 基于结构风险最小化原则，能很好地解决有限数量样本的高维模型构造和“过学习”问题，具有良好的推广性和较好的分类精确性，已被应用于人脸识别、医疗诊断等方面。
尽管SVM 的应用领域很广，但其理论研究还相对滞后，其中就包括算法本身改进和算法的实际应用。支持向量机分类器最终可以转化为解决一个二次规划问题，目前的研究大都集中于如何在训练数据较多的情况下来解决这个二次规划问题。现基于改进共轭梯度迭代PRP-SVM 算法的基础，提出一种对任何SVM 核通用的正交校正共轭梯度迭代支持向量机算法（CGM-OC-SVM），并通过程序实现此算法，利用Matlab进行算法结果的图形模拟。
2 支持向量机（SVM）
SVM与传统统计学的大样本量研究方向不同，它最大的特点是遵循“结构风险最小化原则”，尽量提高学习机的泛化能力，即由有限的训练样本集获得小的误差的特性，保证对独立的测试集有小的误差，从而解决了有限样本的“过学习”问题（即机器复杂性越高，则置信范围越大，导致真实风险与经验风险可能的差别越大）。目前，该技术已应用到手写体识别、人脸识别、指纹识别、语音识别、数据挖掘等领域。
SVM的核心理论包括：(1)VC维理论，不仅要使机器学习的经验误差最小，而且应该最小化函数集的VC维，从而控制学习机的结构误差，使SVM分类器具有较强的泛化能力；(2)引入最优超平面概念，使函数的VC维上届达到最小，而最优超平面问题可以转化为二次规划问题；(3)核空间理论，通过非线性映射将输入空间映射到高维特征空间，使低维输入空间线性不可分问题转化为高维特征向量空间线性可分问题，并通过核函数绕过高维空间，使计算在低维输入空间进行，从而不需知道非线性映射的具体形式。
2.1 线性SVM最优分界面
2.1.1 线性可分情况
假定训练数据为 个观测样本(x1,y1),(x2,y2)…(xn,yn),xi∈Rp,yi∈{+1,-1}，则存在超平面(w·x)+b=0线性可分，使训练点中的正类输入和负类输入分别位于该超平面的两侧，或者说存在参数对(w,b)，使得yi=sgn((w·xi)+b),i=1,…,n这样的超平面通常不止一个，因此，我们的目的是要找到一个最优分类超平面，使分类面经验风险最小（即错分最少），并且推广能力最大（即空白最大）。如图1中(a)、(b)所示：
图1 2-class分类
SVM问题的数学表示为：
2.1.2 线性不可分情况
2.2 非线性SVM最优分界面
在很多情况下，数据是线性完全不可分的，这就属于非线性划分问题。我们可以通过非线性映射将向量x映射到一个高维特征空间Z，在这个高维特征空间中构造最优平面或推广的最优分类超平面。即通过函数Φ:Rn→Z将所有样本点映射到高维空间，将原来的xi·xj变为Φ(xi)·Φ(yi)形式，记核函数K(xi,xj)=Φ(xi)·Φ(yi)。常见的满足Mercer条件的核函数有多项式核函数K(xi,xj)=[(xixj)+1]d和高斯径向基核函数（即RBF核）
该策略的主要思想是对N分类问题构建N个支持向量机，每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面w·b+b距离最大的那个支持向量机决定。
2.3.3 层次策略
该策略的主要思想是对N分类问题构建若干个支持向量机，且它们之间是有层次地连接成一个有向无环图的结构，分类结果根据图经过的若干个支持向量机的判别得到。
3 算法模拟
CGM-OC-SVM算法是用C语言编写的，并选择RBF核作为核函数，现应用该算法分别对平面上两点和多点训练样本点进行分类训练、算法模拟。
(1)设x,y平面上的2个训练样本点为α=(1,1),b=(2,3)
假设训练集为S={(a,-1),(b,1)}，其中a是-1类点，b是+1类点。取核参数δ=1，惩罚参数C=2时，采用改进的CGM-OC-SVM算法求解得α*=(1,1)，设定x,y平面上的一点为k=(x,y)，分类函数为：，
内层迭代次数为1，外层迭代次数为1。利用Matlab分别作其三维、二维模拟图，见图3(a)和(b)。
图3
(2)设x，y平面上的5个训练样本点为a=(3,1),b=(4,2),c=(8,0.3),d=(2,3),e=(3,4)
假定训练集为S={(a,-1),(b,-1),(c,-1),(d,1),(e,1)}，其中a,b,c是-1类点，d,e是+1类点。取核参数δ=1，惩罚参数C=2时，采用改进的CGM-OC-SVM算法求解得α*=(0.801222,0.799457,0.799498,1.200462,1.20044)，设定x,y平面上的一点为k=(x,y)，分类函数为：
内层迭代次数为1，外层迭代次数为1。利用Matlab分别作其三维、二维模拟图，见图4(a)和(b)。
图4
4 结束语
由于支持向量机是建立在统计学习理论的VC维理论和结构风险最小原理的基础上，根据有限样本在学习精度和学习能力之间寻求最佳折衷，因此具有最好的推广能力。提出的CGM-OC-SVM算法改进了PRP-SVM算法只能选择多项式核函数的缺点，具有通用性。
参考文献：
[1] 邓乃扬, 田英杰. 数据挖掘中的新方法——支持向量机[M]. 北京：科学出版社,2004.
[2] 张学工. 关于统计学习理论与支持向量机[J]. 自动化学报，2000,26(1).
[3] 黄琼英. 支持向量机多类分类算法的研究与应用[D]. 河北：河北工业大学，2005.
[4] E.Osuna, R.Freund, and F.Girosi Support Vector Machines: Training and Applications A.I. Memo 1602, MIT Artificial Intelligence Laboratory, 1997.
[5] Zhang Ling, Zhang Bo. Relationship between Support Vector Set and Kernel Functions in SVM, J.Comput.Sci.&Technol,2002,17(5):549.
[6] O Chapelle，V Vapnik et al.Choosing Multiple Parameters for Support Vector Machine[J]. Machine Learning,2002,46:131-159.
支持向量机方法论文 篇12
电子商务的迅速发展给用户带来了更多的选择商品的机会, 但是面对海量的信息资源, 用户很难在有限的时间内通过手工方式获得符合其自身需求的信息, 由此产生了所谓的“信息过载”和“资源迷向”问题。个性化推荐系统可以帮助用户从海量的信息中找到自己所需的产品, 为用户的信息浏览和产品选择带来了极大的方便。协同过滤推荐技术是目前发展最为完善、应用最为广泛的推荐技术之一。然而, 协同过滤推荐系统的工作模式存在着很大的安全隐患, 某些不良商家人为给推荐系统注入大量虚假用户概貌, 使推荐系统频繁推荐自己的商品, 而减少或不推荐竞争对手的商品。这种攻击被称为“托攻击”或“概貌注入攻击”[1]。托攻击检测技术近年来引起了学界的广泛关注, 并已成为当前推荐系统领域的研究热点之一[2]。
Vapnik等人根据统计学习理论提出的支持向量机SVM[3]方法具有泛化能力强、没有局部极小点和解具有稀疏表示等突出优点, 正成为托攻击检测领域的一种流行方法, 并取得了较好的检测效果[4]。然而目前基于支持向量机的托攻击检测方法大多未考虑对样本特征的选择问题, 实际应用中, 虽然支持向量机可以有效地处理高维数据, 但是过多不相关或冗余的特征会降低支持向量机的检测准确率[5,6]。因此, 在利用SVM进行托攻击检测之前, 必须优选出最具判别能力、信息冗余最少的检测特征集。
根据特征选择是否依赖于学习算法, 特征选择方法分为Filter和Wrapper两大类[7]。彭飞等人[8]和张逸石[9]等人将基于互信息的特征选择方法应用于托攻击检测领域。这些方法属于Fliter特征选择方法, 评估准则直接由数据集求得, 独立于学习算法, 具有计算代价小、时间复杂度低的优点, 但缺点是评估和后续学习算法的性能有较大偏差。Guyon等人[10]提出基于支持向量机的特征递归消减 (SVM-RFE) 方法是公认的效果较好的Wrapper式特征选择方法, 该方法直接利用支持向量机算法的训练准确率评估特征子集, 特征选择的降维效果好, 但因为计算代价大而效率较低。如何在不损失检测信息的前提下, 有效提取最有价值的特征信息是托攻击检测领域迫切需要解决的问题。
本文结合Filter和Wrapper的优点, 针对SVM提出一种特征选择算法, 用类别可分性作为Filter评估准则, 用SVM作为Wrapper评估方法, 为不同类型的托攻击选择有效的检测特征, 将该特征选择算法和支持向量机结合起来进行推荐系统托攻击检测。在Movie Lens数据集上与已有其他方法进行比较, 实验结果表明本文方法在特征约减和检测效果等方面具有良好的性能。
1 CS-SVM-RFE特征选择算法
特征优选的目的是将最有价值的、彼此相关性不强的检测特征保留下来。对于两类分类问题, 意味着两类样本之间的平均相似性更小, 具有更大的可分性。因此, 可以定义类别可分性度量用于表示两类样本的差异。类别可分性越大, 则两类样本间的相似性越小, 越容易分开。本文首先定义了特征的样本差异性度量和特征的类别可分性度量CS (Class Separability) , 以CS作为Filter评估准则, 以SVM作为Wrapper评估分类器, 采用递归反向特征剔除算法RFE (recursive feature elimination) 逐次优选最佳特征子集。因此, 命名此特征选择算法为基于类别可分性度量与支持向量机的递归反向特征选择算法CS-SVM-RFE (Class Separability and Support Vector Machine Recursive Feature Elimination) 。该过程的模型描述如图1所示。
具体地, CS-SVM-RFE算法主要包含4个步骤:①定义特征的样本差异性度量;②定义特征的类别可分性度量;③依据特征的类别可分性度量进行特征排序;④以支持向量机为评估方法搜索获取最优特征子集。
1.1 特征的样本差异性度量
为了定义特征的类别可分性度量, 首要的工作是定义基于特征的样本差异性度量。给定两个用户u与v, 本文使用绝对误差距离来衡量两个用户在第j个特征值上的差异程度:
其中, diff (uj, vj) 表示用户u与用户v在第j个检测特征上的差异程度, uj和vj分别表示用户u与用户v第j个检测特征值。
1.2 特征的类别可分性度量
根据样本在某一特征上的差异性度量可以定义特征的类别可分性度量。设数据集D={ (x1, y1) , (x2, y2) , …, (xn, yn) }, 共含有n个训练样本分别属于正类和负类, 其中正类中含有n1个样本, 负类中含有n2个样本。根据样本差异性度量方法, 可以在类内平均差异度和类间平均差异度的基础上定义类别可分性度量。针对两类分类问题, 设p为类别标记, p∈{+1, -1}。类内差异度为同类别样本差异度的平均值, 即:
类间差异度为不同类别样本差异度的平均值, 即:
如果某个特征是重要特征, 则在该特征上同类样本的差异度应尽可能地小, 而异类样本的差异度应尽可能地大, 这样两类样本越容易分离。由此给出类别可分性度量为:
在式 (4) 中分子表示类间平均差异度, 分母表示同类类内平均差异度之和。CS值越大, 表明此特征的分类辨别力越强, 分类效果就越好。
1.3 基于类别可分性度量的特征排序
首先利用式 (4) 计算每个特征的CS值;然后对每个特征根据其CS值进行降序排序。具体算法描述如下:
①输入训练样本集D={ (x1, y1) , (x2, y2) , …, (xn, yn) }, x∈Rl, y∈{+1, -1}。设初始特征集F={f1, f2, …, fd}, 特征排序集R=Ø。
②计算当前特征集F={f1, f2, …, fd}中每一个特征的类别可分性度量:
③找出对应于最大类可分性度量的特征:
④更新属性排序集合:R=[f, R]。
⑤输出按照特征对分类的重要性递减排序的特征排序集R。
1.4 基于支持向量机的特征评估
在以往的研究中, 通常采用设定阈值的方法进行特征选择, 但是由于阈值的设置缺乏客观性很难实现特征子集的最优选取[11]。本文利用递归反向特征剔除算法每次从特征排序集R中删除一个当前CS值最小的特征, 再应用SVM算法对当前选取的特征子集进行评价。每次迭代中, 采用SVM的F-measure值作为当前被选特征子集的评估标准, F-measure是一种综合考虑准确率和查全率的指标。F-measure的计算公式如下:
基于支持向量机优化评估的反向特征选择算法:
①设特征排序集为R, R中包含K个特征。
②计算当前特征集下F-measure值。F-measure值为特征子集f在训练集上5折交叉验证支持向量机托攻击检测准确率的平均值, 其中支持向量机模型采用原始特征集上5折交叉验证得到的最优模型参数。
③令, 删除特征集R中f*对应的特征, 形成新的特征集。
④若R≠Ø, 迭代执行②、③步;否则退出循环。
⑤选取最大F-measure值对应的特征子集作为最佳特征集。
2 实验与分析
实验数据使用Minnesota大学Group Lens研究小组通过Movie Lens网站 (http://movielens.umn.edu) 收集的Movie Lens100K数据集[12]。Movie Lens100K数据集包含了943位用户对1682部电影的100 000条评分数据。每位用户至少对20部电影进行了评分, 评分数据是1~5的整数, 评分体现了用户对某部电影的偏好, 数值越高, 表明用户对该电影的偏爱程度越高。
2.1 不同特征子集的检测结果比较
本文引用Williams和Burke等人在文献[13]中定义的11个检测特征:平均背离度RDMA (Rating Deviation from Mean A-greement) 、评价值背离度SDUR (Standard Deviation in User’s Ratings) 、与其他用户相适应度DAOU (Degree of Agreement the Other Users) 、加权评分中心背离度WDMA (Weighted Deviation from Mean Agreement) 、加权相似度WDA (Weighted Degree of A-greement) 、最近N邻居用户相似度Deg Sim (Degree of Similarity with Top-N Neighbors) 、加权最近N邻居用户相似度De Sim’ (Weighted Degree of Similarity with Top-N Neighbors) 、长度方差Length Var (Length Variance) 、填充均值目标差异FMTD (Filler Mean Target Difference) 、均值方差、目标模型焦点TMF (Target Model Focus) 。实验向Movie Lens数据集中分别注入攻击率为10%, 填充率为10%的随机攻击、均值攻击、流行攻击, 攻击均为推攻击。
计算各类攻击下所有特征的类别可分性度量, 结果如图2所示。可以看出对于不同类型的攻击特征的权值排序结果差异性很大, 如WDA检测特征对随机攻击的检测作用很小, 但对均值攻击和流行攻击的检测结果却很好, 而FMTD检测特征对随机攻击的检测效果很好, 对均值攻击和流行攻击的检测效果却很差。因此, 一个检测特征不可能对所有类型的托攻击都有很好的检测效果, 通常一个检测特征仅仅对某些类型的托攻击有效, 如果不进行特征选择盲目地选取检测特征, 很难应对所有种类的托攻击。
然后从特征集的末尾逐一消去特征, 每次迭代中, 采用支持向量机进行检测, 检测结果如表1所示。
由表1可以看出, 几乎所有的特征子集都表现出了一定的检测能力, 但是对于不同类型的托攻击F-measure达到最大值时所对应的特征子集是不同的。可见, 检测特征和检测结果之间呈现出较复杂的关系。对于随机攻击当选择CS值最大的4个检测指标时F-measure值达到最大值为0.908;对于均值攻击当选择CS值最大的3个检测指标时F-measure值达到最大值为0.879;对于流行攻击当选择CS值最大的5个检测指标时F-measure值达到最大值为0.874。从表1还可以看出, 选取所有的11个检测特征时, 随机攻击的F-measure值为0.659、均值攻击的F-measure值为0.639、流行攻击的F-measure值为0.638检测效果并不是最好。这说明11个特征中有些特征参与检测不但增加运算规模, 还给检测结果带来负面影响, 必须通过相关技术, 选择出规模小但检测效果好的特征子集。
2.2 不同模型的检测结果比较
为了使本文托攻击检测方法的检测结果更具说服力, 第二组实验将本文方法与采用全部特征值和支持向量机模型 (SVM) 、文献[8, 9]中的互信息 (IM) 算法单独选择特征和支持向量机模型 (IM+SVM) 、文献[10]中的SVM-RFE算法单独选择特征和支持向量机模型 (SVM-RFE+SVM) 作为对比, 比较四种检测模型在攻击率为10%, 填充率分别为3%, 5%, 10%, 15%, 20%的情形下对随机攻击、均值攻击、流行攻击的检测效果, 每次独立的攻击实验重复进行10次, 实验结果为这10次实验结果的平均值。模型性能评价指标选择准确率 (Precision) 和查全率 (Recall) 。
表2、表3和表4是四种检测模型, 分别针对随机攻击、均值攻击、流行攻击的检测结果。
具体分析如下:IM+SVM方法的检测准确率和检测查全率与SVM方法相比提高不明显, 这是由于IM算法会赋予所有和类别相关性高的特征较高的权值, 而不管该特征是否和其余特征冗余, 因此最终选择的特征子集中引入了部分干扰特征, 影响了最终的检测效果。另外, 从实验中可以看出SVM-RFE和SVM相结合的方法大幅提高了SVM方法的分类性能, 说明通过SVM-RFE方法进行特征选择, 能有效提高SVM方法的分类能力。但从实验结果可以看出本文提出的CS-SVM-RFE方法对改善SVM方法检测性能的效果更加明显, 这是由于CS-SVM-RFE方法在SVM-RFE特征选择前使用了特征的类别可分性度量对特征进行了初选, 选取合适的特征空间为SVM-RFE作进一步优选, 在消除大量冗余和不相关特征的同时又能保留规模小但分类效果好的特征子集, 避免了分类信息的损失, 从而增大了后续分类方法对攻击用户的决策空间, 因此明显优于较单独使用SVM-RFE算法的检测性能。
最后, 值得一提的是在低填充率时, 四种方法的检测准确率和检测查全率均低于高填充率的检测准确率和检测查全率。出现以上情况的原因在于, 当注入的攻击用户概貌填充率较低时, 正常用户概貌与攻击用户概貌的统计特性差异不明显, 而当注入的攻击用户概貌填充率较高时, 正常用户概貌与攻击用户概貌的统计特性差异较大, 这说明在攻击用户概貌填充率较低时托攻击检测的难度较大, 而在攻击用户概貌填充率较高时托攻击检测的难度较小。而本文方法能有效提高在低填充率下支持向量机的检测效果, 从而进一步提高了支持向量机方法的有效性。
3 结语