【摘 要】提高Web信息搜索的效率，改善搜索的性能，是信息檢索領(lǐng)域一個重要的研究課題。本文利用爬山算法求得針對特定類別的最小集中網(wǎng)站集，再通過網(wǎng)頁聚類，找到能獲得最完全而準(zhǔn)確信息的網(wǎng)頁序列，從而提高Web搜索的速度和準(zhǔn)確率。

【關(guān)鍵詞】Web信息搜索 集中網(wǎng)站 爬山算法 聚類 相似度

搜索引擎（Search engine）是目前Web信息檢索的主要工具，它所提供的導(dǎo)航服務(wù)已經(jīng)成為互聯(lián)網(wǎng)上非常重要的網(wǎng)絡(luò)服務(wù)，但在查詢速度與查準(zhǔn)率、查全率等方面還具有較大的局限性。研究發(fā)現(xiàn)，網(wǎng)站集合中的一部分網(wǎng)站就已經(jīng)包含了幾乎全部網(wǎng)頁信息，這樣的最小覆蓋網(wǎng)站子集被稱為集中網(wǎng)站[1]，因此找到這樣的集中網(wǎng)站就可以提高搜索引擎的搜索效率。另外，分析Web網(wǎng)頁間的超鏈接結(jié)構(gòu)并充分利用，可以提高檢索的質(zhì)量?；谶@種超鏈分析的思想，在1998年，Serger Brin和Lawrence Page提出了PageRank[2]算法。同年，J.Kleinberg提出了HITS[3]算法，還有其他一些研究者相繼提出了一些改進(jìn)算法，如SALSA、PHITS等，在實(shí)際應(yīng)用中取得了良好的效果。

由于最小集中網(wǎng)站是針對某一特定分類而言，因此下面的工作是假定在已得到某一特定類網(wǎng)站集的基礎(chǔ)上而做的。

求集中網(wǎng)站的問題可以看作是求圖的最小頂點(diǎn)覆蓋問題，經(jīng)證明是NP完全問題，考慮采用一種啟發(fā)式查找算法——爬山算法來求集中網(wǎng)站。

爬山算法是一種基于鄰域搜索技術(shù)的、沿著有可能改進(jìn)解的質(zhì)量的方向進(jìn)行單方向搜索（爬山） 的搜索方法。它通過在解空間中進(jìn)行逐步搜索，擴(kuò)展當(dāng)前結(jié)點(diǎn)并估價它的子結(jié)點(diǎn)，最優(yōu)的子結(jié)點(diǎn)被選擇并進(jìn)一步擴(kuò)展。利用爬山算法求集中網(wǎng)站，首先在所有網(wǎng)站中選擇包含網(wǎng)頁數(shù)量最多的網(wǎng)站，放入集中網(wǎng)站集中，同時將該網(wǎng)站所包含的網(wǎng)頁在其它網(wǎng)站的網(wǎng)頁集中刪除，接下來再在剩下的網(wǎng)站集中重復(fù)上面的操作，直到集中網(wǎng)站集中所包含的網(wǎng)頁幾乎覆蓋了所有的網(wǎng)頁為止。

下面需要對最小集中網(wǎng)站所包含的網(wǎng)頁進(jìn)行檢索前聚類，考慮綜合利用網(wǎng)頁間內(nèi)容和鏈接結(jié)構(gòu)的相似度來進(jìn)行網(wǎng)頁的聚類。

網(wǎng)頁內(nèi)容相似度可以考慮用文本相似度來表示，將文本描述為一個以詞為單位的元組集合，并以2字詞為主，將主要以助詞、感嘆詞等無關(guān)語義信息的單字詞略去，這樣就可以通過網(wǎng)頁中詞和詞頻的比較來表示網(wǎng)頁的內(nèi)容相似度。

以下應(yīng)用HITS算法及相應(yīng)改進(jìn)算法，計(jì)算任兩個網(wǎng)頁間的作用力，進(jìn)而求得受作用力的相似性，也就是鏈接相似度。

網(wǎng)頁p和q若存在p直接（或非直接）指向q，則稱p和q之間存在相互作用力，并且 p對q的作用力為FA（p），q對p的反作用力為FH（q）；網(wǎng)頁p和q若不存在p直接（或非直接）指向q，則稱p和q之間不存在相互作用力，或稱相互作用力為0。

其中，

FA（p）=KHHub（p），Hub（p）為用HITS算法計(jì)算出來的p的Hub值向量；

FH（q）=KAAuthority（q），Authority（q）為用HITS算法計(jì)算出來的q的Authority值向量；

KH、KA為衰減系數(shù)。當(dāng)p直接指向q時， KH =1， KA=1；當(dāng)p非直接指向q時，KA和KH隨兩者之間最短路徑長度的增加而減小，KH、KA<=1；

假設(shè)共有m個網(wǎng)頁，其中每個網(wǎng)頁都會受到另外m-1個網(wǎng)頁對它的分別的作用力，每個作用力又分為FA和FH兩部分。

設(shè)網(wǎng)頁p和q之間所受作用力為FA和FH，依據(jù)歐式距離公式，可得FA和FH的相似度分別為：

SFA （p，q）=1-

SFH （p，q）= 1-

其中，SFA 、SFH。

設(shè)網(wǎng)頁集團(tuán)中任兩個網(wǎng)頁p和q之間的鏈接相似度Slink包括Sd、SFA、SFH三部分，即

Slink=Wd×Sd（p，q）+Wa× SFA （p，q）+Wh× SFH （p，q）

其中，Wd、Wa、Wh為各自的權(quán)值，Wd+Wa+Wh=1。

Sd（p，q）為網(wǎng)頁p和q間的距離特性，隨二者之間距離的減小而增大。

SFA （p，q）為網(wǎng)頁p和q所受作用力FA的相似度。

SFH （p，q）為網(wǎng)頁p和q所受作用力FH的相似度。

Sd 、SFA 、SFH 。

有了網(wǎng)頁間基于內(nèi)容和超鏈接結(jié)構(gòu)的相似度后，就可以得到將二者結(jié)合起來考慮的網(wǎng)頁間的混合相似度：

設(shè)兩個網(wǎng)頁的混合相似度表示為：

S=Wl×Slink+Wt×Sterm 其中，Wl 、Wt為各自的權(quán)值， Wl+Wt=1，S。

常用的聚類算法有層次聚類法、平面劃分法（k-means算法）、簡單貝葉斯聚類法、K-最近鄰參照聚類法、分級聚類法、基于概念的文本聚類等。

通過以上的網(wǎng)頁聚類，已經(jīng)得到了某類最小集中網(wǎng)站所包含網(wǎng)頁的類別?？蓪⒕W(wǎng)頁的Authority值作為度量其重要性的一個指標(biāo)。同時，在聚類過程中，還用到了網(wǎng)頁p對類Ci的隸屬度M（Ci，p），表示網(wǎng)頁p對該類信息的相關(guān)性，因此也能體現(xiàn)出網(wǎng)頁在其所屬類別中的重要程度。由此定義如下：

設(shè)類Ci中的任一網(wǎng)頁p對類Ci的隸屬度為M（Ci，p），p的Authority值為Authority（p），則在類Ci中網(wǎng)頁p的重要度為：

Importance（p）=M（Ci，p） Authority（p）

在每一類中，選取Importance值最大的一、二條網(wǎng)頁，就可以使查詢結(jié)果中只出現(xiàn)具有代表性的內(nèi)容，從而使查詢效率獲得提高。

本文所提出的對所求得的最小集中網(wǎng)站中所包含的網(wǎng)頁進(jìn)行聚類，并選取每類中的重要性網(wǎng)頁來進(jìn)行web搜索優(yōu)化的方法，有以下幾點(diǎn)優(yōu)勢：（1）通過搜索最小集中網(wǎng)站，可以減小搜索面，提高搜索的有效性；（2）利用內(nèi)容和超鏈接結(jié)構(gòu)的相似性來進(jìn)行網(wǎng)頁聚類，可以得到更好的聚類效果。

參考文獻(xiàn)：

[1]趙云，劉惟一.一種基于遺傳算法求集中網(wǎng)站的方法.云南大學(xué)學(xué)報(bào)，2003，25（6）.

[2]陳曉平，許卓明.一種基于超級鏈接結(jié)構(gòu)的WWW模糊聚類算法[J].常州技術(shù)師范學(xué)院學(xué)報(bào)，2002，8（2）：47-52.