搜索引擎-一种提示词推荐算法

       搜索引擎可以说目前所有互联网应用里技术含量最高的一种。尽管应用形式比较简单:用户输入查询词,搜索引擎返回搜索结果。但是,搜索引擎需要达到的目标:更全、更快、更准。如何让搜索结果更准确始终是搜索引擎的一大难题。

  公司最近在开发某行业的垂直搜索引擎,我作为该项目组的核心成员主要是负责核心算法的研究工作。我也是刚开始接触这个行业,目前还处于摸索阶段,还有很长的路要走。

言归正传,先谈一下这个项目的背景。这个项目是一个行业性质的垂直搜索引擎。用户分为两大类:普通用户、专业用户。整个项目分为:爬虫技术组,引擎组,大数据分析组和算法组。引擎的爬虫、词库的建立和引擎的选型都不是本文的重点,就一笔带过,重点在于推荐算法的设计。

一、网络爬虫

  系统的数据,需要从几个专业网站进行抓取。尝试了几个爬虫,最后选取heritrix最为我们的爬虫框架,选取它的原因主要是感觉配置项虽然多,但是比较灵活,特别适合我们的要求。当然,爬从技术组也自己尝试实现了一个爬虫,主要是爬取地址比较固定几种数据。

二、词库的建立

  词库初步分为专业主题词、行业普通词库、一般通用词库、废词库、还有用于感情分析的词库。

专业词库的实现前期是采取人工的方式来处理的,并制作了若干的辅助工具,供专业人员来挑选、合并、删除主题词的操作。

后面几种词库的实现,是先选用了搜狗等几种输入法的词库库为基础,在这些词库的基础上对爬虫爬出来的文档进行向量化。

三、引擎的搭建

  通过对采集的数据进行去噪、分段、特征提取,然后把相应的数据导入到solr里。

四、推荐算法

  当用户输入关键词查询的时候,如何让用户查询更准确呢?我们设想,针对用户的输入,我们如果能给出若干个和用户输入的关键词相似度很近的词,以这些作为查询条件,如果我们的算法足够好,搜索出来的结果会大大增加检索的准确度。下面给出具体的算法思路:

从向量化的角度来看,每一篇文档都对应一个向量,其中表示特征项i.

是一个向量由词、词的位置、TF等义项来确定的。对于版本1,我们只取了词、词的位置。我们先用分类规则,把文档分成若干类,基于每一类进行如下计算:

表示两个特征项的相似度。

我们定义一下距离公式

 

我们对于每个文档的特征项,两两求出特征项的相似度。通过这个距离公式

我们可以得出,对于每一个分类,以这些特征项为顶点,以相似度距离为边,就构

成了如下的无向图。

     (lawnet

  类比于wordnet和知网的hownet我们称这个无向图,为lawnet

  那我们的设想问题就转化为:选取任意一个顶点,找出若干个(譬如10个)由这些顶点组成的最小生成树或者边权之和最小的最小子图。这是一个局部最优的随机问题。也就是说,我们只需要满足用户认可的体验程度即可,如果概率为90%,也就是说,当用户输入10000次,我们能成功给出9000次的提示词就行了。

目前的解法我尝试了两种:

  一种PRIM算法。

  第二种算法:先通过floyd算法,算出任意两点的最短距离,作为一个边;这些边就组合成一个集合。然后给任意的顶点,从这个边集合里找出包含这个顶点的前N个最小边。

版权声明:本文为博主原创文章,未经博主允许不得转载。
原链接:http://www.cnblogs.com/bigdatafly/p/4989031.html

发表评论

必填

选填

选填

必填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。