基于交互作用的文本分類特征選擇算法

唐小川，邱曦偉，羅 亮

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

0 引言

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

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

特征選擇算法的作用是從源數(shù)據(jù)特征空間中選取一個(gè)特征子集作代表。現(xiàn)有的特征選擇算法分三類：過(guò)濾式(Filter)、封裝式(Wrapper)和嵌入式(Embedded)。過(guò)濾式方法通過(guò)定義一個(gè)評(píng)分標(biāo)準(zhǔn)對(duì)所有特征進(jìn)行排序，從而選擇評(píng)分高的特征。相比封裝式和嵌入式方法，過(guò)濾式方法的優(yōu)勢(shì)是計(jì)算復(fù)雜度低且獨(dú)立于分類器[4]，因此，本文研究文本分類領(lǐng)域的過(guò)濾式特征選擇方法。基于互信息的特征選擇方法是一類重要的過(guò)濾式方法[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)對(duì)比了常用的文本分類特征選擇方法。卡方統(tǒng)計(jì)法(Chi- square)用一個(gè)卡方統(tǒng)計(jì)量表示特征與類標(biāo)簽之間的統(tǒng)計(jì)相關(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)某個(gè)特征的文檔數(shù)越多，則該文檔越重要。文獻(xiàn)[6]提出一種新的文本分類特征選擇算法，稱之為最大判別法(Maximum Discrimination， MD)。該算法使用JMH(Jeffreys- Multi- Hypothesis)多分布散度，即KL(Kullback- Leibler)散度的一種變形，解決文本分類中的多分類問(wèn)題。文獻(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]為基于信息測(cè)度的特征選擇方法提出一個(gè)框架，對(duì)比實(shí)驗(yàn)結(jié)果表明JMI的精度高并且結(jié)果穩(wěn)定。本文的研究發(fā)現(xiàn)，JMI使用的聯(lián)合互信息可以被分解為二階和三階交互作用。聯(lián)合互信息最大化(Joint Mutual Information Maximization， JMIM)[10]使用最大最小法解決了JMI由于累加造成的一些特征估計(jì)過(guò)高的問(wèn)題。交互作用權(quán)重特征選擇(Interaction Weight Feature Selection， IWFS)[11]用一個(gè)三階交互作用的變體表示正交互作用和冗余性。

但是，更高階的交互作用也能提升特征選擇。本文提出一種新的特征選擇方法考慮了多種交互作用。該方法使用交互作用信息量計(jì)算交互作用，并使用最大最小方法避免由于累加造成的交互作用估計(jì)過(guò)高的問(wèn)題。大量實(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代表一個(gè)特征。列y=(y1,y2,…,yM)T代表目標(biāo)變量。輸入的特征集合記為X={x1,x2,…,xN}。特征選擇問(wèn)題是指從輸入特征中選擇一個(gè)最具代表性的特征集合S={x1′,x2′,…,xk′}?X。

1.1 交互作用信息量

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

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

(1)

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

I(S)

(2)

其中S={xi1,xi2,…,xis}是一個(gè)特征子集，T={xj1,xj2,…,xjt}是S的一個(gè)子集。I(S)=I(xi1;xi2;…;xis)是指S中所有變量之間的交互作用信息，其中分號(hào)“;”用于表示交互作用信息。H(T)=H(xj1,xj2,…,xjt)是指T中所有變量的聯(lián)合信息熵，其中逗號(hào)“,”用于表示聯(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是源特征集合的一個(gè)特征子集，y是目標(biāo)變量；但是，子集的個(gè)數(shù)有指數(shù)多個(gè)，當(dāng)特征個(gè)數(shù)較多時(shí)，無(wú)法窮舉所有特征子集。基于信息論的方法通常使用低維的交互信息逼近高維的I(S,y)，比如：相關(guān)性I(xi;y)和冗余性I(xi;xj)。這些方法基于如下幾個(gè)假設(shè)[13]：

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

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

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

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

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

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是這些變量的異或。此時(shí)四階交互作用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 給定三個(gè)變量xi∈Sk，xk∈XSk和y，那么Sk中的各個(gè)特征獨(dú)立的影響這三個(gè)變量，即：

(5)

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

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

(6)

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

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

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

從而式(6)得證。

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

(7)

基于互信息的特征選擇方法的搜索策略通常為順序前向搜索(Sequential Forward Search， SFS)[16]。封裝式方法需要枚舉所有特征子集，而后向搜索需要從全集開(kāi)始逐個(gè)刪除N-k個(gè)特征。本文使用效率更高的SFS計(jì)算式(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

計(jì)算I(Tk;y)

fori=1 ton-s-1 do

計(jì)算I(Si;Tk;y)

forj=1 ton-sdo

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

end for

end for

用式(7)計(jì)算J(Tk)

end for

S=S∪z

T=Tz

end for

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

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

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

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

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

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

本文通過(guò)大量實(shí)驗(yàn)對(duì)比了Max-Interaction與其他特征選擇算法。該實(shí)驗(yàn)使用了6個(gè)廣泛使用的文本分類數(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所示。本文使用分類精度對(duì)比特征選擇方法。使用的分類器包括支持向量機(jī)(Support Vector Machine， SVM)、k近鄰(k- Nearest Neighbors，kNN)、決策樹(shù)(Decision Tree)和貝葉斯分類器(Na?ve Bayes)。這些分類器都有相應(yīng)的Matlab內(nèi)建函數(shù)。本文對(duì)比了1個(gè)考慮了三階交互作用的特征選擇方法IWFS[11]，以及4個(gè)文本分類中的特征選擇方法，包括MD、Chi- square、MI和DF[6]。所有的實(shí)驗(yàn)在Matlab/C++環(huán)境中實(shí)現(xiàn)。

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

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