搜索引擎算法淺談

搜索引擎算法淺談

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