段落及類別分布的特征選擇方法

楊鳳芹,樊 娜,孫紅光,孫鐵利,彭 楊

1(東北師范大學 計算機科學與信息技術學院,長春 130117) 2(智能信息處理吉林省高校重點實驗室,長春 130117)

1 引 言

隨著Internet技術的發展,電子文本信息的數量迅猛增長.如何自動高效地組織這些文本信息是文本分類研究所面臨的重要問題.文本分類技術根據文本的內容將文本分成相應的類別.向量空間模型是文本分類過程中常用的文本表示模型.在這種表示模型中,每個文檔對應一個特征向量,文檔中的每個特征詞是向量中的一個特征項.然后利用特征加權方法對每個特征項進行加權,常用的特征加權方法有TF[1],TF*IDF[2]和TF-IGM[3]等,所有文檔特征向量構成了特征向量空間[4].由于特征向量空間模型將出現在文檔集合中的每個詞看作一個特征項,因此特征向量空間會包含上萬個特征,從而導致了文檔表示向量的高維性和稀疏性.這不僅會增加存儲負擔和執行時間,而且會增加分類的錯誤率.錯誤率增加的原因是特征向量中包含了很多不相關的特征,也就是說特征空間中存在很多噪音.因此,有必要在文本分類過程中引入特征選擇技術來減少文本表示中的噪音數據,選擇有效特征,從而節省存儲空間和執行時間,并提高分類的準確率[5].

本文將特征詞在文檔中的段落分布信息與其在類別內和類別間的分布信息相結合,提出了一種新的特征選擇方法.實驗結果表明,與其它特征選擇方法相比,所提出的方法能夠在選擇較少數目特征的前提下,達到最優的分類效果.

2 相關工作

特征選擇問題可以看作狀態空間搜索問題,空間中的每個狀態代表一個可能的特征子集.在文本分類中,特征向量的維數非常高,所以不可能窮盡搜索每個特征子集.因此,為了避免窮盡搜索所有的特征子集,研究者提出利用特征評價函數來計算每個特征的重要程度.根據特征的重要程度對特征進行排序,從而選擇得分高的特征構成最后的特征子集.廣泛應用的特征評價函數有文檔頻率(Document Frequency,DF)[6],信息增益(Information Gain,IG),卡方統計(CHI square)和基于類內和類間綜合度量的特征選擇方法(feature selection based on comprehensive measurement both in inter category and intra category,CMFS)[7].下面介紹一下這些評價函數的基本原理.

假設訓練集包含N篇文檔,這些文檔屬于|C|個類別,類別集合C={C1,C2,…,C|C|}.這N篇文檔共包含|V|個不同特征,ti為第i個特征.對于特定類別Ck,k∈{1,2,…,|C|},a為Ck中包含特征ti的文檔數;b為Ck中不含ti的文檔數;c為包含ti但不屬于C|C|的文檔數;d為不含ti也不屬于Ck的文檔數.

文檔頻率的基本思想:類別Ck中包含特征ti的文檔數越多,ti對Ck的代表能力越強,特征評價函數為:

DF(ti,Ck)=a

(1)

信息增益是一種基于熵的特征評價方式,度量了某個特征的出現或不出現對文本正確分類所提供的信息量,特征ti的信息增益得分計算方式如下:

(2)

卡方統計度量了特征和類別的相互依賴程度.卡方統計根據包含特征ti的文檔和類別Ck的四種關系,定義ti和Ck的相互依賴程度如公式(3).

(3)

CMFS特征選擇方法綜合衡量了特征在類內的相對重要性和在整個訓練集中的相對重要性,度量標準依賴于特征的詞頻,函數定義為:

(4)

其中tf(ti,Ck)是特征ti在類別Ck中的出現頻率,tf(ti)是ti在整個訓練集中的頻率,tf(t,Ck)是類別Ck中所有特征的頻率之和.

此外,還有一些其他的特征評價標準.文獻[8]利用特征類內和訓練集的平均詞頻以及文檔平均詞頻差異程度的綜合值作為特征評價標準.文獻[9]提出了基于詞頻的t-test特征選擇方法,該方法計算特征項在訓練集中詞頻平均值和類內詞頻平均值的差異程度和波動情況.文獻[10]提出了基于泊松分布偏差度量的特征選擇方法,將特征的文檔頻率代入泊松偏差,并結合特征與類別的關系計算特征的重要程度.文獻[11]利用特征項的詞頻替換特征項的文檔頻率對多個特征選擇方法進行了改進,實驗結果證明了詞頻對于特征選擇的作用.

現有的特征選擇方法把詞頻或文檔頻率作為特征重要性的基本度量標準.但是,特征的詞頻無法區分特征在類內各文檔間的均勻分布程度;特征的文檔頻率無法區分特征在文檔中的均勻分布程度[12].為了克服特征的詞頻和文檔頻率的缺點,本文提出了特征的段落頻率,并將其與特征的類別分布信息相結合,提出了一種新的特征選擇方法.

3 本文特征選擇方法

3.1 特征選擇的基本原則

一般來說,選擇有代表性的特征應該遵循以下三個原則.

1.文檔中分布均勻.均勻分散在文檔各個部分的特征比只集中出現在文檔某一小部分的特征應具有更高的得分[12].一些特征僅在文檔的一小段集中出現,而且出現頻率相對較高.如果僅根據特征詞頻對特征重要性排序,會使特征選擇方法更傾向于選擇具有這種特點的特征,忽視了文檔中分布相對均勻的更具有代表性的特征.

2.類內廣泛分布.在同一類別中出現概率較大的特征應賦予較高的得分[13].就某一特定類別而言,如果某個特征在類內分布廣泛,說明該特征表示這個類內文檔的能力更強.

3.語料庫中分布相對集中.當某個特征在特定類別中的出現水平遠高于在整個訓練集中的出現水平時,應賦予其較高的得分[14].如果一個特征在所有類別中出現情況都相同,那么這個特征代表特定類別的能力就會減弱.如果特征在某一類別中頻繁出現而在其它類中出現次數相對較少,這樣的特征更傾向于表達特定類別信息.

3.2 基于段落分布的特征選擇方法

通常,在寫作過程中,作者首先根據主題對文章進行段落劃分,一個段落就是作者想要表達的一個語義群.因此,段落是構成文章的基本單位.針對3.1節中特征選擇原則1,將特征在文檔段落中的分布信息作為衡量特征重要性的影響因素之一.為了量化特征在文檔中均勻分布的程度,本文定義了特征的段落頻率.具體地說,我們根據文檔的自然段來對文檔進行分割,如果特征ti在某個自然段中出現,那么該特征的段落頻率得分加1.特征ti在文檔dj中的段落頻率PF(ti,dj)定義如下:

(5)

其中,ParaNum表示文檔dj中的自然段數目,IsContain(ti,Pp)表示段落Pp中是否包含特征ti,如果Pp中包含ti,則IsContain(ti,Pp)=1,否則IsContain(ti,Pp)=0.

文本數據區別于其它數據的一個顯著特點就是不同文檔的長度差別很大.同一語料庫不同類別的文檔長度相差很大,甚至同一類別中的不同文檔長度差別也非常大.為了消除文檔長度對特征段落頻率的影響,對特征ti在文檔dj中的段落頻率PF(ti,dj)進行規范化,規范化公式為:

(6)

其中,|V|表示文檔集合中特征的總數.

根據特征在文檔中的段落頻率,可以計算特征在類別中的段落頻率.特征ti在類別Ck中的段落頻率的計算公式如下:

(7)

其中,|Ck|表示類別Ck包含的文檔數.

3.3 基于類別分布的特征選擇

針對3.1節中特征選擇原則2和原則3,本文用特征ti在類別Ck中出現的概率,即P(ti|Ck),來刻畫特征ti對類別Ck的描述能力,同時用P(Ck|ti)來刻畫特征ti在整個訓練集中區分各個類別文檔的能力.根據特征的文檔頻率,概率P(ti|Ck)和P(Ck|ti)的定義如公式(8)和公式(9)所示.

(8)

(9)

文獻[11,15]和文獻[16]已經證明了概率P(ti|Ck)和P(Ck|ti)對特征ti重要性的刻畫能力.文獻[15]提出的改進的GINI方法公式(10)和文獻[16]中提出的DFS方法公式(11)均采用了這兩個概率.

(10)

(11)

兩個方法的核心部分都是概率P(ti|Ck)和P(Ck|ti),區別在于引入了不同的平滑因子.

3.4 基于段落分布及類別分布的特征選擇方法

研究已證明概率P(ti|Ck)和P(Ck|ti)能夠刻畫特征ti對類別Ck的代表能力和對各類文檔的區分能力.但在現有的方法中大多用特征的文檔頻率來描述這兩個概率.特征的文檔頻率并沒有考慮特征在文檔中的分布情況,也就是說文檔頻率并不能區分特征是在整個文檔中是均勻出現還是集中出現在文檔中的某個部分.因此,基于文檔頻率的特征選擇方法并不滿足3.1節中特征選擇的原則(1),而本文3.2節中提出的特征的段落頻率充分考慮了特征在文檔中的均勻分布程度.

為了滿足3.1節中特征選擇的3個原則,用特征的段落頻率,即公式(7)中的CPF(ti,Ck),來替換公式(8)和公式(9)中的文檔頻率,重新定義概率P(ti|Ck)和P(Ck|ti)如公式(12)和公式(13)所示.

(12)

(13)

根據公式(12)和公式(13),我們定義基于段落分布和類別分布的特征選擇函數FSPC為:

(14)

通過公式(14)可以計算得到特征ti對類別Ck的重要性得分,然后利用最大化的方法得到ti在訓練集所有類別中最大的重要性得分,并將其作為ti在整個訓練集中的重要性得分,如公式(15).

(15)

根據函數FSPC(ti)對特征進行降序排列,選擇函數值大的特征作為特征選擇結果.

4 實驗與分析

4.1 實驗設置

實驗使用復旦數據集*http://www.nlpir.org/download/tc-corpus-answer.rar和搜狐新聞數據集*http://www.sogou.com/labs/resource/cs.php作為實驗數據,通過選擇不同數量的文檔構造了一個均衡和一個相對失衡的復旦數據集,數據的具體描述如表1所示.搜狐新聞語料庫選擇Business,Yule,Learning,Fund,Sport,Music,Dealer,Digi 8個類別,每類800篇作為訓練集,200篇作為測試集.

采用支持向量機[17]和樸素貝葉斯[18]作為文本分類器,將本文提出的方法FSPC與CHI square,DF,IG和CMFS四種特征選擇方法進行實驗對比分析,將F1值[19]作為評價指標.

實驗采用eclipse和weka作為實驗平臺,利用中科院分詞系統*http://ictclas.nlpir.org/newsdown loads?DocId=389進行分詞,并根據中文停用詞表去停用詞,只保留漢字且長度大于1的詞項,并刪除文檔頻率低于3的詞,采用歸一化的TFIDF方案[10]對文檔進行加權表示.

表1 復旦數據集
Table 1 FuDan datasets

ImbalancedFuDanbalancedFuDanClassTrainTestTrainTestArt450150450150Computer450150450150Sport450150450150Agriculture450150450150Policy750250450150Economic1200400450150Count375012502700900

4.2 實驗結果分析

為了分析各種特征選擇方法的性能,本文參照文獻[7-11,13-16]將選擇的特征數目設置為50,100,200,400,600,800,1000,1200,1400,1600,1800,2000,3000,4000和5000.

4.2.1 均衡復旦數據集上實驗結果分析

下頁表2給出了在均衡數據集上支持向量機和樸素貝葉斯分類器的實驗結果.分類性能的變化曲線如圖1和圖2所示.

對于支持向量機分類器,從整體上看,CMFS和FSPC都優于CHI Square,DF和IG,而FSPC優于CMFS.特征數目為200時,FSPC達到了最佳性能,F1值為96.9%,而CMFS達到最佳性能時(F1值為96.8%),特征數是1000.CHI Square,DF和IG分別在特征數為1000,600和1600時達到其峰值96.3%,95.5%和94.9%.

對于樸素貝葉斯分類器來說,CMFS和FSPC都優于CHI Square,DF和IG,而FSPC優于CMFS.特征數為400時,FSPC的分類性能達到最高值92.9%.CMFS達到它的最高性能時,F1值為92.1%,特征數為1600.

4.2.2 非均衡復旦數據集上實驗結果分析

表3給出了在失衡數據集上支持向量機和樸素貝葉斯分類器的實驗結果.分類結果變化曲線如下頁圖3和圖4所示.

表2 在復旦均衡數據集上分類器支持向量機(a)和樸素貝葉斯(b)的F1值(%)
Table 2 F1 (%) measure on the balanced FuDan dataset using (a) SVM and (b) Na?ve Bayes

Featuresize50100200400600800100012001400160018002000300040005000(a)IG74．675．777．282．991．192．292．993．994．794．994．893．392．491．892．2DF81．183．189．694．495．594．394．695．595．295．295．493．892．692．392．6CHISquare85．689．393．495．195．896．196．396．295．995．395．694．093．993．092．7CMFS89．093．896．796．596．496．696．896．396．196．095．894．594．293．893．4FSPC92．094．196．996．796．696．896．596．496．296．195．994．794．393．993．8(b)IG62．864．164．771．177．378．882．282．283．683．383．581．478．478．878．1DF71．772．778．583．384．684．185．886．285．685．687．284．582．381．580．4CHISquare71．476．684．386．089．691．491．290．590．590．090．788．187．987．387．2CMFS83．486．589．690．289．590．491．191．791．392．191．990．790．289．588．9FSPC86．087．990．792．992．091．491．992．192．491．891．890．389．689．990．1

圖1 在均衡數據集上支持向量機的F1值(%)變化曲線Fig.1 F1 (%) measure curves on the balanced FuDan dataset using SVM

圖2 在均衡數據集上樸素貝葉斯的F1值(%)變化曲線Fig.2 F1 (%) measure curves on the balanced FuDan dataset using naive bayes

Featuresize(a)50100200400600800100012001400160018002000300040005000(a)IG71．674．376．486．789．292．793．293．993．294．195．193．893．493．593．7DF73．577．585．892．093．094．694．194．694．795．394．592．893．594．593．8CHISquare87．691．692．095．096．096．795．996．396．095．996．094．393．894．294．4CMFS90．893．995．795．996．096．296．496．696．096．295．594．594．894．994．4FSPC92．894．796．096．996．996．996．596．496．396．296．094．894．394．194．2(b)IG58．759．361．473．077．079．380．682．381．683．382．680．779．278．678．1DF70．071．174．079．881．484．984．284．384．785．284．781．181．179．479．3CHISquare70．781．581．985．788．688．889．288．488．988．288．289．290．590．490．2CMFS86．988．688．487．687．889．088．588．388．288．988．789．489．690．290．1FSPC88．989．089．690．690．690．790．890．790．489．989．889．989．789．689．4

就支持向量機分類器的性能來說,CMFS和FSPC都優于CHI Square,DF和IG,而FSPC優于CMFS.特征數目為400時,FSPC取得了最佳性能,F1值為96.9%.CMFS達到了它的最佳性能時,F1值為96.6%,特征數為1200.

就樸素貝葉斯分類結果來說,CMFS和FSPC都優于CHI Square,DF和IG.特征數為1000時,FSPC的分類性能達到峰值90.8%.CMFS取得的最佳結果時,F1值為90.2%,特征數為4000.

4.2.3 搜狐新聞數據集上實驗結果分析

表4給出了在搜狐新聞數據集上支持向量機和樸素貝葉斯分類器的實驗結果.分類性能的變化曲線如圖5和圖6所示.

對于支持向量機分類器,從整體上看,FSPC優于CMFS,CHI Square,DF和IG.特征數目為800時,FSPC達到了最佳性能,F1值為92.5%,其它方法在特征數少于或等于800時均未能取得這樣的性能.此外,通過性能變化曲線我們可以發現,隨著特征數目的增加分類性能沒有明顯的提升.

圖3 在失衡數據上支持向量機的F1值(%)變化曲線Fig.3 F1 (%) measure curves on the imbalanced FuDan dataset using SVM

對于樸素貝葉斯分類器來說,特征數為3000時,FSPC的分類性能達到最高值88.3%,之后趨于平緩.其它方法也未能在特征數少于3000時超越FSPC.

圖4 在失衡數據上樸素貝葉斯的F1值(%)變化曲線Fig.4 F1 (%) measure curves on the imbalanced FuDan dataset using Naive Bayes

從上述實驗結果可以看出,分類器的性能基本呈現先升后降或趨于平穩的趨勢,這說明特征數目過少時,所選的特征無法精確描述文檔的語義,但如果特征數目過多,選擇的特征會包含一些噪聲,也會影響文檔的語義描述.從整體性能來說,CHI Square、DF和IG的性能都不及CMFS和FSPC兩種方法,而本文提出的FSPC方法總能夠以最少的特征數目獲得最好的分類性能,這充分驗證了FSPC方法能夠選擇最有效的文本特征,并剔除冗余的噪音特征.

表4 在搜狐數據集上分類器支持向量機(a)和樸素貝葉斯(b)的F1值(%)
Table 4 F1 (%) measure on SogouCS dataset using (a) SVM and (b) Na?ve Bayes

Featuresize(a)50100200400600800100012001400160018002000300040005000(a)IG57．667．579．586．888．889．589．990．189．990．090．590．891．291．591．4DF84．087．589．790．891．091．491．191．391．391．291．391．691．691．491．6CHISquare85．988．289．190．691．391．992．091．991．892．092．092．091．992．092．2CMFS85．989．290．191．191．592．392．592．392．292．291．892．192．092．292．2FSPC86．189．390．791．491．892．592．392．092．192．192．392．291．791．691．8(b)IG49．959．368．476．179．681．883．884．584．985．085．685．585．786．086．0DF73．381．083．184．485．085．886．086．786．587．087．187．387．387．187．5CHISquare71．079．276．679．381．984．184．685．186．087．786．787．087．787．788．2CMFS69．477．080．884．685．186．387．187．487．487．787．887．888．188．288．3FSPC73．381．483．485．486．287．287．687．988．188．188．287．988．388．388．2

圖5 在搜狐數據上支持向量機的F1值(%)變化曲線Fig.5 F1 (%) measure curves on SogouCS dataset using SVM

5 結束語

針對現有特征選擇方法沒有利用特征在文檔段落中分布信息的問題,本文充分考慮特征的段落分布和特征的類內和類間的分布,提出了一種新的特征選擇方法FSPC.提出的方法可以選擇出在文檔中均勻分布的特征,在特定類別中頻繁出現的特征,并剔除在整個語料庫的各類文檔中都頻繁出現的無用特征.在真實數據集上,采用支持向量機和樸素貝葉斯分類器進行實驗,將文本提出的FSPC方法與CHI Square,DF,IG和CMFS四種特征選擇方法進行實驗對比分析.實驗結果驗證了本文提出的特征選擇方法的有效性.下一步工作的重點是研究文本內容的主題檢測方法,應用這些方法更加細致地劃分文檔結構,從而進一步提高特征選擇效率.

圖6 在搜狐數據上樸素貝葉斯的F1值(%)變化曲線Fig.6 F1 (%) measure curves on SogouCS dataset using Naive Bayes

[1] Lopes L,Fernandes P,Vieira R.Estimating term domain relevance through term frequency,disjoint corpora frequency-tf-dcf [J].Knowledge Based Systems,2016,97(C):237-249.

[2] Lan M,Tan C L,Su J,et al.Supervised and traditional term weighting methods for automatic text categorization [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(4):721-735.

[3] Chen Ke-wen,Zhang Zu-ping,Long Jun,et al.Turning from TF-IDF to TF-IGM for term weighting in text classification[C].Expert Systems with Applications,2016,66(C):245-260.

[4] Pinheiro R H W,Cavalcanti G D C,Ren T I.Data-driven global-ranking local feature selection methods for text categorization [J].Expert Systems with Applications,2015,42(4):1941-1949.

[5] Xiao Yi-nan,Xie Rong,Du Juan.Feature selection method for data classification based on t-test and elastic net [J].Journal of Chinese Computer Systems,2015,36(10):2213-2217.

[6] Yang Yi-ming,Pedersen Jan O.A comparative study on feature selection in text categorization [C].In Proceedings of the 14th International Conference on Machine Learning,1997,4(3):412-420.

[7] Yang Jie-ming,Liu Yuan-ning,Zhu Xiao-dong,et al.A new feature selection based on comprehensive measurement both in inter-category and intra-category for text categorization [J].Information Processing and Management,2012,48(4):741-754.

[8] Zhou Hong-fang,Guo Jie,Wang Ying-hui.A feature selection approach based on term distributions [J].Springerplus,2016,5(1):1-14.

[9] Wang De-qing,Zhang Hui,Liu Rui,et al.t-Test feature selection approach based on term frequency for text categorization[J].Pattern Recognition Letters,2014,45(11):1-10.

[10] Ogura H,Amano H,Kondo M.Feature selection with a measure of deviations from Poisson in text categorization [J].Expert Systems with Applications,2009,36(3):6826-6832.

[11] Azam N,Yao Jing-tao.Comparison of term frequency and document frequency based feature selection metrics in text categorization[J].Expert Systems with Applications,2012,39(5):4760-4768.

[12] Xue Xiao-bing,Zhou Zhi-hua.Distributional features for text categorization [J].IEEE Transactions on Knowledge and Data Engineering,2009,21(3):428-442.

[13] Uysal A K,Gunal S.A novel probabilistic feature selection method for text classification[J].Knowledge Based Systems,2012,36(6):226-235.

[14] Rehman A,Javed K,Babri H A,et al.Relative discrimination criterion-A novel feature ranking method for text data[J].Expert Systems with Applications,2015,42(7):3670-3681.

[15] Shang Wen-qian,Huang Hou-kuan,Zhu Hai-bin,et al.A novel feature selection algorithm for text categorization[J].Expert Systems with Applications,2007,33(1):1-5.

[16] Zong Wei,Wu Feng,Chu LapKeung,et al.A discriminative and semantic feature selection method for text categorization[J].International Journal of Production Economics,2015,165:215-222.

[17] Wang Zhen-fei,Liu Kai-li,Zheng Zhi-yun,et al.Prediction retweeting of microblog based on logistic regression model[J].Journal of Chinese Computer Systems,2016,37(8):1651-1655.

[18] Zhang Lun-gan,Jiang Liang-xiao,Li Chao-qun,et al.Two feature weighting approaches for naive Bayes text classifiers[C].Knowledge Based Systems,2016,100(C):137-144.

[19] Kim H K,Kim M.Model-induced term weighting schemes for text classification[J].Applied Intelligence,2016,45(1):30-43.

附中文參考文獻：

[5] 肖憶南,謝 榕,杜 娟.基于t檢驗和彈性網的數據分類特征選擇方法[J].小型微型計算機系統,2015,36(10):2213-2217.

[17] 王振飛,劉凱莉,鄭志蘊,等.基于邏輯回歸模型的微博轉發預測[J].小型微型計算機系統,2016,37(8):1651-1655.