【正文】 1XTb = Xb。這里X= (XTX)1XT稱為X的偽逆，X是N*(n+1)階的長方陣。由上式可知，只要求出b即可求得w。利用梯度法可求得b的迭代公式為：根據(jù)上述約束條件，在每次迭代中，b(k)的全部分量只能是正值。由J的準則函數(shù)式，J也是正值，因此，當取校正增量C為正值時，為保證每次迭代中的b(k)都是正值，應使為非正值。在此條件下，準則函數(shù)J的微分為：該式滿足以下條件：若[Xw(k) – b(k)] 0，則若[Xw(k) – b(k)] 0，則由b的迭代式和微分，有：b(k+1) = b(k) + δb(k)δb(k) = C[Xw(k) – b(k) + | Xw(k) – b(k)|]將此式代入w=Xb，有：w(k+1) = Xb(k+1) = X[b(k) +δb(k)] = w(k) + Xδb(k)為簡化起見，令e(k) = Xw(k) – b(k)，可得HK算法的迭代式。設初值為b(1)，其每一分量均為正值，則：w(1) = Xb(1)。e(k) = Xw(k) – b(k)。w(k+1) = w(k) + X{C[Xw(k) – b(k) + |Xw(k) – b(k)|]}= w(k) + CX[e(k) + |e(k)|]。由于Xe(k) = X[Xw(k) – b(k)] = (XTX)1XT[Xw(k) – b(k)]= w(k) –Xb(k) = 0。因此w(k+1) = w(k) + CX|e(k)|。b(k+1) = b(k) + C[Xw(k) – b(k) + |Xw(k) – b(k)|]= b(k) + C[e(k) + |e(k)|]模式類別可分性的判別當不等式組Xw0有解時，該算法對收斂，可求得解w。(k)=0，Xw(k)=b(k)0，有解。(k)0，此時隱含的條件，有解。若繼續(xù)進行迭代，可使e(k)0。(k)的全部分量停止變?yōu)檎担ǖ皇侨繛榱悖砻髟撃Ｊ筋悇e線性不可分。因此，若e(k)沒有一個分量為正值，則b(k)不會再變化，所以不能求得解。小結(jié)：實現(xiàn)相對簡單，可直接引伸到多類模式的分類情況，但未提供模式線性可分的測試特征；：相對復雜，需要對XTX求逆（維數(shù)高時求逆比較困難），但對兩類情況，提供了線性可分的測試特征。 勢函數(shù)法 — 一種確定性的非線性分類方法目的：用勢函數(shù)的概念來確定判別函數(shù)和劃分類別界面?；舅枷爰僭O要劃分屬于兩種類別ω1和ω2的模式樣本，這些樣本可看成是分布在n維模式空間中的點xk。把屬于ω1的點比擬為某種能源點，在點上，電位達到峰值。隨著與該點距離的增大，電位分布迅速減小，即把樣本xk附近空間x點上的電位分布，看成是一個勢函數(shù)K(x, xk)。對于屬于ω1的樣本集群，其附近空間會形成一個“高地”，這些樣本點所處的位置就是“山頭”。同理，用電位的幾何分布來看待屬于ω2的模式樣本，在其附近空間就形成“凹地”。只要在兩類電位分布之間選擇合適的等高線，就可以認為是模式分類的判別函數(shù)。 判別函數(shù)的產(chǎn)生模式分類的判別函數(shù)可由分布在模式空間中的許多樣本向量{xk, k=1,2,…和 的勢函數(shù)產(chǎn)生。 任意一個樣本所產(chǎn)生的勢函數(shù)以K(x, xk)表征，則判別函數(shù)d(x)可由勢函數(shù)序列K(x, x1)， K(x, x2)，…來構(gòu)成，序列中的這些勢函數(shù)相應于在訓練過程中輸入機器的訓練模式樣本x1，x2，…。在訓練狀態(tài)，模式樣本逐個輸入分類器，分類器就連續(xù)計算相應的勢函數(shù)，在第k步迭代時的積累位勢決定于在該步前所有的單獨勢函數(shù)的累加。以K(x)表示積累位勢函數(shù)，若加入的訓練樣本xk+1是錯誤分類，則積累函數(shù)需要修改，若是正確分類，則不變。逐步分析設初始勢函數(shù)K0(x) = 0。第一步：加入第一個訓練樣本x1，則有。這里第一步積累勢函數(shù)K1(x)描述了加入第一個樣本時的邊界劃分。當樣本屬于ω1時，勢函數(shù)為正；當樣本屬于ω2時，勢函數(shù)為負。第二步：加入第二個訓練樣本x2，(x2)0，或且K1(x2)0，則分類正確，此時K2(x) = K1(x)，即積累勢函數(shù)不變。(x2)0，則 (x2)0，則以上3兩種情況屬于錯分。假如x2處于K1(x)定義的邊界的錯誤一側(cè)，則當時，積累位勢K2(x)要加K(x, x2)，當時，積累位勢K2(x)要減K(x, x2)。第K步：設Kk(x)為加入訓練樣本x1，x2，…，xk后的積累位勢，則加入第(k+1)個樣本時，Kk+1(x)決定如下：(xk+1)0，或且Kk(xk+1)0，則分類正確，此時Kk+1(x) = Kk(x)，即積累位勢不變。(xk+1)0，則 。(xk+1)0，則因此，積累位勢的迭代運算可寫成：，rk+1為校正系數(shù)：若從給定的訓練樣本集{x1, x2, …, xk, …}中去除不使積累位勢發(fā)生變化的樣本，即使Kj(xj+1)0且，或Kj(xj+1)0且的那些樣本，則可得一簡化的樣本序列，它們完全是校正錯誤的樣本。此時，上述迭代公式可歸納為：其中也就是說，由k+1個訓練樣本產(chǎn)生的積累位勢，等于ω1類和ω2類兩者中的校正錯誤樣本的總位勢之差。從勢函數(shù)可以看出，積累位勢起著判別函數(shù)的作用當xk+1屬于ω1時，Kk(xk+1)0；當xk+1屬于ω2時，Kk(xk+1)0，則積累位勢不做任何修改就可用作判別函數(shù)。由于一個模式樣本的錯誤分類可造成積累位勢在訓練時的變化，因此勢函數(shù)算法提供了確定ω1和ω2兩類判別函數(shù)的迭代過程。判別函數(shù)表達式：取d(x)=K(x)，則有：dk+1(x)= dk(x)+rk+1K(x, xk+1 ) 勢函數(shù)的選擇? 選擇勢函數(shù)的條件：一般來說，若兩個n維向量x和xk的函數(shù)K(x, xk)同時滿足下列三個條件，則可作為勢函數(shù)。– K(x, xk)= K(xk, x)，并且當且僅當x=xk時達到最大值；– 當向量x與xk的距離趨于無窮時，K(x, xk)趨于零；– K(x, xk)是光滑函數(shù)，且是x與xk之間距離的單調(diào)下降函數(shù)。構(gòu)成勢函數(shù)的兩種方式第一類勢函數(shù)：可用對稱的有限多項式展開，即：其中{}在模式定義域內(nèi)為正交函數(shù)集。將這類勢函數(shù)代入判別函數(shù)，有：得迭代關系：其中因此，積累位勢可寫成：，Ci可用迭代式求得。第二類勢函數(shù)：選擇雙變量x和xk的對稱函數(shù)作為勢函數(shù)，即K(x, xk) = K(xk, x)，并且它可展開成無窮級數(shù)，例如：(a) (b) ，α是正常數(shù)(c) 討論:用第二類勢函數(shù)，當訓練樣本維數(shù)和數(shù)目都較高時，需要計算和存儲的指數(shù)項較多。正因為勢函數(shù)由許多新項組成，因此有很強的分類能力。作業(yè): {(0 1)T, (0 1)T},ω2: {(1 0)T, (1 0)T} 求解以下模式的分類問題ω1: {(0 1)T, (0 1)T} ω2: {(1 0)T, (1 0)T} 決策樹簡介決策樹，或稱多級分類器，是模式識別中進行分類的一種有效方法，對于多類或多峰分布問題，這種方法尤為方便。利用樹分類器可以把一個復雜的多類別分類問題，轉(zhuǎn)化為若干個簡單的分類問題來解決。它不是企圖用一種算法、一個決策規(guī)則去把多個類別一次分開，而是采用分級的形式，使分類問題逐步得到解決。決策樹示意圖 一般來講，一個決策樹由一個根節(jié)點n1，一組非終止節(jié)點ni和一些終止節(jié)點tj組成，可對tj標以各種類別標簽，有時不同的終止節(jié)點上可以出現(xiàn)相同的類別標簽。如果用T表示決策樹，則一個決策樹T對應于特征空間的一種劃分，它把特征空間分成若干個區(qū)域，在每個區(qū)域中，某類的樣本占優(yōu)勢，因此可以標出該類樣本的類別標簽。決策樹的一種簡單形式是二叉樹，它是指除葉結(jié)點外，樹的每個節(jié)點僅分為兩個分支，即每個非終止節(jié)點ni都有且僅有兩個子節(jié)點nil和nir。二叉樹結(jié)構(gòu)分類器可以把一個復雜的多類別分類問題轉(zhuǎn)化為多級多個兩類問題來解決，在每個非終止節(jié)點ni都把樣本集分成左右兩個子集。分成的每一部分仍然可能包含多個類別的樣本，可以把每一部分再分成兩個子集，如此下去，直至分成的每一部分只包含同一類別的樣本，或某一類樣本占優(yōu)勢為止。二叉樹結(jié)構(gòu)分類器概念簡單、直觀、便于解釋，而且在各個節(jié)點上可以選擇不同的特征和采用不同的決策規(guī)則，因此設計方法靈活多樣，便于利用先驗知識來獲得一個較好的分類器。一個二叉決策樹的例子在此例中，每個節(jié)點只選擇一個特征，并給出相應的決策值。對于一個未知樣本x，只要從根節(jié)點到葉結(jié)點，順序把x的某個特征觀測值與相應的閾值相比較，就可做出決策，把x分到相應的分支，最后分到合適的類別中去。在設計一個決策樹時，主要應解決以下幾個問題：選擇一個合適的樹結(jié)構(gòu)，即合理安排樹的節(jié)點和分支；確定在每個非終止節(jié)點上要使用的特征；在每個非終止節(jié)點上選擇合適的決策規(guī)則。上述三個問題解決了，決策樹的設計也就完成了。二叉樹的設計也不例外。把一個多類別分類問題轉(zhuǎn)化為兩類問題的形式是多種多樣的，因此，對應的二叉樹的結(jié)構(gòu)也是各不相同的。通常的目的是要找一個最優(yōu)的決策樹。一個性能良好的決策樹結(jié)構(gòu)應該具有小的錯誤率和低的決策代價。但是由于很難把錯誤率的解析表達式和樹的結(jié)構(gòu)聯(lián)系起來，而且在每個節(jié)點上所采用的決策規(guī)則也僅僅是在該節(jié)點上所采用的特征觀測值的函數(shù)，因此，即使每個節(jié)點上的性能都達到最優(yōu)，也不能說整個決策樹的性能達到最優(yōu)。在實際問題中，人們往往提出其它一些優(yōu)化準則，例如極小化整個樹的節(jié)點數(shù)目，或從根節(jié)點到葉結(jié)點的最大路經(jīng)長度，或從根節(jié)點到葉結(jié)點的平均路經(jīng)長度等，然后采用動態(tài)規(guī)劃的方法，力爭設計出能滿足某種準則的“最優(yōu)”決策樹。25