基于个性化词典的搜索引擎查询扩展模型

摘要：为了向用户提供个性化的web信息检索服务，该文对已有的个性化服务模型加以改进，介绍了一种基于用户个性化词典的搜索引擎查询扩展模型。该模型采用用户个性化词典替换传统的全局词典，并利用查询扩展策略实现个性化服务。用户个性化词典能够优化用户兴趣建模过程，使用户兴趣模型更加准确，从而优化最终生成的扩展词。借助扩展词，用户可以在搜索引擎上更方便地检索到更符合自己兴趣的网页。实验表明该模型能够通过搜索引擎，向用户提供有效可行的个性化服务。

关键词：用户个性化词典；二级向量；查询扩展；个性化服务；搜索引擎

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2012）28-6764-07

网络是人们获取知识和传递信息的桥梁。然而，随着近年来internet的高速发展，网络上信息的数量也呈现指数级的增长，在这一背景下，互联网使用者往往无法轻松找到需要的信息。搜索引擎的出现使我们信息检索方面的需求在一定程度上得到解决。目前，搜索引擎的概念已经深入人心，成为进行互联网信息检索必不可少的工具。但它存在如下几个方面的局限性。

1）搜索结果集庞大，用户为找到其真正感兴趣的信息，耗费大量的时间和精力。

2）不同用户在不同时期采用同样的查询关键词请求所得到的搜索结果几乎相同，对用户来说不能提供个性化的服务。

3）用户在使用搜索引擎检索时带有一定的目的性，但往往由于该用户相关领域知识的不足以及搜索引擎查询接口的局限性，导致用户不能清楚地表达其信息需求[2]。

针对传统搜索引擎不能提供面向用户的个性化服务这一缺陷，大量的专家学者开始研究查询扩展技术，并在此领域有所突破。文献[1]根据文档分析，提出局部共现的思想，利用词项与所有查询词在局部文档集合中的共现程度以及在语料集中的全局统计信息来评估扩展词的质量，选择合适的扩展词；文献[3-5]通过分析用户浏览历史，主要采用关联规则进行查询扩展；文献[6]利用HITS和TextRank技术提取用户主题，并结合关联规则进行查询扩展；而文献[7]提出了一种基于二级向量的搜索引擎个性化服务模型SEPMBDVD（Search Engine Personalization Model Based on Double Vector Description），其实质也是利用对用户浏览的历史网页进行挖掘而得的用户兴趣模型生成与用户输入的查询关键词配对的扩展词。通过扩展词加入，使用户在利用搜索引擎检索的时候能够得到符合用户兴趣或者兴趣偏好的结果，经过实验验证该模型具有查准率高，反应速度快等优点。这种查询扩展模型依赖于用户兴趣模型，文献[7]采用的是二级向量模型，即通过一组关键词向量和扩展词向量描述用户兴趣，这种模型是基于一个全局词典对用户浏览的历史网页进行描述、聚类挖掘以后生成的。整个模型结构如图1所示。

全局词典由于词汇量过大，词汇太杂，无法体现用户的兴趣等原因，会对用户兴趣模型的生成造成较大的影响，从而影响到词扩展的效果。因此本文使用个性化词典替换全局词典，并采用查询扩展策略实现个性化服务，设计出一种基于个性化词典的搜索引擎查询扩展模型QEMBUPDSE（Query Expansion Model Based on User Personalization Dictionary for Search Engine）。该模型能够通过个性化词典优化用户兴趣模型，从而优化查询扩展词，使得用户的个性化搜索更快，更准确。

1 基于个性化词典的搜索引擎查询扩展模型

基于个性化词典的搜索引擎查询扩展模型从用户浏览历史网页描述开始就利用个性化词典的两级词典，即关键词词典和扩展词词典，形成网页的二级向量描述，接着通过数据挖掘手段更直接的生成用户兴趣的二级向量模型，最后根据用户输入的关键词进行查询扩展，如图2所示。

2.1 个性化词典的定义与实现

根据文献[10]，个性化词典UPD（User Personalization Dictionary）由关键词词典（KeyDict）和扩展词词典（ExDict）两级构成，位于两级词典中的词分别定义为关键词和扩展词。每一级词典中包含n个（n由人为设定）由词和词权构成的二元组。关键词通常表示用户浏览兴趣，词的权值越大，表示在用户兴趣中的重要性越大。而扩展词用于描述用户在兴趣点上的兴趣偏好，从而在查询扩展时提供符合用户偏好的扩展检索词。

特定用户的UPD能够充分表达用户对信息需求的倾向性，同时对基于二级向量的用户兴趣模型提供支持，是一种符合用户兴趣的私有词典，在词典设计上主要考虑如下主要原则：

1）网页文档集合中，某词出现的频度越高，该词对用户特征的描述能力越强。

2）网页文档集合中，包含某词的网页数越多，该词对用户特征的描述能力越强。

3）对于一些网页中比较常用的，没有检索价值的词，我们称之为网页频繁词，如：评论、版权、文章等，在词典中应该被过滤掉，以免对用户的个人描述带来噪音。

在公式1中S为网页集合，T为词空间，W（t，S）为词t在S中的权重，tf（t，S）为词t在S中的词频，N为S包含的网页总数，nt为S中的文档出现t的数量，分母为归一化因子。在TF-IDF公式中，㏒（N/nt+0.01）为IDF因子，即“逆文本频率指数”，在WTUPD中依然沿用这个名称，IDF因子越大，表明该词在网页集合中分布越稀疏，那么该词的重要性越小，权值越小。反之，该词的IDF因子越小，表明其在网页集中分布越密集，越均匀，那么该词的重要性越大，权值越大。

考虑到词在网页集合中分布的均匀程度不同，本文认为词t在整个网页集合S中的权重与其在网页中的均匀度成正比。因此，本文引入衡量均匀度的因子对词t的权重进行修正，公式1中词t的均匀度由t在网页集合中的标准差（Standard Deviation）来衡量，如公式2所示：

通过WTUPD公式可以看出：词t在网页集S中的权重，与它在该网页集中的词频成正比，与它在该网页集中分布的稀疏程度和均匀程度成正比。通过WTUPD公式得到用户浏览的网页文集合中所有词的权重并排序，再根据个人浏览兴趣的广泛度选择关键词扩展词，兴趣点较集中的用户选择前1/3的词作为关键词，余下的词即为扩展词。而兴趣点较分散（核心兴趣点5个以上）的用户选择前1/2的词作为关键词，余下即为扩展词，以此形成关键词词典和扩展词词典。

最后还要清除关键词词典和扩展次词典中的频繁词，频繁词的特征是分布在网页集合中大多数文档中，且在单张网页中出现的次数往往较少（一般为1-2次）。本文采用如下的方法对这部分词进行过滤。

经过以上公式处理，最终可以建立满足用户兴趣描述要求的个性化词典。

2.2 基于个性化词典的用户兴趣建模

最终的词扩展依赖于准确的用户兴趣模型，而个性化词典的建立将有利于用户兴趣模型快速、准确地建立，因此本文采取的用户兴趣建模方法如下：

首先，利用个性化词典将用户浏览的网页转换为特征向量，由于个性化词典包含两级词典，因此，生成的网页特征向量即为二级向量，例如某网页的特征向量表示为{[（单反，0.05327385），（摄影，0.04826857），（像素，0.03272436），（市场，0.02713352），（专业，0.02639451），……]；[（镜头，0.01135712），（显示屏，0.01023895），（环境，0.09325765），（浏览，0.09031257），（效果，0.08736234）……]}，分号之前是关键词向量而之后是扩展词向量。

接着，利用网页特征向量进行聚类分析，得到用户的各个兴趣子类。

最后，利用各类的网页特征向量将兴趣子类描述成为二级向量，生成用户兴趣模型。

由此可见，个性化词典使得整个用户兴趣建模过程均使用二级向量，用户兴趣模型的生成更直接和顺利，并且由于个性化词典规避了传统全局词典中的大量与用户兴趣无关的词和频繁词，使得网页特征描述更加准确，为后续的聚类分析和兴趣模型生成奠定良好的基础，并通过用户兴趣模型提供符合用户兴趣偏好的扩展词，有利于扩展词的分析比较和选取。

2.3 查询扩展策略的实现

其中，分子为向量ci与Qini各分量乘积的和，分母为向量模的乘积。本文选择与初始查询相似度最高的兴趣点C作为用户的查询意图。即：

为了尽可能的向用户提供查询扩展词，如果在关键词向量中无法找到用户的查询词，即Qini与关键词向量的相似度为0的话，那就将扩展词向量并入关键词向量中一起参与运算。

接下来，为了找到与用户查询词最相关的扩展词，需要计算词间关联度。本文参照LSI模型[7]中的方法，将一个网页文档集合表示成“词—文档”矩阵TD，如表1所示。

表1为“词—文档”矩阵TD的截取内容，顶部一行表示文档集合中所有文档的名称（编号），而左边一列中的“欧洲、足球”为用户向搜索引擎提交的初始查询词Qini，“国家队、世界杯、澳大利亚、…”为Qini所匹配兴趣类的扩展词向量中的扩展词。中间的矩阵单元TDij为对应的词Ti在文档Dj中的权值（频度）按行归一化后的结果。由于词和文档的数量都很大，而单个文档中出现的词又非常有限。因此，TD一般为高阶稀疏矩阵。

然后利用TD构造词间关系矩阵TT，并计算词间关联度，构造方法如公式（6）：

其中TD’是TD的转置。所得矩阵TT中每一个单元的TTij的值所反映的是在特定环境下（特定用户的特定兴趣类）词i与词j之间的相似度。我们可以看到，每个词与它本身的相似程度为1，而在该兴趣类的任何文档中都没有同现的两个词之间的相似度为0。如表2所示。

公式7中x*表示词间关系矩阵TT中与初始查询词Qini相似度最大的候选扩展词对应的关联度，x表示其他候选扩展词与Qini的关联度。公式8中的参数[δ]表示x与x*的相对误差阈值，表示只要某候选扩展词与Qini的关联度与x*之间的相对误差只要小于δ，那么该候选扩展词就可以最终推荐给用户，在实际应用中δ通常取值10%，可以保留较好的扩展词，同时也减少运算时间。可以根据情况设置。这样将筛选出来的词进行按关联度从大到小的顺序排序以后，就可以推荐给用户了。由于过多的扩展词将导致搜索的返回结果减少，反而会不利于用户获取足够的信息。通常选择3个扩展词为宜，那么最终可以从已经排序的扩展词队列里面选择前3个进行推荐。当然，根据用户需求，扩展词的推荐数量可以自行设定。

3 实验与分析

3.1 评价指标SWUI

由于用户个性化词典UPD实际上几乎包含了用户所有感兴趣的词，并且从浏览历史网页里计算出的词的权值也反映了用户对这些词的感兴趣程度，因此，本文利用通过查询扩展搜索到的网页集合与用户个性化词典进行比较的方式来进行实验，评测本文提出的个性化服务模型的效果。

为了将检索到的网页集合与用户个性化词典进行比较，本文计算检索到的网页集合特征向量的中心向量，并称中心向量为用户向量UV（User Victor），然后计算UV与UPD之间的相似度（余弦函数值），通过该相似度反映网页集合与用户兴趣之间的相关程度，称该相似度为SWUI（Similarity between Webpages and User Interests）。

3.2 实验数据

本文实验基于三位用户进行，他们分别按照自己的兴趣浏览网页，然后将自己感兴趣的网页保存下来，接着对三位用户提供的兴趣网页进行兴趣建模，得到用户兴趣模型表4所示，限于篇幅，每个兴趣类只用部分关键词表示。

3.3 对比实验

本文在Google和百度两大主流搜索引擎上，进行了以下三组实验：

1）None实验：不采用查询扩展，只使用用户查询关键词进行检索的实验。

2）Standard实验：采用文献[7]提出的SEPMBDVD模型进行查询扩展，然后在搜索引擎上进行检索的实验。

3）UPD based实验：采用本文提出的QEMBUPDSE模型进行查询扩展，然后在搜索引擎上进行检索的实验。

对比实验由提供用户兴趣模型的三位用户实施，每位用户对自己的每个兴趣选用适当的关键词按以上三组实验要求在Google和百度上进行搜索，每组实验都将每种搜索引擎返回的前100张网页保存下来。接着针对每种搜索引擎，计算每个关键词搜索到的网页集合与UPD之间的SWUI，最后根据各SWUI计算各个兴趣类的ASWUIIC（Average Similarity between Webpages and User Interest in each Interest Class），计算公式如公式9所示：

公式9中，n为某兴趣类的测试关键词数量，因此ASWUIIC表示某兴趣类的所有关键词搜索的网页集合与UPD之间的SWUI的平均值。最终实验结果如表5所示：

为了更直观的反映对比的效果，本文计算了UPD based相对于None以及Standard的实验结果的提高百分比，如表6所示：

从表6可以看出，首先，使用QEMBUPDSE模型进行查询扩展后，搜索到的网页比不使用查询扩展明显与用户的兴趣更相关。其次，与使用SEPMBDVD模型扩展相比，使用QEMBUPDSE模型进行查询扩展后，搜索到的网页在与用户的相关性上也有一定的提高，反映了网页更符合用户的兴趣。这主要是由于在用户建模之前使用了UPD后，可以使整个用户建模过程得到一定程度的优化，最终的用户兴趣模型更加准确，使查询扩展发挥出更好的效果。

4 结束语

本文在文献[7]提出的基于二级向量的搜索引擎个性化服务模型基础上进行改进，加入了用户个性化词典，用以优化用户兴趣建模过程，进而改善查询扩展的效果。实验表明基于个性化词典的搜索引擎查询扩展模型能够更有效的辅助用户利用搜索引擎搜索到自己感兴趣的信息。在下一步的研究中，需要考虑如何更准确地建立个性化词典和用户兴趣模型，提出更好的相似度计算方法，用以改进整个个性化搜索模型的性能。

参考文献：

[1] 丁国栋，白硕，王斌.一种基于局部共现的查询扩展方法[J].中文信息学报，2006， 20（3）：48-53.

[2] 袁薇，高淼.搜索引擎系统中个性化机制的研究[J].微电子学与计算机，2006（2）：68-75.

[3] 黄名选，严小卫，张师超.基于关联规则挖掘的查询扩展模型研究[J].现代图书情报技术， 2007（10）：47-51.

[4] 黄名选，严小卫，张师超.基于矩阵加权关联规则挖掘的伪相关反馈查询扩展[J].软件学报， 2009，20（7）：1854-1865.

[5] 黄名选，严小卫，张师超.完全加权关联规则挖掘及其在查询扩展中的应用[J].计算机应用研究， 2008，25（6）：1724-1730.

[6] 支凤麟，徐炜民.基于主题的个性化查询扩展模型[J].计算机工程与设计，2010，31（20）：4471-4475.

[7] 徐静秋，朱征宇，谭明红，等.基于二级向量的搜索引擎个性化服务模型[J].计算机科学，2007， 34（11）：89-92.

[8] Zhengyu ZHU， Yunyan TIAN，Kunfeng YUAN，Yong YANG.An Improved Web Document Clustering Method. Journal of Computational Information Systems，2007，3（3）：1087-1094.

[9] Khan M S，Khor S.Enhanced web document retrieval using automatic query expansion[J].Journal of the American Society for Information Science and Technology，2004，55（1）：29-40.

[10] 罗颖，朱征宇，李力沛，等.Web检索模型上个性化词典的研究与实现[J].计算机应用研究，2009（10）.