搜索引擎的算法

1、搜索引擎算法研究 搜索引擎算法研究１．引言 １．引言萬維網(wǎng) WWW（World Wide Web）是一個巨大的，分布全球的信息服務(wù)中心，正在以飛快的速度擴展。1998年 WWW 上擁有約3.5億個文檔[14]，每天增加約1百萬的文檔[6]，不到9個月的時間文檔總數(shù)就會翻一番[14]。WEB 上的文檔和傳統(tǒng)的文檔比較，有很多新的特點，它們是分布的，異構(gòu)的，無結(jié)構(gòu)或者半結(jié)構(gòu)的，這就對傳統(tǒng)信息檢索技術(shù)提出了新的挑戰(zhàn)。傳統(tǒng)的 WEB 搜索引擎大

2、多數(shù)是基于關(guān)鍵字匹配的，返回的結(jié)果是包含查詢項的文檔，也有基于目錄分類的搜索引擎。這些搜索引擎的結(jié)果并不令人滿意。有些站點有意提高關(guān)鍵字出現(xiàn)的頻率來提高自身在搜索引擎中的重要性，破壞搜索引擎結(jié)果的客觀性和準確性。另外，有些重要的網(wǎng)頁并不包含查詢項。搜索引擎的分類目錄也不可能把所有的分類考慮全面，并且目錄大多靠人工維護，主觀性強，費用高，更新速度慢[2]。最近幾年，許多研究者發(fā)現(xiàn)，WWW 上超鏈結(jié)構(gòu)是個非常豐富和重要的資源，如果能夠充分利

3、用的話，可以極大的提高檢索結(jié)果的質(zhì)量?；谶@種超鏈分析的思想，Sergey Brin 和 Lawrence Page 在1998年提出了 PageRank 算法[1]，同年 J. Kleinberg 提出了 HITS 算法[5]，其它一些學者也相繼提出了另外的鏈接分析算法，如 SALSA，PHITS，Bayesian 等算法。這些算法有的已經(jīng)在實際的系統(tǒng)中實現(xiàn)和使用，并且取得了良好的效果。文章的第2部分按照時間順序詳細剖析了各種鏈接分析

4、算法，對不同的算法進行了比較。第3部分對這些算法做了評價和總結(jié)，指出了存在的問題和改進方向。２． ２．WEB 超鏈分析算法 超鏈分析算法２.１ Google 和 PageRank 算法 算法搜索引擎 Google 最初是斯坦福大學的博士研究生 Sergey Brin 和 Lawrence Page 實現(xiàn)的一個原型系統(tǒng)[2]，現(xiàn)在已經(jīng)發(fā)展成為 WWW 上最好的搜索引擎之一。Google 的體系結(jié)構(gòu)類似于傳統(tǒng)的搜索引擎，它與傳統(tǒng)的搜索引擎最

5、大的不同處在于對網(wǎng)頁進行了基于權(quán)威值的排序處理，使最重要的網(wǎng)頁出現(xiàn)在結(jié)果的最前面。Google 通過 PageRank 元算法計算出網(wǎng)頁的 PageRank 值，從而決定網(wǎng)頁在結(jié)果集中的出現(xiàn)位置，PageRank 值越高的網(wǎng)頁，在結(jié)果中出現(xiàn)的位置越前。２.１.１ PageRank 算法 算法PageRank 算法基于下面2個前提：前提1：一個網(wǎng)頁被多次引用，則它可能是很重要的；一個網(wǎng)頁雖然沒有被多次引用，但是被重要的網(wǎng)頁引用，則它也可能

6、是很重要的；一個網(wǎng)頁的重要性被平均的傳遞到它所引用的網(wǎng)頁。這種重要的網(wǎng)頁稱為權(quán)威（Authoritive）網(wǎng)頁。前提2：假定用戶一開始隨機的訪問網(wǎng)頁集合中的一個網(wǎng)頁，以后跟隨網(wǎng)頁的向外鏈接向前瀏覽網(wǎng)頁，不回退瀏覽，瀏覽下一個網(wǎng)頁的概率就是被瀏覽網(wǎng)頁的 PageRank 值。簡單 PageRank 算法描述如下：u 是一個網(wǎng)頁， 是 u 指向的網(wǎng)頁集合， 是指向 u 的網(wǎng)頁集合， 是 u 指向外的鏈接數(shù)，顯然 =| | ，c 是一個用于規(guī)

7、范化2.基于商業(yè)或競爭因素考慮，很少有 WEB 網(wǎng)頁指向其競爭領(lǐng)域的權(quán)威網(wǎng)頁。3.權(quán)威網(wǎng)頁很少具有顯式的描述，比如 Google 主頁不會明確給出 WEB 搜索引擎之類的描述信息。可見平均的分布權(quán)值不符合鏈接的實際情況[17]。J. Kleinberg[5]提出的 HITS 算法中引入了另外一種網(wǎng)頁，稱為 Hub 網(wǎng)頁，Hub 網(wǎng)頁是提供指向權(quán)威網(wǎng)頁鏈接集合的 WEB 網(wǎng)頁，它本身可能并不重要，或者說沒有幾個網(wǎng)頁指向它，但是 Hub 網(wǎng)

8、頁確提供了指向就某個主題而言最為重要的站點的鏈接集合，比一個課程主頁上的推薦參考文獻列表。一般來說，好的 Hub 網(wǎng)頁指向許多好的權(quán)威網(wǎng)頁；好的權(quán)威網(wǎng)頁是有許多好的 Hub 網(wǎng)頁指向的 WEB網(wǎng)頁。這種 Hub 與 Authoritive 網(wǎng)頁之間的相互加強關(guān)系，可用于權(quán)威網(wǎng)頁的發(fā)現(xiàn)和 WEB結(jié)構(gòu)和資源的自動發(fā)現(xiàn)，這就是 Hub/Authority 方法的基本思想。２.２.１ HITS 算法 算法HITS（Hyperlink－Induc

9、ed Topic Search）算法是利用 Hub/Authority 方法的搜索方法，算法如下：將查詢 q 提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎．搜索引擎返回很多網(wǎng)頁，從中取前 n 個網(wǎng)頁作為根集(root set)，用 S 表示。S 滿足如下3個條件：1．S 中網(wǎng)頁數(shù)量相對較小2．S 中網(wǎng)頁大多數(shù)是與查詢 q 相關(guān)的網(wǎng)頁3．S 中網(wǎng)頁包含較多的權(quán)威網(wǎng)頁。通過向 S 中加入被 S 引用的網(wǎng)頁和引用 S 的網(wǎng)頁將 S 擴展成一個更大的集

10、合 T．以 T 中的 Hub 網(wǎng)頁為頂點集 Vl，以權(quán)威網(wǎng)頁為頂點集 V2，Vl 中的網(wǎng)頁到 V2中的網(wǎng)頁的超鏈接為邊集 E，形成一個二分有向圖 SG＝(V1，V2，E)。對 V1中的任一個頂點 v，用h(v)表示網(wǎng)頁 v 的 Hub 值，對 V2中的頂點 u，用 a(u)表示網(wǎng)頁的 Authority 值。開始時 h(v)＝a(u)＝1，對 u 執(zhí)行 I 操作修改它的 a(u)，對 v 執(zhí)行 O 操作修改它的 h(v)，然后規(guī)范化 a

11、（u） ，h（v） ，如此不斷的重復(fù)計算下面的操作 I，O，直到 a（u） ，h（v）收斂。 （證明此算法收斂可見 ）I 操作： （1） O 操作：（2）每次迭代后需要對 a(u),h(v)進行規(guī)范化處理：式(1)反映了若一個網(wǎng)頁由很多好的 Hub 指向，則其權(quán)威值會相應(yīng)增加(即權(quán)威值增加為所有指向它的網(wǎng)頁的現(xiàn)有 Hub 值之和)。式(2)反映了若一個網(wǎng)頁指向許多好的權(quán)威頁，則Hub 值也會相應(yīng)增加(即 Hub 值增加為該網(wǎng)頁鏈接的所有

12、網(wǎng)頁的權(quán)威值之和)。和 PageRank 算法一樣，可以用矩陣形式來描述算法，這里省略不寫。HITS 算法輸出一組具有較大 Hub 值的網(wǎng)頁和具有較大權(quán)威值的網(wǎng)頁。２.２.２ HITS 的問題 的問題HITS 算法有以下幾個問題：1．實際應(yīng)用中，由 S 生成 T 的時間開銷是很昂貴的，需要下載和分析 S 中每個網(wǎng)頁包含的所有鏈接，并且排除重復(fù)的鏈接。一般 T 比 S 大很多，由 T 生成有向圖也很耗時。需要分別計算網(wǎng)頁的 A/H 值，計