改進(jìn)的向量空間模型在主題爬蟲中的應(yīng)用

1、改進(jìn)的向量空間模型在主題爬蟲中的應(yīng)用 改進(jìn)的向量空間模型在主題爬蟲中的應(yīng)用*510摘要：主題爬蟲是垂直搜索引擎中的關(guān)鍵組成模塊，而向量空間模型 VSM 常被主題爬蟲用來判斷一個(gè)抓取到的網(wǎng)頁與搜索主題的相關(guān)度。使用傳統(tǒng)向量空間計(jì)算文檔相關(guān)度值時(shí)不考慮特征項(xiàng)在網(wǎng)頁中的位置,致使相關(guān)度計(jì)算不能達(dá)到最優(yōu)。本文在研究傳統(tǒng)向量模型的基礎(chǔ)上,提出了一種改進(jìn)的向量空間模型,將網(wǎng)頁文檔按位置分塊后首先計(jì)算搜索表達(dá)式與文本塊的相關(guān)度,然后依據(jù)位置權(quán)重綜合計(jì)算出網(wǎng)頁文檔與搜索表達(dá)式的相關(guān)度。經(jīng)實(shí)驗(yàn)對比驗(yàn)證,改進(jìn)后的向量空間模型可以有效的提高爬蟲的主題識別能力,并降低爬蟲運(yùn)行負(fù)載。關(guān)鍵詞：計(jì)算機(jī)應(yīng)用；位置分塊；向量空

2、間模型；主題爬蟲；中圖分類號：TP39315Application of Improved VSM in Focused CrawlerZeng Ming, Yu Junsheng School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing100876 2025303540Abstract: Focused crawler is a key model of vertical search engine,and vector space model VSM is co

3、mmonly used to calculate the relevance of a fetched web page and the query topic. When thetraditional VSM is used,the calculation can not get the optimal result because it does not careabout the position of the feature items in the page.Based on the research on the traditional VSM,animproved VSM is

4、raised in this article.A web page is cut into several pieces based on its structurefirst and each piece is used to calculate its relevance with the query expression.Finally therelevance between the web page and the query topic can be calculated using all the relevance ofthe pieces and its weights.Ex

5、perimental comparison results indicates that the improved VSM canhelp the crawler effectively improve its ability of identifying the query topic and reduce itsrunning load.Key words: Computer Application;Position Cutting;VSM; Focused Crawler0 引言當(dāng)前網(wǎng)絡(luò)媒體發(fā)展迅速，其中蘊(yùn)含的信息每天都是在以爆炸式的速度增長，搜索引擎已經(jīng)成為人們訪問互聯(lián)網(wǎng)的一個(gè)重要的工

6、具。與傳統(tǒng)搜索引擎不同，垂直搜索引擎是近些年來發(fā)展迅速的一個(gè)互聯(lián)網(wǎng)應(yīng)用。它為互聯(lián)網(wǎng)用戶提供專業(yè)的針對行業(yè)的深度查詢服務(wù)，是傳統(tǒng)的搜索引擎技術(shù)的延伸1。垂直搜索引擎對信息過濾精細(xì)，整合某類行業(yè)信息而使得搜索結(jié)果的查準(zhǔn)率、查全率更高，返回給用戶的結(jié)果集更加專而深，從而深受用戶歡迎。一個(gè)專業(yè)的垂直搜索引擎一般由以下幾個(gè)主要模型構(gòu)成：主題爬蟲模塊、索引模塊、檢索模塊以及用戶接口，而主題爬蟲無疑是整個(gè)引擎中一個(gè)核心的模塊2。主題爬蟲基于網(wǎng)頁中的超鏈接不斷爬行而抓取所爬到的網(wǎng)頁，利用一定的搜索策略對網(wǎng)頁進(jìn)行分析，將不會抓取范圍外的網(wǎng)頁而只保存指定領(lǐng)域、指定范圍內(nèi)的相關(guān)網(wǎng)頁信息，以使得抓取結(jié)果相對通用搜索引

7、擎更顯精而深。主題爬蟲的爬蟲范圍只限定于特定主題或?qū)I(yè)領(lǐng)域，因而其在爬行的過程中不需要對整-1-個(gè)互聯(lián)網(wǎng)進(jìn)行遍歷，而只需要選擇與主題相關(guān)的頁面進(jìn)行訪問3。依據(jù)這個(gè)原則，主題爬蟲45往往采取最佳優(yōu)先的爬行策略，此爬行策略的基本思想就是按照一定的模型來計(jì)算網(wǎng)頁與主題的相關(guān)度，進(jìn)而依據(jù)此相關(guān)度來確定是否抓取以及抓取的順序，而向量空間模型即是一個(gè)被廣泛應(yīng)用的主題判定模型。1 傳統(tǒng)向量空間模型501.1傳統(tǒng)模型的基本思想Salton 等人在 70 年代提出了向量空間模型的概念，它是一個(gè)文檔的特征向量表示模型，可將文檔表示成為特征向量4。這個(gè)模型中的基本要素有：（1）文檔 D，即平常意義上的電子文本，而具

8、體到搜索技術(shù)領(lǐng)域中即為一個(gè)具體的網(wǎng)頁。（2）特征項(xiàng) t，即文本所包含的基本語言單位，如詞、短語等，向量空間模型用特征項(xiàng)5560組合來表示一個(gè)文檔。（3）權(quán)重 w，用來標(biāo)識特征項(xiàng)在文檔中的重要程度。在此模型中，將每一個(gè)網(wǎng)頁文檔及用戶的查詢表達(dá)式都看作由相互獨(dú)立的特征項(xiàng) t1 , t 2 ,., t i ,., t n 組成的等長向量，對于每一個(gè)特征項(xiàng) t i ，根據(jù)其在網(wǎng)頁文檔 D j 中重要程度 賦 予 其 一 個(gè) 權(quán) 重 wij ， 并 將 t1, t2 ,., ti ,., tn 看 作 一 個(gè) n 維 坐 標(biāo) 系 中 的 坐 標(biāo) 軸 ，w1 j , w2 j ,., wij ,., wn

9、j 為對應(yīng)的坐標(biāo)值，由此可以將網(wǎng)頁文檔映射為 n 維空間中的一個(gè)點(diǎn)，文檔 D j 可以表示為 n 維向量 D j w1 j , w2 j ,., wij ,., wnj ，而用戶輸入的查詢式依據(jù)同樣的轉(zhuǎn)換方式可表示為 Qk wk1 , wk 2 ,., wki ,., wkn ，這樣的話查詢式與網(wǎng)頁文檔之間的匹配問題就轉(zhuǎn)化為 n 維向量空間中的矢量匹配問題5。65特征項(xiàng)權(quán)重 wij 的計(jì)算特征項(xiàng) t i 及其權(quán)重 wij 是利用向量空間進(jìn)行網(wǎng)頁主題判斷的關(guān)鍵，因?yàn)樗鼈儧Q定了這個(gè)特征項(xiàng)在此文檔 D j 中的重要程度，也即這個(gè)特征項(xiàng)在多大程度可以將此文檔與其他文檔區(qū)分開來6。在中文信息檢索中，一般

10、選取字、詞、短語等作為特征項(xiàng) t i ，當(dāng)然也會受系統(tǒng)的精度、存儲空間等方面的影響。通常來講，詞作為特征項(xiàng)比較合適，因?yàn)樗俏谋镜幕窘M成元素70且在文本中的出現(xiàn)頻率呈一定的統(tǒng)計(jì)規(guī)律7。對于特征項(xiàng)的權(quán)重 wij ，定義方法可以依據(jù)具體使用環(huán)境決定。常用的權(quán)重計(jì)算方法是DF-IDF 算法，這個(gè)算法綜合利用特征項(xiàng)的項(xiàng)頻度 tf、逆文檔頻度 idf 以及文檔加權(quán) wa 來計(jì)算特征項(xiàng)的權(quán)重。項(xiàng)頻度 tf ij 表示特征項(xiàng) t i 在網(wǎng)頁文檔 D j 中出現(xiàn)的次數(shù)， tf ij 越大也就表示這個(gè)特征項(xiàng)對于此文檔越重要。而逆文檔頻度 idf ij 的定義公式是8：75idf i log Ndf i 1 其

11、中 N 表示整個(gè)文檔集合中文檔的數(shù)量， dfi 為文檔頻度，即文檔 D j 在整個(gè)文檔集合中出現(xiàn)的次數(shù)。逆文檔頻度 idf ij 用來衡量特征項(xiàng) t i 在整個(gè)文檔集合中的分布情況，其值越高，就意味著-2-此特征項(xiàng)對于文檔區(qū)分的作用越大。依據(jù)以上討論，可以定義特征項(xiàng) t i 的權(quán)重 wij 為：8085wij tf ij idf i waij其中 waij 表示文檔加權(quán)。查詢向量 Qk 與文檔向量 D j 的相關(guān)性計(jì)算查詢向量與文檔向量具有相同的維度，其定義如下：其中 t i 為指定特征項(xiàng)，Q 為查詢表達(dá)式。?1, ti Q?0, ti Q 2 3 查詢向量與文檔向量之間的相似度，也即 Qk

12、與 D j 的相關(guān)性函數(shù)，直接反映了用戶查詢式和文檔集合中某一具體文檔的匹配程度，是進(jìn)行查詢結(jié)果排序的重要標(biāo)準(zhǔn)。一般相似度的計(jì)算有多種方法，如內(nèi)積法、余弦法等。常用的余弦法定義相關(guān)性函數(shù) Sim Qk , Di 如下990Sim Qk , Di ni1ni1ki2ki? wijni1ij 2 4 其中 n 為文檔向量及查詢向量的維度， wki 和 wij 分別為查詢向量 Qk 和文檔向量 D j 在第 i 維上的坐標(biāo)值。1.2傳統(tǒng)模型的不足目前的信息檢索系統(tǒng)中經(jīng)常利用傳統(tǒng)空間向量模型來處理查詢文檔匹配問題，按照此模95型可以依據(jù)計(jì)算出來的相似度來排列命中的文檔，解決了查詢結(jié)果部分匹配問題，檢索

13、結(jié)果也相對更加精確。模型將自然語言文檔轉(zhuǎn)換到 n 維空間中，利用向量的相似度來反映文檔與查詢式的相關(guān)系，提高了匹配處理的可操控性，相關(guān)度值也克服了布爾模型的缺陷，部分匹配的結(jié)果更加符合用戶的需要。但傳統(tǒng)向量空間模型的不足也是明顯的：100（1）向量空間模型是基于一個(gè)假定的，即所有特征項(xiàng)是獨(dú)立的，沒有考慮到特征項(xiàng)之間的關(guān)聯(lián)，這與現(xiàn)實(shí)中的文檔詞匯分布詞不符。（2）計(jì)算權(quán)重時(shí)，文本長度越長，則文檔越容易被命中，因?yàn)殚L度越長，就意味著其中特征項(xiàng)的出現(xiàn)頻度就可能越高。（3）計(jì)算權(quán)重時(shí)沒有考慮特征項(xiàng)在文檔中的位置，一般特征項(xiàng)位于網(wǎng)頁文檔中的不105同位置時(shí)，其對網(wǎng)頁文檔的主題決定性貢獻(xiàn)也不相同，而傳統(tǒng)向量

14、模型沒有考慮這個(gè)因素。為了解決傳統(tǒng)空間向量模型的不足，尤其針對其沒有考慮特征項(xiàng)位置的缺點(diǎn)，本文提出了改進(jìn)的空間向量模型，用于提高網(wǎng)頁文檔的主題判斷的準(zhǔn)確性，下一節(jié)會給出詳細(xì)思想。-3-2 基于特征項(xiàng)位置的向量空間模型1102.1改進(jìn)模型的基本思想針對傳統(tǒng)向量空間模型沒有考慮到特征項(xiàng)位置的缺陷，本文提出改進(jìn)的基于特征項(xiàng)位置的向量空間模型?；舅枷胧菍⒁粋€(gè)網(wǎng)頁文檔按結(jié)構(gòu)自定義提取為與標(biāo)題、正文、錨文本等位置相對應(yīng)的文本塊，其次針對各文本塊建立特征向量，得到此網(wǎng)頁文檔的特征向量集合。進(jìn)行信息檢索時(shí)，首先分別計(jì)算檢索表達(dá)式 Qk 與網(wǎng)頁文檔對應(yīng)的位置特征向量集合中的各個(gè)位置特征向量進(jìn)行相關(guān)性計(jì)算，可得

15、到與文檔分塊相同數(shù)目的相關(guān)性值，賦予不同位115置的計(jì)算出來的相關(guān)性值不同的權(quán)重，則最終可算出文檔的基于特征項(xiàng)位置的加權(quán)相關(guān)性值。依據(jù)這種算法計(jì)算出來的相關(guān)性值可以更好的反映出特征項(xiàng)位于不同位置上時(shí)對網(wǎng)頁文檔主題與檢索表示式的相關(guān)性的影響能力，并且設(shè)計(jì)者可以自定義不特征項(xiàng)位于不同位置時(shí)的影響權(quán)重，系統(tǒng)更加靈活。120基于位置分塊的特征項(xiàng)權(quán)重計(jì)算將一個(gè)網(wǎng)頁文檔 D j 按照位置結(jié)構(gòu)提取為 m 個(gè)文本塊，第 l 個(gè)文本塊的標(biāo)記為 Sjl，則在此改進(jìn)的向量空間中，特征項(xiàng) ti 在 Sjl 中的塊權(quán)重可表示為：S jl? S jl NtiS jl df iS jl N df ii ?2 5 其中 l

16、為位置加權(quán)，可依據(jù)特征項(xiàng)位于不同位置上時(shí)對該網(wǎng)頁文檔的主題貢獻(xiàn)度進(jìn)行調(diào)整，tfiS jl為特征項(xiàng)在文本塊 Sjl 中出現(xiàn)的頻度，dfi 為包含特征項(xiàng) ti 網(wǎng)頁文檔在整個(gè)文檔集125合中出現(xiàn)的次數(shù)?；谖恢梅謮K的查詢向量與文檔向量相關(guān)性計(jì)算依據(jù)上一節(jié)中提出的基于位置的特征項(xiàng)權(quán)重計(jì)算方法及傳統(tǒng)模型中查詢向量與文檔向量相關(guān)性計(jì)算公式，我們可以推算出本文中改進(jìn)的向量空間模型中一個(gè)查詢向量 Qk 與一個(gè)文本塊 Sjl 及一個(gè)網(wǎng)頁文檔 D j 的相關(guān)性計(jì)算公式分別為：130Sim Qk , S jl ni1ni1S jlii? wkini1ki2 6 ml1 7 其中 Sim Qk , S jl 表示查

17、詢特征向量與網(wǎng)頁文檔 D j 中第 l 個(gè)文本塊的相關(guān)性值，pl 表示特征項(xiàng)位于第 l 個(gè)位置時(shí)對文檔主題的影響權(quán)重，n 表示查詢向量的維度，m 表示網(wǎng)頁文檔分塊的數(shù)目。-4-135改進(jìn)的向量空間模型特點(diǎn)本文依據(jù)網(wǎng)頁文檔的半結(jié)構(gòu)化特點(diǎn)，提出的基于特征向量位置的向量空間模型，相對于傳統(tǒng)模型不考慮特征項(xiàng)在文檔中位置的缺陷有了針對性的改進(jìn)，使得特征項(xiàng)在位于不同位置時(shí)對文檔主題影響的差異得到充分反映。與傳統(tǒng)向量空間模型相比，改進(jìn)后的向量空間模型引入文檔文本分塊并賦予其不同影響140權(quán)重，充分考慮到特征項(xiàng)出現(xiàn)的位置及附加的相關(guān)信息，而不是簡單統(tǒng)計(jì)其在文檔中出現(xiàn)的頻率而忽略其他有用信息，對于 web 信息

18、檢索的準(zhǔn)確率的改善有很大的幫助。3 改進(jìn)的模型在主題爬蟲中的應(yīng)用1451503.1主題爬蟲系統(tǒng)組成本文設(shè)計(jì)的實(shí)驗(yàn)主題爬蟲系統(tǒng)分為以下幾個(gè)模塊：（1） 抓取模塊，依據(jù)設(shè)置的初始種子抓取 6html 網(wǎng)頁文檔。（2） 主題相關(guān)性判定模塊，調(diào)用傳統(tǒng)向量空間模型或者本文中改進(jìn)的空間向量模型進(jìn)行網(wǎng)頁文檔主題相關(guān)性判斷。（3） 鏈接分析模塊，利用 PageRank 算法分析網(wǎng)頁上的鏈接，得出 PR 值。（4） 排序模塊，依據(jù)主題相關(guān)性判定值及 PR 值綜合對抓取結(jié)果排序。系統(tǒng)組成圖如下：主題相關(guān)度判定模塊抓取模塊抓取模塊抓取模塊數(shù)據(jù)庫圖 1主題爬蟲系統(tǒng)Fig. 1Focused Crawler Syste

19、m1551603.2主題爬蟲工作流程本文設(shè)計(jì)的主題爬蟲工作流程為：（1） 抓取模塊取回網(wǎng)頁；（2） 調(diào)用主題相關(guān)性判定模塊，得到網(wǎng)頁文檔主題相關(guān)度值；（3） 調(diào)用鏈接分析模塊，得到網(wǎng)頁文檔 PR 值；（4） 抓取模塊綜合返回的網(wǎng)頁文檔主題相關(guān)度值及 PR 值處理此文檔；（5） 抓取模塊繼續(xù)處理抓取隊(duì)列中的其他 url；（6） 排序模塊依據(jù)主題相關(guān)度值及 PR 值進(jìn)行結(jié)果排序。4 實(shí)驗(yàn)驗(yàn)證本實(shí)驗(yàn)分別實(shí)現(xiàn)了依據(jù)傳統(tǒng)向量空間模型以及本文中改進(jìn)的空間向量模型設(shè)計(jì)的主題165相關(guān)度判定模塊并集成到實(shí)驗(yàn)主題爬蟲系統(tǒng)中，利用 eclipse 開發(fā)環(huán)境開發(fā)系統(tǒng)并進(jìn)行實(shí)驗(yàn)。-5-實(shí)驗(yàn)硬件環(huán)境為 CPU：P725

20、0 2.0GHz；內(nèi)存：2.0G。爬蟲的參數(shù)為：抓取深度為 5，判定模塊判定模型閾值為 0.1。設(shè)置主題爬蟲的初始種子為當(dāng)前主流電子商務(wù)網(wǎng)站，抓取個(gè)人電腦有關(guān)信息，種子列表為：170175在兩種主題判定模塊工作時(shí)，爬蟲抓取的網(wǎng)頁數(shù)據(jù)統(tǒng)計(jì)數(shù)據(jù)如表 1 所示：表 1爬蟲抓取數(shù)據(jù)統(tǒng)計(jì)Tab. 1Statistics of Data from Crawler發(fā)現(xiàn)文檔/個(gè)提取文檔/個(gè)提取失敗/個(gè)收集數(shù)據(jù)/Byte抓取時(shí)間/s傳統(tǒng)向量空間9 7637 638579278 238 738492模型改進(jìn)的向量空8 5025 806506194 386 932362間模型比較爬蟲在使用兩種主題判定模塊時(shí)抓取到的

21、數(shù)據(jù)，我們可以看出：（1）爬蟲提取的文檔數(shù)目出現(xiàn)了明顯減少，這主要是因?yàn)橹黝}相關(guān)性判定模塊幫助180爬蟲排除了大量的無關(guān)網(wǎng)頁，這與我們前文中的分析基本吻合。（2）爬蟲的抓取速度得到了明顯提升，原因在于前面排除的大量網(wǎng)頁使得爬蟲需要分析的網(wǎng)頁數(shù)據(jù)減少，降低了爬蟲的運(yùn)行負(fù)載。另外，從檢索界面可以看出，利用改進(jìn)的向量空間判定模塊時(shí)，爬蟲返回的結(jié)果集排序更加合理，與主題相關(guān)度較高的網(wǎng)頁排名非常先前，這一點(diǎn)要優(yōu)于使用傳統(tǒng)的向量空間模型185190195200作為判定模塊時(shí)的結(jié)果。總體分析來看，基于特征項(xiàng)位置的改進(jìn)的向量空間模型在對主題爬蟲的抓取精度、抓取速度方面都有很大改善。5 結(jié)論本文研究了傳統(tǒng)向量空間模型在計(jì)算網(wǎng)頁文檔與查詢表達(dá)式的相似度方面的缺陷，提出了一個(gè)改進(jìn)的向量空間模型：將一個(gè)網(wǎng)頁文檔按照其結(jié)構(gòu)提取為若干個(gè)文本塊，每個(gè)文本塊均表示為一個(gè)特征向量，利用查詢表達(dá)式的特征向量分別與這些文本塊計(jì)算相關(guān)度,最后對不同位置的文本塊計(jì)算出來的相關(guān)度值進(jìn)行加權(quán)計(jì)算而得到整個(gè)文檔與查詢表達(dá)式的相關(guān)度，而即網(wǎng)頁的主題相關(guān)度。將改進(jìn)的向量空間模型及傳統(tǒng)向量空間模型分別實(shí)現(xiàn)并集成到主題爬蟲中進(jìn)行實(shí)驗(yàn)，結(jié)果表明，改進(jìn)的向量空間模型能幫助爬蟲更好的識別主題相關(guān)的網(wǎng)頁文檔，并有效的降低爬蟲的運(yùn)行負(fù)載，可見改進(jìn)的效果明