判別函數(shù)及幾何分類法.ppt

第3章 判別函數(shù)及幾何分類法,第3章 判別函數(shù)及幾何分類法,3.1 判別函數(shù) 3.2 線性判別函數(shù) 3.3 廣義線性判別函數(shù) 3.4 線性判別函數(shù)的幾何性質(zhì) 3.5 感知器算法 3.6 梯度法 3.7 最小平方誤差算法 3.8 非線性判別函數(shù),3.1 判別函數(shù),聚類分析法（第七章）,判決函數(shù)法,幾何分類法 確定性事件分類 （第三章）,概率分類法 隨機(jī)事件分類 （第二章）,線性判決函數(shù)法,統(tǒng) 計(jì) 決 策 方 法,非線性判決函數(shù)法,復(fù)習(xí)與引申：,若分屬于1，2的兩類模式可用一方程d(X) =0來(lái) 劃分，那么稱d(X) 為判別函數(shù)，或稱判決函數(shù)、 決策函數(shù)。,3.1 判別函數(shù)(discriminant function),直接用來(lái)對(duì)模式進(jìn)行分類的準(zhǔn)則函數(shù)。,例：一個(gè)二維的兩類判別問(wèn)題，模式分布如圖示，這些分屬于1，2兩類的模式可用一直線方程 d(X)=0來(lái)劃分。,為坐標(biāo)變量，,為方程參數(shù)。,式中：,圖3.2 兩類二維模式的分布,1判別函數(shù)的定義,若 ，則,若 ，則 類；,若 ，則 類；,或拒絕,將某一未知模式 X 代入：,維數(shù)=3時(shí)：判別邊界為一平面。 維數(shù)3時(shí)：判別邊界為一超平面。,d(X) 表示的是一種分類的標(biāo)準(zhǔn)，它可以是1、2、3維的， 也可以是更高維的。,判別界面的正負(fù)側(cè)，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的。,2判別函數(shù)正負(fù)值的確定,圖3.3 判別函數(shù)正負(fù)的確定,1）判決函數(shù)d(X)的幾何性質(zhì)。它可以是線性的或非線性的函 數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。,如：已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：,3. 確定判別函數(shù)的兩個(gè)因素,例：非線性判決函數(shù),2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。,3.2 線性判別函數(shù),3.2.1 線性判別函數(shù)的一般形式,將二維模式推廣到n維，線性判別函數(shù)的一般形式為：,(3-2),式中：,增廣向量的形式：,式中：,為增廣權(quán)向量，,為增廣模式向量。,權(quán)向量,3.2.2 線性判別函數(shù)的性質(zhì),1. 兩類情況,對(duì)M個(gè)線性可分模式類，1， 2， M，有三種 劃分方式：,2. 多類情況,兩分法,兩分法,兩分法特例,用線性判別函數(shù)將屬于i類的模式與其余不屬于i類的 模式分開(kāi)。,識(shí)別分類時(shí)：,對(duì)某一模式區(qū)，di(X)0 的條件超過(guò)一個(gè)，或全部 的di(X)0 ，分類失效。 相當(dāng)于不確定區(qū)(indefinite region ，IR)。,此法將 M 個(gè)多類問(wèn)題分成M個(gè)兩類問(wèn)題，識(shí)別每一類均 需M個(gè)判別函數(shù)。識(shí)別出所有的M類仍是這M個(gè)函數(shù)。,例3.1 設(shè)有一個(gè)三類問(wèn)題，其判別式為：,現(xiàn)有一模式，X=7,5T，試判定應(yīng)屬于哪類？并畫出三類模式的分布區(qū)域。,解：將X=7,5T代入上三式，有：,三個(gè)判別界面分別為：,圖示如下：,步驟：,a) 畫出界面直線。,b) 判別界面正負(fù)側(cè)：找特殊點(diǎn)帶入。,c) 找交集。,例3.2 已知di(X)的位置和正負(fù)側(cè)，分析三類模式的分布區(qū)域 。,一個(gè)判別界面只能分開(kāi)兩個(gè)類別，不能把其余所有的類 別都分開(kāi)。判決函數(shù)為： 。這里 。,則 類，而 在判別 類模式時(shí)不起作用。,如：對(duì)一個(gè)三類問(wèn)題，如果 ，,識(shí)別分類時(shí)：,判別函數(shù)性質(zhì)：,與 值無(wú)關(guān)。,例3.3 一個(gè)三類問(wèn)題，三個(gè)判決函數(shù)為：,解：計(jì)算得,可寫成：,x2,x1,d23(X)=0,d12(X)=0,d13(X)=0,5,5,3,0,分類時(shí)：每分離出一類，需要與I 有關(guān)的M-1個(gè)判決函數(shù)；要分開(kāi)M類模式，共需M(M-1)/2個(gè)判決函數(shù)。對(duì)三類問(wèn)題需要3(3-1)/2=3個(gè)判決函數(shù)。即：每次從M類中取出兩類的組合：,例3.4 已知dij(X)的位 置和正負(fù)側(cè)，分析三 類模式的分布區(qū)域 。,當(dāng)i /j兩分法中的判別函數(shù)dij(X) ，可以定義為,時(shí)，那么di(X) dj(X)就相當(dāng)于多類情況2中的dij(X) 0。,因此對(duì)具有判別函數(shù),的M類情況，判別函數(shù)性質(zhì)為：,或：,識(shí)別分類時(shí)：,判別界面需 要做差值。對(duì)i 類，應(yīng)滿足： di其他所有dj, 除邊界區(qū)外，沒(méi)有不確定區(qū)域。,特點(diǎn)：, 是第二種情況的特例。由于dij(X)= di (X) dj(X) ，若在第三 種情況下可分，則在第二種情況下也可分，但反過(guò)來(lái)不一定。, 把 M 類情況分 成了(M -1)個(gè)兩類 問(wèn)題。并且 類 的判別界面全部與 類的判別 界面相鄰（向無(wú)窮 遠(yuǎn)處延伸的區(qū)域除 外）。,特別的定義,例3.5 一個(gè)三類模式（M=3）分類器，其判決函數(shù)為：,試判斷X0=1,1T屬于哪一類，且分別給出三類的判決界面。,解：,判決界面如圖所示。,類的判決函數(shù)：,類的判決函數(shù)：,例3.6 已知判決界面的位置和正負(fù)側(cè)，分析三類模式的分布 區(qū)域 。,(1) 明確概念：線性可分。,一旦線性判別函數(shù)的系數(shù)Wk被確定以后，這些函數(shù)就可以 作為模式分類的基礎(chǔ)。,3. 小結(jié),(2) 分法的比較：,對(duì)于M類模式的分類， 兩分法共需要M個(gè)判別函數(shù)，但 兩分法需要M(M-1)/2個(gè)。當(dāng)時(shí)M3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。,原因：,一種類別模式的分布要比M-1類模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性大。,兩分法,若只有di(X)0，其他d(X)均0，則判為i 類,兩分法:,定義,1非線性多項(xiàng)式函數(shù) 非線性判別函數(shù)的形式之一是非線性多項(xiàng)式函數(shù)。,3.3 廣義線性判別函數(shù),目的： 對(duì)非線性邊界：通過(guò)某映射，把模式空間X變成X*，以便 將X空間中非線性可分的模式集，變成在X*空間中線性可分的 模式集。,設(shè)一訓(xùn)練用模式集，X在模式空間X中線性不可分，非線 性判別函數(shù)形式如下：,(3-9),式中 是模式X的單值實(shí)函數(shù)， 。,fi(X)取什么形式及d(X)取多少項(xiàng)，取決于非線性邊界的復(fù)雜程度。,廣義形式的模式向量定義為：,(3-10),這里X*空間的維數(shù)k高于X空間的維數(shù)n，(3-9)式可寫為,上式是線性的。討論線性判別函數(shù)并不會(huì)失去一般性的意義。,(3-11),隨著小樣本學(xué)習(xí)理論和支持向量機(jī)的迅速發(fā)展，廣義線性 判別函數(shù)的 “維數(shù)災(zāi)難”問(wèn)題在一定程度上找到了解決的辦法。,非線性變換可能非常復(fù)雜 。,問(wèn)題：,維數(shù)大大增加： 維數(shù)災(zāi)難。,例3.7 假設(shè)X為二維模式向量， fi(X)選用二次多項(xiàng)式函數(shù)，原判 別函數(shù)為,定義：,d(X)線性化為：,即：,廣義線性判別函數(shù)：,3.4 線性判別函數(shù)的幾何性質(zhì),3.4.1 模式空間與超平面,模式空間：以n維模式向量X的n個(gè)分量為坐標(biāo)變量的歐氏空間。,模式向量的表示：點(diǎn)、有向線段。,線性分類：用d(X)進(jìn)行分類，相當(dāng)于用超平面d(X)=0把模式空 間分成不同的決策區(qū)域。,2. 討論,1. 概念,式中， ， 。,設(shè)判別函數(shù)：,超平面：,(1) 模式向量X1和X2在超平面上, W0是超平面的法向量， 方向由超平面的負(fù)側(cè)指向正側(cè)。,設(shè)超平面的單位法向量為U：,(2) X不在超平面上,將X向超平面投影得向量Xp， 構(gòu)造向量R：,r：X到超平面的垂直距離。有,(r), 判別函數(shù)d(X) 正比于點(diǎn)X到超平面的代數(shù)距離。,X到超平面的距離：, 點(diǎn)X到超平面的代數(shù)距離（帶正負(fù)號(hào)）正比于d(X)函數(shù)值。,(3) X在原點(diǎn),得, 超平面的位置由閾值權(quán)wn+1決定：,wn+1 0時(shí)，原點(diǎn)在超平面的正側(cè)；,wn+1 0時(shí)，原點(diǎn)在超平面負(fù)側(cè)；,wn+1= 0 時(shí)，超平面通過(guò)原點(diǎn)。,3.4.2 權(quán)空間與權(quán)向量解,1. 概念,權(quán)空間：以 的權(quán)系數(shù)為 坐標(biāo)變量的（n+1）維歐氏空間,增廣權(quán)向量的表示：點(diǎn)、有向線段。,2. 線性分類,判別函數(shù)形式已定，只需確定權(quán)向量。,類：X11，X12，X1p,類： X21，X22，X2q,設(shè)增廣樣本向量：,使d(X)=0將1和 2分開(kāi)，需滿足,給2的q個(gè)增廣模式乘以（1），統(tǒng)一為, 其中, 樣本的規(guī)范化過(guò)程。,對(duì)每個(gè)已知的X，d(X)=0在權(quán)空間確定一個(gè)超平面，共(p+q)個(gè)。,在權(quán)空間中尋找向量W使判別函數(shù)d(X)能把1類和2類 分開(kāi)，就是尋找一個(gè)權(quán)向量，使得上式中的（p+q）個(gè)不等式 同時(shí)成立, 因此滿足條件的權(quán)向量必然在（p+q）個(gè)超平面的 正側(cè)的交迭區(qū)域里(即W的解區(qū))。,X：規(guī)范化增廣樣本向量。,例：二維權(quán)空間，超平面的方程為：,超平面：過(guò)原點(diǎn)的直線；,陰影部分：解區(qū)。,3.4.3 二分法,二分法（Dichotomies）：用判別函數(shù)d(X)將給定的N個(gè)模式 分成兩類的方法。是一種基本的分類方法。,判別函數(shù)的不同分類能力可以通過(guò)二分法總數(shù)衡量。,若不限制判別函數(shù)的形式，N個(gè)n維模式用判別函數(shù)分成兩 類的二分法總數(shù)為2N。,若限定用線性判別函數(shù)，并且樣本在模式空間是良好分布 的，即在n維模式空間中沒(méi)有(n+1)個(gè)模式位于(n1)維子空間 中，可以證明，N個(gè)n維模式用線性判別函數(shù)分成兩類的方法總 數(shù)，即線性二分法總數(shù)為,或線性二分法概率：,只要模式的個(gè)數(shù)N小于或等于增廣模式的維數(shù)（n+1）， 模式類總是線性可分的，,例：4個(gè)良好分布的2維模式，若用線性判別函數(shù)分類,線性二分法總數(shù)：,線性二分法概率：,圖3.14 線性二分法的概率,將=2時(shí)的N值定義為閾值N0，稱為二分法能力，即,通過(guò)N0，可以對(duì)任意N個(gè)樣本的線性可分性進(jìn)行粗略估計(jì)。,3.5 感知器算法,1. 概念理解,訓(xùn)練：用已知類別的模式樣本指導(dǎo)機(jī)器對(duì)分類規(guī)則進(jìn)行反復(fù)修 改，最終使分類結(jié)果與已知類別信息完全相同的過(guò)程。,1）訓(xùn)練與學(xué)習(xí),只要求出權(quán)向量，分類器的設(shè)計(jì)即告完成。本節(jié)開(kāi)始介紹如何通過(guò)各種算法，利用已知類別的模式樣本訓(xùn)練出權(quán)向量W。,對(duì)線性判別函數(shù)，當(dāng)模式維數(shù)已知時(shí)，判別函數(shù)的形式實(shí)際上已經(jīng)確定，如：三維時(shí),3）感知器 對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼，屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問(wèn)題，由于無(wú)法實(shí)現(xiàn)非線性分類而下馬。但“賞罰概念（ reward-punishment concept）” 得到廣泛應(yīng)用。,2）確定性分類器,處理確定可分情況的分類器。通過(guò)幾何方法將特征空間 分解為對(duì)應(yīng)不同類的子空間，又稱為幾何分類器。,2. 感器算法（perception approach）,兩類線性可分的模式類： ，設(shè),其中， ，,應(yīng)具有性質(zhì),對(duì)樣本進(jìn)行規(guī)范化處理，即2類樣本全部乘以(1)，則有：,感知器算法通過(guò)對(duì)已知類別的訓(xùn)練樣本集的學(xué)習(xí)，尋找 一個(gè)滿足上式的權(quán)向量。,感知器算法步驟：,（1）選擇N個(gè)分屬于1和 2類的模式樣本構(gòu)成訓(xùn)練樣本集 X1, , XN 構(gòu)成增廣向量形式，并進(jìn)行規(guī)范化處理。任取權(quán)向量初始 值W(1)，開(kāi)始迭代。迭代次數(shù)k=1 。,（2）用全部訓(xùn)練樣本進(jìn)行一輪迭代，計(jì)算WT(k)Xi 的值，并修 正權(quán)向量。,分兩種情況，更新權(quán)向量的值：,c：正的校正增量。,分類器對(duì)第i個(gè)模式做了錯(cuò)誤分類，,權(quán)向量校正為：,統(tǒng)一寫為：,（3）分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到（2），直至 對(duì)所有樣本正確分類。,分類正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變； 分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。,感知器算法是一種賞罰過(guò)程：,3. 收斂性,收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的W，則稱算法是收斂的。,可以證明感知器算法是收斂的。 收斂條件：模式類別線性可分。,例3.8 已知兩類訓(xùn)練樣本,解：所有樣本寫成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。,用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。,任取W(1)=0，取c=1，迭代過(guò)程為：,第一輪：,有兩個(gè)WT(k)Xi 0的情況（錯(cuò)判），進(jìn)行第二輪迭代。,第二輪：,第三輪：,第四輪：,該輪迭代的分類結(jié)果全部正確，故解向量,相應(yīng)的判別函數(shù)為：,當(dāng)c、W(1)取其他值 時(shí)，結(jié)果可能不一樣， 所以感知器算法的解不是單值的。,判別界面d(X)=0如圖示。,采用多類情況3的方法時(shí)，應(yīng)有：,4. 感知器算法用于多類情況,對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù)：,算法主要內(nèi)容：,設(shè)有 M 種模式類別：,設(shè)其權(quán)向量初值為：,第k次迭代時(shí)，一個(gè)屬于i類的模式樣本 X 被送入分類器， 計(jì)算所有判別函數(shù),訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理。,分二種情況修改權(quán)向量：, 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即：,可以證明：只要模式類在情況3判別函數(shù)時(shí)是可分的，則 經(jīng)過(guò)有限次迭代后算法收斂。,， c為正的校正增量,例3.9 設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為, 若 則權(quán)向量不變；,現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)。,解：增廣向量形式：,注意，這里任一類的樣本都不能乘以（1）。,任取初始權(quán)向量,；c=1,第一次迭代：,三個(gè)權(quán)向量都需要修改：,第二次迭代：,第三次迭代：,修改為權(quán)向量。,以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類，進(jìn) 行下一輪迭代。,第四次迭代： ,在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。,權(quán)向量的解：,判別函數(shù)：,設(shè)函數(shù)f (Y)是向量 的函數(shù)，則f (Y)的梯度 定義為：,3.6 梯度法,梯度的方向是函數(shù) f (Y) 在Y點(diǎn)增長(zhǎng)最快的方向， 梯度的模是f (Y)在增長(zhǎng)最快的方向上的增長(zhǎng)率 (增長(zhǎng)率最大值)。,1. 梯度概念,梯度向量的最重要性質(zhì)之一：指出函數(shù) f 在其自變量增加 時(shí)，增長(zhǎng)最快的方向。,3.6.1 梯度法基本原理,顯然：負(fù)梯度指出了最陡下降方向。梯度算法的依據(jù)。,即：,2. 梯度算法,設(shè)兩個(gè)線性可分的模式類1和2的樣本共N個(gè)，2類樣本 乘(-1)。將兩類樣本分開(kāi)的判決函數(shù)d(X)應(yīng)滿足：,梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo) 思想是將聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的 問(wèn)題。,N個(gè)不等式,準(zhǔn)則函數(shù)的選取原則： 具有唯一的最小值，并且這個(gè)最小值發(fā)生在W TXi0時(shí)。,用負(fù)梯度向量的值對(duì)權(quán)向量W進(jìn)行修正，實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá) 到極小值的目的。,定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J(W, X)，在J的梯度 方向上對(duì)權(quán)向量進(jìn)行修改。一般關(guān)系表示成從W(k)導(dǎo)出W(k+1)：,其中c是正的比例因子。,（1）將樣本寫成規(guī)范化增廣向量形式，選擇準(zhǔn)則函數(shù)，設(shè)置初始權(quán)向量W(1)，括號(hào)內(nèi)為迭代次數(shù)k=1。,權(quán)向量修正為：,迭代次數(shù)k加1，輸入下一個(gè)訓(xùn)練樣本，計(jì)算新的權(quán)向量，直至對(duì)全部訓(xùn)練樣本完成一輪迭代。,（3）在一輪迭代中，如果有一個(gè)樣本使 ，回到(2)進(jìn)行下 一輪迭代。否則， W不再變化，算法收斂。,（2）依次輸入訓(xùn)練樣本X。設(shè)第k次迭代時(shí)輸入樣本為Xi，此時(shí) 已有權(quán)向量W(k)，求 ：,例3.10 選擇準(zhǔn)則函數(shù) ， ，簡(jiǎn)單地考慮 X為一維增廣模式的情況X=1，此時(shí)W=w，兩者均為標(biāo)量，,錯(cuò)誤分類時(shí)：,， 對(duì)權(quán)向量校正。,正確分類時(shí)：,， 對(duì)權(quán)向量不做修正。,隨著權(quán)向量W向理想值接近，準(zhǔn)則函數(shù)關(guān)于W的導(dǎo)數(shù) ( ) 越來(lái)越趨近于零，這意味著準(zhǔn)則函數(shù)J 越來(lái)越接近最小值。當(dāng) 最終 時(shí)，J達(dá)到最小值，此時(shí)W不再改變，算法收斂。, 將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為 求函數(shù)J極小值的問(wèn)題。,c) 梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形 式取決于準(zhǔn)則函數(shù)J(W, X)的選擇，J(W, X)的形式不同，得到的 具體算法不同。,a),b) c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。,3.6.2 固定增量法,準(zhǔn)則函數(shù)：,求W(k)的遞推公式：,1. 求J的梯度,方法：函數(shù)對(duì)向量求導(dǎo)=函數(shù)對(duì)向量的分量求導(dǎo)，即,該準(zhǔn)則函數(shù)有唯一最小值“0”，且發(fā)生在 的時(shí)候。,設(shè) ，,部分：,首先求,另：矩陣論中有,其中, 由的結(jié)論 有：,將 代入,得：,由此可以看出，感知器算法是梯度法的特例。即：梯度法是將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題，將原來(lái)有多個(gè)解的情況，變成求最優(yōu)解的情況。,上式即為固定增量算法，與感知器算法形式完全相同 。,即：,只要模式類是線性可分的，算法就會(huì)給出解。,線性分類器設(shè)計(jì)步驟,線性分類器設(shè)計(jì)任務(wù)：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項(xiàng)系數(shù)w。步驟： 抽取類別標(biāo)志明確的樣本集合 K=x1,x2,xN作為訓(xùn)練樣本集。 確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對(duì)應(yīng)于“最好”決策。 用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設(shè)計(jì)。,對(duì)于未知樣本x，計(jì)算g(x)，判斷其類別。,4.2 Fisher線性判別,線性判別函數(shù)y=g(x)=wTx: 樣本向量x各分量的線性加權(quán) 樣本向量x與權(quán)向量w的向量點(diǎn)積 如果| w |=1，則視作向量x在向量w上的投影 Fisher準(zhǔn)則的基本原理：找到一個(gè)最合適的投影方向，使兩類樣本在該方向上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。,Fisher線性判別圖例,Fisher判別,x1,x2,w1,H: g=0,w2,Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì) 均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。,d維空間樣本分布的描述量,Fisher判別,各類樣本均值向量mi,樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw,樣本類間離散度矩陣Sb：,離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個(gè)樣本在空間分布的離散程度,一維Y空間樣本分布的描述量,Fisher判別,各類樣本均值,樣本類內(nèi)離散度和總類內(nèi)離散度,樣本類間離散度,以上定義描述d維空間樣本點(diǎn)到一向量投影的分散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似,Fisher準(zhǔn)則函數(shù)定義的原則為，希望投影后，在一維空間中樣本類別區(qū)分清晰，即兩類距離越大越好，也就是類間離散度越大越好；各類樣本內(nèi)部密集，即類內(nèi)離散度越小越好，根據(jù)上述準(zhǔn)則，構(gòu)造Fisher準(zhǔn)則函數(shù)。,樣本與其投影統(tǒng)計(jì)量間的關(guān)系,Fisher判別,類內(nèi)離散度,Fisher準(zhǔn)則函數(shù),Fisher判別,評(píng)價(jià)投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開(kāi)，類內(nèi)盡可能密集的要求 Fisher準(zhǔn)則函數(shù)的定義：,Fisher最佳投影方向的求解,Fisher最佳投影方向的求解,Fisher判別,采用拉格朗日乘子算法解決,m1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開(kāi)，同時(shí)又使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)m1-m2 向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn),判別函數(shù)的確定,前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng)w0（閾值）可采用以下幾種方法確定：,分類規(guī)則:,Fisher判別,Fisher公式的推導(dǎo),Fisher判別,3.7 最小平方誤差算法,（least mean square error, LMSE；亦稱Ho-Kashyap算法）,上述的感知器算法、梯度算法、固定增量算法或其他類 似方法，只有當(dāng)模式類可分離時(shí)才收斂，在不可分的情況下， 算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂 時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：,a) 迭代過(guò)程本身收斂緩慢 b) 模式本身不可分,對(duì)可分模式收斂。 對(duì)于類別不可分的情況也能指出來(lái)。,LMSE算法特點(diǎn)：,1. 分類器的不等式方程,上式分開(kāi)寫為：,寫成矩陣形式為 ：,令N (n+1) 的長(zhǎng)方矩陣為X，則 , 變?yōu)椋?式中：,0為零向量,感知器算法是通過(guò)解不等式組 ，求出W。,2. LMSE算法,1) 原理,的求解。式中：, 兩式等價(jià)。,為各分量均為較小正值的矢量。,LMSE算法把對(duì)滿足 XW 0 的求解，改為滿足,準(zhǔn)則函數(shù)定義為：,“最小二乘”： 最?。菏狗匠探M兩邊誤差最小， 也即使J最小。 二乘：次數(shù)為2，乘了兩次,考察向量(XWB) 有：,可以看出： 當(dāng)函數(shù)J達(dá)到最小值，等式XW=B有最優(yōu)解。即又將問(wèn)題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問(wèn)題。 因?yàn)镴有兩個(gè)變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。,XW=B 的近似解也稱“最優(yōu)近似解”： 使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。,準(zhǔn)則函數(shù)：,使J 對(duì)W求最小，令 ，得：,2) 推導(dǎo)LMSE算法遞推公式,與問(wèn)題相關(guān)的兩個(gè)梯度：,(3-46),(3-47),由(3-47)式可知：只要求出B，就可求出W。,求遞推公式：,(1) 求W 的遞推關(guān)系,X為N(n+1)長(zhǎng)方陣，X#為(n+1) N 長(zhǎng)方陣。,稱為X的偽逆，,式中：,(3-45),(2) 求B(k+1)的迭代式,(3-46)代入，得,令,，定義,(3-49),(3-50),(3) 求W(k+1)的迭代式,將(3-50)代入(3-47)式W=X#B 有：,總結(jié)：設(shè)初值B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù) 。,W(k+1)、B(k+1)互相獨(dú)立，先后次序無(wú)關(guān)。,求出B，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B， W。,或另一算法：先算B(k+1)，再算W(k+1)。,3）模式類別可分性判別, 如果e(k)0 ，表明XW(k)B(k) 0， 隱含有解。繼續(xù)迭代， 可使e(k) 0 。, 如果e(k)0（所有分量為負(fù)數(shù)或零，但不全為零），停止迭 代，無(wú)解。此時(shí)若繼續(xù)迭代，數(shù)據(jù)不再發(fā)生變化。,可以證明：當(dāng)模式類線性可分，且校正系數(shù)c滿足 時(shí)，該算法收斂，可求得解W。,理論上不能證明該算法到底需要迭代多少步才能達(dá)到收 斂，通常在每次迭代計(jì)算后檢查一下XW(k) 和誤差向量e(k) ， 從而可以判斷是否收斂。, 如果e(k)=0 ，表明XW(k)=B(k) 0，有解。,分以下幾種情況：,情況分析：,e(k)0,綜上所述：只有當(dāng)e(k)中有大于零的分量時(shí)，才需要繼續(xù)迭 代，一旦e(k)的全部分量只有0和負(fù)數(shù)，則立即停止。事實(shí)上，往 往早在e(k)全部分量都達(dá)到非正值以前，就能看出其中有些分量 向正值變化得極慢，可及早采取對(duì)策。,通過(guò)反證法可以證明：在線性可分情況下，算法進(jìn)行過(guò)程中不會(huì)出現(xiàn) e(k)的分量全為負(fù)的情況；若出現(xiàn)e(k)的分量全為負(fù)，則說(shuō)明模式類線性不可分。,4) LMSE算法描述,(1) 根據(jù)N個(gè)分屬于兩類的樣本，寫出規(guī)范化增廣樣本矩陣X。,(2) 求X的偽逆矩陣 。,(3) 設(shè)置初值c和B(1)，c為正的校正增量，B(1)的各分量大于零， 迭代次數(shù)k=1 。開(kāi)始迭代：,計(jì)算,(4) 計(jì)算 ，進(jìn)行可分性判別。,如果e(k)0，線性可分，若進(jìn)入(5)可使e(k) 0 ，得最優(yōu)解。,如果e(k)0，線性不可分，停止迭代，無(wú)解，算法結(jié)束。,如果e(k)=0，線性可分，解為W(k)，算法結(jié)束。,否則，說(shuō)明e(k)的各分量值有正有負(fù)，進(jìn)入(5)。,(5) 計(jì)算W(k+1)和B(k+1)。,方法1：分別計(jì)算,方法2：先計(jì)算,再計(jì)算,迭代次數(shù)k加1，返回(4)。,3. 算法特點(diǎn),(1) 算法盡管略為復(fù)雜一些，但提供了線性可分的測(cè)試特征。,(2) 同時(shí)利用N個(gè)訓(xùn)練樣本，同時(shí)修改W和B，故收斂速度快。,(3) 計(jì)算矩陣 復(fù)雜，但可用迭代算法計(jì)算。,例3.11 已知兩類模式訓(xùn)練樣本：,試用LMSE算法求解權(quán)向量。,解：(1) 寫出規(guī)范化增廣樣本矩陣：,Aij是aij的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。,(2) 求偽逆矩陣,求逆矩陣：,劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij ，將 叫做元素aij的代數(shù)余子式。例：,代數(shù)余子式定義：,行列式:,(3) 取 和 c=1 開(kāi)始迭代：,解為 W(1) ，判斷函數(shù)為：,圖示如下：,例3.12 已知模式訓(xùn)練樣本： ，,( 2) 求 ：,解：(1) 規(guī)范化增廣樣本矩陣：,(3) 取 和c=1，迭代：,用LMSE算法求解權(quán)向量。,e(1)全部分量為負(fù)，無(wú)解，停止迭代。為線性不可分模式。,小結(jié)：,(1) 感知器法、梯度法、最小平方誤差算法討論的分類算法 都是通過(guò)模式樣本來(lái)確定判別函數(shù)的系數(shù)，所以要使一個(gè)分 類器設(shè)計(jì)完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的 權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。,(2) 要獲得一個(gè)有較好判別性能的線性分類器，所需要的訓(xùn) 練樣本的數(shù)目的確定。,用指標(biāo)二分法能力N0來(lái)確定訓(xùn)練樣本的數(shù)目：,通常訓(xùn)練樣本的數(shù)目不能低于N0 ，選為 N0的510倍左右。,二維：不能低于6個(gè)樣本，最好選在3060個(gè)樣本之間。 三維：不能低于8個(gè)樣本，最好選在4080個(gè)樣本之間。,n為模式維數(shù),如,3.8 非線性判別函數(shù),3.8.1 分段線性判別函數(shù),線性判別函數(shù)的特點(diǎn)：形式簡(jiǎn)單，容易學(xué)習(xí)； 用于線性可分的模式類。 非線性判別函數(shù)：用于線性不可分情況。分段線性、超曲面。,特點(diǎn),基本組成為超平面。,* 相對(duì)簡(jiǎn)單； * 能逼近各種 形狀的超曲面。,1一般分段線性判別函數(shù),設(shè)有M類模式，將i類（i=1,2, ,M）劃分為li個(gè)子類：,其中第n個(gè)子類的判別函數(shù)：,i類的判別函數(shù)定義為：,M類的判決規(guī)則：,用各類判別函數(shù)進(jìn)行分類判決實(shí)際是 用各類選出的子類判別函數(shù)進(jìn)行判決,判別面由各子類 的判別函數(shù)決定,若i類的第n個(gè)子類和j類的第m個(gè)子類相鄰，判別界面方程為：,子類之間的判別界面組 成各類之間的判別界面,類間判別界 面分段線性,2基于距離的分段線性判別函數(shù),設(shè) 1類均值向量：,2類均值向量：,N1，N2：兩類樣本數(shù)。,任一模式X到M1和M2的歐氏距離平方：,判決規(guī)則：,判別界面方程：,1）最小距離分類器,化簡(jiǎn)得：, X的線性方程，確定一個(gè)超平面。, 最小距離分類器,2）分段線性距離分類器,設(shè)：M類模式，其中i類劃分為li個(gè)子類，第n個(gè)子類的均值 向量為 。每個(gè)子類的判別函數(shù)：,每類的判別函數(shù)：,判決規(guī)則：,若,則,3.8.2 分段線性判別函數(shù)的學(xué)習(xí)方法,1已知子類劃分時(shí)的學(xué)習(xí)方法,* 每個(gè)子類看成獨(dú)立的類； * 在一類范圍內(nèi)根據(jù)多類情況3，學(xué)習(xí)各子類判別函數(shù)； * 繼而得到各類判別函數(shù)。,2已知子類數(shù)目時(shí)的學(xué)習(xí)方法,用類似于固定增量算法的錯(cuò)誤修正算法學(xué)習(xí)分段線性 判別函數(shù),3未知子類數(shù)目時(shí)的學(xué)習(xí)方法,樹(shù)狀分段線性分類器,樹(shù)狀分段線性分類器判別函數(shù)的學(xué)習(xí)及分類過(guò)程,暫停點(diǎn),：,，,；,：,，,3.8.3 勢(shì)函數(shù)法,1. 勢(shì)函數(shù)概念,劃分屬于1和2類模式樣本： 樣本是模式空間中的點(diǎn)， 將每個(gè)點(diǎn)比擬為點(diǎn)能源，在點(diǎn)上勢(shì)能達(dá)到峰值，隨著與 該點(diǎn)距離的增大，勢(shì)能分布迅速減小。 1類樣本勢(shì)能為正勢(shì)能積累形成 “高地”； 2類樣本勢(shì)能(-1)勢(shì)能積累形成 “凹地”； 在兩類電勢(shì)分布之間，選擇合適的等勢(shì)面（如零等勢(shì) 面），即可認(rèn)為是判別界面了。,借用點(diǎn)能源的勢(shì)能概念解決模式分類問(wèn)題。,一維情況示例,2. 勢(shì)函數(shù)法判別函數(shù)的產(chǎn)生,依次輸入樣本，利用勢(shì)函數(shù)逐步積累勢(shì)能的過(guò)程。,判別函數(shù)由模式空間中樣本向量 的勢(shì)函數(shù)K(X,