支持向量分类机与入侵检测课件

什么是入侵检测v入侵是指系统的未授权用户试图或已经窃取了系统的访问权限,以及系统的被授权用户超越或滥用系统所授予的访问权限,而进行的有目的的威胁或危害网络资源的完整性(Integrity)、机密性(Confidentiality)或有效性(Availability)的行为集合。;为什么可以把SVM应用于入侵检测系统 标准的SVM的核心思想是:对于输入空间中非线性可分的的情形,选择一个适当的非线性映射,将输入空间中的样本点映射到一个高维的特征空间,使得对应的样本点在该特征空间中是线性可分SVM算法对于两类问题的分类问题,有许多成功的应用实例。然而,标准的SVM在训练过程中要求同时使用正样本和负样本。但是在某些应用领域,更关心一类样本正样本,例如:信息检索以及入侵检测中。笔者将入侵行为以及被怀疑为入侵行为或存在入侵倾向者所对应的数据规定为负样本,而正常数据规定为正样本。根据SVM理论,2类SVM分类器的分类超平面由靠近分类超平面的支持向量决定。而实际操作中,只需要选用比较靠近分类面的样本点即可。但是,当负样本的数量不足时会严重影响分类器的泛化性能。并且,由于用于训练的负样本数量不足,将直接导致分类器的错误率太高。因此,支持向量机至今仍没有真正应用到入侵检测这一重要的领域。SVM:What is it and what can it do for me?vSVM,Support Vector Machine,简而言之它是个起源跟类神经网路有点像的东西，不过现今最常拿來就是做分类(classification)。也就是说，如果我有一堆已经分好类的东西（可是分类的依据是未知的！），那当收到新的东西时，SVM 可以预测(predict)新的资料要分到哪一堆去。v听起來是很神奇的事，请重想一想这句话代表什么：分类的依据是未知的！也很像要 AI 之类的高等技巧.不过 SVM 基于统计学习理论统计学习理论 可以在合理的时间內漂亮的解決这个问题。以图形化的例子来说明(by SVMToy),像假定我在空间中标了一堆用颜色分类的点，点的颜色就是他的类別,位置就是他的資料,那 SVM 就可以找出间隔这些点的方程式,依此就可以分出一个个的区域;拿到新的点(资料）时,只要对照该位置在哪一区域就可以(predict)找出他应该是哪一颜色(类別)了v当然 SVM 不是真的只有画图分区那么简单,不过看上面的例子应该可以了解 SVM 大概在作什么.vSVM有关概念介绍vSVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面vSVM分解算法HistoryvSVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。关于SVMv思想：通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。v途径：构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrained quadratic programing),求解该问题，构造分类超平面，从而得到决策函数。提纲提纲vSVM有关概念介绍vSVM分类问题的数学表示和推导v简单的最优分类面v广义最优分类面v非线性最优分类面vSVM分解算法ayestdenotes+1denotes-1f xf(x)=sgn(w.x+b)How would you classify this data?ayestdenotes+1denotes-1f xf(x)=sgn(w.x+b)How would you classify this data?ayestdenotes+1denotes-1f xf(x)=sgn(w.x+b)Copyright 2001,2003,Andrew W.MooreHow would you classify this data?ayestdenotes+1denotes-1f xf(x)=sgn(w.x+b)How would you classify this data?分类问题的数学表示分类问题的数学表示已知：已知：训练集包含 个样本点：说明：说明：是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；是输出指标，或输出.问题问题：对一个新的模式 ，推断它所对应的输出 是1还是-1.实质：实质：找到一个把 上的点分成两部分的规则.2维空间上的分类问题)n维空间上的分类问题.根据给定的训练集其中，寻找 上的一个实值函数 ，用决策函数判断任一模式 对应的 值.可见，分类学习机构造决策函数的方法(算法)，两类分类问题 多类分类问题 线性分类学习机 非线性分类学习机 分类学习方法分类学习方法SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。最大间隔原则最大间隔原则考虑图1.2.1(a)上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取如何选取 和和？简单问题：简单问题：设法方向 已选定，如何选取？解答：解答：选定 平行直线 极端直线 和 取 和 的中间线为分划直线如何选取如何选取？对应一个 ，有极端直线 ，称 和 之间的距离为“间隔”.显然应选使“间隔”最大的 。最大间隔法的直观导出最大间隔法的直观导出数学语言描述：数学语言描述：给定适当的法方向 后，这两条极端直线 可表示为调整 ，使得令 ，则两式可以等价写为与此相应的分划直线表达式:如何计算分划间隔？如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况求出两条极端直线的距离：分划直线表达式为 “间隔”为极大化“间隔”的思想导致求解下列对变量 和 的最优化问题说明：说明：只要我们求得该问题的最优解 ，从而构造分划超平面 ，求出决策函数 。上述方法对一般 上的分类问题也适用.原始问题原始问题求解原始问题？求解原始问题？为求解原始问题，根据最优化理论，我们转化为对偶问题来求解对偶问题对偶问题 为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解1.线性可分问题线性可分问题计算 ，选择 的一个正分量 ,并据此计算事实上，的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。称 不为零的这些训练点的输入 为支持向量支持向量(SV)构造分划超平面 ,决策函数根据最优解2.近似线性可分问题近似线性可分问题不要求所有训练点都满足约束条件 ，为此对第 个训练点 引入松弛变量松弛变量(Slack Variable),把约束条件放松到 。体现了训练集被错分的情况，可采用 作为一种度量来描述错划程度。两个目标两个目标：1.间隔 尽可能大 2.错划程度 尽可能小显然，当 充分大时，样本点 总可以满足以上约束条件。然而事实上应避免 太大，所以需在目标函数对 进行惩罚（即“软化”约束条件）2.近似线性可分问题近似线性可分问题因此，引入一个惩罚参数惩罚参数 ，新的目标函数变为:体现了经验风险，而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。算法：算法：(广义广义)线性支持向量分类机线性支持向量分类机1.设已知训练集 ，其中 2.选择适当的惩罚参数 ，构造并求解最优化问题 3.计算 ，选择 的一个分量 ，并据此 计算出 4.构造分划超平面 ,决策函数求得3.非线性分划非线性分划例子:实现非线性分划的思想实现非线性分划的思想决策函数其中核函数核函数(核或正定核核或正定核)定义定义设 是 中的一个子集。称定义在 上的函数 是核函数(正定核或核)，如果存在着从 到某一个空间 的映射使得其中 表示 中的内积核函数的选择核函数的选择n多项式内核n径向基函数内核RBFnSigmoind内核目前研究最多的核函数主要有三类：得到q 阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定Thank you!