第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=