駱魁永

(信陽農(nóng)林學(xué)院 信息工程學(xué)院，河南 信陽 464000)

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)中各種文本信息以指數(shù)級的速度增長，文本分類[1,2]在信息檢索、內(nèi)容信息過濾、自然語言處理和信息組織與管理等領(lǐng)域應(yīng)用越來越廣泛.然而，在對海量電子文檔的分類中，發(fā)現(xiàn)數(shù)據(jù)不均衡分布的情況普遍存在，在數(shù)據(jù)集中不同類別之間的文本數(shù)量可能存在數(shù)量級的差距，這給文本分類帶來了新的挑戰(zhàn).面對這樣的情況，特征選擇作為文本分類的重要環(huán)節(jié)，傳統(tǒng)的χ2特征選擇方法在特征項選擇的過程中往往會出現(xiàn)類別傾向的問題，導(dǎo)致分類器對稀有類別不能產(chǎn)生較好的分類效果.

目前，一些學(xué)者指出了χ2統(tǒng)計模型存在的缺點，并提出了相應(yīng)的改進模型.文獻[3]指出負相關(guān)特征項也會包含分類價值，正負相關(guān)特征項需要區(qū)別對待，通過對正負相關(guān)特征項賦予不同權(quán)重，改進了χ2統(tǒng)計模型；針對特征項在類間與類內(nèi)分布的差異性對χ2統(tǒng)計模型的影響；文獻[4]結(jié)合信息增益與文本頻率方法的優(yōu)點，提出了一種組合型模型，提高了χ2統(tǒng)計模型的性能；針對與類別正負相關(guān)的特征項對χ2統(tǒng)計模型的影響；文獻[5]定義了頻度、集中度和分散度的概念，并以此作為特征項的權(quán)重應(yīng)用到新的模型中，使得改進后的模型傾向于選擇高頻、集中度高和分散度低的特征項；文獻[6]提出了特征項與類別正負相關(guān)性的概念，并剔除與類別負相關(guān)的特征項，從而達到χ2統(tǒng)計模型的優(yōu)化；文獻[7]在χ2統(tǒng)計模型的基礎(chǔ)上添加了三個調(diào)節(jié)參數(shù)，以此度量特征項對特定類別的分類價值，提出了一種基于方差的χ2統(tǒng)計模型.然而上述所有方法都沒有考慮在不均衡數(shù)據(jù)集的類別間文檔頻數(shù)的差異性，針對上述存在的問題和不均衡數(shù)據(jù)集傾斜的特點，本文引入了類內(nèi)詞頻概率因子、類間文檔概率集中因子和類內(nèi)均勻因子，對傳統(tǒng)卡方統(tǒng)計模型進行改進，提出了一種改進的CHI特征選擇方法，通過在復(fù)旦大學(xué)計算機信息與技術(shù)系整理的語料庫中進行實驗，實驗結(jié)果表明該特征選擇方法在不均衡數(shù)據(jù)集上分類效果比傳統(tǒng)CHI要好，特別是在小類別中分類效果有明顯的提高.

1 CHI特征選擇算法及相關(guān)研究

1.1 CHI特征選擇算法

χ2統(tǒng)計量可以用來度量特征tk和文檔類別Ci之間的相關(guān)程度；假設(shè)特征tk(k=1,2,…,n)和文檔類別Ci之間符合具有一階自由度的χ2分布.假定訓(xùn)練文本集為S，其中有M個類別C1,C2,…Ci,…CM，S的總文檔數(shù)為N，那么特征tk與類別Ci之間χ2統(tǒng)計量可以表示如式(1)所示.

(1)

式(1)中:A表示在類別Ci中且包含有特征項tk的文檔數(shù)；B表示不在類別Ci中但包含有特征項tk的文檔數(shù)；C表示在類別Ci但是不包含有特征項tk的文檔數(shù)；D表示既不在類別Ci也不包含有特征項tk的文檔數(shù)；N表示語料集中的樣本總數(shù).

對于全局特征選擇，先按式(1)計算tk與每個類別Ci的χ2值，然后根據(jù)式(2)或式(3)計算特征tk對整個訓(xùn)練文本集的χ2統(tǒng)計值.最后根據(jù)χ2統(tǒng)計值的大小進行排序，在候選特征集中選擇指定數(shù)目的特征項作為特征集.

(2)

(3)

特征項tk與類別Ci的相關(guān)性越強，χ2(tk,Ci)的值就越大，此時特征項tk對類別Ci來說，分類價值越多.

1.2 相關(guān)改進算法描述

Yang[8]在研究中指出，χ2統(tǒng)計特征選擇算法是當前針對中文文本分類性能最好的特征選擇算法之一，但算法依然存在很多不足.首先，一個有分類價值的特征詞，應(yīng)該在指定類各文檔中均勻地出現(xiàn)，若只集中出現(xiàn)在該類的個別文檔中，而在其他文檔中很少出現(xiàn)，則對該類別來說，該特征項具有的類別鑒別信息要少很多；其次，χ2統(tǒng)計模型很容易把對特定類別貢獻低而對其他類別貢獻高的特征項選擇出來；最后，傳統(tǒng)χ2統(tǒng)計模型只考慮了特征項在所有文檔中出現(xiàn)的次數(shù)，并不考慮特征項在某一文檔中出現(xiàn)的次數(shù)，存在傾向低頻詞的缺點.

針對以上的問題，文獻[7]，在χ2模型的基礎(chǔ)上引入3個調(diào)節(jié)參數(shù)作為特征項的影響權(quán)重，提出了一種基于方差的χ2特征選擇方法.公式表示如式(4)所示：

(4)

文獻[6]針對χ2統(tǒng)計特征選擇算法對類別負相關(guān)和正相關(guān)的特征項平等對待的問題，對傳統(tǒng)χ2統(tǒng)計方法做了一定的改進，將那些與類別表現(xiàn)負相關(guān)的特征項剔除，從而忽略了與類別負相關(guān)對χ2統(tǒng)計模型的影響，改進后的模型表示如式(5)：

(5)

文獻[3]指出僅考慮特征項與類別的正相關(guān)性，完全忽略與類別表現(xiàn)為負相關(guān)的特征項具有一定不合理性，對于小類來說，與類別負相關(guān)的特征項依然含有一定的鑒別信息.因此文獻[9,10]在χ2模型的基礎(chǔ)上，加入了傾向因子α，改進后模型如式(6)所示：

(6)

2 改進的CHI特征選擇算法

2.1 加入類內(nèi)詞頻概率因子

χ2統(tǒng)計模型只考慮了特征項在所有文檔出現(xiàn)的次數(shù)，而沒有考慮特征項在指定類中出現(xiàn)的次數(shù).即χ2統(tǒng)計模型只考慮了特征項的文檔頻數(shù)，沒有考慮特征項在指定類中的詞頻，從而放大了低頻詞對指定類別的分類價值.

基于客觀事實，一個有分類價值的特征詞，應(yīng)該在指定類文檔中出現(xiàn)的次數(shù)較多.因此文獻[7]將特征項在指定類中各文檔出現(xiàn)的總次數(shù)作為χ2統(tǒng)計模型的調(diào)節(jié)參數(shù)，其中調(diào)節(jié)參數(shù)α如式(7)：

α(tk,Ci)=tf(tk,Ci)

(7)

但是在不均衡數(shù)據(jù)集中，由于各類別之間文檔頻數(shù)差異比較大，單純的以詞頻來度量特征項的頻繁程度，算法往往會更傾向于選擇大類的特征項，這對稀有類別是不公平的，降低了稀有類別的分類效果.

例如：假設(shè)在一個小類別Cp有200篇文檔，特征詞ts在類別Cs中出現(xiàn)的總次數(shù)為50；而在另一個大類別Cq中有1000篇文檔，特征詞tt在類別Cq中出現(xiàn)的總次數(shù)為100，那么明顯α(tk,Cp)<α(tk,Cq)，但是實際上，特征詞ts對于類別Cp的重要性是高于特征詞tt對于類別Cq的重要性的，導(dǎo)致模型傾向于選擇對大類有分類價值的特征項，減少了對稀有類別有分類價值的特征項，從而降低了小類別分類的準確性.

為了避免對大類的特征項的這種選擇傾向性，本文以類內(nèi)的特征項在文檔中概率信息來度量特征項在不平衡數(shù)據(jù)集的頻繁程度，引入了類內(nèi)詞頻概率因子αnew，表示如式(8)所示：

(8)

類內(nèi)詞頻概率因子αnew(tk,Ci)表示在類別Ci中特征項tk的詞頻概率，度量了在不平衡數(shù)據(jù)集下特征項tk在類別Ci出現(xiàn)的頻繁程度.αnew(tk,Ci)值越大，表示該特征項在該類中出現(xiàn)的頻率較高，表明該特征項對該類具有強類別區(qū)分能力；αnew(tk,Ci)值越低，表示該特征項在該類中出現(xiàn)的頻率較低，表明該特征項對該類具有弱類別區(qū)分能力.

2.2 加入類間文檔概率集中因子

χ2統(tǒng)計模型是一種雙邊準則的特征選擇模型，即該模型沒有區(qū)分與類別正負相關(guān)的特征項對指定類別的重要程度，使得選擇出來的特征項對特定類別貢獻低而對其他類別貢獻高[3].一個有分類價值的特征項，應(yīng)該在指定類文檔中出現(xiàn)的次數(shù)較多，在其他類文檔中出現(xiàn)次數(shù)較少.文獻[7]以文檔頻數(shù)為基礎(chǔ)，根據(jù)方差的思想度量了特征項在類間的集中程度，并引入了參數(shù)β，其中β如式(9)所示.

(9)

分析式(9)可知，與類別負相關(guān)的特征項，其β(tk,Ci)值為負值，在模型選擇中會被忽略，從而消除了與類別負相關(guān)的特征項對模型選擇的影響.但是在不平衡數(shù)據(jù)集中，上述方法都沒有考慮各類別之間文檔頻數(shù)的差異性，以文檔頻數(shù)為基礎(chǔ)度量特征項在各類間的集中程度，在不平衡數(shù)據(jù)集中并不能適用，同樣存在傾向于選擇大類特征項的問題.

假設(shè)現(xiàn)在有兩個類別，一個小類別Cp有200篇文檔，大類別Cq有1000篇文檔，其中小類別Cp含有特征詞ts的文檔數(shù)有199篇，大類別Cq含有特征詞ts的文檔數(shù)有10篇，小類別Cp含有特征詞tt的文檔數(shù)有10篇，大類別Cq含有特征詞ts的文檔數(shù)有101篇，那么明顯α(ts,Cp)<α(tt,Cq)，算法會選擇tt做特征項，但是對比很容易發(fā)現(xiàn)，特征詞ts幾乎在類別Cp中的全部文檔出現(xiàn)，而特征詞tt雖然出現(xiàn)在類別Cq的文檔頻數(shù)比特征詞ts出現(xiàn)在類別Cp的文檔頻數(shù)大，但出現(xiàn)的文檔數(shù)只占類別Cq的總體文檔的一小部分，因此特征詞ts對于類別Cp的分類價值是高于特征詞tt對于類別Cq的分類價值.

因此，為了解決類別傾向性問題，以及忽略了負相關(guān)對特征選擇的影響的問題，本文以類內(nèi)中包含特征項tk的文檔概率來度量特征項在不平衡數(shù)據(jù)集中類間的集中程度，并考慮了負相關(guān)特征項的對稀有類別的價值，添加了類別傾向因子θ，并對β進行了修正和完善，得到了類間文檔概率集中因子βnew，如式(10)所示:

(10)

式(10)中：M表示類別總數(shù)；df(tk,Ci)表示類別Ci中含有特征項tk的文檔頻數(shù)；df(Ci)表示類別Ci中的文檔頻數(shù)；A表示在類別Ci中含有特征項tk的文檔數(shù)；B表示不在類別Ci中但包含特征項tk的文檔數(shù)；C表示在類別Ci但是不包含有特征項tk的文檔數(shù)；D表示既不在類別Ci中也不包含有特征項tk的文檔數(shù)；當AD-BC<0且θ>0.5時，表示A相對D來說較多，造成負相關(guān)的主要原因是D較少，在實際應(yīng)用中，小類發(fā)生這樣的可能性往往大于大類，所以θ是一個傾向于小類的選擇的因子.

類間文檔頻率集中因子βnew(tk,Ci)表示類別Ci中含有特征項tk的文檔頻率與所有類中還有該特征項的文檔頻率的平均值的偏離程度，度量了在不均衡數(shù)據(jù)集中特征項tk在類別Ci出現(xiàn)的集中程度.βnew(tk,Ci)值越大，表示該特征項在該類中的文檔中出現(xiàn)的概率越高，而在其它類中的文檔中出現(xiàn)的頻率越低，顯然該特征項對該類具有高的分類價值.

2.3 加入類內(nèi)均勻因子

χ2統(tǒng)計模型沒有考慮特征項在類內(nèi)各文檔的分布情況.一般來說，對特定類別具有鑒別能力的特征項，應(yīng)該在指定類中各文檔中均勻地出現(xiàn)，若只集中在該類的個別文檔中出現(xiàn)，而在其它文檔中很少出現(xiàn)，則表明特征項對該類別的鑒別信息就要小很多.

考慮下面的情況，假設(shè)特征項tk在類別Ci中，僅在少數(shù)幾個文檔中出現(xiàn)，即使出現(xiàn)頻數(shù)比較大，該特征項對該類別也不具有很高的分類價值.因此，特征項在某一類中各個文檔中分布越均勻，其類別表現(xiàn)能力越強.

根據(jù)樣本方差的思想，特征項在該類各個文檔出現(xiàn)頻數(shù)越接近，說明該特征項在該類各文檔中分布越均勻，總體方差就越小，其類別表現(xiàn)能力越強.反之，樣本方差越大，其類別表現(xiàn)能力越低.

對文獻[7]中的γ參數(shù)進行修正和變型，可以得到特征項類內(nèi)平衡因子γnew，如式(11)所示：

(11)

式(11)中：Mi表示類別Ci中的文檔數(shù)；tf(tk,dij)表示特征詞tk在類別Ci中的文檔dij中出現(xiàn)的次數(shù).

γnew(tk,Ci)度量的是特征項tk在類別Ci中各文檔的分布均勻程度，顯然特征項tk在類Ci各個文檔之間的分布越平均，γnew(tk,Ci)的值越大，該特征項對該類的鑒別價值就越高.

綜上可知，在不平衡數(shù)據(jù)集中，其類內(nèi)詞頻概率因子、類間文檔概率集中因子和類內(nèi)平衡因子都有很大的特征項，該特征項對該類的類別辨識能力越強.因此對傳統(tǒng)χ2統(tǒng)計模型改進后如式(12)所示：

(12)

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

數(shù)據(jù)來源于復(fù)旦大學(xué)計算機信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組整理的訓(xùn)練和測試語料庫.在20個類別當中，選取了政治、體育、計算機、藝術(shù)、經(jīng)濟、環(huán)境和歷史這7個文檔數(shù)目較多的類別作為實驗訓(xùn)練、測試集.語料集為各類文檔分布不均勻的語料集，各類文檔具體的選取情況如下表所示.

表1 語料集上訓(xùn)練集和測試集的選取情況

3.2 評價指標

本文采用文本分類中最常用的性能評價指標查全率(recall)、查準率(precision)和F1.

(13)

(14)

(15)

式(15)中：r表示查全率；p表示查準率；

3.3 實驗過程

3.4 結(jié)果分析

表2 不平衡數(shù)據(jù)集下的對比實驗結(jié)果

4 結(jié) 語