《数据挖掘原理与应用 第2版 》课件 6.6分类预测-支持向量机

第6章分类预测支持向量机支持向量机支持向量机是在统计学理论的基础上最新发展起来的新一代学习算法，是一种借助最优化方法解决机器学习问题的新工具，也是数据挖掘中的一项新技术。支持向量机(SVM，SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。原理【例】建立分类模型xyc

xyc5.211.2+1

18.08.0-14.014.1+1

19.55.5-19.011.0+1

20.07.0-14.95.5+1

17.06.4-13.28.0+1

16.05.1-17.213.9+1

12.56.0-18.07.0+1

17.72.0-13.010.5+1

16.83.7-16.27.9+1

14.57.5-1？分割线在分割线右侧

C2在分割线左侧

C1训练数据原理【例】建立分类模型分割线可以有无穷多个，分割线的位置不同，则对未分类点的分类结果也会不同：未分类点被分割线l1分类为C2而对于分割l2，则会被分类为C1怎样分割合适？靠“中间”！l1l2原理设分割线：方法1两个类中相距最近的点的连线的垂直平分线作为分割线。这种方法不能保证分割线能够在中间位置，有时用这种方法甚至无法找出正确的分割线原理设分割线：方法2找出C1中临近C2的两个点并连线，平行推移到最临近的C2中的点，取中间位置做分割线；或者反过来，找出C2中临近C1的两个点并连线，平行推移到最临近的C1中的点，取中间位置做分割线。能使分类间隔较宽的分割线即为最优分割线。支持向量确定分割线时，图中提供垂直平分线的两个点构成的向量，支持了分割线的确定。这些点被称为支持向量(SupprotVectors)边界线分割线到间隔线（图中虚线）的距离被称为分类间隔，虚线称为边界线分割线方程二维平面

分割线方程二维平面

分类模型

分类模型

【例】建立分类模型

xyc

xyc5.211.2+1

18.08.0-14.014.1+1

19.55.5-19.011.0+1

20.07.0-14.95.5+1

17.06.4-13.28.0+1

16.05.1-17.213.9+1

12.56.0-18.07.0+1

17.72.0-13.010.5+1

16.83.7-16.27.9+1

14.57.5-1训练数据

【例】建立分类模型

分类间隔约为3.5【例】建立分类模型

分类间隔约为4.6

分类间隔最大化的过程。【例】建立分类模型

(9,11)(8,7)(12.5,6)得平行于得到分类模型

【例】建立分类模型(12.5,9)对未知数据点进行分类有应分类为C2。支持向量机分类模型：

支持向量机分类总结来说，支持向量机的原理就是根据给定的训练数据，找到一个最优分割线或超平面，能够正确地对训练数据进行分类，建立起有效的分类模型，并可对新数据进行正确分类。这里所说的最优，就是使分割线或超平面距两个类别的数据点具有最大的最小距离。支持向量机分类直观上，在两个类之间能够找到一条分割线，使得C1类中的数据点距该分割线的距离的最小值，与C2类中的数据点距该分割线的距离的最小值相等，即分割线能够在“中间”分割两个类别的数据，则认为这条分割线能够较好地代表了对C1和C2类的分类。进一步，如果能够找到使这个距离的最小值最大的分割线，则找到了对数据进行划分的模型。PartI多维数据，分割超平面对于训练数据为多维数据的情况，则数据被映射到一个高维度的空间，同样可以在这个多维空间中，找出一个超平面，将两个不同类的数据集合区分开来。多维数据，分割超平面

多维数据，分割超平面

多维数据，分割超平面

定义分割超平面

定义分割超平面距超平面最近的点，到超平面的距离，可以表示为：

定义分割超平面

则

定义分割超平面

或等效地：

求解分割超平面拉格朗日函数

求解分割超平面拉格朗日函数对偶性SMOKaruch-Kuhn-Tucher（KKT）条件二次规划方法

几点扩展对于互相渗透的情况引入松弛变量

几点扩展对于互相渗透的情况为“+”为“-”找不到符合条件的线性函数y≥0，x<0;否则x>0多类问题SVM是对二类问题设计的，其对应方法也是针对二类问题的，如何处理多类问题?训练令C={c1,c2,...,ck}是类标号的集合1-r方法：分解成k个二类问题每一个类ci

C创建一个二类问题，其中所有属于ci的样本都被看作正类，而其他样本作为负类1-1方法：构建k(k

1)/2个二类分类器每一个分类器用来区分一对类(ci,cj)为类(ci,cj)构建二类分类器时，不属于ci或cj的样本被忽略掉32多类问题(续)分类投票表决票的计算1-r方法如果一个样本被分为正类，则正类得一票如果一个样本被分为负类，则除正类之外的所有类都得到一票1-1方法

如果Cj把样本分到yi类，则yi类得一票冲突处理分到多数类/少数类33多类问题:例例：C={c1,c2,c3,c4}1-r方法建立4个分类器(1/234,2/134,3/124,4/123)设这4个分类器分别把检验实例x

分类为+，

，

，

使用简单的多数表决，c1得到最高的票4，而其他类仅仅得到3票，因此检验实例被分类为c11-1方法建立6个分类器(1/2,1/3,1/4,2/3,2/4,3/4)假设它们对

x投票结果如下表c1和c4都得到2票，而c2和c3仅仅得到1票34二类分类器类对+：c1

：c2

+：c1

：c3

+：c1

：c4

+：c2

：c3

+：c2

：c4

+：c3