没有合适的资源?快使用搜索试试~ 我知道了~
首页Opencv2.4.9源码分析——Support Vector Machines
Opencv2.4.9源码分析——Support Vector Machines
5星 · 超过95%的资源 需积分: 9 105 下载量 199 浏览量
更新于2023-06-01
评论 3
收藏 689KB PDF 举报
本文档共分为三个部分,第一个部分介绍SVM的原理,我们全面介绍了5中常用的SVM算法:C-SVC、ν-SVC、单类SVM、ε-SVR和ν-SVR,其中C-SVC和ν-SVC不仅介绍了处理两类分类问题的情况,还介绍处理多类问题的情况。在具体求解SVM过程中,我们介绍了SMO算法和广义SMO算法。第二个部分我们给出了OpenCV中SVM程序的详细注解。第三个部分我们给出了一个基于OpenCV的SVM算法的简单应用实例。
资源详情
资源评论
资源推荐
1
Opencv2.4.9 源码分析——SupportVectorMachines
赵春江
http://blog.csdn.net/zhaocj
〇、引言
本文共分为三个部分,第一个部分介绍 SVM 的原理,我们全面介绍了 5 中常用的 SVM
算法:C-SVC、ν-SVC、单类 SVM、ε-SVR 和 ν-SVR,其中 C-SVC 和 ν-SVC 不仅介绍了处
理两类分类问题的情况,还介绍处理多类问题的情况。在具体求解 SVM 过程中,我们介绍
了 SMO 算法和广义 SMO 算法。第二个部分我们给出了 OpenCV 中 SVM 程序的详细注解。
第三个部分我们给出了一个基于 OpenCV 的 SVM 算法的简单应用实例。
一、原理
支持向量机(SVM,Support Vector Machine)是一种监督的学习算法,它不仅可以用于
分类问题(称之为 SVC),还可以用于回归问题(称之为 SVR)。该算法最早是由 Vapnik 等
人于 1963 年首次提出,然而在经过了将近 30 年的时间后,在 1992 年由 Boser,Guyon 和
Vapnik 等人撰写的一篇论文——Atrainingalgorithmforoptimalmarginclassifiers,才最终奠定
了 SVM 在机器学习领域的重要地位。SVM 算法的重要性不仅体现在理论上,还体现在它的
实效性。理论性好主要表现为以下三点:1、对含有大量特征属性的小样本具有很强的鲁棒
性;2、对简单和复杂分类模型都具有很强的学习能力;3、如果采用复杂的数学模型,可以
有效的避免过拟合的现象。实效性强主要表现为在目前应用 SVM 的许多场合中,SVM 都能
给出很满意的结果,并普遍好于其他机器学习算法。
SVM 最主要的分类方法有 C-SVC 和 ν-SVC,它们不仅可以处理 2 类问题,还可以处理
多类问题。SVM 最主要的回归方法有 ε-SVR 和 ν-SVR,另外 SVM 类型中还包括单类 SVM
算法。在求解 SVM 算法中,SMO 算法的性能比较突出,并且林智仁等人还在此基础上提出
了广义 SMO 算法。上述提到的各种算法,我们都会一一详细的给出介绍。
1、C‐SVC 算法
在训练样本集中一共有 N 个样本,每个样本可以用含有
p 个元素的向量 x
i
∈R
p
,i=1,…,N
表示,即 x
i
=(x
1
,x
2
,…,x
p
),这 p 个元素分别表示样本 x
i
的 p 个特征属性。每个样本 x
i
又分别
对应一个标签 y
i
∈{+1,‐1},用于表示该样本的分类,即 x
i
要么属于用+1 表示的类(称之为正
例),要么属于用‐1 表示的类(称之为负例)。
如果该训练样本集可以用超平面正确的分隔开来,即属于正例的样本全部在超平面的同
2
一侧,而属于负例的样本全部在超平面的另一侧,则我们称该样本集线性可分。图 1 直观的
表现了只含有两个特征属性的样本集的线性可分情况。对于二维空间,超平面是一条直线,
对于三维空间,超平面是一个平面,也就是在 p 维空间内,用于线性分隔的超平面是 p-1 维
的。图 1 中的虚线就是线性可分的超平面。
Ox
1
x
2
图 1 二维空间的线性可分
超平面的方程可以表示为:
∙0
(1)
式中,w 表示向量 x 的权向量,即 w=(w
1
,w
2
,…,w
p
),b 表示偏移量,w·x 表示向量 w 和 x 点
乘。因此,对于线性可分的判别式可以表示为:
∙
0如果
1
∙
0如果
1
(2)
对于一个新的样本,只需带入下式的决策函数,就可以判断它的分类情况:
sgn∙
(3)
式中,sgn(x)为符号函数,x 大于 0,函数值为 1,x 小于 0,函数值为-1。
对于超平面来说,w 的含义是法向量,一个超平面的法向量有无数条,但它的单位法向
量只有一个,超平面到原点的距离也是唯一的。如果 w
1
和 w
2
都是式 1 所表示的超平面的法
向量,则它们一定是平行的,即它们一定满足下列条件:
(4)
式中,k 为任意实数。而它们的单位法向量
是相同的,即:
‖
‖
‖
‖
‖
‖
3
(5)
式中,||w||表示 w 的 L
2
范数。式 1 所表示的超平面到原点的距离
为:
‖
‖
(6)
我们对式 1 两边除以||w||,则该超平面就用
和
表示为:
‖
‖
∙
‖
‖
∙
0
(7)
通过比较式 1 和式 7 可以看出,(w, b)和(kw, kb)表示的是同一个超平面(在式 7 中,
kw=
,kb=
,k=1/||w||),因此我们可以得出这样的结论:无论 k 为多少,它们的单位法向
量和到原点的距离都是相等的,也就是说超平面与 k 无关。
Ox
1
x
2
图 2 不同的超平面
从图 2 可以看出,分隔两类的超平面可能有无数个,那么我们就需要选择一个最佳的超
平面用于分隔。这个最佳分隔超平面不仅要能够正确的对样本数据进行分类,更重要的是分
类的确信度要大。超平面离两侧的样本数据的间隔(margin)越大,分类的确信度就越大。
因此 SVC 本质上是最大间隔分类器。
如图 3 所示,我们得到了最大间隔,其中超平面 H1 和 H2 分别是+1 和‐1 的间隔边界超
平面,它们与分隔超平面 H 平行,并且等间距。因此只要 H1 和 H2 已知,H 就会唯一的确
定下来。H1 和 H2 形成了一个分隔带,在分隔带内没有任何样本数据,但在 H1 和 H2 上会
有一些样本数据(实心部分),这些样本非常重要,因为 H1 和 H2 的形成完全取决于这些样
本,当这些样本的全部、甚至一部分改变位置时,H1 和 H2 就要重新确定。而其他的样本数
据就变得无足轻重,移动位置(只要不移动到分隔带内)甚至把它们去掉,都不会影响 H1
和 H2。因此我们把 H1 和 H2 上的样本称为“支持向量”,事实上支持向量的样本数量会远远
小于非支持向量的样本数量。
4
Ox
1
x
2
H
H1
H2
1
bxw
1 bxw
w1
w1
0
bxw
图 3 间隔
式 1 表示的是分隔超平面 H,由于 H 和 H1 平行,因此它们的法向量可以是相同的,但
偏移量不同,所以我们可以用下式表示 H1 :
∙
(8)
其中 H1 的偏移量为 b-c,因 此 (w, b-c)这两组参数表示了 H1。由前面的分析可知,只要对
(w, b-c)等比例的缩放,最终所得到超平面仍然是 H1 ,所以我们对式 8 除以 c,得到
∙
1
(9)
为了符号统一,我们仍然使用 w 和 b,则式 9 重新写为:
∙1
(10)
之所以要得到式 10,主要是要使等式的右边为 1,这样做便于后面的公式推导。由于 H 与
H1 和 H2 等间距,因此依据式 10,H2 的表示形式为:
∙1
(11)
即 H1 和 H2 相对于 H 的偏移量都为 1 个单位长度,一个是相左偏移,一个是相右偏移。
我们已经有了 H1 和 H2,因此就可以用它们来实现对样本数据的分类,即
∙
1如果
1
∙
1如果
1
(12)
如果我们对式 12 的两个不等式的两边都乘以 y
i
,则这两个不等式可以合并为一个,即
∙
11,2,…,
(13)
5
下面我们计算 H1 和 H2 的距离 D,即分隔带的宽度,它应该等于 H1 和 H2 到原点距离
之差的绝对值,即
|
1
1
|
‖
‖
2
‖
‖
(14)
由前面的分析可知,线性可分的 SVM 的目标是使 D 最大,即
max
2
‖
‖
(15)
而式 15 与下式是等价的:
min
1
2
‖
‖
min
1
2
(16)
式中,1/2 是为了方便后面的求导。式 16 是最大间隔分类器的最终目的,即它是目标函数,
我们要得到权向量 w 的每个元素 w
i
。式 13 是约束条件,它保障了分类的正确,我们把式 16
和式 13 写到一起,就得到了线性可分 SVM 的原公式(primal formulation,即线性可分 SVM
的原始模型):
min
1
2
‖
‖
min
1
2
,受限于
∙
11,2,…,
(17)
如果 S 为凸集,f 是 S 上的凸函数,g
i
(i=1,2,…,m)是 S 上的凹函数,则:
min,受限于
01,2,…,
(18)
为凸规划问题,它具有的一个重要性质是 min
f(x)的局部极小点就是全局极小点,并且唯一
存在。我们来判断式 17,R
p
⊆ R
n
(整个欧式空间),因此它属于凸集,
∑
是凸函数,y
i
(w·x
i
+b)-1 是基于 w 的线性函数,它既是凹函数又是凸函数,所以式 17 是一个凸规划问题,
它的解存在且唯一,而且是全局最优解。
我们再来看下面的公式:
min
1
2
,受限于
(19)
式中,x 表示含有 n 个元素的待求向量,c 和 b 分别为 n 维和 m 维的实数向量,Q 为 n×n 的
实对称矩阵,A 为 m×n 的实矩阵,上标 T 表示转置,Ax ≤ b 表示向量 Ax 的每个元素都小于
或等于向量 b 中的相对应元素。式 19 的含义就是二次规划(quadratic programming)问题。
我们把该式与式 17 进行比较就会发现,如果式 19 中的未知量 x 为式 17 中的 w,Q 为 p×p
剩余69页未读,继续阅读
zhaocj
- 粉丝: 2551
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2