基于监督学习的模式识别方法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Pattern Recognition Methods Using Supervised Learning,基于监督学习的模式识别方法,模式与模式识别,模式,：模式是对某些感兴趣的客体的定量的或结构的,描述,，模式类是具有某些共同特性的模式的,集合,。在模式识别学科中，常常不区分,“,模式,”,和,“,模式类,”,模式识别,：把对象根据其特征划分到若干类别中适当的一类,模式指的并不是事物本身，而是对事物的一种描述，也就是我们从事物获得的,信息,模式识别的过程就是建立分类器的过程,一些模式识别的例子：语音识别，字符与文字识别，人脸识别等等,模式识别的方法,模式识别方法主要分为基于,知识,的方法和基于,数据,的方法,基于知识的方法,：根据人们已知的关于研究对象的知识，整理出若干描述特征与类别关系的准则，对未知样本通过这些知识推理决策其类别。主要利用先验的知识,基于数据的方法,：不利用先验知识，完全依靠训练样本来建立样本与模式之间的联系，属于一种机器学习的分类方法。基于数据的方法是模式识别最主要的方法,对象,G,S,LM,x,y,y,基于数据的模式识别方法,基于数据的模式识别方法可以分为两种：监督模式识别和非监督模式识别,监督模式识别,：基于一定数量的类别已知的训练样本建立分类器，也是模式识别的主要方法,非监督模式识别,：事先不知道要划分什么类别，更没有类别已知的样本用作训练，主要进行聚类分析,监督模式识别方法,监督模式识别方法,贝叶斯决策法,判别函数法,线性判别法,非线性判别法,近邻法,决策树法,贝叶斯决策法,核心思想,：根据对象归于某个模式的概率来进行决策分类,问题：已知对象的特征,x,，以及,n,个类别,1,n,，求对象属于哪个类别,贝叶斯公式：,P(,i,),：先验概率,p(x|,i,),：类条件概率密度,p(x),：总体概率密度,P(,i,|x),：,后验概率,贝叶斯决策法,最小错误率决策法,样本的错误率,：,决策的错误率,：样本错误概率的期望,最小错误率决策法即让,P(e),达到最小。由于,p(x),是固定的，所以等价于对于所有,x,都让,P(e|x),取最小。由样本,x,的错误率计算公式可知，最小错误率决策等价于如下一种决策：,若,则,贝叶斯决策法,最小错误率决策法,根据贝叶斯公式：,重点讨论离散概率模型下的概率估计方法,贝叶斯决策法,朴素贝叶斯分类器,朴素贝叶斯分类器（,Naive Bayes Classifier,）,：假定特征各分量是相互独立的，因此类条件概率可写为,即根据 的,最大值来进行分类决策,贝叶斯决策法,朴素贝叶斯分类器,步骤,一，通过训练样本估计先验概率,P(,“,3,”,),步骤二，通过训练样本估计,P(=1|,”,3,”,),P,(=,1|,”,3,”,),步骤三，通过独立假设计算类条件概率,P(,样本,|,“,3,”,),=P(=,1|,”,3,”,)*,P(=,1|,”,3,”,),假定要计算该,样本,属于,“,3,”,的概率,步骤四，,P(,“,3,”,|,样本,)P,(,“,3,”,),*,P(,样本,|,“,3,”,),贝叶斯决策法,朴素贝叶斯分类器,P(=1|,”,3,”,),可以采用最大似然估计：,若采用最大似然估计，朴素贝叶斯分类器对于稀疏数据非常敏感,设想若训练样本中所有,“,3,”,在,处都没有值，那么计算得到的后验概率等于零！,改用其他估计方法来进行平滑处理！,贝叶斯决策法,拉普拉斯估计,假如投一次硬币，正面朝上，如何估计正面朝上的概率？,假如投,100,次硬币，有,80,次正面朝上，如何估计正面朝上的概率？,假如投,100,万次硬币，有,80,万次正面朝上，如何估计正面朝上的概率？,启发：,1.,在进行估计之前，我们有一些先验的期望,2.,若样本数量很少，我们应该更依赖先验期望,3.,若样本数量很多，我们应该更依赖数据,|X|,为,x,的取值个数，,k,为待定参数,贝叶斯决策法,NBC,的优缺点,优点：算法复杂度低，不要求很大的训练样本数量,缺点：要求特征分量满足条件独立条件，但很多时候这种条件不能满足,改进：树增广朴素贝叶斯分类器（,TAN,）；贝叶斯增广朴素贝叶斯分类器（,BAN,）,贝叶斯决策法依赖于样本的概率密度模型，当概率密度模型难以估计时很难建立分类器。,判别函数法,核心思想,：根据训练样本确定一个判别函数,g(x),，根据,g(x),的值来对未知样本进行分类,线性分类器,：判别函数的形式是线性的,两类情况：,多类情况：,非线性分类器,：判别函数的形式是非线性的,核心问题是如何根据训练样本确定权向量和阈值向量,线性分类器,Fisher,线性判别,核心,思想,：使投影后两类相隔尽量远，而同时每一类内部的样本又尽可能聚集。通过最优化方法求解,该最优投影方向,Fisher,线性判别法只能得到最优投影方向即权向量，,阈值向量需要进一步求解,线性分类器,感知器算法,线性分类器,感知器算法,可以使用迭代方法求解,线性分类器,感知器算法,感知器算法只能解决线性可分问题,线性分类器,最优分类超平面与线性,SVM,支持平面,支持向量,最,优分类超平面,线性支持向量机（,SVM,）,线性不可分时引入惩罚函数进行求解,非线性分类器,有时候最优分类面并非线性,平面，此时可以使用非线性判别函数来进行分类,二次判别函数,分段线性函数,非线性分类器,核心思想,：将非线性判别函数转换为广义线性判别函数，然后在线性空间里求解最优分类平面,支持向量机,核函数,核函数目前没有一个通用的选择方法,其他分类方法,核心思想,：近朱者赤，近墨者黑,最近邻法和,K-,近邻法,最近邻算法,：以离未知样本最近的样本作为唯一判决依据,K-,近邻算法（,KNN,）,：以离未知样本最近的,k,个样本作为判决依据,核心问题：,k,的选择以及计算速度的优化,其他分类方法,非数值特征,：颜色，性别，年龄等没有数值意义的变量，也可以称为属性,决策树算法,决策树算法：,利用一定训练样本，从数据中,“,学习,”,出决策规则,其他分类方法,一个典型的决策树算法为,ID3,方法，其基础是香农信息论中的信息熵,信息熵,：信息论告诉我们，如果一个事件有,k,种可能的结果，每种结果对应的概率为,Pi,，则对事件结果进行观察的信息熵为,决策树算法,其他分类方法,决策树算法,问题：,根据用户的,年龄,（,youth/middleaged/senior,）,收入（,high/medium/low,）,是否学生（,yes/no,）,信用评级（,excellent/fair,）,判断,其是否会买电脑（,yes/no,）,利用所提供的,14,个训练样本以及,ID3,算法建立决策树,其他分类方法,决策树算法,第一步：,计算总的信息熵,是否买电脑,5,次,no,，,9,次,yes,第二步,：,计算各属性的信息熵，以年龄为例,youth,共出现,5,次，,3,次,no2,次,yes,类似得到,middleaged,和,senior,的信息熵分别为,0,和,0.971,。因此年龄属性的信息熵为,其他属性的信息熵计算方法类似,其他分类方法,决策树算法,第三步：,求出各属性的信息熵减少量（或信息增益），使用信息增益最大的属性作为根节点,第四步,：,使用递归的方法扩展树的节点，递归终止条件为后继节点只包含一类样本,决策树算法存在过拟合的问题，需要通过剪枝的方法来控制决策树的规模,Thanks,