一种基于分布式信息检索系统的集合选择方法

摘要

本发明涉及一种分布式信息检索中集合选择方法，目的是提供一种检索效率高和效果好的基于分布式信息检索系统的集合选择方法。实现上述发明目的的技术方案是：一种基于分布式信息检索系统的集合选择方法，该方法包括：计算需要检索的数据对待选数据库的覆盖程度，根据覆盖程度的大小，确定选择数据库集合的先后顺序。本发明方法大大提高了计算机在进行分布式信息检索时系统计算的时间和空间开销，保证了提问结果的查全率和查准率，增强了分布式信息检索的效率和效果。

说明书

技术领域

本发明涉及计算机信息检索领域，具体涉及分布式信息检索中集合选择方法。

背景技术

分布式信息检索是信息检索的一个重要研究方向，研究的主要内容包含“集合选择”、“单数据集合检索”、“结果合并”等几个部分。利用集合选择算法找出最相关的数据集合进行检索，从而实现查询部分文档集合而给出很好的检索结果的效果。集合选择的效果直接决定着最终检索结果的质量。在分布式信息检索领域，集合选择又叫数据库选择或资源选择。

在集合选择方面，著名的算法主要有3种：(1)CORI(Collection RetrievalInference Network)算法：信息库检索推理网络方法，是Callan等人1995年提出，由原有的对文档进行相关性判断的贝叶斯推理网而来，把每个信息库都看成是一篇巨大的文献，信息库等级排列的方法与传统信息检索系统中的文献等级排列的方法相似。(2)gGlOSS(Generalized Glossary of Servers Server)算法：是由Gravano L.等人1999年提出，是根据信息库对输入提问式的友好性对信息库进行等级排列，这样做可以估计每个信息库中含有超过某一阈值的文献数量，然后根据文献数量确定信息库的得分，试图解决得到多个匹配源的时候如何选择合适的源，并开发了向量空间搜索版本和布尔变量版本。(3)CVV(The Cue-Validity-Variance)算法：是由Yuwono和Lee于1997年提出，注意到了Internet的查询特点，在向量空间算法的基础上对算法作了改进。Kirsch；Steven T.和Chang；William I.(2000，US Patent 6,018,733)公开了一种基于特殊查询的文档检索的集合选择方法。Kirsch(1999，US Patent 5,983,21)公开了一种根据统计文档集合所包含的特定词的多少来自动选择集合。此外，D‘Souza(2004)和Si(2004)以及MinJie Zhang(2006)等提出，基于语言模型的集合选择方法要优于CORI算法。Sergey Chernov等(2007)提出一种基于词频统计和假相关语言模型的集合选择算法。Wu和Crestani(2003)提出一种多目标模式的集合选择方法综合考虑了与提问的相关程度、计算时间开销、以及同时在多个资源中获得同一数据的可能机会。张刚(2007)将集合选择问题转化为文档检索问题，尝试了多种文档检索方法来解决集合选择问题。

发明内容

本发明目的是：提供一种检索效率高和效果好的基于分布式信息检索系统的集合选择方法。

实现上述发明目的的技术方案是：

一种基于分布式信息检索系统的集合选择方法，该方法包括：计算需要检索的数据对待选数据库的覆盖程度，根据覆盖程度的大小，确定选择数据库集合的先后顺序。

所述计算需要检索的数据对待选择的数据库的覆盖程度进一步包括以下步骤：

1.通过给包含于待选数据库中的检索数据加权求和的方法(即贪心计算方法)计算待选数据库集合的重要性分值；

2.对于同一条检索数据，如果在先前已选的数据库中出现过，在计算后面的数据库重要性分值时，考虑到不同数据库集合之间的覆盖，该条数据再次出现也不再计入后面的数据库分值内。

上述步骤1所述的贪心算法进一步为：假设有一个提问，检索结合融合排序后的前n个数据(n为自然数)，分别记为：d1，d2，...，dk，...，dn。第k个数据dk在某个数据库C_j中出现时对该数据库重要性的贡献分值为1/k^β，β为正有理数；数据库的重要性分值为其所包含的所有特定的数据的贡献分值之和。

对于一个检索提问可供检索的数据库，有包含提问答案的M个数据库，数据库集合C＝(C₁，C₂，...，C_M)，C_i为第i个可供选择的数据库，i＝1，2，...，M。n为经过融合排序后的检索结果中，前n个文档。C’为根据相关度大小，所有的被选择上的m个数据库的集合，C’＝(C₁’，C₂’，...，C_m’)，C_j’为第j个被选择上的数据库，j＝1，2，...，m，SC_j’为第j个被选择上的数据库的分值，j＝1，2，...，m，β为权函数中的常参数，为正有理数，此处实例中取β＝1。文档k如果出现在数据库C_i中，在形式上标记为kC_i，其贡献分值记为文档k如果出现在数据库C’_j中，在形式上标记为kC’_j，其贡献分值记为数据库的重要性分值计算公式为：

${\mathrm{SC}}_1^{\prime }=\underset{i=1}{\overset{M}{\max }}\underset{k=1}{\overset{n}{\Sigma }}\frac{1}{{\left({\mathrm{kC}}_i\right)}^{\beta }}---\left(a\right)$

${\mathrm{SC}}_l^{\prime }=\underset{i=1}{\overset{M}{\max }}\underset{k=1}{\overset{n}{\Sigma }}\frac{1}{{({\mathrm{kC}}_i-\underset{j=1}{\overset{l-1}{\Sigma }}{\mathrm{kC}}_j^{\prime })}^{\beta }}2\le l\le m---\left(b\right)$

上述方案中，具体包括以下选择步骤：

(1)计算所有含有以上n个数据中任何一个数据的数据库C_i的重要性份值，选择分值最大的数据库作为数据库集合选择中首选的数据库并记为C’₁；

(2)除去已经被选择过的数据库，计算剩下的数据库中，所述包含n个数据中任何一个数据的数据库C_i的重要性份值，在计算中，去除已经选择的数据库中包含的数据；选择重要性份值中最大的一个，记为第2选择数据库C’₂；

(3)重复以上步骤(2)，直到第m次选择C’_m，当这1到m个被选择的数据库已共同补充覆盖所有的n个数据时，结束数据库选择步骤。

与现有技术相比，本发明方法具有以下优点：

1、采用集合覆盖和贪心算法，而非以往的“数字指纹”、“词频统计”、或“语言模型”等信息检索方法，极大地减少了计算机信息检索计算开销；

2、考虑了数据库之间实际存在的覆盖问题，优化了分布式集合选择结果，提高了检索的效率和效果；

3、根据数据在检索结果融合排序后位置的不同，给以不同的权值用以计算该数据对数据库的贡献分值，提高了分布式信息检索的召回率和查准率。

附图说明

图1为分布式信息检索系统结构图；

图2集合选择过程方法流程示意图。

具体实施方式

下面结合附图做进一步说明。

如图1所示，一种基于分布式信息检索系统包括客户机1，客户机2……客户机n，信息检索服务器1，信息检索服务器2……信息检索服务器n，客户机群和信息检索服务器群通过网络连接，客户机群提供检索提问数据，信息检索服务器群提供包含提问答案的所有数据库，本发明提供一种基于该系统进行信息检索的集合选择方法。

对以下实施例，首先定义相关的符号及其代表的意义：

表1表示符号及其意义

  符号含义  M包含提问答案的所有数据库个数  C_i第i个可供选择的数据库，i＝1，2，...，M

 C  对于一个检索提问可供检索的数据库集合C＝(C₁，C₂，...，C_M) m  最终被选择的数据库个数 C_j’  根据相关度大小，第j个被选择上的数据库，j＝1，2，...，m SC_j’  第j个被选择上的数据库的分值，j＝1，2，...，m C’  所有的被选择上的数据库集合，C’＝(C₁’，C₂’，...，C_m’) n  经过融合排序后的检索结果中，前n个文档 kC_i  检索结果中排在第k个位置的文档出现在第i个可供选择的集合C_i中 kC_j’  检索结果中排在第k个位置的文档出现在第j个被选择的集合C_j’ β  β为权函数中的常参数，为正有理数，此处实例中取β＝1

文档k如果出现在C_i中，在形式上标记为kC_i，其贡献分值记为文档k如果出现在C’_j中，在形式上标记为kC’_j，其贡献分值记为数据库的重要性分值计算公式为：

${\mathrm{SC}}_1^{\prime }=\underset{i=1}{\overset{M}{\max }}\underset{k=1}{\overset{n}{\Sigma }}\frac{1}{{\left({\mathrm{kC}}_i\right)}^{\beta }}---\left(a\right)$

${\mathrm{SC}}_l^{\prime }=\underset{i=1}{\overset{M}{\max }}\underset{k=1}{\overset{n}{\Sigma }}\frac{1}{{({\mathrm{kC}}_i-\underset{j=1}{\overset{l-1}{\Sigma }}{\mathrm{kC}}_j^{\prime })}^{\beta }}2\le l\le m---\left(b\right)$

实施例1

如图2所示，假设n＝10，即取融合排序后的结果中位于前10位的文档。且每个文档用自几的排序号标识。假设有一可供选择的数据库集合：C₁中包含了1，2，3，4文档；C₂中包含了2，3，7，8文档；C₃中包含了1，5，6，7文档；C₄中包含了4，5，6，9文档；C₅中包含了9，10文档。其它数据库中未包含所要求的检索结果，不作选择对象考虑。第k个文档对包含其的数据库的贡献分值为：1/k(此处假设β＝1)选择数据库的过程为：

首先被选择的数据库为：在所有的数据库中，对每个数据库，将包含的特定数据贡献分值求和后找最大值。根据各文档k对数据库的贲统治SC₁’＝max{1+1/2+1/3+1/4，1/2+1/3+1/7+1/8，1+1/5+1/6+1/7，1/4+1/5+1/6+1/9，1/9+1/10}＝{1+1/2+1/3+1/4}。于是最重要的一个数据库也就是第1个被选择的数据为包含1，2，3，4文档的数据库，记为C₁’＝C₁＝{1，2，3，4}。

选择第2个数库：除了已被选出的C₁外，对于剩下的4个数据库中，分别去掉第1次被选择出的数据库中已出现的文档后，再分别进行重要性打分计算。表示第2次选出的数据库是包含1、5、6、7文档的数据库，记为C₂’＝C₃＝{1，5，6，7}。

选择第3个数库：除了已被选出的C₁和C₃外，对于剩下的3个数据库中，分别去掉第1次和第2次被选择出的数据库中已出现的文档后，再分别进行库重要性打分计算。表示第3次选出的数据库是包含9、10文档的数据库，记为C₃’＝C_5.＝＝{9，10}；

选择第4个数库：除了已被选出的C₁、C₃和C₅外，对于剩下的2个数据库中，分别去掉第1次、第2次和第3次被选择出的数据库中已出现的文档后，于是第4个被选择的数据库为包含2，3，7，8文档的数据库，记为C₄’＝C_2.＝{2，3，7，8}。

选择第5个数库：除了已被选出的C₁、C₂、C₃和C₅外，对于剩下的1个数据库中，分别去掉第1次、第2次、第3次和第4次被选择出的数据库中已出现的文档后，再分别进行库重要性打分计算。说明剩下的数据库选择已经没意义，集合选择到此结束。于是被选择出来的数据库共为4个，m＝4。

实施例2

假设取前100个文档，同样每个文档用其在检索结果中的排序位置序号作为其标识。假设有60个数据库可供检索，采用随机数方法，使这60个数据库都随机地包含有这100个文档中的某些。从这60个数据库中根据本发明的方法，在某次随机数产生后，选择出24个优化组合的数据库集合，可供检全这100个文档的同时，被选择的数据库之间彼此覆盖达到最小。实验结果再现了被选中的24个数据库是如何相互补充覆盖这100个文档的。如第一个被选出的数据库，也是最重要一个数据库，实验结果显示，此数据库覆盖了第1，第9，第11，第33，第46，第53，第55，第62，第64，第82，第83，第86，第87，第91，第94和第96个文档。

本发明从大量的、分散和异构的信息资源集合中，选择合适的信息资源子集合，以满足用户的提问，能够搜索到适合的信息，保证一定的查全率和查准率的同时减少计算机计算开销，提高检索效率。