基于形式概念分析的用户查询词扩展方法的研究

Internet已经成为人们日常生活中的主要信息来源之一。搜索引擎是人们在Internet查找所需信息的主要工具。目前主流的搜索引擎主要采用用户查询词与网页中的关键词精确匹配的方式来向用户返回结果。 搜索引擎的重要任务之一就是提供更多与用户查询相关的用户感兴趣的网页，减少用户不感兴趣的网页，即提高查询的精度。查询扩展技术是提高搜索引擎查询精度的主要技术之一。但是由于网页结构上的特殊性，对于搜索引擎这样规模巨大的查询而言，现有的一些查询扩展技术显得力不从心。因此改进现有的查询扩展技术成为了一个热点问题。 本文采用了形式概念分析的方法，在概念格上对搜索引擎中的用户查询词扩展问题进行研究，提出了一套基于形式概念分析的用户查询词扩展方法，赋予了搜索引擎更高的“智能”。本文根据形式概念分析的思想，对用户所需网页的下近似集合中网页进行形式化描述，形成网页—关键词形式背景，并在此形式背景的基础上构建概念格作为本文研究的查询扩展方法的基础数据结构。然后在概念格的基础上，本文探讨了基于极小生成子项集的查询词与非查询词间最小无冗余关联规则的挖掘方法。其中详细讨论了极小生成子项集的概念、生成及其与关键词闭集合之间的关系；给出了通过概念格上的形式概念和它们之间的“父—子”关系以及它们的关键词闭集合的极小生成子项集来生成可信度等于100％、小于100％的关联规则的算法。相对于其它关联规则挖掘方法而言，本文讨论的方法更加符合搜索引擎的实际情况，减少了大量的冗余关联规则，使得整个查询扩展过程在处理时间上比较理想。 最后本文采用C++程序设计语言，将所探讨的查询扩展方法进行了实验。通过5组数量不同的查询词及获取的下近似、上近似网页集合，对查询扩展方法进行验证。实验表明，在查询词个数为3个到7个，下近似网页数量为50个，上近似网页数为60个，每个网页取包含查询词在内的前100个权重最大的关键词来描述该网页的情况下，处理时间是用户可以接受的。文本还在Mushroom数据集上与F.A. Grootjen的查询扩展方法和Zaki的关联规则挖掘方法进行实验对比，实验显示本文的方法能够扩展出较多的关键词，在搜索引擎中具有较大的实际应用价值。