SVM理论之线性分类

标签: svm 理论 线性 | 发表时间:2013-06-07 23:50 | 作者:Seiyagoo
出处:http://www.cnblogs.com/
  离上次发博文差不多有一年的时间了,因为一直在准备考研直到4月份才有时间,无奈考研后进入空白期,对专业、技术甚至生活失去了兴趣,部分原因也是没有什么好写
的,现在刚做完毕设,有点积累,就从这里开始吧!希望能尽快找回节奏!
  我将从svm理论到应用,分享一下学习经历,文章有很多内容来自文献和网络牛人,后面给出链接。我自己也阅读了好几遍(写得真的很不错),思考后加入了自己的理解,
且作为一系列的学习笔记吧。
 
 
相关学科、领域的关系
 
1、数据挖掘和机器学习:
     数据挖掘受到很多学科领域的影响,其中数据库、机器学习、统计学无疑影响最大。简言之,对数据挖掘而言,数据库提供数据管理技术,机器学习和统计学提供数据分析
技术。由于统计学往往醉心于理论的优美而忽视实际的效用,因此,统计学界提供的很多技术通常都要在机器学习界进一步研究,变成有效的机器学习算法之后才能再进入数据
挖掘领域。从这个意义上说,统计学主要是通过机器学习来对数据挖掘发挥影响,而机器学习和数据库则是数据挖掘的两大支撑技术。
     从数据分析的角度来看,绝大多数数据挖掘技术都来自机器学习领域,但机器学习研究往往并不把海量数据作为处理对象,因此,数据挖掘要对算法进行改造,使得算法性能
和空间占用达到实用的地步。同时,数据挖掘还有自身独特的内容,即关联分析。
 
2、模式识别和机器学习:
     传统的模式识别的方法一般分为两种:统计方法和句法方法。句法分析一般是不可学习的,而统计分析则是发展了不少机器学习的方法。也就是说,机器学习同样是给模式识别
提供了数据分析技术。机器学习是方法,模式识别是目的。
 
3、数据挖掘和模式识别:
     从其概念上来区分吧,数据挖掘重在发现知识,模式识别重在认识事物。
 
 
什么是SVM
 
     SVM是一种分类算法,所以先从分类开始。分类作为数据挖掘领域中一项非常重要的任务,目前在商业上应用最多(比如分析型CRM里面的客户分类模型,客户流失模型,客户
盈利等等,其本质上都属于分类问题)。而分类的目的则是学会一个分类函数或分类模型(或者叫做分类器),该模型能吧数据库中的数据项映射到给定类别中的某一个,从而可以用
于预测未知类别。
     下面是一个心脏病的例子:现代医学里可以利用一些比较容易获得的临床指标推断某人是否得了心脏病,假定是否患有心脏病与病人的年龄和胆固醇水平密切相关。比如说医生
可以根据以往病人的临床资料(年龄,胆固醇等),对后来新来的病人通过检测年龄、胆固醇等指标,以此来推断或者判定病人是否有心脏病。而这就是分类(classification)技
术。下表对应10个病人的临床数据(年龄用[x1]表示,胆固醇水平用[x2]表示):
     
     
     这样,问题就变成了一个在二维空间上的分类问题,可以在平面直角坐标系中描述如下:根据病人的两项指标和有无心脏病,把每个病人用一个样本点来表示,有心脏病者用
“+”形点表示,无心脏病者用圆形点,如下图所示:
     
     很明显的看到,可以在该平面上用一条直线把圆点和“+”分开来的。
 
 
svm应用
 
     SVM是由Vanpik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术。它是一种基于统计学习理论的模式识别方法,在解决小样本、非线性及
高维模式识别问题中表现出许多独特的优势,SVM不同于很多只限于实验室研究使用的算法,SVM不仅是学术界非常有力的研究方法,并且广泛运用于商业应用,在文本分类和
手写识别、生物信息学等领域都取得了成功的应用。
 
 
线性分类

(1) 分类问题定义
     一般使用X表示输入空间,Y表示输出域。通常X∈Rn,对于两类问题,Y = {-1, 1};对于多类问题,Y = {1,2,…,m}; 训练集是训练数据(样本)的集合,通常S=((x1,y1),..(xn, yn))
∈(X×Y)n,其中n是样本数目,xi是样本(向量),yi是它们的标记。

(2) 线性判别函数
     线性函数:在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是一个平面,如果不关注空间的维数,这种线性函数还有一个统一的名称——超平面(Hyper Plane)。
     由x的各个分量的线性组合而成的线性函数 :
                            g(x) = wT•x + b    (参数w是权重向量、b是偏置向量;w、x都为n维向量,b为实数).                     (1)
             方程g(x)=0                                                                                                                                      (2)
      定义了一个判定面(分类面),它把归类于C1的点与归类于C2的点分开来。当x1和x2都在判定面上时,有g(x 1)=g(x 2)即w T •x 1 + b = w T •x 2 + b ,故 w T •(x 1– x 2 )=0 ,
这表明w和超平面上任意向量正交,并称w为超平面的法向量。

两类情况:对于两类问题的决策规则为
•     如果g(x)>0,则判定x属于C1,
•     如果g(x)<0,则判定x属于C2;

此时也等价于给函数g(x)附加一个符号函数sgn(),即f(x)=sgn [g(x)]是我们真正的判别函数。如果 g(x)=0,则很难办了,分到哪一类都不是。事实上,对于 g(x)的绝对值很小的
情况(即接近超平面的点),我们都很难处理,因为细微的变动(比如超平面稍微转一个小角度)就有可能导致结果类别的改变。理想情况下,我们希望 g(x) 的值都是很大的正数
或者很小的负数,这样我们就能更加确信它是属于其中某一类别的。
 
 
                    图1

(3) 线性可分与不可分
 
线性可分:若存在一线性函数能够把两类点完全分开。称此训练集为线性可分的。

定义一个点到某个超平面的函数间隔(functional margin):γ f=y i(w T •x i+b) 。由两分类问题可知,γ f总大于0. 考虑w和b,如果同时加大w和b,比如在 前面乘个系数比如2,
那么所有点的函数间隔都会增大二倍,这个对求解问题来说不应该有影响,因为我们要求解的是 ,同时扩大w和b对结果是无影响的。这样,我们为了限制w和b,可能需要加入
归一化条件,毕竟求解的目标是确定唯一一个w和b,而不是多组线性相关的向量。现在把w和b进行一下归一化,即用 分别代替原来的w和b,那么间隔就可以写成
γ g = ,此时称γ g为几何间隔(geometrical margin),它就是解析几何中点xi 到直线g(x)=0的距离公式(推广则是到超平面g(x)=0的距离, g(x)=0就是上面提到的分类
超平面)。
注:|w||叫做向量w的范数,范数是对向量长度的一种度量。向量w=(w 1, w 2, w 3,…… w n),它的p-范数为||w||p = (w 1 p+w 2 p+…+w n p)  
            图2
 
 
归一化的几何意义:
       如图所示,假设我们有了B点所在的 分割面。任何其他一点,比如A到该面的距离以γ表示,假设B就是A在分割面上的投影。我们知道向量BA的方向是 w
(分割面的梯度),单位向量是 。设A为x,B为x 0(x、x 0都是向量),向量BA = x-x 0 = γ . 又由于 x 0 是超平面上的点,满足 f(x 0)=0 ,代入超平面的方程,
两边同乘||w||,又w Tw=||w|| 2,即可算出 γ=  。这里的 γ 是带符号的,我们需要的只是它的绝对值,类似地,也乘上对应的类别 y
                         γ = yγ =  .                                                                  (3)
即函数间隔归一化结果就是几何间隔。
 

线性不可分:本属于某一类的点跑到另一类(分类面的另一侧),即存在离群点。
                                   图3
 
 
 
参考:《支持向量机导论》
 

本文链接

相关 [svm 理论 线性] 推荐:

SVM理论之线性分类

- - 博客园_首页
  离上次发博文差不多有一年的时间了,因为一直在准备考研直到4月份才有时间,无奈考研后进入空白期,对专业、技术甚至生活失去了兴趣,部分原因也是没有什么好写. 的,现在刚做完毕设,有点积累,就从这里开始吧.   我将从svm理论到应用,分享一下学习经历,文章有很多内容来自文献和网络牛人,后面给出链接.

CAP 理论

- - 忘我的追寻
CAP理论被很多人拿来作为分布式系统设计的金律,然而感觉大家对CAP这三个属性的认识却存在不少误区. 从CAP的证明中可以看出来,这个理论的成立是需要很明确的对C、A、P三个概念进行界定的前提下的. 在本文中笔者希望可以对论文和一些参考资料进行总结并附带一些思考. CAP原本是一个猜想,2000年PODC大会的时候大牛Brewer提出的,他认为在设计一个大规模可扩放的网络服务时候会遇到三个特性:一致性(consistency)、可用性(Availability)、分区容错(partition-tolerance)都需要的情景,然而这是不可能都实现的.

zookeeper 理论

- - zzm
引用官方的说法:“Zookeeper是一个高性能,分布式的,开源分布式应用协调服务. 它提供了简单原始的功能,分布式应用可以基于它实现更高级 的服务,比如同步,配置管理,集群管理,名空间. 它被设计为易于编程,使用文件系统目录树作为数据模型. 服务端跑在java上,提供java和C的客户端 API”.

气球的理论

- Pen - 我是白骨精
最近的都是小事物大哲理系列么…….

情绪ABC理论

- - CSDN博客互联网推荐文章
  ABC理论是由美国心理学家埃利斯创建的. 错误信念也称为非理性信念.   如图中,A(Antecedent)指事情的前因,C(Consequence)指事情的后果,有前因必有后果,但是有同样的前因A,产生了不一样的后果C1和C2. 这是因为从前因到结果之间,一定会透过一座桥梁B(Bridge),这座桥梁就是信念和我们对情境的评价与解释.

长尾理论和web2.0

- 弛 - 学而时嘻之
Thomas Friedman 的《世界是平的》是一本很不错的书,我还特意做了详细的读书笔记. 作为一个记者,作者能够观察到这个趋势,能够给出建议,甚至做出预测,但他未能总结出 一个抽象的理论. 假设你开公司,第一步就是骗风险投资,如果你跟人家说世界是平的,人肯定说你说的那本畅销书连我妈都看过了. 我感觉现在最流行的两个词是”长尾理论”和”web2.0″,很可能是风险投资公司最爱听的词.

10000小时天才理论

- - 牛博
10000小时天才理论. 这本书的作者安德斯•埃里克森研究了体育、音乐、教育等很多领域的成功人士后发现,无论在任何一个领域如果想达到世界级的水平必需投入10000小时. 相对比天分和努力来说,正像王安石《伤仲永》讲的那样,有天分没有成功的人比皆是,没有天分占成功人士的比例更多的原因就是他们有没有持续投入10000小时.

NOSQL 相关概念理论

- - SQL - 编程语言 - ITeye博客
本文介绍一下NoSQL相关的知识. 书籍推荐 <> 英文名 <> 作者 Martin Fowler.    第一眼看到NoSQL时把它理解为No SQL,这让我着实高兴了一阵子. 因为我对SQL没啥兴趣,尤其遇到写Function、Procedure、Trigger时更是烦恼.

Redis Cluster理论整理

- - 开源软件 - ITeye博客
Redis 集群的 TCP 端口(Redis Cluster TCP ports). 每个 Redis 集群节点需要两个 TCP 连接打开. 正常的 TCP 端口用来服务客户端,例如 6379,加 10000 的端口用作数据端口,在上面的例子中就是 16379. 第二个大一些的端口用于集群总线(bus),也就是使用二进制协议的点到点通信通道.

Hive Lock 理论与实践

- - leejun2005的个人页面
最近两天数据仓库中一张核心表遭遇了锁的问题,导致数据插入失败,影响挺大,之前一直没注意到这个问题,借此总结一下这块的知识和遇到的坑. hive 在 0.7 版本之后开始支持并发,线上的环境默认是用 zookeeper 做 hive 的锁管理,Hive开启并发功能的时候自动开启锁功能. hive 目前主要有两种锁,SHARED(共享锁 S)和 Exclusive(排他锁 X).