BP神經網絡算法在個性化搜索排名中的應用
2010-12-31 00:00:00歐洋伶
現代商貿工業 2010年15期
摘要:介紹了利用BP神經網絡算法，通過推理搜索詞與環境關鍵詞的關系強度，以及環境關鍵詞對搜索結果排序的影響權重，從而智能地學習用戶的搜索環境。通過搜索環境的智能設置，讓用戶得到更好的搜索體驗。
關鍵詞:BP神經網絡;搜索引擎結果排名
中圖分類號:TP
文獻標識碼:A
文章編號:1672-3198(2010)15-0315-02
1 引言
自從上世紀90年代萬維網的誕生開始，就注定我們將進入搜索引擎時代，可以說我們的生活已經離不開搜索引擎。當前流行的搜索引擎，如Google等搜索能力已經非常強大，可以說“只有想不到，沒有搜不到”，而且檢索時間通常在0.1秒以內。對于現在的搜索引擎而言，最重要的問題不是能否將所有資源索引到，或者檢索速度是否快捷，最重要的問題是如何將符合搜索要求的結果呈現給用戶。面對成指數倍增長的網絡信息洪流，人們通過“關鍵詞”這種傳統的搜索方式檢索到的網頁，動輒數百萬。如何在這浩如煙海的信息中快速找到自己想要的信息，成了現在所有搜索引擎用戶最迫切的需求。解決搜索結果的準確性問題，實際上就是解決搜索范圍和結果排名的問題。
對于結果排名技術，經典的有Google的PageRankTM算法。它的核心思想是一個網頁的質量和重要性可以通過其他網頁對其超文本連接的數量來衡量。一個網頁被其他網頁引用得越多，其PR值就越高。這種算法，目前在通用搜索引擎領域，無疑是較為公正、合理的，但是，它依然沒有解決用戶的個性化需求。于是專門的個性化搜索引擎的概念應運而生，也成為了近年搜索引擎領域的熱點。Google、Yahoo等已經相繼推出了個性化搜索引擎創建平臺，用戶可以在web上根據提示快速建立自己的搜索引擎，創建自己的搜索環境，達到精簡搜索范圍、自定義排序的目的。
但是，現在的自定義搜索還局限在靜態的環境里。比如，用戶在Google的平臺上創建自己的搜索引擎，必須給出搜索范圍(如*.znufe.edu.cn)，然后搜索引擎才會在這個范圍內搜索，如果要擴展搜索范圍，用戶必須手動添加。還有，對于一些網站，用戶可以給出自定義的排名權重，但是，這個權重是否合理，用戶恐怕自己也不清楚。這時，如果能有一種人工智能，輔助用戶決策，動態地改善用戶搜索環境，無疑能加強用戶的搜索體驗。
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].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]陳文偉.決策支持系統教程[M].北京:清華大學出版社，2004，(11). [5]王紅霞.神經網絡BP算法在網絡搜索中的應用[J].微計算機信息，2007，(23):5-3.
