基于粗糙集的社交文本特征選擇方法

曹守富,蔣慧平，譚 陽

(1.湖南廣播電視大學(xué)教育信息技術(shù)中心，長沙 410004；2.湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院網(wǎng)絡(luò)技術(shù)學(xué)院，長沙 410004)

一、引言

在社交文本的分類過程中，很多特征項對分類沒有意義，它們的存在一方面影響分類的速度，另一方面影響分類的效果。因此，在分類之前需要進(jìn)行特征選擇。常用的特征選擇方法有詞頻(TF)、文檔頻數(shù)(DF)、信息增益(IG)、互信息(MI)和卡方統(tǒng)計量(CHI)[1]等。已有研究表明，卡方統(tǒng)計量和信息增益是文本分類中效率較高的兩個特征選擇算法[2]。在此基礎(chǔ)上，學(xué)者們圍繞如何提高分類性能進(jìn)行探討：一是對期望交叉熵、互信息和信息增益三種特征選擇方法進(jìn)行比較，并提出了進(jìn)一步改進(jìn)的方法，經(jīng)實驗驗證，改進(jìn)的期望交叉熵能提高分類性能[3]；二是提出了基于互信息和粗糙集的融合特征選擇算法[4]；三是在信息增益方法中添加合適的比例因子，對信息增益進(jìn)行改進(jìn)，使其適應(yīng)樣本均勻和非均勻訓(xùn)練集[5]；四是考慮到社交文本內(nèi)容比較短，特征項較少，為了擴(kuò)展社交文本的特征，提出了一種微博特征提取方法[6]；五是提出了一種基于粗糙集與概率加權(quán)的特征選擇算法，通過計算依賴度結(jié)合特征項在微博中出現(xiàn)的概率來實現(xiàn)特征選取[7]；六是提出了基于WordNet語義特征選擇方法，通過WordNet減少和消除特征項的歧義[8]；七是提出利用粗糙集理論并采用約翰遜啟發(fā)式屬性約簡的方法來達(dá)到特征選擇的目的[9]。

上述的改進(jìn)方法各有優(yōu)點，在一定程度上解決了分類過程中特征選擇的問題，但不足之處是無法自動確定特征項的選擇數(shù)目，即選擇的特征項數(shù)目不能夠支持算法正確區(qū)分文本集中各條文本所屬分類。本研究在分析特征選擇常用方法的基礎(chǔ)上，提出一種基于粗糙集的社交文本特征選擇方法(RS)：利用方差衡量特征項的類間波動情況，波動越大表明其類別區(qū)分度越高，以此作為先驗知識對已有的決策表進(jìn)行約簡，獲取的屬性集即核心選擇特征項；使用核心選擇特征項可區(qū)分文本集中的文本，在此基礎(chǔ)上若適當(dāng)補(bǔ)充其他屬性，可達(dá)到更佳的特征選擇效果。

二、粗糙集理論

決策系統(tǒng)DS也稱為決策表，表示為DS=(U,A=C∪D,V,f)。DS將信息系統(tǒng)的屬性集A劃分為兩個集合，即條件屬性集C和決策屬性集D，即A=C∪D，C∩D≠?，D≠?。那么在決策系統(tǒng)DS=(U,C,D,V,f)中，對于U中任意兩個對象ui和uj，若在條件屬性子集P(P?C)上的取值相等，即?a∈P，a(ui)=a(uj)成立，則稱對象ui、uj對于屬性集P是不可區(qū)分的，表示為：

IND(P)={(ui,uj)|(ui,uj)∈U×U,?a∈P，

a(ui)=a(uj)}

(1)

在決策信息系統(tǒng)DS=(U,C,D,V,f)中，對于?P?C∪D，若U/P={P1,P2,…,Pm}且X?U，則稱P-(X)=∪{Pi|Pj∈U/P,Pi?X}為X關(guān)于屬性集P的下近似集，稱P-(X)=∪{Pi|Pj∈U/P,Pi∩X?≠?}為X關(guān)于屬性集P的上近似集。在DS中若U/D={D1,D2,…,Dk}為決策屬性D對U劃分形成的決策類，對于P?C，若U/P={P1,P2,…,Pm}為條件屬性P對U劃分形成的條件類，則POSp(D)稱為條件屬性集P關(guān)于決策屬性集D的正區(qū)域。

(2)

若在決策信息系統(tǒng)DS=(U,C,D,V,f)上存在兩個等價關(guān)系族C和D(C,D?DS)，對于?P∈C而言，如果P是C相對于D的獨立子集，并且POSp(D)=POSC(D)成立，則稱P為條件屬性集C相對于決策屬性集D的正區(qū)域模型下的知識約簡[10]。

三、構(gòu)建決策表

(一)計算屬性權(quán)重

社交文本的特性為文本長度較短，但總體的詞匯量較大，在不同的時間段會派生出許多新的詞匯，訓(xùn)練集中出現(xiàn)的詞匯一般遵循Zipf定律，即只有少數(shù)詞匯被經(jīng)常使用[11]。大量詞匯在訓(xùn)練集中出現(xiàn)的次數(shù)很少甚至只出現(xiàn)1次，這些詞匯被稱為稀有詞匯，它們對分類的特征選擇貢獻(xiàn)度很低。因此，在構(gòu)建決策表時，可以把每個特征項作為決策表中的一個屬性看待，計算得出的屬性權(quán)重即特征項權(quán)重。本研究在計算權(quán)重時，過濾了出現(xiàn)次數(shù)少于或等于3次的詞匯，過濾后再根據(jù)訓(xùn)練集D={d1,d2,…,dn}得到所有社交文本的特征項集合T={t1,t2,…,tm}，以每條文本在相應(yīng)特征項的取值計算該特征項的權(quán)重，計算權(quán)重采用TF- IDF權(quán)重計算方法。表1給出了兩條社交文本中部分特征項的權(quán)重值，可以看出：“Mobile”類別中編號為“1141”的社交文本包含了“魅族”“諾基亞”這兩種類別區(qū)分度較高的特征項，其權(quán)重值相對較大；而特征項“微博”“轉(zhuǎn)發(fā)”這兩種類別區(qū)分度較低的特征項，其權(quán)重值相對較小。

表1 部分特征項權(quán)重比較

(二)對屬性值作離散化處理

在向量空間模型中計算得到的每個屬性權(quán)重值是連續(xù)的，約簡之前需要進(jìn)行離散化處理。本研究采用等距離劃分的數(shù)據(jù)離散化方法，每個特征項的權(quán)重值按等距離劃分為2個區(qū)。表2顯示了對關(guān)于“手機(jī)”“籃球賽”的部分特征項權(quán)重作離散化處理的結(jié)果。

表2 部分特征項權(quán)重的離散化處理結(jié)果

(三)生成決策表

訓(xùn)練集中的每個對象要表示成粗糙集能夠處理的決策表形式，在此使用向量空間模型來表示社交文本信息。將整個訓(xùn)練集作為論域，以訓(xùn)練集中的每一條文本為論域中的對象，每個對象包含的特征項為條件屬性，經(jīng)過離散化處理的特征項權(quán)重值為條件屬性值，其所屬類別為決策屬性，以此構(gòu)建決策表。如果某些特征項在一條社交文本中沒有出現(xiàn)，則將其對應(yīng)的屬性值設(shè)置為0。構(gòu)建的決策表形式如表3，其中特征項是條件屬性，類別是決策屬性。

表3 離散化處理后的決策表

四、屬性排序及約簡

(一)條件屬性排序及歸類

在對決策表進(jìn)行屬性約簡時，要不斷向條件屬性子集按照特定順序加入新的屬性，然后判斷新的條件屬性子集是否為一個約簡。這就需要對屬性進(jìn)行排序，然后將每個屬性劃分到相關(guān)的一個或多個類別中。本研究用方差衡量屬性(特征項)在各類別之間的波動，波動越大，則該類別的區(qū)分度越高。具體算法如下：

輸入：未離散化的決策表DS=(U,C,D,V,f)。

輸出：已排序和歸類的屬性類別關(guān)系矩陣。

第一步：在未作離散化處理的決策表中，按類別分組，計算每個分組中每一列的和，即某個屬性在該類別中的權(quán)重值之和，這樣每個類別最終都會對應(yīng)一個向量v=(∑Wi1,∑Wi2,…,∑Wij,…,∑Win),其中∑Wij為類別i中屬性j的權(quán)重值之和。

第二步：將上一步每個類別對應(yīng)的向量v組成一個矩陣M，m個類別n個屬性對應(yīng)的矩陣為M。

(3)

第三步：計算矩陣M每一列的方差，將它們組合成一個向量q=(σ1，σ2，…，σn)，q中分量σj反映了屬性j在類間分布的波動情況。

第四步：將q中的分量值從大到小進(jìn)行排序，形成一個新的向量q′，同時調(diào)整屬性的排列順序，矩陣M中的各列也根據(jù)q中分量的排序情況進(jìn)行調(diào)整，形成新的矩陣M′。

第五步：將各屬性劃分到各個類別中。對屬性j劃分的方法為：計算M′中第j列的最大值max∑Wij，其中1≤i≤m，最大值對應(yīng)的類別即為該屬性對應(yīng)的類別；然后計算∑Wkj/max∑Wij，其中1≤k,i≤m,k≠i,，即該列的其他分量與最大值的比值；設(shè)置一個閾值β，當(dāng)∑Wkj/max∑Wij≥β時，將該屬性劃分到max∑Wij對應(yīng)的類別。

第六步：輸出已排序和歸類的屬性類別關(guān)系矩陣P。

(4)

每一行是劃分到某一類的屬性，值得注意的是，各類別所包含的屬性數(shù)量可能不同，并且一個屬性可能同時屬于多個類別。在選擇屬性時，按列的方向從上到下、從左到右依次選擇，當(dāng)遇到已選擇的屬性時跳過當(dāng)前屬性，選擇下一個，詳情見圖1。采用這種選擇策略是為了保證各個類別所包含的特征項數(shù)量均等，避免和減少因特征項不平衡而導(dǎo)致分類器有所偏好。

圖1 特征選擇順序

(二)屬性約簡

決策表屬性約簡一般采用啟發(fā)式的約簡方法得到一個最優(yōu)或次優(yōu)的約簡，如基于屬性重要度的屬性約簡算法[12]，或基于區(qū)分矩陣的屬性約簡算法[13]，這些方法需要計算核屬性。由于本研究根據(jù)社交文本信息生成的決策表屬性數(shù)目多且屬性值分布稀疏，采用核屬性計算方法得到的結(jié)果經(jīng)常是空集。因此，在初始屬性選擇方法上采用前文所述方法，按順序選取少量屬性作為約簡的初始條件屬性集，記為S，以排序后的向量q′中的分量值作為啟發(fā)信息來實現(xiàn)約簡。屬性約簡的具體算法如下：

輸入：決策表DS=(U,C,D,V,f)。

輸出：條件屬性集C相對S的一個約簡及新的屬性類別關(guān)系矩陣P′。

第一步：從屬性類別關(guān)系矩陣P中選擇m個條件屬性組成初始條件屬性集S，記錄初始條件屬性集最后一個屬性在P中的位置Pos，令R=S，Posend是P中最后一個元素的位置。

第二步：若POSR(D)=POSC(D)，則轉(zhuǎn)到第七步，否則令T=S。

第三步：設(shè)置Pos=Pos+1。

第四步：在矩陣P中從Pos至Posend，按屬性選擇順序依次選取屬性c，如果c在T中存在，則跳過當(dāng)前屬性選擇下一個，否則將c加入到T中，直到POST(D)=POSC(D)，記錄c此時所在的位置Posc,并設(shè)置Posend=Posc。

第五步：設(shè)置R=R∪{C}，T=R，調(diào)整c在矩陣P中的位置，將其插入到Pos位置處，該位置對應(yīng)行的后面元素依次向后移動。

第六步：如果Posend=Pos，表明找到了一個包含屬性較少的約簡結(jié)果，此時屬性類別關(guān)系矩陣已經(jīng)發(fā)生變化，新的屬性類別關(guān)系矩陣記為P′，轉(zhuǎn)到第七步。若Posend≠Pos，則轉(zhuǎn)到第三步。

第七步：輸出約簡結(jié)果R及屬性類別關(guān)系矩陣P′，算法結(jié)束。

R中包含的屬性是能夠區(qū)分訓(xùn)練集中所有樣本的一個較小屬性集，我們在選擇特征時應(yīng)該包含這些特征項。在特征選擇時，選擇的特征項數(shù)目應(yīng)該大于或等于|R|，即大于或等于約簡后的屬性數(shù)，這樣就保證了選擇的特征中包含正確分類的特征項。

五、實驗分析

為了能夠明確RS方法的性能，本研究選取詞頻數(shù)(TF)方法、文檔頻數(shù)(DF)方法、互信息(MI)方法及卡方統(tǒng)計量(CHI)方法進(jìn)行比較。實驗在同一環(huán)境下進(jìn)行，對5種方法用Java語言進(jìn)行重寫，分類方法采用樸素貝葉斯分類方法。實驗數(shù)據(jù)集來源于新浪微博中63641個用戶的真實數(shù)據(jù)集[14]。為了有效提取文本特征，避免數(shù)據(jù)過于分散，我們從63641個用戶中分類提取了5類數(shù)據(jù)，分別為：手機(jī)類、足球賽類、籃球賽類、電視劇類和房地產(chǎn)類。通過基本的數(shù)據(jù)清理，一共篩選出長度在14個字符以上的有效數(shù)據(jù)6000條，并由人工分別對其進(jìn)行類別標(biāo)注。其中，均勻訓(xùn)練集中每個類別700個數(shù)據(jù)，共3500個訓(xùn)練樣本；非均勻訓(xùn)練集中各類樣本數(shù)量分別為900、600、1200、300、600，共3600個訓(xùn)練樣本。實驗環(huán)境為：Core i5 3.3GHz的CPU和8GB的RAM。

比較采用查全率r、準(zhǔn)確率p、F1值作為性能評價指標(biāo)。準(zhǔn)確率(查準(zhǔn)率)是針對預(yù)測結(jié)果而言的，表示當(dāng)預(yù)測為正的樣本中真正的正樣所占的比率。查全率(召回率)是針對原來的樣本而言的，表示樣本中的正例被預(yù)測正確的比率。F1值為綜合評價指標(biāo)，F(xiàn)1=2pr/(p+r)。另外，屬性歸類時需要確定閾值β，本研究針對β的不同取值對算法性能的影響進(jìn)行了對比實驗。實驗結(jié)果表明，當(dāng)取值為0.65時分類算法取得了較好的性能，因此在后續(xù)的實驗過程將β設(shè)置為0.65，詳見圖2。

圖2 不同閾值對分類性能的影響

(一)屬性約簡后的特征項分類性能對比

經(jīng)過清除稀有詞匯，均勻訓(xùn)練集中有3353個特征項，通過屬性約簡取130個特征項。對于5種方法分別獨立運行20次，得到其在均勻數(shù)據(jù)集上特征選擇的平均值。表4中列出了5種方法在均勻訓(xùn)練集上的特征選擇情況，通過屬性約簡大幅降低了數(shù)據(jù)向量空間的維度。可以看出，RS方法在查全率和準(zhǔn)確率上均優(yōu)于其他方法，表現(xiàn)出更好的文本分類性能。

表4 5種特征選擇方法在均勻訓(xùn)練集上的性能比較

為了進(jìn)一步驗證RS方法的性能，還可以采用非均勻訓(xùn)練集進(jìn)行對比測試。非均勻訓(xùn)練集中共有3890個特征項，經(jīng)過清理和約簡，保留了112個特征項。表5中列出了5種方法在非均勻訓(xùn)練集上的特征選擇情況。

表5 5種特征選擇方法在非均勻訓(xùn)練集上的性能比較

從表4和表5可以看出，跟其他4種方法相比，RS方法具有比較優(yōu)勢。在樣本均勻情況下的分類性能普遍高于非均勻情況下的分類性能，其原因在于在樣本非均勻情況下選擇相同數(shù)量的特征項，由于樣本數(shù)的差距，每個類別的特征項分類能力會有所差異。

(二)特征項數(shù)量不同時的分類性能對比

用實驗驗證在不同數(shù)量特征項情況下5種特征選擇方法的分類性能，圖3是在樣本均勻情況下不同方法的分類性能(F1值)對比?？梢钥闯?，當(dāng)特征項數(shù)量在400～500范圍內(nèi)時，所有特征選擇算法均達(dá)到了自身性能的最佳狀態(tài)，但RS方法的分類性能均優(yōu)于其他對比方法，雖然在特征項數(shù)量大于700后性能有所下降，但仍然優(yōu)于其他對比方法，表現(xiàn)出更好的魯棒性。

圖3 樣本均勻情況下的分類性能

圖4是樣本非均勻情況下分類性能(F1值)的對比情況?？梢钥闯?，RS方法在特征項較少(小于800)時分類性能高于其他方法，這是因為該方法選擇的特征項至少能夠保證正確地對訓(xùn)練樣本集進(jìn)行分類，而其他方法不能保證。當(dāng)特征項數(shù)量達(dá)到一定規(guī)模(1200～1600)后，分類性能最佳，如果繼續(xù)增加特征項數(shù)量，分類性能反而下降，這是因為過多的特征項中會包含無意義的、有噪聲的特征項。

圖4 樣本非均勻情況下的分類性能

六、結(jié)語

本研究利用方差衡量特征項的類間波動情況，波動越大表明其類別區(qū)分度越高。將特征項按方差大小進(jìn)行排序，然后將其均勻地分配到各個類別中，形成一個特征項類別關(guān)系矩陣P。對屬性進(jìn)行約簡時，需要選擇初始屬性，從P矩陣中按照指定順序選取少量屬性作為初始屬性，然后按屬性的波動大小作為啟發(fā)信息，不斷加入新屬性尋找一個約簡結(jié)果，直到初始屬性集穩(wěn)定。實驗結(jié)果表明，該方法可以大幅度減少特征項數(shù)量并能保持較好的分類效果。當(dāng)特征項數(shù)量在約簡結(jié)果的基礎(chǔ)上適當(dāng)增大時，本方法的分類性能同樣優(yōu)于常用的4種特征選擇方法。