武漢大學(xué)-模式識(shí)別-第三章-判別函數(shù)精編版

1、 第三章 判別函數(shù) 3.1 線性判別函數(shù) 3.2 廣義線性判別函數(shù) 3.3 分段線性判別函數(shù) 3.4 模式空間和權(quán)空間 3.5 Fisher線性判別 3.6 感知器算法 3.7 采用感知器算法的多類模式的分類 3.8 可訓(xùn)練的確定性分類器的迭代算法 3.9 勢(shì)函數(shù)法 一種確定性的非線性分類算法 3.10 決策樹簡(jiǎn)介 3.1 線性判別函數(shù) 3.1.1 用判別函數(shù)分類的概念 模式識(shí)別系統(tǒng)的主要作用 判別各個(gè)模式所屬的類別 對(duì)一個(gè)兩類問(wèn)題的判別，就是將模式x 劃分成1和2兩類。 3.1 線性判別函數(shù) 3.1.1 用判別函數(shù)分類的概念 描述：兩類問(wèn)題的判別函數(shù) 3.1 線性判別函數(shù) 3.1.1 用判別

2、函數(shù)分類的概念 用判別函數(shù)進(jìn)行模式分類依賴的兩個(gè)因素 （1）判別函數(shù)的幾何性質(zhì)：線性的和非線性的函數(shù)。 線性的是一條直線； 非線性的可以是曲線、折線等； 線性判別函數(shù)建立起來(lái)比較簡(jiǎn)單（實(shí)際應(yīng)用較多）； 非線性判別函數(shù)建立起來(lái)比較復(fù)雜。 （2）判別函數(shù)的系數(shù)：判別函數(shù)的形式確定后，主 要就是確定判別函數(shù)的系數(shù)問(wèn)題。 只要被研究的模式是可分的，就能用給定的模式樣本 集來(lái)確定判別函數(shù)的系數(shù)。 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) n維線性判別函數(shù)的一般形式 權(quán)向量 增廣模式向量 增廣權(quán)向量 分類問(wèn)題 兩類情況：判別函數(shù)d(x) 多類情況：設(shè)模式可分成1, 2, M共M類，則 有三種劃分方法

3、 多類情況1 多類情況2 多類情況3 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) 分類問(wèn)題 多類情況1 判別函數(shù) 圖例 例子 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) 分類問(wèn)題 多類情況2 判別函數(shù) 圖例 例子 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) 分類問(wèn)題 多類情況3 判別函數(shù) 圖例 例子 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) 小結(jié)：線性可分 模式分類若可用任一個(gè)線性函數(shù)來(lái)劃分， 則這些模式就稱為線性可分的，否則就是 非線性可分的。 一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù) 就可用作模式分類的基礎(chǔ)。 3.1 線性判別函數(shù) 3.1.2 線性判別函數(shù) 多類情況1和多類

4、情況2的比較 對(duì)于M類模式的分類，多類情況1需要M個(gè)判別函 數(shù)，而多類情況2需要M*(M-1)/2個(gè)判別函數(shù)，當(dāng)M 較大時(shí)，后者需要更多的判別式（這是多類情況2 的一個(gè)缺點(diǎn)）。 采用多類情況1時(shí)，每一個(gè)判別函數(shù)都要把一種類 別的模式與其余M-1種類別的模式分開(kāi)，而不是將 一種類別的模式僅于另一種類別的模式分開(kāi)。 由于一種模式的分布要比M-1種模式的分布更為聚 集，因此多類情況2對(duì)模式是線性可分的可能性比 多類情況1更大一些（這是多類情況2的一個(gè)優(yōu)點(diǎn)）。 作業(yè)（1） 在一個(gè)10類的模式識(shí)別問(wèn)題中，有3類 單獨(dú)滿足多類情況1，其余的類別滿足 多類情況2。問(wèn)該模式識(shí)別問(wèn)題所需判 別函數(shù)的最少數(shù)目是多

5、少？ 作業(yè)（2） 一個(gè)三類問(wèn)題，其判別函數(shù)如下： d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1 設(shè)這些函數(shù)是在多類情況1條件下確定的， 繪出其判別界面和每一個(gè)模式類別的區(qū)域。 設(shè)為多類情況2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。繪出其判別界 面和多類情況2的區(qū)域。 設(shè)d1(x), d2(x)和d3(x)是在多類情況3的條件 下確定的，繪出其判別界面和每類的區(qū)域。 3.2 廣義線性判別函數(shù) 出發(fā)點(diǎn) 線性判別函數(shù)簡(jiǎn)單，容易實(shí)現(xiàn)； 非線性判別函數(shù)復(fù)雜，不容易實(shí)現(xiàn)； 若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函 數(shù)，則

6、有利于模式分類的實(shí)現(xiàn)。 3.2 廣義線性判別函數(shù) 基本思想 設(shè)有一個(gè)訓(xùn)練用的模式集x，在模式空間x中 線性不可分，但在模式空間x*中線性可分，其 中x*的各個(gè)分量是x的單值實(shí)函數(shù)，x*的維數(shù)k 高于x的維數(shù)n，即若取 x* = (f1(x), f2(x), ., fk(x), kn 則分類界面在x*中是線性的，在x中是非線性 的，此時(shí)只要將模式x進(jìn)行非線性變換，使之 變換后得到維數(shù)更高的模式x*，就可以用線性 判別函數(shù)來(lái)進(jìn)行分類。 描述 3.2 廣義線性判別函數(shù) 廣義線性判別函數(shù)的意義 線性的判別函數(shù) fi(x)選用二次多項(xiàng)式函數(shù) x是二維的情況 x是n維的情況 fi(x)選用r次多項(xiàng)式函數(shù)，

7、 x是n維的情況 例子 d(x)的總項(xiàng)數(shù) 說(shuō)明 d(x)的項(xiàng)數(shù)隨r和n的增加會(huì)迅速增大，即使原來(lái)模式x的維 數(shù)不高，若采用次數(shù)r較高的多項(xiàng)式來(lái)變換，也會(huì)使變換后 的模式x*的維數(shù)很高，給分類帶來(lái)很大困難。 實(shí)際情況可只取r=2，或只選多項(xiàng)式的一部分，例如r=2時(shí) 只取二次項(xiàng)，略去一次項(xiàng)，以減少x*的維數(shù)。 3.2 廣義線性判別函數(shù) 例子：一維樣本空間 -二維樣本空間 作業(yè) 兩類模式，每類包括5個(gè)3維不同的模式， 且良好分布。如果它們是線性可分的， 問(wèn)權(quán)向量至少需要幾個(gè)系數(shù)分量？假如 要建立二次的多項(xiàng)式判別函數(shù)，又至少 需要幾個(gè)系數(shù)分量？（設(shè)模式的良好分 布不因模式變化而改變。） 3.3 分段線

8、性判別函數(shù) 出發(fā)點(diǎn) 線性判別函數(shù)在進(jìn)行分類決策時(shí)是最簡(jiǎn)單有效的， 但在實(shí)際應(yīng)用中，常常會(huì)出現(xiàn)不能用線性判別函數(shù) 直接進(jìn)行分類的情況。 采用廣義線性判別函數(shù)的概念，可以通過(guò)增加維數(shù) 來(lái)得到線性判別，但維數(shù)的大量增加會(huì)使在低維空 間里在解析和計(jì)算上行得通的方法在高維空間遇到 困難，增加計(jì)算的復(fù)雜性。 引入分段線性判別函數(shù)的判別過(guò)程，它比一般的線 性判別函數(shù)的錯(cuò)誤率小，但又比非線性判別函數(shù)簡(jiǎn) 單。 3.3 分段線性判別函數(shù) 圖例：用判別函數(shù)分類 可用一個(gè)二次判別函數(shù)來(lái)分類 也可用一個(gè)分段線性判別函數(shù)來(lái)逼近這個(gè) 二次曲線 3.3 分段線性判別函數(shù) 分段線性判別函數(shù)的設(shè)計(jì) 采用最小距離分類的方法 最小距

9、離分類 3.3 分段線性判別函數(shù) 圖例：分段線性分類設(shè)計(jì) 3.4 模式空間和權(quán)空間 分類描述 模式空間 對(duì)一個(gè)線性方程w1x1+w2x2+w3x3=0，它在三 維空間(x1 x2 x3)中是一個(gè)平面方程式， w=(w1 w2 w3)T是方程的系數(shù)。 把w向量作為該平面的法線向量，則該線性 方程決定的平面通過(guò)原點(diǎn)且與w垂直。 3.4 模式空間和權(quán)空間 模式空間 若x是二維的增廣向量，此時(shí)x3=1，則在非增廣的 模式空間中即為x1, x2 二維坐標(biāo)，判別函數(shù)是下 列聯(lián)立方程的解 w1x1+w2x2+w3=0 x3=1 即為這兩個(gè)平面相交的直線AB 此時(shí)，w =(w1 w2)T為非增廣的權(quán)向量，它與

10、直線 AB垂直；AB將平面分為正、負(fù)兩側(cè)，w離開(kāi)直線 的一側(cè)為正， w射向直線的一側(cè)為負(fù)。 3.4 模式空間和權(quán)空間 模式空間 增廣向量決定的平面 (a) 非增廣向量決定的直線 3.4 模式空間和權(quán)空間 權(quán)空間 若將方程x1w1+x2w2+w3=0繪在權(quán)向量w=(w1 w2 w3)T 的三維空間中，則x=(x1 x2 1)T為方程的系數(shù)。 若以x向量作為法線向量，則該線性方程所決定的 平面為通過(guò)原點(diǎn)且與法線向量垂直的平面，它同樣 將權(quán)空間劃分為正、負(fù)兩邊。 在系數(shù)x不變的條件下，若w值落在法線向量離開(kāi) 平面的一邊，則wTx0，若w值落在法線向量射向 平面的一邊，則wTx 0。 3.4 模式空間

11、和權(quán)空間 權(quán)空間中判別界面的平面示意圖 3.5 Fisher線性判別 出發(fā)點(diǎn) 應(yīng)用統(tǒng)計(jì)方法解決模式識(shí)別問(wèn)題時(shí)，一再 碰到的問(wèn)題之一就是維數(shù)問(wèn)題。 在低維空間里解析上或計(jì)算上行得通的方 法，在高維空間里往往行不通。 因此，降低維數(shù)有時(shí)就會(huì)成為處理實(shí)際問(wèn) 題的關(guān)鍵。 3.5 Fisher線性判別 問(wèn)題描述 考慮把d維空間的樣本投影到一條直線上，形成一 維空間，即把維數(shù)壓縮到一維。 然而，即使樣本在d維空間里形成若干緊湊的互相 分得開(kāi)的集群，當(dāng)把它們投影到一條直線上時(shí)， 也可能會(huì)是幾類樣本混在一起而變得無(wú)法識(shí)別。 但是，在一般情況下，總可以找到某個(gè)方向，使 在這個(gè)方向的直線上，樣本的投影能分得開(kāi)。

12、3.5 Fisher線性判別 問(wèn)題描述 問(wèn)題：如何根據(jù)實(shí)際情況找到一條最好的、 最易于分類的投影線，這就是Fisher判別方 法所要解決的基本問(wèn)題。 3.5 Fisher線性判別 從d維空間到一維空間的一般數(shù)學(xué)變換 方法 假設(shè)有一集合包含N個(gè)d維樣本x1, x2, , xN，其中N1個(gè)屬于1類的樣本記為子集1， N2個(gè)屬于2類的樣本記為子集2 。若對(duì)xn 的分量做線性組合可得標(biāo)量： yn = wTxn, n=1,2,N 這樣便得到N個(gè)一維樣本yn組成的集合，并 可分為兩個(gè)子集1和2 。 3.5 Fisher線性判別 從d維空間到一維空間的一般數(shù)學(xué)變換 方法 實(shí)際上，w的值是無(wú)關(guān)緊要的，它僅是y

13、n乘 上一個(gè)比例因子，重要的是選擇w的方向。 w的方向不同，將使樣本投影后的可分離程 度不同，從而直接影響的分類效果。 因此，上述尋找最佳投影方向的問(wèn)題，在 數(shù)學(xué)上就是尋找最好的變換向量w*的問(wèn)題。 3.5 Fisher線性判別 Fisher準(zhǔn)則函數(shù)的定義 幾個(gè)必要的基本參量 我們希望投影后，在一維Y空間中各類樣本 盡可能分得開(kāi)些，即希望兩類均值之差越 大越好，同時(shí)希望各類樣本內(nèi)部盡量密集， 即希望類內(nèi)離散度越小越好。 Fisher準(zhǔn)則函數(shù)定義 最佳變換向量w*的求取 3.5 Fisher線性判別 基于最佳變換向量w*的投影 w*是使Fisher準(zhǔn)則函數(shù)JF(w)取極大值時(shí)的解，也就 是d維X

14、空間到一維Y空間的最佳投影方向。有了 w*，就可以把d維樣本x投影到一維，這實(shí)際上是 多維空間到一維空間的一種映射，這個(gè)一維空間 的方向w*相對(duì)于Fisher準(zhǔn)則函數(shù)JF(w)是最好的。 利用Fisher準(zhǔn)則，就可以將d維分類問(wèn)題轉(zhuǎn)化為一 維分類問(wèn)題，然后，只要確定一個(gè)閾值T，將投影 點(diǎn)yn與T相比較，即可進(jìn)行分類判別。 3.6 感知器算法 出發(fā)點(diǎn) 一旦判別函數(shù)的形式確定下來(lái)，不管它是 線性的還是非線性的，剩下的問(wèn)題就是如 何確定它的系數(shù)。 在模式識(shí)別中，系數(shù)確定的一個(gè)主要方法 就是通過(guò)對(duì)已知樣本的訓(xùn)練和學(xué)習(xí)來(lái)得到。 感知器算法就是通過(guò)訓(xùn)練樣本模式的迭代 和學(xué)習(xí)，產(chǎn)生線性（或廣義線性）可分的

15、模式判別函數(shù)。 3.6 感知器算法 基本思想 采用感知器算法(Perception Approach)能通 過(guò)對(duì)訓(xùn)練模式樣本集的“學(xué)習(xí)”得到判別 函數(shù)的系數(shù)。 說(shuō)明 這里采用的算法不需要對(duì)各類別中模式的 統(tǒng)計(jì)性質(zhì)做任何假設(shè)，因此稱為確定性的 方法。 3.6 感知器算法 背景 “感知器”一詞出自于20世紀(jì)50年代中期 到60年代中期人們對(duì)一種分類學(xué)習(xí)機(jī)模型 的稱呼，它是屬于有關(guān)動(dòng)物和機(jī)器學(xué)習(xí)的 仿生學(xué)領(lǐng)域中的問(wèn)題。 當(dāng)時(shí)的一些研究者認(rèn)為感知器是一種學(xué)習(xí) 機(jī)的強(qiáng)有力模型，后來(lái)發(fā)現(xiàn)估計(jì)過(guò)高了， 但發(fā)展感知器的一些相關(guān)概念仍然沿用下 來(lái)。 3.6 感知器算法 感知器的訓(xùn)練算法 感知器算法實(shí)質(zhì)上是一種賞

16、罰過(guò)程 對(duì)正確分類的模式則“賞”，實(shí)際上是“不罰” ，即權(quán)向量不變。 對(duì)錯(cuò)誤分類的模式則“罰”，使w(k)加上一個(gè)正 比于xk的分量。 當(dāng)用全部模式樣本訓(xùn)練過(guò)一輪以后，只要有一個(gè) 模式是判別錯(cuò)誤的，則需要進(jìn)行下一輪迭代，即 用全部模式樣本再訓(xùn)練一次。 如此不斷反復(fù)直到全部模式樣本進(jìn)行訓(xùn)練都能得 到正確的分類結(jié)果為止。 3.6 感知器算法 例子 感知器算法的收斂性 只要模式類別是線性可分的，就可以在有限的迭 代步數(shù)里求出權(quán)向量。（證明作為練習(xí)） 作業(yè)及編程 用感知器算法求下列模式分類的解向 量w: 1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T 2: (0 0

17、 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T 編寫求解上述問(wèn)題的感知器算法程序。 3.7 采用感知器算法的 多類模式的分類 采用3.1的多類情況3，將感知器算法 推廣到多類模式。 感知器算法判別函數(shù)的推導(dǎo) 例子 3.7 采用感知器算法的 多類模式的分類 討論 這里的分類算法都是通過(guò)模式樣本來(lái)確 定判別函數(shù)的系數(shù)，但一個(gè)分類器的判 斷性能最終要受并未用于訓(xùn)練的那些未 知樣本來(lái)檢驗(yàn)。 要使一個(gè)分類器設(shè)計(jì)完善，必須采用有 代表性的訓(xùn)練數(shù)據(jù)，它能夠合理反映模 式數(shù)據(jù)的整體。 3.7 采用感知器算法的 多類模式的分類 討論 要獲得一個(gè)判別性能好的線性分類器， 究竟需要多少訓(xùn)練樣本

18、？ 直觀上是越多越好，但實(shí)際上能收集到的樣 本數(shù)目會(huì)受到客觀條件的限制； 過(guò)多的訓(xùn)練樣本在訓(xùn)練階段會(huì)使計(jì)算機(jī)需要 較長(zhǎng)的運(yùn)算時(shí)間； 一般來(lái)說(shuō)，合適的樣本數(shù)目可如下估計(jì)： 若k是模式的維數(shù)，令C=2(k+1)，則通常選 用的訓(xùn)練樣本數(shù)目約為C的1020倍。 作業(yè) 用多類感知器算法求下列模式的判別函 數(shù)： 1: (-1 -1)T 2: (0 0)T 3: (1 1)T 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.1 梯度法 定義 梯度是一個(gè)向量，它的最重要性質(zhì)就是指 出了函數(shù)f在其自變量y增加時(shí)最大增長(zhǎng)率 的方向。 負(fù)梯度指出f的最陡下降方向 利用這個(gè)性質(zhì)，可以設(shè)計(jì)一個(gè)迭代方案來(lái) 尋找函數(shù)的

19、最小值。 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.1 梯度法 采用梯度法求解的基本思想 對(duì)感知器算法 式中的w(k)、xk隨迭代次數(shù)k而變，是變量。 定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J(w, x)。先任 選一個(gè)初始權(quán)向量w(1)，計(jì)算準(zhǔn)則函數(shù)J的梯度， 然后從w(1)出發(fā)，在最陡方向（梯度方向）上移動(dòng) 某一距離得到下一個(gè)權(quán)向量w(2) 。 從w(k)導(dǎo)出w(k+1)的一般關(guān)系式 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.1 梯度法 討論 若正確地選擇了準(zhǔn)則函數(shù)J(w,x)，則當(dāng)權(quán)向量w是 一個(gè)解時(shí)，J達(dá)到極小值（J的梯度為零）。由于 權(quán)向量是按J的梯度值減小，因此這種方法稱為

20、 梯度法（最速下降法）。 為了使權(quán)向量能較快地收斂于一個(gè)使函數(shù)J極小 的解，C值的選擇是很重要的。 若C值太小，則收斂太慢； 若C值太大，則搜索可能過(guò)頭，引起發(fā)散。 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.1 梯度法 例子 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.2 固定增量的逐次調(diào)整算法 描述 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.2 固定增量的逐次調(diào)整算法 過(guò)程說(shuō)明： 設(shè)已由前一步迭代得到w(k)的值。 讀入模式樣本xk，判別wT(k)xk是否大于0。在示意 圖中，xk界定的判別界面為wT(k)xk=0。當(dāng)w(k)在 判別界面的負(fù)區(qū)域時(shí)， wT(k)xk0，

21、試導(dǎo)出兩類模式的分類 算法。 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.3 最小平方誤差(LMSE)算法 出發(fā)點(diǎn) 感知器算法只是當(dāng)被分模式可用一個(gè)特定的判別界面分 開(kāi)時(shí)才收斂，在不可分情況下，只要計(jì)算程序不終止， 它就始終不收斂。 即使在模式可分的情況下，也很難事先算出達(dá)到收斂時(shí) 所需要的迭代次數(shù)。 這樣，在模式分類過(guò)程中，有時(shí)候會(huì)出現(xiàn)一次又一次迭 代卻不見(jiàn)收斂的情況，白白浪費(fèi)時(shí)間。 為此需要知道：發(fā)生遲遲不見(jiàn)收斂的情況時(shí)，到底是由 于收斂速度過(guò)慢造成的呢，還是由于所給的訓(xùn)練樣本集 不是線性可分造成的呢？ 最小平方誤差(LMSE)算法，除了對(duì)可分模式是收斂的以 外，對(duì)于類別不可分的情況

22、也能指出來(lái)。 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.3 最小平方誤差(LMSE)算法 分類器的不等式方程 Ho-Kashyap(H-K)算法 模式類別可分性的判別 例1：有解情況 例2：無(wú)解情況 3.8 可訓(xùn)練的確定性分類器的 迭代算法 3.8.3 最小平方誤差(LMSE)算法 小結(jié) 固定增量算法：實(shí)現(xiàn)相對(duì)簡(jiǎn)單，可直接 引伸到多類模式的分類情況，但未提供 模式線性可分的測(cè)試特征； LMSE算法：相對(duì)復(fù)雜，需要對(duì)XTX求逆 （維數(shù)高時(shí)求逆比較困難），但對(duì)兩類 情況，提供了線性可分的測(cè)試特征。 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 目的 用勢(shì)函數(shù)的概念來(lái)確定判別函數(shù)和劃分類別

23、界面。 基本思想 假設(shè)要?jiǎng)澐謱儆趦煞N類別1和2的模式樣本，這些樣本可看 成是分布在n維模式空間中的點(diǎn)xk。 把屬于1的點(diǎn)比擬為某種能源點(diǎn)，在點(diǎn)上，電位達(dá)到峰值。 隨著與該點(diǎn)距離的增大，電位分布迅速減小，即把樣本xk附 近空間x點(diǎn)上的電位分布，看成是一個(gè)勢(shì)函數(shù)K(x, xk)。 對(duì)于屬于1的樣本集群，其附近空間會(huì)形成一個(gè)“高地”， 這些樣本點(diǎn)所處的位置就是“山頭”。 同理，用電位的幾何分布來(lái)看待屬于2的模式樣本，在其附 近空間就形成“凹地”。 只要在兩類電位分布之間選擇合適的等高線，就可以認(rèn)為是 模式分類的判別函數(shù)。 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.1 判別函數(shù)的產(chǎn)生 模

24、式分類的判別函數(shù)可由分布在模式空間中的許多樣 本向量xk, k=1,2,和 的勢(shì)函數(shù)產(chǎn)生。 任意一個(gè)樣本所產(chǎn)生的勢(shì)函數(shù)以K(x, xk)表征，則判別 函數(shù)d(x)可由勢(shì)函數(shù)序列K(x, x1)， K(x, x2)，來(lái)構(gòu) 成，序列中的這些勢(shì)函數(shù)相應(yīng)于在訓(xùn)練過(guò)程中輸入機(jī) 器的訓(xùn)練模式樣本x1，x2，。 在訓(xùn)練狀態(tài)，模式樣本逐個(gè)輸入分類器，分類器就連 續(xù)計(jì)算相應(yīng)的勢(shì)函數(shù)，在第k步迭代時(shí)的積累位勢(shì)決 定于在該步前所有的單獨(dú)勢(shì)函數(shù)的累加。 以K(x)表示積累位勢(shì)函數(shù)，若加入的訓(xùn)練樣本xk+1是 錯(cuò)誤分類，則積累函數(shù)需要修改，若是正確分類，則 不變。 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9

25、.1 判別函數(shù)的產(chǎn)生 逐步分析 從勢(shì)函數(shù)可以看出，積累位勢(shì)起著判別函數(shù) 的作用 當(dāng)xk+1屬于1時(shí)，Kk(xk+1)0；當(dāng)xk+1屬于2時(shí)， Kk(xk+1)0，則積累位勢(shì)不做任何修改就可用作判 別函數(shù)。 由于一個(gè)模式樣本的錯(cuò)誤分類可造成積累位 勢(shì)在訓(xùn)練時(shí)的變化，因此勢(shì)函數(shù)算法提供了 確定1和2兩類判別函數(shù)的迭代過(guò)程。 判別函數(shù)表達(dá)式 取d(x)=K(x)，則有：dk+1(x)= dk(x)+rk+1K(x, xk+1 ) 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.2 勢(shì)函數(shù)的選擇 選擇勢(shì)函數(shù)的條件：一般來(lái)說(shuō)，若兩個(gè) n維向量x和xk的函數(shù)K(x, xk)同時(shí)滿足下列三 個(gè)條件，

26、則可作為勢(shì)函數(shù)。 K(x, xk)= K(xk, x)，并且當(dāng)且僅當(dāng)x=xk時(shí)達(dá)到最大 值； 當(dāng)向量x與xk的距離趨于無(wú)窮時(shí)，K(x, xk)趨于零； K(x, xk)是光滑函數(shù)，且是x與xk之間距離的單調(diào)下 降函數(shù)。 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.2 勢(shì)函數(shù)的選擇 構(gòu)成勢(shì)函數(shù)的兩種方式 第一類勢(shì)函數(shù) 第二類勢(shì)函數(shù) 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.2 勢(shì)函數(shù)的選擇 例1 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.2 勢(shì)函數(shù)的選擇 例2 3.9 勢(shì)函數(shù)法 一種確 定性的非線性分類方法 3.9.2 勢(shì)函數(shù)的選擇 討論 用第二類勢(shì)函數(shù)，

27、當(dāng)訓(xùn)練樣本維數(shù)和數(shù) 目都較高時(shí)，需要計(jì)算和存儲(chǔ)的指數(shù)項(xiàng) 較多。 正因?yàn)閯?shì)函數(shù)由許多新項(xiàng)組成，因此有 很強(qiáng)的分類能力。 作業(yè)（1） 用二次埃爾米特多項(xiàng)式的勢(shì)函數(shù)算法求 解以下模式的分類問(wèn)題 1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T 作業(yè)（2） 用下列勢(shì)函數(shù) 求解以下模式的分類問(wèn)題 1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T 3.10 決策樹簡(jiǎn)介 決策樹，或稱多級(jí)分類器，是模式識(shí)別中進(jìn) 行分類的一種有效方法，對(duì)于多類或多峰分 布問(wèn)題，這種方法尤為方便。 利用樹分類器可以把一個(gè)復(fù)雜的多類別分類 問(wèn)題，轉(zhuǎn)化為若干個(gè)簡(jiǎn)單的分類問(wèn)題來(lái)解決。 它不是企圖用一種算法、一個(gè)決策規(guī)則去把 多個(gè)類別一次分開(kāi)，而是采用分級(jí)的形式， 使分類問(wèn)題逐步得到解決。 3.10 決策樹簡(jiǎn)介 決策樹示意圖 3.10 決策樹簡(jiǎn)介 一般來(lái)講，一個(gè)決策樹由一個(gè)根節(jié)點(diǎn)n1，一組 非終止節(jié)點(diǎn)ni和一些終止節(jié)點(diǎn)tj組成，可對(duì)tj標(biāo) 以各種類別標(biāo)簽，有時(shí)不同的終止節(jié)點(diǎn)上可 以出現(xiàn)相同的類別標(biāo)簽。 如果用T表示決策樹，則一個(gè)決策樹T對(duì)應(yīng)于 特征空間的一種劃分，它把特征空間分成若 干個(gè)區(qū)域，在每個(gè)區(qū)域中，某類的樣本占優(yōu) 勢(shì)，因此可以標(biāo)出該類樣本的類別標(biāo)簽。 3.10 決策樹簡(jiǎn)介 決策樹的一種