粒度支持向量机

2024-06-10

粒度支持向量机（精选十篇）

粒度支持向量机篇1

由Vapnik等人于1992年将基于支持向量机SVM (support vector machine) 引入到机器学习领域后, 由于其特别适用于有限样本、非线性问题, 得到的学习模型也具有较好的推广性, 所以成为众多机器学习方法中的热点[1,2]。但是, 由于SVM针对大规模样本数据时, 其处理能力的有限性也阻碍了支持向量机的广泛应用。

2004年, Yuchun Tang提出了将粒度计算理论和支持向量机相结合的机器学习模型, 称为粒度支持向量机[3]。它不但可以有效地克服传统支持向量机对于大规模数据集以及不平衡数据集的训练效率低下的问题, 同时也可以获得较好的泛化性能。目前已然成为了支持向量机研究热点之一[4,5,6]。

目前关于GSVM的研究依然处于起步阶段, 但粒度计算与支持向量机相结合的研究工作取得了一些进展。2005年, Y.C.Tang提出了基于关联规则的粒度支持向量机[7], 其主要思想就是将核函数展开并分析提取出对分类有效的关联规则, 利用这些规则进行划分粒, 最终建立分类器。2009年, 王文剑等人提出了核粒度支持向量机[8], 其主要思想是利用核函数将原样本映射到高维空间再进行粒度划分, 从而建立分类模型。2003年, 李红莲等人将最近邻法与SVM相结合, 提出了一种NN-SVM的混合模型, 该模型利用NN方法对类别交错严重的样本点进行“裁剪”, 从而提高分类器的泛化能力[9]。2009年, Mei等人利用KNN与SVM相结合, 提出一种针对基因表达数据分类问题的混合模型———HKNNSVM。该模型首先利用KNN方法对样本进行预处理, 然后结合KNN和SVM双重分类器对样本点进行分类, 其分类精度得到了有效的提高[10]。此外, 不少学者针对不同的问题, 以不同的方式将KNN与SVM结合进行分类, 与传统的SVM相比, 都达到了较高的分类效果[11]。

对于GSVM来说, 其划分方式、关键信息的提取对其训练效能、泛化能力都有着非常大的影响。本文主要针对这两个问题, 将SNN法与GSVM相结合, 提出一种全新的混合模型———GS-VM-SNN。首先, 利用SNN方法可以获得任意形状的簇 (粒) 这个特点, 对样本点进行粒化, 得到若干个信息粒, 然后针对不同的信息粒, 利用不同的方法提取关键信息点;a) 由于纯粒 (即信息粒中所有样本点的标签一致) 中支持向量较少 (有时甚至没有) , 冗余点较多。我们提出一种KNN连通度, 利用该连通度对其边缘点进行提取。这样在保证不丢失关键信息的前提下, 对冗余点进行删除从而降低训练时间。b) 由于我们使用SNN方法进行粒化, 所以得到的混合粒 (即信息粒中样本点的标签不一致) 一般都是类别交错程度不一的样本点, 而这类信息粒中存在着大量的关键信息。因此, 本文利用KNN对其进行“修剪”后保留该信息粒, 这样既可以克服传统GSVM利用线性SVM提取关键点而造成关键信息丢失的问题, 又可以对混合粒进行降噪, 从而增强其泛化能力。

1 粒度支持向量机

支持向量机是针对整体样本集构造最优超平面, 而粒度支持向量机的主要思想是通过一定的方法将样本空间划分成为若干个子空间, 得到一系列的信息粒, 然后在每个信息粒上进行支持向量机的学习, 最后通过信息粒上的信息或者规则等, 获得最终的支持向量机决策函数。

如图1所示, GSVM将样本空间划分为若干个粒, 构建出比传统支持向量机更加优越的间隔宽度, 从而提高了模型的泛化能力。

其次, 如图2所示, 选取合适的粒化方法, 可以划分出纯粒子空间。纯粒中的支持向量较少, 对建立最终模型的贡献不大, 所以我们只需要将其边缘点 (即对建立最优超平面有用的点) 提取出来。这样大大的降低了支持向量机的计算成本。

2 GSVM-SNN算法

2.1 SNN相似度

传统的相似度大部分直接利用了距离来定义相似性, 如两个对象之间的距离越接近, 则两个对象的相似性就越高。但是, 由于数据在高维空间中的稀疏性使得点与点之间的距离或者相似性度量变得趋于一致。因此, 在高维空间中传统的相似度并不能准确地度量两个点之间的相似性, 而且对于密度不同的样本空间, 传统的基于密度聚类方法也无法准确将样本点区分出来。针对以上问题, Jarvis-Patrick提出了一种相似性的间接方法:共享最近邻相似度SNN (shared nearest neighbor) [12,13,14,15]。其原理就是:如果两点与相同的点集中大部分相似, 即使两点的直接相似度量无法反映两点的相似性, 两点依然相似。本文利用该相似度对样本空间进行粒化。

定义1

xi和xj式样本集{x1, x2, …, xn}的任意两点, 若两点存在对方的k-最近邻中, 则两点的相似, 且其共享最近邻点的个数为两点的相似度, 即:

其中:nn[xi]和nn[xj]分别是xi和xj的的最近k邻近点列表, size (A) 表示集合A的大小。

定义2 (共享最近邻图)

<V, E>表示共享最近邻图u, v∈Ω, u, v之间存在链接当且仅当u∈nn[v]且v∈nn[u], 其中链接强度由式 (1) 计算得到。

定义3 (密度)

点xi的密度为xi的k最近邻列表中与xi相似的点的个数, 即:

其中:xi在xj的k最近邻列表中, n为判断两个点是否相似的阈值, 即两个点相似的条件就是它们之间共享了n个或者超过n个最近邻居。

定义4 (核心点与噪声点)

核心点为高密度点, 即该点密度大于或等于阈值n的点称之为核心点;噪声点表示低密度点, 即该点密度小于阈值n的点。其公式分别为:

式中kernel表示核心点, noise表示噪声点, n为阈值。

图3解释了SNN相似度的计算。首先, 计算两个黑点的8个最近邻, 而其中4个灰色点是两个黑点共享的最近邻点, 则我们称这两个黑点之间的SNN相似度为4。

2.2 KNN连通度

支持向量机进行分类的关键就是那些分布在最优分隔超平面两旁的支持向量点, 所以只有这些点对超平面的建立有贡献, 而这些支持向量点大都分布在两类样本点的边缘位置。如何将这些点预先提取出来, 或者说在保证这些关键信息点存在的前提下, 如何尽可能地减少训练样本点的数目也成为了很多研究人员关注的焦点之一[16]。

传统GSVM利用一个线性SVM对每个信息粒提取关键点, 为了保证关键信息不丢失, 该线性SVM的参数c取的非常小。但对于高维数据来说, 这样的提取方式并不可靠。虽然纯粒内部的关键点较少 (有时甚至没有) , 但依然不能忽略。所以, 本文提出一种KNN连通度提取纯粒的边缘点。

定义5

xi和xj式样本集{x1, x2, …, xn}的任意两点, 若xi是xj的k最近邻居列表中的一点, 则称点xi与点xj连通。

定义6

点xi在样本集的k最近邻列表中出现的次数之和称为点xi在该样本集中的连通度, 即:

式中X表示样本集, xi表示任一一个样本点, T (xi) 表示点xi出现在k最近邻列表的次数。

假设有10个2维样本点, 其分布情况如图4 (a) 所示, 计算每一个点的4个最近邻点, 得出样本点的最近邻列表, 并计算每个点的KNN连通度 (如表1所示) 。

最后, 提取KNN连通度小于阈值s=4的点, 得到了该样本集的边缘点如图4 (b) 所示。

KNN连通度的本质就是反映该点被其它点的包围程度, 该点周围的点越多, 其KNN连通度就越高。也就是说, 连通度越低, 该点分布越靠近边缘, 所包含的信息对建立最终决策模型越为重要;相反, KNN连通度越高的点, 表明其被周围点包围程度越高, 也就越远离样本数据的“边缘”, 其包含的信息对最终决策模型的建立贡献不大或者没有贡献, 也就是我们所认为的“冗余点”。所以, 在保证不丢失关键信息点的前提下, 合理选取阈值s变得尤为重要。本文取样本连通度的平均值作为其阈值, 即:

式中, size (X) 表示样本点的个数, str (xi, X) 表示xi点的KNN连通度的值。

由于本文利用SNN方法进行粒化, 所得到的信息粒都遵循原样本点的分布特征。一般来说, 划分出的混合粒均为类别交错程度不一的样本点。而那些混杂在另一类中的点往往对最终分类器的建立没有帮助, 为了改善分类器的泛化能力, 文献[10]利用NN法对样本点进行修剪。这么做有一定的改善作用, 但也存在一些缺陷。如图5 (a) 所示, 两个距离较近的同类噪声点, 在异类中成为孤立对时, 由于二者互为最近邻而未被删除;如图5 (b) 所示, 关键样本与噪声点较接近时而被误删, 对其分类器的泛化能力有所影响。针对以上两个问题, 本文利用KNN计算混合粒中每个样本点的k最近邻列表, 根据该点周围邻居的标签来决定该点是否删减, 其具体步骤如下:

Step1 计算信息粒中所有样本点的k最近邻, 得到KNN列表;

Step2 考察每个样本点的邻居标签是否一致。

Step2.1 若邻居的标签一致, 则查看该点是否与之相同, 相同则保留该点, 反之则删除;

Step2.2 若邻居标签不一致, 则转入Step3;

Step3 考察邻居中两类点的个数比, 若两类点的个数比不为1, 则该点的邻居标签取决于较多的那一类, 然后判断该点的标签是否与之相同, 相同则保留, 反之则删除;若两类点的个数比为1, 则保留该点。

2.3 GSVM-SNN算法描述

本文主要探讨对训练样本粒化、信息粒的处理等问题, 对于如何选择合适的参数不做深入的讨论。

算法的详细步骤如下:

Step1 输入训练样本。

Step2 设定KNN中阈值k值, SNN中链接阈值n。

Step3 计算训练样本点间的欧氏距离, 构造距离矩阵D= (ai, j) n×n, 其中xi, yj为样本点, 其中:

式 (7) 是由D构造最近邻列表矩阵nn。

Step4 由定义1和nn构造相似性矩阵SI。

Step5 由SI和定义2构造共享最近邻图SH。

Step6 由SH和式 (2) 计算每个样本点的密度。

Step7 利用样本点的密度划分得到噪声点以及若干个信息粒X→{G1, G2, …, Gi}。

Step7.0 若只划分出一个粒, 则转Step 8。

Step7.1 对于属于混合粒的信息粒{Gmix}, 利用KNN法对其进行“裁剪”, 得到关键信息{GS}。

Step7.2 对于属于纯粒的信息粒{Gpure}, 计算其KNN连通度。

Step7.3 利用式 (6) 计算纯粒中样本点的KNN连通度平均值Dm作为阈值, 将连通度大于阈值的样本点删除并提取边缘点{Gb}。

Step7.4 对于粒化得到的噪声点保留成一个粒, 称之为噪声粒{Gn}。

Step8 将从混合粒中提取出的支持向量点{GS}、纯粒中提取出的边缘点{Gb}、以及噪声点{Gn}融合并进行SVM训练, 得到最终的决策模型。

3 实验

3.1 人工数据对比分析

为了验证GSVM-SNN方法的有效性, 本文选取1组人工数据MM (manmade data) (表2中的1号数据) , 对GSVM-SNN方法进行实验验证, 并与传统的GSVM、NN-SVM进行对比验证。以下所有实验均在一台CPU为2.68 GHz;内存为2 G, 操作系统为Windows XP的计算机上运行, 实验平台为Matlab 7.12R (2011a) 。

为了保证实验结果的准确性, 所有的实验均使用10折交叉验证法进行10次实验并求取平均值, 惩罚系数C=100, 核半径σ=0.5;并且分别利用不同的核函数进行实验对比。

对比图6 (a) 、图6 (b) 、图6 (c) 可以看出, 得益于SNN方法的优势, 设定阈值k=20, 其粒的个数可以直接算出, 且划分出的信息遵从样本分布的原始形态 (即3个粒, 其中2个纯粒, 1个混合粒) ;相反, 传统GSVM粒的个数只能由用户自行确定, 所以其划分结果具有一定随机性, 甚至有可能会出现信息粒中样本数据分布不平衡等问题, 增加了样本点的复杂性。对于NN-SVM算法而言, 对于样本类别交错区域有一定的积极作用, 然而由于上节所提到的缺陷导致误删了某些关键点, 而且对于没有类别交错的区域, 该方法失效。

表3为人工数据在3种不同方法下的实验对比结果, 从结果中可以看出, 由于划分出两个混合粒, GSVM提取点明显较多, 但线性SVM在提取过程中有可能丢失关键信息, 且对于类别交错区域无法合理“降噪”, 从而影响其分类准确率以及泛化能力。

3.2 实际数据对比分析

为了验证GSVM-SNN方法在实际数据中的有效性, 本文选用4组UCI数据集:Mushrooms (Mu) 、Australian (Au) 、Banknote (Bn) 、Four Class (FC) (表2中的2~5号数据) , 然后与传统SVM方法[1]、GSVM方法[3]、NN-SVM方法[9]进行实验对比, 其结果见表4、表5所示。

图7显示了不同k值, 样本点划分的粒的个数情况。可以看出, 当k值过大时, 信息粒的个数变少甚至为1 (即将原样本点化成1个粒) , 随着k值减小, 信息粒的个数增加, 而信息粒中包含的样本点个数却逐渐减少, 甚至只有一个样本点, 即将原样本点中的每一个点成为一个独立的粒。也就是说, 当k值过大或者过小时, GSVM-SNN将原样本划成一个混合粒。所以, 对于不适合粒化的样本, 本文提出的方法可以避免传统GSVM的强行划分而导致分类器的准确率的下降。其次, 当k值从极小到极大之间变化时, 样本点划分粒的个数是有限的几个值, 即样本点粒的个数是有限范围内的变化, 这不同于传统的GSVM粒个数的不确定性。虽然Jarvis-Patrick二人并没有对k的取值提出一个科学有效的方法, 但从图5可以看出, 对于低维样本点, k值一般取5~15, 对于高维样本点而言, k值一般取10~25。

从表4、表5的对比结果可以看出, GSVM-SNN都优于其他3种方法, 由于NN-SVM只有在样本点存在类别交错现象时才能体现其优势, 所以当数据无类别交错或交错程度非常轻微时 (如2、4和5号数据) , 该方法因为额外计算了最近邻反而导致训练时间的增加。从准确率的角度来看, 由于传统GSVM利用线性SVM提取关键信息由于参数C的取值问题而不可靠, 可能会造成关键信息点的丢失, 严重影响其分类精度;相反, 本文利用SNN方法粒化, 对不同的信息粒有的放矢, 保证了关键信息的完整性, 删去了冗余点、噪声点, 从而提高了分类精度。从泛化能力的角度来看, 对于传统SVM来说, 支持向量点的个数并非越少越好, 有效地保留关键支持向量对分类器的训练效能、泛化能力非常重要。对比3号数据结果可以看出, 利用KNN方法对类别交错区域进行有效的“裁剪”, 减少噪声点对分类器的影响, 从而获得更好的泛化能力;而1、3和4号数据来说, 由于信息粒均为纯粒, 通过对其粒化并提取边缘点, 在保证关键信息不丢失的前提下, 降低了样本的复杂性, 简化了分类面, 从而获得了较好的泛化能力。

4 结语

本文利用SNN方法的优势, 对传统GSVM的划分方式进行了改进, 提出了一种GSVM-SNN混合模型。针对纯粒的特点, 提出了KNN连通度, 对其进行边缘点提取, 以降低样本的训练成本;针对混合粒使用KNN法进行降噪, 简化分类面, 提高分类器的泛化能力。实验结果表明, 与SVM、GSVM相比, GSVM-SNN的训练效能、泛化能力都有一定的优越性。但是, SNN方法的时间复杂度问题依然需要深入研究, 且阈值S的确定也缺乏科学的指导, 未来将会对此做进一步的探讨。

摘要：粒度支持向量机GSVM (Granular Support Vector Machine) 在处理大规模数据集时, 粒的划分对其模型的训练效能、泛化能力等有很大的影响。然而传统划分方法的随机性, 严重影响着其模型的训练效果。针对这个问题提出一种结合共享最近邻法和粒度支持向量机的混合模型 (GSVM-SNN) 。利用共享最近邻法将样本点自动划分成若干个信息粒, 从中提取出关键信息。由于支持向量点大都分布在信息粒的边缘, 提出一种KNN连通度, 通过计算连通度提取纯粒边缘点并融合关键信息建立最终决策模型。实验结果表明, 与传统的GSVM相比, 该方法在分类时间、分类准确率上都有一定的优越性。

粒度支持向量机篇2

支持向量机(Support Vector Machines)是近年来热门的一种有监督学习的.方法,它广泛的应用于统计分类以及回归分析中.通过SVM模型,考察分析一系列影响因素对高速公路路面质量指标的影响,并对提高高速公路路面质量提出建议.

作者：陶甄吴元梁晓辉 TAO Zhen WU Yuan LIANG Xiao-hui 作者单位：陶甄,TAO Zhen(上海交通大学,金融系,上海,30)

吴元,梁晓辉,WU Yuan,LIANG Xiao-hui(上海交通大学,计算机科学与工程系,上海,40)

基于光滑支持向量机的经济预测模型篇3

关键词：经济预测模型；支持向量机；加函数；光滑函数；Newton-Armijo算法

1.引言

支持向量机原理及展望篇4

支持向量机(Support Vector Machine,SVM)是由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术,SVM是一种基于统计学习理论的模式识别方法,主要应用于模式识别领域。由于当时这些研究尚不十分完善,在解决模式识别问题中往往趋于保守,且数学上比较艰涩,这些研究一直没有得到充分的重视。直到90年代,统计学习理论(Statistical Learning Theory,SLT)的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难,比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等,使得SVM迅速发展和完善,在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中,从此迅速的发展起来,现在已经在许多领域取得了成功的应用。

1 基本原理

假设如图1这些数据点是n维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。

如图1有很多个分类器(超平面)可以把数据分开,但是只有一个能够达到最大分割。

支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。假定平行超平面间的距离或差距越大,分类器的总误差越小。

支持向量机属于一般化线性分类器。他们也可以认为是提克洛夫规则化(Tikhonov Regularization)方法的一个特例。这种分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。

所谓支持向量是指那些在间隔区边缘的训练样本点。这里的“机(machine,机器)”实际上是一个算法。在机器学习领域,常把一些算法看做是一个机器。

如图2设样本属于两个类,用该样本训练svm得到的最大间隔超平面。在超平面上的样本点也称为支持向量,支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力。

支持向量机(Support vector machines,SVM)与神经网络类似,都是学习型的机制,但与神经网络不同的是SVM使用的是数学方法和优化技术。

2 支持向量机的算法

SVM的支持向量机的主要思想可以概括为两点:

1)它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;

2)它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。

支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开来,通常分为两类情况来讨论:线性可分与线性不可分。

2.1 线性可分情况

在线性可分的情况下,就会存在一个超平面使得训练样本完全分开,该超平面可描述为:

其中,“·”是点积,w是n维向量,b为偏移量。

最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面,最优超平面可以通过解下面的二次优化问题来获得:

满足约束条件:

在特征数目特别大的情况,可以将此二次规划问题转化为其对偶问题:

满足约束条件:

这里α=(α1,...,αn)是Lagrange乘子,b*是最优超平面的法向量,是最优超平面的偏移量,在这类优化问题的求解与分析中,KKT条件将起到很重要的作用,在(7)式中,其解必须满足:

从式(5)可知,那些aι=0的样本对分类没有任何作用,只有那些aι>0的样本才对分类起作用,这些样本称为支持向量,故最终的分类函数为:

根据f(x)的符号来确定X的归属。

2.2 线性不可分的情况

对于线性不可分的情况,可以把样本X映射到一个高维特征空间H,并在此空间中运用原空间的函数来实现内积运算,这样将非线性问题转换成另一空间的线性问题来获得一个样本的归属,根据泛函的有关理论,只要一种核函数满足Mercer条件,它就对应某一空间中的内积,因此只要在最优分类面上采用适当的内积函数就可以实现这种线性不可分的分类问题。此时的目标函数为:

其相应的分类函数为:

2.3 内积核函数

SVM的关键在于核函数。低维空间向量集通常难于划分,解决的方法是将它们映射到高维空间。但这个办法带来的困难就是计算复杂度的增加,而核函数正好巧妙地解决了这个问题。也就是说,只要选用适当的核函数,就可以得到高维空间的分类函数。在SVM理论中,采用不同的核函数将导致不同的SVM算法。目前有三类用的较多的内积核函数:第一类是

我们所能得到的是p阶多项式分类器,第二类是径向基函数(RBF),也称作高斯核函数:

第三类是Sigmoid函数:

这时SVM实现的就是包含一个隐层感知器,隐层结点数是由算法自动确定的。究竟用哪一种核函数比较好,这还是取决你对数据处理的要求,不过建议可以使用径向基函数。

3 支持向量机的特点

1)它是专门针对有限样本情况的,其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值;

2)算法最终将转化成为一个二次型寻优问题,从理论上说,得到的将是全局最优点,解决了在神经网络方法中无法避免的局部极值问题;

3)算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space),在高维空间中构造线性判别函数来实现原空间中的非线性判别函数,特殊性质能保证机器有较好的推广能力,同时它巧妙地解决了维数问题,其算法复杂度与样本维数无关;

4)在SVM方法中,只要定义不同的内积函数,就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function或RBF)方法、多层感知器网络等许多现有学习算法。

5)该方法不但算法简单,而且具有较好的“鲁棒”性。

4 结束语

支持向量机算法是一个凸二次优化问题,能够保证找到的极值解就是全局最优解,是神经网络领域取得的一项重大突破。与神经网络相比,它的优点是训练算法中不存在局部极小值问题,可以自动设计模型复杂度(例如隐层节点数),不存在维数灾难问题,泛化能力强,SVM已初步表现出很多优于已有方法的性能。SVM正在成为继神经网络研究之后新的研究热点,并将推动机器学习理论和技术有重大的发展。

支持向量机能非常成功地处理回归问题(时间序列分析)、模式识别(分类问题、判别分析)、概率密度函数估计等诸多问题,并可推广于预测和综合评价等领域,例如,在模式识别方面,对于手写数字识别、语音识别、人脸图像识别、文章分类等问题,SVM算法在精度上已经超过传统的学习算法或与之不相上下。目前国际上支持向量机理论研究和实际应用两方面都正处于飞速发展阶段。

摘要：支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法,通过寻求结构化风险最小来提高学习机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量较少的情况下,亦能获得良好统计规律的目的。该方法不但算法简单,而且具有较好的“鲁棒”性,与神经网络相比,它的优点是训练算法中不存在局部极小值问题,在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中,现在已经在许多领域取得了成功的应用。

关键词：支持向量机,神经网络,分类器,核函数

参考文献

[1]B.E.Boser,I.M.Guyon,and V.N.Vapnik.A training algorithmfor optimal margin classifiers.In D.Haussler,editor,5th Annual ACM Workshop on COLT,pages 144-152,Pittsburgh,PA,1992.ACM Press.

[2]Corinna Cortes and V.Vapnik,"Support-Vector Networks,Machine Learning,20,1995,1.

[3]张艳.一类基于支持向量机的软件故障预测方法[J].小型微型计算机系统,2010.31(7):1380-1383.

[4]杜树新,吴铁军.模式识别中的支持向量机方法[J].浙江大学学报(工学版),2003,9,37(5):521-526.

[5]刘渤海.基于ANN和SVM的质量预测方法研究[J].制造业自动化,2010.32(5):152-155.

粒度支持向量机篇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

关键词：支持向量机,样本,约束条件,分类平面

0 引言

SVM是一种不同于现有的传统方法的小样本学习方法。近年来,它在基本理论与工程实践上得到了更深远地应用发展。它具有其他学习方法不可有的本质优点:首先,由于它完全不涉及概率测度的定义及大数定律等,所以实际上它就避开了从归纳到演绎的一般基本过程,高效的实现了从训练样本到预报样本的变换推导,这使得回归与分类问题得到了大幅度的简化。其次,支持向量机的最终决策函数只是由较为少数的SV(支持向量)所确定,计算的复杂性取决于支持向量的数目,基本上已经避免了维数危机。再次,正是少数支持向量决定了最终函数结果的原因,与此同时也削减了冗余样本,使其算法得到简化,并且具有更好的健壮性。最后,支持向量机通过核函数实现到高维空间的非线性映射,所以SVM对非线性问题有着非常好的适应性,并且具有很强的泛化性能。下面先介绍一下它的基本原理。

1 支持向量机的样本分类

先假设有限可分的两类样本:

可以采用下面的超平面进行分离:

W与b是参数,约束条件为:

超平面的约束条件如下:

样本点到超平面的距离如下所示:

为了实现把两类样本正确的分开,并且还要达到分类间隔最大化的目的,就要获取这样的分类线,即最优分类线。如果不是在平面内分类,而是在高维空间上,就是要获取最优分类面。参考图1所示。

图1中,三角形与正方形分别代表了两个不同类别的样本,H是分类线,我们找到图中两类样本中离分类现最近的样本点,过这两个样本分别作直线平行于分类线H,把这两条直线的距离记作,定义如下:

其中,ia是LAGRANGE乘子,对W与b求拉格朗日最小值,分别对W和b求拉格朗日偏导使其等于零,且需满足最优解KKT条件,得:

2 支持向量机的非线性变换

通过上面的变换,不仅错误划分的样本数目被降低,而且使其对应的分类间隔保持最大化,最终就获得了广义最优分类平面。由以上可知,线性问题在支持向量机中是以数据内积形式表达的。那么,对于非线性问题而言,SVM是可以通过非线性变换将非线性问题转化为在某个高维空间中的线性问题,从而求出它的最优分类面。变换过程如图2所示。

就这样,通过满足条件的内积函数去实现高维空间的非线性映射,只要在新的高维空间中去寻找广义的最优分类面,这样的思想过程就是支持向量机的基本概念原理。SVM的分类函数是一个三层神经网络的类似结构,输出是由几个中间节点的线性组合求出,第二层网络节点是对应的输入样本与它的一个支持向量的内积。如图3所示。

假如输入样本能够通过映射后在高维特征空间里找到最优分类面,那么SVM的推广性与变换后空间的维数并没有直接联系,只有找到合适的内积,在其他条件不变的情况下,只要建立一个支持向量数目相对较少的最优分类平面,推广能力就已经得到了非常不错的提升。

参考文献

[1]郭明玮,赵宇宙,项俊平,张陈斌,陈宗海.基于支持向量机的目标检测算法综述[J].控制与决策,2014(02).

[2]马芳芳,仝卫国,宋雨倩.模糊支持向量机的研究与应用[J].电脑与信息技术,2013(01).

基于支持向量机音乐类型分类方法篇8

音乐类型分类是多媒体应用中的重要组成部分。随着数据存储、压缩技术和互联网技术的飞速发展, 音乐类型数据急剧增加。在实际应用中, 所有的商业音乐数据库和mp3音乐下载站点首要的任务是将这些音乐收藏到不同音乐类型的数据库中。传统的人工检索方法已经不能满足对海量信息的检索分类。分类音乐类型的目的就是为了解决上述问题, 它可利用音乐本身的声学特征对其进行自动分类, 取代手工的方法。同时, 确定背景音乐类型也是检索视频场景的一种有效方法。

从本质上讲, 音乐类型分类是一个模式识别的问题, 主要包括两个方面内容:特征提取和分类。很多研究者在这个领域做了大量的工作, 采用了不同的音频特征和分类方法。文献[1]采用混合高斯模型, 对MPEG-7格式的13种类型音乐分类。文献[2]使用KNN和GMM分类器和小波特征分类音乐类型, 错误率分别为38%和36%。

传统参数虽然在实际中取得了较好的效果, 但这些方法的鲁棒性、适应性和推广能力有限, 特别是特征参数大都采用短时平稳信号的分析方法取得的。小波理论是一种非平稳信号的分析方法, 采用多分辨分析的思想, 非均匀划分时-频空间, 是时频域分析中非常有效的工具, 并有广泛应用[3,4,5]。SVM是在统计学理论基础上发展起来的一种新的机器学习方法, 它在小样本的条件下依然保持很好的推广能力, 在结构风险最小化原则基础上, 在特征空间建立最优的分类超平面, 克服传统基于规则的分类算法的缺点。近年来SVM已广泛被应用于各领域[6,7], 并在语音识别上也取得了很好的实验效果[8]。

因此, 本文提出了一种基于小波特征和SVM的分类音乐类型的方法。

1连续小波变换

设f (t) 是平方可积函数[记作f (t) ∈L2 (R) ], ψ (t) 是基本小波或母小波函数, 则:

$[W_{ψ} f] (a, τ) = \int x (t) \frac{1}{\sqrt{a}} ψ (\frac{t - τ}{a}) d t$ (1)

成为f (t) 的小波变换。式中a是尺度因子, 其值大于零;τ是时间位移, 其值可正负。计算机要求在有限的离散数据下工作, 因此离散的小波变换公式如下:

$[W D_{ψ} f] (a, τ) = \sum_{n = - \infty}^{+ \infty} x [n] \frac{1}{\sqrt{a}} ψ (\frac{n - τ}{a})$ (2)

1.1数据预处理

直接实现小波变换要求很大的计算量, 这可能导致算法消耗大量内存。因此, 对数据进行预处理, 在不改变计算过程和精度的前提下实现数据计算量实质性的压缩。

可以预先设定不同尺度小波, 需完成以下几步:

(1) 选择小波最大和最小尺度;

(2) 计算所有的小波尺度;

(3) 计算相应尺度下基小波离散点值。

小波尺度与频率成反比。选择对数规律改变尺度。尺度计算如下:

$s c a l e_{k \in [1, n u m]} = Μ a x W v L n g \cdot \exp [- \frac{k}{n u m} \cdot \log (\frac{Μ a x W v L n g}{Μ i n W v L n g})]$ (3)

scalek是第k个尺度;MaxWvLng是小波尺度最大值;MinWvLng是小波尺度最小值;num是尺度总数目 (256) 。

选择B样条小波作为基小波。对于不同尺度下的B样条小波函数如图1所示。

1.2计算连续小波变换

计算连续小波变换如下:

$\begin{array}{l} C W Τ (p o s, k) = \sqrt{r s c a l e [k]} \cdot \\ \sum_{i = 0}^{Μ a x W v L n g} (w a v e [p o s - \frac{Μ a x W v L n g}{2} + i] \cdot w v l t [k] [i]) (4) \end{array}$

pos是时间轴采样点的位置;k是小波编号;rscale[k]是系数, 与小波尺度成反比;wave[]是采样信号数据集;wvlt[k][i]是第k个小波的第i点采样值;

由公式 (4) 计算得到二维时频域的小波系数。小波变换后某时刻的小波系数如图2所示。图中横、纵坐标分别是尺度和小波的归一化系数。

不同类型音乐的连续小波变换如图3、图4所示。将语音信号延频率轴分割成不同的子带, 从图中可以看出, 摇摆音乐的高频分量高于古典音乐, 且基频分布较均匀 (图中白色部分为基频) 。

1.3提取特征向量

在时频域内沿着时间轴分割成子段, 沿着频率轴分割成子带, 如图5所示。提取特征方法1:将每个分割块单元中小波系数取平均值, 按列将这些平均值排成序列作为特征向量ave (b1) 、ave (b2) 、…、ave (b16) 。方法2:取平均值时每个块的子段起始位置由零开始, 特征向量依次为ave (b1) 、ave (b2) 、ave (b3) 、ave (b4) 、ave (b1+b5) 、ave (b2+b6) 、ave (b3+b7) 、ave (b4+b8) 、ave (b1+b5+b9) 、…、ave (b4+b8+b12+b16) 。bn表示第n块内所有小波系数之和, ave表示求平均值。

2支持向量机分类

支持向量机训练分类器的目的就是找到最优分类超平面H, H要最大化两类凸包到分类超平面的垂直距离, 并使训练的错误最小。

$\frac{1}{2} ∥ ω ∥^{2} + C \sum_{i = 1}^{n} ξ$ (5)

其中ξ是松弛变量, 作为对误分的修正。C是错误惩罚力度因子。引入拉格朗日乘子αi≥0, βi≥0, 式 (5) 优化问题由拉格朗日函数对偶式 (6) 给出。

$L_{d} = \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j})$ (6)

约束条件为 $\sum_{i = 1}^{n} α_{i} y_{i} = 0$ ;0≤αi≤C;i=1, …, n。二次规划问题的解为α*= (α $_{1}^{0}$ , α $_{2}^{0}$ , …, α $_{n}^{0}$ ) 。α $_{i}^{0}$ >0所对应的训练样本, 称之为支持向量。

对于实际中难以线性分类的情况, SVM通过选择合适的非线性变换将输入向量映射到高维特征空间, 在高维空间建立线性超平面。设存在映射ψ:X→Z, X∈Rd, Z∈Rk, k≥d, 它可以把输入样本xi∈X映射到k维特征空间Z。若函数K (xi, xj) =ψ (xi) ·ψ (xj) , 则称K为内核函数。代入式 (6) 得:

$L_{d} = \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} α_{i} α_{j} y_{i} y_{j} Κ (x_{i}, x_{j})$ (7)

在高维空间Z中, 最终的分类决策函数是:

$f (x) = sgn (\sum_{支持向量} α_{i}^{0} y_{i} k (x_{i} x_{i}) - b)$ (8)

常用的内核函数有多项式内核函数, 高斯径向基函数RBF, 指数径向基函数ERBF。实验采用指数径向基函数, 其函数如下:

$Κ (x, y) = \exp (\frac{- ∥ x - y ∥}{2 δ^{2}})$ (9)

SVM训练算法采用序列最小优化SMO (Sequential Minimal Optimization) 算法。该算法的优点是针对2个样本的二次规划问题可以有解析解的形式, 从而避免了多样本情况下的数据解不稳定及耗时问题, 同时也不需要大的矩阵存储空间。其工作集的选择采用启发式, 通过两个嵌套的循环来寻找待优化的样本变量, 循环优化, 直到全部样本都满足最优条件。

3实验结果

研究选用4种音乐类型:古典、爵士、流行和摇摆。实验数据库包含400首音乐录音, 16位PCM格式, 采样速率22.050KHz, 每首截取30秒长度片断。400首录音出自不同作品。每种音乐类型100首录音。数据库录音来自CD、mp3、数据库和无线电广播。

每类50个样本作为训练集, 50个样本作为测试集。由于小波系数值较大, 提取特征时需要作归一化处理, 提高识别精度。训练测试SVM, 循环迭代参数C和δ, 从实验中得到精度最高的C和δ。当存在多个相同的最高测试率时, 取支持向量少的那组参数作为最优参数。窗口长度4096个采样点。对每种音乐类型提取特征向量, 使用不同的子带和子段的数目进行测试。实验中使用6种组合形式用SVM分类。实验结果见表1。整个实验在Visual C++ 6.0平台下开发完成。

4结论

音乐类型分类在多媒体应用中有重要的应用价值。本文采用B样条小波变换作为音乐特征, SVM分类音乐类型, 分类正确率可达86%, 尤其对古典/摇摆这对类型分类表现最好。表明该方法合理、有效。

参考文献

[1]Burred J, Lerch A, Hierarchical A.approach to automatic musical genreclassification[C]//Int.Conf.on Digital Audio Effects (DAFx-03) , London, UK, 2003:308-311.

[2]Li T, Oginara M, Li Q.A comparative study on content-based musicgenre classification.in Proc.Of the 26thannual int.ACMSIGIR conf.on Research and development in information retrieval, ACM, ACMPress, 2003:282-289.

[3]Mallat S G.A Theory for Multiresolution Signal Decomposition:theWavelet Representation[J].IEEE Trans Pattern Analysis and MachineIntelligence, 1989, 11 (7) :674-693.

[4]Downie T R, Silverman B W.The discrete multiple wavelet transformand thresholding methods[J].IEEE Transon Signal Processing, 1998, 46 (9) :2558-2561.

[5]Tzanetakis J, Cook P.Musical genre classification of audio signals[J].IEEE Trans.on Speech and Audio Processing, 2002, 5 (10) :293-302.

[6]Moreno Pedro J, Clarkson Philip.On the use of support vector machinesfor phonetic classification[C]//Proceedings of1999 IEEE Internation-al Conference on Acoustics, Speech and Signal Processing, 1999.

[7]Fine S, Navratil J, Gopinath R A.A hybrid GMM/SVM approach tospeaker identification[C]//Proceedings of 2001 IEEE InternationalConference on Acoustics, Speech and Signal Processing, 2001.

基于支持向量机回归的模型辨识篇9

关键词：迟滞,支持向量机,连续模型

1 引言

压电陶瓷、磁致伸缩材料、形状记忆合金等智能材料构成的传感器或执行器在航空航天、微纳米定位、微电子制造、精密机械、生物工程等领域应用的越来越广泛, 但是, 这些智能材料都表现出迟滞特性, 迟滞的存在不但会降低系统的控制精度, 甚至会导致系统不稳定[1]。为了消除迟滞非线性对系统的不良影响, 通常的做法是建立迟滞的数学模型并构建相应的逆模型来实现对迟滞的补偿[2]。支持向量机[3]是Vapnik等在解决模式识别问题时提出来的。其基本思想是在训练样本集中通过某种算法选出一个特征样本子集, 使得对此样本子集的划分等价于对原训练集的划分, 从而大大简化分类和回归问题。本文在此基础上提出一种简化的遗忘因子矩形窗LS-SVR算法, 并通过MATLAB仿真验证算法。

2 支持向量机回归原理

最小。其中R[f]为期望风险, L为损失函数。支持向量机回归是一种机器学习的算法, 而机器学习的目的是求出对某系统输入、输出之间依赖关系的估计, 使它能够对未知输出尽可能地预测, 即使期望风险最小化。传统机器学习采用经验风险最小化来近似期望风险最小化。对 (1) 式, 经验风险为:

现在, 实际系统回归过程中我们一般采用结构风险最小化来代替期望风险最小化。结构风险为

-不敏感损失函数表达式如下:

根据以上分析, 我们固定经验风险, 最小化函数集复杂度即 , 就得到优化问题

但是, 在实际回归过程中, 总是有一个或几个样本点不能在精度下无误差的拟合。我们又不能为了这个别的几个点牺牲整体的性能, 所以我们引入松弛变量i0, i*0, 认为这几个点是由系统扰动形成。得到最终的优化问题用线性二次规划表示如下:

3 MATLAB仿真

为验证简化后的遗忘因子矩形窗算法的最小二乘支持向量机算法的有效性, 考虑非线性系统。

其中, 为单位阶跃函数, 即

4 结语

本章首先介绍了支持向量机的基本理论, 然后针对标准支持向量机存在的缺陷, 引入最小二乘、矩形窗以及遗忘因子等思想对其进行改进, 研究了一种简化的基于遗忘因子矩形窗算法的最小二乘支持向量机回归算法, 最后通过MATLAB仿真验证了其可行性。

参考文献

[1]G.Tao, EV.Kolotovic.Adaptive control of plants with unknown hysteresiss[J].IEEE Trans on automatic Control, 1995 (2) :200-212.

[2]赵新龙, 董建萍.基于神经网络的迟滞非线性补偿控制[J].控制工程, 2010 (4) :475-477.

支持向量机的算法及应用篇10

支持向量机是一种通用学习机器, 是统计学习理论的一种实现方法, 它较好地实现了结构风险最小化思想。将输入向量映射到一个高维的特征空间, 并在该特征空间中构造最优分类面, 它能够避免在多层前向网络中无法克服的一些缺点, 并且理论证明了:当选用合适的映射函数时, 大多数输入空间线性不可分的问题在特征空间可以转化为线性可分问题来解决。但是, 在低维输入空间向高维特征空间映射过程中, 由于空间维数急速增长, 这就使得在大多数情况下难以直接在特征空间直接计算最佳分类平面。支持向量机通过定义核函数 (Kernel Function) , 巧妙地利用了原空间的核函数取代高维特征空间中的内积运算, 避免了维数灾难。具体做法通过非线性映射把样本向量映射到高维特征空间, 在特征空间中, 维数足够大, 使得原空间数据的像具有线性关系, 再在特征空间中构造线性最优决策函数, 如图1.1所示。

支持向量机具有坚实的数学理论基础, 是专门针对小样本学习问题提出的。从理论上来说, 由于采用了二次规划寻优, 因而可以得到全局最优解, 解决了在神经网络中无法避免的局部极小问题。由于采用了核函数, 巧妙解决地了维数问题, 使得算法复杂度与样本维数无关, 非常适合于处理非线性问题。另外, 支持向量机应用了结构风险最小化原则, 因而支持向量机具有非常好的推广能力。

二、支持向量机的几种常见算法

2.1二类支持向量机算法

假定大小为L的训练样本集{ (Xi, Yi) , i=1, 2…, L}, 由二类别组成, 如果Xi∈R (N) 属于第一类, 则标记为正 (Yi=1) , 如果属于第2类, 则标记为负 (Yi=-1) 。

学习的目标是构造一个决策函数, 将测试数据尽可能正确地分类。针对训练样本集为线性或者非线性两种情况分别讨论。

2.1.1线性情况

如果存在分类超平面

使得

则称训练集是线性可分的, 其中ω·xi表示向量ω∈R (N) 与x∈R (N) 的内积。式 (l.1) 和式 (l.2) 中的ω∈R (N) , b∈R (1) 都进行了规范化, 使每类样本集中与分类超平面距离最近的数据点满足式 (l.2) 的等式要求。对于式 (l.2) , 可写成如下形式

由统计学习理论可知, 如果训练样本集没有被超平面错误分开, 并且距超平面最近的样本数据与超平面之间的距离最大, 则该超平面为最优超平面 (如图1.2所示) , 由此得到的决策函数

其推广能力最优, 其中sign (·) 为符号函数。最优超平面的求解需要最大化2/||ω||, 即最小化为1/2||ω||2, 为如下的二规划问题

训练样本集为线性不可分时, 需引入非负松驰变量ξi, i=1, 2, …, l, 分类超平面的最优化问题为

其中, C为惩罚参数, C越大表示对错误分类的惩罚越大。采用拉格朗日乘子法求解这个具有线性约束的二次规划问题, 即

其中, αi, βi为拉格朗日乘子0≤αi, 0≤βi, 由此得到

将式 (1.8) - (1.10) 代入式 (1.7) , 得到对偶最优化问题

最优化求解得到的αi中, αi可能是: (1) αi=0: (2) 0<αi<C; (3) αi=C:后两者所对应的xi, 为支持向量 (Support Vector, SV) o由式 (l.14) 可知只有支持向量对ω有贡献, 也就对最优超平面、决策函数有贡献, 支持向量由此得名, 对应的学习方法称之为支持向量机。在支持向量中, (3) 所对应的xi称为边界支持向量 (Boundary Su PP0rt Vector, BSV) , 实际上是错分的训练样本点, (2) 所对应的xi称为标准支持向量 (Normal support Vector, NSV) 。根据Karush一Kuhn一Tucher条件[Vapnik, 1995] (简称KKT条件) 知, 在最优点, 拉格朗日乘子与约束的积为0, 即

对于标准支持向量 (0<αi<C) , 由式 (1.10) 得到βi>O, 则由式 (l.12) 得到ξi=0, 因此, 对于任一标准支持向量, 满足

从而计算参数b为

为了计算可靠, 对所有标准支持向量分别计算b的值, 然后求平均, 即

其中, NNSV为标准支持向量数, .JN为标准支持向量的集合, J为支持向量的集合。

由式 (l.13) 可知, 支持向量机就是满足式 (l.10) 要求的样本数据, 支持向量如图1.4所示。式 (1.11) 中的约束条件约束了ω, b使得经验误差为o, 同时最小化||ω||2可使vc维最小, 因此式 (l.11) 的最优化体现了结构风险最小化准则, 具有较好的推广能力。

2.1.2非线性情况

训练集为非线性时, 通过一个非线性函数φ (·) 将训练集数据x映射到一高维线性特征空间, 在这个维数可能为无穷大的线性空间中构造最优分类超平面, 并得到分类器的决策函数。因此, 在非线性情况, 分类超平面为

决策函数为

最优分类超平面问题描述为

得到对偶最优化问题

其中K (xi, xj) =覬 (xi) ·覬 (xj) 称为核函数。决策函数和参数b分别为

其中的NNSV为标准支持向量数, JN为标准支持向量的集合, J为支持向量的集合。

由式 (1.19) -式 (l.21) 知, 尽管通过非线性函数将样本数据映射到具有高维甚至于无穷维的特征空间, 并在特征空间中构造最优分类超平面, 但在求解最优化问题和计算决策函数时并不需要显式计算该非线性函数, 而只需计算核函数, 从而避免特征空间维数灾难问题。核函数的选择必须满足Merce条件[Vapnik, 1995]。常见的核函数有线性函数K (xi, x) 二xi·x、多项式函数K (xi, x多) = (层x感i·x知+器1) 函d、数径向基函数K (xi, x) =exp (-x-xÁÁ?Á) 、

对于式 (l.12) 的KKT条件, 也可以写为 (非线性情况)

由于KKT条件是充要条件, 利用上式可判别α是否为最优。

2.2多类支持向量机算法

支持向量机最初是针对二类分类问题而提出的, 不能直接应用于多类分类问题。目前, 有关多类支持向量机的研究较少, 实际应用中主要采用的算法可以分为两种类型: (l) 一次性求解方法[1] (2) 通过组合多个二值SVM子分类器, 实现多类别分类, 其中包括"一对多" (one-against-rest, OAR) 方法、"一对一" (one-againstone, OAO) 方法、DDAGSVM ( (Decision Directed Acyclic Graph SVM) 方法、二叉决策树方法 (Binary DecisionTree) 等[2,3]。

三、支持向量机的应用

统计学习理论从七十年代末诞生, 到九十年代之前都处在初级研究阶段, 近几年才逐渐得到重视, 其本身也趋向完善, 并产生了支持向量机理论付诸实现的有效的机器学习方法。目前, SVM算法在模式识别、概率密度、函数估计等方面都有应用。例如, 在模式识别方面, 对于手写字识别、语音识别、文本分类、人脸图像识别、遥感图像分析等问题, SVM算法在精度上已经超过传统的学习算法或与之不相上下。

支持向量机在工业领域的应用研究正逐渐受到研究者的重视。支持向量机用于系统辨识, 进行线性和非线性动态系统的辨识。De Kruif将支持向量机用于前馈学习控制, Suykens将最小二乘支持向量机应用于非线性系统的最优控制。

支持向量机还被应用到其它一些领域。支持向量机在时间序列的预测和混沌系统的动态重构中显示出了强大的优势。在信号处理方面, Chen对多路径通道DS-CDMA信号传输构造了一个基于支持向量机的自适应多用户检测将自适应参数SVM用于对经济时间序列的预测。

参考文献

[1]Vapnik V N.张学工译.统计学习理论的本质[M].北京:清华大学出版社, 2000.

[2]邓乃扬, 田英杰.数据挖掘中的新方法-支持向量机.北京:科学出版社, 2004

[3]张学工.关于统计学习理论与支持向量机.自动化学报, 2000, 26 (1) :32-42

[4]Vapnik V, Chapelle O.Bounds on error expectation for supportvector machines Neural Computation, 2000, 12 (9) :2013-2036

[5]Wahba G, Lin Y., Zhang H.GACV for support vector machine.Advance in Larger Margin Classifiers, MIT Press, 1999

[6]杜树新, 吴铁军, 模式识别中的支持向量机方法[J], 浙江大学学报 (工学版) , 2003

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【粒度支持向量机】相关文章：

支持向量回归机模型05-12