网络搜索结果的主题覆盖度优化研究，本文主要内容关键词为：搜索结果论文,主题论文,网络论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 概述 随着网络搜索研究的深入，相关性已不是搜索和排序模型唯一的优化目标。在相关性的基础上，研究者尝试从两个方面满足用户多样化的需求。一是资源类型，如对“北京”的搜索显示地图、天气预报、网络百科全书和网页等不同资源类型的结果。目前这一领域研究已经较为成熟，主要通过联合搜索实现(如文献[1]和文献[2])。一是主题内容，如对“电纸书”的搜索结果包括有关电纸书的介绍、新闻和阅读器报价等不同的主题。一个实际的网络搜索可能是上述两方面的组合，如对“功夫熊猫”的搜索既包括视频、图片和网页等不同的资源类型，亦包括介绍、新闻和影评等不同的主题。 本文针对信息型网络搜索[3]尝试满足用户多样化的信息需求，提出相关度量指标——主题覆盖度及相应的优化模型，以期针对给定的用户查询，返回尽可能多样的相关主题。 2 相关研究 现有主题建模主要采用主题生成、主题聚类和主题发现三种方式。在Sp
rck等的BM25模型中，参数b是对文档中主题数量的调节变量[4]。推理网络模型的概念表示层的理想状态是独立于内容或段落的主题概念[5]。翟成祥等将最大边际相关(MMR)和最大多样相关(MDR)作为损失函数，嵌入风险最小化检索决策模型。其中，MMR损失函数通过相关性和新颖性的插值，MDR通过主题生成参数τ完成对主题的建模[6]。LDA假设文档由一系列的潜在主题随机组合而成，主题则由词的分布刻画[7]。Wei等将其与语言模型相结合，得到基于LDA的检索模型[8]。Carterette等则借助LDA寻找查询主题的分面[9]。 聚类技术在汇聚相关文档时将相关主题汇聚在一起。Liu等将聚类引入语言模型，使用p(Q|C)代替pML(w[,i]|Coll)部分进行平滑(Q为查询，C为类簇，Coll为文档集合)[10]。Kurland等比较了四种模型：基线系统(仅使用语言模型)、选择模型(聚类仅用于结果选择)、分面模型(聚类仅用于平滑)和混合模型(选择模型和分面模型的插值)，发现类簇数量对选择模型有影响，但是对分面模型影响不大，插值参数的功效在于均衡相关性取值和类簇之间的作用[11]。Wang等将用户的查寻历史聚类，形成不同种类的用户需求，进而将聚类的结果作为分类的依据[12]。Santos等则借助于搜索引擎的提示词[13]、日志或网络分类表[14]等工具寻找一个查询对应的子查询，借助于联合搜索分类的方法提高搜索结果的多样性。Agrawal等从优化搜索结果集合整体出发，通过计算不同类簇与查询的相关性确定搜索结果中主题来源[15]。Mei等通过随机游走引入与连通性有关的变量[16]。 新颖性技术能够发现具有新主题的文档。最大边际相关法对给定的文档集C，查询Q，相关排序R和已提供给用户的子集S，则具有最大边际相关的文档定义为[17]
其中，
(·，·)，i=1，2是相关匹配(相似)函数，λ为插值参数。Allan等为避免仅使用两个句子计算时可能存在的偏差，使用类簇取代作为基准的句子[18]。Yang等针对TDT首次新闻识别任务提出两阶段模型，在每一阶段选择不同的特征[19]。Gollapudi等提出MaxSum和MaxMin两种相关性和新颖性的计算方法，并指出要安排好相关性和新颖性之间的关系[20]。Minack等认为采用后续结果中相关性较低但是差异性较大的文档代替前k项结果中相关性较高的文档可以提高多样性，在MaxSum和MaxMin的度量框架下提出了增量计算方法[21]。Drosou等提出贪婪构造的方法，用以快速地计算多样性(实为新颖性)[22]。 上述研究在引入辅助工具方面的贡献十分突出。例如，引入LDA模型和随机游走，将新颖性纳入研究框架，利用查询日志、提示词和网络分类表等。但是，这些研究没有充分利用相关排序结果固有的结构特征。本文则从相关排序结果的结构特征出发提出排序模型，这是本文的主要贡献和区别于上述研究之处。 3 基本术语 3.1 空间定义
本研究是由约束(1)和优化目标(3)所构成的优化问题。 4 模型 4.1 文档检索的邻域、内部和导集 考察操作序列d→f(d)→g°f(d)。对于给定的文档d，映射f(d)找出文档d包含的主题。进一步，映射g将这一结果映回文档空间，则g°f(d)是与文档d含有共同主题的文档的集合(图1)。显然，文档d与自身拥有共同的主题，即d∈g°f(d)，将g°f(d)定义为d的邻域。从检索的角度考察邻域，文档d的邻域是与文档d有共同主题的文档的集合，是文档间的一种相关。
图1 文档邻域
图2 相关文档集合内部
图3 相关文档集合导集
图4 不同区域的函数 4.2
上的优化 匹配策略建立在文档检索空间结构之上。相对而言，在
内部的情形较为简单，只需一种匹配方法。在
导集上的情形较为复杂，它既需要讨论在
内部与
导集交集的部分，也需要讨论
外部与
导集交集的部分。这两部分需要使用不同的方法计算其对匹配结果的贡献。
函数ρ是一种相关性的衡量指标。ρ不是本文研究的重点，本文选取Indri系统默认的匹配模型[23]。这是因为Indri系统的结果可用作基线系统，与试验系统横向比较。
尽管新颖性算法能够发现新颖的内容，但也存在这些内容与查询不相关的问题。为此，本文采用两种新颖性计算方法。 (1)差集模型。这是相对激进的新颖性算法。这种新颖性算法不考虑新颖部分与查询之间的关系，只要有新颖部分存在，就将它计入新颖性取值。直接也最简单的新颖性方法是计算类簇边界部分的(加权)词频，即文档d与
的核心部分差集的(加权)词频。设标引词
，其(加权)词频为
，则有
其中，
中标引词的数量，作为归一化因子。这一模型的优点是它能够尽可能地覆盖文档之中的主题，但是它无法保证所有的主题均与查询相关。 (2)查询似然模型。这是相对保守的新颖性算法。该算法则需考虑新颖部分与查询之间的关系。一个对象(主要为语段)不仅有新颖的内容，并且它与查询紧密相关，才能得到新颖性取值。具体而言，它计算差集部分生成查询的概率，即
这一模型能够保证计算出的主题与查询相关，也存在排斥大量相关主题的问题。后文将检验这两种方法的具体效果。 最后，将ρ和δ的线性组合作为综合考查一个文档d的指标，选定一个阈值
，则在导集上的文档d被检出的判别条件是
其中，μ，λ∈(0，1)为组合参数，实际经常选取μ=1-λ作为插值参数。 这样可以确定检出集合Z的构成。Z包括两部分：一部分是
，另一部分是满足上述判别公式的
，即
在式中，
是相关文档集合(根据拓扑的定义，它是一个开集)的内部，它起到(通过f)占据最基本的相关主题的作用，是主题度量的基量。
是相关文档集合的导集，导集上文档的邻域起到补充提供相关主题的作用，是主题度量的增量。基量和增量共同作用，提高检索结果的总体主题覆盖度。 4.3 多类簇情形与搜索结果聚类 4.3.1 对多类簇情形的讨论
4.3.2 相关排序结果聚类 下面具体讨论与搜索结果聚类有关的问题，包括：①聚类对象、②类心选取、③类簇形成和④度量的选取。其中，①是搜索结果的特征，②和③的选取与该特征紧密联系。 聚类对象：本文是对搜索结果的联机聚类，所采用的聚类方法要求输入按照相关性排序的列表，按照相关性排序由高到低，依序输入，而非无序文档集合。 类心选取：由于在一个类簇中，相关性最大的文档与查询的相关性越高，因此选择它作为类心可保证类簇与查询的相关性，亦可较好地确定主题的基量。因此，类心选取类簇中相关性取值最高的文档。 类簇形成：类簇形成过程包括初始、聚类和终止三个过程。聚类前，获得相关性列表后，选取一个截断阈值τ，以下为聚类算法(算法1)
度量选取：在聚类过程中，文档之间的相似度(或距离)是决定类簇形状的重要因素。本文采用两种相似度量展开试验，其一，采用余弦相似度[24]；其二，采用KL散度[25]。这两种度量是目前信息检索研究中常用的相似度度量，分别来自于向量空间模型和语言模型，以检验何种空间适用于本文的聚类算法。具体选择何种距离将由试验确定。 5 试验 5.1 试验设定与本试验中主题覆盖度的定义 本文选择TREC 2004年新颖性项目的评测集合。它使用AQUAINT语料集合作为评测文档集合，包括：《纽约时报》(New York Times)1998～2000年的新闻语料、美联社(Associated Press)1998～2000年的新闻语料和新华社1996～2000年的英文新闻语料。 查询集合来自TREC 2004年新颖性评测项目的N51～N100共计50个查询题目。与一般的TREC查询课题不同，除TREC必需的标题(title)、描述(description)和详述(narrative)三个字段外，还有文档字段(〈document〉)。TREC的新颖性项目向各个参赛团队提供相关的文档，对这些文档标引到句子层级。这为建立本文的评价指标创造了可能。 本文将查全率这一概念从文档(网页)层面平移到主题层面，根据(2)式定义主题覆盖度(定义1) 定义1(主题覆盖度，topic coverage) 主题覆盖度是检索到的相关主题集合的势与相关主题全集的势的百分比。 下面进一步定义“相关主题”。TREC 2004年新颖性项目提供了这些参与评测文档中的相关句子[26]和新颖句子[27]，每个被TREC标注为相关或新颖的句子对应一个相关主题，通过统计文档中相关句子数量和新颖句子数量可以求得一篇文档的相关主题数量。这样，根据TREC新颖性项目对相关性和新颖性的标注，本文对相关主题定义如下： 定义2(相关主题，relevant topic) 一篇文档中所包含的与用户查询相关的主题，简称相关主题，是该文档中被TREC新颖性项目标注为相关或新颖的句子的主题。一个被TREC标引为相关或新颖的句子对应一个主题。 注意到对查询相关主题的统计不能重复，因此要根据定义2对具体的计算方法加以说明。相关句子的规模约为新颖句子规模的2.5倍，它导致严重的重复统计；而每个新颖句子对应着一个内容相对独立的主题，使用新颖性标注的结果可以避免重复统计。因此，尽管相关段落中含有查询相关主题，但是考虑到集合运算要避免重复统计，在计算主题覆盖度时，仅统计新颖段落的数量。即，在搜索结果中，新颖段落的数量为相关主题的数量。因此，我们定义相关主题数量为 定义3(查询相关主题数量) 搜索结果中相关主题数量是搜索结果文档中所含的TREC新颖性项目标注为新颖段落的数量。 根据上述可以计算一个搜索结果的主题覆盖度。上述定义适合于实验室中采用TREC新颖性项目的评测设置。 本文的试验过程包括三个步骤： (1)获得基线系统的检索结果列表。首先使用Indri的indribuildindex方法对AQUAINT语料库进行索引，并采用混合平滑模型进行检索(indrirunquery)，得到1000篇文档的检索结果。Adhoc检索过程采用混合平滑模型默认的参数设置(λ=0.4，μ=2500)。进而，将Indri的检索结果与TREC 2004年新颖性项目中的文档进行交集操作，并保持Indri的检索结果的原有排序，得到基线系统的检索结果。 (2)对基线系统的结果列表采用本文提出的模型进行处理，得到面向主题多样性优化的结果列表。 (3)用主题覆盖度评价和比较试验系统和基线系统，分析并讨论优化搜索结果的主题多样性的关键环节和技术。 5.2 试验结果 5.2.1 基线系统 采用Indri的indrirunquery方法得到基线系统。通过统计，得到基线系统的TC@n曲线如图5Indri曲线(实线)。其中，TC@5=24.9％，TC@10=43.3％，TC@15=61.5％。 5.2.2 试验系统 这一小节介绍试验系统的运行结果。第3节给出了两种新颖性方法(差集方法和查询似然方法)和两种聚类度量(余弦相似和KL散度)。本节将上述新颖性方法和聚类度量两两组合进行试验。试验结果按照从坏到好顺序介绍。 (1)查询似然方法。总体而言，使用查询似然方法的两种模型均不理想(表1)。余弦相似和查询似然方法的组合的结果十分不理想。TC@5最高为24.65％(λ=0.4，τ=0.7，N=20)，TC@10为42.18％(λ=0.4，τ=0.7，N=15)，均明显小于基线系统。这一模型不适合用于主题多样性的优化。 KL散度和查询似然方法的组合亦不十分理想，主题覆盖度水平低，TC@5和TC@10较之基线系统只有约1％的主题覆盖度改善，而TC@15又低于基线系统。
以上试验结果说明，查询似然方法对新颖性的计算过于保守，不适合在本试验设置中改善检索结果的主题多样性。 (2)余弦相似与差集方法的组合。这一组试验结果具有相对较好的TC值。其中，TC@5最高为27.48％(λ=0.4，τ=0.6，N=20)，TC@10为46.85％(λ=0.7，τ=0.8，N=20)。这说明余弦相似度和差集方法的组合取得了一定改善的效果。但是，这一效果并不令人十分满意，主要表现在主题覆盖度仍旧不够高；并且优化效果不稳定，一组参数不能达到TC％5、TC@10和TC@15等位点的同时优化。 (3)KL散度和差集方法的组合。这是所有试验中最好的模型组合。其中，有三组参数设置达到了令人满意的效果： 1.λ=0.1，τ=2.2，N=20时，TC@5=28.15％，TC@10=46.43％，TC@15=61.59％； 2.λ=0.4，τ=0.8，N=20时，TC@5=28.15％，TC@10=46.30％，TC@15=62.39％； 3.λ=0.2，τ=2.2，N=20时，TC@5=28.09％，TC@10=46.39％，TC@15=60.12％。 绘制上述三种情况下的主题覆盖度曲线和Indri系统的主题覆盖度曲线如图5所示。在图5所示三条试验曲线中，所有的试验系统曲线均大部在基线系统曲线(Indri)的上方，说明在这三组参数设置下主题覆盖度较之Indri系统的结果确实有改善。并且以λ=0.4，τ=0.8，N=20的曲线和基线的差距最为明显，中间围成的区域饱满，并且试验系统曲线没有明显下凹。
图5 基线系统和试验系统TC@N随N变化曲线 5.3 试验结论 本文在AQUAINT语料库和TREC N51-N100查询课题构成的测试平台上，采用本文定义1所定义的主题覆盖度进行批处理试验与评价研究，主要得出以下四点结论。这四点结论均只在上述试验设定下得到检验。 (1)在合适的模型选取的前提下，本文第3节所提的模型确实能够优化搜索结果的主题覆盖度。 (2)查询似然的新颖性计算方法过于保守，不合适改善搜索结果的主题覆盖度。 (3)KL散度较之余弦相似更适合作为主题覆盖度优化的类簇内文档间相似度。 (4)在KL散度作为类簇的相似度量，差集作为新颖性计算方法的前提下，当聚类阈值为τ=0.8，插值参数λ=0.4，参与聚类的文档数N=20时，可以达到主题覆盖度的最优。 6 结语与展望 本文构造了文档检索拓扑空间、主题检索拓扑空间和聚类检索拓扑空间，在不引入标引、加权和度量的前提下刻画了文档检索拓扑空间和类簇的邻域(微观)和宏观结构。文档检索空间和类簇均可以根据其上的邻域结构划分为内部和边界两部分，其中内部提供主题的基量，边界提供主题的增量。本文的主题覆盖度优化模型通过对基量和增量插值得到。试验结果显示，在合适的模型选取和参数设置条件下，采用AQUAINT语料库和TREC N51-N100查询课题作为试验平台时，本文提出的主题多样性优化模型确实有效。 本文也存在一定的问题。主要包括：第一，本文的试验研究是在改造新颖性测试集合的基础上进行的，改造过程中可能发生偏差；第二，本文试验研究的主旨是说明面向主题覆盖度进行排序的必要要素，而不是找到一个“最好”的方法，因此在试验之中并没有测试太多的成分、方法和参数。后续研究将引入更多的成分和方法，以期得到最优结果。
标签：聚类论文; 相关性分析论文; 网络模型论文; 集合运算论文; 主题模型论文; 组合优化论文;
