一种基于语义的查询推荐方法和系统

摘要

本发明提供一种基于语义的查询推荐方法和系统，所述方法包括建立查询概念二元图，构建查询点击URL二元图，将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；根据用户的输入查询词，利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列，得到查询推荐列表。本发明提供的基于语义的查询推荐方法和系统旨在增强推荐出的查询与原始查询的语义关联性，给用户推荐出更好的查询，满足用户的查询需求。

权利要求

1.一种基于语义的查询推荐方法，其特征在于，包括：

根据用户历史查询日志数据得到历史查询词，将历史查询词映射成维基百科概念，建立查询概念二元图；所述将历史查询词映射成维基百科概念，进一步包括：将维基百科文档进行加权的倒排索引，构造语义解释器；利用语义解释器将历史查询词映射成维基百科中的概念；

根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图，将用户的历史查询和点击行为记录在查询点击URL二元图中；

将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；

根据用户的输入查询词，利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列，得到查询推荐列表。

2.根据权利要求1所述的基于语义的查询推荐方法，其特征在于，所述利用语义解释器将历史查询词映射成维基百科中的概念，进一步包括：将历史查询词进行分词，每个分词与维基百科文档按照TF-IDF值来进行对应。

3.根据权利要求2所述的基于语义的查询推荐方法，其特征在于，所述TF-IDF值计算公式如下：其中，TF-IDF值代表词i在文档j中对应的权值，TFij是词i在文档j中出现的频率，IDFi是词i在文档j中的逆向文档频率，nij是词i在文档j中出现的次数，∑knkj是在文档j中所有字词的出现次数；|D|为语料库中的文件总数，|{j：ti∈dj}|为包含了词i的文档个数。

4.根据权利要求1所述的基于语义的查询推荐方法，其特征在于，所述利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，计算公式如下：Pij为一类节点A里的一个节点i一步转移到另一类节点B里的一个节点j的概率，Cij为节点i和节点j连接的权值。

5.根据权利要求1所述的基于语义的查询推荐方法，其特征在于，所述用户历史查询日志数据包括用户名称信息、用户查询内容信息、点击的URL、查询的时间。

6.根据权利要求1所述的基于语义的查询推荐方法，其特征在于，所述三层随机游走模型为三层马尔科夫随机游走模型。

7.一种基于语义的查询推荐系统，其特征在于，包括：

概念映射模块，用来根据用户历史查询日志数据得到历史查询词，将维基百科文档进行加权的倒排索引，构造语义解释器，利用语义解释器将历史查询词映射成维基百科中的概念，建立查询概念二元图；

查询与点击URL对应模块，用来根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图；

三层随机游走模块，用来将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；

用户输入模块，用来输入用户查询词；

查询推荐模块，用来利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列得到查询推荐列表对用户进行查询推荐。

说明书

一种基于语义的查询推荐方法和系统

技术领域

[0001] 本发明涉及信息检索领域，特别涉及一种基于语义的查询推荐方法和系统。

背景技术

[0002] 随着时代的发展，互联网也在世界范围内得到了蓬勃的发展，越来越多的人开始在互联网上找寻所需要的信息。随着互联网上的信息越来越多，搜索引擎逐渐成为用户访问网络资源所必不可少的工具，用户通过向搜索引擎输入查询，来反映自己的信息需求，搜索引擎获取并分析用户查询，返回给用户需要的信息。但是并不是每一次的查询，用户都能得到想要的结果。这是因为一方面用户在查询某样信息时，本身就这一方面知识缺乏了解，难以构造出合适的查询；另一方面，由于搜索引擎技术方面原因，搜索引擎自身有时也会混淆用户的查询；最后，由于自然语言的多义性，有些查询本身在不同语境下具有不同的语义。比如，当用户输入“苹果”时，用户有可能是想搜索苹果科技公司，用户也有可能是想搜索水果苹果，用户还有可能是想搜索一部叫《苹果》的电影。由于以上的种种原因，搜索引擎很难保证在用户第一次输入时就能够给出让用户满意的结果。为了更好地了解用户的查询意图，帮助用户构造好的查询，现代搜索引擎都提供了查询推荐的技术。

[0003] 目前主流的查询推荐的方法有三种：一种是基于文档的方法，这类方法是通过处理查询搜索出来的文档，以此作为反馈，进一步地理解用户意图，来扩充查询的语义。第二种是基于查询日志的方法，是利用查询日志来获取相似的查询，利用查询日志记录的用户信息，可以挖掘出查询词直接的联系。第三种是基于会话的方法，首先对搜索日志进行会话划分，然后对每个会话利用关联规则、互信息和相似度算法度量查询间相关性。

[0004] 目前，北京大学提出了一种基于用户日志进行查询推荐的方法及系统，根据用户日志中的数据集得到相关的查询日志，并选择一些查询串作为训练集进行查询推荐；国际商业机器公司根据用户输入的查询，从不同的搜索引擎中获得相对应的查询推荐集合进行推荐；百度公司利用用户分组来进行推荐；百度公司还通过用户等级来构建查询推荐，该方法根据用户的查询生成交互式问题，并将交互式问题提供到用户，根据用户对于交互式问题的答案确定用户的等级，最后再利用用户的等级和搜索词生成查询推荐结果并提供至用户。

[0005] 虽然查询推荐技术已经较为成熟，但是仍然存在着一些问题：

[0006] 第一，基于文档的方法需要外部文档，而且全局文档分析的时间复杂度高，受自然语言处理技术限制，效果也不是很好，局部文档分析对于如何准确获取查询相关文档也是一个难题，计算开销依然很大。

[0007] 第二，基于会话的方法需要先对查询日志进行准确的会话划分，而会话比查询更少，直接依据统计信息依然存在着信息稀疏的问题。而基于点击信息的方法则非常依赖搜索引擎的效果，而且用户点击结果中也存在着许多的噪音和偏向性，而且查询日志中的查询也存在着稀疏性的问题。

[0008] 第三，传统的查询推荐方法一般只考虑点击信息或者只是查询词本身，很少会考虑到查询词后的深层语义。这导致推荐出来的结果存在着准确度不高的情况。

[0009] 第四，由于查询日志的稀疏性，很多查询词在查询日志中出现的次数很少甚至都没有出现。对于这些查询，传统的方法也很难给出好的查询推荐。

发明内容

[0010] 针对以上问题，本发明专利目的在于设计了一种基于语义的查询推荐方法和系统，旨在增强推荐出的查询与原始查询的语义关联性，给用户推荐出更好的查询，满足用户的查询需求。

[0011] 本发明是通过以下技术方案实现的：

[0012] 本发明提供一种基于语义的查询推荐方法，包括：

[0013] 根据用户历史查询日志数据得到历史查询词，将历史查询词映射成维基百科概念，建立查询概念二元图；

[0014] 根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图，将用户的历史查询和点击行为记录在查询点击URL二元图中；

[0015] 将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；

[0016] 根据用户的输入查询词，利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列，得到查询推荐列表。

[0017] 进一步，本发明所述将历史查询词映射成维基百科概念，进一步包括：

[0018] 将维基百科文档进行加权的倒排索引，构造语义解释器；

[0019] 利用语义解释器将历史查询词映射成维基百科中的概念。

[0020] 进一步，本发明所述利用语义解释器将历史查询词映射成维基百科中的概念，进一步包括：

[0021] 将历史查询词进行分词，每个分词与维基百科文档按照TF-IDF值来进行对应。

[0022] 进一步，本发明所述TF-IDF值计算公式如下：

[0023]

[0024] 其中，TF-IDF值代表词i在文档j中对应的权值，nij是词i在文档j中出现的次数，∑knkj是在文档j中所有字词的出现次数；|D|为语料库中的文件总数，|{j:ti∈dj}|为包含了词i的文档个数。

[0025] 进一步，本发明所述利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，计算公式如下：

[0026]

[0027] Pij为一类节点A里的一个节点i一步转移到另一类节点B里的一个节点j的概率，Cij为节点i和节点j连接的权值。

[0028] 进一步，本发明所述用户历史查询日志数据包括用户名称信息、用户查询内容信息、点击的URL、查询的时间。

[0029] 进一步，本发明所述三层随机游走模型为三层马尔科夫随机游走模型.[0030] 本发明还提供一种基于语义的查询推荐系统，包括：

[0031] 概念映射模块，用来根据用户历史查询日志数据得到历史查询词，将历史查询词映射成维基百科概念，建立查询概念二元图；

[0032] 查询与点击URL对应模块，用来根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图；

[0033] 三层随机游走模块，用来将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；

[0034] 用户输入模块，用来输入用户查询词；

[0035] 查询推荐模块，用来利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列得到查询推荐列表对用户进行查询推荐。

[0036] 本发明提供的一种基于语义的查询推荐方法和系统，通过将查询映射成维基百科的概念，扩展了查询的语义性，并将它与点击URL信息相结合，利用三层随机游走模型，将查询推荐结果依游走概率从高到低进行排序，使得推荐结果在语义信息和点击URL信息上都与原始的查询保持相关性，最终推荐出更为准确、相关性更好的查询，供用户使用，提高用户的满意度。

附图说明

[0037] 以下参照附图对本发明实施例作进一步说明，其中：

[0038] 图1是本发明一种基于语义的查询推荐方法的查询概念二元图；

[0039] 图2是本发明一种基于语义的查询推荐方法的查询点击URL二元图；

[0040] 图3是本发明一种基于语义的查询推荐方法的概念查询点击URL三元图；

[0041] 图4是本发明一种基于语义的查询推荐系统的模块图。

具体实施方式

[0042] 下面结合附图和具体实施例对本发明作进一步的详细说明。

[0043] 本发明提出了本发明提供一种基于语义的查询推荐方法，包括如下步骤：

[0044] 步骤(A)，根据用户历史查询日志数据得到历史查询词，将历史查询词映射成维基百科概念，建立查询概念二元图。

[0045] 具体的，查询词往往很短，一般有2、3个词组成，用概念来拓展查询词的语义，克服了由于查询词的语义稀疏的缺点。概念映射过程主要用了基于维基百科的显示语义分析技术，将查询词映射成了维基百科中的概念。这里的维基百科的概念指的是维基百科的词条，映射的具体步骤如下：

[0046] (1)利用维基百科文档构建语义解释器；

[0047] (2)利用语义解释器将查询词映射成维基百科中的概念。

[0048] 步骤(1)是利用维基百科文档构建语义解释器，为这些维基百科文档建立有权重的倒排索引。所谓的倒排索引，是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取这个单词的文档列表。它主要由两个部分组成：单词词典和倒排文件。单词词典值得是有文档集合中出现的所有的单词组成的字符串集合，单词词典内构成的字符串集合。倒排文件是记载所有单词的倒排列表的地方，倒排列表中则记载了出现过某个单词的所有文档的文档列表以及单词在文档中出现的位置信息，每条记录叫做一个倒排项。根据倒排表，可以获得哪些文档包含了某个单词。

[0049] 步骤(2)是用语义解释器将查询词映射成维基百科的概念。首先将查询词进行分词，分词是指将查询词分为一个个单独的词，而每个词都可以在步骤(1)中倒排索引中找到与之对应的维基百科文档，而它们对应的权值可以根据TF-IDF值来确定。

[0050] TF-IDF(term frequency-inverse document frequency)是一种统计方法，用以评估一个字词对于文档集或者一篇文档的重要程度。字词的重要性与它在文档中出现的次数相关，出现的越多越重要，这也是TF(term frequency，词频)的意义，词i在文档j中的TF值计算公式如下：

[0051]

[0052] nij是词i在文档j中出现的次数，∑knkj是在文档j中所有字词的出现次数。

[0053] 但有些词比如“一个”、“好”等词语，几乎在每一篇文档中都频繁的出现过很多次，这些词的重要程度应该降低，这就是IDF(inverse document frequency，逆向文档频率)的意义，它计算的是一个词在语料库中出现的频率的反比。对于单词i，它的IDF计算如下：

[0054]

[0055] |D|为语料库中的文件总数，|{j:ti∈dj}|为包含了词i的文档个数。

[0056] 为了不让分母为0，于是在后面加上了一个1。而TF-IDF值是TF值与IDF值得乘积，即TF-IDF＝TF*IDF。那么一个词i在文档j的TF-IDF值为:

[0057] TF-IDFij＝TFij*IDFi

[0058] 而一个查询由若干个词组成，将它们所有的TF-IDF值统计起来，便得到了查询与维基百科文档的对应关系。而维基百科文档又是与维基百科概念(即维基百科的词条)一一对应，这样我们将查询与维基百科的概念对应起来了，并且可以计算它们之间对应的权重。

[0059] 根据这些可以建议建立一个查询概念二元图，请参阅图1，查询概念二元图中有概念类节点V1和查询类节点V2，两类节点之间的连线就是他们之间的TF-IDF权值。

[0060] 步骤(B)，根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图，将用户的历史查询和点击行为记录在查询点击URL二元图中。

[0061] 具体的，查询日志是搜索引擎为了记录用户的搜索行为而生成的日志，它记载了用户ID、用户查询、点击的URL、查询的时间、点击的URL(统一资源定位符)的排名等等重要信息。对于每一条查询日志中的记录，都能找到一个查询和与它相对应的URL。利用历史查询日志，将查询和点击URL对应起来，构建查询点击URL二元图，请参阅图2，查询点击URL二元图中的节点V由两大类节点组成V1和V2。V1代表所有的查询，而V2代表所有的URL。如果V1中的点Q1与V2中的U1直接存在连线，表示用户输入Q1后，点击了U1。连线的权重e(Q1，U1)与点击的URL次数相关。

[0062] 查询点击URL二元图的构建过程如下：

[0063] 查询点击URL二元图开始设为空；

[0064] 对于历史查询日志中的一条记录，取出它的查询(Qi)和点击URL(Uj)；

[0065] 对于每一对取出来的查询(Qi)和点击URL(Uj)，如果在查询点击URL二元图中没有查询(Qi)，添加查询节点(Qi)；如果查询点击URL二元图中没有URL(Uj)，添加URL节点(Uj)；如果Qi和Uj没有连线，则将Qi和Uj连接起来，并置边eij的权重为1；如果Qi和Uj之间有连线，则将边eij的权重加1；

[0066] 重复第二步到第三步直到查询日志的所有记录都被处理完。

[0067] 步骤(C)，将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型。

[0068] 具体的，步骤(A)和步骤(B)得到的查询点击URL二元图和查询概念二元图中的查询节点是一一对应的，直接将两个图进行按照查询节点进行合并，可以得到概念查询点击URL三元图，请参阅图3。

[0069] 概念查询URL三元图中，并在此三元图上计算游走概率，将三元图变成了三层马尔科夫随机游走模型。由概念、查询、URl三类节点组成，其中查询类节点可以一步游走到概念类节点和URL类节点，而概念类节点和URL类节点之间无法一步转移到达。

[0070] 查询类节点和另外两类节点之间的游走概率计算过程如下：

[0071]

[0072] Pij为一类节点A里的一个节点i一步转移到另一类节点B里的一个节点j的概率，Cij为节点i和节点j连接的权值。

[0073] 利用该计算公式，可以计算出概念查询URL三元图中任意点出发，经过t步转移到其他节点的概率，从而我们能够得到转移概率矩阵。转移矩阵(记做Z)中的行和列都是三元图中的节点，而每一个单元的值是它们之间转移的概率。从三元图中节点i转移到节点j的转移概率为：

[0074] Pij＝[Zt]ij

[0075] 在概念查询点击URL三层随机游走模型中，即三层马尔科夫随机游走模型，从某个查询节点出发，经过偶数步的随机游走后，最终依概率游走到查询类节点中。将这些查询节点按照游走概率从高到低排列，便可以得到查询推荐列表。

[0076] 步骤(D)，根据用户的输入查询词，用户输入查询，通常使用浏览器，如常用的Internet Explorer，FireFox，Chrome等浏览器等，利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列，得到查询推荐列表。

[0077] 相应的，本发明还提供一种基于语义的查询推荐系统，请参阅图4，包括：

[0078] 概念映射模块，用来根据用户历史查询日志数据得到历史查询词，将历史查询词映射成维基百科概念，建立查询概念二元图；

[0079] 查询与点击URL对应模块，用来根据用户历史查询日志数据，将历史查询日志与点击URL对应起来，构建查询点击URL二元图；

[0080] 三层随机游走模块，用来将所述查询概念二元图和查询点击URL二元图按照查询节点进行合并，形成概念查询点击URL三元图，并建立三层随机游走模型；

[0081] 用户输入模块，用来输入用户查询词；

[0082] 查询推荐模块，用来利用所述三层随机游走模型计算输入查询词节点与概念节点和URL节点之间的游走概率，将输入查询词节点按照游走概率从高到低排列得到查询推荐列表对用户进行查询推荐。

[0083] 本发明提供的一种基于语义的查询推荐方法和系统具体实施例，查询推荐系统分为线上部分和线下部分两个，线下部分可以离线来处理，而线上部分则需要在线进行处理。

[0084] 线下部分中，概念映射单元首先将维基百科文档进行加权的倒排索引，构造成查询语义解释器。所谓语义解释器，就是能够将文本内容映射成维基百科的概念。然后利用查询日志得到所有记录的查询词，对于每一个查询词，概念映射单元将它进行分词，得到若干个独立的词语，然后放入索引好的维基百科文档集中进行索引，得到TF-IDF值。

[0085] 将维基文档集进行倒排索引，然后对于查询日志中的每一个查询，分好词，放到索引好的维基文档集中进行TF-IDF值的计算，并统计相加，得到查询与各个维基文档之间的联系的概率，而维基百科的文档与维基概念(也即是维基百科的词条)是一一对应的，这样我们就把查询和维基概念统一对应起来，进而构造了查询概念二元图。

[0086] 查询点击URL映射单元利用查询日志，将查询和点击URL相互对应。查询日志中的每条记录，都可以找到一个查询和与它对应的点击URL，它们反映了用户的搜索、点击行为。一般来说，若两个查询对应的点击URL分布很类似，那么说明这两个查询也较为类似。查询点击URL映射单元通过处理查询日志，构建查询，点击URL二元图，将用户的搜索、点击行为的关键数据记录在了这个二元图中。

[0087] 在得到了查询点击URL二元图和查询概念二元图后，三层随机游走单元将这两个二元图进行合并，形成概念查询点击URL三元图，并在此三元图上计算游走概率，将三元图变成了三层马尔科夫随机游走模型。构造了概念查询点击URL三层随机游走模型。

[0088] 线上部分主要是在线处理用户输入的查询，在三层随机游走模型上应用随机游走算法，给出相应的查询推荐。用户输入单元负责接受用户输入的查询，当用户输入单元获取到了查询时，一方面会进行检索，给出检索结果。另一方面，它将查询放入到离线生成的三层随机游走模型中，进行查询推荐的工作。

[0089] 在三层随机游走模型的概念查询点击URL三元图中，以该查询作为随机游走的起始节点，在该三层随机游走模型中进行t步随机游走，计算转移t步游走后转移矩阵Z的值。假设原始查询在三层模型中的节点为i，那么t步游走后，计算Zt，最终Zt的第i行的值就是到各个查询节点的转移概率值。将最终的转移概率按照从大到小排序，选出前n个结果作为查询推荐。

[0090] 以上所述本发明的具体实施方式，并不构成对本发明保护范围的限定。任何根据本发明的技术构思所做出的各种其他相应的改变与变形，均应包含在本发明权利要求的保护范围内。