一种基于层次结构子话题的搜索结果多样化排序方法
一种基于层次结构子话题的搜索结果多样化排序方法
【技术领域】
[0001 ]本发明涉及一种基于层次结构子话题的搜索结果多样化排序方法。
【背景技术】
[0002] 互联网信息越来越全面的覆盖了人们的日常生活，用户逐渐习惯依赖于搜索引擎 来查找自己需要的信息。大量研究表明，在提交给搜索引擎中的查询中，有相当部分的查询 是短文本查询。这些短文本查询由于信息量少，在解释用户意图时，通常是有歧义的，或者 有多重含义的。常见的有歧义的查询，例如，搜索"苹果"，有的用户可能是在找关于著名的 苹果公司的相关信息，有的用户则是关心水果苹果相关的信息;搜索"人大"，某些用户可能 是在找关于著名高校中国人民大学的相关信息，某些用户查找的则是全国人民代表大会的 相关信息。而多重含义的查询，是指在该查询下常包含了多个领域，例如，搜索"红楼梦"，用 户实际是想找与该查询相关的一个具体领域，如"红楼梦电视剧"，"红楼梦著作"，"红楼梦 人物"，"红楼梦明星"等。搜索结果多样化技术旨在解决上述问题。
[0003] 目前，搜索结果多样化方法可以划分为两大类：隐性（implicit)方法和显性 (explicit)方法。早期的多样化技术大多属于隐性多样化模型，其中最有影响力的工作之 一是Carbone 11和Go Ids te in在1998年提出的MMR算法。这类隐性方法认为，如果两个文档 (搜索结果)的文本内容越相似，则这两个文档涉及的话题越相似，冗余性越高。如果能减少 排序中的冗余文档，即可提高排序的多样性。于是，在多样化重排序时，隐性方法侧重于比 较文档间的相似度，将更新颖的文档排在前面，从而实现搜索结果多样化。但是，由于该类 方法在多样化时只完成了冗余处理，没有明确查询的用户意图。因此，该方法不知道哪些用 户意图更应该被覆盖，不能有目的地完成多样化，其效果有限。
[0004] 显性方法又称为基于子话题的方法，是目前搜索多样化技术的主流。该类方法明 确地利用子话题模拟用户意图，并通过子话题对搜索结果进行多样化。显性方法认为，两个 文档覆盖的子话题的相似性即为两个文档的相似性，而一个更多样化的文档排序应该在有 限的结果中覆盖尽可能多的子话题。
[0005] 在现有的显性方法中，一个查询的用户意图通常表示为一个子话题列表形式，其 中每个子话题对应一个用户意图。对于一个查询，获取相关子话题列表的方法有很多，包 括:用查询的分类信息作为子话题，巧用搜索引擎获取相关子话题，分析结果文档的短语或 词组生成子话题，或者联合多个外部资源生成组合子话题等。例如，用Google的查询推荐和 相关查询来代表查询的用户意图；从比较相关的检索文档中抽取单词和短语生成查询意 图。从四类不同类型的数据中挖掘子话题。
[0006] 在搜索结果多样化方向的国际竞赛或评测任务中（如TREC Web Track的 Diversity task，和NTCIR的Intent\IMine task)，查询的子话题由标注人员的主观标注确 定，视为真实的用户意图。多样化算法中使用的子话题应该尽可能地贴近真实用户意图，方 能得到让真实用户满意的多样化结果。然而，由于多样化算法中的子话题是根据查询自动 地生成的，很难完美地和真实的用户意图相匹配。而目前多样化方法中主要采用列表形式 的子话题，很难找到合适粒度的子话题能够完美匹配真实的用户意图。而真实的用户意图 本身则是隐含逻辑的层次结构。
[0007] 因此，如何解决上述问题成为本领域技术人员亟需解决的技术问题。
【发明内容】
[0008] 针对【背景技术】中存在的问题，本发明的目的在于提供一种基于层次结构子话题的 搜索结果多样化排序方法，该方法定义了查询的层次结构子话题，以及多层子话题和查询、 文档间的相关性推算方法，基于该层次结构子话题的搜索结果多样化算法，能够灵活地利 用不同粒度的子话题，更准确地匹配真实用户意图，从而提高搜索结果的多样性。
[0009] 本发明的目的是通过以下技术方案来实现的：
[0010] 一种基于层次结构子话题的搜索结果多样化排序方法，所述方法包括如下步骤： [0011] 1)定义查询词的层次结构树状子话题的表示方法；
[0012] 2)对层次结构子话题和查询、文档的相关性进行估算；
[0013] 3)建立基于查询词的层次结构子话题的搜索结果多样化模型；
[0014] 其中，所述步骤3)通过两种排序方法的任一种实现：
[0015] a)排序方法一:根据层次结构话题新颖性模型对文档进行多样化排序；
[0016 ] b)排序方法二:根据层次结构话题比例模型对文档进行多样化排序。
[0017] 进一步，所述步骤1)中层次结构子话题的表示方法具体为：
[0018] (1)对于每个新闻搜索词q，在搜索引擎中抽取其查询推荐词作为该搜索词的第一 层子话题，表示为{ tl，t2，t3，. . . };
[0019] (2)对于第一层子话题t，在搜索引擎中抽取其查询推荐词为该子话题的子话题， 作为搜索词的第二层子话题，表示为. . .};
[0020] (3)对于第j层子话题％,..?，在搜索引擎中抽取其查询推荐词为该子话题的子话 题，作为搜索词的第二层子话题\,& 3,...};
[0021] 上述子话题的生成方式并不局限于搜索引擎的查询推荐。
[0022] 进一步，所述步骤2)具体为：
[0023] (1)对于层次结构子话题树内部，定义父亲子话题在该查询词中的重要程度可以 由其所有孩子子话题完全覆盖，
[0024] (2)定义层次结构中每个子话题和查询的相关性概率的推导方式为：
[0025] (3)定义层次结构中每个子话题和文档d的相关性概率的推导方式为：
[0026]进一步，所述步骤3)中涉及的多样化排序方法，其基本步骤为：
[0027] (1)遍历所有待排序文档，根据算法策略选择当前多样性最佳的文档；
[0028] (2)将当前最佳文档加入已选文档列表；
[0029 ] (3)重复上述步骤，直到已选文档的数目符合要求；
[0030] (4)文档的选择顺序即为最终输出的文档排序，即搜索结果多样化排序。
[0031 ]进一步，所述步骤3)中算法a)层次结构话题新颖性排序方法，其最佳文档的选择 策略为：
[0032] (1)对于层次结构子话题中的第j层子话题，考虑该层子话题本身的重要性，子话 题被已选择文档集D覆盖的情况，以及子话题和待选文档d的相关性，计算文档d在该层子话
[0033] (2)综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性
，此时 各层子话题的贡献由参数α控制；
[0034] (3)选择整体多样性?(d，D)最大的文档为当前最佳文档。
[0035] 进一步，所述步骤3)中算法b)层次结构话题比例排序方法，其最佳文档的选择策 略为：
[0036] (1)对于第」层子话题，考虑该层中每个子话题本身的重要性「(~1,.. !:;10，以及 子话题被已选择文档集D覆盖的情况，计算子话题％,尚未被满足的份额
[0037] (2)对于第j层子话题，选择份额最大的子话题为该层的最佳子话题
[0038] (3)计算文档d在第j层子话题上的多样性此时重点考虑文 档d和该层最佳子话题^的相关性，同时也考虑文档d和该层其余非最佳子 话题的相关性，以及该层最佳子话题与其余子话题的关系KWh,.,ip，即
[0039] (4)综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性
*此时 各层子话题的贡献由参数α控制；
[0040] (5)选择整体多样性?(d，D)最大的文档为当前最佳文档。
[0041] 本发明具有以下积极的技术效果：
[0042] 本发明的方法可以获得更多有效的词项列表，在得到补充后的词项列表之后，对 新的词项列表进行打分，将相似的词项列表进行合并分类，计算不同的查询分面、词项列表 的重要性，最终使得挖掘出的查询维度更加完善，使得用户可以获得更为完整的信息。
【附图说明】
[0043] 图1是查询"defender"的两层结构子话题；
[0044] 图2是层次结构子话题树示意图。
【具体实施方式】
[0045] 下面结合附图和【具体实施方式】对本申请作进一步的说明。
[0046] 定义层次结构子话题的表达方式和相关概念：
[0047] 对于一个给定的查询q，我们用. . .，dm}表示最初的尚未多样化的文档 集合，用Tq={ti，t2, . . .，tn}表示查询相关的η个子话题集合。给定P(d|q)代表文档d和查询 q相关的概率，P(d|t)代表文档d和子话题t相关的概率，P(t|q)代表子话题t在查询q中的重 要程度。目前大部分基于子话题的多样化算法，利用T q、P(d | q)、P(d 11)、P(t | q)对初始文档 R进行重排序，得到多样化后的结果文档，记为D。在层次化的多样化模型中，由于多层子话 题的引入，本发明需要对上述子话题形式和概率进行重新定义。
[0048]层次结构子 话题的定义：
[0049] 本申请用1\1=^1，乜，...}表示查询(1的第一层子话题集合{匕1}，其中1 1代表子话 题t在集合Tq的位置（ii = l，2,...）。同理，1?二…}表示子话题\的所有孩 子子话题(第二层)的集合{tw2}，其中i 2代表子话题在集合τ?ι中的相对索引编号。以 此递推，我们用.,?代表层次结构中第j层子话题，用代表其孩子子话题(第j+Ι层） 的集合，其中子话题子话题在第j+Ι层上的第ij+1个孩子子话题。
[0050] 如图2所示，其展示了一个两层结构的子话题示例。第一层包含两个子话题t#Pt2， 第二层有四个子话题1：1,1，1：1,2 42,1和七2,2。其中，1：1,1和1：1,2是1：1的孩子话题42,1和七2,2是七2的 孩子话题。上述关系可以表不为1'1={1：1,1，1：1,2}和了2={^2,1山,2}。
[0051 ] 本申请使用图1中的查询"defender"来解释上述形式化定义。子话题"defender windows"有三个孩子子话题："defender windows home"代表用户希望访问软件主页， "defender windowsdownload"表不软件的下载需求，"defender windows problems"显不 用户对软件的各种问题感兴趣。同样地，第一层子话题"defender arcade game"和 "defenderland rover"都有各自的第二层孩子话题。注意，单词级别的多样化模型也有类 似的表达形式，将一个子话题表不为包含多个单词的一个集合= {^丨…|_。与 本申请的方法不同的是，该模型并不考虑子话题U和单词tj.之间的关系，而将每个单词tj视 为一个独立的子话题，然后把所有单词其合并起来形成一个更大的单词子话题集合
相比之下，本申请保持了完整的层次结构子话题树， 并以此为依据对文档进行多样化。
[0052]层次子话题的概率计算：
[0053]
是描述子话题在其双亲子话题hbij中重要程度的概 率。假设可以被其孩子子话题集合全覆盖，且每个孩子子话题之间相对独立。 由此可以得到：
[0055] 在图2中，可得:P(tl，l I tl)+P(tl，2 I tl) = 1，P(t2，l I t2)+P(t2,2 I t2) = 1。
[0056] Pd+lg) :是描述子话题ij在查询q中的重要性。在多层子话题中，此概率的 计算方式受子话题的生成方式影响。若已知叶子话题的重要性(例如，双亲子话题是由孩子 子话题聚类生成），双亲子话题的重要性可由其孩子子话题的重要性相加得到，由此迭代找 到所有子话题的重要性。
[0058]在另一种情况下，可能只知道第一层子话题的重要性。例如，在利用Google Suggestions生成多层结构子话题时，必须先得到第一层子话题，然后才能将其输入检索框 能找到第二层子话题。此时，可以利用贝叶斯公式计算每个孩子子话题的重要性：
[0060] 在图2中，若已知P(t1;1|q)和P(t1>2|q)，则？(七七）=?(七 1,七)+卩(七1,七）；若已知？ (ti|q)JlJP(ti，i|q)=P(ti|q).P(ti，i|ti)，P(ti，2|q)=P(ti|q).P(ti，2|ti)。
[0061] 代表文档d满足子话题1,?的概率。由于PM:l 也可以记为本申请默认叶子话题为单词或短语的形式，于是叶子 话题和文档的相关概率ρ(引?;)可用语言模型或其他检索模型直接计算得到。然而，非 叶子话题不一定是单词或短语的形式，他们可能是一组子话题的集合(例如，将原始Google Suggestions作为第二层子话题，将其聚类信息视为虚拟第一层子话题）。考虑到此类情 况，本申请使用一个自底向上的方法来递归地生成子话题和文档相关的概率，具体公式如 下：
[0063] 上式中，（1 - 是文档d不满足子话题^七的概率，其乘积代表d不 满足~,+.的所有孩子子话题的概率，则1-π (...)表示d满足至少一个的孩子子话题 的概率。
[0064] 话题新颖性模型：
[0065] 话题新颖性模型（topic novelty model)起源于经典MMR算法，是目前被广泛接受 的一个多样化算法框架。其基本思想是，在排序中同时考虑文档与查询的相关性和文档之 间的新颖性。具体到每次的文档选择时，它倾向选择既与查询相关，并与已选择文档尽可能 不相关的文档。其公式如下：
[0067]其中，?(d，D)代表文档d与已选择文档集D不相关的概率，即该文档的新颖性(又 称多样性），在不同的算法中有不同的定义。本申请选择了著名的xQuAD算法，作为层次化模 型的基础。xQuAD显示地利用文档在子话题上的覆盖情况来计算文档的多样性。
[0069] 上式中，（l-PU' I t))表示已选择的某个文档不满足子话题t的概率，其乘积 Π dkD(...)表示所有已选文档D不能满足t的概率。再考虑查询相关所有子话题的情况，以 及子话题的权重P(t|q)，上述多样性?(d，D)代表了当前文档d满足而已选文档不满足各个 子话题的概率。
[0070] 然而，公式(4)是针对列表形式存在的子话题设计的，在处理层次结构的用户意图 时可能并不适用。以图2所示的用户意图为例，假设文档cU和山与子话题t 1;1相关，文档d3和 子话题t1>2相关，文档d4和子话题t 2>1相关，需要对文档进行多样化排序。一个理想的排序为 cU-ck-cb-cb，其多样性在每次选择中均为最大。如果只使用第一层子话题，xQuAD可能输 出排序cU-ck-cb-cb，因为此时子话题较粗糙，无法区分文档山和山的细微差别，认为其均 与ti相关;如果只使用第二层子话题，xQuAD可能输出排序cU-cb-cU-cb，因为此时子话题 太细，认为d 3与d4相对于cU都是同样新颖，并不知道d3与cU都和子话题相关，而d 4才是真正 全新的选择。
[0071] 为了解决上述问题，本申请改进了 xQuAD的整体框架，提出了一个能处理多层子话 题的层次结构话题新颖性模型(Hierarchical xQuAD，HxQuAD)，可以显示地利用层次结构 的子话题来解决搜索结果多样化问题。在计算文档多样性时，HxQuAD会对层次结构中的每 层子话题独立地估算文档在该层的多样性。文档在子话题树中第j层的多样性计算如下：
[0073] 其中，| h，.山| = j表示子话题位于子话题树中的第j层，P 描述 在查询q中的重要程度，而P p 则代表d满足子话题々的概率，通过自底向
该局部多样性 〇(d，D，j)估算的是文档d在第j层子话题中多样性。
[0074] 然后，本申请把所有局部多样性整合起来，以评估文档在所有子话题层（即整个子 话题树)上的多样性。我们引入参数α来控制每层子话题（即子话题粒度)在判断多样性时的 贡献。具体做法如下面公式：
[0076]上式中，α的取值范围为（0，1]。当α = 0.5时，每层子话题在计算多样性时同等重 要；当α>0.5时，算法更看重文档在较粗粒度子话题上的多样性；当α〈0.5时，算法则更偏向 于文档在较细粒度子话题上的表现。特别地，若a = 1，则算法只使用第一层的子话题;反之， 若α接近于0,则算法倾向于只考虑最底层的叶子话题。注意，如果子话题树只存在两层结 构，α的最小值可以为0。
[0077]简而言之，HxQuAD将xQuAD的传统多样性计算改进为处理单层多样性的局部多样 性计算，在此基础上提出可处理层次结构子话题的多样化模型。HxQuAD包含两个参数:传统 子话题新颖性模型必有的用于平衡文档相关性和新颖性的参数λ，和多层结构模型特有的 用于控制子话题层次影响的参数α。
[0078] 话题比例模型：
[0079] 话题比例模型（topic proportionality model)通过子话题的比例对文档进行排 序，其特点是将多样化中的文档选择划分为两个步骤:选择子话题和选择最佳文档。在每次 迭代中，该模型首先根据子话题比例策略选择最佳子话题，然后根据当前最佳子话题寻找 最相关的文档。
[0080] PM2是话题比例模型的代表算法。它将搜索结果多样化问题类比为政治选举中的 党派席位分配问题，认为既然选举中的席位应该满足党派受到选票的比例，则文档的多样 化结果应该满足子话题的分布比例。它参考选举中使用的圣拉古计算法(Sainte-Laguel)， 用其席位分配方法模拟子话题的选择。在每次排序迭代中，PM2首先根据Sainte-Lague公式 计算当前子话题ti需要改善的分布比例，记为子话题的份额qti(quotient):
[0082]为了使已选文档中的子话题分布与原始文档的整体子话题分布尽可能一致，PM2 选择当前最大份额的(待改善程度最大的)子话题，作为当前最佳子话题然后，它计算多 样化函数?(d，D，t，，找到与最佳子话题f最相关，与其他子话题较相关的文档，作为当前 最佳文档cf。
[0084] 其中，Φ (d，D，t*) =λ · qti* · P(d | ti*) + ( 1_λ) · Σ i在i*qti · P(d | ti) (8)
[0085] 在文档cf加入 已选文档集D后，为了惩罚cf的相关子话题，PM2在每个子话题中计算 (f占用的比例，作为当前已占有的席位 Sl(seat)。
[0087]该算法重复上述过程，每次迭代时从R中选择最佳文档cf加入D。
[0088]在本申请中，我们改进了PM2的基础框架，提出了可处理树状结构子话题的层次结 构话题比例模型(Hierarchical PM2 model，冊]?2)。冊]\12保留了原模型PM2的核心思想，即 根据预选的最佳子话题选择最佳文档。与之不同的是，
[0089]------------------在层次结构的子话题树中，每层的子话题可能包含不同粒 度的多样化信息，对于每层的子话题，HPM2都能根据当前子话题比例找到一个该层最佳的 子话题。最后，HPM2综合考虑文档与各层最佳子话题的关系，选择最佳文档。以图2中的子话 题树为例。我们根据子话题比例，可能选择第一层的最佳子话题为ti，选择第二层的最佳子 话题为t 1;1，然后寻找和最相关的文档为最佳文档。注意，由于每层最佳子话题在选 择时相互独立，有时我们也可能选择tdPt2>1为第一层和第二层的最佳子话题。HPM2的具体 过程如下：
[0090]首先，对每层的子话题，HPM2计算该子话题在对应子话题层中的份额，作为当前子 话题在该层的比例，记为?。对于第j层的子话题，.心，其份额的具体计算方式类似 公式(7)，具体如下。其中PCtL.+ lq)代表满足q的概率。
[0092] HPM2比较第j层上的所有子话题的份额，选择份额最大的子话题为该层最佳子话 题，记为€,.心。同理，4，《七，…，分别表示从子话题树的第1层，第2层，…，第 η层选出的该层最佳子话题。对于每层子话题，HPM2计算文档与该层最佳子话题和其他子话 题的相关程度，代表文档在该层子话题的多样性。
[0093]对于第j层的子话题，根据ΡΜ2定义的多样化表达，一个多样化的文档应与该层最 佳子话题$,.,?尽可能地相关，与该层其他子话题％(丨到=/,? 比较相关。 ΗΡΜ2定义^(么^ ^为文档d在第j层子话题上的多样性，如下：
[0095]上式中，函数来表达子话题tk和最佳子话题々之间的依赖关系。
[0096] ΗΡΜ2引入该函数的原因是，由于子话题树独特的层次结构，同层的非最佳子话题 与最佳子话题的关系是存在亲疏远近的，需要不同对待。在层次结构中，如果子话题t与最 佳子话题f同属一个双亲子话题，则相比于该层的其他子话题，t与f更相关。仍然以图2的 子话题树为例，如果t 1;1是选中的最佳子话题，是决定文档多样性的关键，由于t1>2与t1;1关 系紧密（同双亲子话题），则讧 2显然比t2,#Pt2,2更重要。因此，在文档多样性的计算中，HPM2 应该给t 1>2更高的权重，以示其与t2,#Pt2,2的区别。具体地，每个非最佳子话题的权重，由其 与最佳子话题在层次结构中的距离来决定。函数的相关公式如下：
[0098]其中，dis(t，t，是子话题树中从t到f的路径距离。由于两个第j层子话题的最大 距离为2j，我们在公式中用2j对距离做归一化处理。继续讨论图2的例子，我们得到P(t211〇 =(2 · 1-2+1)/(2 · l) = 0.5,P(ti;2|ti;i) = (2 · 2-2+1)/(2 · 2) =0.75 ,P(t2>21 ti,i) = (2 · 2-4+1)/(2 · 2)=0.25。
[0099]更进一步地，本申请综合考虑文档在每层子话题中的多样性，然后根据下列公式 选择最佳文档cf。其中，参数ae(〇，l]用于控制子话题粒度(子话题层)在多样性中的影响， 类似公式(5)。
[0101]最后，HPM2基于选择的最佳文档cf，更新其相关的子话题的比例，具体公式如下所 示。注意，由于层次结构中各层的子话题比例相对独立，子话题的比例是逐层统计，子话题 比例的更新也是在每层上完成。
[0103] 简而言之，HPM2的工作过程是:根据每层子话题比例选择该层的最佳子话题，结合 所有最佳子话题计算多样性并选择当前最佳文档，基于当前文档和子话题的关系逐层更新 子话题占有比例。与PM2中只考虑一个最佳子话题不同，HPM2需要为层次结构中的每层子话 题选择当前最佳子话题，并且在文档的选择中同时考虑η个最佳子话题。此外，HPM2还引入 了一个距离函数，利用非最佳子话题和最佳子话题在层次结构中的距离远近判断子话题间 的相关性，从而控制不同相关程度的非最佳子话题在多样性中的影响。
[0104] 上面所述只是为了说明本发明，应该理解为本发明并不局限于以上实施例，符合 本发明思想的各种变通形式均在本发明的保护范围之内。
【主权项】
1. 一种基于层次结构子话题的搜索结果多样化排序方法，其特征在于，所述方法包括 如下步骤： 1) 定义查询词的层次结构树状子话题的表示方法； 2) 对层次结构子话题和查询、文档的相关性进行估算； 3) 建立基于查询词的层次结构子话题的搜索结果多样化模型； 其中，所述步骤3)通过两种排序方法的任一种实现： a) 排序方法一:根据层次结构话题新颖性模型对文档进行多样化排序； b) 排序方法二:根据层次结构话题比例模型对文档进行多样化排序。2. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤1)中层次结构子话题的表示方法具体为： (1) 对于每个新闻搜索词q，在搜索引擎中抽取其查询推荐词作为该搜索词的第一层子 话题，表不为{tl，t2，t3, . . . }; (2) 对于第一层子话题t，在搜索引擎中抽取其查询推荐词为该子话题的子话题，作为 搜索词的第二层子话题，表示为{",1，12，1 3，...}; (3) 对于第j层子话题k.4r，在搜索引擎中抽取其查询推荐词为该子话题的子话题，作为 搜索词的第二层子话题Uil 上述子话题的生成方式并不局限于搜索引擎的查询推荐。3. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤2)具体为： (1) 对于层次结构子话题树内部，定义父亲子话题在该查询词中的重要程度可以由其 所有孩子子话题完全覆盖，即(2) 定义层次结构中每个子话题和查询的相关性概率的推导方式为：(3) 定义层次结构中每个子话题和文档d的相关性概率的推导方式为：4. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中涉及的多样化排序方法，其基本步骤为： (1) 遍历所有待排序文档，根据算法策略选择当前多样性最佳的文档； (2) 将当前最佳文档加入已选文档列表； (3) 重复上述步骤，直到已选文档的数目符合要求； (4) 文档的选择顺序即为最终输出的文档排序，即搜索结果多样化排序。5. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中算法a)层次结构话题新颖性排序方法，其最佳文档的选择策略为： (1)对于层次结构子话题中的第j层子话题，考虑该层子话题本身的重要性，子话题被 已选择文档集D覆盖的情况，以及子话题和待选文档d的相关性，计算文档d在该层子话题中 的多样性(2) 综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性此时 各层子话题的贡献由参数α控制； (3) 选择整体多样性Φ (d，D)最大的文档为当前最佳文档。6.根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中算法b)层次结构话题比例排序方法，其最佳文档的选择策略为： (1) 对于第j层子话题，考虑该层中每个子话题本身的重要性15%刈幻，以及子话题被已选择 文档集D覆盖的情况W计算子话题14;尚未被满足的份额(2) 对于第j层子话题，选择份额最大的子话题为该层的最佳子话题 (3) 计算文档第的多样性Φ(Α认?,.Λ?)，此时重点考虑文档碑口该层最佳子话题（心 的相关性，同时也考虑文档d和该层其余非最佳子话题的相关性，以及该层最佳子话题与其余子话题 的关系即(4) 综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性此时 各层子话题的贡献由参数α控制； (5) 选择整体多样性Φ (d，D)最大的文档为当前最佳文档。
【专利摘要】本发明公开了一种基于层次结构子话题的搜索结果多样化排序方法，其包括如下步骤：1)定义查询词的层次结构树状子话题的表示方法；2)对层次结构子话题和查询、文档的相关性进行估算；3)建立基于查询词的层次结构子话题的搜索结果多样化模型；其中，步骤3)通过两种排序方法的任一种实现：a)：根据层次结构话题新颖性模型对文档进行多样化排序；b)：根据层次结构话题比例模型对文档进行多样化排序。本发明定义了查询的层次结构子话题，以及多层子话题和查询、文档间的相关性推算方法，提出基于该层次结构子话题的搜索结果多样化算法，能够灵活地利用不同粒度的子话题，更准确地匹配真实用户意图，从而提高搜索结果的多样性。
【IPC分类】G06F17/30
【公开号】CN105488195
【申请号】CN201510888616
【发明人】窦志成, 文继荣, 胡莎
【申请人】中国人民大学
【公开日】2016年4月13日
【申请日】2015年12月7日
【技术领域】
[0001 ]本发明涉及一种基于层次结构子话题的搜索结果多样化排序方法。
【背景技术】
[0002] 互联网信息越来越全面的覆盖了人们的日常生活，用户逐渐习惯依赖于搜索引擎 来查找自己需要的信息。大量研究表明，在提交给搜索引擎中的查询中，有相当部分的查询 是短文本查询。这些短文本查询由于信息量少，在解释用户意图时，通常是有歧义的，或者 有多重含义的。常见的有歧义的查询，例如，搜索"苹果"，有的用户可能是在找关于著名的 苹果公司的相关信息，有的用户则是关心水果苹果相关的信息;搜索"人大"，某些用户可能 是在找关于著名高校中国人民大学的相关信息，某些用户查找的则是全国人民代表大会的 相关信息。而多重含义的查询，是指在该查询下常包含了多个领域，例如，搜索"红楼梦"，用 户实际是想找与该查询相关的一个具体领域，如"红楼梦电视剧"，"红楼梦著作"，"红楼梦 人物"，"红楼梦明星"等。搜索结果多样化技术旨在解决上述问题。
[0003] 目前，搜索结果多样化方法可以划分为两大类：隐性（implicit)方法和显性 (explicit)方法。早期的多样化技术大多属于隐性多样化模型，其中最有影响力的工作之 一是Carbone 11和Go Ids te in在1998年提出的MMR算法。这类隐性方法认为，如果两个文档 (搜索结果)的文本内容越相似，则这两个文档涉及的话题越相似，冗余性越高。如果能减少 排序中的冗余文档，即可提高排序的多样性。于是，在多样化重排序时，隐性方法侧重于比 较文档间的相似度，将更新颖的文档排在前面，从而实现搜索结果多样化。但是，由于该类 方法在多样化时只完成了冗余处理，没有明确查询的用户意图。因此，该方法不知道哪些用 户意图更应该被覆盖，不能有目的地完成多样化，其效果有限。
[0004] 显性方法又称为基于子话题的方法，是目前搜索多样化技术的主流。该类方法明 确地利用子话题模拟用户意图，并通过子话题对搜索结果进行多样化。显性方法认为，两个 文档覆盖的子话题的相似性即为两个文档的相似性，而一个更多样化的文档排序应该在有 限的结果中覆盖尽可能多的子话题。
[0005] 在现有的显性方法中，一个查询的用户意图通常表示为一个子话题列表形式，其 中每个子话题对应一个用户意图。对于一个查询，获取相关子话题列表的方法有很多，包 括:用查询的分类信息作为子话题，巧用搜索引擎获取相关子话题，分析结果文档的短语或 词组生成子话题，或者联合多个外部资源生成组合子话题等。例如，用Google的查询推荐和 相关查询来代表查询的用户意图；从比较相关的检索文档中抽取单词和短语生成查询意 图。从四类不同类型的数据中挖掘子话题。
[0006] 在搜索结果多样化方向的国际竞赛或评测任务中（如TREC Web Track的 Diversity task，和NTCIR的Intent\IMine task)，查询的子话题由标注人员的主观标注确 定，视为真实的用户意图。多样化算法中使用的子话题应该尽可能地贴近真实用户意图，方 能得到让真实用户满意的多样化结果。然而，由于多样化算法中的子话题是根据查询自动 地生成的，很难完美地和真实的用户意图相匹配。而目前多样化方法中主要采用列表形式 的子话题，很难找到合适粒度的子话题能够完美匹配真实的用户意图。而真实的用户意图 本身则是隐含逻辑的层次结构。
[0007] 因此，如何解决上述问题成为本领域技术人员亟需解决的技术问题。
【发明内容】
[0008] 针对【背景技术】中存在的问题，本发明的目的在于提供一种基于层次结构子话题的 搜索结果多样化排序方法，该方法定义了查询的层次结构子话题，以及多层子话题和查询、 文档间的相关性推算方法，基于该层次结构子话题的搜索结果多样化算法，能够灵活地利 用不同粒度的子话题，更准确地匹配真实用户意图，从而提高搜索结果的多样性。
[0009] 本发明的目的是通过以下技术方案来实现的：
[0010] 一种基于层次结构子话题的搜索结果多样化排序方法，所述方法包括如下步骤： [0011] 1)定义查询词的层次结构树状子话题的表示方法；
[0012] 2)对层次结构子话题和查询、文档的相关性进行估算；
[0013] 3)建立基于查询词的层次结构子话题的搜索结果多样化模型；
[0014] 其中，所述步骤3)通过两种排序方法的任一种实现：
[0015] a)排序方法一:根据层次结构话题新颖性模型对文档进行多样化排序；
[0016 ] b)排序方法二:根据层次结构话题比例模型对文档进行多样化排序。
[0017] 进一步，所述步骤1)中层次结构子话题的表示方法具体为：
[0018] (1)对于每个新闻搜索词q，在搜索引擎中抽取其查询推荐词作为该搜索词的第一 层子话题，表示为{ tl，t2，t3，. . . };
[0019] (2)对于第一层子话题t，在搜索引擎中抽取其查询推荐词为该子话题的子话题， 作为搜索词的第二层子话题，表示为. . .};
[0020] (3)对于第j层子话题％,..?，在搜索引擎中抽取其查询推荐词为该子话题的子话 题，作为搜索词的第二层子话题\,& 3,...};
[0021] 上述子话题的生成方式并不局限于搜索引擎的查询推荐。
[0022] 进一步，所述步骤2)具体为：
[0023] (1)对于层次结构子话题树内部，定义父亲子话题在该查询词中的重要程度可以 由其所有孩子子话题完全覆盖，
[0024] (2)定义层次结构中每个子话题和查询的相关性概率的推导方式为：
[0025] (3)定义层次结构中每个子话题和文档d的相关性概率的推导方式为：
[0026]进一步，所述步骤3)中涉及的多样化排序方法，其基本步骤为：
[0027] (1)遍历所有待排序文档，根据算法策略选择当前多样性最佳的文档；
[0028] (2)将当前最佳文档加入已选文档列表；
[0029 ] (3)重复上述步骤，直到已选文档的数目符合要求；
[0030] (4)文档的选择顺序即为最终输出的文档排序，即搜索结果多样化排序。
[0031 ]进一步，所述步骤3)中算法a)层次结构话题新颖性排序方法，其最佳文档的选择 策略为：
[0032] (1)对于层次结构子话题中的第j层子话题，考虑该层子话题本身的重要性，子话 题被已选择文档集D覆盖的情况，以及子话题和待选文档d的相关性，计算文档d在该层子话
[0033] (2)综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性
，此时 各层子话题的贡献由参数α控制；
[0034] (3)选择整体多样性?(d，D)最大的文档为当前最佳文档。
[0035] 进一步，所述步骤3)中算法b)层次结构话题比例排序方法，其最佳文档的选择策 略为：
[0036] (1)对于第」层子话题，考虑该层中每个子话题本身的重要性「(~1,.. !:;10，以及 子话题被已选择文档集D覆盖的情况，计算子话题％,尚未被满足的份额
[0037] (2)对于第j层子话题，选择份额最大的子话题为该层的最佳子话题
[0038] (3)计算文档d在第j层子话题上的多样性此时重点考虑文 档d和该层最佳子话题^的相关性，同时也考虑文档d和该层其余非最佳子 话题的相关性，以及该层最佳子话题与其余子话题的关系KWh,.,ip，即
[0039] (4)综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性
*此时 各层子话题的贡献由参数α控制；
[0040] (5)选择整体多样性?(d，D)最大的文档为当前最佳文档。
[0041] 本发明具有以下积极的技术效果：
[0042] 本发明的方法可以获得更多有效的词项列表，在得到补充后的词项列表之后，对 新的词项列表进行打分，将相似的词项列表进行合并分类，计算不同的查询分面、词项列表 的重要性，最终使得挖掘出的查询维度更加完善，使得用户可以获得更为完整的信息。
【附图说明】
[0043] 图1是查询"defender"的两层结构子话题；
[0044] 图2是层次结构子话题树示意图。
【具体实施方式】
[0045] 下面结合附图和【具体实施方式】对本申请作进一步的说明。
[0046] 定义层次结构子话题的表达方式和相关概念：
[0047] 对于一个给定的查询q，我们用. . .，dm}表示最初的尚未多样化的文档 集合，用Tq={ti，t2, . . .，tn}表示查询相关的η个子话题集合。给定P(d|q)代表文档d和查询 q相关的概率，P(d|t)代表文档d和子话题t相关的概率，P(t|q)代表子话题t在查询q中的重 要程度。目前大部分基于子话题的多样化算法，利用T q、P(d | q)、P(d 11)、P(t | q)对初始文档 R进行重排序，得到多样化后的结果文档，记为D。在层次化的多样化模型中，由于多层子话 题的引入，本发明需要对上述子话题形式和概率进行重新定义。
[0048]层次结构子 话题的定义：
[0049] 本申请用1\1=^1，乜，...}表示查询(1的第一层子话题集合{匕1}，其中1 1代表子话 题t在集合Tq的位置（ii = l，2,...）。同理，1?二…}表示子话题\的所有孩 子子话题(第二层)的集合{tw2}，其中i 2代表子话题在集合τ?ι中的相对索引编号。以 此递推，我们用.,?代表层次结构中第j层子话题，用代表其孩子子话题(第j+Ι层） 的集合，其中子话题子话题在第j+Ι层上的第ij+1个孩子子话题。
[0050] 如图2所示，其展示了一个两层结构的子话题示例。第一层包含两个子话题t#Pt2， 第二层有四个子话题1：1,1，1：1,2 42,1和七2,2。其中，1：1,1和1：1,2是1：1的孩子话题42,1和七2,2是七2的 孩子话题。上述关系可以表不为1'1={1：1,1，1：1,2}和了2={^2,1山,2}。
[0051 ] 本申请使用图1中的查询"defender"来解释上述形式化定义。子话题"defender windows"有三个孩子子话题："defender windows home"代表用户希望访问软件主页， "defender windowsdownload"表不软件的下载需求，"defender windows problems"显不 用户对软件的各种问题感兴趣。同样地，第一层子话题"defender arcade game"和 "defenderland rover"都有各自的第二层孩子话题。注意，单词级别的多样化模型也有类 似的表达形式，将一个子话题表不为包含多个单词的一个集合= {^丨…|_。与 本申请的方法不同的是，该模型并不考虑子话题U和单词tj.之间的关系，而将每个单词tj视 为一个独立的子话题，然后把所有单词其合并起来形成一个更大的单词子话题集合
相比之下，本申请保持了完整的层次结构子话题树， 并以此为依据对文档进行多样化。
[0052]层次子话题的概率计算：
[0053]
是描述子话题在其双亲子话题hbij中重要程度的概 率。假设可以被其孩子子话题集合全覆盖，且每个孩子子话题之间相对独立。 由此可以得到：
[0055] 在图2中，可得:P(tl，l I tl)+P(tl，2 I tl) = 1，P(t2，l I t2)+P(t2,2 I t2) = 1。
[0056] Pd+lg) :是描述子话题ij在查询q中的重要性。在多层子话题中，此概率的 计算方式受子话题的生成方式影响。若已知叶子话题的重要性(例如，双亲子话题是由孩子 子话题聚类生成），双亲子话题的重要性可由其孩子子话题的重要性相加得到，由此迭代找 到所有子话题的重要性。
[0058]在另一种情况下，可能只知道第一层子话题的重要性。例如，在利用Google Suggestions生成多层结构子话题时，必须先得到第一层子话题，然后才能将其输入检索框 能找到第二层子话题。此时，可以利用贝叶斯公式计算每个孩子子话题的重要性：
[0060] 在图2中，若已知P(t1;1|q)和P(t1>2|q)，则？(七七）=?(七 1,七)+卩(七1,七）；若已知？ (ti|q)JlJP(ti，i|q)=P(ti|q).P(ti，i|ti)，P(ti，2|q)=P(ti|q).P(ti，2|ti)。
[0061] 代表文档d满足子话题1,?的概率。由于PM:l 也可以记为本申请默认叶子话题为单词或短语的形式，于是叶子 话题和文档的相关概率ρ(引?;)可用语言模型或其他检索模型直接计算得到。然而，非 叶子话题不一定是单词或短语的形式，他们可能是一组子话题的集合(例如，将原始Google Suggestions作为第二层子话题，将其聚类信息视为虚拟第一层子话题）。考虑到此类情 况，本申请使用一个自底向上的方法来递归地生成子话题和文档相关的概率，具体公式如 下：
[0063] 上式中，（1 - 是文档d不满足子话题^七的概率，其乘积代表d不 满足~,+.的所有孩子子话题的概率，则1-π (...)表示d满足至少一个的孩子子话题 的概率。
[0064] 话题新颖性模型：
[0065] 话题新颖性模型（topic novelty model)起源于经典MMR算法，是目前被广泛接受 的一个多样化算法框架。其基本思想是，在排序中同时考虑文档与查询的相关性和文档之 间的新颖性。具体到每次的文档选择时，它倾向选择既与查询相关，并与已选择文档尽可能 不相关的文档。其公式如下：
[0067]其中，?(d，D)代表文档d与已选择文档集D不相关的概率，即该文档的新颖性(又 称多样性），在不同的算法中有不同的定义。本申请选择了著名的xQuAD算法，作为层次化模 型的基础。xQuAD显示地利用文档在子话题上的覆盖情况来计算文档的多样性。
[0069] 上式中，（l-PU' I t))表示已选择的某个文档不满足子话题t的概率，其乘积 Π dkD(...)表示所有已选文档D不能满足t的概率。再考虑查询相关所有子话题的情况，以 及子话题的权重P(t|q)，上述多样性?(d，D)代表了当前文档d满足而已选文档不满足各个 子话题的概率。
[0070] 然而，公式(4)是针对列表形式存在的子话题设计的，在处理层次结构的用户意图 时可能并不适用。以图2所示的用户意图为例，假设文档cU和山与子话题t 1;1相关，文档d3和 子话题t1>2相关，文档d4和子话题t 2>1相关，需要对文档进行多样化排序。一个理想的排序为 cU-ck-cb-cb，其多样性在每次选择中均为最大。如果只使用第一层子话题，xQuAD可能输 出排序cU-ck-cb-cb，因为此时子话题较粗糙，无法区分文档山和山的细微差别，认为其均 与ti相关;如果只使用第二层子话题，xQuAD可能输出排序cU-cb-cU-cb，因为此时子话题 太细，认为d 3与d4相对于cU都是同样新颖，并不知道d3与cU都和子话题相关，而d 4才是真正 全新的选择。
[0071] 为了解决上述问题，本申请改进了 xQuAD的整体框架，提出了一个能处理多层子话 题的层次结构话题新颖性模型(Hierarchical xQuAD，HxQuAD)，可以显示地利用层次结构 的子话题来解决搜索结果多样化问题。在计算文档多样性时，HxQuAD会对层次结构中的每 层子话题独立地估算文档在该层的多样性。文档在子话题树中第j层的多样性计算如下：
[0073] 其中，| h，.山| = j表示子话题位于子话题树中的第j层，P 描述 在查询q中的重要程度，而P p 则代表d满足子话题々的概率，通过自底向
该局部多样性 〇(d，D，j)估算的是文档d在第j层子话题中多样性。
[0074] 然后，本申请把所有局部多样性整合起来，以评估文档在所有子话题层（即整个子 话题树)上的多样性。我们引入参数α来控制每层子话题（即子话题粒度)在判断多样性时的 贡献。具体做法如下面公式：
[0076]上式中，α的取值范围为（0，1]。当α = 0.5时，每层子话题在计算多样性时同等重 要；当α>0.5时，算法更看重文档在较粗粒度子话题上的多样性；当α〈0.5时，算法则更偏向 于文档在较细粒度子话题上的表现。特别地，若a = 1，则算法只使用第一层的子话题;反之， 若α接近于0,则算法倾向于只考虑最底层的叶子话题。注意，如果子话题树只存在两层结 构，α的最小值可以为0。
[0077]简而言之，HxQuAD将xQuAD的传统多样性计算改进为处理单层多样性的局部多样 性计算，在此基础上提出可处理层次结构子话题的多样化模型。HxQuAD包含两个参数:传统 子话题新颖性模型必有的用于平衡文档相关性和新颖性的参数λ，和多层结构模型特有的 用于控制子话题层次影响的参数α。
[0078] 话题比例模型：
[0079] 话题比例模型（topic proportionality model)通过子话题的比例对文档进行排 序，其特点是将多样化中的文档选择划分为两个步骤:选择子话题和选择最佳文档。在每次 迭代中，该模型首先根据子话题比例策略选择最佳子话题，然后根据当前最佳子话题寻找 最相关的文档。
[0080] PM2是话题比例模型的代表算法。它将搜索结果多样化问题类比为政治选举中的 党派席位分配问题，认为既然选举中的席位应该满足党派受到选票的比例，则文档的多样 化结果应该满足子话题的分布比例。它参考选举中使用的圣拉古计算法(Sainte-Laguel)， 用其席位分配方法模拟子话题的选择。在每次排序迭代中，PM2首先根据Sainte-Lague公式 计算当前子话题ti需要改善的分布比例，记为子话题的份额qti(quotient):
[0082]为了使已选文档中的子话题分布与原始文档的整体子话题分布尽可能一致，PM2 选择当前最大份额的(待改善程度最大的)子话题，作为当前最佳子话题然后，它计算多 样化函数?(d，D，t，，找到与最佳子话题f最相关，与其他子话题较相关的文档，作为当前 最佳文档cf。
[0084] 其中，Φ (d，D，t*) =λ · qti* · P(d | ti*) + ( 1_λ) · Σ i在i*qti · P(d | ti) (8)
[0085] 在文档cf加入 已选文档集D后，为了惩罚cf的相关子话题，PM2在每个子话题中计算 (f占用的比例，作为当前已占有的席位 Sl(seat)。
[0087]该算法重复上述过程，每次迭代时从R中选择最佳文档cf加入D。
[0088]在本申请中，我们改进了PM2的基础框架，提出了可处理树状结构子话题的层次结 构话题比例模型(Hierarchical PM2 model，冊]?2)。冊]\12保留了原模型PM2的核心思想，即 根据预选的最佳子话题选择最佳文档。与之不同的是，
[0089]------------------在层次结构的子话题树中，每层的子话题可能包含不同粒 度的多样化信息，对于每层的子话题，HPM2都能根据当前子话题比例找到一个该层最佳的 子话题。最后，HPM2综合考虑文档与各层最佳子话题的关系，选择最佳文档。以图2中的子话 题树为例。我们根据子话题比例，可能选择第一层的最佳子话题为ti，选择第二层的最佳子 话题为t 1;1，然后寻找和最相关的文档为最佳文档。注意，由于每层最佳子话题在选 择时相互独立，有时我们也可能选择tdPt2>1为第一层和第二层的最佳子话题。HPM2的具体 过程如下：
[0090]首先，对每层的子话题，HPM2计算该子话题在对应子话题层中的份额，作为当前子 话题在该层的比例，记为?。对于第j层的子话题，.心，其份额的具体计算方式类似 公式(7)，具体如下。其中PCtL.+ lq)代表满足q的概率。
[0092] HPM2比较第j层上的所有子话题的份额，选择份额最大的子话题为该层最佳子话 题，记为€,.心。同理，4，《七，…，分别表示从子话题树的第1层，第2层，…，第 η层选出的该层最佳子话题。对于每层子话题，HPM2计算文档与该层最佳子话题和其他子话 题的相关程度，代表文档在该层子话题的多样性。
[0093]对于第j层的子话题，根据ΡΜ2定义的多样化表达，一个多样化的文档应与该层最 佳子话题$,.,?尽可能地相关，与该层其他子话题％(丨到=/,? 比较相关。 ΗΡΜ2定义^(么^ ^为文档d在第j层子话题上的多样性，如下：
[0095]上式中，函数来表达子话题tk和最佳子话题々之间的依赖关系。
[0096] ΗΡΜ2引入该函数的原因是，由于子话题树独特的层次结构，同层的非最佳子话题 与最佳子话题的关系是存在亲疏远近的，需要不同对待。在层次结构中，如果子话题t与最 佳子话题f同属一个双亲子话题，则相比于该层的其他子话题，t与f更相关。仍然以图2的 子话题树为例，如果t 1;1是选中的最佳子话题，是决定文档多样性的关键，由于t1>2与t1;1关 系紧密（同双亲子话题），则讧 2显然比t2,#Pt2,2更重要。因此，在文档多样性的计算中，HPM2 应该给t 1>2更高的权重，以示其与t2,#Pt2,2的区别。具体地，每个非最佳子话题的权重，由其 与最佳子话题在层次结构中的距离来决定。函数的相关公式如下：
[0098]其中，dis(t，t，是子话题树中从t到f的路径距离。由于两个第j层子话题的最大 距离为2j，我们在公式中用2j对距离做归一化处理。继续讨论图2的例子，我们得到P(t211〇 =(2 · 1-2+1)/(2 · l) = 0.5,P(ti;2|ti;i) = (2 · 2-2+1)/(2 · 2) =0.75 ,P(t2>21 ti,i) = (2 · 2-4+1)/(2 · 2)=0.25。
[0099]更进一步地，本申请综合考虑文档在每层子话题中的多样性，然后根据下列公式 选择最佳文档cf。其中，参数ae(〇，l]用于控制子话题粒度(子话题层)在多样性中的影响， 类似公式(5)。
[0101]最后，HPM2基于选择的最佳文档cf，更新其相关的子话题的比例，具体公式如下所 示。注意，由于层次结构中各层的子话题比例相对独立，子话题的比例是逐层统计，子话题 比例的更新也是在每层上完成。
[0103] 简而言之，HPM2的工作过程是:根据每层子话题比例选择该层的最佳子话题，结合 所有最佳子话题计算多样性并选择当前最佳文档，基于当前文档和子话题的关系逐层更新 子话题占有比例。与PM2中只考虑一个最佳子话题不同，HPM2需要为层次结构中的每层子话 题选择当前最佳子话题，并且在文档的选择中同时考虑η个最佳子话题。此外，HPM2还引入 了一个距离函数，利用非最佳子话题和最佳子话题在层次结构中的距离远近判断子话题间 的相关性，从而控制不同相关程度的非最佳子话题在多样性中的影响。
[0104] 上面所述只是为了说明本发明，应该理解为本发明并不局限于以上实施例，符合 本发明思想的各种变通形式均在本发明的保护范围之内。
【主权项】
1. 一种基于层次结构子话题的搜索结果多样化排序方法，其特征在于，所述方法包括 如下步骤： 1) 定义查询词的层次结构树状子话题的表示方法； 2) 对层次结构子话题和查询、文档的相关性进行估算； 3) 建立基于查询词的层次结构子话题的搜索结果多样化模型； 其中，所述步骤3)通过两种排序方法的任一种实现： a) 排序方法一:根据层次结构话题新颖性模型对文档进行多样化排序； b) 排序方法二:根据层次结构话题比例模型对文档进行多样化排序。2. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤1)中层次结构子话题的表示方法具体为： (1) 对于每个新闻搜索词q，在搜索引擎中抽取其查询推荐词作为该搜索词的第一层子 话题，表不为{tl，t2，t3, . . . }; (2) 对于第一层子话题t，在搜索引擎中抽取其查询推荐词为该子话题的子话题，作为 搜索词的第二层子话题，表示为{",1，12，1 3，...}; (3) 对于第j层子话题k.4r，在搜索引擎中抽取其查询推荐词为该子话题的子话题，作为 搜索词的第二层子话题Uil 上述子话题的生成方式并不局限于搜索引擎的查询推荐。3. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤2)具体为： (1) 对于层次结构子话题树内部，定义父亲子话题在该查询词中的重要程度可以由其 所有孩子子话题完全覆盖，即(2) 定义层次结构中每个子话题和查询的相关性概率的推导方式为：(3) 定义层次结构中每个子话题和文档d的相关性概率的推导方式为：4. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中涉及的多样化排序方法，其基本步骤为： (1) 遍历所有待排序文档，根据算法策略选择当前多样性最佳的文档； (2) 将当前最佳文档加入已选文档列表； (3) 重复上述步骤，直到已选文档的数目符合要求； (4) 文档的选择顺序即为最终输出的文档排序，即搜索结果多样化排序。5. 根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中算法a)层次结构话题新颖性排序方法，其最佳文档的选择策略为： (1)对于层次结构子话题中的第j层子话题，考虑该层子话题本身的重要性，子话题被 已选择文档集D覆盖的情况，以及子话题和待选文档d的相关性，计算文档d在该层子话题中 的多样性(2) 综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性此时 各层子话题的贡献由参数α控制； (3) 选择整体多样性Φ (d，D)最大的文档为当前最佳文档。6.根据权利要求1所述的基于层次结构子话题的搜索结果多样化排序方法，其特征在 于，所述步骤3)中算法b)层次结构话题比例排序方法，其最佳文档的选择策略为： (1) 对于第j层子话题，考虑该层中每个子话题本身的重要性15%刈幻，以及子话题被已选择 文档集D覆盖的情况W计算子话题14;尚未被满足的份额(2) 对于第j层子话题，选择份额最大的子话题为该层的最佳子话题 (3) 计算文档第的多样性Φ(Α认?,.Λ?)，此时重点考虑文档碑口该层最佳子话题（心 的相关性，同时也考虑文档d和该层其余非最佳子话题的相关性，以及该层最佳子话题与其余子话题 的关系即(4) 综合文档d在每层子话题的多样性，计算文档d在子话题树上的多样性此时 各层子话题的贡献由参数α控制； (5) 选择整体多样性Φ (d，D)最大的文档为当前最佳文档。
【专利摘要】本发明公开了一种基于层次结构子话题的搜索结果多样化排序方法，其包括如下步骤：1)定义查询词的层次结构树状子话题的表示方法；2)对层次结构子话题和查询、文档的相关性进行估算；3)建立基于查询词的层次结构子话题的搜索结果多样化模型；其中，步骤3)通过两种排序方法的任一种实现：a)：根据层次结构话题新颖性模型对文档进行多样化排序；b)：根据层次结构话题比例模型对文档进行多样化排序。本发明定义了查询的层次结构子话题，以及多层子话题和查询、文档间的相关性推算方法，提出基于该层次结构子话题的搜索结果多样化算法，能够灵活地利用不同粒度的子话题，更准确地匹配真实用户意图，从而提高搜索结果的多样性。
【IPC分类】G06F17/30
【公开号】CN105488195
【申请号】CN201510888616
【发明人】窦志成, 文继荣, 胡莎
【申请人】中国人民大学
【公开日】2016年4月13日
【申请日】2015年12月7日
最新回复(0)