模式識別：感知器的實現 · 模式分類理論與方法

在之前的模式識別研究中，判別函數J(.)的參數是已知的，即假設概率密度函數的參數形式已知。本節不考慮概率密度函數的確切形式，使用非參數化的方法來求解判別函數。由于線性判別函數具有許多優良的特性，因此這里我們只考慮以下形式的判別函數：它們或者是**x**的各個分量的線性函數，或者是關于以**x**為自變量的某些函數的線性函數。在設計感知器之前，需要明確以下幾個基本概念： ##一、判別函數：是指由x的各個分量的線性組合而成的函數： ![這里寫圖片描述](http://img.blog.csdn.net/20150423013758528) 若樣本有c類，則存在c個判別函數，對具有![這里寫圖片描述](http://img.blog.csdn.net/20150429194019502)形式的判別函數的一個兩類線性分類器來說，要求實現以下判定規則： ![這里寫圖片描述](http://img.blog.csdn.net/20150423013919314) 方程g(x)=0定義了一個判定面，它把兩個類的點分開來，這個平面被稱為超平面，如下圖所示。 ![這里寫圖片描述](http://img.blog.csdn.net/20150429194018755) ##二、廣義線性判別函數線性判別函數g(x)又可寫成以下形式： ![這里寫圖片描述](http://img.blog.csdn.net/20150429194446184) 其中系數wi是權向量w的分量。通過加入另外的項（w的各對分量之間的乘積），得到二次判別函數： ![這里寫圖片描述](http://img.blog.csdn.net/20150429194657895) 因為![這里寫圖片描述](http://img.blog.csdn.net/20150429194806254)，不失一般性，可以假設![這里寫圖片描述](http://img.blog.csdn.net/20150429194714964)。這樣，二次判別函數擁有更多的系數來產生復雜的分隔面。此時g(x)=0定義的分隔面是一個二階曲面。若繼續加入更高次的項，就可以得到多項式判別函數，這可看作對某一判別函數g(x)做級數展開，然后取其截尾逼近，此時廣義線性判別函數可寫成： ![這里寫圖片描述](http://img.blog.csdn.net/20150429195040710) 或： ![這里寫圖片描述](http://img.blog.csdn.net/20150429194945379) 這里y通常被成為“增廣特征向量”(augmented feature vector)，類似的，a被稱為“增廣權向量”，分別可寫成： ![這里寫圖片描述](http://img.blog.csdn.net/20150429195130820) 這個從d維x空間到d+1維y空間的映射雖然在數學上幾乎沒有變化，但十分有用。雖然增加了一個常量，但在x空間上的所有樣本間距離在變換后保持不變，得到的y向量都在d維的自空間中，也就是x空間本身。通過這種映射，可以將尋找權向量w和權閾值w0的問題簡化為尋找一個簡單的權向量a。 ##三、樣本線性可分即在特征空間中可以用一個或多個線性分界面正確無誤地分開若干類樣本；對于兩類樣本點w1和w2，其樣本點集合表示為：![這里寫圖片描述](http://img.blog.csdn.net/20150423014224502)?，使用一個判別函數![這里寫圖片描述](http://img.blog.csdn.net/20150423014527700)來劃分w1和w2，需要用這些樣本集合來確定判別函數的權向量**a**，可采用增廣樣本向量**y**，即存在合適的增廣權向量**a**，使得： ![這里寫圖片描述](http://img.blog.csdn.net/20150423013321566) 則稱樣本是線性可分的。如下圖中第一個圖就是線性可分，而第二個圖則不可分。所有滿足條件的權向量稱為解向量。 ![這里寫圖片描述](http://img.blog.csdn.net/20150423015016628) ![這里寫圖片描述](http://img.blog.csdn.net/20150423014926202) 通常對解區限制：引入余量b，要求解向量滿足： ![這里寫圖片描述](http://img.blog.csdn.net/20150423020849518) 余量b的加入在一定程度上可防止優化算法收斂到解區的邊界。 ##四、感知器準則函數這里考慮構造線性不等式![這里寫圖片描述](http://img.blog.csdn.net/20150423015326864)?的準則函數的問題，令準則函數J(.)為： ![這里寫圖片描述](http://img.blog.csdn.net/20150423015720802) 其中Y是被權向量a錯分的樣本集。當且僅當JP(a*) = min JP(a) = 0 時，a*是解向量。這就是感知器（Perceptron）準則函數。 **1.基本的感知器設計** 感知器準則函數的最小化可以使用梯度下降迭代算法求解： ![這里寫圖片描述](http://img.blog.csdn.net/20150423021458927) 其中，k為迭代次數，η為調整的步長。即下一次迭代的權向量是把當前時刻的權向量向目標函數的負梯度方向調整一個修正量。 ![這里寫圖片描述](http://img.blog.csdn.net/20150423021156781) 即在每一步迭代時把錯分的樣本按照某個系數疊加到權向量上。這樣就得到了感知算法。 **2.批處理感知器算法** ![這里寫圖片描述](http://img.blog.csdn.net/20150429195256823) **3.固定增量感知器算法** 通常情況，一次將所有錯誤樣本進行修正不是效率最高的做法，更常用是每次只修正一個樣本或一批樣本的固定增量法： ![這里寫圖片描述](http://img.blog.csdn.net/20150429195352639) ##五、收斂性分析：只要訓練樣本集是線性可分的，對于任意的初值 a(1) ，經過有限次迭代運算，算法必定收斂。而當樣本線性不可分時，感知器算法無法收斂。 **總結**：感知器是最簡單可以“學習”的機器，是解決線性可分的最基本方法。也是很多復雜算法的基礎。感知器的算法的推廣有很多種，如帶裕量的變增量感知器、批處理裕量松弛算法、單樣本裕量松弛算法等等。以下是批處理感知器算法與固定增量感知器算法實現的MATLAB代碼，并給出四組數據以供測試： ~~~ % 批處理感知器算法 function BatchPerceptron(w1, w2) figure; plot(w1(:,1),w1(:,2),'ro'); hold on; grid on; plot(w2(:,1),w2(:,2),'b+'); % 對所有訓練樣本求增廣特征向量y one = ones(10,1); y1 = [one w1]; y2 = [one w2]; w12 = [y1; -y2]; % 增廣樣本規范化 y = zeros(size(w12,1),1); % 錯分樣本集y初始為零矩陣 % 初始化參數 a = [0 0 0]; % [0 0 0]; Eta = 1; time = 0; % 收斂步數 while any(y<=0) for i=1:size(y,1) y(i) = a * w12(i,:)'; end; a = a + sum(w12(find(y<=0),:));%修正向量a time = time + 1;%收斂步數 if (time >= 300) break; end end; if (time >= 300) disp('目標函數在規定的最大迭代次數內無法收斂'); disp(['批處理感知器算法的解矢量a為： ',num2str(a)]); else disp(['批處理感知器算法收斂時解矢量a為： ',num2str(a)]); disp(['批處理感知器算法收斂步數k為： ',num2str(time)]); end %找到樣本在坐標中的集中區域，以便于打印樣本坐標圖 xmin = min(min(w1(:,1)),min(w2(:,1))); xmax = max(max(w1(:,1)),max(w2(:,1))); xindex = xmin-1:(xmax-xmin)/100:xmax+1; yindex = -a(2)*xindex/a(3)-a(1)/a(3); plot(xindex,yindex); title('批處理感知器算法實現兩類數據的分類'); ~~~ ~~~ % 固定增量感知器算法 function FixedIncrementPerceptron(w1, w2) [n, d] = size(w1); figure; plot(w1(:,1),w1(:,2),'ro'); hold on; grid on; plot(w2(:,1),w2(:,2),'b+'); % 對所有訓練樣本求增廣特征向量y one = ones(10,1); y1 = [one w1]; y2 = [one w2]; w12 = [y1; -y2]; % 增廣樣本規范化 y = zeros(size(w12,1),1); % 錯分樣本集y初始為零矩陣 % 初始化參數 a = [0 0 0]; Eta = 1; % k = 0; time = 0; % 收斂的步數 yk = zeros(10,3); y = a * w12'; while sum(y<=0)>0 % for i=1:size(y,1) % y(i) = a * w12(i,:)'; % end; y = a * w12'; rej=[]; for i=1:2*n %這個循環計算a(K+1) = a(k) + sum {yj被錯誤分類} y(j) if y(i)<=0 a = a + w12(i,:); rej = [rej i]; end end % fprintf('after iter %d, a = %g, %g\n', time, a); % rej time = time + 1; if ((size(rej) == 0) | (time >= 300)) break; end end; if (time >= 300) disp('目標函數在規定的最大迭代次數內無法收斂'); disp(['固定增量感知器算法的解矢量a為： ',num2str(a)]); else disp(['固定增量感知器算法收斂時解矢量a為： ',num2str(a)]); disp(['固定增量感知器算法收斂步數kt為： ',num2str(time)]); end %找到樣本在坐標中的集中區域，以便于打印樣本坐標圖 xmin = min(min(w1(:,1)),min(w2(:,1))); xmax = max(max(w1(:,1)),max(w2(:,1))); xindex = xmin-1:(xmax-xmin)/100:xmax+1; % yindex = -a(2)*xindex/a(3)-a(1)/a(3); yindex = -a(2)*xindex/a(3) - a(1)/a(3); plot(xindex,yindex); title('固定增量感知器算法實現兩類數據的分類'); ~~~ ~~~ close all; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 感知器實驗 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% w1 = [ 0.1 1.1;... 6.8 7.1;... -3.5 -4.1;... 2.0 2.7;... 4.1 2.8;... 3.1 5.0;... -0.8 -1.3;... 0.9 1.2;... 5.0 6.4;... 3.9 4.0]; w2 = [ 7.1 4.2;... -1.4 -4.3;... 4.5 0.0;... 6.3 1.6;... 4.2 1.9;... 1.4 -3.2;... 2.4 -4.0;... 2.5 -6.1;... 8.4 3.7;... 4.1 -2.2]; w3 = [-3.0 -2.9;... 0.54 8.7;... 2.9 2.1;... -0.1 5.2;... -4.0 2.2;... -1.3 3.7;... -3.4 6.2;... -4.1 3.4;... -5.1 1.6;... 1.9 5.1]; w4 = [-2.0 -8.4;... -8.9 0.2;... -4.2 -7.7;... -8.5 -3.2;... -6.7 -4.0;... -0.5 -9.2;... -5.3 -6.7;... -8.7 -6.4;... -7.1 -9.7;... -8.0 -6.3]; BatchPerceptron(w1, w2); FixedIncrementPerceptron(w1, w3); ~~~