第五章 線性判別函數,線性判別函數 Fisher線性判別 最小平方誤差準則 多類問題 分段線性判別函數,5.1 問題的提出 GenerativeDiscriminative,基于樣本的Bayes分類器：通過估計類條件概率密度函數，設計相應的判別函數,“最優(yōu)”分類器：錯誤率最小，風險最小等對分類器設計在理論上有指導意義 獲取統(tǒng)計分布及其參數很困難，實際問題中并不一定具備獲取統(tǒng)計分布的條件,訓練 樣本集,樣本分布的 統(tǒng)計特征： 概率密度函數,決策規(guī)則： 判別函數 決策面方程,判別函數,基于訓練樣本確定判別函數,例：正態(tài)分布最小錯誤率貝葉斯分類器在特殊情況下，是線性判別函數 g(x)=wTx（決策面是超平面），能否基于樣本直接確定w? 設定判別函數形式，用樣本集確定參數 使用準則函數，表達分類器應滿足的要求 這些準則的“最優(yōu)”并不一定與錯誤率最小相一致：次優(yōu)分類器,該樣本集中的每個樣本的類別已知,線性分類器設計步驟,線性分類器設計任務：給定樣本集K，確定線性判別函數 g(x)=wTx 的各項系數w： 收集一組樣本K=x1,x2,xN 按需要確定一準則函數J(K,w)，其值反映分類器的性能，其極值解對應于“最優(yōu)”決策 用最優(yōu)化技術求準則函數J的極值解w*，從而確定判別函數，完成分類器設計,對于未知樣本x，計算g(x)，判斷其類別,設計,應用,線性判別函數,d維空間中的線性判別函數的一般形式：,x是樣本向量，即樣本在d維特征空間中的描述， w是權向量，w0是一個常數(閾值權),為了說明向量W的意義，我們假設在決策平面上有兩個特征向量X1與X2，則應有 其中(X1-X2)也是一個向量，上式表明向量W與該平面上任兩點組成的向量(X1-X2)正交，因此W的方向就是決策面的法線方向,兩類問題的分類決策規(guī)則,是決策面方程，它是兩類模式的分界，對于二維空間情況，它是一條直線；對于三維情況，它是一個平面；而對于高維空間的情況，則是一個超平面,構造一個二類模式的線性分類器，如下圖所示：,線性判別函數的幾何意義,決策面(decision boundary) H 方程：g(x)=0 決策面將特征空間分成決策區(qū)域 向量w是決策面H的法向量 g(x)是點x到決策面H的距離的一種代數度量,線性判別函數的幾何意義,結論：利用線性判別函數進行決策，就是用一個超平面把特征空間分割成兩個決策區(qū)域，超平面方向由權向量W決定，它的位置由閾值權w0確定,=0,廣義線性判別函數,線性判別函數是形式最為簡單的判別函數，但是它不能用于復雜情況 例：設計一個一維分類器，使其功能為：,判別函數：,廣義線性判別函數,二次函數的一般形式：,g(x)又可表示成：,映射XY,廣義線性判別函數,按照上述原理，任何非線性函數g(x)用級數展開成高次多項式后，都可轉化成線性來處理 一種特殊映射方法：增廣樣本向量y與增廣權向量a,廣義線性判別函數,增廣樣本向量使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對于分類效果也與原決策面相同，只是在Y空間中決策面是通過坐標原點的，這在分析某些問題時具有優(yōu)點，因此經常用到。,線性判別函數的齊次簡化：,廣義線性判別函數,例1：設五維空間的線性方程為55x1+68x2+32x3+16x4+26x5+10 =0，試求出其權向量與樣本向量點積的表達式wTx+w0=0中的w，x以及增廣權向量與增廣樣本向量形式aTy中的a與y。,答： 樣本向量：x = (x1, x2, x3, x4, x5)T 權向量：w = (55, 68, 32, 16, 26)T, w0=10 增廣樣本向量：y = (1, x1, x2, x3, x4, x5)T 增廣權向量：a = (10, 55, 68, 32, 16, 26)T,廣義線性判別函數,例2：有一個三次判別函數：z=g(x)=x3+2x2+3x+4。試建立一映射xy，使得z轉化為y的線性判別函數。,答：映射XY如下：,廣義線性判別函數,例3：設在三維空間中一個兩類別分類問題擬采用二次曲面。如欲采用廣義線性方程求解，試問其廣義樣本向量與廣義權向量的表達式，其維數是多少？,答：設該二次曲面方程為:,二次 曲面,廣義 權向量,廣義樣本向量,維數為10,廣義線性 判別函數,5.2 Fisher線性判別 降維/兩類,線性判別函數 y = g(x) = wTx : 樣本向量x各分量的線性加權 樣本向量x與權向量w的向量點積 如果| w |=1，則視作向量x在w上的投影 Fisher準則的基本原理：找到一個最理想的投影軸，使兩類樣本在該軸上投影之間的距離盡可能遠，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳,Fisher線性判別圖例,Fisher準則的描述：用投影后數據的統(tǒng)計性質 均值和離散度的函數作為判別優(yōu)劣的標準,d維X空間樣本分布的描述量,各類樣本均值向量mi,樣本類內離散度矩陣Si與總類內離散度矩陣Sw,樣本類間離散度矩陣Sb：,離散度矩陣在形式上與協(xié)方差矩陣很相似,一維Y空間樣本分布的描述量,各類樣本均值,樣本類內離散度和總類內離散度,樣本類間離散度,以上定義描述d維空間樣本點到一向量投影后的分散情況,原樣本與其投影統(tǒng)計量間的關系,樣本x與其投影 y 的統(tǒng)計量之間的關系：,樣本與其投影統(tǒng)計量間的關系,Fisher準則函數,評價投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內盡可能密集的要求 Fisher準則函數的定義：,Fisher最佳投影方向的求解,Fisher最佳投影方向的求解,采用拉格朗日乘子算法解決,m1-m2是一向量，對與(m1-m2)平行的向量投影可使兩均值點的距離最遠。但是如果從使類間分得較開，同時又使類內密集程度較高這樣一個綜合指標來看，則需根據兩類樣本的分布離散程度對投影方向作相應的調整，這就體現在對m1-m2 向量按Sw-1作一線性變換，從而使Fisher準則函數達到極值點,判別函數的確定,前面討論了使Fisher準則函數極大的d維向量w*的計算方法，判別函數中的另一項w0（閾值）可采用以下幾種方法確定：,分類規(guī)則:,Fisher準則舉例,例1：設兩類樣本的類內離散矩陣分別為S1，S2，各類樣本均值分別為m1=(2, 0)T, m2=(2, 2)T, 試用Fisher準則求其決策面方程,解,由于兩類樣本分布形狀是相同的（只是方向不同），因此w0應為（投影后）兩類均值的中點,Fisher準則最佳投影,Fisher準則最佳分界面,Fisher最佳線性分界面,R1,R2,圖中綠線為最佳分界面,x1,x2,5.3 最小平方誤差準則 MSE,對于增廣樣本向量，線性判別函數為 g(x)=aTy 規(guī)范化增廣樣本向量yi，增廣權向量a，yi被正確分類，要求： aTyi0, i=1,N 線性分類器設計 求一組N個線性不等式的解 樣本集增廣矩陣Y及一組N個線性不等式的的矩陣表示：,引入余量(目標向量) b=b1, b2, , bNT， bi任意給定正常數， aTyi = bi 0 N個線性方程的的矩陣表示：,平方誤差準則函數,定義誤差向量 e =Ya - b： 定義平方誤差準則函數 Js(a):,最小二乘解（MSE解）：,MSE方法的思想：對每個樣本，設定一個“理想”的判別函數輸出值，以最小平方誤差為準則求最優(yōu)權向量,MSE準則函數的偽逆解,Y的 偽逆矩陣,MSE方法的迭代解,a*=Y+b, Y+=(YTY)-1YT，計算量大 實際中常用梯度下降法：,批量樣本修正法,單樣本修正法,梯度下降算法：對(迭代)向量沿某函數的負梯度方向修正，可較快到達該函數極小值,MSE方法與 Fisher方法的關系,與Fisher方法的關系：可證明當,MSE解等價于Fisher解,MSE方法與Bayes方法的關系,可證明當N，b=uN= 1,1, , 1T 時，則它以最小均方誤差逼近Bayes判別函數：,5.4 多類問題,兩類別問題可以推廣到多類別問題 i/i 法：將C類別問題化為(C-1)個兩類（第i類與所有非i類）問題，按兩類問題確定其判別函數與決策面方程 i/j 法：將C類中的每兩類別單獨設計其線性判別函數，因此總共有C(C-1)/2個線性判別函數,多類線性判別函數,將特征空間確實劃分為c個決策域，共有c個判別函數,決策規(guī)則：,決策域的邊界由相鄰決策域的判別函數共同決定，此時應有gi(x)=gj(x) 線性分類器的決策面是凸的，決策區(qū)域是單連通的 多類分類器的分界面是分段線性的,多類線性決策面圖例,決策樹,決策樹：一種多極分類器，它采用分級的形式，綜合用多個決策規(guī)則，逐步把復雜的多類別分類問題轉化為若干個簡單的分類問題來解決,二叉決策樹,二叉決策樹把復雜的多類別分類問題轉化為多級兩類分類問題來解決,5.5 分段線性判別函數,有些復雜模式識別問題不是線性可分的，需使用非線性的分類方法 分段線性判別函數：一種特殊的非線性判別函數，它的決策面是若干超平面,分段線性距離分類器,最小距離分類器：把各類別樣本的均值向量作為各類的代表點(prototype) ，根據待識樣本到各類別代表點的最小距離判別其類別。決策面是兩類別均值連線的垂直平分面,分段線性距離分類器,分段線性距離分類器：將各類別劃分成相對密集的子類，每個子類以它們的均值作為代表點，然后按最小距離分類,基于距離的分段線性判別函數,判別函數定義：i有l(wèi)i個子類，即屬于i 的決策域Ri分成li個子域Ri1, Ri2, Rili)，每個子區(qū)域用均值mik作為代表點,判別規(guī)則：,分段線性判別函數,分段線性判別函數的形式: gik(x)表示第i類第k段線性判別函數，li為i類所具有的判別函數個數，wik與wi0k分別是第k段的權向量與閾值,第i類的判別函數:,分段線性判別函數,判別規(guī)則: