搜索引擎的算法

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

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

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

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

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

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

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

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

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

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

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

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