劉振巖，孟 丹，王偉平，王 勇

(1. 中國科學院 計算技術(shù)研究所，北京 100190; 2. 中國科學院大學，北京 100049; 3. 中國科學院 信息工程研究所，北京 100093; 4. 北京理工大學 軟件學院，北京 100081)

1 引言

在文本分類的實際應用中，偏斜數(shù)據(jù)集是普遍存在的。數(shù)據(jù)集的偏斜主要表現(xiàn)為類別分布的不均衡，即數(shù)據(jù)集中不同類別的樣本數(shù)量差別很大。在數(shù)據(jù)偏斜的情況下，樣本無法準確反映整個空間的數(shù)據(jù)分布,分類器容易被大類淹沒而忽略小類，從而直接影響分類效果[1]。

對于常用的基于向量空間模型的文本分類技術(shù)而言，這個問題的真正原因是傳統(tǒng)的特征選擇方法默認數(shù)據(jù)集的各類別樣本數(shù)量是相同的或是相差不多的，這樣會使得由這些方法所確定的特征空間的特征項會絕大多數(shù)來自于大類，只有很少部分或者甚至沒有特征項來自小類。因此，解決數(shù)據(jù)集偏斜問題的一個比較有效的措施就是改進特征選擇方法，使之能夠平等地從各類中選出最具有類別區(qū)分能力的特征項，不會因為數(shù)據(jù)集的偏斜而偏重大類忽略小類，一些有效的改進方法有： CTD[2], SCIW[3], DFICF[4]。但是這些方法的局限之處都是沒有充分分析并綜合利用所有的隱含在偏斜文本數(shù)據(jù)集中的影響特征選擇的重要因素。

本文將首先針對偏斜文本數(shù)據(jù)集的數(shù)據(jù)特點，充分分析發(fā)現(xiàn)偏斜數(shù)據(jù)集中影響特征選擇的所有重要因素，然后綜合利用這些因素來構(gòu)造一個尤其適用于偏斜文本數(shù)據(jù)集的特征選擇函數(shù) — 相對類別差異(Relative Category Difference,RCD)。并在復旦大學的中文語料和Ruters21578英文語料上與傳統(tǒng)特征選擇方法進行對比實驗，實驗結(jié)果表明使用該方法進行特征選擇會極大提高偏斜文本數(shù)據(jù)的分類效果。

本文的內(nèi)容安排如下： 第2節(jié)針對偏斜文本數(shù)據(jù)集的數(shù)據(jù)特點，分析發(fā)現(xiàn)偏斜文本數(shù)據(jù)集中影響特征選擇的所有重要因素；第3節(jié)介紹如何基于這些重要因素來構(gòu)造一個新的特征選擇函數(shù) — 相對類別差異RCD；第4節(jié)首先設(shè)計實驗方案，然后分別在中英文語料上與傳統(tǒng)特征選擇方法進行對比實驗，最后進行實驗結(jié)果分析；第5節(jié)是全文總結(jié)及下一步工作展望。

2 偏斜文本數(shù)據(jù)集中特征選擇的影響因素

偏斜文本數(shù)據(jù)集的顯著特點是不同類別的樣本數(shù)量差別很大，對于大規(guī)模的語料庫，有的類別間的樣本數(shù)可能存在數(shù)量級的差距，小類別的樣本數(shù)會遠遠小于大類別的樣本數(shù)。而傳統(tǒng)的特征選擇方法(DF，CHI等[5-6])默認訓練樣本數(shù)據(jù)集的各類別的樣本數(shù)量是相同的或是相差不多的，在這種默認下，使用這些方法選出的特征詞主要傾向于較高頻出現(xiàn)的詞條，而較低頻出現(xiàn)的詞條通常被去除。但是，在偏斜文本數(shù)據(jù)集中，對于在小類別樣本中較高頻出現(xiàn)的某些重要詞條，因為此類別樣本總數(shù)相對大類別來說很少，導致這些詞條不會被傳統(tǒng)的特征選擇方法選出；而對于在大類別樣本中較低頻出現(xiàn)的某些不重要的詞條，卻因為大類別樣本數(shù)量巨大，很可能會使得這些詞條的特征值超過預設(shè)的閾值而被選出。這樣就會導致由傳統(tǒng)特征選擇方法所確定的特征空間的特征項絕大多數(shù)來自于大類，只有很少部分或者甚至沒有特征項來自小類，從而使得大類別數(shù)據(jù)的分類效果較好，而小類的分類效果很差。

因此，需要深入分析發(fā)現(xiàn)所有隱含在偏斜文本數(shù)據(jù)集中的影響特征選擇的重要因素，再利用這些因素改進特征選擇方法使之能夠平等地從各類中選出最具有類別區(qū)分能力的特征項。本節(jié)將深入分析偏斜數(shù)據(jù)集的數(shù)據(jù)特點，探尋影響特征選擇的重要因素。

特征選擇的主要目的是要選出類別區(qū)分能力較強的特征項(簡稱強特征)，去除類別區(qū)分能力較弱的特征項(簡稱弱特征)。在偏斜文本數(shù)據(jù)集中，強特征和弱特征的特點分析如下。

強特征的特點是：

(1) 只在一個類別的樣本中出現(xiàn)，且在此類別中較多的樣本中出現(xiàn)；

(2) 在多個類別的文檔中出現(xiàn)，但是在其中某個類別中的文檔頻率明顯多。

弱特征的特點是：

(1) 只在一個類別的樣本中出現(xiàn)，但在此類別中較少的樣本中出現(xiàn)；

(2) 在多個類別的文檔中出現(xiàn)，但是在這多個類別中的文檔頻率大致相當。

根據(jù)以上分析可以發(fā)現(xiàn)： 影響特征項類別區(qū)分能力的一個重要因素之一是特征項的類別分布，即對于兩個文檔頻率相同的特征項，若一個特征項只是集中出現(xiàn)在一個類別或極少的幾個類別中，而另一個特征項幾乎均勻分散出現(xiàn)在所有的類別中，則這兩個特征項的類別區(qū)分能力是不同的，前一種情況的特征項更具有類別區(qū)分能力。

但是，特征項在各類中文檔頻率的不同也會影響特征項的類別區(qū)分能力，對于偏斜文本數(shù)據(jù)集來說，因為各類別樣本數(shù)量相差懸殊，使用絕對的文檔頻率的差異顯然不能用來衡量這種不同，故采用相對文檔頻率差異來衡量，所謂的相對文檔頻率就是特征項在某類中的文檔頻率和該類的樣本總數(shù)之比。特征項在兩類間相對文檔頻率差異越大，說明該特征項表征其中一類的能力越強，越可以將兩類樣本區(qū)分開。這就是影響特征項類別區(qū)分能力的另一個重要影響因素——特征項的類間差異。

總結(jié)以上分析，在偏斜文本數(shù)據(jù)集中，影響特征項類別區(qū)分能力的兩個重要因素是特征項的類別分布和特征項的類間差異。其中特征項的類別分布因素反映的是特征項在整個數(shù)據(jù)集中的類別頻率差異，而類間差異反映的是特征項在不同類別之間的相對文檔頻率差異。這兩個重要因素不是各自獨立的，兩者缺一不可，需要互相配合來共同完成偏斜文本數(shù)據(jù)集的特征選擇任務。

3 適用于偏斜文本分類的特征選擇方法——相對類別差異RCD

3.1 構(gòu)造RCD特征選擇函數(shù)

基于上節(jié)所介紹的影響偏斜文本數(shù)據(jù)集特征選擇的兩個重要因素，本節(jié)將闡述如何構(gòu)造一個新的尤其適用于偏斜文本分類的特征選擇方法——相對類別差異RCD。此方法包含兩個因子，一個是類別分布因子，該因子反映的是特征項在整個數(shù)據(jù)集中類別頻率差異;另一個是類間差異因子，該因子反映的是特征項在不同類別之間的相對文檔頻率差異。第一個類別分布因子采用倒轉(zhuǎn)類別頻率ICF(Inverse Category Frequency)[4]的概念進行計算，來強化出現(xiàn)在較少類別中特征項，如式(1)所示。

3.2 RCD特征選擇算法

設(shè)訓練集有m個不同類別，且所有樣本已經(jīng)按類別分組，經(jīng)過分詞等預處理后的訓練集中有n個不重復的詞條，用一個n×m的二維數(shù)組df記錄每一個詞在每一個類中出現(xiàn)的文檔數(shù)。

則RCD特征選擇算法思想描述如下：

(i) 第一次掃描訓練集，得到原始的所有不重復的詞條，然后將它們加入到一個Hash表中，形成原始的詞集合D；

(ii) 第二次掃描訓練集，得到每個原始詞條在每個類中的文檔頻率，偽代碼如下：

doc=0;

While(doc<訓練集的樣本總數(shù)){

If(doc是第ci類樣本){

不重復地取出所有出現(xiàn)在doc中的詞條;

對于每個詞條在D中找到該詞條的位置ti，并將df[ti][ci]加一;

}

doc++;

}

(iii) 基于二維數(shù)組df，按照式(2)計算每一個詞條t的m個RCD(t,ci)，再求這m個的平均值，并加一完成類間差異因子的計算；

(iv) 按照式(1)計算另一個類別分布因子ICF，即掃描二維數(shù)組df，統(tǒng)計每行的非0個數(shù)，即為每個詞條出現(xiàn)的類別數(shù)；

(v) 按照式(3)為每個詞條計算最終的得分，并取出高于某個預設(shè)的閾值的所有詞條，形成特征詞典。

4 實驗設(shè)計與結(jié)果分析

4.1 實驗設(shè)計

為了分析和驗證本文所提出的相對類別差異特征選擇方法RCD，專門設(shè)計并實現(xiàn)了一個文本分類系統(tǒng)，整個系統(tǒng)由兩個子系統(tǒng)組成，一個是訓練子系統(tǒng)，另一個是測試子系統(tǒng)。訓練子系統(tǒng)的任務是基于訓練集建立特征空間(即特征詞典)并訓練分類器，測試子系統(tǒng)的任務是首先使用訓練階段所建立的特征詞典進行文本表示，然后再使用分類器進行分類。

實驗數(shù)據(jù)有兩個，一個來自于復旦大學計算機信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組整理的中文語料庫，另一個來自于英文語料Reuters21578。對于中文語料庫，選取了經(jīng)濟、計算機和藝術(shù)三類共550篇作為訓練集，其中經(jīng)濟類400篇、藝術(shù)類100篇、計算機類50篇；測試集共300篇，各類平均100篇。訓練集的預處理主要包括分詞和去停用詞，使用中國科學院的中文分詞工具ICTCLAS*http://ictclas.org/Down_OpenSrc.asp進行分詞。對于英文語料庫，使用了Ana*http://web.ist.utl.pt/acardoso/整理的已經(jīng)進行了去停用詞、詞干還原等預處理的Reuters R8的數(shù)據(jù)集，從中選取了三類作為訓練和測試數(shù)據(jù)集，三類分別是acq，crude和ship類，訓練集的樣本數(shù)共1 957個，各類分別是1 596、253和108，測試集的樣本數(shù)共853個，各類分別是696、121和36。

為了將相對類別差異特征選擇方法RCD和傳統(tǒng)的特征選擇方法進行對比，建立特征詞典分別使用了三種特征選擇方法，即RCD，DF，CHI，之所以選用DF和CHI兩種方法，是因為有實驗表明[7-8]這兩種方法的性能都比較好。在文本表示階段使用TF-IDF計算權(quán)值。分類算法采用性能較好的SVM，具體實現(xiàn)借助于臺灣大學提供的LIBSVM工具包*http://www.csie.ntu.edu.tw/～cjlin/，核函數(shù)采用線性核函數(shù)。

此分類系統(tǒng)的性能評價指標采用宏平均正確率，宏平均召回率，宏平均F1，因為宏平均指標對每個類別同等對待，不會主要受大類的影響，因此，它更適合于偏斜文本分類的性能評價[9]。若訓練集中有m個不同類別，則宏平均的三個指標的具體計算公式如下。

宏平均正確率如式(4)所示。

其中，Pi表示第i個類別的正確率，即分類結(jié)果的第i類別中判斷正確的文檔所占的比例。

宏平均召回率如式(5)所示。

其中，Ri表示第i個類別的召回率，即測試集的第i類別中判斷正確的文檔所占的比例。

宏平均F1如式(6)所示。

其中，F(xiàn)1i表示第i個類別的F1值，即

4.2 實驗結(jié)果分析

對于中文語料，分別使用RCD，DF和CHI三種特征選擇方法，通過調(diào)整各自的閾值，從原始詞集合(59 043個不重復的詞)中選出數(shù)量大致相同的特征項建立各自的特征詞典進行對比實驗。本文選取了能達到較好分類效果的各有880個左右特征項的特征詞典的實驗結(jié)果進行展示，各項評價指標的詳細對比如表1所示，宏平均各項指標的對比如圖1所示。從實驗結(jié)果可以發(fā)現(xiàn)，和CHI和DF方法相比，RCD方法的宏平均召回率、準確率和F1值都均有顯著提高，尤其是小類(計算機類)的召回率有很大提高。

對于英文語料，同樣分別使用RCD，DF和CHI三種特征選擇方法，通過調(diào)整各自的閾值，從原始詞集合(9 469個不重復的詞)中選出數(shù)量大致相同的特征項建立各自的特征詞典進行對比實驗。本文選取了能達到較好分類效果的各有750個左右特征項的特征詞典的實驗結(jié)果進行展示，各項評價指標的詳細對比如表2所示，宏平均各項指標的對比如圖2所示。從實驗結(jié)果可以發(fā)現(xiàn)，和CHI和DF方法相比，RCD方法的宏平均各項評價指標均有較大提高，尤其是小類(ship類)的召回率有很大提高，只是較中文語料的提高要略小一些，但是實驗結(jié)果基本是一致的。

表1 中文語料上RCD，DF和CHI三種特征選擇方法的對比

圖1 中文語料上三種特征選擇方法的宏平均各項評價指標對比

CHIDFRCD召回率R/%準確率P/%F1/%召回率R/%準確率P/%F1/%召回率R/%準確率P/%F1/%acq99．7197．6198．6598．9995．6997．3299．1497．3298．22crude90．9193．2292．0571．0786．0077．8390．0896．4693．16ship58．3387．5070．0069．4475．7672．4680．5693．5586．57宏平均82．9992．7886．9079．8485．8282．5489．9395．7892．65

圖2 英文語料上三種特征選擇方法的宏平均各項評價指標對比

綜上所述，通過在中英文語料上的實驗表明： 與其他同類特征選擇方法相比，RCD特征選擇方法不僅能夠保證整體的分類性能，而且尤其能夠提高小類的分類效果。

5 結(jié)論與下一步工作

本文針對偏斜文本數(shù)據(jù)集中類別分布極其不均衡的特點，提出一種有效的特征選擇方法——相對類別差異RCD方法，此方法尤其對不同類別的樣本數(shù)量差異很敏感，它充分考慮了特征項在不同類別間的差異，這種差異包含兩部分，即特征項的類別頻率差異以及不同類別間的相對文檔頻率差異。通過在中英文語料上與同類方法的對比實驗表明，RCD特征選擇方法不僅能夠保證整體的分類性能，而且尤其能夠提高小類的分類效果，因而是一種非常適合于偏斜文本分類的特征選擇方法。而且該方法計算復雜度不高，實現(xiàn)簡單，能夠很容易地被推廣應用。

下一步工作的重點將放在將RCD方法與實際應用相結(jié)合，進一步驗證并完善此方法的特征選擇函數(shù)。

[1] 蘇金樹，張博鋒，徐昕. 基于機器學習的文本分類技術(shù)研究進展[J]. 軟件學報，2006, 17(9): 1848-1859

[2] How B C, Nara Yanan K. An Empirical Study of Feature Selection for Text Categorization based on Term weightage[C]//Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence(WI’04), Beijing, 2004: 599-602.

[3] Shoushan Li, Chengqing Zong. A New Approach to Feature Selection for Text Categorization[C]//Proceedings of the IEEE International Conference on Natural Language Processing and Knowledge Engineering (NLP-KE).Wuhan, 2005: 626-630.

[4] 徐燕，李錦濤，王斌，等. 不均衡數(shù)據(jù)集上文本分類的特征選擇研究[J]. 計算機研究與發(fā)展，2006, 43(11): 58-62.

[5] 周茜，趙明生，等. 中文文本分類中的特征選擇研究[J]. 中文信息學報，2003, 18(3): 17-23.

[6] 張愛華，靖紅芳，王斌，等. 文本分類中特征權(quán)重因子的作用研究[J]. 中文信息學報，2010, 24(3): 97-104.

[7] Yang Y, Pedersen J. A Comparative Study on Feature Selection in Text Categorization[C]//Proceedings of the 14th International Conference on Machine Learning, 1997: 412-420.

[8] 代六玲，黃河燕，等. 中文文本分類中特征抽取方法的比較研究[J]. 中文信息學報,2003, 18(1): 26-32.

[9] Christopher D M, Prabhakar R, Hinrich S. Introduction to Information Retrieval[M], 2008.

劉振巖(1973—)，博士研究生，講師，主要研究領(lǐng)域為海量數(shù)據(jù)處理，人工智能。

E-mail: zhenyanliu@bit.edu.cn

孟丹(1965—)，博士，研究員，主要研究領(lǐng)域為并行與分布式處理,網(wǎng)絡(luò)與系統(tǒng)安全。

E-mail: mengdan@iie.ac.cn

王偉平(1975—)，博士，副研究員，主要研究領(lǐng)域為數(shù)據(jù)庫，海量數(shù)據(jù)處理。

E-mail: wangweiping@iie.ac.cn