集成检索系统中资源选择技术及算法，本文主要内容关键词为：算法论文,检索系统论文,中资源论文,技术论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 导言
集成检索系统是整合系统的一种重要形式，在这种系统中，将检索提问发送至所有数据库分别检索，必然会耗费大量的时间和系统资源，成本较高。为了提高检索的效率，理想的做法是每次只将检索提问发送至可能检索到所需信息的数据库。这就需要在检索之前建立起对数据源的描述，使得集成检索系统能针对用户给定的检索提问，利用所形成的资源描述，选择出与用户提问相关度高的那部分资源作为检索对象，从而提高检索效率[1]。
下面，笔者对近年来出现的主要资源选择技术的基本思想及算法逐一进行介绍。
2 基于资源相关度排序的资源选择技术
基于资源相关度排序的资源选择技术是在对资源进行描述的基础上，计算特定检索提问与各资源的相似度，按相似度对资源进行排序，选取一定数量的排在前面的资源进行检索。
基于资源相关度排序的资源选择技术以基于提问取样(query-based sampling)方法建立起的资源描述为基础。基于提问取样是目前普遍采用的一种资源描述技术，其基本方法是：首先定义期望的结果数量N和初始词汇库V(仅包含种子检索词t)；用单一检索词t在数据库中进行查询，分析返回的前n个结果，将结果中包含的词汇加入词汇库V；从V中随机抽取检索词，重复查询并对V进行更新，直到返回的结果页面数量达到预先定义的N值。这样，最终返回的结果文献具有较强的代表性，将此作为该资源的一个样本，可以对其进行分析、标引，从而建立起对资源的描述，包括样本文献数量、文献中所含词的倒排档、各词的文献频率统计等。
典型的基于资源相关度排序的资源选择算法有gGlOSS、CORI等[2]。
2.1 gGlOSS算法
gGlOSS算法[3] 是在Gravano等人提出的用于布尔检索模型的资源选择算法GlOSS(the Glossary-of-Servers Server)的基础上发展起来的，用于处理向量空间信息检索模型。事实上，这一算法能够广泛应用于各类信息检索模型。
gGlOSS用“goodness”来描述各资源与特定检索提问的切合度，因而各提问的goodness值能够在很大程度上反映资源的内容特征。gGlOSS方法计算每一个资源Ri关于特定检索提问q的goodness，根据goodness来对各资源进行排序。每个Ri的goodness定义如下：
附图
其中，Sim(q，d)是计算提问q和文献d相似度的函数，l是一个预先设定的阈值。根据资源的goodness(l,q,R[，i])，将其进行倒排，则排在前面的资源与检索提问相关度较高，即包含有较多数量的相关文献。
gGlOSS方法中计算文献与提问相似度需要两个基本信息，即资源R[，i]中含有词t[，j]的文献频率df[，tj]和资源R[，i]中每个词t[，j]的权重之和，该信息一般从资源描述中获得。
2.2 CORI
CORI[3-6] 被公认为众多资源选择算法中最稳定且效率最高的一种。它采用信息检索中的贝叶斯推论网络模型(Bayesian Inference Network model)，在基于提问取样方法建立起的资源描述基础上，构造资源选择索引。每一个资源R[，j]用一系列节点(即标引词)r[，j]来描述，信息需求由一个或几个检索提问q来表达，检索提问一般由检索词c[，k]和检索运算符组成。
CORI方法通过计算检索提问在各资源中的概率P(q｜R[，j])来反映资源与提问的相关度。由于检索提问q由单检索词c[，k]组成，因而要首先计算概率P(c[，k]｜R[，j]，其定义如下：
附图
其中，df为资源R[，j]中含检索词c[，k]的文献数，cf为含有检索词c[，k]的资源数，C为备选资源总数，cw为资源R[，j]中的词汇数量，
为备选资源的平均词汇数量，b为一个默认的概率值，一般情况下设为0.4。
概率P(q｜R[，j])与检索提问q的结构有关，但一般情况下可以用P(c[，k]｜R[，j])的平均值来表示。根据计算出的P(q｜R[，j])对各资源进行倒排，排在前面的资源与检索提问具有较高的相关度。
3 基于文献分布状况的资源选择技术
大量实验表明，将gGlOSS、CORI等算法运用于一系列小型数据库是非常有效的，而对于大型数据库，由于准确获得各词的文献频率需要付出较高的成本，其效率会明显下降。针对这种情况，人们提出了基于文献分布状况的资源选择技术。
基于文献分布状况的资源选择技术[7] 一般也用基于提问取样方法进行资源描述，通过分析样本文献集中相关文献频率，直接计算各资源中相关文献分布状况，并按相关文献分布率排序以进行资源选择。此类资源选择技术以ReDDE(Relevant Document Distribution Estimation)为代表。
ReDDE资源选择策略首先也要采用基于提问取样(query-based sampling)技术建立资源描述，在此基础上运用Sample-Resample方法计算资源库的大小，计算方法如下：
N[，Rj]=(df[，qirj][*]N[，rj-samp])/(df[，qirj-samp])
其中，N[，Rj]为资源R[，j]的大小(未知)，r[，j]-samp为资源描述的样本文献集，N[，rj-samp]为样本文献集的大小，df[，qirj]为R[，j]中含词q[，i]的文献数量，df[，qirj-samp]表示样本文献集r[，j]-samp中包含词q[，i]的文献数量。
ReDDE方法分别计算各资源R[，j]中与检索提问q相关的文献数量Rel_q(j)，再利用Rel_q(j)计算与q相关文献的分布状况Dist_Rel_q(j)，据此对资源进行排序。其基本计算方法如下：
附图
(1)中P(rel｜d[，i])表示特定文献与检索提问的相关性概率，在ReDDE算法中，设定检索提问q是在全部资源中检索，返回的结果文献按相关性排序，则每篇文献均有一个等级值，表示为Rank_central(d[，i])，计算如下：
附图
其中Nr(d[，j])表示集中完全数据库中含文献d[，j]的数量，Nr(d[，j])_samp表示在资源样本文献集合中包含文献d[，j]的数量，Rank_samp(d[，i])表示文献d[，j]关于提问q在资源样本文献集合中的等级值。
在此基础上，文献相关概率可由分步函数表示如下：
附图
该函数的含义是排在前面的文献的相关概率是一个正常数，而其他文献相关概率则为0。ratio是一个阈值，它揭示了资源库中待处理的文献集合，如选取ratio=0.003，相当于考虑包含1000000篇文献的数据库中的前3000篇文献，N[，all]是所有备选资源中的文献总量，C[，q]为控制常数。
将计算出的P(rel｜d[，i])代入公式(1)，计算出每个资源对于检索提问q的相关文献数量Rel_q(j)，进而利用公式(2)计算出R[，j]的相关文献分布概率Dist_Rel_q(j)，据此对资源进行排序，推荐适当的资源作为集成检索的对象。
4 基于检索成本计算的资源选择技术
基于资源相关度排序的资源选择技术属于传统的资源选择技术，如gGlOSS、CORI算法等，它们都是以资源与检索提问之间的相关程度为标准来进行资源排序和选择的。而基于检索成本计算的资源选择技术提供了另外的一系列标准，其中最具代表性的就是DTF(Decision-theoretic Framework)框架，它根据不同的检索影响因素，如检索质量、花费时间或数据库成本等，计算最小检索成本，以此为依据进行资源的选择。
DTF的基本思想为[8-9]：为每一个资源DL[，i]分配详细的检索成本C[，i](s[，i]，q)，其中s[，i]是对于提问q所检索的文献数量。这里的“成本”是一个广义的概念，除了金钱成本外，还包括时间、质量等其他成本因素。用户根据其检索提问q，需要在所有资源中检索出数量为n的文献，则需计算资源选择的最优解决方案，例如用一个向量空间
=(s[，1]，s[，2]，…，s[，m])[T]，
来表示对于提问q的资源选择方案，即在每个数据库资源中所检索出的文献数量分布情况(共有m个数据库资源)，则此资源选择方案须具有最小的检索成本：
附图
对于检索成本C[，i](s[，i]，q)的计算需要考虑多个方面：
· 资源效用成本：即资源与文献的相关程度，这是最重要的成本因素，用C[，i][rel](s[，i]，q)表示。
· 时间成本：包括在数据库中的检索计算时间以及结果文献在网络中进行传输的时间，用C[，i][time](s[，i]，q)表示。
· 金钱成本：即数据库的使用费用。一些数据库的使用是要收取费用的，该使用费对于用户来讲是一项比较重要的开销，用C[，i][money](s[，i]，q)表示。
以上各种成本必须在检索之前计算得出，才能保证资源选择的有效进行，但资源效用成本(如相关文献数量)是无法在检索之前得出的，因此，可用期望成本EC[，i](s[，i]，q)来代替C[，i](s[，i]，q)，设C[，t]、C[，m]分别代表时间成本和金钱成本的参数，则期望成本EC[，i](s[，i]，q)的计算公式如下：
EC[，i](s[，i]，q)=EC[，i][rel](s[，i]，q)+C[，t][*]EC[，i][time](s[，i]，q)+C[，m][*]ECi[money](s[，i]，q)
其中，EC[，i][rel](s[，i]，q)为期望资源效用成本，EC[，i][time](s[，i]，q)为期望时间成本，EC[，i][money](s[，i]，q)为期望金钱成本。
这样，资源选择方案须具有最小的期望检索成本，公式(3)转换为：
附图
5 基于资源内容等级结构的资源选择技术
基于资源内容等级结构的资源选择技术(selecting databases hierarchically)[10] 的基础为资源内容描述的树状等级结构(topic categories)，这种等级结构是一个类目体系。在进行数据库资源描述时，应用基于提问取样的资源描述技术，通过调焦提问探测算法(focused probing)[2]，建立数据库的样本文献集、词频统计等相关描述信息，并将数据库归入类目体系中的某一子类目下。这样，每个数据库都被归入某个类目体系的不同子类目下，使得数据库的内容描述具有一定的层次性。这种数据库资源描述结果如图1所示：
附图
图1 数据库资源描述等级结构图
基于资源内容等级结构的资源选择技术将同在一个类目下的数据库内容描述进行合并，作为一个大的“数据库”，并计算这个类目与某提问式之间的相关程度。
设类目C下有数据库db[，1]，……，db[，n]，有下列几个参数：
·NumDB[，s](C)：C类目下的数据库数目；
·NumDocs(C)：即C类目下数据库中包含文献的总数量，NumDocs(C)=
NumDocs(db[，i])；
·ActualDF[，est](w)：C类目下数据库中包含词w的文献的数量；
·ActualDF[，est](w):ActualDFest(w)=(ActualDF[，est](w)fordb[，i])。
然后，针对每一个类目层次，应用CORI、gGlOSS等算法计算该类目下层各子类目与提问的相关程度。根据计算结果，再选择其中一个子类目，进行其下层子类目的递归计算。这种分层次的资源算法有很多种，这里介绍其中的一种。
设分层次算法为HierSelect(Query Q,Category C,int K)，即输入提问式Q，选择出K个数据库(设K=3)，算法描述如下[10]：
·步骤一：以位于最上层的C类目为入口，应用CORI、gGlOSS等算法计算其子类目与提问Q之间的相关程度。例如根类目C下有arts、computers、health、sports子类目，分别包括35、55、25、21个数据库，应用CORI或gGlOSS算法，计算得出表示子类目与提问式Q相关程度的值分别为0.0、0.15、0.10、0.93。
·步骤二：如果相关程度存在非0值，则选出值最大的子类目C[，j]，进入步骤三，在此例中选出sports子类目。如果相关程度值均为0，则应用CORI、gGlOSS等算法计算C类目下各数据库与Q的相关程度，进行排序，选择前K个数据库作为返回结果。
·步骤三：如果C[，j]中包含的数据库数量大于或等于K，则选择C[，j]，继续计算C[，j]下层子类目与提问式Q之间的相关程度，按照步骤二进行判断；否则，应用CORI、gGlOSS等算法计算与C[，j]同层次的其他子类目下各数据库与提问式Q之间的相关程度，选择K-NumDBs(C[，j])个数据库，再加上C[，j]中包含的数据库，作为目标数据库。
在此例中，由于K为3，sports子类目中包含有21个数据库(大于K)，则计算sports的下层子类目与提问式Q之间的相关程度。sports下有basketball、hockey、soccer三个子类目(分别包括7、8、5个数据库)和ESPN数据库，它们与提问式Q之间的相关程度分别为0.78、0.08、0.12、0.68。因此，选出相关程度最高的basketball子类目(相关程度为0.78)，继续进行步骤三的计算。
此时，如果K取值为10，由于basketball子类目只含有7个数据库(小于K)，则应用CORI、gGlOSS等算法分别计算hockey、soccer子类目下数据库以及ESPN数据库与提问式之间的相关程度，选择排序靠前的3(K-NumDBs(Basketball))个数据库，加上basketball子类目下的7个数据库，作为返回结果。
6 简要评价
资源选择是集成信息检索的一项关键技术，不同的资源选择策略虽然采用不同的数学模型，各有侧重，但其基本原理都是考虑检索提问在各资源中的相关文献数量及文献的相关程度，以此为标准对资源进行排序，选择出包含较多相关程度较高文献的最恰当的资源，从而提高集成信息检索的效率及自动化程度。
gGlOSS、CORI等基于资源相关度排序的资源选择技术发展较早，是传统的资源选择策略，其算法比较简单，但需准确计算词汇的文献频率，因而效率有限，在小型数据库的资源选择中应用能够取得比较好的效果。
基于文献分布状况的资源选择技术针对上述资源选择策略的不足，通过分析与检索提问相关文献在样本文献集合中的频率，直接计算资源中相关文献的分布状况，其算法中对结果文献的排序，能够极大地提高检准率，从而提高检索效率，因而可以应用于大型数据库的资源选择。
基于检索成本计算的资源选择技术DTF考虑的因素比较全面，传统的提问与资源的相关程度只是众多因素中的一种，数据库成本、检索时间等因素也对资源选择造成一定的影响。DTF将这些因素看成有机的整体，综合考虑了其在资源选择过程中的影响程度。
基于资源内容等级结构的资源选择技术将每个类目下的数据库融合在一起，将每个类目看成一个大的“数据库”，有效地弥补了数据库内容描述方面的误差，因此采用基于资源内容等级结构的资源选择技术能够大大提高检索效率。实验表明，应用基于资源内容等级结构的资源选择技术，对比单纯应用基于资源相关度排序的资源选择技术，其检准率至少可提高50％。
随着集成信息检索系统的发展，已经出现了许多资源选择技术，这些技术基本是对文本型数据库进行选择，多媒体信息技术的发展使得集成信息检索的对象扩展到音频、图像/图片、视频等多媒体信息，因而多媒体数据库的资源选择成为一个新的研究热点。同时，研究人员也在不断改进和探索高效率的资源选择策略，以提高集成信息检索系统的检索效率。