資源描述：
《比較pagerank算法和hits算法的優(yōu)缺點(diǎn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、題目：請(qǐng)比較PageRank算法和HITS算法的優(yōu)缺點(diǎn)，除此之外，請(qǐng)?jiān)俳榻B2種用于搜索引擎檢索結(jié)果的排序算法，并舉例說明。答：1998年，SergeyBrin和LawrencePage[1]提出了PageRank算法。該算法基于“從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁”的回歸關(guān)系，來判定網(wǎng)頁的重要性。該算法認(rèn)為從網(wǎng)頁A導(dǎo)向網(wǎng)頁B的鏈接可以看作是頁面A對(duì)頁面B的支持投票，根據(jù)這個(gè)投票數(shù)來判斷頁面的重要性。當(dāng)然，不僅僅只看投票數(shù)，還要對(duì)投票的頁面進(jìn)行重要性分析，越是重要的頁面所投票的評(píng)價(jià)也就越高。根據(jù)這樣的分析，得到了高評(píng)價(jià)的重要頁面會(huì)被給予較高的PageRank值，在檢索結(jié)果內(nèi)的名次
2、也會(huì)提高。PageRank是基于對(duì)“使用復(fù)雜的算法而得到的鏈接構(gòu)造”的分析，從而得出的各網(wǎng)頁本身的特性。HITS算法是由康奈爾大學(xué)(CornellUniversity)的JonKleinberg博士于1998年首先提出。Kleinberg認(rèn)為既然搜索是開始于用戶的檢索提問，那么每個(gè)頁面的重要性也就依賴于用戶的檢索提問。他將用戶檢索提問分為如下三種：特指主題檢索提問（specificqueries，也稱窄主題檢索提問）、泛指主題檢索提問（Broad-topicqueries，也稱寬主題檢索提問）和相似網(wǎng)頁檢索提問（Similar-pagequeries）。HITS算法專注于改善泛指主題檢索的結(jié)
3、果。Kleinberg將網(wǎng)頁（或網(wǎng)站）分為兩類，即hubs和authorities，而且每個(gè)頁面也有兩個(gè)級(jí)別，即hubs（中心級(jí)別）和authorities（權(quán)威級(jí)別）。Authorities是具有較高價(jià)值的網(wǎng)頁，依賴于指向它的頁面；hubs為指向較多authorities的網(wǎng)頁，依賴于它指向的頁面。HITS算法的目標(biāo)就是通過迭代計(jì)算得到針對(duì)某個(gè)檢索提問的排名最高的authority的網(wǎng)頁。通常HITS算法是作用在一定范圍的，例如一個(gè)以程序開發(fā)為主題的網(wǎng)頁，指向另一個(gè)以程序開發(fā)為主題的網(wǎng)頁，則另一個(gè)網(wǎng)頁的重要性就可能比較高，但是指向另一個(gè)購物類的網(wǎng)頁則不一定。在限定范圍之后根據(jù)網(wǎng)頁的出度和入
4、度建立一個(gè)矩陣，通過矩陣的迭代運(yùn)算和定義收斂的閾值不斷對(duì)兩個(gè)向量authority和hub值進(jìn)行更新直至收斂。從上面的分析可見，PageRank算法和HITS算法都是基于鏈接分析的搜索引擎排序算法，并且在算法中兩者都利用了特征向量作為理論基礎(chǔ)和收斂性依據(jù)。雖然兩種算法均為鏈接分析算法，但兩者之間還是有明顯的區(qū)別的。HITS算法計(jì)算的authority值只是相對(duì)于某個(gè)檢索主題的權(quán)重，因此HITS算法也常被稱為Query-dependent算法；而PageRank算法是獨(dú)立于檢索主題，因此也常被稱為Query-independent算法。PageRank算法的優(yōu)點(diǎn)在于它對(duì)互聯(lián)網(wǎng)上的網(wǎng)頁給出了一個(gè)
5、全局的重要性排序，并且算法的計(jì)算過程是可以離線完成的，這樣有利于迅速響應(yīng)用戶的請(qǐng)求。不過，其缺點(diǎn)在于主題無關(guān)性，沒有區(qū)分頁面內(nèi)的導(dǎo)航鏈接、廣告鏈接和功能鏈接等，容易對(duì)廣告頁面有過高評(píng)價(jià)；另外，PageRank算法的另一弊端是，舊的頁面等級(jí)會(huì)比新頁面高，因?yàn)樾马撁?，即使是非常好的頁面，也不?huì)有很多鏈接，除非他是一個(gè)站點(diǎn)的子站點(diǎn)。這就是PageRank需要多項(xiàng)算法結(jié)合的原因。HITS算法的優(yōu)點(diǎn)在于它能更好地描述互聯(lián)網(wǎng)的組織特點(diǎn)，由于它只是對(duì)互聯(lián)網(wǎng)中的很小的一個(gè)子集進(jìn)行分析，所以它需要的迭代次數(shù)更少，收斂速度更快，減少了時(shí)間復(fù)雜度。但HITS算法也存在如下缺點(diǎn)：中心網(wǎng)頁之間的相互引用以增加其網(wǎng)頁評(píng)
6、價(jià)，當(dāng)一個(gè)網(wǎng)站上的多篇網(wǎng)頁指向一個(gè)相同的鏈接，或者一個(gè)網(wǎng)頁指向另一個(gè)網(wǎng)站上的多個(gè)文件時(shí)會(huì)引起評(píng)分的不正常增加，這會(huì)導(dǎo)致易受“垃圾鏈接”的影響；網(wǎng)頁中存在自動(dòng)生成的鏈接；主題漂移，在鄰接圖中經(jīng)常包括一些和搜索主題無關(guān)的鏈接，如果這些鏈接自身也是中心網(wǎng)頁或權(quán)威網(wǎng)頁就會(huì)引起主題漂移：對(duì)于每個(gè)不同的查詢算法都需要重新運(yùn)行一次來獲取結(jié)果。這使得它不可能用于實(shí)時(shí)系統(tǒng)，因?yàn)閷?duì)于上千萬次的并發(fā)查詢這樣的開銷實(shí)在太大。PageRank算法和HITS算法都是客觀的描述了網(wǎng)頁之間的本質(zhì)特征，但是它們都很少考慮到用戶瀏覽習(xí)慣時(shí)的主題相關(guān)性。Hilltop算法：HillTop，是一項(xiàng)搜索引擎結(jié)果排序的專利，是Goog
7、le的一個(gè)工程師Bharat在2001年獲得的專利。HillTop算法的指導(dǎo)思想和PageRank是一致的，即都通過反向鏈接的數(shù)量和質(zhì)量來確定搜索結(jié)果的排序權(quán)重。但HillTop認(rèn)為只計(jì)算來自具有相同主題的相關(guān)文檔鏈接對(duì)于搜索者的價(jià)值會(huì)更大，即主題相關(guān)網(wǎng)頁之間的鏈接對(duì)于權(quán)重計(jì)算的貢獻(xiàn)比主題不相關(guān)的鏈接價(jià)值要更高。在1999-2000年，當(dāng)這個(gè)算法被Bharat與其他Google開發(fā)人員開發(fā)出來的時(shí)候，他們稱這
