搜索引擎算法淺談

搜索引擎算法淺談

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