分类算法小结课件.ppt

1、分类问题小结 By Zhou Qi基本概念u分类：根据识别对象的观测值确定其类别u样本与样本空间表示：12,Tnnx xxRxx12,ic u决策：是从样本空间S，到类别空间的 一个映射，表示为 D D:S -:S -u类别与类别空间：c个类别(类别数已知)决策准则 评价决策有多种标准，对于同一个问题，采用不同的标准会得到不同意义下“最优”的决策。Bayes决策常用的准则：最小错误率准则（最小错误率）最小风险准则（最小风险）支持向量机中常用的准则：结构风险最小分类问题的主要步骤数据获取预处理特征提取与选择分类决策分类器设计信号空间特征空间分类问题的分类线性分类：判别函数为线性函数。如贝叶斯分类

2、器，支持 向量机，感知器算法。非线性分类：判别函数为非线性函数。如分段线性判别函数。监督分类：样本数据类型已知，训练分类器对新数据进行分 类非监督分类：样本数据未知，训练分类器以求对新数据进行分类（一般首先进行聚类）半监督分类：小部分样本数据类型已知，另一部分样本类型未知，训练分类器对新数据进行分类按判别函数的类别：按已知的样本信息：主要介绍的分类算法1.贝叶斯分类算法(Bayes)2.k近邻算法(k-nearest neighbor)3.神经网络(Artificial Neural Networks)4.支持向量机(support vector machine)基于判别函数的分类器设计u判别

3、函数(discriminant function)：相应于每一类定义一个函数，得到一组判别函数：gi(x),i=1,2,cu决策区域与决策面判别函数决策规则(decision rule)()maxift )hen (jijiggxxxargmax()iijgx规则表达1规则表达2判别函数分类器设计u分类器是某种由硬件或软件组成的“机器”：计算c个判别函数gi(x)最大值选择ARGMAXg1.g2gc.x1x2xna(x)判别函数贝叶斯决策所要研究的问题：量进行分类的问题某一样本按照其特征向对）已知的条件下，如何（概率密度函数及类条件的先验概率，在各类别ii|xp)(c,21iP基本概念先验概率

4、先验概率：根据大量统计确定某类事物出现的比例。：根据大量统计确定某类事物出现的比例。如在我国大学中，一个学生是男生的先验概率为0.7，而为女生的概率是0.3，这两类概率是互相制约的，因为这两个概率的和应该为1。类条件概率密度函数类条件概率密度函数：同一类事物的各个属性都有一定的变化范围，在这：同一类事物的各个属性都有一定的变化范围，在这些些变化范围内的分布概率用一种函数形式表示，则称为类条件概率密度函数。变化范围内的分布概率用一种函数形式表示，则称为类条件概率密度函数。如x x表示某一个学生的头发的长度，w1表示男生，w2表示女生，男生类头发的概率密度表示成P(x x|w1)，女生则表示成P(

5、x x|w2)，这两者之间没有任何关系，即一般的情况下P(x x|w1)+P(x x|w2)1，可为从0,2之间的任意值。后验概率后验概率：一个具体事物属于某种类别的概率。：一个具体事物属于某种类别的概率。如一个学生用特征向量x表示，它是男性或女性的概率表示成P(男生|x)和P(女生|x)，这就是后验概率。由于一个学生只可能为两个性别之一，因此有P(男生|x)+P(女生|x)=1的约束，这一点是与类分布密度函数不同的。后验概率与先验概率也不同，后验概率涉及一个具体事物，而先验概率是泛指一类事物，因此P(男生|x)和P(男生)是两个不同的概念。后验概率P(i|x)的计算uBayes公式：假设已知

6、先验概率P(i)和观测值的类条件概率密度函数p(x|i)，i=1,2。(,)(|)()()(|)()(|)iiiijjjPPpPpPpxxxxxBayes决策常用的准则：最小错误率准则最小风险准则在限定一类错误率条件下使另一类错误率为最小的准则最小最大决策准则贝叶斯决策是所有分类算法的一个基准贝叶斯决策是所有分类算法的一个基准（BENCHMARK）基于最小错误率的Bayes决策 决策准则:选择后验概率P(w1|x)，P(w2|x)中大的w作为决策，使得在观测值x下的条件错误率最小。Bayes最小错误率决策例解u两类细胞识别问题：正常(1)和异常(2)u根据已有知识和经验，两类的先验概率为：正常

7、(1)：P(1)=0.9异常(2)：P(2)=0.1对某一样本观察值x，通过 计算或查表得到：p(x|1)=0.2，p(x|2)=0.4u如何对细胞x进行分类？p(x|1)p(x|2)x类条件概率密度函数u利用贝叶斯公式计算两类的后验概率：11121()(|)0.90.2(|)0.8180.90.20.1 0.4()(|)jjjPpPPpxxx22221()(|)0.40.1(|)0.1820.20.90.40.1()(|)jjjPpPPpxxxargmax(|)1iijPx1x决策结果Bayes最小错误率决策例解 为什么错误率最小？条件错误率：P(e|x)错误率：)|()()|(),()(x

8、ePEdxxpxePdxxePeP错误率是条件错误率的数学期望！错误率是条件错误率的数学期望！基于最小错误率的Bayes决策的错误率基于最小错误率的Bayes决策的错误率 条件错误率P(e|x)的计算:以两类问题为例，当获得观测值x后，有两种决策可能：判定 x1，或者x2。此时条件错误率为：211122(|)1(|)(|)(|)1(|)1max(|)iiPPP ePPP xxxxxxxx若决定若决定 Bayes最小错误率决策使得每个观测值下的条件错误率最小，因而保证了错误率最小。Bayes决策是一致最优决策。p(1|x)p(2|x)后验概率211122(|)1(|)(|)(|)1(|)1max

9、(|)iiPPP ePPP xxxxxxxx若决定若决定基于最小错误率的Bayes决策的错误率设t为两类的分界面，则在特征向量x是一维时，t为x轴上的一点。形成两个决策区域:R1(-，t)和R2(t，+)基于最小错误率的Bayes决策的错误率t基于最小错误率的Bayes决策的错误率t12122121212122112211()(,)(,)()(|)()(|)()(|)()(|)()()()()RRPePxRPxRPPxRPPxRPpxd xPpxd xPPePPe基于最小风险的Bayes决策 决策的风险：risk，cost做决策要考虑决策可能引起的损失。以医生根据白细胞浓度判断一个人是否患血液

10、病为例：没病(1)被判为有病(2)，还可以做进一步检查，损失不大；有病(2)被判为无病(1)，错过诊治时机，损失严重。损失的定义：(N类问题)做出决策D(x)=i，但实际上 x j，受到的损失定义为：,()|),1,2,i jijDijNx基于最小风险的Bayes决策损失矩阵：条件风险：获得观测值x后，决策D(x)对x实际所属类别的各种可能所造成的损失的平均，称为条件风险()|)(),)()|)(|)iiiiR DEPDDxxxxx()()|)()|)()R DE R DR Dpdxxxxxxx期望风险：条件风险对观测值x的数学期望基于最小风险的Bayes决策基于最小风险的Bayes决策()a

11、 rgm in()|)a rgm in(),)(|)DiiDiDRDDPxxxxx 决策准则:决策有代价，选择（条件）风险最小的决策。Bayes最小风险决策通过保证每个观测值下的条件风险最小，使得它的期望风险最小，是一致最优决策。条件风险风险系数基于最小风险的Bayes决策计算1.根据Bayes公式计算后验概率P(j|x)2.根据后验概率及给定的损失矩阵，算出每个决策的条件风险R(i|x)3.按最小的条件风险进行决策。u损失矩阵在某些特殊问题，存在简单的解析表达式。u实际问题中得到合适的损失矩阵不容易。两类问题最小风险Bayes决策11111222211222()|)(|)(|)()|)(|)

12、(|)R D xxPxPxR D xxPxPx用Bayes公式展开，最小风险Bayes决策得到：11222212211112(|)()()()f (|)()()()otherwisep xPD xip xPD xu两类细胞识别问题：正常(1)和异常(2)u根据已有知识和经验，两类的先验概率为：正常(1)：P(1)=0.9异常(2)：P(2)=0.1对某一样本观察值x，通过计算或查表得到：p(x|1)=0.2，p(x|2)=0.411=0，12=6，21=1，22=0u按最小风险决策如何对细胞x进行分类？基于最小风险的Bayes决策例解u后验概率：P(1|x)=0.818，P(2|x)=0.18

13、221112212222111(|)(|)(|)1.092(|)(|)(|)0.818jjjjjjRPPRPPxxxxxxargmin(|)2iijRx2x决策结果基于最小风险的Bayes决策例解最小风险决策的一般性u基于最小错误率的Bayes决策可作为最小风险Bayes决策的一种特殊情形。u只需要定义损失为：,1(,),1,2,1(,)0i jijijNijijij决策正确时，损失为0决策错误时，损失为1支持向量机所要研究的问题：支持向量机支持向量机(Support Vector Machine)是Vapnik等人于1995年在统计学习理论（统计学习理论（Statistical Learni

14、ng Theory）的基础上提出来的。它以在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合函数拟合等其他机器学习问题中。统计学习理论 （Statistical Learning Theory）传统统计学：传统统计学：渐进理论，即当样本数量趋向于无穷大时的极限特性。统计学习理论：统计学习理论：目前针对小样本统计估计和预测学习的最佳理论。核心问题：(1)经验风险最小化原则下统计学习一致性的条件。(2)在这些条件下关于统计学习方法推广性的界的确定。(3)在这些界的基础上建立的小样本归纳推理原则。(4)实现这些新的原则的实际方法（算法）。经验风险最小与期望风险最小经验

15、风险：经验风险：学习样本序列上的错误频率。)(),()(),()(2xdpxFxdpxP期望期望(平均平均)风险：风险：整个样本空间上的风险的期望。NiiexFNP12),(1)()(x是待分类样本，是待分类样本，是判决规则的参数向量是判决规则的参数向量。为类别值，当样本属于第一为类别值，当样本属于第一类时，类时，为为1；当样本属于第二类时，；当样本属于第二类时，为为0。F(x,)为决策规则，即当为决策规则，即当F(x,)为为1时，把样本分到第一类，而当时，把样本分到第一类，而当F(x,)为为0时，把样本分到第二类时，把样本分到第二类。为参数向量上的经验风险函数，为参数向量上的期望风险函数。使

16、错分频率最小的判决规则 并不是这个判决函数类中具有最小或者接近最小错误率 的判决规则。)()(P*t经验风险最小与期望风险最小VC维理论指示函数集的指示函数集的VC维维：使用这个指示函数集所能够打散的最大样本集的样本数目。如果存在h个样本的样本集能够被函数集打散，而不存在h+1个样本的样本集能够被该函数集打散，则函数集的VC维就是h。VC维是指示函数复杂度的描述！打散打散（shattering）：）：有h个样本的样本集能够被一个函数集中的函数按照所有可能的2h种方式分为两类，则称函数集能够把样本数为h的样本集打散。VC维理论 对于任意一个d维线性分类器（超平面），其VC维 h=d+1。当d=2

17、，线性分类器的vc维是3无论三个样本怎么组合，总存在一条直线可以将其分为两类。VC维理论 对于任意一个d维线性分类器（超平面），其VC维 h=d+1。当d=2，线性分类器的vc维是3无论三个样本怎么组合，总存在一条直线可以将其分为两类。而当有四个样本时，在如下情况下无法使用一条直线将它们分成两类。结构风险最小置信风险：置信风险：两类分类问题，对指示函数集中的所有函数，经验风险和实际风险之间至少以概率满足如下关系：21)()(empRRnhnhRRemp4ln)12(ln)()(经过计算:W为参数空间，n为样本个数，h为指示函数的VC维1结构风险最小置信风险：置信风险：两类分类问题，对指示函数集

18、中的所有函数，经验风险和实际风险之间至少以概率满足如下关系：1)()()(nhRRemp其中 为置信风险，它的上界与随着h的增大而单调递增，随着n的增大而单调递减。在 和n一定的情况下，我们应该尽量减小指示函数的VC维，从而使风险上界最小。)(nh)(empR最优分平面（Optimal Hyperplane）H为把两类样本无错误分开的的分类线，H1和H2分别为过各类样本中离分类线最近的点且平行与分类线的直线，H1和H2之间的距离叫做两类的分类间隔（两类的分类间隔（margin）实心点和空心点分别代表两类的训练样本，1.两类样本无误的分开 经验风险最小（此时为0）2.两类间的分类间隔最大最优分类

19、线最优分类线是样本集合到分类是样本集合到分类面的间隔，面的间隔，R=max|xi|i=1,.,n，即，即R是所有样本中向量长度最长的值（代表样本的是所有样本中向量长度最长的值（代表样本的分布有多么广分布有多么广）最优分平面（Optimal Hyperplane）1,1,1),(yRxniyxdiibxwxg)(线性可分样本为是类别标签d维空间中线性判别函数的一般形式为 我们的目标是寻找其最优分平面。寻找其最优分平面。问题描述：问题描述：对判别函数进行归一化，使得离分类面最近的样本的 ，这样分类间隔就等于2/|w|，因此使间隔最大等价于最小化|w|（或|w|2）分类线对所有样本都正确分类，那么应

20、该满足限制条件:1)(xgnibxwyii,2,1,01)(支持向量机 niiiibxwywwbwL11)()(21),(2,21minwbwnibxwyii,2,1,01)(subject to 构造构造Lagrange函数：函数：0i其中：其中：对偶形式：对偶形式：max0ininjnjjjijijixxyy111)(21subject to liiiy10凸规划问题目标函数目标函数：间隔支持向量机 niiiixyw1*目标函数：目标函数：max0ininjnjjjijijixxyy111)(21subject to liiiy10判别函数：判别函数：若若为最优解为最优解支持向量的支持向量

21、的权系数向量权系数向量)(sgn)sgn()(1*niiiibxxybxwxf支持向量机 线性不可分？1.转换到高维空间2.引入松弛变量支持向量机 横轴上a和b间红色部分的所有点为正类，两边黑色部分的点为负类 无法用一条直线分无法用一条直线分开（二维超平面）开（二维超平面）试试二次曲线？（三维超平面）试试二次曲线？（三维超平面）可分？Or not 可分？支持向量机 横轴上a和b间红色部分的所有点为正类，两边黑色部分的点为负类 非线性？g(x)=f(y)=ay 一般来说，对于任一般来说，对于任何高次判别函数，都可何高次判别函数，都可以通过适当的变换转换以通过适当的变换转换为另一个空间中的线性为另

22、一个空间中的线性判别函数来处理判别函数来处理！核函数 目标函数：目标函数：max0ininjnjjjijijixxyy111)(21subject to liiiy10判别函数：判别函数：)(sgn)sgn()(1*niiiibxxybxwxf求解过程中只涉及到训练样本之间的内积运算)(jixx 分类判决函数中只包含待分类样本和支持向量的内积运算)(ixx 只关心高维空间里内积的值！只关心高维空间里内积的值！引入核函数！引入核函数！核函数 使用函数,将所有样本点(x1,x2 xn)映射到高为空间，则新的样本集为:),().(),(11nnyxyx)()(),(2121xxxxK核函数：)()(

23、),(2121xxxxK作用：接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。0)(xdxx)(20)()(),(xdxdxxxxKMercer条件：条件：对于任意的对称函数K(x,x)，它是某个特征空间中的内积运算的充分必要条件时，对于任意的 ，且有常见的核函数 1.多项式内积2.核函数型内积 3.S型函数内积 qiixxxxK 1)(),(exp),(22iixxxxK)(tanh),(cxxvxxKiiq阶多项式分类器 径向基函数分类器 两层感知器神经网络 松弛变量 转换到高维空间后仍线性不可分？噪声？松弛变量 nibxwyii,2,1,1)(nibxwyii

24、i,2,1,1)(引入松弛变量松弛变量)()(21),(min1niiCwwwnibxwyiii,2,1,01)(subject to 引入松弛变量后的目标函数：引入松弛变量后的目标函数：2,21minwbwnibxwyii,2,1,01)(subject to 原目标函数原目标函数：C为惩罚系数，为松弛因子 i硬间隔软间隔松弛变量)()(21),(min1niiCwwwnibxwyiii,2,1,01)(subject to 引入松弛变量后的目标函数：引入松弛变量后的目标函数：C为惩罚系数，为松弛因子 i1.只有“离群点”才有一个松弛变量与其对应。2.松弛变量的值实际上标示出了对应的点到底“离群”有多远。3.惩罚因子C决定了你有多重视离群点带来的损失。当所有离群点的松弛变量的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这就退化成了硬间隔问题。4.惩罚因子C不是一个变量，而是定值。Thank you!