搜索引擎算法淺談

搜索引擎算法淺談

關(guān)鍵詞：搜索引擎；頁面排序；鏈接分析中圖分類號(hào)：TP393.09文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1001-3695(2007)06-0004-04隨著Internet的飛速發(fā)展，其提供的文檔(網(wǎng)頁)也以驚人的速度在增長。有關(guān)的調(diào)查統(tǒng)計(jì)表明，Internet上的網(wǎng)頁每不到一年的時(shí)間就會(huì)增長一倍。要從這么大量的信息庫中提取出有用的信息就越來越依賴于搜索引擎的功能。而網(wǎng)頁的排序則是搜索引擎要解決的關(guān)鍵問題之一。SergeyBrin等人［1］提出PageRank算法開啟了鏈接分析研究的熱潮?；阪溄臃治龅乃惴?，提供了一種衡量網(wǎng)頁質(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)頁；然后根據(jù)頁面因素(標(biāo)題、關(guān)鍵字密度等)進(jìn)行排名；最后通過PageRank得分調(diào)整網(wǎng)站排名結(jié)果。近幾年來，基于鏈接分析的頁面排序算法一直是一個(gè)熱點(diǎn)問題，學(xué)者提出了許多頁面排序算法。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)頁的重要性得分。其基本思想是：如果網(wǎng)頁T存在一個(gè)指向網(wǎng)頁A的鏈接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個(gè)重要性得分的值則由T的PageRank值PR(T)和T的出鏈(從T鏈出的鏈接)數(shù)C(T)決定。具體公式為：PR(T)/C(T)。而對(duì)于頁面A，其PageRank值PR(A)的計(jì)算如下：PR(A)=PR(T1)/C(T1)+…+PR(Tn)/C(Tn)(1)其中，T1，T2，…，Tn為含有指向A鏈接的頁面。為了避免LinkSink(許多網(wǎng)頁沒有入鏈或出鏈)問題，對(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)頁后，不斷地點(diǎn)擊網(wǎng)頁上的鏈接，但是從不返回；除非最后厭煩了才隨機(jī)選擇另一個(gè)頁面。隨機(jī)沖浪者訪問某個(gè)頁面的隨機(jī)概率就是該頁面的PageRank值；阻尼系數(shù)d就是隨機(jī)沖浪者在某個(gè)頁面會(huì)厭煩然后選擇一個(gè)新頁面的概率。頁面的PageRank值越高，則隨機(jī)沖浪者發(fā)現(xiàn)它的概率亦越高。這種思路非常富有創(chuàng)意。一個(gè)網(wǎng)頁的外部鏈接越多，則對(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)勢在于它是一個(gè)與查詢無關(guān)的靜態(tài)算法，因此所有網(wǎng)頁的PageRank值均可以通過離線計(jì)算獲得。這樣有效地減少了在線查詢時(shí)的運(yùn)算量，極大地降低了查詢響應(yīng)時(shí)間。然而Internet上的內(nèi)容涵蓋了眾多主題，在現(xiàn)實(shí)應(yīng)用中，人們的查詢所希望得到的信息往往是具有某一方面主題特征的，而PageRank僅僅依靠計(jì)算網(wǎng)頁的外部鏈接數(shù)量來決定該網(wǎng)頁的排名，而忽略了頁面的主題相關(guān)性，從而影響了搜索結(jié)果的相關(guān)性和準(zhǔn)確性。另一方面，PageRank算法對(duì)新網(wǎng)頁有很嚴(yán)重的歧視性，因?yàn)橐粋€(gè)新網(wǎng)頁入鏈數(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ì)頁面排序。最初的PageRank算法中是沒有考慮主題相關(guān)因素的。主題敏感PageRank算法(TopicSensitivePageRank，TSPR)［5］正是在這種背景下提出來的。TSPR核心思想就是通過離線計(jì)算，計(jì)算出一個(gè)PageRank向量集合(在PageRank算法中，僅計(jì)算一個(gè)PageRank向量)，該集合中的每一個(gè)向量與某一主題相關(guān)，即計(jì)算某個(gè)頁面關(guān)于不同主題的得分。例如某個(gè)網(wǎng)頁在教育這個(gè)主題的得分為a，在體育這個(gè)主題的得分為b，……。具體來說，TSPR也可分為兩個(gè)主要階段：(1)主題相關(guān)的PageRank向量集合的計(jì)算。先將所有頁面的內(nèi)容劃分為16個(gè)主題，根據(jù)Crawler搜集來的網(wǎng)頁，計(jì)算該網(wǎng)頁在不同主題的得分情況，即不同的PageRank向量。(2)在線查詢，主題的確定。根據(jù)用戶的查詢請(qǐng)求和相關(guān)Context判斷用戶查詢相關(guān)的主題(即用戶的興趣取向)，從而提高返回結(jié)果的準(zhǔn)確性無疑是一種有效的方法。遺憾的是TSPR并沒有利用主題的相關(guān)性來提高鏈接得分的準(zhǔn)確性。事實(shí)上對(duì)于網(wǎng)頁類別的劃分可以更有效地計(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)頁之間的鏈接分析與上述論文評(píng)閱的例子類似?？梢园丫W(wǎng)頁A指向網(wǎng)頁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中僅考慮那些專家頁面(ExportSources)，即專門用于引導(dǎo)人們?yōu)g覽資源的頁面。Hilltop在收到一個(gè)查詢請(qǐng)求時(shí)，首