曹守富,蔣慧平，譚 陽(yáng)

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

一、引言

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

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

二、粗糙集理論

決策系統(tǒng)DS也稱(chēng)為決策表，表示為DS=(U,A=C∪D,V,f)。DS將信息系統(tǒng)的屬性集A劃分為兩個(gè)集合，即條件屬性集C和決策屬性集D，即A=C∪D，C∩D≠?，D≠?。那么在決策系統(tǒng)DS=(U,C,D,V,f)中，對(duì)于U中任意兩個(gè)對(duì)象ui和uj，若在條件屬性子集P(P?C)上的取值相等，即?a∈P，a(ui)=a(uj)成立，則稱(chēng)對(duì)象ui、uj對(duì)于屬性集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)中，對(duì)于?P?C∪D，若U/P={P1,P2,…,Pm}且X?U，則稱(chēng)P-(X)=∪{Pi|Pj∈U/P,Pi?X}為X關(guān)于屬性集P的下近似集，稱(chēng)P-(X)=∪{Pi|Pj∈U/P,Pi∩X?≠?}為X關(guān)于屬性集P的上近似集。在DS中若U/D={D1,D2,…,Dk}為決策屬性D對(duì)U劃分形成的決策類(lèi)，對(duì)于P?C，若U/P={P1,P2,…,Pm}為條件屬性P對(duì)U劃分形成的條件類(lèi)，則POSp(D)稱(chēng)為條件屬性集P關(guān)于決策屬性集D的正區(qū)域。

(2)

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

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

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

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

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

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

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

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

(三)生成決策表

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

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

四、屬性排序及約簡(jiǎn)

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

圖1 特征選擇順序

(二)屬性約簡(jiǎn)

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

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

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

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

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

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

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

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

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

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

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

五、實(shí)驗(yàn)分析

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

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

圖2 不同閾值對(duì)分類(lèi)性能的影響

(一)屬性約簡(jiǎn)后的特征項(xiàng)分類(lèi)性能對(duì)比

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

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

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

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

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

(二)特征項(xiàng)數(shù)量不同時(shí)的分類(lèi)性能對(duì)比

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

圖3 樣本均勻情況下的分類(lèi)性能

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

圖4 樣本非均勻情況下的分類(lèi)性能

六、結(jié)語(yǔ)

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