《模式识别原理、应用及实现》 课件 第4章非参数判别分类方法

4.1线性判别函数4.1.1判别函数若分属于ω1，ω2的两类模式可用一方程d(X)=0来划分，那么称d(X)为判别函数，或称判决函数、决策函数。直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程d(X)=0来划分。为坐标变量，为方程参数。式中：1．判别函数的定义若，则若，则类；若，则类；

或拒绝将某一未知模式

X

代入：维数=3时：判别边界为一平面。维数>3时：判别边界为一超平面。4.1.1判别函数d(X)表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。2．判别函数正负值的确定图3.3判别函数正负的确定4.1.1判别函数1）判决函数d(X)的几何性质。它可以是线性的或非线性的函数，维数在特征提取时已经确定。如：已知三维线性分类——判决函数的性质就确定了判决函数的形式：3.确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。4.1.1判别函数1、线性判别函数的一般形式将二维模式推广到n维，线性判别函数的一般形式为：(3-2)式中：：权向量，即参数向量。式中：为增广权向量，为增广模式向量。4.1.2线性判别函数2、线性判别函数的性质（1）

两类情况d(X)=0：不可判别情况，可以

对M个线性可分模式类，ω1，ω2，…ωM，有三种划分方式：（2）

多类情况两分法两分法两分法特例4.1.2线性判别函数两分法多类情况1：

用线性判别函数将属于ωi类的模式与其余不属于ωi类的模式分开。将某个待分类模式X分别代入M个类的d

(X)中，若只有di(X)>0，其他d(X)均<0，则判为ωi类。识别分类时：4.1.2线性判别函数对某一模式区，di(X)>0的条件超过一个，或全部的di(X)<0，分类失效。相当于不确定区(indefiniteregion，IR)。

全部＜０不属任何类

IR，可能

属于1w或3w

1w2w3w0)(2=Xd0)(3=Xd++IR，可能

属于3w或2w

+---0)(1=Xd0,,0312<>ddd0,,0321<>ddd0,0,321<>dddIR，可能属于1w或2w

0,,0213<>ddd2x1x+4.1.2线性判别函数两分法多类情况2：

一个判别界面只能分开两个类别，不能把其余所有的类别都分开。判决函数为：。这里。在M类模式中，与i有关的M-1个判决函数全为正时，X∈ωi。其中若有一个为负，则为IR区。则类，而在判别类模式时不起作用。如：对一个三类问题，如果，识别分类时：4.1.2线性判别函数1w2w2x1x--003231>>dd001312>>dd002321>>dd3w+++-

d23(X)=0d12(X)=0d13(X)=0IR000231312ïþïýü<><ddd4.1.2线性判别函数当ωi

/ωj两分法中的判别函数dij(X)，可以分解为时，那么di(X)>dj(X)就相当于多类情况2中的dij(X)>0。两分法特例多类情况3：因此对具有判别函数的M类情况，判别函数性质为：或：

4.1.2线性判别函数2313dddd>>01w2w2x1x()0)(21=-XdXd+++---()0)(31=-XdXd()0)(32=-XdXd3212dddd>>3121dddd>>3w4.1.2线性判别函数4.2广义线性判别函数武汉理工大学目的：对非线性边界：通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。

设一训练用模式集，{X}在模式空间X中线性不可分，非线性判别函数形式如下：(3-9)fi(X)取什么形式及d(X)取多少项，取决于非线性边界的复杂程度。1．非线性多项式函数非线性判别函数的形式之一是非线性多项式函数。式中是模式X

的单值实函数，。(3-10)上式是线性的。讨论线性判别函数并不会失去一般性的意义。(3-11)

随着小样本学习理论和支持向量机的迅速发展，广义线性判别函数的“维数灾难”问题在一定程度上找到了解决的办法。非线性变换可能非常复杂。维数大大增加：维数灾难。广义形式的模式向量定义为：这里X*空间的维数k高于X空间的维数n，(3-9)式可写为问题：例

假设X为二维模式向量，fi(X)选用二次多项式函数，原判别函数为定义：d(X)线性化为：即：广义线性判别函数：4.3线性判别函数的几何性质武汉理工大学模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。模式向量的表示：点、有向线段。2.讨论式中，，。设判别函数：超平面：线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式空间分成不同的决策区域。1.概念4.4.1模式空间与超平面(1)模式向量X1和X2在超平面上——W0是超平面的法向量，方向由超平面的负侧指向正侧。设超平面的单位法线向量为U：4.4.1模式空间与超平面(2)X不在超平面上

将X向超平面投影得向量Xp，构造向量R：r：X到超平面的垂直距离。有(r)——判别函数d(X)正比于点X到超平面的代数距离。4.4.1模式空间与超平面4.4.2权空间与权向量解1.概念权空间：以的权系数为坐标变量的（n+1）维欧氏空间增广权向量的表示：点、有向线段。2.线性分类判别函数形式已定，只需确定权向量。类：X11，X12，…，X1p

类：X21，X22，…，X2q

设增广样本向量：使d(X)将ω1和ω2分开，需满足给ω2的q个增广模式乘以（－1），统一为,其中——样本的规范化过程。对每个已知的X，d(X)=0在权空间确定一个超平面，共(p+q)个。

在权空间中寻找向量W使判别函数d(X)能把ω1类和ω2类分开，就是寻找一个权向量，其在（p+q）个超平面的正侧的交迭区域里(W的解区)。X：规范化增广样本向量。4.4.2权空间与权向量解例：二维权空间，超平面的方程为：超平面：过原点的直线；阴影部分：解区。4.4.2权空间与权向量解二分法（Dichotomies）：用判别函数d(X)将给定的N个模式分成两类的方法。是一种基本的分类方法。判别函数的不同分类能力可以通过二分法总数衡量。

若不限制判别函数的形式，N个n维模式用判别函数分成两类的二分法总数为2N。4.4.3二分法

若限定用线性判别函数，并且样本在模式空间是良好分布的，即在n维模式空间中没有(n+1)个模式位于(n－1)维子空间中，可以证明，N个n维模式用线性判别函数分成两类的方法总数，即线性二分法总数为或线性二分法概率：

只要模式的个数N小于或等于增广模式的维数（n+1），模式类总是线性可分的，4.4.3二分法例：4个良好分布的2维模式，若用线性判别函数分类线性二分法总数：线性二分法概率：图3.14线性二分法的概率4.4.3二分法将λ=2时的N值定义为阈值N0，称为二分法能力，即通过N0，可以对任意N个样本的线性可分性进行粗略估计。4.4.3二分法4.4感知器算法武汉理工大学基本思想只要求出权向量，分类器的设计即告完成。本节开始介绍如何通过各种算法，利用已知类别的模式样本训练出权向量W。

对线性判别函数，当模式维数已知时，判别函数的形式实际上已经确定，如：三维时感知器：对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（reward-punishmentconcept）”得到广泛应用。感知器算法两类线性可分的模式类：，设其中，，应具有性质对样本进行规范化处理，即ω2类样本全部乘以(－1)，则有：

感知器算法通过对已知类别的训练样本集的学习，寻找一个满足上式的权向量。感知器算法步骤：（1）选择N个分属于ω1和

ω2类的模式样本构成训练样本集

{X1,…,XN}

构成增广向量形式，并进行规范化处理。任取权向量初始

值W(1)，开始迭代。迭代次数k=1。（2）用全部训练样本进行一轮迭代，计算WT(k)Xi的值，并修正权向量。分两种情况，更新权向量的值：c：正的校正增量。分类器对第i个模式做了错误分类，①感知器算法统一写为：分类正确，权向量不变：②（3）分析分类结果：只要有一个错误分类，回到（2），直至对所有样本正确分类。分类正确时，对权向量“赏”——这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”——对其修改，向正确的方向转换。感知器算法是一种赏罚过程：感知器算法3.收敛性收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。可以证明感知器算法是收敛的。收敛条件：模式类别线性可分。例3.8已知两类训练样本解：所有样本写成增广向量形式；进行规范化处理，属于ω2的样本乘以(－1)。用感知器算法求出将模式分为两类的权向量解和判别函数。感知器算法任取W(1)=0，取c=1，迭代过程为：第一轮：

有两个WT(k)Xi≤0的情况（错判），进行第二轮迭代。感知器算法第二轮：第三轮：第四轮：感知器算法该轮迭代的分类结果全部正确，故解向量相应的判别函数为：

当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。判别界面d(X)=0如图示。感知器算法4.5梯度法武汉理工大学

设函数f(Y)是向量

的函数，则f(Y)的梯度定义为：梯度的方向是函数f(Y)在Y点增长最快的方向，梯度的模是f(Y)在增长最快的方向上的增长率(增长率最大值)。1.梯度概念

梯度向量的最重要性质之一：指出函数f在其自变量增加时，增长最快的方向。显然：负梯度指出了最陡下降方向。——梯度算法的依据。即：2.梯度算法

设两个线性可分的模式类ω1和ω2的样本共N个，ω2类样本乘(-1)。将两类样本分开的判决函数d(X)应满足：

梯度算法的目的仍然是求一个满足上述条件的权向量，主导思想是将联立不等式求解W的问题，转换成求准则函数极小值的问题。——N个不等式

准则函数的选取原则：具有唯一的最小值，并且这个最小值发生在W

TXi>0时。

用负梯度向量的值对权向量W进行修正，实现使准则函数达到极小值的目的。基本思路：

定义一个对错误分类敏感的准则函数J(W,X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：其中c是正的比例因子。

梯度法求解步骤：（1）将样本写成规范化增广向量形式，选择准则函数，设置初始权向量W(1)，括号内为迭代次数k=1。2.梯度算法2.梯度算法迭代次数k加1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。（3）在一轮迭代中，如果有一个样本使，回到(2)进行下一轮迭代。否则，W不再变化，算法收敛。（2）依次输入训练样本X。设第k次迭代时输入样本为Xi，此时已有权向量W(k)，求：权向量修正为：例3.10

选择准则函数，，简单地考虑X为一维增广模式的情况X=1，此时W=w，两者均为标量，错误分类时：，对权向量校正。正确分类时：，对权向量不做修正。3.梯度算法举例

随着权向量W向理想值接近，准则函数关于W的导数()越来越趋近于零，这意味着准则函数J越来越接近最小值。当最终

时，J达到最小值，此时W不再改变，算法收敛。——将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。c)梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W,X)的选择，J(W,X)的形式不同，得到的具体算法不同。a)b)c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。4.梯度算法说明4.6最小平方误差算法武汉理工大学1.基本思想

上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a)迭代过程本身收敛缓慢b)模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：

两类分类问题的解相当于求一组线性不等式的解。如果给出分属于，两个模式类的训练样本集，应满足：其中，Xi是规范化增广样本向量，。上式分开写为：2.分类器的不等式方程写成矩阵形式为：令N×(n+1)的长方矩阵为X，则

变为：2.分类器的不等式方程式中：0为零向量感知器算法是通过解不等式组，求出W。2.分类器的不等式方程3.LMSE算法原理的求解。式中：∴

两式等价。为各分量均为正值的矢量。LMSE算法把对满足XW>0

的求解，改为满足①在方程组中当行数>>列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模式的维数n，因此方程的个数(行数)>>模式向量的维数(列数)，是矛盾方程组，只能求近似解W*，即说明：②LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B

可得到近似解（最小二乘近似解）。③LMSE算法的思路：转化为转化为准则函数定义为：3.LMSE算法原理考察向量(XW－B)有：可以看出：①当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。②因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。XW=B

的近似解也称“最优近似解”：——使方程组两边所有误差之和最小（即最优）的解。准则函数：3.LMSE算法原理4.推导LMSE算法递推公式与问题相关的两个梯度：(3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。(1)求W的递推关系X为N×(n+1)长方阵，X#为(n+1)×N长方阵。称为X的伪逆，(3-45)(2)求B(k+1)的迭代式(3-46)代入，得

令，定义(3-49)(3-50)利用梯度算法公式有：4.推导LMSE算法递推公式(3)求W(k+1)的迭代式(3-49)(3-50)4.推导LMSE算法递推公式……W(k+1)、B(k+1)互相独立，先后次序无关。总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数。4.推导LMSE算法递推公式5.模式类别可分性判别③

如果e(k)<0（所有分量为负数或零，但不全为零），停止迭代，无解。此时若继续迭代，数据不再发生变化。

可以证明：当模式类线性可分，且校正系数c满足

时，该算法收敛，可求得解W。

理论上不能证明该算法到底需要迭代多少步才能达到收敛，通常在每次迭代计算后检查一下XW(k)和误差向量e(k)，从而可以判断是否收敛。①

如果e(k)=0

，表明XW(k)=B(k)>0，有解。②

如果e(k)>0

，表明XW(k)>B(k)>0，隐含有解。继续迭代，可使e(k)→0

。4.7支持向量机（SVM）SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag,NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication4.7.1

支持向量机的提出代表+1代表-1如何正确分开?

4.7.1

支持向量机的提出+1-1那一条直线是最好的？

+1-1间隔（margin）：到超平面最近的样本与此超平面之间的距离。13

4.7.1

支持向量机的提出+1-1支持向量(SupportVectors)：是那些距离超平面最近的点。线性支持向量机具有最大间隔的线性分类器叫做最大间隔线性分类器。其就是称为线性支持向量机，（LSVM）

4.7.1

支持向量机的提出“PredictClass=+1”“PredictClass=-1”wx+b=1wx+b=0wx+b=-1M=间隔的宽度x-x+由线性判别函数的几何性质：支持向量到决策面的距离：4.7.2

支持向量机的推导4.7.2

支持向量机的推导“PredictClass=+1”“PredictClass=-1”wx+b=1wx+b=0wx+b=-1M=间隔的宽度x-

x+

4.7.2支持向量机的推导

argminsubjectto典型的有约束二次优化问题如何求解？4.7.2支持向量机的推导代回目标函数拉格朗日乘子法

4.7.2支持向量机的推导SVM的对偶形式

4.7.2支持向量机的推导4.7支持向量机（SVM）4.7.3

软间隔（松弛）4.7.3

软间隔（松弛）𝐶>0:正则化参数𝜉𝑖——代价，我们要最小化代价函数（总代价）——正则项，对分类器进行限制，使复杂度不至于太高引入惩罚项，目标函数改写为：4.7.3

软间隔（松弛）对偶形式仅依赖于内积SVM的对偶性4.7.4非线性SVMs4.7.4非线性SVMs最后得到决策函数可得在求得最优化问题的解4.7.4非线性SVMs4.7.4非线性SVMs目前研究最多的核函数主要有三类：多项式内核径向基函数内核RBFSigmoind内核4.7.4非线性SVMs4.7.5结构风险最小化结构风险最小化的思想认为，真实风险​应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险代表了在多大程度上可以信任分类器在未知文本上分类的结果。结构风险中包含的经验风险和置信风险，可以理解成训练误差和模型复杂度的问题。经验风险是模型在已有样本上的误差，置信风险中利用VC维对模型的复杂度进行度量，并希望能够尽量降低复杂度，增加模型的泛化能力。模式识别85/justinruan/Learning-ML学以致用，知行合一（实践篇）4.9感知机算法算法2.1(感知机学习算法的原始形式)输入：训练数据集学习率输出：；感知机模型（1）选取初值（2）在训练集中随机选取数据（3）如果，更新（4）转至（2），直到训练集中没有误分的点86求偏导感知器与鸢尾花87鸢尾花数据鸢尾花数据集共收集了三类鸢尾花，即Setosa山鸢尾、Versicolour变色鸢尾和Virginica维吉尼亚鸢尾，每一类鸢尾花收集了50条样本记录，共计150条。有4个属性：萼片长度、萼片宽度、花瓣长度和花瓣宽度。88属性最大值最小值均值方差萼长7.94.35.840.83萼宽4.42.03.050.43瓣长6.91.03.761.76瓣宽2.50.11.200.76感知器的Numpy实现89构造数据集选择前两种鸢尾花的第二个及第三个特征进行实验，只取两个特征：（花萼宽度花瓣长度）90

判别函数91找到一个违例：测试函数进行训练和测试：92Weight=[-0.0440.049],b=-0.01样本空间可视化画出分割的边界93感知器与SK-Learn94感知器与MNISTMNIST是一个手写数字图像的数据集，每幅图像都由一个整数标记。MNIST数据库有60,000个用于训练的28*28的灰度手写数字图片，10,000个测试图片95#从外部的npz文件中加载数据trainset:(60000,785)#第一个维度是标注testset:(10000,785)#从第二个维度开始是图像数据X_train=(60000,784)y_train=(60000,)X_train=(10000,784)y_train=(10000,)感知器与MNIST96感知器与MNISTConfusionmatrix97权重系数权重矩阵：(10,784)分10类，各对应784个系数98模式识别99/justinruan/Learning-ML学以致用，知行合一（实践篇）SVM编程算例100回顾SVM的三步曲

101

4.10.1sklearn里的SVMSVM算法在sklearn.svm工具包中，其中SVC类是用于进行分类任务，SVR是用来进行数值回归任务的。这里使用离散的数值计算来代替连续的数值回归classsklearn.svm.SVC(C=1.0,kernel='rbf',degree=3,gamma='auto',coef0=0.0,shrinking=True,probability=False,tol=0.001,cache_size=200,class_weight=None,verbose=False,max_iter=-1,decision_function_shape='ovr',random_state=None)首先需要选择SVM的核函数，参数kernel指定‘linear’,‘poly’,‘rbf’,‘sigmoid’,‘precomputed’oracallable.1024.10.1sklearn里的SVM

103

示例1：两个特征，两个类别数据集生成一个有两个特征，两个类别的数据集，然后用线性核函数的SVM算法进行分类。104示例1105画出支持向量生成数据网格预测数据网格画出分界线画出训练样本示例2：两个特征，三个类别数据集分别构造4个SVM算法来分割数据集，线性核，三阶多项式核，gamma=0.5的高斯核，gamma=0.1的高斯核。106示例2左上角：线性核右上角：三阶多项式核左下角：gamma=0.5的高斯核右下角：gamma=0.1的高斯核问题：为什么很多支持向量远离分隔超平面？1074.10.2乳腺癌检测使用逻辑回归算法进行了乳腺癌检测模型的学习和训练，这里使用支持向量机来解决这个问题。1）载入数据108这里有569个样本,30个特征;数据集很小，高斯核函数太复杂，容易造成过拟合datashape:(569,30);no.positive:357;no.negative:2124.10.2乳腺癌检测生成训练集和测试集使用高斯核函数进行训练训练集近满分，测试集评分很低，过拟合现象。109参数优化使用GridSearchCV来自动选择gamma参数。110高斯核参数优化设定gamma=0.01，画出学习曲线111过拟合多项式核使用二阶多项式核函数来拟合模型112多项式核画出一阶多项式和二阶多项式的学习曲线113多项式核二阶多项式核的效果更好。114与逻辑回归的比较115SVMDegree=2LogisticDegree=1,penalty=L1LogisticDegree=2,penalty=L1LogisticDegree=1,penalty=L2LogisticDegree=2,penalty=L2最好的效果是Logistic，二阶多项式特征，L1范数的正则项。SVM，二阶多项式核次之。Logistic，二阶多项式特征，L2范数的正则项的效果最差。模型选择和模型参数调优的作用4.10.3人脸识别使用英国剑桥AT&T实验室的研究人员自拍的一组照片（AT&TLaboratoriesCambridge，1992~1994），来开发一个特定的人脸识别系统。1161）加载数据集代码自动到网上下载人脸数据集到子目录datasets中，得到olivetti_py3.pkz文件。加载的图片保存到faces变量中。人脸数据集117原始图像是PGM格式，图像大小为92x112，256级灰度加载数据集整个数据集有400张人脸的缩略图，包含40位人员。每个人10张照片。这里sklearn已经把每张照片做了预处理，裁剪成64x64大小，且人脸居中显示。这一步至关重要，否则我