搜索引擎網(wǎng)頁(yè)排序算法

2.1基于詞頻統(tǒng)一詞位置加權(quán)的搜索引擎利用關(guān)鍵詞在文檔中出現(xiàn)的頻率和位置排序是搜索引擎最早期排序的主要思想，其技術(shù)發(fā)展也最為成熟，是第一階段搜索引擎的主要排序技術(shù)，應(yīng)用非常廣泛，至今仍是許多搜索引擎的核心排序技術(shù)。其基本原理是：關(guān)鍵詞在文檔中詞頻越高，出現(xiàn)的位置越重要，則被認(rèn)為和檢索詞的相關(guān)性越好。1）詞頻統(tǒng)計(jì)文檔的詞頻是指查詢關(guān)鍵詞在文檔中出現(xiàn)的頻率。查詢關(guān)鍵詞詞頻在文檔中出現(xiàn)的頻率越高，其相關(guān)度越大。但當(dāng)關(guān)鍵詞為常用詞時(shí)，使其對(duì)相關(guān)性判斷的意義非常小。TF/IDF很好的解決了這個(gè)問(wèn)題。TF/IDF算法被認(rèn)為是信息檢索中最重要的發(fā)明。TF（TermFrequency）:單文本詞匯頻率，用關(guān)鍵詞的次數(shù)除以網(wǎng)頁(yè)的總字?jǐn)?shù)，其商稱為“關(guān)鍵詞的頻率”。IDF（InverseDocumentFrequency）:逆文本頻率指數(shù)，其原理是，一個(gè)關(guān)鍵詞在N個(gè)網(wǎng)頁(yè)中出現(xiàn)過(guò)，那么N越大，此關(guān)鍵詞的權(quán)重越小，反之亦然。當(dāng)關(guān)鍵詞為常用詞時(shí)，其權(quán)重極小，從而解決詞頻統(tǒng)計(jì)的缺陷。2）詞位置加權(quán)在搜索引擎中，主要針對(duì)網(wǎng)頁(yè)進(jìn)行詞位置加權(quán)。所以，頁(yè)面版式信息的分析至關(guān)重要。通過(guò)對(duì)檢索關(guān)鍵詞在Web頁(yè)面中不同位置和版式，給予不同的權(quán)值，從而根據(jù)權(quán)值來(lái)確定所搜索結(jié)果與檢索關(guān)鍵詞相關(guān)程度?？梢钥紤]的版式信息有：是否是標(biāo)題，是否為關(guān)鍵詞，是否是正文，字體大小，是否加粗等等。同時(shí)，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁(yè)面的內(nèi)容。2.2基于鏈接分析排序的第二代搜索引擎鏈接分析排序的思想起源于文獻(xiàn)引文索引機(jī)制，即論文被引用的次數(shù)越多或被越權(quán)威的論文引用，其論文就越有價(jià)值。鏈接分析排序的思路與其相似，網(wǎng)頁(yè)被別的網(wǎng)頁(yè)引用的次數(shù)越多或被越權(quán)威的網(wǎng)頁(yè)引用，其價(jià)值就越大。被別的網(wǎng)頁(yè)引用的次數(shù)越多，說(shuō)明該網(wǎng)頁(yè)越受歡迎，被越權(quán)威的網(wǎng)頁(yè)引用，說(shuō)明該網(wǎng)頁(yè)質(zhì)量越高。鏈接分析排序算法大體可以分為以下幾類(lèi)：基于隨機(jī)漫游模型的，比如PageRank和Repution算法；基于概率模型的，如SALSA、PHITS；基于Hub和Authority相互加強(qiáng)模型的，如HITS及其變種；基于貝葉斯模型的，如貝葉斯算法及其簡(jiǎn)化版本。所有的算法在實(shí)際應(yīng)用中都結(jié)合傳統(tǒng)的內(nèi)容分析技術(shù)進(jìn)行了優(yōu)化。本文主要介紹以下幾種經(jīng)典排序算法：1）PageRank算法PageRank算法由斯坦福大學(xué)博士研究生SergeyBrin和LwraencePage等提出的。PageRank算法是Google搜索引擎的核心排序算法，是Google成為全球最成功的搜索引擎的重要因素之一，同時(shí)開(kāi)啟了鏈接分析研究的熱潮。PageRank算法的基本思想是：頁(yè)面的重要程度用PageRank值來(lái)衡量，PageRank值主要體現(xiàn)在兩個(gè)方面：引用該頁(yè)面的頁(yè)面?zhèn)€數(shù)和引用該頁(yè)面的頁(yè)面重要程度。一個(gè)頁(yè)面P（A）被另一個(gè)頁(yè)面P（B）引用，可看成P（B）推薦P（A），P（B）將其重要程度（PageRank值）平均的分配P（B）所引用的所有頁(yè)面，所以越多頁(yè)面引用P（A），則越多的頁(yè)面分配PageRank值給P（A），PageRank值也就越高，P（A）越重要。另夕卜，P（B）越重要，它所引用的頁(yè)面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。其計(jì)算公式為:PR（A）:頁(yè)面A的PageRank值；d：阻尼系數(shù)，由于某些頁(yè)面沒(méi)有入鏈接或者出鏈接，無(wú)法計(jì)算PageRank值，為避免這個(gè)問(wèn)題（即LinkSink問(wèn)題），而提出的。阻尼系數(shù)常指定為0.85。R（Pi）:頁(yè)面Pi的PageRank值；C（Pi）:頁(yè)面鏈出的鏈接數(shù)量；PageRank值的計(jì)算初始值相同，為了不忽視被重要網(wǎng)頁(yè)鏈接的網(wǎng)頁(yè)也是重要的這一重要因素，需要反復(fù)迭代運(yùn)算，據(jù)張映海撰文的計(jì)算結(jié)果，需要進(jìn)行10次以上的迭代后鏈接評(píng)價(jià)值趨于穩(wěn)定，如此經(jīng)過(guò)多次迭代，系統(tǒng)的PR值達(dá)到收斂。PageRank是一個(gè)與查詢無(wú)關(guān)的靜態(tài)算法，因此所有網(wǎng)頁(yè)的PageRank值均可以通過(guò)離線計(jì)算獲得。這樣，減少了用戶檢索時(shí)需要的排序時(shí)間，極大地降低了查詢響應(yīng)時(shí)間。但是PageRank存在兩個(gè)缺陷：首先PageRank算法嚴(yán)重歧視新加入的網(wǎng)頁(yè)，因?yàn)樾碌木W(wǎng)頁(yè)的出鏈接和入鏈接通常都很少，PageRank值非常低。另外PageRank算法僅僅依靠外部鏈接數(shù)量和重要度來(lái)進(jìn)行排名，而忽略了頁(yè)面的主題相關(guān)性，以至于一些主題不相關(guān)的網(wǎng)頁(yè)（如廣告頁(yè)面）獲得較大的PageRank值，從而影響了搜索結(jié)果的準(zhǔn)確性。為此，各種主題相關(guān)算法紛紛涌現(xiàn)，其中以以下幾種算法最為典型。2）Topic-SensitivePageRank算法由于最初PageRank算法中是沒(méi)有考慮主題相關(guān)因素的，斯坦福大學(xué)計(jì)算機(jī)科學(xué)系TaherHaveli-wala提出了一種主題敏感（Topic-Sensitive）的PageRank算法解決了“主題漂流”問(wèn)題。該算法考慮到有些頁(yè)面在某些領(lǐng)域被認(rèn)為是重要的，但并不表示它在其它領(lǐng)域也是重要的。網(wǎng)頁(yè)A鏈接網(wǎng)頁(yè)B，可以看作網(wǎng)頁(yè)A對(duì)網(wǎng)頁(yè)B的評(píng)分，如果網(wǎng)頁(yè)A與網(wǎng)頁(yè)B屬于相同主題，則可認(rèn)為A對(duì)B的評(píng)分更可靠。因?yàn)锳與B可形象的看作是同行，同行對(duì)同行的了解往往比不是同行的要多，所以同行的評(píng)分往往比不是同行的評(píng)分可靠。遺憾的是TSPR并沒(méi)有利用主題的相關(guān)性來(lái)提高鏈接得分的準(zhǔn)確性。3）HillTop算法HillTop是Google的一個(gè)工程師Bharat在2001年獲得的專利。HillTop是一種查詢相關(guān)性鏈接分析算法，克服了的PageRank的查詢無(wú)關(guān)性的缺點(diǎn)°HillTop算法認(rèn)為具有相同主題的相關(guān)文檔鏈接對(duì)于搜索者會(huì)有更大的價(jià)值。在Hilltop中僅考慮那些用于引導(dǎo)人們?yōu)g覽資源的專家頁(yè)面（ExportSources）。Hilltop在收到一個(gè)查詢請(qǐng)求時(shí)，首先根據(jù)查詢的主題計(jì)算出一列相關(guān)性最強(qiáng)的專家頁(yè)面，然后根據(jù)指向目標(biāo)頁(yè)面的非從屬專家頁(yè)面的數(shù)量和相關(guān)性來(lái)對(duì)目標(biāo)頁(yè)面進(jìn)行排序。HillTop算法確定網(wǎng)頁(yè)與搜索關(guān)鍵詞的匹配程度的基本排序過(guò)程取代了過(guò)分依靠PageRank的值去尋找那些權(quán)威頁(yè)面的方法，避免了許多想通過(guò)增加許多無(wú)效鏈接來(lái)提高網(wǎng)頁(yè)P(yáng)ageRank值的作弊方法。HillTop算法通過(guò)不同等級(jí)的評(píng)分確保了評(píng)價(jià)結(jié)果對(duì)關(guān)鍵詞的相關(guān)性，通過(guò)不同位置的評(píng)分確保了主題（行業(yè)）的相關(guān)性，通過(guò)可區(qū)分短語(yǔ)數(shù)防止了關(guān)鍵詞的堆砌。但是，專家頁(yè)面的搜索和確定對(duì)算法起關(guān)鍵作用，專家頁(yè)面的質(zhì)量對(duì)算法的準(zhǔn)確性起著決定性作用，也就忽略了大多數(shù)非專家頁(yè)面的影響。專家頁(yè)面在互聯(lián)網(wǎng)中占的比例非常低（1.79%），無(wú)法代表互聯(lián)網(wǎng)全部網(wǎng)頁(yè)，所以HillTop存在一定的局限性。同時(shí)，不同于PageRank算法，HillTop算法的運(yùn)算是在線運(yùn)行的，對(duì)系統(tǒng)的響應(yīng)時(shí)間產(chǎn)生極大的壓力。4）HITSHITS（HyperlinkInducedTopicSearch）算法是Kleinberg在1998年提出的，是基于超鏈接分析排序算法中另一個(gè)最著名的算法之一。該算法按照超鏈接的方向，將網(wǎng)頁(yè)分成兩種類(lèi)型的頁(yè)面：Authority頁(yè)面和Hub頁(yè)面。Authority頁(yè)面又稱權(quán)威頁(yè)面，是指與某個(gè)查詢關(guān)鍵詞和組合最相近的頁(yè)面，Hub頁(yè)面又稱目錄頁(yè)，該頁(yè)面的內(nèi)容主要是大量指向Authority頁(yè)面的鏈接，它的主要功能就是把這些Authority頁(yè)面聯(lián)合在一起。對(duì)于Authority頁(yè)面P，當(dāng)指向P的Hub頁(yè)面越多，質(zhì)量越高，P的Authority值就越大；而對(duì)于Hub頁(yè)面H，當(dāng)H指向的Authority的頁(yè)面越多，Authority頁(yè)面質(zhì)量越高，H的Hub值就越大。對(duì)整個(gè)Web集合而言，Authority和Hub是相互依賴、相互促進(jìn)，相互加強(qiáng)的關(guān)系。Authority和Hub之間相互優(yōu)化的關(guān)系，即為HITS算法的基礎(chǔ)。HITS基本思想是：算法根據(jù)一個(gè)網(wǎng)頁(yè)的入度（指向此網(wǎng)頁(yè)的超鏈接）和出度（從此網(wǎng)頁(yè)指向別的網(wǎng)頁(yè)）來(lái)衡量網(wǎng)頁(yè)的重要性。在限定范圍之后根據(jù)網(wǎng)頁(yè)的出度和入度建立一個(gè)矩陣，通過(guò)矩陣的迭代運(yùn)算和定義收斂的閾值不斷對(duì)兩個(gè)向量Authority和Hub值進(jìn)行更新直至收斂。實(shí)驗(yàn)數(shù)據(jù)表明，HITS的排名準(zhǔn)確性要比PageRank高，HITS算法的設(shè)計(jì)符合網(wǎng)絡(luò)用戶評(píng)價(jià)網(wǎng)絡(luò)資源質(zhì)量的普遍標(biāo)準(zhǔn)，因此能夠?yàn)橛脩舾玫睦镁W(wǎng)絡(luò)信息檢索工具訪問(wèn)互聯(lián)網(wǎng)資源帶來(lái)便利。但卻存在以下缺陷：首先，HITS算法只計(jì)算主特征向量，處理不好主題漂移問(wèn)題；其次，進(jìn)行窄主題查詢時(shí)，可能產(chǎn)生主題泛化問(wèn)題；第三，HITS算法可以說(shuō)一種實(shí)驗(yàn)性質(zhì)的嘗試。它必須在網(wǎng)絡(luò)信息檢索系統(tǒng)進(jìn)行面向內(nèi)容的檢索操作之后，基于內(nèi)容檢索的結(jié)果頁(yè)面及其直接相連的頁(yè)面之間的鏈接關(guān)系進(jìn)行計(jì)算。盡管有人嘗試通過(guò)算法改進(jìn)和專門(mén)設(shè)立鏈接結(jié)構(gòu)計(jì)算服務(wù)器（ConnectivityServer）等操作，可以實(shí)現(xiàn)一定程度的在線實(shí)時(shí)計(jì)算，但其計(jì)算代價(jià)仍然是不可接受的。2.3基于智能化排序的第三代搜索引擎排序算法在搜索引擎中具有特別重要的地位，目前許多搜索引擎都在進(jìn)一步研究新的排序方法，來(lái)提升用戶的滿意度。但目前第二代搜索引擎有著兩個(gè)不足之處，在此背景下，基于智能化排序的第三代搜索引擎也就應(yīng)運(yùn)而生。1）相關(guān)性問(wèn)題相關(guān)性是指檢索詞和頁(yè)面的相關(guān)程度。由于語(yǔ)言復(fù)雜，僅僅通過(guò)鏈接分析及網(wǎng)頁(yè)的表面特征來(lái)判斷檢索詞與頁(yè)面的相關(guān)性是片面的。例如：檢索“稻瘟病”，有網(wǎng)頁(yè)是介紹水稻病蟲(chóng)害信息的，但文中沒(méi)有“稻瘟病”這個(gè)詞，搜索引擎根本無(wú)法檢索到。正是以上原因，造成大量的搜索引擎作弊現(xiàn)象無(wú)法解決。解決相關(guān)性的的方法應(yīng)該是增加語(yǔ)意理解，分析檢索關(guān)鍵詞與網(wǎng)頁(yè)的相關(guān)程度，相關(guān)性分析越精準(zhǔn)，用戶的搜索效果就會(huì)越好。同時(shí)，相關(guān)性低的網(wǎng)頁(yè)可以剔除，有效地防止搜索引擎作弊現(xiàn)象。檢索關(guān)鍵詞和網(wǎng)頁(yè)的相關(guān)性是在線運(yùn)行的，會(huì)給系統(tǒng)相應(yīng)時(shí)間很大的壓力，可以采用分布式體系結(jié)