基于改進(jìn)SVM算法的聚焦爬蟲設(shè)計(jì)與實(shí)現(xiàn)?

喬平安 田晶晶 任 靜

（西安郵電大學(xué) 西安 710061）

1 引言

作為Internet搜索引擎的核心部分，網(wǎng)絡(luò)爬蟲［1］是如今研究重點(diǎn)之一［2］，它面向整個互聯(lián)網(wǎng)并從大量的網(wǎng)頁中爬取資源，是搜索引擎的數(shù)據(jù)來源。隨著互聯(lián)網(wǎng)信息量的驟增，傳統(tǒng)的搜索引擎已無法滿足不同環(huán)境、不同背景下用戶對主題或領(lǐng)域相關(guān)信息的查詢需求，并存在網(wǎng)頁采集周期長、信息更新不及時以及查準(zhǔn)率不高等諸多問題。

針對這種情況，主題搜索引擎以更專注于某一主題、速度更快、信息更新及時等諸多優(yōu)點(diǎn)成為研究的熱門技術(shù)。本文針對網(wǎng)頁特征提取算法，將UM值計(jì)算方法與SVM分類算法中權(quán)重的計(jì)算方法結(jié)合，設(shè)計(jì)實(shí)現(xiàn)了一種基于改進(jìn)SVM算法的聚焦爬蟲，提高了聚焦爬蟲算法的性能，在保證不降低分類準(zhǔn)確性的情況下減少訓(xùn)練時間，提高分類的效率。

2 相關(guān)工作

聚焦網(wǎng)絡(luò)爬蟲是為了爬取與某主題相關(guān)的信息而產(chǎn)生的網(wǎng)頁信息爬取工具。因此，聚焦網(wǎng)絡(luò)爬蟲的首要問題是使用何種方法去判斷主題與所要爬取的網(wǎng)頁信息內(nèi)容是否相關(guān)，以及依據(jù)主題相關(guān)度對統(tǒng)一資源定位符（Uniform Resoure Locator，URL）進(jìn)行優(yōu)先級排序來提高爬取結(jié)果的精確度和搜索效率。而網(wǎng)頁文本特征的提取是確定網(wǎng)頁主題的關(guān)鍵之處，文本特征提取結(jié)果的好壞和特征的數(shù)量直接影響網(wǎng)頁爬取的效果和主題相關(guān)度的計(jì)算速率。目前常用的文本特征提取方法主要有以下兩種類型:1）依據(jù)詞頻信息提取文本特征或者把所有的詞都作為文本特征，但此方法忽略了語法結(jié)構(gòu)的特點(diǎn)以及詞匯之間的關(guān)系，同時特征數(shù)量也會很多；2）利用串匹配算法選擇一些字符串作為文本特征，但該方法會提取到大量的“無價值”的字符串序列，從而使提取的文本特征不能代表網(wǎng)頁文本的特征，且文本特征數(shù)量較多。針對文本特征的提取問題國內(nèi)外學(xué)者針對該研究提出了不同的算法思路:Schleimer等提出的Winnowing算法，是把滑動窗口內(nèi)最小哈希值選取為指紋特征［3］，該算法的問題是數(shù)字指紋密度較大［4］；針對該問題，韋永壯等提出了CCDet算法，根據(jù)句號特征串匹配規(guī)則進(jìn)行文本特征提取，抽取句號前的若干詞語作為句號的特征，進(jìn)行相似度比較［5］，但計(jì)算量很大；徐琴提出合并整體詞的概念，將具有整體性的詞語進(jìn)行合并將其作為文本特征，通過二次特征提取算法來減少數(shù)字指紋數(shù)量［6］，但是該算法存在計(jì)算復(fù)雜度高的問題；Sidorov等提出了一種基于語法結(jié)構(gòu)的的n-grams特征提取算法，將語法信息引入特征提取過程中［7］；Vani等提出利用文檔的概念在不同的結(jié)構(gòu)層次上對文檔和段落級別進(jìn)行檢測［8］。

本文針對特征提取存在的計(jì)算復(fù)雜度高、特征數(shù)量多的問題，提出結(jié)合SVM算法中詞權(quán)重的計(jì)算和UM計(jì)算的詞權(quán)重綜合作為特征詞的權(quán)重，提高特征提取的精確性和降低特征向量的維數(shù)，從而提高爬取的效率、查全率和查準(zhǔn)率，且計(jì)算復(fù)雜度降低。

3 特征提取方法改進(jìn)

3.1 網(wǎng)頁特征提取

在利用SVM分類算法對網(wǎng)頁進(jìn)行分類前，需將網(wǎng)頁的每一個文檔表示成為一個特征向量，以此表示網(wǎng)頁的信息，而特征詞是特征向量的一個分量。SVM算法中采用向量空間模型（VSM）表示網(wǎng)頁文本特征。

VSM［9～10］將文檔的內(nèi)容用多維特征向量表示出來，將文檔 d 用特征向量｛＜w1，t1＞…＜w6，t6＞…＜wi，ti＞｝進(jìn)行表示，其中 wi為文檔中的詞組，ti為該詞組在文檔中所占的權(quán)重，詞組的權(quán)重用TF-IDF（term-frequency-inverse document frequency）算法獲得。

詞頻TF（d，t）可通過式（1）計(jì)算:

其中n（d，t）是詞 t在文檔d中出現(xiàn)的次數(shù)，分母是文檔中詞t的總量。詞t的逆文檔頻率IDF（t）可用式（2）得到:

其中D為所爬取的文檔總數(shù)，Dt是含詞t的文檔數(shù)量。詞t在文檔中的權(quán)重TF-IDF可以通過式（3）得到:

通過VSM可以將文檔表示成較為標(biāo)準(zhǔn)的特征向量，即每個特征向量都是一個n維的空間向量，便于對文檔進(jìn)行分析處理。但利用TF-IDF算法得到的有些特征對文本分類作用不大，并使向量空間的維數(shù)增大，甚至?xí)档蚐VM分類的準(zhǔn)確性。

3.2 聚焦爬蟲特征提取優(yōu)化

3.2.1 特征詞權(quán)重優(yōu)化

通常在對文本進(jìn)行分類時，需要利用文本的特征詞來進(jìn)行預(yù)測，而特征詞則由最確信的詞確定。針對以往常用特征提取方法中這樣類似的問題，本文把UM值的特征提取方法［11］運(yùn)用到聚焦爬蟲算法中。通常，UM描述的是一個特征項(xiàng)屬于一個類的概率，用式（4）、式（5）計(jì)算特征項(xiàng)的概率值。當(dāng)UM的值越近似1時，這個特征項(xiàng)屬于這個類別的概率就越大，相反，當(dāng)UM的值越近似0時，這個特征項(xiàng)屬于這個類別的概率就越小。

tf（t，c）是特征項(xiàng)t在c類中出現(xiàn)的頻率，tf（t）是特征項(xiàng)t在整個類集合中出現(xiàn)的概率。閾值th的范圍在［0，1），若特征項(xiàng)的UM＜th，則被丟棄；若特征項(xiàng)的UM≥th，則保存。因?yàn)樵赟VM算法中每個特征項(xiàng)都有一個權(quán)重，所以同時也將UM值作為這個特征項(xiàng)的權(quán)重。因此，若特征項(xiàng)的UM值高，則它的權(quán)重就大。以此剔除特征詞在文檔中的權(quán)重TF-IDF值比UM值小的權(quán)重值，從而減少向量空間的維數(shù)和降低算法的復(fù)雜度提高分類的準(zhǔn)確率。

3.2.2 閾值設(shè)定的方法

目前針對高頻詞閾值的設(shè)定方法主要是頻次選取法、前N位選取法、中心度選取法、高低頻詞界定公式選取法和普賴斯公式選取法。文獻(xiàn)［11］對五種方法進(jìn)行了對比介紹，結(jié)合本文權(quán)重優(yōu)化計(jì)算方法，本文的閾值的設(shè)定選擇普賴斯公式選取法進(jìn)行計(jì)算。

普賴斯公式最早是用于確定高頻被引用的文獻(xiàn)，從而確定某研究領(lǐng)域內(nèi)的核心作者。因普賴斯公式相較于用高低頻詞界定公式更簡單，比自定義選取法更科學(xué)，逐漸被學(xué)者們接受并應(yīng)用于不同領(lǐng)域的研究中。其高頻詞閾值根據(jù)普賴斯公式確定，計(jì)算公式:，其中M為高頻詞閾值，Nmax表示區(qū)間學(xué)術(shù)論文被引頻次最高值［11］。普賴斯公式可以用于確定領(lǐng)域核心文獻(xiàn)，因此也可利用此公式確定領(lǐng)域核心關(guān)鍵詞。將自變量Nmax表示為關(guān)鍵詞的頻次最高值即可，因此本文用普賴斯公式計(jì)算本文閾值th，其值設(shè)置為0.3。

4 聚焦爬蟲的實(shí)現(xiàn)

4.1 支持向量機(jī)分類

本文利用SVM算法進(jìn)行網(wǎng)頁分類［12～13］，其流程如圖1所示。

圖1 Web文本分類流程

利用SVM分類算法進(jìn)行分類的具體執(zhí)行過程如下:

1）運(yùn)用VSM把網(wǎng)頁文本數(shù)據(jù)轉(zhuǎn)化為SVM分類算法可以處理的格式。

2）選擇合適核函數(shù)。通過多次試驗(yàn)眾多核函數(shù)（線性核函數(shù)、sigmoid核函數(shù)、高斯（RBF）核函數(shù)），實(shí)驗(yàn)結(jié)果表明，選擇RBF作為核函數(shù)所得結(jié)果最好。

3）計(jì)算最優(yōu)的參數(shù)。通過試驗(yàn)對比遺傳算法和粒子群優(yōu)化算法（PSO）對SVM參數(shù)的優(yōu)化，試驗(yàn)結(jié)果表明，采用PSO最優(yōu)化算法計(jì)算SVM分類器的最優(yōu)參數(shù)。

4）對文本樣本數(shù)據(jù)進(jìn)行訓(xùn)練并用測試集進(jìn)行分類預(yù)測時，利用3）所得到的最優(yōu)參數(shù)運(yùn)用到SVM算法分類器中來進(jìn)行實(shí)現(xiàn)。

對網(wǎng)頁進(jìn)行分類后，再進(jìn)行聚焦爬蟲可以提高爬取的效率，減少運(yùn)算量和時間。

4.2 主題相關(guān)度分析

為了爬取的網(wǎng)頁與主題有關(guān)，需要對網(wǎng)頁進(jìn)行篩選。在聚焦爬蟲中若一個頁面的主題相關(guān)度很低，則表明某些關(guān)鍵詞只是偶爾出現(xiàn)在該網(wǎng)頁中，且指定主題和頁面的主題之間關(guān)系較小，處理其中的鏈接沒有意義。因此，將主題相關(guān)度值小于設(shè)定閾值的網(wǎng)頁舍棄，不需要處理該頁面中的鏈接。

目前相似度的計(jì)算方法主要有向量內(nèi)積、歐式距離、余弦距離等幾種。本文聚焦爬蟲的主題相關(guān)度［14］計(jì)算則采用余弦度量法，余弦距離越大表示文檔的相似度越高。該方法是統(tǒng)計(jì)網(wǎng)頁中關(guān)鍵詞出現(xiàn)的頻率，然后與初始的關(guān)鍵詞按式（6）求余弦值，即可得到該網(wǎng)頁的相關(guān)度。

對網(wǎng)頁進(jìn)行分析時，需要設(shè)定一個閾值r，若cos＜α，β＞≥r，則判定該頁面和主題是有關(guān)聯(lián)的。根據(jù)經(jīng)驗(yàn)和實(shí)際要求確定r（取值范圍是［0，1））的取值，如果r值設(shè)置的小則獲得較多的頁面，若r值設(shè)置的大則獲得較少的頁面。在本文的程序中，將閾值r設(shè)置為0.95。其中閾值r以相似與不相似文本的界限值來設(shè)置的，對于三組文本，相似度分別是0.85、0.74與0.95，數(shù)值上雖都接近1，但第一組是不相似的文本，第二組是相似度較高的文本，第三組是最相似的文本。而對于不相似的兩組文本，相似度都集中0.85附近，因此以0.95作為閾值則可區(qū)分相似度高和不相似文本。

4.3 網(wǎng)頁排序

網(wǎng)頁排序［15］主要依據(jù)主題相關(guān)度值使網(wǎng)頁主題相關(guān)度高的網(wǎng)頁排在前面，以便用戶更加快速地訪問到所需要的信息。本文采用余弦距離除以該網(wǎng)頁包含的鏈接個數(shù)，獲得了更加精確的優(yōu)先級順序。

分析鏈接排序采用PageRank算法［16～18］排序，其排序結(jié)果相對更好。算法中網(wǎng)頁的重要程度值可以表示為:P=w1·cos＜α，β＞+w2·R（u），其中cos＜α，β＞是通過上述的主題相關(guān)度分析計(jì)算出的主題相關(guān)度值，用于頁面排序的網(wǎng)頁P(yáng)ageRank值，其中d為界于（0，1）區(qū)間的阻尼系數(shù)，取值為0.85；w1為主題相關(guān)度的權(quán)重，w2為R（u）的權(quán)重，根據(jù)實(shí)驗(yàn)需求來設(shè)置二者的取值，但必須保證w1+w2=1，通過試驗(yàn)本算法設(shè)定w1取0.6，w2取0.4；u是一個網(wǎng)頁，F(xiàn)（u）是u指向的網(wǎng)頁集合，B（u）是指向u的網(wǎng)頁集合，N（u）是u指向外的鏈接數(shù)。利用網(wǎng)頁的重要程度值P對網(wǎng)頁進(jìn)行排序，得到網(wǎng)頁的優(yōu)先級序列。

4.4 評價指標(biāo)

通常每個類的評價指標(biāo)［15，19］是以查準(zhǔn)率（Precision）和查全率（Recall）作為標(biāo)準(zhǔn)，而對于不同的分類器的性能進(jìn)行評估時選用F1值（綜合考慮準(zhǔn)確率和查全率，得到的新評估指標(biāo)F1測試值，也稱為綜合分類率）作為標(biāo)準(zhǔn)測度。計(jì)算公式如式（7）所示:式（7）中 Pi為類i的查準(zhǔn)率，Ri為i的查全率，Ai為正確分到i類的測試文檔數(shù)，Bi為錯誤分到i類的測試文檔數(shù)，Ci為屬于但未被分到i類的測試文檔數(shù)。

4.5 聚焦爬蟲實(shí)現(xiàn)

本文實(shí)驗(yàn)采用Java程序語言實(shí)現(xiàn)聚焦爬蟲，在Eclipse開發(fā)環(huán)境下運(yùn)行，具有良好的擴(kuò)展性和可移植性。程序流程如圖2所示。

圖2 程序運(yùn)行流程

Step 1:對種子和關(guān)鍵詞進(jìn)行初始化；

Step 2:從初始種子開始爬取網(wǎng)頁得到其全部鏈接，并將爬取的鏈接添加到待抓取隊(duì)列之中；

Step 3:對所爬取的網(wǎng)頁利用SVM方法進(jìn)行分類；

Step 4:從優(yōu)先隊(duì)列中獲得鏈接，抓取網(wǎng)頁；

Step 5:判斷網(wǎng)頁的相關(guān)度以決定是否舍棄該網(wǎng)頁:利用VSM和余弦距離計(jì)算主題相關(guān)度，如果網(wǎng)頁相關(guān)度大于閾值，則再將其添加到優(yōu)先隊(duì)列中等待爬取，否則舍棄；將有用鏈接放入等待抓取的URL隊(duì)列；

Step 6:以最佳的搜索策略（OPS）［20～21］從隊(duì)列中選取接下來要抓取的網(wǎng)頁URL，并循環(huán)此過程，一直到滿足爬取結(jié)束的某一要求時終止此次爬??；

Step 7:將所有被爬蟲抓取的網(wǎng)頁保存起來，對其進(jìn)行一定的分析、過濾，并建立索引，方便以后用戶的查閱和檢索。就聚焦爬蟲而言，這一過程所得到的分析結(jié)果可對以后的抓取過程給出反饋和指導(dǎo)。

5 實(shí)驗(yàn)結(jié)果及分析

本文主要是對傳統(tǒng)的聚焦爬蟲算法和基于改進(jìn)的SVM算法的聚焦爬蟲算法進(jìn)行實(shí)驗(yàn)對比驗(yàn)證。本文算法分詞工具采用ICTCLAS版本，選擇云計(jì)算為主題，種子鏈接選取URL=http://cloud.csdn.net/進(jìn)行爬取，利用SVM算法進(jìn)行分類并存儲。然后在各個分類塊中進(jìn)行聚焦爬蟲，獲取與主題相關(guān)的網(wǎng)頁并計(jì)算F1值和主題相關(guān)度。

實(shí)驗(yàn)一:兩種算法在爬取速度方面的對比。對傳統(tǒng)的聚焦爬蟲算法、基于改進(jìn)SVM的聚焦爬蟲算法與基于自適應(yīng)遺傳算法（AGA）的聚焦爬蟲和基于遺傳算法（GA）的聚焦爬蟲進(jìn)行爬取速率的對比。獲取達(dá)到表1要求的網(wǎng)頁，爬蟲訪問所需時間與網(wǎng)頁數(shù)量變化的關(guān)系，如圖3所示。

表1 算法與主相關(guān)度的對比

圖3 算法訪問時間與網(wǎng)頁數(shù)量的變化

從圖3中可以看出，在爬取網(wǎng)頁的開始階段，優(yōu)化后的聚焦爬蟲算法在爬取達(dá)到表1要求的相關(guān)網(wǎng)頁時的速度不及傳統(tǒng)的聚焦爬蟲算法、AGA和GA，但隨著算法的推進(jìn)，優(yōu)化后的聚焦爬蟲算法抓取到的相關(guān)網(wǎng)頁速度明顯略高于傳統(tǒng)的聚焦爬蟲算法、AGA和GA。說明優(yōu)化后的聚焦爬蟲算法通過對特征詞權(quán)重的調(diào)整和對網(wǎng)頁進(jìn)行分類調(diào)整后，在聚集爬蟲爬取網(wǎng)頁的過程中具有更大的覆蓋率，能夠抓取到更多的相關(guān)網(wǎng)頁，速率較高。

實(shí)驗(yàn)二:兩種算法在爬蟲查全率和查準(zhǔn)率（即F1值）方面的對比。在實(shí)驗(yàn)中增加可供測試的網(wǎng)頁文檔的數(shù)量。隨著文檔數(shù)量的增加，驗(yàn)證傳統(tǒng)的聚焦爬蟲算法、基于改進(jìn)SVM算法的聚焦爬蟲和基于AGA的聚焦爬蟲的F1值隨著網(wǎng)頁數(shù)量的增多的變化關(guān)系，以及與廣度優(yōu)先搜索策略（BFS）進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 F1與網(wǎng)頁數(shù)量的關(guān)系對比

從圖4可明顯看出，爬取到的網(wǎng)頁在查全率和查準(zhǔn)率（即F1）方面，對爬取到的網(wǎng)頁利用優(yōu)化后的特征提取方法和用分類器分類后，優(yōu)化后的聚焦爬蟲算法隨著更深入的爬取F1明顯比AGA提高的快和高；采用BFS抓取到的網(wǎng)頁F1隨著爬取的深入開始降低，AGA在持續(xù)一段時間后開始降低，而優(yōu)化后的聚焦爬蟲算法整體有較小的波動后區(qū)域穩(wěn)定，說明優(yōu)化后的聚焦爬蟲算法能夠爬取到更多的主題相關(guān)度高的網(wǎng)頁，且隨著網(wǎng)頁數(shù)量的增多效果反而更好更穩(wěn)定。

6 結(jié)語

通過研究，本論文實(shí)現(xiàn)了一個基于改進(jìn)的SVM算法的聚焦網(wǎng)絡(luò)爬蟲，其中UM值的計(jì)算是通過詞頻進(jìn)行特征詞權(quán)重計(jì)算，之后用其對SVM算法中計(jì)算權(quán)值組成的n×n特征向量進(jìn)行降維處理，剔除了“無意義”的特征詞，從而降低主題詞與網(wǎng)頁特征向量匹配的計(jì)算復(fù)雜度。同時，利用主題相關(guān)度對URL進(jìn)行排序，提高訪問的速率。通過實(shí)驗(yàn)證明，算法提高了爬取與主題相關(guān)的URL時間、主題相關(guān)度以及查全率和查準(zhǔn)率。提出的此算法在爬取網(wǎng)頁URL時可進(jìn)行控制，隨時暫停爬取并訪問爬取的網(wǎng)頁，以驗(yàn)證是否為所需的網(wǎng)頁；還可自行設(shè)置爬取的網(wǎng)頁數(shù)量。在網(wǎng)絡(luò)環(huán)境良好的情況下爬取網(wǎng)頁的質(zhì)量和效率都取得了不錯的效果。