[發明專利]基于小生境粒子群優化算法的分類器集成的多層選擇方法

無效

• 申請號: 200710193876.2
• 申請日: 2007-11-30
• 公開（公告）號: CN101187944A
• 公開（公告）日: 2008-05-28
• 發明（設計）人: 黃德雙;章軍
• 申請（專利權）人: 中國科學院合肥物質科學研究院
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F15/18
• 代理公司: 安徽省合肥新安專利代理有限責任公司
• 代理人: 趙曉薇

1.一種基于小生境粒子群優化算法的分類器集成的多層選擇方法，其特征是：

(1)對基分類器構建一個二值輸出向量(Oracle?Output)

設共有L個分類器參加集成，D＝{D₁，….D_L}，y_i＝[y_i1，….，y_iL]^T為L個分類器對輸入樣本x_i的識別輸出。每個分類器均為標簽分類器，其中y_ij是指第j個分類器對第i個訓練樣本的識別輸出。每個分類器輸出中能夠正確識別該樣本，則對應的y_ij＝0，不能正確識別，則對應y_ij＝1，通過這種方式，構成了一個分類器多層選擇模型的基礎。

(2)制定集成選擇標準

在集成選擇中，選擇標準是非常重要的。在實際應用中，最常用的選擇標準即基于驗證集的大多數投票錯誤(majority?voting?error，MVE)。在本專利中，所有的輸出都是基于前一層中的二值輸出向量的。對于本專利所提出的多層集成選擇模型，如果提供足夠多和差異度大的二值輸出(oracle?output)，則很可能會出現過擬合現象。因此，本專利提出了一種新的選擇標準，使用的是平均大多數投票錯誤率的計算不僅根據驗證集，而且根據訓練集，它主要希望訓練集和驗證之間的誤差盡可能是接近。因而能最大可能減小系統的泛化錯誤。

(3)集成的選擇表示方法

在多層集成選擇模型中，每一個集成可以通過發現一個選擇向量(pruning?vector)來表示對應的選擇結果，假定H_i＝[h_i1，……，h_iL]^T為第i層的選擇向量，其中h_ij表示對應的第j個分類器或二值輸出是否被加入到集成中，當h_ij＝1時表示對應的輸出或分類器被包括在集成中，如果為零則將該分類器或輸出排除在集成之外。因此，在多層集成選擇模型中，對每一個集成需要發現這樣一個合適的二值向量以選擇對應的分類器或輸出。在這里，使用小生境粒子群優化算法來發現這樣的二值向量。

(4)小生境粒子群優化算法

使用一種多子群并行小生境PSO算法，算法能夠有效地模擬一個自然的生態系統，其中不同的子群之間互相競爭。在競爭以后，勝利者將繼續探索原來的區域(小生境)，而失敗者將被迫探索其他的區域(小生境)。在算法中，具體的實現是通過小生境識別技術來判斷探索中的兩點是否位于同一小生境，其他子群中粒子進入勝利者所擁有的小生境，則通過罰函數方式，迫使該粒子離開其他子群所擁有的小生境。罰函數如下式所示：

eval(xni)=f(xni)if hill_valley(xni,xkbest)=1f(xni)-p(xni)otherwise---(1)]]>

上式中，xⁱ_n表示第n個子群中第i個粒子位置，f(xⁱ_n)為該粒子原始的適應度值。x_k^best是第k個子群中最優粒子的位置，k不等于n，p(xⁱ_n)是罰函數，在這里可以取一個較大的常數。

原始的粒子群優化是一種基于實值的算法，在本專利中，Kennedy等所提出的一種簡單的二進制版本的PSO算法被采用。在該算法中，粒子的速度被用來作為一個概率來決定對應的位為零還是一。整個數學描述如下所示：

S(v)=11+exp-v---(2)]]>

xid=1ifrand(*)≤S(v)0otherwise---(3)]]>

在上面的公式中，v表示對應粒子的速度，rand(*)是一個均勻分布在[0，1]之間的隨機數。粒子的狀態只有兩種情況1或0，而速度V與某個概率閾值相關，速度越大，則粒子位置取1的可能性越大，反之越小。

(5)多層集成選擇模型的構建

在多層模型中，每一層中將有多種不同的選擇集成。底層是由基分類器所產生的二值輸出向量(Oracle?output?vector)所組成。整個多層選擇模型以第一層中的二值輸出向量為基礎，每層將依賴上一層而選擇出多種不同的、性能優秀的集成，而新的集成的結果又組成一個二值輸出向量，這樣就有機地構成了一個新穎的集成多層選擇模型。每一層的多個集成選擇問題被看成是一個多模優化問題，小生境PSO算法被用來在每一層中發現多組最優的選擇集成，從而在實踐中最終實現了分類器多層選擇模型。