一種基于Context Graph主題爬行算法的改進(jìn)

高慶芳，蒲寶卿，包 蕾

（隴南師范高等?？茖W(xué)校，甘肅隴南 742500）

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展和全面普及，通過不同網(wǎng)絡(luò)搜索引擎，從海量網(wǎng)絡(luò)信息中獲取信息，是互聯(lián)網(wǎng)應(yīng)用在學(xué)習(xí)和生活中的重要表現(xiàn)形式和組成部分，搜索引擎的核心是網(wǎng)絡(luò)搜索引擎爬行算法.

通過對(duì)主題爬行算法的研究[1]，傳統(tǒng)的算法思想可分為2類：一類是基于Context Graph的主題爬行算法以及基于網(wǎng)絡(luò)的超鏈接結(jié)構(gòu)的爬行算法；另一類是早期由學(xué)者Diligenti提出的基于Context Graph的主題爬行思想，即利用爬行算法爬取相近主題的頁面時(shí)，路線都是相似的[2].要實(shí)現(xiàn)后者的爬行算法，就要構(gòu)建Context Graph模型層次結(jié)構(gòu)圖，用鏈接指向表明頁面之間的聯(lián)系，爬行路徑讓主題爬蟲自主爬取.

根據(jù)相關(guān)文獻(xiàn)，機(jī)器學(xué)習(xí)是主題爬蟲最突出的特點(diǎn)，即可在爬行時(shí)選擇其一網(wǎng)頁分析算法選擇鏈接對(duì)象，對(duì)于無關(guān)的對(duì)象可進(jìn)行剔除.在這種情況下，在保證爬取效率的同時(shí)，也必須確保得到的結(jié)果頁面具有更好的相關(guān)性.在計(jì)算機(jī)系統(tǒng)中用中文分詞系統(tǒng)對(duì)中文文本進(jìn)行詞語自動(dòng)識(shí)別，這方面的研究目前已經(jīng)比較成熟，很多學(xué)者都總結(jié)提出了相關(guān)的算法.根據(jù)其特點(diǎn)，可以對(duì)現(xiàn)有的中文分詞算法分類，主要有基于字符串匹配的、基于統(tǒng)計(jì)的和基于語義的 3類[1].

傳統(tǒng)的主題爬行算法存在不足之處是會(huì)降低網(wǎng)絡(luò)的搜索速度.本文對(duì)傳統(tǒng)的算法做了一個(gè)改進(jìn)，主要修改了TF?IDF公式，目的是可以提高特征詞權(quán)重計(jì)算的準(zhǔn)確性，完成分類器的訓(xùn)練[3].主題爬蟲是基于某個(gè)主題只爬取與主題屬于同一類內(nèi)容的頁面，在建立的主題集上進(jìn)行特征分類，在諸多量化方法中，下文提出的Context Graph層次模型具有較大優(yōu)勢.

1 Context Graph模型的構(gòu)建

基于Context Graph的主題爬蟲算法可以判斷目標(biāo)頁面的路徑與新訪問的頁面一致[3]，計(jì)算當(dāng)前頁面及頁面之間的位置.通過已知位置頁面的樣本訓(xùn)練，得到一定的鏈接路徑，到達(dá)目標(biāo)頁面.

以一個(gè) 2層的 Context Graph模型為例[4]，其結(jié)構(gòu)如圖1所示.為實(shí)現(xiàn)查詢而收集的示例頁面構(gòu)成圖的中心結(jié)點(diǎn)，作為第0層，指向第0層的頁面（這些節(jié)點(diǎn)也稱作父鏈接或者Backlink）被分到第1層，第1層和第0層的節(jié)點(diǎn)之間是直接鏈接關(guān)系，第1層的Backlink節(jié)點(diǎn)做為第2層，以此類推，直到構(gòu)建出所需的模型為止.

圖1 2層的Context Graph模型

2 對(duì)特征權(quán)重算法的改進(jìn)

傳統(tǒng)的Context Graph主題爬行算法存在不足，如要基于爬蟲爬行得到的已知頁面集計(jì)算特征詞的權(quán)值，而計(jì)算的值有時(shí)并不準(zhǔn)確.在此，對(duì)原始算法TF?IDF公式做出改進(jìn).

2.1 文檔特征權(quán)重的計(jì)算方法

TF?IDF函數(shù)用來表示一個(gè)特征項(xiàng)是否重要，即計(jì)算某個(gè)特定向量中一個(gè)詞項(xiàng)的權(quán)重.特征項(xiàng)用詞頻（term frequency，TF）和逆文本頻數(shù)（inverse docu?ment frequency，IDF）2個(gè)因素衡量其重要程度[5].

2.1.1 TF

TF表示某個(gè)文本中某個(gè)特征項(xiàng)出現(xiàn)的次數(shù)[6]，值越大說明該特征項(xiàng)越重要.設(shè)特征詞為ti，文檔為dj，TF定義為

式中ni，j表示在特定文件dj中某個(gè)特征詞的出現(xiàn)次數(shù)，dj包含的所有特征詞出現(xiàn)的次數(shù)之和記做特征權(quán)重的計(jì)算會(huì)受到少數(shù)高頻詞的影響，所以要進(jìn)行歸一化處理[7]，用lg(freqij)+1縮小TF范圍，防止tf值偏向包含更多詞項(xiàng)的長文件，則TF最終可表示為

2.1.2 IDF

IDF反映了特定特征項(xiàng)在不同文檔中的區(qū)別.假設(shè)一個(gè)文檔集中，某個(gè)特征詞很少出現(xiàn)，會(huì)有這樣的情況，即雖然該詞頻度很小，但實(shí)際上該詞具有較高的重要性[8].因此，往往包含某個(gè)特征詞的文檔的總數(shù)與該特征詞的權(quán)重成反比，或近似反比[2].IDF表示為

式中n為所有的訓(xùn)練樣本數(shù)，則特征詞ti出現(xiàn)的訓(xùn)練樣本數(shù)為ni.

通過對(duì)TF?IDF公式的研究，則有，如果某些特征詞在一類文檔中出現(xiàn)頻率足夠高，而在整個(gè)文檔集合的其他文檔中出現(xiàn)頻率足夠小[5]，該詞能更好地區(qū)別不同文檔，因此，用TF和IDF的乘積來標(biāo)記特征空間坐標(biāo)系的取值[10].TF?IDF 公式為

在文檔dj中，特征詞ti的頻度為TFij，n為所有訓(xùn)練樣本數(shù)，ti出現(xiàn)過的訓(xùn)練樣本數(shù)為ni.

2.2 分類訓(xùn)練及主題分類

目前有較多的基于機(jī)器學(xué)習(xí)分類文本的算法，此處基于貝葉斯定理，用分類準(zhǔn)確率較高的樸素貝葉斯（naive bayes classifier）算法[11].假設(shè)一個(gè)類變量y依賴于特征向量(x1，x2，…，xn)，由貝葉斯定理有

假設(shè)條件：

每個(gè)特征項(xiàng)都是獨(dú)立的[12]，則有

基于所有i的關(guān)系，可化簡為

算法步驟：

（1）先驗(yàn)概率、條件概率的計(jì)算，

（2）其中I(·)是指數(shù)函數(shù)I(true)=1，i(false)=0，

（3）j=1，2，…，n，l=1，2，…，Sj，k=1，2，…，K，表示第i個(gè)樣本的第j個(gè)特征，ajl是第j個(gè)特征可能取值的第l個(gè)特征；

分類器的構(gòu)建通過分類訓(xùn)練實(shí)現(xiàn)，過程如下：

（1）將待分類項(xiàng)設(shè)為x={a1，a2，…，am}，a為特征屬性；

（2）存在類別集合C={y1，y2，…，yn}；

（3）計(jì)算條件概率P(y1|x)，P(y2|x)，…，P(yn|x)；

（4）如果P(yk|x)=max{P(y1|x)，P(y2|x)，…，P(yn|x)}，則x∈yk；

（5）計(jì)算（3）步驟中的每個(gè)條件概率是關(guān)鍵.算法思想是先定好訓(xùn)練樣本集，然后對(duì)每個(gè)類別中的各個(gè)特征詞的條件概率估值進(jìn)行統(tǒng)計(jì)[13].

若設(shè)定條件獨(dú)立的各特征屬性，按貝葉斯定理有

分母是常值，在此只需最大化分子.基于各條件獨(dú)立的特征屬性得到

相關(guān)的研究顯示[14]，構(gòu)建N層的上下圖文集模型，則參與訓(xùn)練的先驗(yàn)概率就要為N+2個(gè)類別：P(ci)(i=0，1，2，…，N)、P(cother（)若某頁面不在N層中，則將被歸至cother類），可估計(jì)其先驗(yàn)概率，包含較多文檔的層具有較大的先驗(yàn)概率.因此，重要步驟是估算各個(gè)特征詞在每個(gè)層次（類）的先驗(yàn)概率P(mt|cj)(t=1，2，3，…，|kj|)，可用公式為

式中f(Di(mt)P(cj))為詞mt在文檔Di中出現(xiàn)的次數(shù)，|Vj|為詞集中詞的總數(shù).

N層Context Graph需N+2個(gè)先驗(yàn)概率類別，則文本分類器要有N+1個(gè)類別[15].每次爬取新的頁面Di時(shí)，先對(duì)類別Di進(jìn)行判斷，確定是否會(huì)被劃歸至P(cj|Di)，根據(jù)事先設(shè)定的閥值計(jì)算最大的類別Cj，再與閥值比較，若小于閥值，則Cj會(huì)被歸于P(cj|Di)類.

因此，在一個(gè)N層上下圖文模型中，爬蟲得到的頁面鏈接存放需要N+2個(gè)隊(duì)列.初始狀態(tài)下，0～N隊(duì)列為空，少量特定的頁面會(huì)存放在第N+1隊(duì)列中.經(jīng)判斷，對(duì)應(yīng)層次Ci的頁面會(huì)存放在0～N隊(duì)列中，經(jīng)計(jì)算，某個(gè)頁面分類值小于預(yù)定閾值，其將被劃歸到cother類別，就存儲(chǔ)在第N+1隊(duì)列中.這個(gè)過程是循環(huán)的，每一個(gè)新的網(wǎng)頁被爬取時(shí)，會(huì)將其從距離模型中心最近的非空隊(duì)列中取出，經(jīng)過文本訓(xùn)練后，確定歸屬的類別，得到概率值，默認(rèn)需求最近的前驅(qū)頁面會(huì)優(yōu)先處理.隊(duì)列內(nèi)部會(huì)根據(jù)概率值的大小進(jìn)行排序存儲(chǔ)，確保優(yōu)先處理的特點(diǎn)[16]，這也是主題爬蟲算法的重要特征.

若事件w發(fā)生的概率記做p(w)，則可定義信息論中的信息量公式為

若屬于類別d的文檔的出現(xiàn)概率為p(d)，在可確定的情況下，p(dmk)的值差別不大.針對(duì)該現(xiàn)象做出一個(gè)改進(jìn)，對(duì)應(yīng)公式為

可知，若計(jì)算得到的MI(d，mk)值越大，則lgp(mk)的值就應(yīng)足夠小.

特征選擇算法的特點(diǎn)是基于TF差異[17].在改進(jìn)的算法中，將實(shí)現(xiàn)對(duì)現(xiàn)有的TF?IDF公式的改善.

如果用M(mk，di)來表示詞mk關(guān)于類別di的權(quán)重[18]，則計(jì)算類別權(quán)重的公式為

式中mk為某一文檔集中第k個(gè)特征詞，di為類別中的第i類，N為數(shù)據(jù)集總類別數(shù)為mk在di中出現(xiàn)頻率，λ為調(diào)整系數(shù)在d中的方差，i在d中的均值.i

基于以上理論提出改善后的TF?IDF公式為

與原計(jì)算公式的差別是，原公式與特征詞的類別權(quán)重進(jìn)行乘運(yùn)算.因?yàn)椴煌悇e的文檔，每一個(gè)特征詞的重要性都應(yīng)該被區(qū)分，也就是存在某個(gè)特征詞在某個(gè)特定類別的文檔中更為重要，而該詞必然不會(huì)在其他類別中表現(xiàn)得更為重要.

一般使用比較成熟的語料庫，優(yōu)點(diǎn)是樣本可直接使用.首先，對(duì)樣本集所包含的各個(gè)分詞在每個(gè)類別的權(quán)值M(mk，di)進(jìn)行計(jì)算；其次，計(jì)算平均值(mk，di)；最后，按照語料庫中某個(gè)主題對(duì)應(yīng)的類別，用已計(jì)算出的類別權(quán)值以及改進(jìn)的TF?IDF公式來進(jìn)行運(yùn)算.如果遇到的分詞還沒計(jì)算出類別權(quán)值，可以取該詞對(duì)應(yīng)類別中所有分詞權(quán)值的平均值，而后整個(gè)集合的特征詞集就由計(jì)算結(jié)果最大的分詞構(gòu)成.

3 結(jié) 果

使用搜狗語料庫作為數(shù)據(jù)源來提取文檔和特征詞，其資源內(nèi)容主要采用手工整理與分類，目前是很多實(shí)驗(yàn)中都在采用的樣本.該語料庫中有財(cái)經(jīng)類，本文選取“20.txt”這一文檔，通過對(duì)各類別特征詞的權(quán)值的計(jì)算，再通過后續(xù)處理.搜索主題為房地產(chǎn)時(shí)，其文檔總數(shù)為720次，得到的部分結(jié)果如表1所示.可知，利息出現(xiàn)過的文檔在整個(gè)文檔集中的比例也不高（24%），如果按照改進(jìn)前的TF?IDF公式，類似的這些分詞不會(huì)被重視，對(duì)原有思想及公式改進(jìn)后，其權(quán)重值增大，說明在此提出的改進(jìn)算法是有效的.

表1 提取房地產(chǎn)的部分特征詞結(jié)果

4 結(jié)束語

本文提出的改進(jìn)算法是成功而有效的，可以提高提取特征詞的準(zhǔn)確性.算法不足之處是特征詞相關(guān)度的確定還需再提高.由于漢語的結(jié)構(gòu)復(fù)雜、語義豐富，怎樣理解用戶的真正意圖并準(zhǔn)確定位用戶的搜索目標(biāo)，能否給出其想要的信息，是目前搜索引擎技術(shù)亟待進(jìn)一步解決的問題之一.