信息檢索中基于智能優化算法的數據融合方法

夏勁松

摘要：如何利用網絡技術手段，幫助用戶從互聯網海量信息中迅速準確地獲取用戶所需信息是信息檢索領域的首要問題。數據融合技術能夠將不同檢索系統提交的檢索結果進行組合從而得到一個新的檢索結果。對數據融合技術中的線性組合法進行研究，著重探討如何采用智能優化算法解決線性組合法的權重分配問題，分析基于差分進化算法和基于粒子群算法的權重分配策略，在上述兩種優化算法的基礎上，提出一種新的線性組合法權重分配策略：基于自適應交替的粒子群差分進化優化算法權重分配策略。

關鍵詞關鍵詞：數據融合；線性組合法；權重分配；差分進化算法；粒子群算法

DOIDOI：10.11907/rjdk.171793

中圖分類號：TP391

文獻標識碼：A文章編號文章編號：16727800（2017）011020204

0引言

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

1數據融合方法

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

同等處理方式的融合方法指在融合成員系統的檢索結果時，用相同的標準去處理每一個成員系統的檢索結果。常用方法有CombSUM和CombMNZ[67]。給定一個文檔集D和m個參與融合的成員系統IR={ir1，ir2，ir3，…，irm}，對于一個以查詢為形式的用戶需求q，m個成員系統對文檔集D中的文檔進行檢索，返回的檢索結果為Li=〈di1，di2，di3，…，din

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

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

2.3基于自適應交替粒子群差分進化算法的權重分配策略

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

圖1自適應交替粒子群差分進化算法流程

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

3實驗及結果分析

3.1實驗設置

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

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

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

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

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

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

3.2實驗結果

3.2.1迭代次數對數據融合方法的影響

根據上述實驗設置與步驟，選取數據進行試驗，實驗結果如表1所示。

50、75、100、150、200、300表示基于智能優化算法權重分配策略的線性組合法的的迭代次數，而CombSUM、CombMNZ和MRFusion算法無需進行循環迭代操作。表1中，只有DEFusion、PSOFusion、AESPSOFusion、PSODEFusion的性能超過了最佳成員系統的性能并且均優于傳統融合方法CombSUM和CombMNZ。總體而言，在MAP評價指標下，隨著迭代次數的增加，基于智能優化算法的融合方法在性能上有一定提升。

3.2.2參與融合成員系統數量對數據融合方法的影響

在實驗中，控制參與融合的成員系統數量，分析不同成員系統數量對融合方法性能的影響程度。參與實驗的方法有：CombSUM、CombMNZ以及基于智能優化算法權重分配策略的線性組合法，結果如圖2所示。

圖2成員系統數量不同情況下的融合結果曲線（評價指標：MAP）

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

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

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

4結語

本文探討了基于差分進化算法和基于粒子群算法的權重分配策略。在上述兩種優化算法的基礎上，探討了基于自適應交替的粒子群差分進化優化算法權重分配策略，該算法是首次被引用到數據融合中。實驗結果表明，兼顧時間和性能、基于自適應交替粒子群差分進化優化算法權重分配策略能夠有效提升融合性能。

參考文獻參考文獻：

[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]黃春蘭，吳勝利.數據融合在搜索結果多元化上的應用[J].山東大學學報：理學版，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]陳婷婷.支持檢索結果多樣化顯式方法的比較研究[D].鎮江：江蘇大學，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]張春美.差分進化算法理論與應用[M].北京：北京理工大學出版社，2014.

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

責任編輯（責任編輯：孫娟）endprint