信息检索中基于智能优化算法的数据融合方法

夏劲松

摘要：如何利用网络技术手段，帮助用户从互联网海量信息中迅速准确地获取用户所需信息是信息检索领域的首要问题。数据融合技术能够将不同检索系统提交的检索结果进行组合从而得到一个新的检索结果。对数据融合技术中的线性组合法进行研究，着重探讨如何采用智能优化算法解决线性组合法的权重分配问题，分析基于差分进化算法和基于粒子群算法的权重分配策略，在上述两种优化算法的基础上，提出一种新的线性组合法权重分配策略：基于自适应交替的粒子群差分进化优化算法权重分配策略。

关键词关键词：数据融合；线性组合法；权重分配；差分进化算法；粒子群算法

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