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

PatternRecognitionMethodsUsingSupervisedLearning基于监督学习的模式识别方法模式与模式识别模式：模式是对某些感兴趣的客体的定量的或结构的描述，模式类是具有某些共同特性的模式的集合。在模式识别学科中，常常不区分“模式”和“模式类”模式识别：把对象根据其特征划分到若干类别中适当的一类•模式指的并不是事物本身，而是对事物的一种描述，也就是我们从事物获得的信息•模式识别的过程就是建立分类器的过程•一些模式识别的例子：语音识别，字符与文字识别，人脸识别等等模式识别的方法模式识别方法主要分为基于知识的方法和基于数据的方法基于知识的方法：根据人们已知的关于研究对象的知识，整理出若干描述特征与类别关系的准则，对未知样本通过这些知识推理决策其类别。主要利用先验的知识基于数据的方法：不利用先验知识，完全依靠训练样本来建立样本与模式之间的联系，属于一种机器学习的分类方法。基于数据的方法是模式识别最主要的方法对象GSLMxyy’基于数据的模式识别方法基于数据的模式识别方法可以分为两种：监督模式识别和非监督模式识别监督模式识别：基于一定数量的类别已知的训练样本建立分类器，也是模式识别的主要方法非监督模式识别：事先不知道要划分什么类别，更没有类别已知的样本用作训练，主要进行聚类分析监督模式识别方法监督模式识别方法贝叶斯决策法判别函数法线性判别法非线性判别法近邻法决策树法贝叶斯决策法核心思想：根据对象归于某个模式的概率来进行决策分类问题：已知对象的特征x，以及n个类别ω1~ωn，求对象属于哪个类别贝叶斯公式：,1,2...,niiipxPPxipxP(ωi)：先验概率p(x|ωi)：类条件概率密度p(x)：总体概率密度P(ωi|x)：后验概率贝叶斯决策法最小错误率决策法样本的错误率：决策的错误率：样本错误概率的期望|dPePexpxx||,ijijpexPxx最小错误率决策法即让P(e)达到最小。由于p(x)是固定的，所以等价于对于所有x都让P(e|x)取最小。由样本x的错误率计算公式可知，最小错误率决策等价于如下一种决策：1,...,n|max|ijjPxPx若则ix贝叶斯决策法最小错误率决策法根据贝叶斯公式：,1,2...,niiipxPPxipx即根据𝑝𝑥|𝜔𝑖𝑃𝜔𝑖的最大值来进行分类决策关键点：类条件概率密度𝑝𝑥|𝜔𝑖的计算方法？重点讨论离散概率模型下的概率估计方法贝叶斯决策法朴素贝叶斯分类器朴素贝叶斯分类器（NaiveBayesClassifier）：假定特征各分量是相互独立的，因此类条件概率可写为121|,,...,||mmjjPxPxxxPx即根据的最大值来进行分类决策1|mijijPPx1argmax|mijijPPx贝叶斯决策法朴素贝叶斯分类器•步骤一，通过训练样本估计先验概率P(“3”)•步骤二，通过训练样本估计P(1,3=1|”3”),P(1,4=1|”3”),…•步骤三，通过独立假设计算类条件概率P(样本|“3”)=P(1,3=1|”3”)*P(1,4=1|”3”)…假定要计算该样本属于“3”的概率•步骤四，P(“3”|样本)~P(“3”)*P(样本|“3”)贝叶斯决策法朴素贝叶斯分类器•P(1,3=1|”3”)可以采用最大似然估计：•若采用最大似然估计，朴素贝叶斯分类器对于稀疏数据非常敏感•设想若训练样本中所有“3”在1,3处都没有值，那么计算得到的后验概率等于零！改用其他估计方法来进行平滑处理！1,31,31,31|33cPc贝叶斯决策法拉普拉斯估计•假如投一次硬币，正面朝上，如何估计正面朝上的概率？•假如投100次硬币，有80次正面朝上，如何估计正面朝上的概率？•假如投100万次硬币，有80万次正面朝上，如何估计正面朝上的概率？启发：1.在进行估计之前，我们有一些先验的期望2.若样本数量很少，我们应该更依赖先验期望3.若样本数量很多，我们应该更依赖数据,,|LAPkcxykPxycykX|X|为x的取值个数，k为待定参数贝叶斯决策法NBC的优缺点•优点：算法复杂度低，不要求很大的训练样本数量•缺点：要求特征分量满足条件独立条件，但很多时候这种条件不能满足•改进：树增广朴素贝叶斯分类器（TAN）；贝叶斯增广朴素贝叶斯分类器（BAN）1argmax|mijijPPx贝叶斯决策法依赖于样本的概率密度模型，当概率密度模型难以估计时很难建立分类器。判别函数法核心思想：根据训练样本确定一个判别函数g(x)，根据g(x)的值来对未知样本进行分类线性分类器：判别函数的形式是线性的两类情况：多类情况：非线性分类器：判别函数的形式是非线性的0Tgxwx0Tiiigxwx核心问题是如何根据训练样本确定权向量和阈值向量线性分类器Fisher线性判别•核心思想：使投影后两类相隔尽量远，而同时每一类内部的样本又尽可能聚集。通过最优化方法求解该最优投影方向•Fisher线性判别法只能得到最优投影方向即权向量，阈值向量需要进一步求解线性分类器感知器算法回顾线性判别函数把𝑥=𝑥1,𝑥2,⋯,𝑥𝑑𝑇进行增广𝑦=1,𝑥1,𝑥2,⋯,𝑥𝑑𝑇把权向量𝑤=𝜔1,𝜔2,⋯,𝜔𝑑𝑇进行增广𝛼=𝜔0,𝜔1,𝜔2,⋯,𝜔𝑑𝑇则线性判别函数可以改写为判别决策可以改写为若𝑔𝑦0则𝑦∈𝜔1；若𝑔𝑦0则𝑦∈𝜔20Tgxwx0,1,,TTigyyziN线性分类器感知器算法线性可分：对于一组样本𝑦1,…𝑦𝑁，若存在𝛼使得对于任一样本𝑦𝑖若𝑦𝑖∈𝜔1则𝑔𝑦0，若𝑦𝑖∈𝜔2则𝑔𝑦0，那么称样本𝑦1,…𝑦𝑁是线性可分的定义新变量𝑧𝑖，当𝑦𝑖∈𝜔1时𝑧𝑖=𝑦𝑖，当𝑦𝑖∈𝜔2时𝑧𝑖=−𝑦𝑖，那么线性可分条件变成存在𝛼使得0,1,,TiziN可以使用迭代方法求解线性分类器感知器算法感知器算法：用最速下降法（迭代修正法）求解满足条件的增广权向量𝛼∗•步骤一，选取权向量初值𝛼=𝛼0•步骤二，依次从训练样本中选取𝑧𝑖，进行如下操作若𝛼𝑇𝑧𝑖0，则𝛼不变，选择下个样本；若𝛼𝑇𝑧𝑖0，则𝛼=𝛼+𝑐𝑧𝑖•重复步骤二直至收敛理论证明，若样本集线性可分，经过有限次迭代修正后一定会收敛到解向量𝛼∗感知器算法只能解决线性可分问题线性分类器最优分类超平面与线性SVM•支持平面•支持向量•最优分类超平面•线性支持向量机（SVM）线性不可分时引入惩罚函数进行求解非线性分类器有时候最优分类面并非线性平面，此时可以使用非线性判别函数来进行分类二次判别函数分段线性函数非线性分类器核心思想：将非线性判别函数转换为广义线性判别函数，然后在线性空间里求解最优分类平面支持向量机21112222xxxx核函数核函数目前没有一个通用的选择方法其他分类方法核心思想：近朱者赤，近墨者黑最近邻法和K-近邻法•最近邻算法：以离未知样本最近的样本作为唯一判决依据•K-近邻算法（KNN）：以离未知样本最近的k个样本作为判决依据核心问题：k的选择以及计算速度的优化其他分类方法非数值特征：颜色，性别，年龄等没有数值意义的变量，也可以称为属性决策树算法决策树算法：利用一定训练样本，从数据中“学习”出决策规则其他分类方法一个典型的决策树算法为ID3方法，其基础是香农信息论中的信息熵信息熵：信息论告诉我们，如果一个事件有k种可能的结果，每种结果对应的概率为Pi，则对事件结果进行观察的信息熵为决策树算法121222221loglogloglogkkkiiiIPPPPPPPP其他分类方法决策树算法问题：根据用户的——年龄（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