第4章線性判別分析主要內(nèi)容4.1基本概念4.2Fisher線性判別分析4.3感知器算法4.4最小二乘法4.5支持向量機(jī)4.6多類問題4.1基本概念（1）貝葉斯決策的局限性前提：對先驗(yàn)概率和類概率密度函數(shù)有充分的先驗(yàn)知識；或有足夠多的樣本，可以較好地進(jìn)行概率密度估計(jì)。局限：若前提條件不滿足，采用最優(yōu)方法設(shè)計(jì)出的分類器往往不具有最優(yōu)的性質(zhì)估計(jì)：實(shí)際問題中，得到的只是樣本集，樣本的分布形式很難確定，進(jìn)行估計(jì)需要大量樣本；當(dāng)樣本數(shù)有限時，概率密度函數(shù)估計(jì)問題往往是一個比分類更難的一般性問題實(shí)際問題中，不去估計(jì)類條件概率，直接利用樣本集設(shè)計(jì)分類器。首先給定某個判別函數(shù)，利用樣本集去確定判別函數(shù)中的未知參數(shù)。判別函數(shù)分類線性判別函數(shù)非線性判別函數(shù)（2）利用樣本集直接設(shè)計(jì)分類器的思路4.1基本概念（3）線性判別函數(shù)實(shí)例分析一維數(shù)據(jù)

ω2

w0

ω1

兩類的分界點(diǎn)為w0

，判別函數(shù)表示為：g(x)=w1x-w0二維數(shù)據(jù)兩類的判別函數(shù)表示為：w、x均為二維列向量4.1基本概念w、x均為n維列向量，w稱為權(quán)向量（系數(shù)）一般表達(dá)式?jīng)Q策規(guī)則決策面方程

4.1基本概念

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

4.1基本概念把一些高次判別函數(shù)作適當(dāng)變換，變換成一次的線性判別函數(shù)，稱為廣義線性判別函數(shù)。b

a如圖所示，一維樣本空間x，如果x<b或x>a，則x∈ω1，如果b<x<a，則x∈ω2。采用線性判別函數(shù)無法分類但二次判別函數(shù)適用（4）廣義線性判別函數(shù)4.1基本概念二次判別函數(shù)一般表達(dá)式：選擇x→z的映射，變換二次函數(shù)為z的線性函數(shù)意義：經(jīng)過以上變換，可以用簡單的線性判別函數(shù)來解決復(fù)雜問題，但增加了維數(shù)。

4.1基本概念（5）廣義齊次線性判別函數(shù)

經(jīng)過變換，維數(shù)增加一維，但分界面變成了通過原點(diǎn)的超平面，給解決問題帶來了方便。4.1基本概念

（6）例題線性和非線性判別分析例4-1：設(shè)5維空間的線性方程為試求出其權(quán)向量與樣本向量點(diǎn)積的表達(dá)式。4.1基本概念例4-2：設(shè)在三維空間中的一個類別分類問題，擬采用二次曲面，如果要采用線性方程求解，試問其廣義樣本向量與廣義權(quán)向量的表達(dá)式。4.1基本概念（7）線性判別函數(shù)的設(shè)計(jì)核心思想根據(jù)樣本集去確定權(quán)向量w和w0，或a尋找合適的準(zhǔn)則函數(shù)如何對準(zhǔn)則函數(shù)求最優(yōu)確定的方法首先要有一個準(zhǔn)則函數(shù)，根據(jù)這個準(zhǔn)則函數(shù)去找出滿足要求的盡可能好的結(jié)果分類器的設(shè)計(jì)轉(zhuǎn)化為求準(zhǔn)則函數(shù)的極值兩個關(guān)鍵問題4.1基本概念生成樣本集：一般通過抽樣生成，個別情況下要轉(zhuǎn)化成增廣樣本集。確定準(zhǔn)則函數(shù)極值對應(yīng)最好的決策是w、w0或a等參數(shù)的函數(shù)求最優(yōu)值w*、w0*或a*設(shè)計(jì)步驟4.1基本概念4.2Fisher線性判別（1）原理降維

把多維空間的樣本變換到低維，簡化問題。這在模式識別中是一個關(guān)鍵問題。降維的方法把n維樣本投影到一條直線上，變換成一維樣本投影線不能任意選擇選擇另一個方向的投影線，投影后兩類樣本相互分開，很容易分類。Fisher法就是要找到這條最易分類的投影線。對于n維樣本，總是可以找到某一個方向，樣本投影在這個方向的直線上，分開的最好。如圖所示：藍(lán)色的星為一類數(shù)據(jù)，紅色的圓為一類數(shù)據(jù)，選擇紫色的直線為投影線，投影后兩類的數(shù)據(jù)混在一起，很難分開。（2）數(shù)學(xué)表示

4.2Fisher線性判別（3）基本參量4.2Fisher線性判別線性和非線性判別分析樣本類內(nèi)離散度矩陣：總類內(nèi)離散度矩陣：樣本類間離散度矩陣：各類樣本均值向量：樣本類內(nèi)離散度總類內(nèi)離散度：各類樣本均值：降維前降維后（4）準(zhǔn)則函數(shù)及求解

確定函數(shù)式定義準(zhǔn)則函數(shù)4.2Fisher線性判別

4.2Fisher線性判別求極值點(diǎn)w*（用Lagrange乘數(shù)法）

4.2Fisher線性判別線性和非線性判別分析這是一個特征方程，求矩陣的特征值w*就是使Fisher準(zhǔn)則函數(shù)取極大值時的解，也是使兩類樣本投影后分開得最好的投影方向。（5）利用Fisher法分類數(shù)據(jù)轉(zhuǎn)化為一維，只需設(shè)定一個閾值點(diǎn)，即可分類4.2Fisher線性判別閾值點(diǎn)的設(shè)定

（6）例題

4.2Fisher線性判別4.2Fisher線性判別

4.2Fisher線性判別線性和非線性判別分析

實(shí)際中，一般有部分已知類別的樣本，去求最好的投影方向W*，然后再對未知類別的樣本進(jìn)行投影并分類。3）分類閾值：

4.2Fisher線性判別

（7）仿真實(shí)現(xiàn)按照Fisher線性判別原理，獲取訓(xùn)練數(shù)據(jù)，計(jì)算兩類的均值、類內(nèi)離散度矩陣，確定投影方向，計(jì)算一維閾值點(diǎn)并對數(shù)據(jù)歸類。設(shè)計(jì)思路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線性判別仿真結(jié)果4.3感知器算法（1）基本概念

線性可分

4.3感知器算法樣本的規(guī)范化4.3感知器算法解向量和解區(qū)

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

分析

準(zhǔn)則函數(shù)

4.3感知器算法

求導(dǎo)梯度法（2）感知器準(zhǔn)則函數(shù)及求解單樣本修正分析

4.3感知器算法準(zhǔn)則函數(shù)

求導(dǎo)梯度法4.3感知器算法任意給定a(1)和系數(shù)ρ利用a(1)去對樣本集分類按梯度下降算法修正權(quán)向量重復(fù)以上過程，直到權(quán)向量對所有樣本正確分類（a不再變化）分類器訓(xùn)練過程

4.3感知器算法（3）例題解：初始工作對樣本進(jìn)行增廣化對樣本進(jìn)行規(guī)范化設(shè)定系數(shù)ρ=1，初始權(quán)向量a(1)=04.3感知器算法迭代權(quán)向量有修正，需進(jìn)行第二輪迭代權(quán)向量有修正，需進(jìn)行第三輪迭代4.3感知器算法權(quán)向量有修正，需進(jìn)行第四輪迭代權(quán)向量無修正，算法結(jié)束4.3感知器算法確定權(quán)向量、判別函數(shù)及決策面方程權(quán)向量：設(shè)樣本：判別函數(shù)：決策面方程：4.3感知器算法（4）仿真實(shí)現(xiàn)

按照感知器算法原理，獲取訓(xùn)練數(shù)據(jù)，進(jìn)行初始化，通過迭代運(yùn)算計(jì)算并更新權(quán)向量。設(shè)計(jì)思路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迭代求權(quán)向量程序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('訓(xùn)練樣本及分界面');xlabel('x1'),ylabel('x2'),zlabel('x3');holdoff繪圖4.3感知器算法仿真結(jié)果（4）算法分析只適用于線性可分情況算法的收斂速度依賴于初始權(quán)向量和系數(shù)ρ非線性可分時，算法來回?cái)[動，不收斂；若運(yùn)算長時間不收斂，無法判斷是非線性可分還是運(yùn)算時間不夠長4.3感知器算法4.4最小二乘法

（1）平方誤差和準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)

4.4最小二乘法準(zhǔn)則函數(shù)求最優(yōu)求導(dǎo)令導(dǎo)數(shù)為0，解方程a的確定還依賴于b，需要進(jìn)一步確定b

算法總結(jié)4.4最小二乘法4.4最小二乘法（2）例題

規(guī)范化增廣樣本矩陣取余量：得：4.4最小二乘法（3）仿真實(shí)現(xiàn)

設(shè)計(jì)思路MATLAB中提供的regress、regstats函數(shù)實(shí)現(xiàn)了基于最小二乘法的多元線性回歸，利用回歸函數(shù)實(shí)現(xiàn)權(quán)向量求解程序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;

%樣本增廣化，常數(shù)項(xiàng)加在了右側(cè)A=regress(label1,Z1)

%計(jì)算權(quán)向量

（1）最優(yōu)分類超平面4.5支持向量機(jī)

若一個樣本集線性可分，存在無數(shù)多解，解區(qū)中的任何向量都是一個解向量。在這些解中，哪一個更好？

分類間隔：越大，受擾動影響越小H：把兩類沒有錯誤地分開的分類線H1、H2：過兩類樣本中離分類線最近的點(diǎn)且平行于分類線的線不但能將兩類無錯誤地分開，而且要使兩類的分類間隔最大。最優(yōu)分類超平面

4.5支持向量機(jī)

求解最優(yōu)分類面構(gòu)建拉格朗日函數(shù)4.5支持向量機(jī)KKT條件：Karush-Kuhn-Tucker，不等式約束條件求解

4.5支持向量機(jī)再求解

求解4.5支持向量機(jī)最優(yōu)權(quán)向量是訓(xùn)練向量的線性組合

判別函數(shù)由于最優(yōu)分類面的解最后完全由支持向量決定，因此這種方法后來被稱作支持向量機(jī)(supportvectormachines-SVM)

以上討論僅是線性可分情況下的線性支持向量機(jī)。4.5支持向量機(jī)

（2）優(yōu)化求解算法支持向量機(jī)的求解都依賴于下列式子的最優(yōu)解4.5支持向量機(jī)

解：

4.5支持向量機(jī)

判別函數(shù)：

4.5支持向量機(jī)SMO：SequentialMinimalOptimization，序列最小優(yōu)化算法，一種高效求解支持向量機(jī)的算法迭代單數(shù)據(jù)算法：IterativelySingleDataAlgorithm，ISDA采用二次規(guī)劃的L1QP算法SMO的基本思路：在一次迭代中，只優(yōu)化兩個變量，固定其他變量，將一個大的優(yōu)化問題分解為若干個小的優(yōu)化問題求解。4.5支持向量機(jī)（3）非線性可分情況問題分析

4.5支持向量機(jī)

要求分類面不但要使兩類的分類間隔最大，而且要錯分樣本盡可能少且錯誤程度盡可能低。4.5支持向量機(jī)C較小，較容忍錯誤，強(qiáng)調(diào)分類間隔；C較大，強(qiáng)調(diào)錯誤懲罰。目標(biāo)函數(shù)：問題求解4.5支持向量機(jī)構(gòu)建拉格朗日函數(shù)KKT條件：最優(yōu)解4.5支持向量機(jī)

軟間隔支持向量4.5支持向量機(jī)

判別函數(shù)：

4.5支持向量機(jī)

對于原空間中的非線性問題，通過特征變換將到新空間，在這個新空間中求取最優(yōu)線性分類面。（4）核函數(shù)變換與非線性支持向量機(jī)問題分析4.5支持向量機(jī)

問題求解4.5支持向量機(jī)

判別函數(shù)：4.5支持向量機(jī)結(jié)論分析無論變換的具體形式如何，變換對支持向量機(jī)的影響是把兩個樣本在原特征空間中的內(nèi)積變成了新空間中的內(nèi)積：

4.5支持向量機(jī)核函數(shù)

定義4.5支持向量機(jī)Mercer條件

選擇一個滿足Mercer條件的核函數(shù)，可以構(gòu)建非線性支持向量機(jī)。進(jìn)一步證明，該條件可放松為滿足如下條件的正定核：

4.5支持向量機(jī)多項(xiàng)式核函數(shù)徑向基(RBF)核函數(shù)Sigmoid函數(shù)常用的核函數(shù)支持向量機(jī)通過選擇不同的核函數(shù)實(shí)現(xiàn)不同形式的非線性分類器；核函數(shù)需要針對具體問題來具體選擇，很難有一個一般性的準(zhǔn)則。4.5支持向量機(jī)（5）支持向量機(jī)概括線性支持向量機(jī)：利用支持向量設(shè)計(jì)最優(yōu)分類面非線性數(shù)據(jù)集設(shè)計(jì)線性支持向量機(jī)：引入余量非線性支持向量機(jī)：通過非線性變換將輸入空間變換到高維空間，然后在這個新空間中求取最優(yōu)線性分類面非線性變換通過定義適當(dāng)?shù)膬?nèi)積核函數(shù)實(shí)現(xiàn)4.5支持向量機(jī)（6）仿真實(shí)現(xiàn)4.5支持向量機(jī)

利用MATLAB中的fitcsvm、predict函數(shù)實(shí)現(xiàn)。MODEL=fitcsvm(X,Y)：利用N×n的矩陣X中的數(shù)據(jù)訓(xùn)練SVM模型MODEL。Y指定N個樣本的類別標(biāo)號。[LABEL,SCORE]=predict(MODEL,X)：利用設(shè)計(jì)好的SVM模型MODEL對樣本X進(jìn)行預(yù)測。設(shè)計(jì)思路4.5支持向量機(jī)程序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支持向量機(jī)[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仿真結(jié)果4.5支持向量機(jī)訓(xùn)練樣本及線性SVM分類平面4.5支持向量機(jī)

clc,clear,closeall;X=