搜索引擎頁面排序算法研究綜述
2007-01-01 00:00:00李紹華高文宇
計算機應用研究 2007年6期
摘 要：系統地分析了現有的頁面排序算法，指出了它們各自的優勢和存在的不足，并指出不同算法在不同領域和場合所具有的優勢。建立專業搜索引擎是提高搜索準確性和性能的有效途徑。通過網格技術將各種專業搜索引擎集成在一起，形成一個基于網格的搜索引擎，從而更好地滿足不同背景不同偏好的用戶需求。
關鍵詞：搜索引擎；頁面排序；鏈接分析
中圖分類號：TP393.09文獻標志碼：A
文章編號：1001-3695(2007)06-0004-04
隨著Internet的飛速發展，其提供的文檔（網頁）也以驚人的速度在增長。有關的調查統計表明，Internet上的網頁每不到一年的時間就會增長一倍。要從這么大量的信息庫中提取出有用的信息就越來越依賴于搜索引擎的功能。而網頁的排序則是搜索引擎要解決的關鍵問題之一。
Sergey Brin等人［1］提出PageRank算法開啟了鏈接分析研究的熱潮。基于鏈接分析的算法，提供了一種衡量網頁質量的客觀方法；獨立于語言，獨立于內容；無需人工干預就能自動發現Web上的重要資源，挖掘出Web上的重要社區，自動實現文檔分類。PageRank在Google中的應用獲得了巨大的商業成功。在最初的Google中，首先使用IR（Information Retrieve）算法找到所有與查詢關鍵字相匹配的網頁；然后根據頁面因素（標題、關鍵字密度等）進行排名；最后通過PageRank得分調整網站排名結果。
近幾年來，基于鏈接分析的頁面排序算法一直是一個熱點問題，學者提出了許多頁面排序算法。
1 PageRank及其相關算法
基于鏈接分析的排序算法中，最為著名的就是PageRank。所謂鏈接分析主要基于如下兩個重要假設：
①超文本鏈接包含了用戶對一個網站的判斷信息；
②對一個網站而言，如果其他網站鏈接到該網站的入鏈數越多，該網站越重要。
以上假設在各種基于鏈接分析的算法中均以某種方式體現出來。
1.１ PageRank算法
PageRank算法是最早提出的鏈接分析算法之一，并被Google用于計算網頁的重要性得分。其基本思想是：如果網頁T存在一個指向網頁A的鏈接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分的值則由T的PageRank值PR(T)和T的出鏈（從T鏈出的鏈接）數C(T) 決定。具體公式為：PR(T) / C(T) 。而對于頁面A，其PageRank值PR(A)的計算如下：
PR（A）=PR（T1）/C（T1）+…+PR（Tn)/C(Tn)（1）
其中，T1，T2，…， Tn為含有指向A鏈接的頁面。
為了避免Link Sink（許多網頁沒有入鏈或出鏈）問題，對式（1）引入一個阻尼系數d，使其變為
PR（A）=（1-d)+d[PR(T1)/C(T1)+…+PR(Tn)/C(Tn)]（2）
如此經過多次迭代，系統的PR值達到收斂。
PR的計算公式可以從概率的角度解釋為一個隨機網絡沖浪者隨機選擇一個網頁后，不斷地點擊網頁上的鏈接，但是從不返回；除非最后厭煩了才隨機選擇另一個頁面。隨機沖浪者訪問某個頁面的隨機概率就是該頁面的PageRank值；阻尼系數d就是隨機沖浪者在某個頁面會厭煩然后選擇一個新頁面的概率。頁面的PageRank值越高，則隨機沖浪者發現它的概率亦越高。這種思路非常富有創意。一個網頁的外部鏈接越多，則對網絡沖浪者來說，發現它的機會也就越大。
文獻［2］結合近年來Web出現的一些新特性對PageRank提出了一些改進措施。文獻［3］中對PageRank算法中的阻尼系數d進行了深入討論，從理論上分析了d的取值不同對于PageRank算法效果的影響。文獻［4］提出了一種方法用于對PageRank中的迭代計算進行加速。
PageRank的一個優勢在于它是一個與查詢無關的靜態算法，因此所有網頁的PageRank值均可以通過離線計算獲得。這樣有效地減少了在線查詢時的運算量，極大地降低了查詢響應時間。
然而Internet上的內容涵蓋了眾多主題，在現實應用中，人們的查詢所希望得到的信息往往是具有某一方面主題特征的，而PageRank僅僅依靠計算網頁的外部鏈接數量來決定該網頁的排名，而忽略了頁面的主題相關性，從而影響了搜索結果的相關性和準確性。
另一方面，PageRank算法對新網頁有很嚴重的歧視性，因為一個新網頁入鏈數量通常都很少，自然PR值很低。1.２ TopicSensitive PageRank
由于Internet上的內容千差萬別，涵蓋眾多不同的領域和主題。同樣一個查詢如“汽車”，可能用戶1是想買一臺汽車，他感興趣的是汽車品牌、價格；而用戶2是想參加與汽車相關的運動，他感興趣的是與汽車相關的運動項目和賽事。因此要想給用戶返回更為準確的查詢信息就有必要基于不同的主題來對頁面排序。最初的PageRank算法中是沒有考慮主題相關因素的。主題敏感PageRank算法（TopicSensitive PageRank，TSPR）［5］正是在這種背景下提出來的。
TSPR核心思想就是通過離線計算，計算出一個PageRank向量集合（在PageRank算法中，僅計算一個PageRank向量），該集合中的每一個向量與某一主題相關，即計算某個頁面關于不同主題的得分。例如某個網頁在教育這個主題的得分為a，在體育這個主題的得分為b，……。
具體來說，TSPR也可分為兩個主要階段：
（1）主題相關的PageRank向量集合的計算。
先將所有頁面的內容劃分為16個主題，根據Crawler搜集來的網頁，計算該網頁在不同主題的得分情況，即不同的PageRank向量。
（2）在線查詢，主題的確定。
根據用戶的查詢請求和相關Context判斷用戶查詢相關的主題（即用戶的興趣取向），從而提高返回結果的準確性無疑是一種有效的方法。
遺憾的是TSPR并沒有利用主題的相關性來提高鏈接得分的準確性。事實上對于網頁類別的劃分可以更有效地計算鏈接的價值和權威性。例如評閱論文時，經常需要填寫對相關領域的熟悉程度。也就是說，評閱者對論文所屬的領域越熟悉，則評閱者所給出的評分越可信，從而在最后的計算中擁有更高的權重。
對于網頁之間的鏈接分析與上述論文評閱的例子類似。可以把網頁A指向網頁B的鏈接視為A對B的評分；若A與B的內容是相近的，則A的評分更為可信。例如一個教育相關的網站A指向另一個教育相關的網站B，較一個娛樂相關的網站C指向教育相關的網站B更為權威、可信。
因此，可以將上述思想應用到PageRank的PR值計算中。這將在今后的研究工作中作進一步的考慮。
1.3 Hilltop
Hilltop［6］算法的指導思想與PageRank是一致的，即通過鏈接的數量和質量來確定搜索結果的排序權重。與PageRank不同的是，在Hilltop中僅考慮那些專家頁面（Export Sources），即專門用于引導人們瀏覽資源的頁面。Hilltop在收到一個查詢請求時，首先根據查詢的主題計算出一列相關性最強的專家頁面，然后根據指向目標頁面的非從屬專家頁面的數量和相關性來對目標頁面進行排序。目標頁面的排序得分反映了與查詢主題相關的最好的獨立專家頁面的集體意見。若在此過程中，Hilltop無法得到一個足夠大的專家頁面集合，則返回空值。
Hilltop算法主要包含兩個步驟：
（1）專家頁面搜索。
所謂專家頁面就是關于某個主題的包含著很多非從屬頁面鏈接的網頁。非從屬頁面是指兩個頁面分別屬于兩個來自非從屬組織的作者。在預處理階段，由搜索引擎的Crawler搜集來的網頁的一個子集被辨識為專家頁面集。
辨識專家頁面的關鍵主要有：
①剔除從屬頁面；
②選擇專家頁面（OutLink大于閾值k）；
③對專家頁面進行索引。
當收到一個查詢時，從專家頁面集中挑選出與查詢主題相關的專家頁面子集。
（2）目標頁面排序。
Hilltop算法認為“一個目標頁面在某個查詢主題是權威的當且僅當有一些與該查詢主題相關的最好的專家頁面指向該目標頁面。”
然而，Hilltop在應用中還存在如下一些問題：
專家頁面的搜索和確定對算法起關鍵作用，專家頁面的質量決定了算法的準確性；而專家頁面的質量和公平性在一定程度上難以保證。同時Hilltop忽略了大多數非專家頁面的影響。在Hilltop的原型系統中，專家頁面只占到整個頁面的1.79%（2.5~140 M），在一定程度上并不能很好地反映整個Internet的民意。
Hilltop算法在無法得到足夠的專家頁面子集時（小于兩個專家頁面），返回為空，即Hilltop適合于對查詢排序進行求精，而不能覆蓋。這意味著Hilltop可以與某個頁面排序算法結合，提高精度，而不適合作為一個獨立的頁面排序算法。
Hilltop中根據查詢主題從專家頁面集合中選取與主題相關的子集也是在線運行的，這與前面提到的HITS算法一樣會影響查詢響應時間。隨著專家頁面集合的增大，算法的可伸縮性存在不足之處。
2 HITS及其相關算法
2.1 HITS算法
HITS（HypertextInduced Topic Search）算法是Kleinberg［7］提出的。它是IBM Almaden Research Center的“CLEVER”研究項目的一部分。
對于每個頁面P，HITS算法計算兩個值，即Authority和Hub。Authority和Hub之間滿足如下關系：對于Authority，如果有越多具有好Hub的頁面指向P，P的Authority值就越大； 對于Hub， 如果P指向越多具有好Authority的頁面，P的Hub值就越大。對整個Web集合而言，Authority和Hub是相互依賴、相互加強的關系。Authority和Hub之間相互優化的關系，即為HITS算法的基礎。
在HITS算法中，將查詢q提交給傳統的基于關鍵字匹配的搜索引擎。搜索引擎返回很多網頁，從中取前n個網頁作為根集(Root Set)，用S表示。S滿足三個條件：
①S中網頁數量相對較小；
②S中網頁大多數是與查詢q相關的網頁；
③S中網頁包含較多的權威網頁。
通過向S中加入被S引用的網頁和引用S的網頁，將S擴展成一個更大的集合T。
以T中的Hub網頁為頂點集V1，以權威網頁為頂點集V2，V1中的網頁到V2中的網頁的超鏈接為邊集E，形成一個二分有向圖SG=(V1，V2，E)。對V1中的任一個頂點v，用h(v)表示網頁v的Hub值；對V2中的頂點u，用a(u)表示網頁的Authority值。開始時h(v)=a(u)=1，對u執行I操作修改其a(u)，對v執行O操作修改其h(v)；然后規范化a(u)、h(v)；如此不斷重復計算下面的操作I、O，直到a(u)、h(v)收斂。HITS算法輸出一組具有較大Hub值的網頁和具有較大權威值的網頁。
實驗數據表明， HITS的排名準確性要比PageRank高。但是HITS最大的問題在于它是一個依賴于查詢關鍵字的算法，在線運算量大，極大地影響了算法的可伸縮性，從而難以應用于大規模的網頁數據集。
HITS算法還存在著主題漂移問題，即緊密鏈接TKC（TightlyKnit Community Effect）現象。如果在集合T中有少數與查詢主題無關的網頁，但是緊密鏈接的，HITS算法的結果可能就是這些網頁。因為HITS只能發現主社區，偏離了原來的查詢主題。
用HITS進行窄主題查詢時，可能產生主題泛化問題，即擴展以后引入了比原來主題更重要的新主題，新主題可能與原始查詢無關。泛化的原因是因為網頁中包含不同主題的向外鏈接，而且新主題的鏈接更加具有重要性。
針對HITS的這些問題提出了許多改進算法，如SALSA［8］、BFS［9］、PHITS［10］等。
2.2 SALSA
PageRank算法是基于用戶隨機的向前瀏覽網頁的直覺知識，HITS算法考慮的是Authority網頁和Hub網頁之間的加強關系。實際應用中，用戶大多數情況下是向前瀏覽網頁，但是很多時候也會回退瀏覽網頁。基于上述直覺知識，R.Lempel和S.Moran提出了SALSA（Stochastic Approach for LinkStructure Analysis）算法。該算法考慮了用戶回退瀏覽網頁的情況，保留了PageRank的隨機漫游和HITS中把網頁分為Authority和Hub的思想，取消了Authority與Hub之間的相互加強關系。
具體算法如下：
（1）與HITS算法的第一步一樣，得到根集并且擴展為網頁集合T，并除去孤立節點。
（2）從集合T構造無向圖G′=(Vh，Va，E)：
（3）定義兩條馬爾可夫鏈的變化矩陣，也是隨機矩陣，分別是Hub矩陣H和Authority矩陣A。
（4）求出矩陣H和A的主特征向量，得到對應的馬爾可夫鏈的靜態分布。
（5）A中值大者對應的網頁就是所要找的重要網頁。
SALSA算法沒有HITS中相互加強的迭代過程，計算量遠小于HITS。SALSA算法只考慮直接相鄰的網頁對自身AH的影響；而HITS是計算整個網頁集合T對自身AH的影響。
試驗結果表明，HITS算法結果集中于主題的某個方面。而SALSA算法的結果覆蓋了多個方面，也就是說，對于TKC現象，SALSA算法比HITS算法有更高的健壯性。
2.3 BFS
SALSA算法計算網頁的Authority值時，只考慮網頁在直接相鄰網頁集中的受歡迎程度，忽略了其他網頁對它的影響。HITS算法考慮的是整個圖的結構，特別地，經過n步以后，網頁i的Authority的權重是｜BFn(i)｜/｜BFn｜。BFn(i)為離開網頁i的(BF)n的路徑數目，即網頁j<>i，對i的權值貢獻等于從i到j的(BF)n路徑數量。如果從i到j包含有一個回路，那么j對i的貢獻將會呈指數級增加，這并不是算法所希望的，因為回路可能不是與查詢相關的。
Allan Borodin等人提出了BFS（Backward Forward Step）算法，既是SALSA的擴展情況，也是HITS的限制情況。其基本思想是，SALSA只考慮直接相鄰網頁的影響，BFS擴展到考慮路徑長度為n的相鄰網頁的影響。在BFS中，BFn(i)被指定表示能通過(BF)n路徑到達i的節點集合，這樣j對i的貢獻就依賴于j到i的距離。BFS采用指數級降低權值的方式，節點i的權值計算如下：
2.4 PHITS
D.Cohn and H.Chang提出了計算Hub和Authority的統計算法PHITS（Probabilistic Analogue of the HITS）。他們提出了一個概率模型。在這個模型中，一個潛在的因子或主題z影響了文檔d到c的一個鏈接。PHITS算法進一步假定，給定因子z，文檔c的條件分布P(c｜z)存在，并且給定文檔d，因子z的條件分布P(z｜d)也存在。
PHITS算法使用Dempster等人［11］提出的EM算法分配未知的條件概率，使得L最大化，即最好地解釋了網頁之間的鏈接關系。算法要求因子z的數目事先給定。Allan Borodin等人［9］指出，PHITS中使用的EM算法可能會收斂于局部最大化，而不是真正的全局最大化。D. Cohn等人［12］還提出了結合文檔內容和超鏈接的概率模型。
3 頁面排序算法的一些新觀點
3.1 Link Fusion
鑒于目前大多數頁面排序算法只分析包含在Web頁面中的鏈接，文獻［13］提出了Link Fusion頁面排序算法。在該算法中，將鏈接分為兩類：①Intratype Links。用于表示同一數據空間中的數據對象關系，多指包含在Web頁面中的鏈接。②Intertype Links。用于表示不同數據空間中數據對象之間的關系，多指用戶、查詢條件與Web頁面之間的關系。在鏈接分析中，同時考慮了Intratype Link和Intertype Link的影響。
具體來說，用戶和他們提交的查詢條件以及用戶瀏覽的Web頁面分別代表三個數據空間。當用戶提交查詢請求時、用戶瀏覽Web頁面時、一個查詢參考其他Web頁面時，這三個不同的數據空間便被聯系起來。三種操作（Submit、Browse、Refe￣rence）包含了這三個不同數據空間之間的Intertype Link。因此在進行頁面排序時，應該不僅僅考慮Intratype Link，還要考慮瀏覽Web頁面的用戶以及參考這些Web頁面的查詢請求。
3.2 確定用戶的特性和目標——CubeSVD
為了提高用戶查詢結果的準確性，一些算法通過用戶的查詢日志（Query Log）來確定用戶的偏好，進而找出用戶的目的。這是非常有效的方法。例如前面提到的TSPR就是希望確定用戶的主題，從而能更準確地返回查詢結果。在文獻［14］中，提出了一種新的用于確定用戶目標的方法——Userclick Behavior。它是利用用戶點擊數據（Clickthrough）來提高搜索引擎的效果。一個搜索引擎每天都要接受大量的查詢請求，將用戶提交的查詢請求以及用戶所點擊的查詢結果頁面記錄下來，然后通過對這些Clickthrough數據的分析，獲得用戶的興趣以及用戶定位信息資源的模式，從而更準確地執行用戶的查詢請求。
4 結束語
Internet上信息量的爆炸式增長使得人們越來越依賴于搜索引擎獲取所需的信息。雖然目前的商用搜索引擎獲得了巨大的成功，但其中還有許多方面可以進一步完善。本文通過對現有搜索引擎頁面排序算法的分析，希望為今后的工作提供一些基礎性支持。
ATT香農實驗室的Brian Amento指出，用權威性來評價網頁的質量與人類專家評價的結果是一致的，并且各種鏈接分析算法的結果在大多數情況下差別很小［15］。通過前面對現有頁面排序算法的分析也可以看出，不同算法在不同領域和場合有各自的優勢。對Internet來說，頁面有著眾多不同的主題（領域），用戶有著各種各樣的背景和偏好，因此難以用一種頁面排序技術來滿足所有的需求。今后對于搜索引擎的研究可以著眼于建立一些專業搜索引擎，即針對不同應用場合和應用領域建立不同用途的專業搜索引擎；然后利用網格技術，建立基于網格的搜索引擎體系結構，將各種不同的專業搜索引擎聯合起來，結合對用戶背景和偏好的自動分析，自動引用不同的專業搜索引擎，從而為用戶提供更為精確的搜索結果。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
