搜索引擎算法淺談

關(guān)鍵詞：搜索引擎；頁(yè)面排序；鏈接分析中圖分類(lèi)號(hào)：TP393.09文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1001-3695(2007)06-0004-04隨著Internet的飛速發(fā)展，其提供的文檔(網(wǎng)頁(yè))也以驚人的速度在增長(zhǎng)。有關(guān)的調(diào)查統(tǒng)計(jì)表明，Internet上的網(wǎng)頁(yè)每不到一年的時(shí)間就會(huì)增長(zhǎng)一倍。要從這么大量的信息庫(kù)中提取出有用的信息就越來(lái)越依賴(lài)于搜索引擎的功能。而網(wǎng)頁(yè)的排序則是搜索引擎要解決的關(guān)鍵問(wèn)題之一。SergeyBrin等人［1］提出PageRank算法開(kāi)啟了鏈接分析研究的熱潮?；阪溄臃治龅乃惴?，提供了一種衡量網(wǎng)頁(yè)質(zhì)量的客觀方法；獨(dú)立于語(yǔ)言，獨(dú)立于內(nèi)容；無(wú)需人工干預(yù)就能自動(dòng)發(fā)現(xiàn)Web上的重要資源，挖掘出Web上的重要社區(qū)，自動(dòng)實(shí)現(xiàn)文檔分類(lèi)。PageRank在Google中的應(yīng)用獲得了巨大的商業(yè)成功。在最初的Google中，首先使用IR(InformationRetrieve)算法找到所有與查詢(xún)關(guān)鍵字相匹配的網(wǎng)頁(yè)；然后根據(jù)頁(yè)面因素(標(biāo)題、關(guān)鍵字密度等)進(jìn)行排名；最后通過(guò)PageRank得分調(diào)整網(wǎng)站排名結(jié)果。近幾年來(lái)，基于鏈接分析的頁(yè)面排序算法一直是一個(gè)熱點(diǎn)問(wèn)題，學(xué)者提出了許多頁(yè)面排序算法。1PageRank及其相關(guān)算法基于鏈接分析的排序算法中，最為著名的就是PageRank。所謂鏈接分析主要基于如下兩個(gè)重要假設(shè)：①超文本鏈接包含了用戶(hù)對(duì)一個(gè)網(wǎng)站的判斷信息；②對(duì)一個(gè)網(wǎng)站而言，如果其他網(wǎng)站鏈接到該網(wǎng)站的入鏈數(shù)越多，該網(wǎng)站越重要。以上假設(shè)在各種基于鏈接分析的算法中均以某種方式體現(xiàn)出來(lái)。1.1PageRank算法PageRank算法是最早提出的鏈接分析算法之一，并被Google用于計(jì)算網(wǎng)頁(yè)的重要性得分。其基本思想是：如果網(wǎng)頁(yè)T存在一個(gè)指向網(wǎng)頁(yè)A的鏈接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個(gè)重要性得分的值則由T的PageRank值PR(T)和T的出鏈(從T鏈出的鏈接)數(shù)C(T)決定。具體公式為：PR(T)/C(T)。而對(duì)于頁(yè)面A，其PageRank值PR(A)的計(jì)算如下：PR(A)=PR(T1)/C(T1)+…+PR(Tn)/C(Tn)(1)其中，T1，T2，…，Tn為含有指向A鏈接的頁(yè)面。為了避免LinkSink(許多網(wǎng)頁(yè)沒(méi)有入鏈或出鏈)問(wèn)題，對(duì)式(1)引入一個(gè)阻尼系數(shù)d，使其變?yōu)镻R(A)=(1-d)+d[PR(T1)/C(T1)+…+PR(Tn)/C(Tn)](2)如此經(jīng)過(guò)多次迭代，系統(tǒng)的PR值達(dá)到收斂。PR的計(jì)算公式可以從概率的角度解釋為一個(gè)隨機(jī)網(wǎng)絡(luò)沖浪者隨機(jī)選擇一個(gè)網(wǎng)頁(yè)后，不斷地點(diǎn)擊網(wǎng)頁(yè)上的鏈接，但是從不返回；除非最后厭煩了才隨機(jī)選擇另一個(gè)頁(yè)面。隨機(jī)沖浪者訪問(wèn)某個(gè)頁(yè)面的隨機(jī)概率就是該頁(yè)面的PageRank值；阻尼系數(shù)d就是隨機(jī)沖浪者在某個(gè)頁(yè)面會(huì)厭煩然后選擇一個(gè)新頁(yè)面的概率。頁(yè)面的PageRank值越高，則隨機(jī)沖浪者發(fā)現(xiàn)它的概率亦越高。這種思路非常富有創(chuàng)意。一個(gè)網(wǎng)頁(yè)的外部鏈接越多，則對(duì)網(wǎng)絡(luò)沖浪者來(lái)說(shuō)，發(fā)現(xiàn)它的機(jī)會(huì)也就越大。文獻(xiàn)［2］結(jié)合近年來(lái)Web出現(xiàn)的一些新特性對(duì)PageRank提出了一些改進(jìn)措施。文獻(xiàn)［3］中對(duì)PageRank算法中的阻尼系數(shù)d進(jìn)行了深入討論，從理論上分析了d的取值不同對(duì)于PageRank算法效果的影響。文獻(xiàn)［4］提出了一種方法用于對(duì)PageRank中的迭代計(jì)算進(jìn)行加速。PageRank的一個(gè)優(yōu)勢(shì)在于它是一個(gè)與查詢(xún)無(wú)關(guān)的靜態(tài)算法，因此所有網(wǎng)頁(yè)的PageRank值均可以通過(guò)離線(xiàn)計(jì)算獲得。這樣有效地減少了在線(xiàn)查詢(xún)時(shí)的運(yùn)算量，極大地降低了查詢(xún)響應(yīng)時(shí)間。然而Internet上的內(nèi)容涵蓋了眾多主題，在現(xiàn)實(shí)應(yīng)用中，人們的查詢(xún)所希望得到的信息往往是具有某一方面主題特征的，而PageRank僅僅依靠計(jì)算網(wǎng)頁(yè)的外部鏈接數(shù)量來(lái)決定該網(wǎng)頁(yè)的排名，而忽略了頁(yè)面的主題相關(guān)性，從而影響了搜索結(jié)果的相關(guān)性和準(zhǔn)確性。另一方面，PageRank算法對(duì)新網(wǎng)頁(yè)有很?chē)?yán)重的歧視性，因?yàn)橐粋€(gè)新網(wǎng)頁(yè)入鏈數(shù)量通常都很少，自然PR值很低。1.2TopicSensitivePageRank由于Internet上的內(nèi)容千差萬(wàn)別，涵蓋眾多不同的領(lǐng)域和主題。同樣一個(gè)查詢(xún)?nèi)纭捌?chē)”，可能用戶(hù)1是想買(mǎi)一臺(tái)汽車(chē)，他感興趣的是汽車(chē)品牌、價(jià)格；而用戶(hù)2是想?yún)⒓优c汽車(chē)相關(guān)的運(yùn)動(dòng)，他感興趣的是與汽車(chē)相關(guān)的運(yùn)動(dòng)項(xiàng)目和賽事。因此要想給用戶(hù)返回更為準(zhǔn)確的查詢(xún)信息就有必要基于不同的主題來(lái)對(duì)頁(yè)面排序。最初的PageRank算法中是沒(méi)有考慮主題相關(guān)因素的。主題敏感PageRank算法(TopicSensitivePageRank，TSPR)［5］正是在這種背景下提出來(lái)的。TSPR核心思想就是通過(guò)離線(xiàn)計(jì)算，計(jì)算出一個(gè)PageRank向量集合(在PageRank算法中，僅計(jì)算一個(gè)PageRank向量)，該集合中的每一個(gè)向量與某一主題相關(guān)，即計(jì)算某個(gè)頁(yè)面關(guān)于不同主題的得分。例如某個(gè)網(wǎng)頁(yè)在教育這個(gè)主題的得分為a，在體育這個(gè)主題的得分為b，……。具體來(lái)說(shuō)，TSPR也可分為兩個(gè)主要階段：(1)主題相關(guān)的PageRank向量集合的計(jì)算。先將所有頁(yè)面的內(nèi)容劃分為16個(gè)主題，根據(jù)Crawler搜集來(lái)的網(wǎng)頁(yè)，計(jì)算該網(wǎng)頁(yè)在不同主題的得分情況，即不同的PageRank向量。(2)在線(xiàn)查詢(xún)，主題的確定。根據(jù)用戶(hù)的查詢(xún)請(qǐng)求和相關(guān)Context判斷用戶(hù)查詢(xún)相關(guān)的主題(即用戶(hù)的興趣取向)，從而提高返回結(jié)果的準(zhǔn)確性無(wú)疑是一種有效的方法。遺憾的是TSPR并沒(méi)有利用主題的相關(guān)性來(lái)提高鏈接得分的準(zhǔn)確性。事實(shí)上對(duì)于網(wǎng)頁(yè)類(lèi)別的劃分可以更有效地計(jì)算鏈接的價(jià)值和權(quán)威性。例如評(píng)閱論文時(shí)，經(jīng)常需要填寫(xiě)對(duì)相關(guān)領(lǐng)域的熟悉程度。也就是說(shuō)，評(píng)閱者對(duì)論文所屬的領(lǐng)域越熟悉，則評(píng)閱者所給出的評(píng)分越可信，從而在最后的計(jì)算中擁有更高的權(quán)重。對(duì)于網(wǎng)頁(yè)之間的鏈接分析與上述論文評(píng)閱的例子類(lèi)似?？梢园丫W(wǎng)頁(yè)A指向網(wǎng)頁(yè)B的鏈接視為A對(duì)B的評(píng)分；若A與B的內(nèi)容是相近的，則A的評(píng)分更為可信。例如一個(gè)教育相關(guān)的網(wǎng)站A指向另一個(gè)教育相關(guān)的網(wǎng)站B，較一個(gè)娛樂(lè)相關(guān)的網(wǎng)站C指向教育相關(guān)的網(wǎng)站B更為權(quán)威、可信。因此，可以將上述思想應(yīng)用到PageRank的PR值計(jì)算中。這將在今后的研究工作中作進(jìn)一步的考慮。1.3HilltopHilltop［6］算法的指導(dǎo)思想與PageRank是一致的，即通過(guò)鏈接的數(shù)量和質(zhì)量來(lái)確定搜索結(jié)果的排序權(quán)重。與PageRank不同的是，在Hilltop中僅考慮那些專(zhuān)家頁(yè)面(ExportSources)，即專(zhuān)門(mén)用于引導(dǎo)人們?yōu)g覽資源的頁(yè)面。Hilltop在收到一個(gè)查詢(xún)請(qǐng)求時(shí)，首