Web文檔分類中TFIDF特征選擇算法的改進(jìn)

段國侖，謝 鈞，郭蕾蕾，王曉瑩

(1.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007；2.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展以及大規(guī)模應(yīng)用，網(wǎng)絡(luò)上的信息資源正以指數(shù)級爆炸式增長。Web已經(jīng)成為一個巨大的資源海洋。如何管理這些海量信息是一個值得研究的問題。通過Web文檔分類[1]手段能夠有效解決這一問題，因此很多學(xué)者在不斷努力尋求較好的分類技術(shù)。在Web文檔分類中，文本信息是最重要的分類信息。分類之前通常將文本表示為向量空間模型(vector space model)，但這種表示方法會使得文本向量維數(shù)很高。這帶來了較大的特征空間和冗余信息，從而影響文本分類的效率和準(zhǔn)確率。

特征選擇是通過某種方式或算法選擇出有益于分類的特征，去除那些無關(guān)或者關(guān)聯(lián)性不強(qiáng)的特征，從而構(gòu)造出更快，消耗更低的預(yù)測模型。

特征選擇是文本分類中的關(guān)鍵環(huán)節(jié)[2-3]。目前已有很多種特征選擇算法用于文本分類，能夠較好地解決特征高維性帶來的問題，但是針對這些方法仍然有很多需要改進(jìn)的地方。

1 相關(guān)工作

1.1 向量空間模型

文本向量空間模型是為了將每一個文本表示為向量空間中的一個向量，將每一個不同的特征對應(yīng)為向量空間中的一個維度，而每一維的值就是對應(yīng)的特征項(xiàng)在文本中的特征值[4]。向量空間模型中，文檔d表示為：V(d)=((t1,a1),(t2,a2),…,(tn,an))。其中ti為文檔d中的特征項(xiàng)，ai為ti的特征值，一般取為詞頻的函數(shù)。有了這樣的表示以后，就可以用分類器對樣本分類。

1.2 特征選擇

特征選擇[5]的方式有多種，如過濾式、包裹式、嵌入式等。過濾式獨(dú)立于后續(xù)要使用的模型，只針對數(shù)據(jù)本身而進(jìn)行選擇特征，從而將特征子集用于分類。由于Web文檔分類維數(shù)較高，所以使用過濾式方法可以有效減少特征選擇所用時間。文本特征選擇，主要是根據(jù)某種準(zhǔn)則從原始特征中選擇部分最有區(qū)分類別能力的特征詞。

目前，國內(nèi)外常用的文本特征選擇方法主要有以下幾種：詞頻、TFIDF[6]、卡方統(tǒng)計(jì)量[7-9]、互信息[10-11]、信息增益[12-13]等，也可以通過遺傳算法以及特征相關(guān)性等來進(jìn)行選擇[14]。

1.3 TFIDF特征選擇算法

如果某個特征詞在文檔中出現(xiàn)的頻率高，并且集中出現(xiàn)在少量文檔之中，則認(rèn)為該特征詞具有很好的類別區(qū)分能力，適合用來分類。這就是TFIDF特征選擇算法的主要思想[15]。TFIDF是比較常用的特征選擇算法，因?yàn)樗子趯⒛切┰~頻較高又不在大量文章中出現(xiàn)的詞項(xiàng)選出，而且計(jì)算復(fù)雜度不高，易于實(shí)現(xiàn)。

計(jì)算出特征項(xiàng)t的TFIDF的值，然后根據(jù)其值來進(jìn)行特征選擇。其計(jì)算公式如下：

TFIDF(t)=TF(t)*IDF(t)

(1)

其中，TF(t)表示特征項(xiàng)t在文檔中出現(xiàn)的詞頻數(shù)；IDF(t)表示特征項(xiàng)t的逆文檔頻率數(shù)。

下面以一個較為簡單的例子對TFIDF算法進(jìn)行分析。假設(shè)有三個類C1、C2、C3，每個類包含3篇文檔，特征詞集合中有t1、t2、t3，分布情況如表1所示。

對于TFIDF的計(jì)算公式中詞頻計(jì)算方式有很多種，列舉如表2所示。

表2 TF的計(jì)算方式

其中，ft為特征t在文檔中出現(xiàn)的頻數(shù)；maxft′為在文檔中出現(xiàn)次數(shù)最多的特征t'對應(yīng)的頻數(shù)；K取值范圍為(0,1)。

對于TFIDF的計(jì)算公式中逆文檔頻率的計(jì)算方式也有很多種，列舉如表3所示。

表3 IDF的計(jì)算方式

其中，nt為出現(xiàn)特征t的文檔頻數(shù)；N為文檔總個數(shù)；maxnt′為文檔頻數(shù)最多的特征t'對應(yīng)的文檔頻數(shù)值。

通過表2和表3中的表達(dá)式，TFIDF的計(jì)算方法可以通過多種組合方式得到，如：

(2)

其中，ft表示特征t在文檔中出現(xiàn)的詞頻數(shù)；nt表示包含特征t的文檔個數(shù)；N表示文檔總數(shù)。

從表1的分布中可以分析得到：t1有益于C1的分類，t2的作用明顯沒有t1大，t3對于分類毫無意義。三個特征的權(quán)重大小應(yīng)該為：

w(t1)>w(t2)?w(t3)

而通過式2計(jì)算t1、t2和t3的權(quán)重值為：

w(t1)=3.17=w(t2)=3.17>w(t3)=1.31

可以看出算法并沒有十分突出分類能力的差異性，而且對于t3這種無助于分類的特征依然獲得較大權(quán)重。所以，這樣的結(jié)果并不能選出較好的特征。因此需要對權(quán)重值的計(jì)算進(jìn)行調(diào)整。

2 TFIDF特征選擇算法的改進(jìn)

TFIDF用于特征選擇具有一定的區(qū)分能力，但同時也存在不足之處。因此，很多研究人員對其進(jìn)行了改進(jìn)，如文獻(xiàn)[16-17]使用了信息熵進(jìn)行改進(jìn)，文獻(xiàn)[18-19]使用了類間散度和類內(nèi)信息熵，Chen等將其改為TF-IGF[20]等。根據(jù)以上分析，以及參考前人研究成果，文中分析總結(jié)了TFIDF特征選擇算法的兩個缺點(diǎn)：

(1)沒有考慮特征項(xiàng)在類間及類內(nèi)的分布情況。集中出現(xiàn)在某個類別，而且在這一類中能夠大量出現(xiàn)，在其他類中出現(xiàn)相對較少，這樣的特征具有較好的分類能力。這些特征本應(yīng)被選出，但是其IDF值可能并不高，通過TFIDF難以被選擇出來。

(2)有的類別文檔數(shù)較多，有的類別卻很少，數(shù)據(jù)集不均衡是十分常見的問題。TFIDF并沒有將類別考慮在內(nèi)，這就使得選擇出的特征詞偏向于大類，而針對數(shù)據(jù)集較小的類的分類特征較少。

針對TFIDF的以上缺點(diǎn)，文中對該算法進(jìn)行改進(jìn)，不再使用IDF，而是使用了類內(nèi)分布因子(α)以及類間分布因子(β)。

W(t)=TF(t)×α(t)×β(t)

(3)

式3考慮了詞頻、類內(nèi)分布、類間分布以及數(shù)據(jù)集不均衡。特征權(quán)重值不依賴于類別，因此這是一個全局特征選擇算法。

詞頻(term frequency，TF)反映的是特征項(xiàng)t在文檔中出現(xiàn)的次數(shù)，詞頻高的有價值。這里選用的詞頻計(jì)算公式如下:

(4)

其中，maxft′為在文檔中出現(xiàn)次數(shù)最多的特征t'對應(yīng)的頻數(shù)值。通過計(jì)算式4，詞頻較高的值較大，同時也將原來的詞頻選擇作用弱化，并將值歸一化。

類內(nèi)分布因子(α)反映的是特征項(xiàng)t在所有類中分布最廣的那一類的分布情況，其值越大表示該特征項(xiàng)在某類中的分布越廣。計(jì)算公式如下：

α(t)=max(X1,···,Xi,···,Xk)

(5)

類間分布因子(β)反映的是特征項(xiàng)t在各類之間的分散程度，值越大說明特征越集中在某一類或幾類當(dāng)中，特征項(xiàng)越有價值。計(jì)算公式如下：

(6)

其中

(7)

希望選擇的特征在各類之間分布差異越大越好。因?yàn)榇嬖诓町愋缘奶卣鞑攀怯幸嬗诜诸惖奶卣?，β就是?jù)此來定義的。這里考慮了數(shù)據(jù)集不均衡問題：在計(jì)算各類分布時，使用的是在各類中所占比重的因式。文獻(xiàn)[18]提出過類似作用的因子，但沒有考慮各類包含文檔數(shù)的差異性。對于不均衡的數(shù)據(jù)集，只考慮各類之間包含特征t文檔數(shù)的差異性顯然沒有意義。

上文已經(jīng)對表1進(jìn)行了分析，通過TFIDF算法計(jì)算得到的權(quán)重值并不能很好地代表各個特征對于分類的重要性。而通過式3計(jì)算t1、t2和t3的權(quán)重值為：

w(t1)=0.22>w(t2)=0.11>w(t3)=0

可以看出，改進(jìn)方法算出的權(quán)重值可以將特征的類別區(qū)分能力較好地表現(xiàn)出來。文中將通過實(shí)驗(yàn)來驗(yàn)證改進(jìn)方法的有效性。

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

實(shí)驗(yàn)在Anaconda環(huán)境下調(diào)用sklearn、matplotlib、numpy、math、re等模塊實(shí)現(xiàn)，所有的實(shí)驗(yàn)結(jié)果均是在一臺2.50 GHz Intel Core(TM) i7-4710MQ處理器，8 Gbytes內(nèi)存的筆記本電腦上測試獲得。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證該方法的有效性，分別針對兩個語料庫進(jìn)行分類實(shí)驗(yàn)，包括搜狗中文語料庫以及從鳳凰網(wǎng)和新浪網(wǎng)上爬取數(shù)據(jù)自建的語料庫。

搜狗中文語料庫是由搜狗實(shí)驗(yàn)室提供，這里選擇了C000008財(cái)經(jīng)(300篇)、C000010 IT(200篇)、C000013健康(100篇)、C000014體育(47篇)、C000016旅游(340篇)、C000020教育(350篇)、C000022招聘(350篇)、C000023文化(1 000篇)、C000024軍事(500篇)。

自建語料庫主要是通過python編程從鳳凰網(wǎng)和新浪網(wǎng)爬取得到，其中包括文化(487篇)、娛樂(1 182篇)、財(cái)經(jīng)(934篇)、健康(1 097篇)、歷史(269篇)、軍事(797篇)、體育(943篇)、科技(905篇)以及社會(897篇)。

選用的數(shù)據(jù)集類別較多但樣本不多，同時也存在著數(shù)據(jù)集不均衡現(xiàn)象。

3.2 評價指標(biāo)

分類模型評估指標(biāo)有準(zhǔn)確率p、召回率r和F度量值[21]。

(8)

(9)

(10)

其中，a表示實(shí)際屬于該類并預(yù)測正確的個數(shù);b表示實(shí)際不屬于該類并預(yù)測正確的個數(shù);c表示實(shí)際屬于該類但預(yù)測錯誤的個數(shù)。

通常希望分類結(jié)果中準(zhǔn)確率和召回率都要高，而且同等重要。文中使用的是β=1的F1度量值，即：

3.3 分類器

選用的分類器是支持向量機(jī)(support vector machine，SVM)。SVM是一種在缺乏先驗(yàn)知識的條件下，以最小化結(jié)構(gòu)風(fēng)險為目標(biāo)，對有限樣本進(jìn)行學(xué)習(xí)的機(jī)器學(xué)習(xí)方法。支持向量機(jī)的基本思想是尋找一個最優(yōu)超平面或最優(yōu)超曲面，使得不同類樣本之間的間距達(dá)到最大[22]。

支持向量機(jī)是目前文本分類中使用較多的分類器。支持向量機(jī)擅長解決小樣本、高維度的分類問題，而文本分類就是一個高維度的分類問題，所以支持向量機(jī)相對較優(yōu)。

文中實(shí)驗(yàn)選用的是python工具包svm.SVC的線性分類器，損失函數(shù)選用squared hinge loss，使用L2正則化，二類向多類的推廣采用的是“一對多”的方式。

3.4 實(shí)驗(yàn)結(jié)果

對選用的兩個語料庫，分別使用TFIDF以及改進(jìn)后的TFIDF特征選擇算法。通過計(jì)算得到各個特征詞的權(quán)重值，將權(quán)重值排序建立有序特征字典，然后根據(jù)字典選取topN個特征。在建立文本的向量空間模型時，特征對應(yīng)的特征值是由TFIDF計(jì)算得到。于是，可將一個文檔轉(zhuǎn)化為一個N維向量。這里需要說明的是，實(shí)驗(yàn)中選用的特征是根據(jù)不同的特征選擇算法計(jì)算出的權(quán)重值決定，即全部特征的子集，而向量空間模型中的特征值在文中均是使用其TFIDF值，當(dāng)然也可以通過其他方式計(jì)算得到。也就是說權(quán)重值用于特征選擇，而特征值是用于分類。

實(shí)驗(yàn)中，按照2∶1的比例將語料庫分為訓(xùn)練集和測試集。針對訓(xùn)練集采用三次三折交叉驗(yàn)證方法確定分類器參數(shù)。最后在測試集上進(jìn)行測試，計(jì)算分類的準(zhǔn)確率、召回率以及F1度量，并對不同特征選擇后的分類結(jié)果進(jìn)行比較。實(shí)驗(yàn)流程如圖1所示。

圖1 文本分類實(shí)驗(yàn)流程

使用兩種特征選擇算法在兩個語料庫中的實(shí)驗(yàn)對比結(jié)果如圖2和圖3所示。圖中清晰顯示了在選取不同的特征維數(shù)時分類F1度量值的對比結(jié)果。

圖2 采用搜狗語料庫的F1度量值

圖3 采用自建語料庫的F1度量值

實(shí)驗(yàn)結(jié)果表明：使用改進(jìn)后的特征選擇算法，在較少的特征維數(shù)下，與傳統(tǒng)的TFIIDF算法相比能有效提升分類效果。表明提出的算法更加有效，同時也表明特征的重要性與其在類間與類內(nèi)的分布關(guān)系密切。

4 結(jié)束語

針對傳統(tǒng)的TFIDF特征選擇算法，主要是針對逆文檔頻率的計(jì)算中沒有考慮特征項(xiàng)類內(nèi)分布、類間分布以及數(shù)據(jù)集不均衡狀況，提出了一種改進(jìn)方法。通過結(jié)合詞頻、類內(nèi)分布因子以及類間分布因子，計(jì)算各個特征的權(quán)重值，并選擇數(shù)值較高的特征項(xiàng)作為分類特征。通過實(shí)驗(yàn)與傳統(tǒng)TFIDF算法進(jìn)行了對比。實(shí)驗(yàn)中將兩種特征選擇算法分別應(yīng)用于搜狗中文語料庫以及自建語料庫，采用支持向量機(jī)作為分類器。最后在測試集上進(jìn)行測試，得到分類的F1度量值。對比結(jié)果表明，改進(jìn)算法確實(shí)對Web文檔分類效果有了一定的提升。