BP神经网络算法在个性化搜索排名中的应用

摘要:介绍了利用BP神经网络算法,通过推理搜索词与环境关键词的关系强度,以及环境关键词对搜索结果排序的影响权重,从而智能地学习用户的搜索环境。通过搜索环境的智能设置,让用户得到更好的搜索体验。

关键词:BP神经网络;搜索引擎结果排名

中图分类号:TP

文献标识码:A

文章编号:1672-3198(2010)15-0315-02

1 引言

自从上世纪90年代万维网的诞生开始,就注定我们将进入搜索引擎时代,可以说我们的生活已经离不开搜索引擎。当前流行的搜索引擎,如Google等搜索能力已经非常强大,可以说“只有想不到,没有搜不到”,而且检索时间通常在0.1秒以内。对于现在的搜索引擎而言,最重要的问题不是能否将所有资源索引到,或者检索速度是否快捷,最重要的问题是如何将符合搜索要求的结果呈现给用户。面对成指数倍增长的网络信息洪流,人们通过“关键词”这种传统的搜索方式检索到的网页,动辄数百万。如何在这浩如烟海的信息中快速找到自己想要的信息,成了现在所有搜索引擎用户最迫切的需求。解决搜索结果的准确性问题,实际上就是解决搜索范围和结果排名的问题。

对于结果排名技术,经典的有Google的PageRankTM算法。它的核心思想是一个网页的质量和重要性可以通过其他网页对其超文本连接的数量来衡量。一个网页被其他网页引用得越多,其PR值就越高。这种算法,目前在通用搜索引擎领域,无疑是较为公正、合理的,但是,它依然没有解决用户的个性化需求。于是专门的个性化搜索引擎的概念应运而生,也成为了近年搜索引擎领域的热点。Google、Yahoo等已经相继推出了个性化搜索引擎创建平台,用户可以在web上根据提示快速建立自己的搜索引擎,创建自己的搜索环境,达到精简搜索范围、自定义排序的目的。

但是,现在的自定义搜索还局限在静态的环境里。比如,用户在Google的平台上创建自己的搜索引擎,必须给出搜索范围(如*.znufe.省略),然后搜索引擎才会在这个范围内搜索,如果要扩展搜索范围,用户必须手动添加。还有,对于一些网站,用户可以给出自定义的排名权重,但是,这个权重是否合理,用户恐怕自己也不清楚。这时,如果能有一种人工智能,辅助用户决策,动态地改善用户搜索环境,无疑能加强用户的搜索体验。

2 搜索引擎原理概述

2.1 搜索引擎原理简介

搜索引擎利用网络爬虫(Spider)程序,漫游访问网络,发现并收集多种类型的文档内容,然后将抓取的内容进行分析,一般包括分词、过滤、转换等工作(具体处理中与文档类型、搜索引擎的具体结构和算法密切相关)。之后,索引器将基于内容分析模块的输出生成索引项并最终建立索引保存到索引库中。用户输入查询语句,搜索引擎将查询语句进行分析,最终得到用户搜索的关键词,然后将包含这些关键词的搜索结果经过特定的排序算法返回给用户。

2.2 通用排序算法

在引言里我们提到了全球最大搜索引擎提供商Google的PageRankTM,又被译作“网页级别”或者“页面等级”,以下简称PR,是Google创始人之一的拉里・佩奇申请的专利技术。它的核心思想是一个网页的质量和重要性可以通过其他网页对其超文本连接的数量来衡量。一个网页被其他网页引用得越多,其PR值就越高。PR值的计算,主要包括三个因素:该网页的链入数量、该网页的链入网页本身的PR值,该网页链入网页本身的链出数量。PR值的计算公式:

PR(A)=(1-d)+d*∑ni=1PR(Ti)C(Ti)

其中,

PR(X)是指网页X的PR值;

Ti是指网页A的第i个的链入网页;

C(Ti)是指网页Ti的链出网页的数量;

d是一个衰减因子,0

PageRankTM技术在很大程度上避免和减少了人为因素,客观地将最恰当的检索结果呈现给用户。当然,纯粹利用PageRankTM显然不够,Google还在系统中整合了对链接的质量分析,包括分析:链接存在时间、链接位置、锚文本及格式、相关性、页面等级。影响Google排名的其他因素还包括:关键词在超文本中出现的次数(超文本匹配分析技术)、网站新旧度、内容的丰富程度、网站访问量等。

2.3 引入环境关键词后的排序

然而,无论是PageRankTM还是其他通用的搜索引擎排序技术都是针对所有的搜索引擎用户而提供的通用排序算法,它无法响应用户个性化需求。于是,近年来对于个性化搜索引擎的研究也越来越多,最著名的产品便是Google的自定义搜索引擎。

Google的自定义搜索引擎向用户提供了一个创建个性化搜索引擎的平台,用户可以通过添加标签和关键字的方式人为改变排名顺序。例如用户对“轮胎”进行搜索,如果没有添加搜索环境关键字,那么会出现的网页可能包括“汽车轮胎”,“赛车轮胎”,“自行车轮胎”等等,但是用户如果设置了环境关键字“自行车”,那么关于“自行车轮胎”的网页排名将会靠前。

3 利用神经网络设置搜索环境

设置搜索环境为用户带来了方便的检索方式,以及个性化的搜索体验。但是我们的搜索环境往往是不断变化而且复杂的,当关键词越来越多,谁的影响权重大,谁的影响权重小,用户自己也难以确定。当用户需要不断地去设置搜索环境,这就变成了一件繁琐的工作,也失去了自定义搜索的意义。于是,我们需要一种智能的搜索引擎系统,可以学习用户的检索习惯,自动生成用户的检索环境。例如,假设现在的搜索环境词包括“自行车”和“汽车”,当用户输入“轮胎”时,搜索引擎应该分别给出搜索词“轮胎”与环境关键词“自行车”和“汽车”的关联强度,以及“自行车+轮胎”和“汽车+轮胎”对搜索结果排名的影响权重,该影响直接表现为哪个组合的权重大,哪个组合的搜索结果排名靠前。这里我们利用BP神经网络的算法学习用户的搜索环境,训练出关联权和影响权。

神经网络模拟神经元处理信息的方式,有的信息使它产生兴奋,有的信息使它受到抑制,多输入,单数出。BP网络是1986年由Rumelhart和McCelland为首的科学家小组提出,是一种按误差逆传播算法训练的多层前馈网络,也是目前应用最为广泛的神经网络模型之一。BP网络能学习和存贮大量的输入-输出模式映射关系,而无需事前揭示描述这种映射关系的数学方程。它的学习规则是使用最速下降法,通过反向传播来不断调整网络的权值和阈值,使网络的误差平方和最小。包括:输入层、隐层、输出层。

图1 神经网络拓扑

BP神经网络可以学习用户的搜索习惯,拓扑图(图1),步骤如下:

(1)用户输入查询词S1(或者查询词组S1,S2……),搜索引擎根据该词与环境关键词之间的连接权Wij计算隐层节点的输出,Wij实际上表示的是第i个搜索词与第j个环境关键词之间的关联程度。作用函数采用经验函数

f(x)=11+e-x

隐节点的输出为

yi=f(∑jWijxj-θi)

其中,Xi表示第i个输入点的取值,但一般,我们认为搜索词之间没有重要性的差别,所以输入值均为1。所以输出调整为

yi=f(∑jWij-θi)

此时,yi实际上表示的是搜索词“S1+KeyWords[i]”对排名的影响权重。表示的是关键词节点的阈值。

(2)计算网页的排名权重

Oi-f(∑jTliyi-θl)

其中,Ol表示第1个网页的排名权重,Tli表示的是“S1+KeyWords[i]”与第1个网页的连接权。θi表示的是网页节点的阈值。

(3)训练网络,根据计算的输出值与真实值之间的误差修正连接权和影响权。这里的真实值是用户对搜索到的网页的点击顺序(或者点击频率)归一化后的结果。当然,前提条件是该用户是理性的。

①误差控制为

E=∑pk=1∑nl=1|tl(k)-O(k)l|

其中,p为训练样本的个数,n为网页节点的个数,tl为该网页节点的真实值(归一化后的实际权重)。

②输出层到隐层的修正。误差公式为

δ1=(t1-Ol)・Ol・(1-Ol)

影响权修正

Tli(k+1)=Tli(k)+ηδiyi

其中,k为迭代次数。阈值修正

θ(k+1)l=θ(k)l+ηδl

③隐层到输入层的修正。误差公式为

δ′i=yi(1-yi)∑lδ1Tli

影响权修正

W(k+1)ij=W(k)ij+η′δ′ixj

阈值修正

θ(k+1)i=θ(k)i+η′δ′i

4 算法调整与测试

上述算法中,关键词需要用户自己设置,但事实上搜索引擎可以提供一种自动设置关键词的机制。比如词汇分类,设置诸如“IT”,“新闻”,“娱乐”,“文学”这种较大的分类词汇。另一种方法,对用户的搜索词进行统计,对检索频率高于一定值的搜索词汇自动设置为环境关键词。对于检索到的页面,搜索引擎可以自动忽略一定数目后的网页,比如用户的检索耐心只有200条,那么只需要对用通用算法排序后的前200条网页进行BP算法的再排序。

随机抽取100名在校同学,让其以“新闻”为搜索词,分别通过Google(通用搜索引擎)、Google自定义搜索(静态设置了环境词的搜索引擎),以及BP算法下的智能搜索引擎进行搜索,并统计在前100条网页中感兴趣的网页数目。结果通过通用搜索引擎检索,准确率平均为12.45%;通过静态设置环境词的搜索引擎,准确率为82.71%;通过BP智能搜索,在进行了451次训练后达到期望精度,在此情况下再进行检索,准确率平均值为96.34%。从而验证了系统的可行性。

5 结语

本文通过介绍BP神经网络算法,反向推理出搜索词与环境关键词的关系强度,以及环境关键词对搜索结果排序的影响权重,智能地学习用户的搜索环境。并对关键词的自动设置提出了建议。

参考文献

[1]Erik Hatcher,Otis Gospodnetic Lucene in Action.

[2]Google自定义搜索API开发人员指南[EB/OL]..

[3]Google的秘密-PageRank彻底解说中文版[EB/OL].Haijime BABA,Ph.D,Kyoto University翻译:袁黄琳www.省略/pagerank_cn.htm.

[4]陈文伟.决策支持系统教程[M].北京:清华大学出版社,2004,(11).

[5]王红霞.神经网络BP算法在网络搜索中的应用[J].微计算机信息,2007,(23):5-3.