唐小川，邱曦偉，羅 亮

(電子科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，成都 611731)(*通信作者電子郵箱xiaochuantang@std.uestc.edu.cn)

0 引言

自動文本分類是許多信息處理應(yīng)用系統(tǒng)的關(guān)鍵[1]。比如，垃圾網(wǎng)頁檢測需要自動標(biāo)記垃圾網(wǎng)頁，這個任務(wù)通常被建模為分類問題，即將網(wǎng)頁分為正常網(wǎng)頁和垃圾網(wǎng)頁兩類。近年來，越來越多解決文本分類問題的機(jī)器學(xué)習(xí)方法被提出。

文本分類的一大挑戰(zhàn)是需要處理高維數(shù)據(jù)。在對文本進(jìn)行分類之前，需要將文本轉(zhuǎn)化為易于分析的表示形式。典型的文本表示方法是向量空間模型(Vector Space Model， VSM)[2]，即用詞向量表示文本。向量的每一個分量對應(yīng)一個單詞特征，其權(quán)重值為詞頻(Term Frequency， TF)或詞頻逆文檔頻率(Term Frequency- Inverse Document Frequency， TF- IDF)。為了進(jìn)一步表示單詞之間的依賴性，提出了N- gram語言模型。該模型假設(shè)第N個單詞只與前面N-1個單詞相關(guān)，從而將相鄰的N個單詞作為新特征。這種模型增加了指數(shù)級的特征[3]，面臨維數(shù)災(zāi)難問題：一方面數(shù)據(jù)相對稀疏可能導(dǎo)致分類器退化：另一方面導(dǎo)致計算量顯著增加。特征選擇方法被廣泛應(yīng)用于降低文本數(shù)據(jù)的維度。

特征選擇算法的作用是從源數(shù)據(jù)特征空間中選取一個特征子集作代表。現(xiàn)有的特征選擇算法分三類：過濾式(Filter)、封裝式(Wrapper)和嵌入式(Embedded)。過濾式方法通過定義一個評分標(biāo)準(zhǔn)對所有特征進(jìn)行排序，從而選擇評分高的特征。相比封裝式和嵌入式方法，過濾式方法的優(yōu)勢是計算復(fù)雜度低且獨(dú)立于分類器[4]，因此，本文研究文本分類領(lǐng)域的過濾式特征選擇方法?；诨バ畔⒌奶卣鬟x擇方法是一類重要的過濾式方法[4]，比如：最大相關(guān)最小冗余(minimal Redundancy Maximal Relevance， mRMR)、聯(lián)合互信息(Joint Mutual Information， JMI)和條件最大熵特征提取(Conditional Infomax Feature Extraction， CIFE)。

特征選擇方法廣泛應(yīng)用于文本分類。文獻(xiàn)[5]用實(shí)驗(yàn)對比了常用的文本分類特征選擇方法?？ǚ浇y(tǒng)計法(Chi- square)用一個卡方統(tǒng)計量表示特征與類標(biāo)簽之間的統(tǒng)計相關(guān)性。信息增益法(Information Gain， IG)用特征刪除前后信息熵的增量表示該特征與類標(biāo)簽之間的關(guān)聯(lián)關(guān)系?；バ畔⒎?Mutual Information， MI)用一種互信息表示特征與類標(biāo)簽之間的依賴關(guān)系。文檔頻率法(Document Frequency， DF)認(rèn)為在數(shù)據(jù)集中出現(xiàn)某個特征的文檔數(shù)越多，則該文檔越重要。文獻(xiàn)[6]提出一種新的文本分類特征選擇算法，稱之為最大判別法(Maximum Discrimination， MD)。該算法使用JMH(Jeffreys- Multi- Hypothesis)多分布散度，即KL(Kullback- Leibler)散度的一種變形，解決文本分類中的多分類問題。文獻(xiàn)[7]提出一種基于詞頻和t檢驗(yàn)的特征選擇方法。這些文本分類中的特征選擇方法并未考慮特征之間的交互作用。文獻(xiàn)[8]提出一種改進(jìn)的基于互信息的文本分類特征選擇方法。最近的一些文獻(xiàn)研究了特征選擇中的二階和三階交互作用。RelaxMRMR(Relaxed Minimal Redundancy Maximal Relevance)[9]用三維條件互信息度量條件冗余性，并改進(jìn)了最大相關(guān)最小冗余法。文獻(xiàn)[4]為基于信息測度的特征選擇方法提出一個框架，對比實(shí)驗(yàn)結(jié)果表明JMI的精度高并且結(jié)果穩(wěn)定。本文的研究發(fā)現(xiàn)，JMI使用的聯(lián)合互信息可以被分解為二階和三階交互作用。聯(lián)合互信息最大化(Joint Mutual Information Maximization， JMIM)[10]使用最大最小法解決了JMI由于累加造成的一些特征估計過高的問題。交互作用權(quán)重特征選擇(Interaction Weight Feature Selection， IWFS)[11]用一個三階交互作用的變體表示正交互作用和冗余性。

但是，更高階的交互作用也能提升特征選擇。本文提出一種新的特征選擇方法考慮了多種交互作用。該方法使用交互作用信息量計算交互作用，并使用最大最小方法避免由于累加造成的交互作用估計過高的問題。大量實(shí)驗(yàn)表明，交互作用能提升文本分類中的特征選擇方法的性能。

1 特征選擇算法

記輸入數(shù)據(jù)集為D=(X,y)，其中X=(xij)∈RM×N包含了輸入的特征，M是數(shù)據(jù)記錄的數(shù)量，N是特征的數(shù)量。X的每一列xj=(x1j,x2j,…,xMj)T代表一個特征。列y=(y1,y2,…,yM)T代表目標(biāo)變量。輸入的特征集合記為X={x1,x2,…,xN}。特征選擇問題是指從輸入特征中選擇一個最具代表性的特征集合S={x1′,x2′,…,xk′}?X。

1.1 交互作用信息量

假設(shè)x1和y是兩個隨機(jī)變量，則用互信息I(x1;y)度量x1和y之間共享的信息，其定義為：

I(x1;y)=H(x1)+H(y)-H(x1,y)=

(1)

定義1 交互作用信息I(x1;x2;…;xn)用于表示多個變量之間共享的信息[12]，其定義為：

I(S)

(2)

其中S={xi1,xi2,…,xis}是一個特征子集，T={xj1,xj2,…,xjt}是S的一個子集。I(S)=I(xi1;xi2;…;xis)是指S中所有變量之間的交互作用信息，其中分號“;”用于表示交互作用信息。H(T)=H(xj1,xj2,…,xjt)是指T中所有變量的聯(lián)合信息熵，其中逗號“,”用于表示聯(lián)合變量。

三維聯(lián)合互信息與交互作用信息量之間的關(guān)系為：

I(xi,xj;y)=I(xi;y)+I(xj;y)+I(xi;xj;y)

(3)

1.2 基于交互作用的特征選擇方法

基于信息論的特征選擇算法的最優(yōu)目標(biāo)函數(shù)是：

(4)

其中S?X是源特征集合的一個特征子集，y是目標(biāo)變量；但是，子集的個數(shù)有指數(shù)多個，當(dāng)特征個數(shù)較多時，無法窮舉所有特征子集。基于信息論的方法通常使用低維的交互信息逼近高維的I(S,y)，比如：相關(guān)性I(xi;y)和冗余性I(xi;xj)。這些方法基于如下幾個假設(shè)[13]：

1)已選的特征之間相互獨(dú)立；

2)已選的特征條件獨(dú)立于候選特征xk；

3)任意已選的特征都獨(dú)立地影響目標(biāo)變量。

但是，研究表明交互作用也是影響特征選擇的重要因素。在自然語言處理領(lǐng)域，N- gram語言模型廣泛地應(yīng)用于描述單詞之間的依賴性，比如短語[3]。在組合測試領(lǐng)域，95%的軟件錯誤是由測試參數(shù)之間的一階、二階和三階交互作用引起的[14]。在統(tǒng)計學(xué)實(shí)驗(yàn)設(shè)計(Design Of Experiments， DOE)領(lǐng)域[15]，析因設(shè)計等經(jīng)典方法廣泛應(yīng)用于研究特征之間的交互作用。

下面舉一個異或問題的例子，說明交互作用的重要性。假設(shè)有三個相互正交的布爾變量：

x1=(-1,-1,-1,-1,1,1,1,1)T

x2=(-1,-1,1,1,-1,-1,1,1)T

x3=(-1,1,-1,1,-1,1,-1,1)T

目標(biāo)變量y=x1⊕x2⊕x3=(-1,1,1,-1,1,-1,-1,1)T是這些變量的異或。此時四階交互作用I(x1;x2;x3;y)=1，其他互信息的值為0，比如：I(x1;y)，I(x2;y)和I(x3;y)。交互作用x123=x1x2x3=(-1,1,1,-1,1,-1,-1,1)T恰好等于y。

因此，有必要放松特征選擇的假設(shè)條件，允許使用更高階的交互作用。

假設(shè)1 給定三個變量xi∈Sk，xk∈XSk和y，那么Sk中的各個特征獨(dú)立的影響這三個變量，即：

(5)

其中Si={x1,x2,…,xi-1}是在xi之前已選擇的特征。

根據(jù)假設(shè)1，基于信息論的特征選擇問題可分解為交互作用之和：

(6)

證明 令xk∈XSk為一個候選特征，Sk={x1,x2,…,xk-1}是在xk之前已選擇的特征。

由式(3)可知，特征選擇問題可轉(zhuǎn)化為：

其中Ω包含了相對于變量xk的常數(shù)項(xiàng)。由假設(shè)1可知，上式可變?yōu)椋?/p>

從而式(6)得證。

但是，式(6)中高階交互作用的數(shù)量多，導(dǎo)致累加值過大，可能造成交互作用估計過高的問題。本文使用最大最小法解決這一問題，最終得到目標(biāo)函數(shù)如下：

(7)

基于互信息的特征選擇方法的搜索策略通常為順序前向搜索(Sequential Forward Search， SFS)[16]。封裝式方法需要枚舉所有特征子集，而后向搜索需要從全集開始逐個刪除N-k個特征。本文使用效率更高的SFS計算式(7)的目標(biāo)函數(shù)，稱之為Max-Interaction文本分類特征選擇算法，Max-Interaction算法具體如下。

輸入：源特征集合{x1,x2,…,xn}，欲選擇的特征數(shù)量m。

輸出：已選的特征子集S。

初始化S=?，T={x1,x2,…,xn}。

fors=1 tomdo

fork=1 ton-sdo

計算I(Tk;y)

fori=1 ton-s-1 do

計算I(Si;Tk;y)

forj=1 ton-sdo

計算I(Si;Sj;Tk;y)

end for

end for

用式(7)計算J(Tk)

end for

S=S∪z

T=Tz

end for

在算法的第一輪，選擇第一個特征T1，使得I(T1;y)最大。將該特征從集合T中移除并放入集合S。在算法的第二輪，用式(7)計算集合T中每一個特征的目標(biāo)函數(shù)值，選擇最大的特征并移動到集合S。重復(fù)這個過程直至選擇了m個特征。最后，算法輸出選擇的特征集合S。

算法1涉及到計算交互作用信息量。常用的方法是基于頻率的直方圖方法，文獻(xiàn)[17]提出一種互信息的并行實(shí)現(xiàn)。文獻(xiàn)[18]將基于信息論的特征選擇方法在Hadoop上實(shí)現(xiàn)，目的是將這些特征選擇方法應(yīng)用于大數(shù)據(jù)。文獻(xiàn)[16]指出將特征離散化為二值變量有助于提升信息測度的估計精度并且減少計算量。大數(shù)定理表明，隨著數(shù)據(jù)的增加，概率密度估計的精度也會增加，因此，隨著大數(shù)據(jù)的出現(xiàn)，基于信息論的特征選擇方法精度會逐漸增高。相比基因組等科學(xué)研究數(shù)據(jù)，文本數(shù)據(jù)收集成本更低，而且呈爆發(fā)式增長，因而能夠?yàn)楦唠A交互作用信息量提供更準(zhǔn)確的估計。

1.3 計算復(fù)雜度分析

假設(shè)輸入數(shù)據(jù)D∈RM×N含有M個實(shí)例，N個特征，欲選擇的特征數(shù)量為k。文獻(xiàn)[9]指出經(jīng)典的算法JMI和mRMR的復(fù)雜度為O(k2MN)，其原因是JMI需要遍歷一次已選擇的特征子集以便計算I(xi,xk;y)。同理，IWFS也需要遍歷一次已選擇的特征子集以便計算三階交互作用I(xi;xk;y)，其復(fù)雜度也為O(k2MN)。

本文提出的算法Max-Interaction考慮了更高維的信息測度，其復(fù)雜度都是O(k3MN)。相比IWFS，Max-Interaction需要多遍歷一次已選擇的特征子集以便計算四階交互作用I(xi;xj;xk;y)。當(dāng)特征太多時，使用歸一化互信息對特征進(jìn)行預(yù)篩選，縮小搜索空間。未來將進(jìn)一步研究如何降低該算法的復(fù)雜度，比如使用并行計算或者量子計算。

2 實(shí)驗(yàn)

本文通過大量實(shí)驗(yàn)對比了Max-Interaction與其他特征選擇算法。該實(shí)驗(yàn)使用了6個廣泛使用的文本分類數(shù)據(jù)集[1,19]，包括：Reuters、TDT2(NIST Topic Detection and Tracking corpus)、RCV1(Reuters Corpus Volume 1)、BASEHOCK(Baseball vs. Hockey)、PCMAC(Pc vs. Mac)、RELATHE(Religion vs. Atheism)，如表1所示。本文使用分類精度對比特征選擇方法。使用的分類器包括支持向量機(jī)(Support Vector Machine， SVM)、k近鄰(k- Nearest Neighbors，kNN)、決策樹(Decision Tree)和貝葉斯分類器(Na?ve Bayes)。這些分類器都有相應(yīng)的Matlab內(nèi)建函數(shù)。本文對比了1個考慮了三階交互作用的特征選擇方法IWFS[11]，以及4個文本分類中的特征選擇方法，包括MD、Chi- square、MI和DF[6]。所有的實(shí)驗(yàn)在Matlab/C++環(huán)境中實(shí)現(xiàn)。

本文的實(shí)驗(yàn)配置如下。首先，對任意一個數(shù)據(jù)集，用特征選擇方法選擇一個大小為30的特征子集。然后，從選擇的第一個特征開始，逐個增加特征，并分別使用分類器得到十折交叉驗(yàn)證的分類精度。其中，在訓(xùn)練數(shù)據(jù)上訓(xùn)練分類器，并用得到的分類器在測試數(shù)據(jù)上得到分類精度。最后，計算分類錯誤率的總體均值和標(biāo)準(zhǔn)差。

表1 實(shí)驗(yàn)中使用的文本分類數(shù)據(jù)集

表2是在文本分類數(shù)據(jù)集上Max-Interaction與其他文本分類特征選擇方法的對比實(shí)驗(yàn)結(jié)果。表中的最后一行是Max-Interaction與對比方法的單邊配對t檢驗(yàn)結(jié)果，表中的符號分別表示Max-Interaction的性能勝(+)、平(=)和負(fù)(-)。

從總體上看，Max-Interaction比IWFS和Chi- square的平均分類精度分別提升了5.5%和6%。Max-Interaction在絕大多數(shù)實(shí)驗(yàn)上都比對比方法的平均分類精度高，即：勝(93.2%)、平(2.5%)、負(fù)(3.3%)。值得注意的是，Max-Interaction僅在8個實(shí)驗(yàn)中與對比方法相等或更差，而這8個實(shí)驗(yàn)中的7個都是在RCV1數(shù)據(jù)集上出現(xiàn)的。一個可能的原因是RCV1數(shù)據(jù)集中的交互作用很弱。對于分類器k近鄰、支持向量機(jī)和決策樹，Max-Interaction在所有的數(shù)據(jù)集上的分類精度都不低于對比方法。對于貝葉斯分類器，Max-Interaction也僅在4個實(shí)驗(yàn)中比其他方法的分類精度低。需要注意的是，并沒有一個特征選擇方法能在所有數(shù)據(jù)集上都最優(yōu)，需要針對具體問題選擇合適的方法。

圖1進(jìn)一步展示了當(dāng)特征數(shù)量逐漸增加時，不同特征選擇方法之間的分類精度比較。其中，分類器為SVM分類器。在Reuters、TDT2和RELATHE數(shù)據(jù)集上，Max-Interaction明顯優(yōu)于其他方法。Max-Interaction將其他特征選擇方法的最高分類精度提升了5個百分點(diǎn)以上。一個可能的原因是Max-Interaction選擇的文本特征包含了顯著的交互作用。在RCV1、PCMAC和BASEHOCK數(shù)據(jù)集上，Max-Interaction仍然優(yōu)于對比方法，略高于IWFS和Chi- square。

表2 各種文本分類特征選擇的分類精度比較(均值±方差%)

圖1 比較不同特征選擇方法的分類精度隨特征數(shù)的變化

3 結(jié)語

本文提出一種新的特征選擇方法Max-Interaction。該方法使用多種交互作用信息挖掘特征之間的交互作用，同時也使用最大最小法避免高估高階交互作用。在一組覆蓋了多個不同類型的分類器、數(shù)據(jù)集和特征選擇的實(shí)驗(yàn)中，Max-Interaction在其中93%的實(shí)驗(yàn)中取得了比其他方法更好的結(jié)果。Max-Interaction也將IWFS和Chi-square的平均分類精度分別提高了5.5%和6%。這些實(shí)驗(yàn)表明，特征之間的交互作用能提升特征選擇的性能。

未來的研究包括使用并行算法降低Max-Interaction的計算復(fù)雜度，以及使用大數(shù)據(jù)集為信息測度提供更好的估計。