搜索引擎查询模块中词与词之间的关联度研究

　　搜索引擎查询模块中词与词之间的关联度研究

　　搜索引擎是计算机的一个重要领域。本文对数据挖掘中的关联规则算法进行改进，并与搜索引擎技术相结合，以提高传统搜索引擎的召回率和准确率。通过改进的关联规则算法和相关的改进树算法，可以建立查询关键词和网页词条之间的相关性，最终可以计算出该网页在搜索结果中的排名。

　　主要工作和研究成果如下：

　　(1）由于传统的关键词查询算法存在召回率和准确率低的问题，文章对传统的经典apriori算法进行了改进，可以很好的与搜索引擎技术结合；首次将关联规则与搜索引擎相结合技术。

　　(2）由于改进的apriori算法存在多次扫描数据库、效率低的问题，引入树的概念来改进搜索引擎。

　　（3）由于上述改进算法没有考虑网页术语的权重，因此与现实存在差距，因此我们在此创造性地使用加权支持来解决搜索引擎中的加权术语查询问题。

　　(4）由于加权过滤方法不够精细过滤，将利用树的思想解决相关的加权过滤问题。基于关联规则推理引擎的推理

　　基于Apriori算法的搜索引擎的实现过程是先使用网络爬虫对网页进行抓取，然后对抓取到的网页进行细分，再利用关联推理模块过滤掉无用的词条。然后计算网页中每个过滤词与每个查询关键词之间的相似度，就可以轻松计算出该网页与查询信息的相似度之和。最后，对页面进行排序。

　　本文的重点是搜索引擎查询模块中单词之间的关系。该推理模块的主要任务是对从上层接收到的查询语句进行推理，以计算网页上单个单词与查询单个单词之间的相关性。

　　(a) 词间相关性判断

　　在网页中，如果网页本体术语通过属性直接连接到查询关键词，则称这两个词直接相关；而两者通过一系列单独的词和属性间接连接的词是一种间接关联。如上所述，本体词A通过属性1与词B相关，该属性被表示为（A，1，B）。本体词A和词B之间的联系称为直接关联。同理(B,1,A),(A,2,C)，本体词B与词C的连接方式称为间接连接。如下图所示：

　　关系图

　　大量关于网页本体术语的文献研究都是基于以上两种关联来计算单个网页词之间的相似度。由于网页中大量的词和词之间的联系很少，如果对这些词进行联系计算，那么这样做必然会影响效率。

　　为了解决上述问题，可以考虑两种情况。 (1)在计算query 关键词与权重高的词(如网页标题词或文章关键词)的相关性时，间接关联性和直接关联性都要考虑；(2)在一般网页的正文部分，不考虑间接关联，即如果查询关键词和网页中的单个词通过属性直接相连，则认为它们是相关的。否则，可以认为两者没有关系。

　　(b) 关联规则过滤思路

　　关联规则是在给定数据集中查找项目之间的联系。当输入的查询信息被本体描述时，返回查询关键词 set Q={Xi,Xj,Xk……}。假设相关数据 D 是一个网页中的词条集合，每个词条都有一个唯一的标识符，称为 TID。本体描述后，每个网页对应一个网页单个词集K'={Yw,Yq,Yx...}，同时建立与集合Q的属性相关联的网页单个词集K ，分别判断集合Q中的每个关键词与集合K'中的每个词项是否有关联关系，即是否通过属性相关。若Yw与Xi有属性相关，则将Yw放入K集合；如果没有相关性，就不要放。

　　假设这里Yw和Yq是K集中的元素，Yw和Xi是相关的。根据协会章程，习有相关支持；如果Yw与Xi相关联，Yw也与Xj相关联，那么{Xi,Xj}的支持度可以设为s，其中s为D中收录Xi∪Xj的百分比（即Xi 和 Xj)。即：

　　支持{Xi,Xj}=P(Xi∪Xj)[15]

　　Support 表示支持程度。以Xi和Xj为例，这里指的是网页中与Xi和Xj都相关的单个词的数量。

　　挖掘关联规则的问题是必须满足以下条件：

　　sup(X∪Y)≥minsup【16】

　　其中，假设关联项的支持度一定不能小于最小支持度（min_sup）。如果k集中元素的支持度大于或等于最小支持度，则该k项集称为频繁k项集。频繁k项集的集合记为L。Ck称为候选频繁k项集的集合，Ck=(r|r为k项集，s

　　挖掘关联规则的过程可以描述如下：

　　1) 查找所有相关项：根据定义，这些相关项的支持度至少等于预定义的最小支持度。

　　2) 频繁项集生成强关联规则：根据定义，这些规则必须满足最小支持度。

　　在候选频繁项集Ck的过程中，本文删除了不必要的扫描事务，以压缩事务数据库，提高扫描效率。 [11]

　　在第一次扫描候选集的过程中，生成的C1是一个有序的项目集。设Q为事务所收录的项，即得到第一个频繁项集L1，执行连接，生成C2，C2有序；所以以此类推，每次连接后生成的Ck都是有序的。因此，第一次扫描事务后，统计每个元素相关的支持度，将长度小于最小支持度（min_sup）的单个元素删除，因为此项不会影响第二个生成的频繁选项集L2以此类推，每次扫描后，统计每个item的支持度，删除当前长度小于最小支持度(min_sup)的item，因为这个item不会对下层候选产生影响集合稍后生成。这样就可以过滤掉网页中与单个查询关键词本体高度相关的单个词。这里结合Apriori核心算法实现推理引擎的语义检索功能。