夏勁松

摘要：如何利用網(wǎng)絡(luò)技術(shù)手段，幫助用戶從互聯(lián)網(wǎng)海量信息中迅速準(zhǔn)確地獲取用戶所需信息是信息檢索領(lǐng)域的首要問題。數(shù)據(jù)融合技術(shù)能夠?qū)⒉煌瑱z索系統(tǒng)提交的檢索結(jié)果進(jìn)行組合從而得到一個(gè)新的檢索結(jié)果。對(duì)數(shù)據(jù)融合技術(shù)中的線性組合法進(jìn)行研究，著重探討如何采用智能優(yōu)化算法解決線性組合法的權(quán)重分配問題，分析基于差分進(jìn)化算法和基于粒子群算法的權(quán)重分配策略，在上述兩種優(yōu)化算法的基礎(chǔ)上，提出一種新的線性組合法權(quán)重分配策略：基于自適應(yīng)交替的粒子群差分進(jìn)化優(yōu)化算法權(quán)重分配策略。

關(guān)鍵詞關(guān)鍵詞：數(shù)據(jù)融合；線性組合法；權(quán)重分配；差分進(jìn)化算法；粒子群算法

DOIDOI：10.11907/rjdk.171793

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）011020204

0引言

從已有研究中可以得知，數(shù)據(jù)融合方法能夠有效提升檢索性能[13]。根據(jù)對(duì)成員系統(tǒng)處理方式不同，數(shù)據(jù)融合方法可分為兩類：同等處理方法和差別處理方法[4]。第一種方法是用相同的標(biāo)準(zhǔn)去處理每一個(gè)成員系統(tǒng)的檢索結(jié)果，如CombSUM和CombMNZ方法；第二種方法會(huì)根據(jù)成員檢索系統(tǒng)具體特征采用某種方式給其加權(quán)，如線性組合法（Linear Combination，LC）。因此，從現(xiàn)行組合法對(duì)成員系統(tǒng)的處理方式可以得知，優(yōu)化權(quán)重分配策略是提升線性組合法融合性能的關(guān)鍵。線性組合法的成員系統(tǒng)權(quán)重分配屬于全局優(yōu)化問題，而全局優(yōu)化問題一般都會(huì)存在非線性、復(fù)雜性、多極值性及約束性等問題。因此，本文使用差分進(jìn)化算法、粒子群算法以及自適應(yīng)交替的差分進(jìn)化粒子群優(yōu)化算法等智能優(yōu)化算法，為線性組合方法訓(xùn)練權(quán)重以提高融合性能。

1數(shù)據(jù)融合方法

數(shù)據(jù)融合方法根據(jù)對(duì)成員系統(tǒng)處理方式的不同主要分為兩類：同等處理方式的融合方法和差別處理方式的融合方法[5]。

同等處理方式的融合方法指在融合成員系統(tǒng)的檢索結(jié)果時(shí)，用相同的標(biāo)準(zhǔn)去處理每一個(gè)成員系統(tǒng)的檢索結(jié)果。常用方法有CombSUM和CombMNZ[67]。給定一個(gè)文檔集D和m個(gè)參與融合的成員系統(tǒng)IR={ir1，ir2，ir3，…，irm}，對(duì)于一個(gè)以查詢?yōu)樾问降挠脩粜枨髊，m個(gè)成員系統(tǒng)對(duì)文檔集D中的文檔進(jìn)行檢索，返回的檢索結(jié)果為L(zhǎng)i=〈di1，di2，di3，…，din

其中，w表示慣性權(quán)重；c1和c2為加速因子；而r1和r2是[0，1]范圍內(nèi)的兩個(gè)隨機(jī)數(shù)；Vmax表示最大速度，用來(lái)限制粒子的移動(dòng)速度，使粒子的運(yùn)動(dòng)保持在一定范圍內(nèi)，從而控制粒子在解空間的搜索范圍；gj表示整個(gè)群體所有粒子的歷史最優(yōu)位置記錄，即全局極值gbest；pij指?jìng)€(gè)體極值pbest，表示粒子i在解空間內(nèi)所搜尋到的歷史最優(yōu)解。

同基于差分進(jìn)化算法的權(quán)重分配策略類似，在確定融合結(jié)果性能值（在MAP評(píng)價(jià)指標(biāo)下）與權(quán)重集合W的關(guān)系后，將集合W作為粒子的所在位置，將MAP（g，Q）作為粒子群算法的適應(yīng)度函數(shù)。這樣，便可以通過(guò)粒子群算法優(yōu)化權(quán)重，通過(guò)多次迭代得到一組權(quán)重，能夠較好地提升融合結(jié)果MAP值。

2.3基于自適應(yīng)交替粒子群差分進(jìn)化算法的權(quán)重分配策略

本文使用了一種基于這兩種算法的混合算法：自適應(yīng)交替粒子群差分進(jìn)化算法。在該算法中，使用p=1/（1+e-i）（i為算法的當(dāng)前迭代次數(shù)）作為交替運(yùn)行這兩種算法的控制參數(shù)。這樣通過(guò)參數(shù)p控制，在算法運(yùn)行初期以較大的幾率運(yùn)行粒子群算法對(duì)種群進(jìn)行優(yōu)化，可以發(fā)揮粒子群算法前期收斂快但后期容易陷入收斂停滯的特點(diǎn)；在算法運(yùn)行后期則以較大的幾率使用差分進(jìn)化算法對(duì)種群進(jìn)行優(yōu)化，這樣便可以充分利用差分進(jìn)化算法前期收斂慢、后期收斂快的特點(diǎn)[11]，提高效率的同時(shí)還能夠降低收斂停滯現(xiàn)象發(fā)生幾率。自適應(yīng)交替粒子群算法流程如圖1所示。

圖1自適應(yīng)交替粒子群差分進(jìn)化算法流程

與前兩種權(quán)重分配策略類似，將成員系統(tǒng)的權(quán)重集合W作為粒子的所在位置，將MAP（G，Q）作為自適應(yīng)交替粒子群差分進(jìn)化算法的適應(yīng)度函數(shù)。這樣，便可以通過(guò)該算法優(yōu)化權(quán)重，經(jīng)過(guò)多次迭代得到一組權(quán)重，可較好地提升融合結(jié)果MAP值。

3實(shí)驗(yàn)及結(jié)果分析

3.1實(shí)驗(yàn)設(shè)置

參與實(shí)驗(yàn)的方法有：CombSUM、CombMNZ、基于多元線性回歸的權(quán)重分配策略、基于差分進(jìn)化算法的權(quán)重分配策略、基于粒子群算法的權(quán)重分配策略、基于自適應(yīng)簡(jiǎn)化粒子群算法的權(quán)重分配策略、基于自適應(yīng)交替粒子群差分進(jìn)化算法的權(quán)重分配策略、基于遺傳算法的權(quán)重分配策略（實(shí)驗(yàn)中分別以MRFusion、DEFusion、PSOFusion、AESPSOFusion、PSODEFusion和GAFusion代替）。

本文采用的數(shù)據(jù)集為TREC 2004 Robust Task。在TREC 2004 Robust Task中一共有14個(gè)信息檢索領(lǐng)域的學(xué)術(shù)組織參賽并提交了最終檢索結(jié)果，這些結(jié)果總共有110個(gè)，根據(jù)所提交組織的不同共分為14個(gè)小組。每個(gè)成員系統(tǒng)的檢索結(jié)果中包含249個(gè)查詢，查詢的編號(hào)范圍為301～450，450～700（其中查詢編號(hào)672沒有在查詢相關(guān)文檔列表，因此不列為實(shí)驗(yàn)數(shù)據(jù)）。

本次實(shí)驗(yàn)共分為3個(gè)部分：

（1）算法迭代次數(shù)對(duì)數(shù)據(jù)融合方法的影響。本文考慮迭代次數(shù)對(duì)融合方法的影響，分別開展循環(huán)次數(shù)為50、75、100、150、200、300共6組實(shí)驗(yàn)。在每組實(shí)驗(yàn)中，從TREC 2004 Robust Task中的14組共110個(gè)成員系統(tǒng)中，每組隨機(jī)選取一個(gè)成員系統(tǒng)，共14個(gè)進(jìn)行50次隨機(jī)融合實(shí)驗(yàn)，最后將得到的結(jié)果取平均值

（2）參與融合的成員系統(tǒng)數(shù)量對(duì)數(shù)據(jù)融合方法的影響。測(cè)試檢索系統(tǒng)的數(shù)量對(duì)融合方法性能的影響，對(duì)不同數(shù)量的成員系統(tǒng)進(jìn)行融合實(shí)驗(yàn)。從TREC 2004 Robust Task中的14組共110個(gè)成員系統(tǒng)中選取不同的組數(shù)進(jìn)行融合實(shí)驗(yàn)（從4到14組）。對(duì)于同一組數(shù)實(shí)驗(yàn)，從每組中隨機(jī)選取一個(gè)成員系統(tǒng)進(jìn)行50次隨機(jī)融合實(shí)驗(yàn)，然后對(duì)其結(jié)果的性能指標(biāo)取平均值。endprint

（3）融合算法所耗時(shí)間比較與分析。在該實(shí)驗(yàn)中，對(duì)8個(gè)融合方法在實(shí)驗(yàn)中的所耗時(shí)間進(jìn)行對(duì)比和分析，實(shí)驗(yàn)中所使用的電腦配置為：CPU：Intel Core i76700，RAM：32GB。

3.2實(shí)驗(yàn)結(jié)果

3.2.1迭代次數(shù)對(duì)數(shù)據(jù)融合方法的影響

根據(jù)上述實(shí)驗(yàn)設(shè)置與步驟，選取數(shù)據(jù)進(jìn)行試驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示。

50、75、100、150、200、300表示基于智能優(yōu)化算法權(quán)重分配策略的線性組合法的的迭代次數(shù)，而CombSUM、CombMNZ和MRFusion算法無(wú)需進(jìn)行循環(huán)迭代操作。表1中，只有DEFusion、PSOFusion、AESPSOFusion、PSODEFusion的性能超過(guò)了最佳成員系統(tǒng)的性能并且均優(yōu)于傳統(tǒng)融合方法CombSUM和CombMNZ?？傮w而言，在MAP評(píng)價(jià)指標(biāo)下，隨著迭代次數(shù)的增加，基于智能優(yōu)化算法的融合方法在性能上有一定提升。

3.2.2參與融合成員系統(tǒng)數(shù)量對(duì)數(shù)據(jù)融合方法的影響

在實(shí)驗(yàn)中，控制參與融合的成員系統(tǒng)數(shù)量，分析不同成員系統(tǒng)數(shù)量對(duì)融合方法性能的影響程度。參與實(shí)驗(yàn)的方法有：CombSUM、CombMNZ以及基于智能優(yōu)化算法權(quán)重分配策略的線性組合法，結(jié)果如圖2所示。

圖2成員系統(tǒng)數(shù)量不同情況下的融合結(jié)果曲線（評(píng)價(jià)指標(biāo)：MAP）

圖2中，橫坐標(biāo)為參與融合成員系統(tǒng)的數(shù)目，用n表示，縱坐標(biāo)表示各融合方法的性能。在所有數(shù)據(jù)融合方法中，性能最好的是PSODEFusion和AESPSOFusion，DEFusion次之。在8種融合方法中，除CombMNZ和MRFuison方法外 ，其余6種融合方法的性能均優(yōu)于最優(yōu)成員系統(tǒng)均值。參與融合的成員系統(tǒng)個(gè)數(shù)逐漸增加，有利于DEFusion、PSODEFusion融合性能的提升。

3.2.3融合算法所耗時(shí)間比較與分析

8種融合方法分別在訓(xùn)練和融合階段的時(shí)間消耗如表2所示。由上文可知，線性組合法在融合前需要訓(xùn)練數(shù)據(jù)獲得權(quán)重，而CombSUM和CombMNZ方法則無(wú)需訓(xùn)練權(quán)重，因此沒有訓(xùn)練所耗時(shí)間。

4結(jié)語(yǔ)

本文探討了基于差分進(jìn)化算法和基于粒子群算法的權(quán)重分配策略。在上述兩種優(yōu)化算法的基礎(chǔ)上，探討了基于自適應(yīng)交替的粒子群差分進(jìn)化優(yōu)化算法權(quán)重分配策略，該算法是首次被引用到數(shù)據(jù)融合中。實(shí)驗(yàn)結(jié)果表明，兼顧時(shí)間和性能、基于自適應(yīng)交替粒子群差分進(jìn)化優(yōu)化算法權(quán)重分配策略能夠有效提升融合性能。

參考文獻(xiàn)參考文獻(xiàn)：

[1]COOPER W S.The inadequacy of probability of usefulness as a ranking criterion for retrieval system output[M].University of California， Berkeley，1971.

[2]LEE J H.Analyses of multiple evidence combination[J]. ACM SIGIR Forum，1996，31（SI）：267276.

[3]WUS，BI Y，ZENG X.The linear combination data fusion method in information retrieval[C]. International Conference on Database and Expert Systems Applications.SpringerVerlag，2011：219233.

[4]WU S，MCCLEAN S.Performance prediction of data fusion for information retrieval[J]. Information Processing & Management，2006，42（4）：899915.

[5]黃春蘭，吳勝利.數(shù)據(jù)融合在搜索結(jié)果多元化上的應(yīng)用[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2015，50（1）：3136.

[6]PANDI V R，BISWAS A，DASGUPTA S，et al.A hybrid bacterial foraging and differential evolution algorithm for congestion management[J].European Transactions on Electrical Power，2010，20（7）：862871.

[7]陳婷婷.支持檢索結(jié)果多樣化顯式方法的比較研究[D].鎮(zhèn)江：江蘇大學(xué)，2016.

[8]SINGHAL A.Modern information retrieval：a brief overview[J].Bulletin of the IEEE Computer Society Technical Committee on Data Engineering，2001，24（24）：3543.

[9]張春美.差分進(jìn)化算法理論與應(yīng)用[M].北京：北京理工大學(xué)出版社，2014.

[10]楊維，李歧強(qiáng).粒子群優(yōu)化算法綜述[J].中國(guó)工程科學(xué)，2004，6（5）：8794.

[11]FOX E A，KOUSHIK M P，SHAW J A，et al.Combining evidence from multiple searches[C].Text Retrieval Conference，1992：319328.

責(zé)任編輯（責(zé)任編輯：孫娟）endprint