一種主題爬蟲文本分類器的構(gòu)建

姜 鵬，宋繼華

(北京師范大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100875)

1 引言

近年來隨著媒體技術(shù)、網(wǎng)絡(luò)技術(shù)的高速發(fā)展，新型信息資源(包括多媒體信息資源、電子出版物、網(wǎng)絡(luò)信息資源等)大量出現(xiàn)，極大豐富了傳統(tǒng)意義上的對外漢語教學(xué)資源，與此同時，由于資源本身存在數(shù)量規(guī)模大、形式多樣、屬性復(fù)雜等特點，資源的獲取顯得異常困難。同時我們也注意到，對外漢語領(lǐng)域相關(guān)的大部分資源通常集中分布在領(lǐng)域性非常強的少數(shù)網(wǎng)站以及部分論文中，自動獲取資源的關(guān)鍵在于資源的分類識別問題。因此，本課題針對對外漢語資源在互聯(lián)網(wǎng)分布的特點，提出將文本自動分類器植入網(wǎng)絡(luò)爬蟲，使得網(wǎng)絡(luò)爬蟲在互聯(lián)網(wǎng)上爬取資源的時候可以自動的采集主題相關(guān)度高的網(wǎng)頁，丟棄相關(guān)度低甚至不相關(guān)的網(wǎng)頁，從而達(dá)到資源自動獲取的目的[1]。

在線進(jìn)行文本分類的難點之一在于文本的特征提取，特征空間維度太高勢必消耗大量的計算資源，維度太低又無法正確表示目標(biāo)文本，從而有可能丟棄大量具有較高相關(guān)度的文本資源。另一個難點在于在線進(jìn)行分類對于效率的要求，如何提高分類效率，從而迅速判定目標(biāo)文檔與主題是否相關(guān)是整個研究的關(guān)鍵[2]。有鑒于此，針對該命題的研究就顯得十分必要。本文從文本特征抽取和文本向量表示、基于標(biāo)題和正文相結(jié)合的分類器構(gòu)建、實驗設(shè)計及結(jié)果分析、實驗結(jié)論等方面進(jìn)行了闡述。

2 文檔向量模型的構(gòu)建

2.1 文檔頻率

文檔頻率(Document Frequency)是指在訓(xùn)練語料中出現(xiàn)該詞條的文檔數(shù)。采用DF作為特征抽取的方法是從語料庫中統(tǒng)計包含該詞條的文檔數(shù)，如果該DF值低于某個預(yù)先設(shè)定的閾值，則認(rèn)為該詞條是低頻詞，它不含或含有較少的類別信息。將這樣的詞條從原始特征空間中移除，能夠降低特征空間的維數(shù)，還有可能提高分類的精度。

文檔頻率簡單易行，能夠容易地被用于大規(guī)模語料統(tǒng)計。但是其缺乏一定的理論依據(jù)，并且根據(jù)信息論，某些DF值低的詞條往往具有較多的信息量，對分類具有重要意義，不應(yīng)該將它們完全移除。

2.2 χ2統(tǒng)計量

χ2統(tǒng)計量(CHI)度量的是詞條t和文檔類別c之間的相關(guān)程度，并假設(shè)t和c之間符合具有一階自由度的χ2分布[3]。詞條對于某類的χ2統(tǒng)計值越高，它與該類之間的相關(guān)性越大，攜帶的類別信息越多，反之越少。其計算方法如下：

χ2(ti,Cj)

(1)

其中N表示訓(xùn)練語料中的文檔總數(shù)，Cj為某一特定類別，ti表示特定的詞條，A表示屬于Cj類且包含ti的文檔頻數(shù)，B表示不屬于Cj類但是包含ti的文檔頻數(shù)，C表示屬于Cj類但是不包含ti的文檔頻數(shù)，D是既不屬于Cj也不包含ti的文檔頻數(shù)。則ti對于Cj的CHI值。

對于多類問題，分別計算ti對于每個類別的CHI值，再用下式計算詞條ti對于整個語料的CHI值，分別進(jìn)行檢驗：

(2)

其中M為類別數(shù)。從原始特征空間中移除低于特定閾值的詞條，保留高于該閾值的詞條作為文檔表示的特征[4]。

2.3 DF與CHI統(tǒng)計量相結(jié)合的方法

鑒于以上提到的兩種方法各自存在的缺陷，可以參考文獻(xiàn)[5]中提到的將二者相結(jié)合的方法進(jìn)行特征提取。具體做法是先針對語料庫中出現(xiàn)的全部詞條計算其文檔頻率DF，刪除DF值低于某個預(yù)先設(shè)定閾值的詞條，認(rèn)為其為噪聲數(shù)據(jù)。余下的詞條對類別計算其CHI統(tǒng)計量，選取CHI統(tǒng)計量高的詞條作為構(gòu)建文檔特征向量的候選詞條。

在實驗中，我們構(gòu)建的分類器為主題分類器，所面臨的是兩類問題，即只須判斷是否與目標(biāo)主題相關(guān)。因此在構(gòu)建文本向量時，我們首先利用DF方法過濾掉DF值較低的詞條，然后利用公式(1)分別計算文檔標(biāo)題和正文中出現(xiàn)詞條的CHI統(tǒng)計量，最后得出標(biāo)題和正文的特征向量，其中標(biāo)題特征相量維度取50，正文部分特征向量維度取200。部分結(jié)果如表1所示。

表1 DF與CHI相結(jié)合的方法針對標(biāo)題與正文統(tǒng)計出的對外漢語高度相關(guān)的詞條

作為對比試驗的傳統(tǒng)的文本分類法同樣采用DF與CHI相結(jié)合的方法選取特征向量，向量維度取200，與標(biāo)題與正文相結(jié)合的文本分類法相同。選取的部分特征如表2所示。

表2 DF與CHI相結(jié)合的方法針對全文統(tǒng)計出的對外漢語高度相關(guān)的詞條

續(xù)表

3 基于標(biāo)題與正文相結(jié)合的分類器構(gòu)建

3.1 文檔表示

實驗過程中需要將文檔轉(zhuǎn)變?yōu)橛嬎銠C可計算的形式，這里采用了目前較為通用的文檔向量模型(VSM)表示法，在該方法中文檔被表示成向量形式，向量中每個分量的具體值為該特征項在文檔中的權(quán)重。

權(quán)重的計算在本文中采用了TFC的計算方法。該方法為對文本長度進(jìn)行規(guī)一化處理后的TF-IDF方法，具體的計算公式如下：

(3)

其中wij表示特征項ti在文本Dj中的權(quán)重；tfij表示特征項ti在文本Dj中出現(xiàn)的頻數(shù)；ni為訓(xùn)練集中出現(xiàn)ti的文檔數(shù)，N為訓(xùn)練集中總文檔數(shù)。

3.2 分類器的構(gòu)建

分類器的構(gòu)建采用了類中心向量法。該方法為著名的Rocchio分類器的一個特例，其基本思想是首先為每個訓(xùn)練文本C創(chuàng)建一個特征向量，然后利用同一個類中的全部訓(xùn)練文本建立該類的類向量。當(dāng)待分類文本輸入后，計算待分類文本與各個類向量之間的距離，然后根據(jù)計算出的距離值決定待分類文檔的類別[6]。本文中涉及的分類問題為兩類問題，即只需要判斷是否與主題相關(guān)，向量的計算方法為：

(4)

其中wj為類向量的第j個分量，nC為屬于類別C的文本數(shù)，xij為類別C中第i個文檔的第j個分量。

這里的距離計算我們采用了向量夾角的余弦值法，計算方法為：

(5)

我們針對主題類別構(gòu)建了兩個類向量：一是類標(biāo)題特征向量，一是類正文特征向量。二者都通過DF與CHI統(tǒng)計量相結(jié)合的方式選取。當(dāng)目標(biāo)文檔輸入后，首先提取其標(biāo)題信息并做出主題相關(guān)度判定，對于無法判定的網(wǎng)頁在對其正文部分進(jìn)行主題相關(guān)度判定，并得出判定結(jié)果。模型如下：

Sim(D,T)

(6)

在閾值的選取過程中，我們采用了F1評價指標(biāo)作為其選取標(biāo)準(zhǔn)，在整個訓(xùn)練集上訓(xùn)練時，隨著首次分類標(biāo)題閾值和二次分類正文閾值的變化，F(xiàn)1指標(biāo)在標(biāo)題閾值取0.3，同時正文閾值取0.2時達(dá)到最大為0.928，此時P值為0.925，R值為0.931，均達(dá)到一個極大值水平，故在此，我們將首次分類標(biāo)題閾值大于0.3的文本判定為主題相似，對于首次分類不能判定的文本，即標(biāo)題相似度介于(0,0.3)的文本進(jìn)行二次分類，如果計算得出的正文相似度大于0.2，則判定為主題相似，至此，分類過程結(jié)束。閾值訓(xùn)練數(shù)據(jù)如表3所示。

表3 兩階段分類閾值訓(xùn)練結(jié)果

3.3 實驗數(shù)據(jù)

實驗數(shù)據(jù)樣本采用了復(fù)旦大學(xué)自然語言處理實驗室提供的公開語料，其數(shù)據(jù)規(guī)模為8 264個文本文件，其中包括藝術(shù)、文學(xué)、教育、哲學(xué)、歷史、航空航天、能源、電子、通信、計算機、礦產(chǎn)、交運、環(huán)境、農(nóng)業(yè)、經(jīng)濟(jì)、法律、醫(yī)療衛(wèi)生、軍事、政治、體育共20個領(lǐng)域的內(nèi)容，這部分?jǐn)?shù)據(jù)在整個樣本集中主要構(gòu)成反例數(shù)據(jù)。對外漢語領(lǐng)域相關(guān)的正例數(shù)據(jù)主要摘自于國家對外漢語網(wǎng)、國際漢語教育學(xué)會網(wǎng)、北京語言大學(xué)、國家漢辦、對外漢語論壇、北京大學(xué)中文論壇以及對外漢語教師之家的951個文本文件，涉及新聞、論文、書籍介紹等對外漢語相關(guān)的題材。整個樣本集規(guī)模為9 215個文本文件，分別從正反例文本集中按各類別所占比例均勻選取其中1 702個文本構(gòu)成測試集，余下的7 513個文本構(gòu)成訓(xùn)練集。對訓(xùn)練集、測試集中的文本提取出標(biāo)題數(shù)據(jù)后，標(biāo)題和正文形成一一對應(yīng)關(guān)系，最后形成的數(shù)據(jù)集中，訓(xùn)練集數(shù)據(jù)包括標(biāo)題正例集767個文本、標(biāo)題反例集6 746個文本以及正文正例集767個文本、正文反例集6 746個文本，共四個部分，測試集包括標(biāo)題集1 702個文本和正文集 1 702個文本兩部分?jǐn)?shù)據(jù)。

4 實驗結(jié)果及分析

為評價分類效果，我們采用了比較通用的性能評價方法：召回率R(Recall)、準(zhǔn)確率P(Precision)和F1評價。召回率為被分類器正確識別的文檔數(shù)占整個測試集中正例文檔總數(shù)的比率。準(zhǔn)確率為正確分類的文檔數(shù)與被分類器識別文檔總數(shù)的比率。F1度量為二者相結(jié)合的一個評價指標(biāo)，其計算方法為：

(7)

測試集1 702個文本中，包含正例數(shù)據(jù)184個，反例數(shù)據(jù)1 518個。試驗過程中，為爭強對比性，傳統(tǒng)的文本分類法與標(biāo)題與正文相結(jié)合的文本分類法采用相同的特征維度以及權(quán)重統(tǒng)計方法(均為歸一化的tf×idf法)，試驗結(jié)果如表4所示。

表4 在測試集上的測試結(jié)果

在測試過程中我們發(fā)現(xiàn)與傳統(tǒng)的文本向量法相比，本文中提出的方法P值比傳統(tǒng)的文本分類方法有一定的提高，R值略遜于傳統(tǒng)方法，F(xiàn)1值也比傳統(tǒng)方法要好，總體而言P值和R值較為平衡，要好于傳統(tǒng)的分類方法。同時，我們注意到，傳統(tǒng)方法在測試集上測試時耗時36 672ms，而改進(jìn)后的新算法僅用時3 250ms，用時僅為傳統(tǒng)方法的十分之一，性能上有了非常顯著的提高，出現(xiàn)這種情況的原因主要是新算法在首次分類過程中處理了1 464個文本，占整個測試集文本數(shù)的86%，由于標(biāo)題部分文本較小，處理起來非?？欤收麄€算法的效率得到了顯著的提升，而效率問題對于在線主題爬蟲而言是至關(guān)重要的，新算法在不犧牲準(zhǔn)確率和召回率的前提下，極大的提升了在線分類的效率，因而有著極高的實用價值。

5 結(jié)論

本文針對主題爬蟲在線爬取主題相關(guān)的網(wǎng)頁時面臨的文本分類問題構(gòu)建了在線文本分類器，設(shè)計了先標(biāo)題再正文的兩階段文本分類模型。實驗結(jié)果表明該分類器較傳統(tǒng)的分類方法在召回率和效率上都有明顯的提高，并且經(jīng)過適當(dāng)?shù)臄U(kuò)展就可以直接用于多類文本的分類問題。目前，基于該分類器，我們已經(jīng)構(gòu)建了對外漢語領(lǐng)域主題爬蟲，通過該爬蟲動態(tài)獲取、分析互聯(lián)網(wǎng)上對外漢語領(lǐng)域相關(guān)資源，大大拓展了對外漢語領(lǐng)域相關(guān)數(shù)據(jù)來源的廣度，并極大的提高了獲取數(shù)據(jù)的效率和質(zhì)量，為大規(guī)模教學(xué)資源庫的構(gòu)建打下了良好的基礎(chǔ)。

以此同時，本課題將為對外漢語教學(xué)資源的積累提供新的出路，通過資源的動態(tài)獲取、分析，大大降低了對外漢語教材編者、教師和本領(lǐng)域的專家學(xué)者教材編著過程中那些機械性、重復(fù)性的勞動，并為其教學(xué)、研究提供了廣泛、實時的數(shù)據(jù)支持，從而更有利于發(fā)揮其創(chuàng)造才能，幫助其更好的實現(xiàn)自身價值。

[1] 劉漢興，劉財興. 主題爬蟲的搜索策略研究 [J]. 計算機工程與設(shè)計,2008,29(12).

[2] Y. Yang. A Comparative Study on Feature Selection in Text Categorization[C]//Proceeding of the Fourteenth International Conference on Machine Learning (ICML 97),412-420，1997.

[3] 彭時名. 中文文本分類中特征提取算法研究[D]. 碩士學(xué)位論文.

[4] 宗成慶 統(tǒng)計自然語言處理 清華大學(xué)出版社，2008.5

[5] 代六玲，黃河燕，陳肇雄.中文文本分類中特征抽取方法的比較研究 [J].中文信息學(xué)報，2004(l)：26-33.

[6] 龐劍鋒，卜東波，白碩.基于向量空間模型的文本自動分類方法的研究與實現(xiàn)[J].計算機應(yīng)用研究， 2001：5-6.

[7] F. Menczer, G. Pant, M. Ruiz, and P. Srinivasan. Evaluating topic-driven Web crawlers[C]//Proc. 24th Annual Intl. ACM SIGIR Conf. on Research and Development in Information Retrieval, 2001.

[8] Dekang Lin, An information-theoretic definition of similarity[C]//Proceedings of the 15th International Conf. on Machine Learning, pp.296-304. Morgan Kaufmann, San Francisco, CA, (1998).

[9] Michelangelo Diligenti， Frans Coetzee, Steve Lawrence, C. Lee Giles， Marco Gori. Focused Crawling using Context Graphs[C]//26thInternational Conference on Very Large Databases, VLDB 2000, Cairo, Egypt, pp.527-534, 2000.