一種基于領(lǐng)域優(yōu)化的集成交叉覆蓋神經(jīng)網(wǎng)絡(luò)

孫 冰， 李曉麗

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京 210009）

神經(jīng)網(wǎng)絡(luò)伴隨著其理論和技術(shù)的不斷發(fā)展，已成功應(yīng)用于模式識(shí)別、函數(shù)逼近、智能控制、數(shù)據(jù)挖掘及知識(shí)發(fā)現(xiàn)等多個(gè)領(lǐng)域。在實(shí)際運(yùn)用中，泛化能力即為神經(jīng)網(wǎng)絡(luò)識(shí)別訓(xùn)練數(shù)據(jù)集之外樣本的能力，被認(rèn)為是衡量神經(jīng)網(wǎng)絡(luò)性能的最重要指標(biāo)，因此，如何有效地提高其能力已成為最受關(guān)注的問(wèn)題之一。

神經(jīng)網(wǎng)絡(luò)集成［1－3］是用有限個(gè)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)同一個(gè)問(wèn)題，集成在某個(gè)輸入示例下的輸出由構(gòu)成集成的各神經(jīng)網(wǎng)絡(luò)在該示例下的輸出共同決定。集成的構(gòu)建通常包括2個(gè)步驟，首先是利用基分類器訓(xùn)練出多個(gè)版本，然后將這些分類器進(jìn)行結(jié)合。文獻(xiàn)［4－5］提出的Boosting算法已經(jīng)證明了集成學(xué)習(xí)能有效地提高學(xué)習(xí)系統(tǒng)的泛化能力。本文采用集成的交叉覆蓋神經(jīng)網(wǎng)絡(luò)，通過(guò)在集成過(guò)程中加入覆蓋領(lǐng)域優(yōu)化算法（coverage areas optimization algorithm，簡(jiǎn)稱CAOA）以降低集成系統(tǒng)的泛化誤差，從而進(jìn)一步提高集成系統(tǒng)的識(shí)別效果。

1 交叉覆蓋算法的基本思想

覆蓋算法是基于MP神經(jīng)元模型［6］的幾何意義所給出的一種神經(jīng)網(wǎng)絡(luò)分類器的設(shè)計(jì)方法。覆蓋算法的基本思想是假定訓(xùn)練樣本或待識(shí)別樣本為n維向量，構(gòu)造型神經(jīng)網(wǎng)絡(luò)將所有的訓(xùn)練樣本投影變換到n＋1維的超球面上，從而模式識(shí)別問(wèn)題被轉(zhuǎn)化為在n＋1維的超球面上的覆蓋問(wèn)題。通過(guò)在超球面上尋找可以對(duì)訓(xùn)練樣本集進(jìn)行正確分類的較優(yōu)覆蓋，實(shí)現(xiàn)對(duì)樣本空間的劃分，并根據(jù)得到的覆蓋判斷待識(shí)別樣本的類別［7］。

設(shè)給定一輸入集K＝｛x1，x2，…，xk｝（K是n維歐式空間的點(diǎn)集），設(shè)K分為s個(gè)子集，K1＝｛x1，x2，…，xm（1）｝，…，Ks＝｛xm（x－1）＋1，…，xk｝。用一個(gè)3層網(wǎng)絡(luò)N構(gòu)造分類器，即等價(jià)于求出一組領(lǐng)域，這組領(lǐng)域?qū)⒉煌惖狞c(diǎn)分隔開，使屬于Ki點(diǎn)的輸出均為yi＝（0，…，1，0，…，0），即其第i個(gè)分量為1，其余分量為0的向量，i＝1，2，…，s［8］。

交叉覆蓋的思想實(shí)際上是用領(lǐng)域進(jìn)行交替覆蓋，具體訓(xùn)練算法步驟如下：

（1）任取一個(gè)第i類尚未被覆蓋的點(diǎn)ai。

（2）判斷訓(xùn)練集中是否存在與ai異類的樣本點(diǎn)，若存在則計(jì)算與ai最近的異類樣本點(diǎn)到ai的距離d1；若不存在異類樣本點(diǎn)，直接轉(zhuǎn)入步驟（3）。

（3）找出訓(xùn)練集中離ai最遠(yuǎn)且距離小于d1的同類點(diǎn)c，兩者距離為d2；當(dāng)沒(méi)有異類點(diǎn)時(shí)，d1和d2都取最大距離。

（4）覆蓋領(lǐng)域的半徑r＝（d1＋d2）／2。

（5）構(gòu)造以ai為中心，閾值為r的覆蓋領(lǐng)域C（ai），找出所有屬于C（ai）的樣本，并從訓(xùn)練樣本中刪除被此領(lǐng)域覆蓋的樣本。

（6）判斷訓(xùn)練集中是否還有樣本點(diǎn)，如果有則找到離ai最近的樣本點(diǎn)，從步驟（2）重復(fù)；若沒(méi)有樣本點(diǎn)則訓(xùn)練過(guò)程結(jié)束。

2 交叉覆蓋算法泛化性能分析

根據(jù)文獻(xiàn)［9］平面螺旋線識(shí)別問(wèn)題中所得結(jié)果，該算法對(duì)學(xué)習(xí)樣本的識(shí)別率為100%，但對(duì)螺旋線上的非學(xué)習(xí)樣本點(diǎn)，則不能達(dá)到100%的識(shí)別率，特別是在測(cè)試樣本有一定隨機(jī)擾動(dòng)時(shí)，識(shí)別率下降很多。泛化能力不理想的主要原因是由于覆蓋領(lǐng)域的邊界接近另外一類，即在求以ai為中心的領(lǐng)域C（ai）時(shí)［9］，C（ai）對(duì)應(yīng)的權(quán)和閾值按下式求得：

由（1）～（3）式可知，當(dāng)d1（i）≈d2（i）時(shí)，d（i）≈d2（i），會(huì)發(fā)生如圖1所示的情況，圖中圓形區(qū)域?yàn)楦采w領(lǐng)域C（ai），當(dāng)領(lǐng)域C（ai）極其接近K2中的點(diǎn)時(shí)，會(huì)產(chǎn)生測(cè)試樣本中K2類的點(diǎn)的誤識(shí)情況。

圖1 誤識(shí)情況示例

其中，○表示K1類的樣本點(diǎn)，●表示K2類的樣本點(diǎn)，點(diǎn)A表示K2類的測(cè)試樣本誤識(shí)為K1類的情況。K2中點(diǎn)的吸引域與覆蓋領(lǐng)域C（ai）的交集非空，因而在測(cè)試時(shí)造成樣本誤識(shí)，而正是上述情況導(dǎo)致了誤差的出現(xiàn)。為直觀計(jì)，將公式中的內(nèi)積直接表示成距離，實(shí)際含義是相同的。但是，該種情況并非不可區(qū)分［10］。

引理1 設(shè)任意一個(gè)覆蓋領(lǐng)域C（ai）的中心為ai（ai∈K1），半徑為R，與其相鄰的最接近的K2類點(diǎn)是a，則點(diǎn)a的吸引域侵入覆蓋領(lǐng)域C（ai）部分的侵入距離r＜R／2。

實(shí)際上，由于R具有單調(diào)增加趨勢(shì)，而r＋r′固定不變，因此r相對(duì)R／2而言是很小的量，則可能出錯(cuò)域是一個(gè)外徑為R、內(nèi)徑為R－r的一個(gè)超圓環(huán)域。由引理1可得定理1。

定理1 設(shè)逼近的目標(biāo)函數(shù)為f：Rn→｛－1，＋1｝，且樣本集按分布p（x）隨機(jī)抽取，則基于覆蓋的單個(gè)神經(jīng)元的泛化誤差E的上限可以估計(jì)為：

由此可見，交叉覆蓋中單個(gè)神經(jīng)元的誤差區(qū)間為最大半徑和最小半徑之間存在的環(huán)域，如圖2所示。

圖2 S環(huán)示例

因此，若想提高神經(jīng)網(wǎng)絡(luò)集成后系統(tǒng)的泛化誤差，降低系統(tǒng)的誤識(shí)率，關(guān)鍵是降低神經(jīng)網(wǎng)絡(luò)集成后系統(tǒng)中各個(gè)神經(jīng)元誤差區(qū)域的交集，即減小集成后各個(gè)神經(jīng)元的S環(huán)交集區(qū)域。所以，在集成過(guò)程中，需要對(duì)產(chǎn)生的覆蓋領(lǐng)域進(jìn)行優(yōu)化處理，以生成合適的神經(jīng)元。

3 基于領(lǐng)域優(yōu)化的交叉覆蓋神經(jīng)網(wǎng)絡(luò)

在構(gòu)造網(wǎng)絡(luò)集成中的每個(gè)個(gè)體網(wǎng)絡(luò)過(guò)程中，采用如下方法。

（1）第1個(gè)神經(jīng)網(wǎng)絡(luò)的構(gòu)造過(guò)程同一般的交叉覆蓋算法。

（2）設(shè)第n個(gè)網(wǎng)絡(luò)已經(jīng)構(gòu)造完成，則第n＋1個(gè)網(wǎng)絡(luò)的構(gòu)造方法是在原有的交叉覆蓋算法基礎(chǔ)上，加入覆蓋領(lǐng)域優(yōu)化算法CAOA。在生成新的覆蓋領(lǐng)域C（ai）時(shí)，檢查與所有已經(jīng)生成的覆蓋領(lǐng)域的交集：① 如果存在C（aj），使

則將覆蓋領(lǐng)域C（ai）平移，生成覆蓋領(lǐng)域C′（ai），使其不滿足（5）式，否則減小C（ai）的半徑r，使其不滿足（5）式；② 如果存在C（aj），使

則將覆蓋領(lǐng)域C（ai）平移，生成覆蓋領(lǐng)域C′（ai），使其不滿足（6）式，否則減小C（ai）的半徑r，使其不滿足（6）式。

在完成n個(gè)神經(jīng)網(wǎng)絡(luò)構(gòu)造之后，每一個(gè)神經(jīng)網(wǎng)絡(luò)都對(duì)各個(gè)類別有著與其他n－1個(gè)神經(jīng)網(wǎng)絡(luò)不同的新劃分，在待識(shí)別的樣本點(diǎn)落入神經(jīng)網(wǎng)絡(luò)模型中時(shí)，n個(gè)網(wǎng)絡(luò)分別獨(dú)立進(jìn)行識(shí)別，最后對(duì)結(jié)果進(jìn)行投票，當(dāng)有多數(shù)網(wǎng)絡(luò)將待測(cè)樣本識(shí)別為同一個(gè)類時(shí)，則輸出多數(shù)網(wǎng)絡(luò)支持的識(shí)別結(jié)果。

4 神經(jīng)網(wǎng)絡(luò)泛化性能分析

由上述分析知，覆蓋領(lǐng)域的中心部分基本沒(méi)有誤差，絕大多數(shù)誤差發(fā)生在覆蓋領(lǐng)域的邊界部分，即覆蓋外側(cè)的環(huán)形區(qū)域內(nèi)。在網(wǎng)絡(luò)集成中，由于各個(gè)子網(wǎng)絡(luò)的差異性，對(duì)于K1類的樣本識(shí)別時(shí)，產(chǎn)生的覆蓋領(lǐng)域如圖3所示，其中陰影部分即為系統(tǒng)發(fā)生誤識(shí)的區(qū)域。

圖3 神經(jīng)網(wǎng)絡(luò)集成后的誤識(shí)區(qū)域

由圖3可見，通過(guò)神經(jīng)網(wǎng)絡(luò)集成，原來(lái)在最大半徑和最小半徑之間存在的環(huán)域中的誤差區(qū)域，已經(jīng)被新的3個(gè)環(huán)域的交集所取代，可能發(fā)生識(shí)別誤差的范圍顯著縮小，僅僅存在于3個(gè)環(huán)域的6個(gè)交集中，而測(cè)試樣本點(diǎn)剛好落在這些區(qū)域內(nèi)的可能性非常小，因此識(shí)別率會(huì)明顯提高。

假設(shè)1 學(xué)習(xí)任務(wù)是利用N個(gè)神經(jīng)網(wǎng)絡(luò)組成的集成對(duì)f：Rn→｛0，1｝進(jìn)行近似，集成采用相對(duì)多數(shù)投票法。

假設(shè)2 樣本集按分布p（x）隨機(jī)抽取，網(wǎng)絡(luò)α對(duì)輸入X的輸出為Vα（X），根據(jù)引理1，則單個(gè)神經(jīng)網(wǎng)絡(luò)α的泛化誤差Eα為：

其中，∪S環(huán)為神經(jīng)網(wǎng)絡(luò)α中所有神經(jīng)元S環(huán)的并集。

定理2 滿足假設(shè)1、假設(shè)2的神經(jīng)網(wǎng)絡(luò)集成的泛化誤差上限可估計(jì)為：

其中，∩∪S環(huán)為相對(duì)多數(shù)個(gè)∪S環(huán)的交集。

在子網(wǎng)絡(luò)的生成過(guò)程中，加入領(lǐng)域優(yōu)化算法CAOA，不斷監(jiān)視覆蓋領(lǐng)域的生成情況，并對(duì)生成的覆蓋領(lǐng)域進(jìn)行優(yōu)化處理，盡量減少覆蓋領(lǐng)域重合、內(nèi)切和外切的情況發(fā)生，如圖4所示，以提高集成后系統(tǒng)的泛化性能。

圖4 覆蓋領(lǐng)域的重合、內(nèi)切和外切狀態(tài)

5 應(yīng)用實(shí)例

采用3個(gè)神經(jīng)網(wǎng)絡(luò)進(jìn)行集成，3個(gè)網(wǎng)絡(luò)分別獨(dú)立進(jìn)行識(shí)別，對(duì)得到的結(jié)果進(jìn)行投票，將輸出多數(shù)網(wǎng)絡(luò)支持的識(shí)別結(jié)果作為系統(tǒng)最終識(shí)別結(jié)果，集成后生成覆蓋領(lǐng)域的個(gè)數(shù)為3個(gè)子網(wǎng)絡(luò)覆蓋領(lǐng)域數(shù)的平均值。

例1 電離層數(shù)據(jù)分類。Ionosphere電離層數(shù)據(jù)庫(kù)是收集于加拿大的Goose Bay和Labrador的雷達(dá)信號(hào)數(shù)據(jù)，它包含17個(gè)脈沖信號(hào)，每個(gè)脈沖有2個(gè)屬性，信號(hào)分為“好”和“壞”2種，“好”是指可反映電離層的結(jié)構(gòu)，而“壞”是指信號(hào)穿過(guò)電離層，不能反映電離層的結(jié)構(gòu)，即數(shù)據(jù)庫(kù)共有35個(gè)屬性。該數(shù)據(jù)庫(kù)的前200個(gè)樣本中“好”和“壞”各占50%，后150個(gè)樣本中，“好”的有123個(gè)。實(shí)驗(yàn)中隨機(jī)抽取75%的數(shù)據(jù)為訓(xùn)練樣本，其余25%的數(shù)據(jù)為測(cè)試樣本。

Ionosphere數(shù)據(jù)識(shí)別結(jié)果見表1所列，其中，方法1為交叉覆蓋算法（50次平均）；方法2為標(biāo)準(zhǔn)交叉覆蓋神經(jīng)網(wǎng)絡(luò)集成；方法3為基于CAOA的交叉覆蓋神經(jīng)網(wǎng)絡(luò)集成?；贑AOA的交叉覆蓋神經(jīng)神經(jīng)網(wǎng)絡(luò)集成中各個(gè)子網(wǎng)絡(luò)識(shí)別結(jié)果，見表2所列。

表1 Ionosphere數(shù)據(jù)識(shí)別結(jié)果

表2 采用方法3A、B、C子網(wǎng)絡(luò)對(duì)例1識(shí)別結(jié)果

例2 玻璃識(shí)別數(shù)據(jù)集分類。Glass數(shù)據(jù)集提供了6種玻璃數(shù)據(jù)的分類信息，共有9種屬性。其中，對(duì)于第1類有70條數(shù)據(jù)記錄，第2類有76條數(shù)據(jù)記錄，第3類有17條數(shù)據(jù)記錄，第4類有13條數(shù)據(jù)記錄，第5類有9條數(shù)據(jù)記錄，第6類有29條數(shù)據(jù)記錄。實(shí)驗(yàn)中隨機(jī)抽取75%的數(shù)據(jù)為訓(xùn)練樣本，其余25%的數(shù)據(jù)為測(cè)試樣本，實(shí)驗(yàn)結(jié)果見表3、表4所列。其中，方法1～方法3同表1。

表3 Glass數(shù)據(jù)識(shí)別結(jié)果

表4 采用方法3A、B、C子網(wǎng)絡(luò)對(duì)例2識(shí)別結(jié)果

以上數(shù)據(jù)顯示，從識(shí)別效果上看，神經(jīng)網(wǎng)絡(luò)集成可以大大提高系統(tǒng)的識(shí)別能力，領(lǐng)域優(yōu)化算法CAOA使集成過(guò)程中獲得較優(yōu)的覆蓋，從而進(jìn)一步提高系統(tǒng)識(shí)別率。從執(zhí)行時(shí)間上看，由于神經(jīng)網(wǎng)絡(luò)集成要訓(xùn)練若干的獨(dú)立的子網(wǎng)絡(luò)，識(shí)別過(guò)程中也需要各子網(wǎng)絡(luò)獨(dú)立給出識(shí)別結(jié)果，因此，訓(xùn)練和測(cè)試時(shí)間都有所延長(zhǎng)。加入算法CAOA，使系統(tǒng)在集成時(shí)對(duì)生成的覆蓋有所選擇，因此會(huì)影響訓(xùn)練時(shí)間，但影響并不十分明顯。在測(cè)試階段，標(biāo)準(zhǔn)交叉覆蓋神經(jīng)網(wǎng)絡(luò)集成與加入算法CAOA的神經(jīng)網(wǎng)絡(luò)集成所用時(shí)間并無(wú)明顯差別。

6 結(jié)束語(yǔ)

本文在對(duì)交叉覆蓋算法的基本思想及泛化性能分析的基礎(chǔ)上，提出了一種集成的交叉覆蓋神經(jīng)網(wǎng)絡(luò)構(gòu)造方法，在子網(wǎng)絡(luò)的生成過(guò)程中加入領(lǐng)域優(yōu)化算法CAOA，對(duì)生成的覆蓋領(lǐng)域進(jìn)行優(yōu)化處理，以降低集成系統(tǒng)的誤識(shí)區(qū)域，增強(qiáng)識(shí)別效果。實(shí)例證明，該神經(jīng)網(wǎng)絡(luò)集成構(gòu)造方法有效。在實(shí)際應(yīng)用過(guò)程中，應(yīng)充分考慮數(shù)據(jù)集本身的分布特征，并綜合考慮網(wǎng)絡(luò)規(guī)模和時(shí)間消耗。

［1］ Hansen L K，Salamon P.Neural network ensembles［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1990，12（10）：993－1001.

［2］ Zhou Z H，Wu J X，Tang W.Ensembling neural networks：Many could be better than all［J］.Artificial Intelligence，2002，137（1／2）：239－263.

［3］ 丁亞明，王樹忠，張志紅，等.基于改進(jìn)神經(jīng)網(wǎng)絡(luò)的模糊聚類算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，30（8）：934－938.

［4］ 周志華，陳世福.神經(jīng)網(wǎng)絡(luò)集成［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25（1）：1－8.

［5］ 姚敏鋒，李心廣，黃文濤.一種k均值和神經(jīng)網(wǎng)絡(luò)集成的語(yǔ)音識(shí)別方法［J］.計(jì)算機(jī)工程與應(yīng) 用，2012，48（12）：144－147.

［6］ 劉政怡，吳建國(guó)，李 煒.基于交叉覆蓋算法的中文分詞［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（6）：1355－1361.

［7］ 賈瑞玉，李永順.基于覆蓋算法的分類器的設(shè)計(jì)與應(yīng)用［J］.安徽大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，35（2）：28－32.

［8］ 劉政怡，龔建成，吳建國(guó).基于交叉覆蓋算法的中文文本分類［J］.計(jì)算機(jī)工程，2006，32（19）：183－184.

［9］ 張 玲，張 鈸，殷海風(fēng).多層前向網(wǎng)絡(luò)的交叉覆蓋設(shè)計(jì)算法［J］.軟件學(xué)報(bào)，1999，10（7）：737－742.

［10］ 宋茂斌，宮寧生.基于改進(jìn)交叉覆蓋設(shè)計(jì)算法的魯棒性［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（22）：71－72.