一種基于多特征因子改進(jìn)的中文文本分類算法

葉 敏，湯世平,牛振東

(北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081)

一種基于多特征因子改進(jìn)的中文文本分類算法

葉 敏，湯世平,牛振東

(北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081)

采用向量空間模型(vector space model，VSM)表示網(wǎng)頁(yè)文本，通過(guò)在CHI(Chi-Square)特征選擇算法中引入頻度、集中度、分散度、位置信息這四個(gè)特征因子，并考慮詞長(zhǎng)和位置特征因子改進(jìn)TF-IDF權(quán)重計(jì)算公式，提出了PCHI-PTFIDF(promoted CHI-promoted TF-IDF)算法用于中文文本分類。改進(jìn)算法能降維得到分類能力更強(qiáng)的特征項(xiàng)集、更精確地反映特征項(xiàng)的權(quán)重分布情況。結(jié)果顯示，與使用傳統(tǒng)CHI和傳統(tǒng)TF-IDF的文本分類算法相比，PCHI-PTFIDF算法的宏F1值平均提高了10%。

Abstract: In the framework of the vector space model(VSM), a new PCHI-PTFIDF(promoted CHI-promoted TFIDF)method based on feature selection and weight calculation is proposed. First, the factors of frequency, concentration, dispersion and location are introduced to CHi-Square based feature selection. Then, the TF-IDF weight is proposed to be optimized by the length and location factors of text terms. The proposed method can reduce the dimensions of the features with better classification ability, and produce better estimation of the weight distribution. The experimental results show that, compared with the algorithm using the traditional CHI and traditional TFIDF, the PCHI-PTFIDF method achieves 10% improvement in Macro-F1 on average.

收稿日期： 2016-06-15 定稿日期： 2016-09-18

1 引言

文本自動(dòng)分類[1]是指在給定的分類體系下，將未知類別的文本采用某種算法自動(dòng)分配到所屬類別的過(guò)程。中文文本分類實(shí)驗(yàn)流程分為文檔分詞、特征選擇和提取、特征權(quán)重計(jì)算、構(gòu)造分類器、分類測(cè)試幾個(gè)步驟。文本文檔通常采用G Salton 提出的向量空間模型(VSM)來(lái)表示，而數(shù)據(jù)的高維性、冗余性會(huì)對(duì)文本分類形成強(qiáng)烈的干擾，權(quán)重分布情況也直接影響著文本分類的準(zhǔn)確度。為了降低特征項(xiàng)集維數(shù)、優(yōu)化特征項(xiàng)權(quán)重表示，本文針對(duì)文本分類流程里特征選擇和權(quán)重計(jì)算兩個(gè)環(huán)節(jié)，分析了常用CHI特征選擇算法和TF-IDF權(quán)重計(jì)算方法的不足，提出了基于多特征因子改進(jìn)的中文本文分類算法。

2 相關(guān)工作

代六玲[4]等人通過(guò)分析中、英文文本分類處理的差異，得出“中文特征空間維數(shù)比英文高，且含有更多的低頻詞”的結(jié)論。而CHI算法對(duì)低頻詞的倚重使中文文本分類處于劣勢(shì)。肖雪[5]等在CHI算法中引入了特征項(xiàng)在某類文檔中的頻度信息，減少了低頻詞的干擾，提高了文本分類的效果，不足之處是沒(méi)有考慮特征項(xiàng)在類內(nèi)、類間的分布差異。劉振巖[6]等人從類間集中度的角度提出了適用于偏斜數(shù)據(jù)集的特征選擇算法。文獻(xiàn)[7-9]就特征項(xiàng)在類內(nèi)、類間分布情況設(shè)計(jì)了權(quán)重因子，從而改進(jìn)分類效果，研究的不足之處在于沒(méi)有考慮特征項(xiàng)在文檔中不同位置的權(quán)重分布及特征降維和特征加權(quán)相結(jié)合的問(wèn)題。

本文通過(guò)分析特征項(xiàng)的頻度、類間集中度、類內(nèi)分散度和文本中的位置信息四個(gè)特征因子，優(yōu)化了CHI特征選擇算法，并對(duì)文本向量表示中TF-IDF權(quán)重計(jì)算方法進(jìn)行了改進(jìn)，使改進(jìn)后的權(quán)重體現(xiàn)出位置因素和詞長(zhǎng)對(duì)文本信息分布的影響。結(jié)合兩步改進(jìn)形成PCHI-PTFIDF算法，該算法將位置特征因子用于TF子式，同時(shí)應(yīng)用于特征選擇和特征項(xiàng)權(quán)重計(jì)算，分類效果與優(yōu)化前相比有顯著提升。

3 PCHI-PTFIDF文本分類算法模型

針對(duì)傳統(tǒng)CHI算法存在的問(wèn)題。擬通過(guò)改進(jìn)頻度、集中度、分散度、位置信息四個(gè)特征因子使評(píng)估函數(shù)包含更多分類信息的特性，降低原有算法對(duì)低頻詞敏感的特性，同時(shí)體現(xiàn)特征項(xiàng)在類內(nèi)、類間分布情況。故而，從下面四個(gè)參考因子入手進(jìn)行改進(jìn)：

(1) 特征項(xiàng)頻度

通常某個(gè)特征項(xiàng)ti在某類文本ck中出現(xiàn)的次數(shù)越多，則ti就越能代表類ck，我們用tf(ti,ck)表示ti在類ck內(nèi)出現(xiàn)的次數(shù)。

(2) 類間集中度

一般特征項(xiàng)ti出現(xiàn)的文本類別數(shù)越少，說(shuō)明該特征項(xiàng)區(qū)別不同類別文本的能力越強(qiáng)，我們把特征項(xiàng)和類別間的這種關(guān)系定義為類間集中度，用F(ti)表示。

如果ti只在一個(gè)類中出現(xiàn)，那么只要在某個(gè)文檔中發(fā)現(xiàn)該特征項(xiàng)，就可以確定這個(gè)文檔的類別。ti在兩個(gè)或多個(gè)類中出現(xiàn)，說(shuō)明包含該特征項(xiàng)的文檔可能屬于某些類，不可能屬于另外一些類。如果ti在所有類中都出現(xiàn)，那么認(rèn)為這樣的特征項(xiàng)對(duì)分類幾乎沒(méi)有幫助，可以直接過(guò)濾掉。

由上述分析，特征項(xiàng)的類間集中度可以表示為式(1)。

(1)

其中|C|為訓(xùn)練文本中總的類別數(shù)，|Ci|為包含特征項(xiàng)ti的類別數(shù)。

(3) 類內(nèi)分散度

一個(gè)特征項(xiàng)僅在某類的少數(shù)幾篇文檔中出現(xiàn)，而在該類的其他文檔中不出現(xiàn)，這個(gè)特征項(xiàng)對(duì)該類的作用就??；相反，一個(gè)特征項(xiàng)越在該類中均勻出現(xiàn)，對(duì)該類的作用越大。特征項(xiàng)在類中的這種分布關(guān)系用類內(nèi)分散度來(lái)衡量，我們用dfk(ti)/Nk表示，其中dfk(ti)表示特征ti在類ck內(nèi)出現(xiàn)的文檔數(shù),Nk表示類ck內(nèi)文檔的總數(shù)。

(4) 特征項(xiàng)在文本中的位置重要性度量

特征項(xiàng)的位置信息在一定程度上反映了它的重要性。標(biāo)題區(qū)域比正文區(qū)域的權(quán)重要大，段首段尾區(qū)域的特征項(xiàng)比文本中間特征項(xiàng)權(quán)重要大。為簡(jiǎn)便起見(jiàn)，我們把預(yù)處理之后的語(yǔ)料文本中第一行信息作為文本的標(biāo)題，其余部分為正文。特征項(xiàng)ti在類ck的標(biāo)題位置出現(xiàn)頻數(shù)為tftitle(ti,ck)，在正文位置出現(xiàn)的頻數(shù)為tfbody(ti,ck),特征項(xiàng)在標(biāo)題區(qū)域的權(quán)重為α，特征項(xiàng)在正文區(qū)域的權(quán)重為β。從α=β=1開(kāi)始，隨著α的增大和β的減小，特征項(xiàng)在標(biāo)題位置的重要性越來(lái)越強(qiáng)，在正文區(qū)的重要性越來(lái)越弱，改變?chǔ)梁挺碌闹?，可衡量不同位置?quán)重對(duì)分類效果的影響。

通過(guò)上述的分析，我們可以得到一個(gè)新的特征選擇函數(shù)，將其表示為式(2)。

(2)

其中tfi表示特征項(xiàng)ti在整個(gè)訓(xùn)練集中的頻數(shù)，α≥1≥β>0。

(3)

3.2 基于詞長(zhǎng)和位置的特征項(xiàng)權(quán)重計(jì)算

TF-IDF(詞頻率—逆文檔頻率)的主要思想是： 特征項(xiàng)在文檔中的權(quán)重為特征項(xiàng)在文檔中出現(xiàn)的頻數(shù)反比于包含該特征項(xiàng)的文檔數(shù)目，用來(lái)評(píng)估特征項(xiàng)的重要程度。傳統(tǒng)的TF-IDF公式如式(4)所示。

(4)

傳統(tǒng)的TF-IDF計(jì)算特征項(xiàng)權(quán)重時(shí)，只考慮了特征項(xiàng)頻率和包含特征項(xiàng)的文檔數(shù)量，沒(méi)有考慮特征項(xiàng)在文本中的位置和特征項(xiàng)的長(zhǎng)度這兩個(gè)重要信息。和特征選擇改進(jìn)算法中特征位置的表示類似，特征項(xiàng)ti在文檔dj的標(biāo)題位置出現(xiàn)頻數(shù)為tftitle(ti,dj)，在dj正文位置出現(xiàn)的頻數(shù)為tfbody(ti,dj)。通常較長(zhǎng)的特征項(xiàng)比較短的特征項(xiàng)包含了更多的信息，更適合表征文本的分類，因此需要增大較長(zhǎng)詞的權(quán)重。據(jù)此改進(jìn)TF-IDF算法如式(5)所示。

(5)

式(5)中，L為特征項(xiàng)的長(zhǎng)度，α、β取值的確立與改進(jìn)與特征選擇算法中所述相同。

3.3 PCHI-PTFIDF文本分類算法

PCHI-PTFIDF文本分類算法思想描述如下：

(1) 遍歷訓(xùn)練集，得到訓(xùn)練文本所有不重復(fù)詞項(xiàng)，然后將這些詞項(xiàng)加入到HashMap中，得到原始詞集itemMap，用PCHI算法對(duì)其進(jìn)行降維即得特征項(xiàng)集fMap。

(2) 根據(jù)得到的特征項(xiàng)集，用PTFIDF算法進(jìn)行訓(xùn)練文本的向量表示，訓(xùn)練分類器模型。

訓(xùn)練過(guò)程的偽碼如下所示：

輸入： 訓(xùn)練集D

輸出： 降維后的特征項(xiàng)集fMap，向量表示的訓(xùn)練文本集VSMmap，訓(xùn)練得到分類器svmmodel

file： 訓(xùn)練集中一篇文本

C： 訓(xùn)練集文檔類別

item： 文本中的詞項(xiàng)

itemMap: 訓(xùn)練集中出現(xiàn)的所有詞項(xiàng)的集合

fit: fMap中的特征項(xiàng)

1. for each file in D do

2. itemMap=WordCut.getItemMap(file)

3. C=WordCut. getClassLabel(file)

4. end for

5. for each item in itemMap

6. itemValue(item)=PCHI(item, C)

7. order(item.itemValue())

8. choose the top-N items to form the fMap

9. end for

9. for each item in D

10. for each item in file

11. if item matches a feature item fit in fMap

11. fitValue(fit)=PTFIDF(item)

12. VSMmap(file).add(fit, fitValue(fit))

13. end for

14. end for

15. libfile=convertToSvmFormat(VSMmap(file))

16. svmmodel=libSVM(libfile)

17. end

(3) 遍歷測(cè)試集，采用PTFIDF算法進(jìn)行測(cè)試文本的向量表示，用訓(xùn)練得到的分類器對(duì)測(cè)試集分類，最后評(píng)估分類效果。

測(cè)試集分類過(guò)程的偽碼如下所示：

輸入： 測(cè)試集T，訓(xùn)練過(guò)程得到的特征項(xiàng)集fMap，訓(xùn)練得到的分類器svmmodel

輸出： 向量表示的測(cè)試文本集testVSMmap,測(cè)試文本的類別predictC

testfile： 測(cè)試集中的一篇文本

testitem： 測(cè)試文本中的詞項(xiàng)

testitemMap: 測(cè)試集中出現(xiàn)的所有詞項(xiàng)的集合

fit: fMap中的特征項(xiàng)

1. for each test file in T do

2. testitemMap=WordCut.getItemMap(testfile)

3. end for

4. for each testfile inT

5. for each testitem in testfile

6. if testitem matches a feature item fit in fMap

7. fitValue(fit)=PTFIDF(testitem)

8. testVSMmap(testfile).add(fit, fitValue(fit))

9. end for

10. end for

11. libtestfile=convertToSvmFormat(testVSMmap(testfile))

12. predictC=svmmodel(libtestfile)

13. end

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

本文使用的分詞系統(tǒng)是中國(guó)科學(xué)院計(jì)算技術(shù)研究所漢語(yǔ)詞法分析系統(tǒng)ICTCLAS[11]，分詞處理后去除常用停用詞。實(shí)驗(yàn)采用由臺(tái)灣大學(xué)林智仁教授開(kāi)發(fā)的LIBSVM[12]進(jìn)行SVM分類，我們選用線性SVM分類器。實(shí)驗(yàn)中線性SVM分類器采用libsvm默認(rèn)參數(shù)。

4.1 數(shù)據(jù)集與評(píng)價(jià)方法

數(shù)據(jù)集采用復(fù)旦大學(xué)的文本分類語(yǔ)料，從中選取宇航、計(jì)算機(jī)、經(jīng)濟(jì)、農(nóng)業(yè)、藝術(shù)、歷史、政治、醫(yī)學(xué)、軍事九個(gè)類別，刪掉文檔中除標(biāo)題與正文外的無(wú)關(guān)信息，并從中隨機(jī)選取3 225篇文檔，使訓(xùn)練集和測(cè)試集的文本數(shù)量之比為2∶1進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)集文本分布情況如表1所示。

表1 語(yǔ)料集

本實(shí)驗(yàn)采用查準(zhǔn)率P(precision)和查全率R(recall)來(lái)作為文本分類的測(cè)評(píng)標(biāo)準(zhǔn)，此外還選取F1值作為標(biāo)準(zhǔn)測(cè)度，它是綜合考慮查準(zhǔn)率和查全率的一個(gè)指標(biāo)。計(jì)算公式如下：

(8)

其中,P為類的查準(zhǔn)率，R為類的查全率，TP為正確分類到ck類的測(cè)試文檔數(shù)，F(xiàn)P為錯(cuò)誤分類到ck類的測(cè)試文檔數(shù)，F(xiàn)N為屬于但未被分類到ck類的測(cè)試文檔數(shù)。

上面提出的查準(zhǔn)率、查全率及F1值都是針對(duì)單個(gè)類的分類情況而言的，當(dāng)需要評(píng)價(jià)某個(gè)分類算法時(shí)，需要將所有的類上的結(jié)果綜合起來(lái)得到平均的結(jié)果，實(shí)驗(yàn)采用宏平均F1方法。

上式中，m是類別數(shù)。

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

就特征選擇和特征項(xiàng)權(quán)重計(jì)算中位置因子系數(shù)的確定進(jìn)行實(shí)驗(yàn)，從α=β=1開(kāi)始，隨著α的增大和β的減小，特征項(xiàng)在標(biāo)題區(qū)的重要性越來(lái)越強(qiáng)，在正文區(qū)的重要性越來(lái)越弱，因此用(α，β)表示變化的位置權(quán)重向量，以0.1為變化間隔，可衡量不同位置權(quán)重對(duì)分類效果的影響。

為了獲得合適的特征項(xiàng)位置權(quán)重(α，β)值，通過(guò)控制變量，在不縮減特征項(xiàng)集維數(shù)情況下，采用PCHI-PTFIDF算法進(jìn)行文本分類實(shí)驗(yàn)，實(shí)驗(yàn)得到文本分類宏F1值如圖1所示。

由圖1可知，特征項(xiàng)位置權(quán)重(α，β)值取(1.2,0.8)時(shí)，文本分類宏F1值最高，即特征項(xiàng)在標(biāo)題區(qū)域的權(quán)重α取1.2，特征項(xiàng)在正文區(qū)域的權(quán)重β取0.8時(shí)可以獲得較好的分類效果。與未考慮特征項(xiàng)在文本中位置重要性(α=β=1)時(shí)對(duì)比，文本分類的宏F1值提升了0.9%。

為了考察PCHI算法和PTFIDF方法的優(yōu)化效果，特征項(xiàng)位置權(quán)重(α，β)值取(1.2,0.8)時(shí)，將PCHI-PTFIDF分類算法、PCHI算法、PTFIDF算法與傳統(tǒng)分類算法做比較。圖2為不同算法隨特征集維數(shù)變化時(shí)的分類效果圖。

從圖2可以看出，特征項(xiàng)集維數(shù)較小時(shí)，文本中不相關(guān)或冗余特征所占比重大，因而傳統(tǒng)CHI算法和PTFIDF算法分類效果較差。而維數(shù)較低時(shí)PCHI方法和PCHI-PTFIDF就有較高的宏F1值，且隨著維數(shù)增加，這兩種算法變化穩(wěn)定，魯棒性較強(qiáng)。當(dāng)維數(shù)達(dá)一定程度時(shí)，傳統(tǒng)算法和改進(jìn)TF-IDF算法的分類效果隨維數(shù)增加首先開(kāi)始下降，說(shuō)明PCHI-PTFIDF算法有效地剔除了特征集中的冗余特征，保留了分類能力更強(qiáng)的特征項(xiàng)，達(dá)到確保分類精度的目的。從圖2可以還可以看出，1 500維時(shí)，PCHI-PTFIDF算法的宏F1值達(dá)0.88，可從較大程度上確保分類的準(zhǔn)確性，同時(shí)實(shí)現(xiàn)特征維數(shù)有效壓縮。因此我們以維數(shù)1 500為例，分析不同文本類別的分類效果。表2是特征維數(shù)為1 500時(shí)不同文本類別的宏F1值，圖3為對(duì)應(yīng)的折線圖。

圖1 文本分類宏F1值隨特征項(xiàng)位置權(quán)重的變化

圖2 不同特征維數(shù)下文本分類宏F1值比較

續(xù)表

圖3 維數(shù)1 500時(shí)不同分類算法宏F1值對(duì)比圖

統(tǒng)計(jì)不同算法的宏F1值得出： PTFIDF算法、PCHI算法、PCHI-PTFIDF算法的宏F1值分別提高了3.73%、8.95%、10.91%。從圖3可以看出，相較于其他三種算法，本文提出的PCHI-PTFIDF算法分類效果最佳，其中宏F1值最高的類別是歷史類。醫(yī)學(xué)和軍事類別分類效果最差，原因是這兩種類別文本篇幅普遍較短，文檔向量含有較多空值，文檔向量的稀疏性導(dǎo)致分類能力下降。從圖3還可以看出，PCHI算法也使分類效果得到顯著提升，說(shuō)明通過(guò)對(duì)低頻、分類能力弱的詞項(xiàng)的過(guò)濾，很好地改善了傳統(tǒng)CHI的缺陷。PTFIDF通過(guò)引入詞長(zhǎng)、位置信息改善了文本向量權(quán)重分布，使分類效果進(jìn)一步得到優(yōu)化。

5 結(jié)論

本文通過(guò)分析特征選擇低頻詞敏感、冗余特征比重較大的問(wèn)題，和文本向量權(quán)重分布不精確的問(wèn)題，提出了PCHI-PTFIDF的文本分類方法，利用最大程度減少信息損失的條件下使特征維數(shù)有效壓縮的原理，有效地選出了分類能力較強(qiáng)的特征項(xiàng)集，并進(jìn)一步優(yōu)化了特征項(xiàng)的權(quán)重計(jì)算，調(diào)節(jié)位置系數(shù)得到分類能力更強(qiáng)的位置權(quán)重因子，使文本分類的精度提高了0.9%。通過(guò)實(shí)驗(yàn)可知，新型的文本分類方法相對(duì)于傳統(tǒng)的方法，宏F1值提升了約10%。

[1] Sebastiani F. Machine learning in automated text categorization[J]. Acm Computing Surveys, 2002, 34(2): 1-47.

[2] DeySarakar S, Goswami S. Empirical Study on Filter based Feature Selection Methods for Text Classification[J]. International Journal of Computer Applications, 2013, 81(6): 38-43.

[3] 胡龍茂. 中文文本分類技術(shù)比較研究[J]. 安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版), 2015(2): 49-53.

[4] 代六玲, 黃河燕, 陳肇雄. 中文文本分類中特征抽取方法的比較研究[J]. 中文信息學(xué)報(bào), 2004, 18(1): 26-32.

[5] 肖雪, 盧建云, 余磊,等. 基于最低詞頻CHI的特征選擇算法研究[J]. 西南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015(6): 138-143.

[6] 劉振巖, 孟丹, 王偉平,等. 基于偏斜數(shù)據(jù)集的文本分類特征選擇方法研究[J]. 中文信息學(xué)報(bào), 2014, 28(2): 116-121.

[7] 劉海峰, 蘇展, 劉守生. 一種基于詞頻信息的改進(jìn)CHI文本特征選擇[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(22): 110-114.

[8] 李國(guó)和, 岳翔, 吳衛(wèi)江,等. 面向文本分類的特征詞選取方法研究與改進(jìn)[J]. 中文信息學(xué)報(bào), 2015, 29(4): 120-125.

[9] 申劍博. 改進(jìn)的 TF-IDF中文本特征項(xiàng)加權(quán)算法研究[J]. 軟件導(dǎo)刊, 2015(4): 67-69.

[10] Yang Y. A re-examination of text categorization methods[C]//Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1999: 42-49.

[11] Zhang H P, Yu H K. Xiong D Y, et al. HHMM-based Chinese lexical analyzer ICTCLAS[C]//Proceeds of the Sighan Workshop on Chinese Language Processing. Association for Computational Linguistics, 2003:758-759.

[12] Chang C C, Lin C J. LIBSVM: A library for support vector machines[J]. Acm Transactions on Intelligent Systems & Technology, 2011, 2(3): 389-396.

葉敏(1989—)，碩士，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理、數(shù)字圖書(shū)館。

E-mail: yanmin_ye@126.com

湯世平(1975—)，博士，講師，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言理解。

E-mail: simontangbit@bit.edu.cn

牛振東(1968—)，博士，教授，主要研究領(lǐng)域?yàn)橹悄芙逃浖到y(tǒng)、數(shù)字圖書(shū)館。

E-mail: zniu@bit.edu.cn

An Improved Chinese Text Classification Algorithm Based On Multiple Feature Factors

YE Min, TANG Shiping, NIU Zhendong

(Department of Computer Science, Beijing Institute of Technology, Beijing 100081, China)

1003-0077(2017)04-0132-06

TP391

A