模式识别 课件 第4章 线性判别分析

第4章线性判别分析主要内容4.1基本概念4.2Fisher线性判别分析4.3感知器算法4.4最小二乘法4.5支持向量机4.6多类问题4.1基本概念（1）贝叶斯决策的局限性前提：对先验概率和类概率密度函数有充分的先验知识；或有足够多的样本，可以较好地进行概率密度估计。局限：若前提条件不满足，采用最优方法设计出的分类器往往不具有最优的性质估计：实际问题中，得到的只是样本集，样本的分布形式很难确定，进行估计需要大量样本；当样本数有限时，概率密度函数估计问题往往是一个比分类更难的一般性问题实际问题中，不去估计类条件概率，直接利用样本集设计分类器。首先给定某个判别函数，利用样本集去确定判别函数中的未知参数。判别函数分类线性判别函数非线性判别函数（2）利用样本集直接设计分类器的思路4.1基本概念（3）线性判别函数实例分析一维数据

ω2

w0

ω1

两类的分界点为w0

，判别函数表示为：g(x)=w1x-w0二维数据两类的判别函数表示为：w、x均为二维列向量4.1基本概念w、x均为n维列向量，w称为权向量（系数）一般表达式决策规则决策面方程

4.1基本概念

几何解释w和超平面H上任一向量正交，即w是H的法向量

4.1基本概念把一些高次判别函数作适当变换，变换成一次的线性判别函数，称为广义线性判别函数。b

a如图所示，一维样本空间x，如果x<b或x>a，则x∈ω1，如果b<x<a，则x∈ω2。采用线性判别函数无法分类但二次判别函数适用（4）广义线性判别函数4.1基本概念二次判别函数一般表达式：选择x→z的映射，变换二次函数为z的线性函数意义：经过以上变换，可以用简单的线性判别函数来解决复杂问题，但增加了维数。

4.1基本概念（5）广义齐次线性判别函数

经过变换，维数增加一维，但分界面变成了通过原点的超平面，给解决问题带来了方便。4.1基本概念

（6）例题线性和非线性判别分析例4-1：设5维空间的线性方程为试求出其权向量与样本向量点积的表达式。4.1基本概念例4-2：设在三维空间中的一个类别分类问题，拟采用二次曲面，如果要采用线性方程求解，试问其广义样本向量与广义权向量的表达式。4.1基本概念（7）线性判别函数的设计核心思想根据样本集去确定权向量w和w0，或a寻找合适的准则函数如何对准则函数求最优确定的方法首先要有一个准则函数，根据这个准则函数去找出满足要求的尽可能好的结果分类器的设计转化为求准则函数的极值两个关键问题4.1基本概念生成样本集：一般通过抽样生成，个别情况下要转化成增广样本集。确定准则函数极值对应最好的决策是w、w0或a等参数的函数求最优值w*、w0*或a*设计步骤4.1基本概念4.2Fisher线性判别（1）原理降维

把多维空间的样本变换到低维，简化问题。这在模式识别中是一个关键问题。降维的方法把n维样本投影到一条直线上，变换成一维样本投影线不能任意选择选择另一个方向的投影线，投影后两类样本相互分开，很容易分类。Fisher法就是要找到这条最易分类的投影线。对于n维样本，总是可以找到某一个方向，样本投影在这个方向的直线上，分开的最好。如图所示：蓝色的星为一类数据，红色的圆为一类数据，选择紫色的直线为投影线，投影后两类的数据混在一起，很难分开。（2）数学表示

4.2Fisher线性判别（3）基本参量4.2Fisher线性判别线性和非线性判别分析样本类内离散度矩阵：总类内离散度矩阵：样本类间离散度矩阵：各类样本均值向量：样本类内离散度总类内离散度：各类样本均值：降维前降维后（4）准则函数及求解

确定函数式定义准则函数4.2Fisher线性判别

4.2Fisher线性判别求极值点w*（用Lagrange乘数法）

4.2Fisher线性判别线性和非线性判别分析这是一个特征方程，求矩阵的特征值w*就是使Fisher准则函数取极大值时的解，也是使两类样本投影后分开得最好的投影方向。（5）利用Fisher法分类数据转化为一维，只需设定一个阈值点，即可分类4.2Fisher线性判别阈值点的设定

（6）例题

4.2Fisher线性判别4.2Fisher线性判别

4.2Fisher线性判别线性和非线性判别分析

实际中，一般有部分已知类别的样本，去求最好的投影方向W*，然后再对未知类别的样本进行投影并分类。3）分类阈值：

4.2Fisher线性判别

（7）仿真实现按照Fisher线性判别原理，获取训练数据，计算两类的均值、类内离散度矩阵，确定投影方向，计算一维阈值点并对数据归类。设计思路4.2Fisher线性判别程序clc,clear,closeall;X=[-5-5;-5-4;-4-5;-5-6;-6-5;55;54;45;56;65];label=[11111-1-1-1-1-1];index1=find(label==1);index2=find(label==-1);N1=length(index1);N2=length(index2);mu1=mean(X(index1,:));mu2=mean(X(index2,:));S1=(X(index1,:)-mu1)'*(X(index1,:)-mu1);S2=(X(index2,:)-mu2)'*(X(index2,:)-mu2);Sw=S1+S2;W=Sw\(mu1-mu2)';z1=W'*mu1';z2=W'*mu2';z0=(z1+z2)/2;

4.2Fisher线性判别plot(X(index1,1),X(index1,2),'ro',X(index2,1),X(index2,2),'b*');x1=-6:0.1:6;x2=-(W(1)*x1-z0)/W(2);holdon;plot(x1,x2,'g--');x=[31]';plot(x(1),x(2),'rp');z=W'*x;ifz>z0result='属于ω1';elseresult='属于ω2';endresult=strcat('(',num2str(x'),')',result);line1='x1';line2=result;xlabel({line1;line2});ylabel('x2');

title('Fisher线性判别');holdoff;4.2Fisher线性判别仿真结果4.3感知器算法（1）基本概念

线性可分

4.3感知器算法样本的规范化4.3感知器算法解向量和解区

4.3感知器算法梯度下降算法

分析

准则函数

4.3感知器算法

求导梯度法（2）感知器准则函数及求解单样本修正分析

4.3感知器算法准则函数

求导梯度法4.3感知器算法任意给定a(1)和系数ρ利用a(1)去对样本集分类按梯度下降算法修正权向量重复以上过程，直到权向量对所有样本正确分类（a不再变化）分类器训练过程

4.3感知器算法（3）例题解：初始工作对样本进行增广化对样本进行规范化设定系数ρ=1，初始权向量a(1)=04.3感知器算法迭代权向量有修正，需进行第二轮迭代权向量有修正，需进行第三轮迭代4.3感知器算法权向量有修正，需进行第四轮迭代权向量无修正，算法结束4.3感知器算法确定权向量、判别函数及决策面方程权向量：设样本：判别函数：决策面方程：4.3感知器算法（4）仿真实现

按照感知器算法原理，获取训练数据，进行初始化，通过迭代运算计算并更新权向量。设计思路4.3感知器算法clc,clear,closeall;X=[000;100;101;110;001;011;010;111];label=[1111-1-1-1-1];[N,n]=size(X);Z=X;Z(:,n+1)=1;pos=label<0;Z(pos,:)=0-Z(pos,:);A=zeros(n+1,1);rho=1;初始化flag=1;whileflagflag=0;fori=1:Ng=A'*Z(i,:)';ifg<=0

A=A+rho*Z(i,:)';flag=1;endendend迭代求权向量程序4.3感知器算法pos=label<0;scatter3(X(pos>0,1),X(pos>0,2),X(pos>0,3),'r*');holdonscatter3(X(~pos,1),X(~pos,2),X(~pos,3),'g*');[x1,x2]=meshgrid(0:.01:1,0:.01:1);x3=-(A(1)*x1+A(2)*x2+A(4))/A(3);mesh(x1,x2,x3),title('训练样本及分界面');xlabel('x1'),ylabel('x2'),zlabel('x3');holdoff绘图4.3感知器算法仿真结果（4）算法分析只适用于线性可分情况算法的收敛速度依赖于初始权向量和系数ρ非线性可分时，算法来回摆动，不收敛；若运算长时间不收敛，无法判断是非线性可分还是运算时间不够长4.3感知器算法4.4最小二乘法

（1）平方误差和准则函数准则函数

4.4最小二乘法准则函数求最优求导令导数为0，解方程a的确定还依赖于b，需要进一步确定b

算法总结4.4最小二乘法4.4最小二乘法（2）例题

规范化增广样本矩阵取余量：得：4.4最小二乘法（3）仿真实现

设计思路MATLAB中提供的regress、regstats函数实现了基于最小二乘法的多元线性回归，利用回归函数实现权向量求解程序4.4最小二乘法clc,clear,closeall;X1=[000;100;101;110;001;011;010;111];label1=[1;1;1;1;-1;-1;-1;-1];[N,n]=size(X1);Z1=ones(N,n+1);Z1(:,1:n)=X1;

%样本增广化，常数项加在了右侧A=regress(label1,Z1)

%计算权向量

（1）最优分类超平面4.5支持向量机

若一个样本集线性可分，存在无数多解，解区中的任何向量都是一个解向量。在这些解中，哪一个更好？

分类间隔：越大，受扰动影响越小H：把两类没有错误地分开的分类线H1、H2：过两类样本中离分类线最近的点且平行于分类线的线不但能将两类无错误地分开，而且要使两类的分类间隔最大。最优分类超平面

4.5支持向量机

求解最优分类面构建拉格朗日函数4.5支持向量机KKT条件：Karush-Kuhn-Tucker，不等式约束条件求解

4.5支持向量机再求解

求解4.5支持向量机最优权向量是训练向量的线性组合

判别函数由于最优分类面的解最后完全由支持向量决定，因此这种方法后来被称作支持向量机(supportvectormachines-SVM)

以上讨论仅是线性可分情况下的线性支持向量机。4.5支持向量机

（2）优化求解算法支持向量机的求解都依赖于下列式子的最优解4.5支持向量机

解：

4.5支持向量机

判别函数：

4.5支持向量机SMO：SequentialMinimalOptimization，序列最小优化算法，一种高效求解支持向量机的算法迭代单数据算法：IterativelySingleDataAlgorithm，ISDA采用二次规划的L1QP算法SMO的基本思路：在一次迭代中，只优化两个变量，固定其他变量，将一个大的优化问题分解为若干个小的优化问题求解。4.5支持向量机（3）非线性可分情况问题分析

4.5支持向量机

要求分类面不但要使两类的分类间隔最大，而且要错分样本尽可能少且错误程度尽可能低。4.5支持向量机C较小，较容忍错误，强调分类间隔；C较大，强调错误惩罚。目标函数：问题求解4.5支持向量机构建拉格朗日函数KKT条件：最优解4.5支持向量机

软间隔支持向量4.5支持向量机

判别函数：

4.5支持向量机

对于原空间中的非线性问题，通过特征变换将到新空间，在这个新空间中求取最优线性分类面。（4）核函数变换与非线性支持向量机问题分析4.5支持向量机

问题求解4.5支持向量机

判别函数：4.5支持向量机结论分析无论变换的具体形式如何，变换对支持向量机的影响是把两个样本在原特征空间中的内积变成了新空间中的内积：

4.5支持向量机核函数

定义4.5支持向量机Mercer条件

选择一个满足Mercer条件的核函数，可以构建非线性支持向量机。进一步证明，该条件可放松为满足如下条件的正定核：

4.5支持向量机多项式核函数径向基(RBF)核函数Sigmoid函数常用的核函数支持向量机通过选择不同的核函数实现不同形式的非线性分类器；核函数需要针对具体问题来具体选择，很难有一个一般性的准则。4.5支持向量机（5）支持向量机概括线性支持向量机：利用支持向量设计最优分类面非线性数据集设计线性支持向量机：引入余量非线性支持向量机：通过非线性变换将输入空间变换到高维空间，然后在这个新空间中求取最优线性分类面非线性变换通过定义适当的内积核函数实现4.5支持向量机（6）仿真实现4.5支持向量机

利用MATLAB中的fitcsvm、predict函数实现。MODEL=fitcsvm(X,Y)：利用N×n的矩阵X中的数据训练SVM模型MODEL。Y指定N个样本的类别标号。[LABEL,SCORE]=predict(MODEL,X)：利用设计好的SVM模型MODEL对样本X进行预测。设计思路4.5支持向量机程序clc,clear,closeall;X=[000;100;101;110;001;011;010;111];y=[1;1;1;1;-1;-1;-1;-1];SVMModel=fitcsvm(X,y);sv=SVMModel.SupportVectors;

s=SVMModel.KernelParameters;W=SVMModel.Beta/s.Scale;w0=SVMModel.Bias;pattern=[00.60.8];[label,scores]=predict(SVMModel,pattern);4.5支持向量机[x1,x2]=meshgrid(0:.1:1,0:.1:1);x3=-(W(1)*x1+W(2)*x2+w0)/W(3);pos=y<0;scatter3(X(pos>0,1),X(pos>0,2),X(pos>0,3),'r*');holdonscatter3(X(~pos,1),X(~pos,2),X(~pos,3),'g>');scatter3(sv(:,1),sv(:,2),sv(:,3),60,'ko');scatter3(pattern(1),pattern(2),pattern(3),60,'b<');mesh(x1,x2,x3);holdoff仿真结果4.5支持向量机训练样本及线性SVM分类平面4.5支持向量机

clc,clear,closeall;X=