BP神經(jīng)網(wǎng)絡(luò)算法在個性化搜索排名中的應(yīng)用

摘要:介紹了利用BP神經(jīng)網(wǎng)絡(luò)算法，通過推理搜索詞與環(huán)境關(guān)鍵詞的關(guān)系強(qiáng)度，以及環(huán)境關(guān)鍵詞對搜索結(jié)果排序的影響權(quán)重，從而智能地學(xué)習(xí)用戶的搜索環(huán)境。通過搜索環(huán)境的智能設(shè)置，讓用戶得到更好的搜索體驗(yàn)。

關(guān)鍵詞:BP神經(jīng)網(wǎng)絡(luò);搜索引擎結(jié)果排名

中圖分類號:TP

文獻(xiàn)標(biāo)識碼:A

文章編號:1672-3198(2010)15-0315-02

1 引言

自從上世紀(jì)90年代萬維網(wǎng)的誕生開始，就注定我們將進(jìn)入搜索引擎時代，可以說我們的生活已經(jīng)離不開搜索引擎。當(dāng)前流行的搜索引擎，如Google等搜索能力已經(jīng)非常強(qiáng)大，可以說“只有想不到，沒有搜不到”，而且檢索時間通常在0.1秒以內(nèi)。對于現(xiàn)在的搜索引擎而言，最重要的問題不是能否將所有資源索引到，或者檢索速度是否快捷，最重要的問題是如何將符合搜索要求的結(jié)果呈現(xiàn)給用戶。面對成指數(shù)倍增長的網(wǎng)絡(luò)信息洪流，人們通過“關(guān)鍵詞”這種傳統(tǒng)的搜索方式檢索到的網(wǎng)頁，動輒數(shù)百萬。如何在這浩如煙海的信息中快速找到自己想要的信息，成了現(xiàn)在所有搜索引擎用戶最迫切的需求。解決搜索結(jié)果的準(zhǔn)確性問題，實(shí)際上就是解決搜索范圍和結(jié)果排名的問題。

對于結(jié)果排名技術(shù)，經(jīng)典的有Google的PageRankTM算法。它的核心思想是一個網(wǎng)頁的質(zhì)量和重要性可以通過其他網(wǎng)頁對其超文本連接的數(shù)量來衡量。一個網(wǎng)頁被其他網(wǎng)頁引用得越多，其PR值就越高。這種算法，目前在通用搜索引擎領(lǐng)域，無疑是較為公正、合理的，但是，它依然沒有解決用戶的個性化需求。于是專門的個性化搜索引擎的概念應(yīng)運(yùn)而生，也成為了近年搜索引擎領(lǐng)域的熱點(diǎn)。Google、Yahoo等已經(jīng)相繼推出了個性化搜索引擎創(chuàng)建平臺，用戶可以在web上根據(jù)提示快速建立自己的搜索引擎，創(chuàng)建自己的搜索環(huán)境，達(dá)到精簡搜索范圍、自定義排序的目的。

但是，現(xiàn)在的自定義搜索還局限在靜態(tài)的環(huán)境里。比如，用戶在Google的平臺上創(chuàng)建自己的搜索引擎，必須給出搜索范圍(如*.znufe.edu.cn)，然后搜索引擎才會在這個范圍內(nèi)搜索，如果要擴(kuò)展搜索范圍，用戶必須手動添加。還有，對于一些網(wǎng)站，用戶可以給出自定義的排名權(quán)重，但是，這個權(quán)重是否合理，用戶恐怕自己也不清楚。這時，如果能有一種人工智能，輔助用戶決策，動態(tài)地改善用戶搜索環(huán)境，無疑能加強(qiáng)用戶的搜索體驗(yàn)。

2 搜索引擎原理概述

2.1 搜索引擎原理簡介

搜索引擎利用網(wǎng)絡(luò)爬蟲(Spider)程序，漫游訪問網(wǎng)絡(luò)，發(fā)現(xiàn)并收集多種類型的文檔內(nèi)容，然后將抓取的內(nèi)容進(jìn)行分析，一般包括分詞、過濾、轉(zhuǎn)換等工作(具體處理中與文檔類型、搜索引擎的具體結(jié)構(gòu)和算法密切相關(guān))。之后，索引器將基于內(nèi)容分析模塊的輸出生成索引項(xiàng)并最終建立索引保存到索引庫中。用戶輸入查詢語句，搜索引擎將查詢語句進(jìn)行分析，最終得到用戶搜索的關(guān)鍵詞，然后將包含這些關(guān)鍵詞的搜索結(jié)果經(jīng)過特定的排序算法返回給用戶。

2.2 通用排序算法

在引言里我們提到了全球最大搜索引擎提供商Google的PageRankTM，又被譯作“網(wǎng)頁級別”或者“頁面等級”，以下簡稱PR，是Google創(chuàng)始人之一的拉里·佩奇申請的專利技術(shù)。它的核心思想是一個網(wǎng)頁的質(zhì)量和重要性可以通過其他網(wǎng)頁對其超文本連接的數(shù)量來衡量。一個網(wǎng)頁被其他網(wǎng)頁引用得越多，其PR值就越高。PR值的計(jì)算，主要包括三個因素:該網(wǎng)頁的鏈入數(shù)量、該網(wǎng)頁的鏈入網(wǎng)頁本身的PR值，該網(wǎng)頁鏈入網(wǎng)頁本身的鏈出數(shù)量。PR值的計(jì)算公式:

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

其中，

PR(X)是指網(wǎng)頁X的PR值;

Ti是指網(wǎng)頁A的第i個的鏈入網(wǎng)頁;

C(Ti)是指網(wǎng)頁Ti的鏈出網(wǎng)頁的數(shù)量;

d是一個衰減因子，0

PageRankTM技術(shù)在很大程度上避免和減少了人為因素，客觀地將最恰當(dāng)?shù)臋z索結(jié)果呈現(xiàn)給用戶。當(dāng)然，純粹利用PageRankTM顯然不夠，Google還在系統(tǒng)中整合了對鏈接的質(zhì)量分析，包括分析:鏈接存在時間、鏈接位置、錨文本及格式、相關(guān)性、頁面等級。影響Google排名的其他因素還包括:關(guān)鍵詞在超文本中出現(xiàn)的次數(shù)(超文本匹配分析技術(shù))、網(wǎng)站新舊度、內(nèi)容的豐富程度、網(wǎng)站訪問量等。

2.3 引入環(huán)境關(guān)鍵詞后的排序

然而，無論是PageRankTM還是其他通用的搜索引擎排序技術(shù)都是針對所有的搜索引擎用戶而提供的通用排序算法，它無法響應(yīng)用戶個性化需求。于是，近年來對于個性化搜索引擎的研究也越來越多，最著名的產(chǎn)品便是Google的自定義搜索引擎。

Google的自定義搜索引擎向用戶提供了一個創(chuàng)建個性化搜索引擎的平臺，用戶可以通過添加標(biāo)簽和關(guān)鍵字的方式人為改變排名順序。例如用戶對“輪胎”進(jìn)行搜索，如果沒有添加搜索環(huán)境關(guān)鍵字，那么會出現(xiàn)的網(wǎng)頁可能包括“汽車輪胎”，“賽車輪胎”，“自行車輪胎”等等，但是用戶如果設(shè)置了環(huán)境關(guān)鍵字“自行車”，那么關(guān)于“自行車輪胎”的網(wǎng)頁排名將會靠前。

3 利用神經(jīng)網(wǎng)絡(luò)設(shè)置搜索環(huán)境

設(shè)置搜索環(huán)境為用戶帶來了方便的檢索方式，以及個性化的搜索體驗(yàn)。但是我們的搜索環(huán)境往往是不斷變化而且復(fù)雜的，當(dāng)關(guān)鍵詞越來越多，誰的影響權(quán)重大，誰的影響權(quán)重小，用戶自己也難以確定。當(dāng)用戶需要不斷地去設(shè)置搜索環(huán)境，這就變成了一件繁瑣的工作，也失去了自定義搜索的意義。于是，我們需要一種智能的搜索引擎系統(tǒng)，可以學(xué)習(xí)用戶的檢索習(xí)慣，自動生成用戶的檢索環(huán)境。例如，假設(shè)現(xiàn)在的搜索環(huán)境詞包括“自行車”和“汽車”，當(dāng)用戶輸入“輪胎”時，搜索引擎應(yīng)該分別給出搜索詞“輪胎”與環(huán)境關(guān)鍵詞“自行車”和“汽車”的關(guān)聯(lián)強(qiáng)度，以及“自行車+輪胎”和“汽車+輪胎”對搜索結(jié)果排名的影響權(quán)重，該影響直接表現(xiàn)為哪個組合的權(quán)重大，哪個組合的搜索結(jié)果排名靠前。這里我們利用BP神經(jīng)網(wǎng)絡(luò)的算法學(xué)習(xí)用戶的搜索環(huán)境，訓(xùn)練出關(guān)聯(lián)權(quán)和影響權(quán)。

神經(jīng)網(wǎng)絡(luò)模擬神經(jīng)元處理信息的方式，有的信息使它產(chǎn)生興奮，有的信息使它受到抑制，多輸入，單數(shù)出。BP網(wǎng)絡(luò)是1986年由Rumelhart和McCelland為首的科學(xué)家小組提出，是一種按誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò)，也是目前應(yīng)用最為廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。BP網(wǎng)絡(luò)能學(xué)習(xí)和存貯大量的輸入-輸出模式映射關(guān)系，而無需事前揭示描述這種映射關(guān)系的數(shù)學(xué)方程。它的學(xué)習(xí)規(guī)則是使用最速下降法，通過反向傳播來不斷調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，使網(wǎng)絡(luò)的誤差平方和最小。包括:輸入層、隱層、輸出層。

圖1 神經(jīng)網(wǎng)絡(luò)拓?fù)?/p>

BP神經(jīng)網(wǎng)絡(luò)可以學(xué)習(xí)用戶的搜索習(xí)慣，拓?fù)鋱D(圖1)，步驟如下:

(1)用戶輸入查詢詞S1(或者查詢詞組S1，S2……)，搜索引擎根據(jù)該詞與環(huán)境關(guān)鍵詞之間的連接權(quán)Wij計(jì)算隱層節(jié)點(diǎn)的輸出，Wij實(shí)際上表示的是第i個搜索詞與第j個環(huán)境關(guān)鍵詞之間的關(guān)聯(lián)程度。作用函數(shù)采用經(jīng)驗(yàn)函數(shù)

f(x)=11+e-x

隱節(jié)點(diǎn)的輸出為

yi=f(∑jWijxj-θi)

其中，Xi表示第i個輸入點(diǎn)的取值，但一般，我們認(rèn)為搜索詞之間沒有重要性的差別，所以輸入值均為1。所以輸出調(diào)整為

yi=f(∑jWij-θi)

此時，yi實(shí)際上表示的是搜索詞“S1+KeyWords[i]”對排名的影響權(quán)重。表示的是關(guān)鍵詞節(jié)點(diǎn)的閾值。

(2)計(jì)算網(wǎng)頁的排名權(quán)重

Oi-f(∑jTliyi-θl)

其中，Ol表示第1個網(wǎng)頁的排名權(quán)重，Tli表示的是“S1+KeyWords[i]”與第1個網(wǎng)頁的連接權(quán)。θi表示的是網(wǎng)頁節(jié)點(diǎn)的閾值。

(3)訓(xùn)練網(wǎng)絡(luò)，根據(jù)計(jì)算的輸出值與真實(shí)值之間的誤差修正連接權(quán)和影響權(quán)。這里的真實(shí)值是用戶對搜索到的網(wǎng)頁的點(diǎn)擊順序(或者點(diǎn)擊頻率)歸一化后的結(jié)果。當(dāng)然，前提條件是該用戶是理性的。

①誤差控制為

E=∑pk=1∑nl=1|tl(k)-O(k)l|<ε

其中，p為訓(xùn)練樣本的個數(shù)，n為網(wǎng)頁節(jié)點(diǎn)的個數(shù)，tl為該網(wǎng)頁節(jié)點(diǎn)的真實(shí)值(歸一化后的實(shí)際權(quán)重)。

②輸出層到隱層的修正。誤差公式為

δ1=(t1-Ol)·Ol·(1-Ol)

影響權(quán)修正

Tli(k+1)=Tli(k)+ηδiyi

其中，k為迭代次數(shù)。閾值修正

θ(k+1)l=θ(k)l+ηδl

③隱層到輸入層的修正。誤差公式為

δ′i=yi(1-yi)∑lδ1Tli

影響權(quán)修正

W(k+1)ij=W(k)ij+η′δ′ixj

閾值修正

θ(k+1)i=θ(k)i+η′δ′i

4 算法調(diào)整與測試

上述算法中，關(guān)鍵詞需要用戶自己設(shè)置，但事實(shí)上搜索引擎可以提供一種自動設(shè)置關(guān)鍵詞的機(jī)制。比如詞匯分類，設(shè)置諸如“IT”，“新聞”，“娛樂”，“文學(xué)”這種較大的分類詞匯。另一種方法，對用戶的搜索詞進(jìn)行統(tǒng)計(jì)，對檢索頻率高于一定值的搜索詞匯自動設(shè)置為環(huán)境關(guān)鍵詞。對于檢索到的頁面，搜索引擎可以自動忽略一定數(shù)目后的網(wǎng)頁，比如用戶的檢索耐心只有200條，那么只需要對用通用算法排序后的前200條網(wǎng)頁進(jìn)行BP算法的再排序。

隨機(jī)抽取100名在校同學(xué)，讓其以“新聞”為搜索詞，分別通過Google(通用搜索引擎)、Google自定義搜索(靜態(tài)設(shè)置了環(huán)境詞的搜索引擎)，以及BP算法下的智能搜索引擎進(jìn)行搜索，并統(tǒng)計(jì)在前100條網(wǎng)頁中感興趣的網(wǎng)頁數(shù)目。結(jié)果通過通用搜索引擎檢索，準(zhǔn)確率平均為12.45%;通過靜態(tài)設(shè)置環(huán)境詞的搜索引擎，準(zhǔn)確率為82.71%;通過BP智能搜索，在進(jìn)行了451次訓(xùn)練后達(dá)到期望精度，在此情況下再進(jìn)行檢索，準(zhǔn)確率平均值為96.34%。從而驗(yàn)證了系統(tǒng)的可行性。

5 結(jié)語

本文通過介紹BP神經(jīng)網(wǎng)絡(luò)算法，反向推理出搜索詞與環(huán)境關(guān)鍵詞的關(guān)系強(qiáng)度，以及環(huán)境關(guān)鍵詞對搜索結(jié)果排序的影響權(quán)重，智能地學(xué)習(xí)用戶的搜索環(huán)境。并對關(guān)鍵詞的自動設(shè)置提出了建議。

參考文獻(xiàn)

[1]Erik Hatcher，Otis Gospodnetic Lucene in Action.

[2]Google自定義搜索API開發(fā)人員指南[EB/OL].http://code.google.com/intl/zh-CN/apis/customsearch/docs/dev_guide.html.

[3]Google的秘密-PageRank徹底解說中文版[EB/OL].Haijime BABA，Ph.D，Kyoto University翻譯:袁黃琳http://www.kreny.com/pagerank_cn.htm.

[4]陳文偉.決策支持系統(tǒng)教程[M].北京:清華大學(xué)出版社，2004，(11).

[5]王紅霞.神經(jīng)網(wǎng)絡(luò)BP算法在網(wǎng)絡(luò)搜索中的應(yīng)用[J].微計(jì)算機(jī)信息，2007，(23):5-3.