第04讲不确定性决策理论与方法概要.ppt

神经网络 不确定性决策理论与方法 1、不确定性决策概述 2、关联规则发现 3、聚类分析 4、连接分析 5、粗糙集分析 6、决策树 7、神经网络 8、支持向量机 支持向量机 20世纪90年代Vapnik提出了支持向量机(Support Vector Machines,SVM)，它被看作是高维空间函数表达的一般方法。使用SVM方法，人们可以在很高维的空间里构造好的分类规则。 支持向量机 经验风险最小化与结构风险最小化原则 经验风险最小化原则 考虑分类问题。样本集为U={x1,x2,...,xl}(m维空间中的l个向量)，每个向量对应一个类别，类别空间Y={+1,-1}。记p(x,y)表示对象x为y类的概率分布。分类的任务就是寻找分类器f：U→Y且使期望风险最小。f的期望风险为： 在有限样本的情况下，p(x,y)是未知的，因此期望风险无法计算。常使用经验风险代替，且当l→∞时两者相等。 支持向量机 如果 成立，则称经验风险最小化原则（Empirical Risk Minimization, ERM）具有一致性。 结构风险最小化原则 Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值，即ERM不成立。因此提出了结构风险最小化原则(Structural Risk Minimization, SRM)，为小样本统计理论奠定了基础。 支持向量机 Vapnik和 Chervonenkis通过研究，得出了期望风险和经验风险的如下关系以概率1-?成立，即 l为样本点数目；参数0???1；h为函数f的维数，简称VC维。(在无法求得期望风险的情形下找到了它的一个上界) 不等式右边与样本的具体分布无关，即Vapnik的统计学习理论无需假设样本分布，克服了高维分布对样本点需求随维数而指数增长的问题。这是小样本统计理论与经典统计理论的本质区别，也是将Vapnik统计方法称之为小样本统计理论的原因。 VC维置信度 支持向量机 讨论： (1)如果l/h较大，则期望风险(实际风险)主要由经验风险来决定，因此对于大样本集经验风险经常能给出较好结果。 (2)如果比值l/h较小(小样本集)，则小的经验风险并不能保证有小的期望风险值，必须同时考虑经验风险和置信范围(称之为VC维置信度)。VC维在其中起重要作用，实际上置信范围是h的增函数。在样本点数目l一定时，分类器越复杂，即VC维越大，则置信范围越大，导致实际风险与经验风险的差别越大。 结论：要想使实际风险最小不仅要使经验风险最小，还同时需要使分类器函数f的VC维h尽可能最小，这就是结构风险最小化原则。因此寻找最小属性集变得非常有意义。 支持向量机 支持向量分类模型 基本分类思想：支持向量机的核心思想是将结构风险最小化原则引入到分类问题中。从线性可分情况下的最优分类超平面发展而来的，其本质是在训练样本中找出具有最优分类超平面的支持向量。在数学上归结为一个求解不等式约束条件的二次规划问题。 支持向量机 margin与支持向量： 设样本集为U={x1,x2,...,xl}(m维空间中的l个向量)，类别空间Y={+1,-1}。xi为输入向量，对应的类标签为yi(+1或-1)。若样本集是线性可分的，则存在超平面H：wx+b=0使得 (1)当wxi+b?1时，yi=+1 (2)当wxi+b?-1时，yi=-1 其中，w为权值向量，b为偏离值。统一(1),(2)得： yi(wxi+b) ?1 对于样本集的任一向量(点)xi，其到超平面H的距离为： 支持向量机 那么，margin的大小可按下式计算： margin=d++d- d+=min{di|i?{1,2,...,l},yi=+1}; d-=min{di|i?{1,2,...,l},yi=-1} 若存在样本点xi使得wxi+b=±1，则称此向量xi为支持向量，此时，d+=d-=1/|w|，margin=2/|w|。 分类模型：寻求最优超平面H，使得margin最大。因此分类问题转为二次凸规划问题： 支持向量机 图中H为最优分类超平面；H+1和H-1为最大间隔超平面；H+1和H-1上的点为支持向量。 x1 x2 H: w?x+b=0 H-1: w?x+b=-1 H+1: w?x+b=1 支持向量机 线性不可分：可引入核函数将线性不可分问题转换为高维空间的线性可分问题，常见核函数有： d次多项式函数 高斯径向基函数 神经网络核函数 大数据分析方法发展动态 方法分类 统计类：统计模型构建，参数估计，统计检验。 机器学习类：建模，抽样，训练，检验。 有哪些信誉好的足球投注网站类：管理目标已知时，可采用有哪些信誉好的足球投注网站策略。 算法类：面向问题迭代计算完成，如k-means，PageRank。 大数据分析方