比較pagerank算法和hits算法的優(yōu)缺點

《比較pagerank算法和hits算法的優(yōu)缺點》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、題目：請比較PageRank算法和HITS算法的優(yōu)缺點，除此之外，請再介紹2種用于搜索引擎檢索結(jié)果的排序算法，并舉例說明。答：1998年，SergeyBrin和LawrencePage[1]提出了PageRank算法。該算法基于“從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁”的回歸關(guān)系，來判定網(wǎng)頁的重要性。該算法認為從網(wǎng)頁A導向網(wǎng)頁B的鏈接可以看作是頁面A對頁面B的支持投票，根據(jù)這個投票數(shù)來判斷頁面的重要性。當然，不僅僅只看投票數(shù)，還要對投票的頁面進行重要性分析，越是重要的頁面所投票的評價也就越高。根據(jù)這樣的分析，得到了高評價的重要頁面會被給予較高的PageRank值，在檢索結(jié)果內(nèi)的名次

2、也會提高。PageRank是基于對“使用復雜的算法而得到的鏈接構(gòu)造”的分析，從而得出的各網(wǎng)頁本身的特性。HITS算法是由康奈爾大學(CornellUniversity)的JonKleinberg博士于1998年首先提出。Kleinberg認為既然搜索是開始于用戶的檢索提問，那么每個頁面的重要性也就依賴于用戶的檢索提問。他將用戶檢索提問分為如下三種：特指主題檢索提問（specificqueries，也稱窄主題檢索提問）、泛指主題檢索提問（Broad-topicqueries，也稱寬主題檢索提問）和相似網(wǎng)頁檢索提問（Similar-pagequeries）。HITS算法專注于改善泛指主題檢索的結(jié)

3、果。Kleinberg將網(wǎng)頁（或網(wǎng)站）分為兩類，即hubs和authorities，而且每個頁面也有兩個級別，即hubs（中心級別）和authorities（權(quán)威級別）。Authorities是具有較高價值的網(wǎng)頁，依賴于指向它的頁面；hubs為指向較多authorities的網(wǎng)頁，依賴于它指向的頁面。HITS算法的目標就是通過迭代計算得到針對某個檢索提問的排名最高的authority的網(wǎng)頁。通常HITS算法是作用在一定范圍的，例如一個以程序開發(fā)為主題的網(wǎng)頁，指向另一個以程序開發(fā)為主題的網(wǎng)頁，則另一個網(wǎng)頁的重要性就可能比較高，但是指向另一個購物類的網(wǎng)頁則不一定。在限定范圍之后根據(jù)網(wǎng)頁的出度和入

4、度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量authority和hub值進行更新直至收斂。從上面的分析可見，PageRank算法和HITS算法都是基于鏈接分析的搜索引擎排序算法，并且在算法中兩者都利用了特征向量作為理論基礎和收斂性依據(jù)。雖然兩種算法均為鏈接分析算法，但兩者之間還是有明顯的區(qū)別的。HITS算法計算的authority值只是相對于某個檢索主題的權(quán)重，因此HITS算法也常被稱為Query-dependent算法；而PageRank算法是獨立于檢索主題，因此也常被稱為Query-independent算法。PageRank算法的優(yōu)點在于它對互聯(lián)網(wǎng)上的網(wǎng)頁給出了一個

5、全局的重要性排序，并且算法的計算過程是可以離線完成的，這樣有利于迅速響應用戶的請求。不過，其缺點在于主題無關(guān)性，沒有區(qū)分頁面內(nèi)的導航鏈接、廣告鏈接和功能鏈接等，容易對廣告頁面有過高評價；另外，PageRank算法的另一弊端是，舊的頁面等級會比新頁面高，因為新頁面，即使是非常好的頁面，也不會有很多鏈接，除非他是一個站點的子站點。這就是PageRank需要多項算法結(jié)合的原因。HITS算法的優(yōu)點在于它能更好地描述互聯(lián)網(wǎng)的組織特點，由于它只是對互聯(lián)網(wǎng)中的很小的一個子集進行分析，所以它需要的迭代次數(shù)更少，收斂速度更快，減少了時間復雜度。但HITS算法也存在如下缺點：中心網(wǎng)頁之間的相互引用以增加其網(wǎng)頁評

6、價，當一個網(wǎng)站上的多篇網(wǎng)頁指向一個相同的鏈接，或者一個網(wǎng)頁指向另一個網(wǎng)站上的多個文件時會引起評分的不正常增加，這會導致易受“垃圾鏈接”的影響；網(wǎng)頁中存在自動生成的鏈接；主題漂移，在鄰接圖中經(jīng)常包括一些和搜索主題無關(guān)的鏈接，如果這些鏈接自身也是中心網(wǎng)頁或權(quán)威網(wǎng)頁就會引起主題漂移：對于每個不同的查詢算法都需要重新運行一次來獲取結(jié)果。這使得它不可能用于實時系統(tǒng)，因為對于上千萬次的并發(fā)查詢這樣的開銷實在太大。PageRank算法和HITS算法都是客觀的描述了網(wǎng)頁之間的本質(zhì)特征，但是它們都很少考慮到用戶瀏覽習慣時的主題相關(guān)性。Hilltop算法：HillTop，是一項搜索引擎結(jié)果排序的專利，是Goog

7、le的一個工程師Bharat在2001年獲得的專利。HillTop算法的指導思想和PageRank是一致的，即都通過反向鏈接的數(shù)量和質(zhì)量來確定搜索結(jié)果的排序權(quán)重。但HillTop認為只計算來自具有相同主題的相關(guān)文檔鏈接對于搜索者的價值會更大，即主題相關(guān)網(wǎng)頁之間的鏈接對于權(quán)重計算的貢獻比主題不相關(guān)的鏈接價值要更高。在1999-2000年，當這個算法被Bharat與其他Google開發(fā)人員開發(fā)出來的時候，他們稱這