基于偏斜數(shù)據(jù)集的文本分類特征選擇方法研究

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

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

1 引言

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

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

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

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

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

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

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

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

強(qiáng)特征的特點(diǎn)是：

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

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

弱特征的特點(diǎn)是：

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

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

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

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

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

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

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

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

3.2 RCD特征選擇算法

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

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

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

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

doc=0;

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

If(doc是第ci類樣本){

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

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

}

doc++;

}

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

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

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

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

此分類系統(tǒng)的性能評(píng)價(jià)指標(biāo)采用宏平均正確率，宏平均召回率，宏平均F1，因?yàn)楹昶骄笜?biāo)對(duì)每個(gè)類別同等對(duì)待，不會(huì)主要受大類的影響，因此，它更適合于偏斜文本分類的性能評(píng)價(jià)[9]。若訓(xùn)練集中有m個(gè)不同類別，則宏平均的三個(gè)指標(biāo)的具體計(jì)算公式如下。

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

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

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

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

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

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

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

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

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

表1 中文語(yǔ)料上RCD，DF和CHI三種特征選擇方法的對(duì)比

圖1 中文語(yǔ)料上三種特征選擇方法的宏平均各項(xiàng)評(píng)價(jià)指標(biāo)對(duì)比

CHIDFRCD召回率R/%準(zhǔn)確率P/%F1/%召回率R/%準(zhǔn)確率P/%F1/%召回率R/%準(zhǔn)確率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 英文語(yǔ)料上三種特征選擇方法的宏平均各項(xiàng)評(píng)價(jià)指標(biāo)對(duì)比

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

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

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

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

[1] 蘇金樹，張博鋒，徐昕. 基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J]. 軟件學(xué)報(bào)，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]. 計(jì)算機(jī)研究與發(fā)展，2006, 43(11): 58-62.

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

[6] 張愛華，靖紅芳，王斌，等. 文本分類中特征權(quán)重因子的作用研究[J]. 中文信息學(xué)報(bào)，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]. 中文信息學(xué)報(bào),2003, 18(1): 26-32.

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

劉振巖(1973—)，博士研究生，講師，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)處理，人工智能。

E-mail: zhenyanliu@bit.edu.cn

孟丹(1965—)，博士，研究員，主要研究領(lǐng)域?yàn)椴⑿信c分布式處理,網(wǎng)絡(luò)與系統(tǒng)安全。

E-mail: mengdan@iie.ac.cn

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

E-mail: wangweiping@iie.ac.cn