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

無效

• 申請?zhí)枺?/td>: 200710193876.2
• 申請日: 2007-11-30
• 公開（公告）號: CN101187944A
• 公開（公告）日: 2008-05-28
• 發(fā)明（設(shè)計）人: 黃德雙;章軍
• 申請（專利權(quán)）人: 中國科學(xué)院合肥物質(zhì)科學(xué)研究院
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F15/18
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司
• 代理人: 趙曉薇

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

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

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

(2)制定集成選擇標(biāo)準(zhǔn)

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

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

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

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

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

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

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

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

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

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

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

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

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