夏勁松

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

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

DOIDOI：10.11907/rjdk.171793

中圖分類號：TP391

文獻標(biāo)識碼：A文章編號文章編號：16727800（2017）011020204

0引言

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

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

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

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

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

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

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

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

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

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

3實驗及結(jié)果分析

3.1實驗設(shè)置

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

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

本次實驗共分為3個部分：

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

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

（3）融合算法所耗時間比較與分析。在該實驗中，對8個融合方法在實驗中的所耗時間進行對比和分析，實驗中所使用的電腦配置為：CPU：Intel Core i76700，RAM：32GB。

3.2實驗結(jié)果

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

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

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

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

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

圖2成員系統(tǒng)數(shù)量不同情況下的融合結(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)個數(shù)逐漸增加，有利于DEFusion、PSODEFusion融合性能的提升。

3.2.3融合算法所耗時間比較與分析

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

4結(jié)語

本文探討了基于差分進化算法和基于粒子群算法的權(quán)重分配策略。在上述兩種優(yōu)化算法的基礎(chǔ)上，探討了基于自適應(yīng)交替的粒子群差分進化優(yōu)化算法權(quán)重分配策略，該算法是首次被引用到數(shù)據(jù)融合中。實驗結(jié)果表明，兼顧時間和性能、基于自適應(yīng)交替粒子群差分進化優(yōu)化算法權(quá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é)報：理學(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]張春美.差分進化算法理論與應(yīng)用[M].北京：北京理工大學(xué)出版社，2014.

[10]楊維，李歧強.粒子群優(yōu)化算法綜述[J].中國工程科學(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