基于對數似然比的中文文本分類特征選擇研究

梁伍七，李 斌，許 磊，江克勤

自動文本分類在垃圾郵件過濾、信息檢索、文本挖掘和搜索引擎等領域有重要應用。分類系統主要包括預處理、分類和評估模塊，預處理模塊包括文本表示、特征選擇和模型建立等過程，分類模塊主要是利用分類算法對待分類文本進行自動分類，評估模塊設計評價指標對分類系統的性能進行評價。1975年Salton提出用向量空間模型描述文本[1]。向量空間模型中，用特征向量來表達文本，特征向量的維數就是特征空間特征詞的個數。降低特征空間的維數，可以提高分類器的分類性能。特征選擇算法可以劃分為過濾式（Filter）、包裹式（Wrapper）和嵌入式（Embedded）三種類型[2]。過濾式特征選擇在分類之前使用，目的是過濾對分類貢獻值不大或和類別相關度不高的特征，自動文本分類中常用的特征選擇多屬于過濾式類型。集成特征選擇[3]是一種提高特征選擇算法穩定性的新技術。文獻[4]提出了多種方法度量兩個特征選擇的輸出結果，用來評估特征選擇算法的穩定性。文獻[5]提出多準則融合特征評估方法來提高分類精度以及特征選擇算法的穩定性。

傳統的特征選擇方法[6]有信息增益(IG)、期望交叉熵(ECE)、互信息(MI)、文本證據權(WET)、文檔頻率(DF)、χ2統計(CHI)等。IG算法廣泛應用于機器學習領域[7]，在不降低分類性能的前提下,IG算法可以大規模地移走“無用的”單詞。文獻[8]在比較樸素貝葉斯和決策樹分類算法時使用IG算法來降低單詞量，文獻[9]在比較支持向量機和其他分類算法時使用IG算法來進行特征選擇，文獻[10]引入類內分散度和類間集中度等因素對IG算法進行了改進。MI算法從頻度指標出發，計算單詞在每個類別中的出現頻度與它在整個語料庫中出現頻度的比值，作為該單詞對某個類別的分類貢獻。MI沒有考慮單詞的集中度和分散度，使得互信息評估函數傾向于選擇低頻單詞，因此MI表現出的分類性能比較差，文獻[11]利用權重因子、修正因子和特征項的位置差異對MI特征選擇進行了改進。文獻[12]研究表明，當IG和CHI等方法的計算代價太高而變得不可用時，DF算法可以代替它們。CHI特征選擇衡量單詞w與類別c之間的相關程度，算法基于Pearson χ2檢驗，用于對變量進行獨立性檢驗。CHI算法和IG算法在文本分類中的性能表現相當，有時候比IG算法性能更優，所以在文本分類系統中應用比較廣泛[6]。但特征選擇問題中，文檔包含單詞w和這個文檔屬于類別c同時發生是稀有事件，此時χ2統計和實際的偏差就會比較大。針對這一問題，提出對數似然比(LLR)特征選擇算法。

1 對數似然比特征選擇算法

假設有兩個隨機變量X和Y，X取值為xi（i=1,2,…,r），Y取值為yj（j=1,2,…,c），觀察值記為Oi,j，在變量獨立的假設下，觀察值的期望次數為

其中N是樣本大小。用于校驗的χ2統計值公式：

對于文本分類特征選擇來說，兩個隨機事件分別是指文檔是否包含單詞w和這個文檔是否隸屬于類別c，兩個隨機事件可能的結果定義為隨機變量X和Y，當文檔包含單詞w時，X取值為1，否則取值為0；當文檔屬于類別c時，Y取值為1，否則取值為0，此時（2）式可簡化為

其中，N11為訓練文檔中包含單詞w的c類文檔數，N10為訓練文檔中包含單詞w的非c類文檔數，N01為訓練文檔中不包含單詞w的c類文檔數，N00為訓練文檔中不包含單詞w的非c類文檔數， ||D為訓練語料中文檔總數。單詞對于某類的χ2統計值越高，它與該類之間的相關性越大。

當期望次數Ei,j＞5時，不管總體屬于什么分布，統計量χ2都服從χ2分布。但特征選擇問題中，文檔包含單詞w和這個文檔屬于類別c同時發生是稀有事件，就有期望次數Ei,j≤5，此時χ2統計和實際的偏差就會比較大，χ2統計就變得不再適用。文獻[13]研究表明，稀有事件的發生概率更接近于貝努利分布，文檔包含單詞w和這個文檔屬于類別c的統計任務可視為重復的貝努利試驗。

設隨機變量X服從參數為n1和p1的二項分布，隨機變量Y服從參數為n2和p2的二項分布，概率分布函數分別為

其中，n1和n2分別表示兩個重復的貝努利試驗的總次數，試驗中出現正面的次數記為k1和k2，試驗中出現正面的概率記為 p1和p2。兩個二項分布的似然函數構造為

其中，參數 p1和p2構成全局參數空間Ω，如果分布的參數 p1和 p2相同，定義集合Ω0={(p1,p2)|p1=p2=p}。構造校驗的似然比為

其中，L(p,k,n)=pk(1-p)n-k，在似然比兩邊取對數有：

稱-2logλ為log似然比統計量。當觀察值的期望次數Ei,j＞5時，log似然比統計量非常接近χ2統計量；當Ei,j≤5時，log似然比統計量更能準確地描述兩個稀有事件的相關性。對于非稀有事件，log似然比統計量和χ2統計量相當；對于稀有事件，log似然比統計量和χ2統計量更準確。

特征選擇問題中，記對數似然比-2logλ為LLR，它可以用來校驗文檔包含單詞w和這個文檔屬于類別c這兩個事件之間的獨立性。具體計算時，仍采用（3）式中的記號。

將結果代入（9）式有：

LLR特征選擇算法描述如下：

（1）計算文檔總數N= ||D，D表示訓練語料庫集合；

（2）對集合D中的文檔進行分詞并過濾停用詞構成詞典集合W；

（3）計算單詞w相對于整個訓練語料庫集合D的LLR值；對于每個單詞w∈W；對于每個類別ci∈C，C表示類別集合；利用鄰接表T信息計算 N11，N10，N01，N00；利用（10）式計算單詞 w和類別ci的LLR(w,ci)值；計算單詞w對分類的貢獻分值；定義向量容器保存單詞w及其LLR(w)值；

（4）依據LLR(w)值作為關鍵字降序排序向量元素；

（5）定義特征維度取值參數M，用排序后的前M個單詞構造特征詞集合K。

LLR算法的時間復雜度為O(V×M)，其中V是訓練語料庫分詞并過濾停用詞后構成的詞典集合大小。

2 實驗過程和性能分析

2.1 性能評估指標

采用通用的性能評估指標評價分類系統的性能，指標包括查準率(Precision，簡記為P)、查全率(Recall，簡記為R)和F1測試值[14]。

針對多個類別的分類問題，對于某個類別c，引進如下記號：

TP：實際上為類別c的文檔被正確分類為類別c的數量；

FP：實際上為非類別c的文檔被錯誤分類為類別c的數量；

FN：實際上為類別c的文檔被錯誤分類為非類別c的數量；

TN：實際上為非類別c的文檔被正確分類為非類別c的數量；

查準率P=TP/(TP+FP)，被正確分類的類別c文檔數量除以被分類為類別c的文檔數量，也稱為準確率。

查全率R=TP/(TP+FN)，被正確分類的類別c文檔數量除以實際為類別的文檔數量，也稱為召回率。

F1=2PR/(P+R)，查準率和查全率的調和平均值。

分類器的查準率、查全率和F1值定義為每個類別的查準率、查全率和F1值的平均值。

2.2 實驗過程

文本分類一般由預處理、特征選擇、向量空間模型建立和分類算法等部分組成[15]。

預處理模塊主要包括中文分詞、建立詞典和處理停用詞等，使用中科院ICTCLAS中文分詞系統對語料庫文本進行分詞，定義詞典數據結構保存詞在每篇文檔中出現的次數，將常用虛詞作為停用詞進行過濾。使用傳統特征選擇和對數似然比特征選擇算法計算詞典文件中的詞對分類貢獻函數值，根據設定的特征空間維數對高維特征空間進行降維，構成分類算法需要的特征空間。

構建向量空間模型主要任務是將訓練文檔表示為特征詞的向量形式，特征項的權重作為文檔向量的分量，特征項的權重計算使用TF-IDF加權算法。TF表示特征項的詞頻，IDF稱為逆文檔頻率，TF-IDF算法綜合利用了詞頻和文檔頻率兩種信息，是目前公認的特征加權方法。根據TFIDF算法計算特征項的權重，將訓練文檔表示成權重作為分量的特征向量并進行歸一化，對待分類文檔按照類似步驟構建分類文檔向量空間模型。

分類算法模塊采用K最近鄰算法（K-Nearest Neighbor Agorithm）[16]。通過建立向量空間模型，訓練文檔和待分類文檔就表示成了特征詞的向量形式，用兩個向量之間的距離度量兩個文檔之間的相似性。在給定新文檔后，計算新文檔和訓練文檔集合中每篇文檔的相似度，選取訓練文檔集合中最相似的K篇文檔，統計K篇文檔中哪個類別出現的次數最多，則將新文檔類別標簽判定為該類別。

2.3 實驗結果和性能分析

實驗采用的語料庫源于搜狗新聞分類語料庫[17]。通過數據整理和清洗，選定36 041篇文檔作為訓練語料庫，分9個類別，測試文檔總數6 000篇，訓練語料庫每個類別的文檔總數如表1所示。

表1 訓練語料庫每個類別的文檔總數

通過中文分詞系統對語料庫文本進行分詞，將常用虛詞進行過濾處理，預處理后的單詞總數為122 347個，特征選擇分別選用IG，ECE，MI，WET，DF，CHI和LLR這7種算法進行。特征空間特征詞數量分別取 50，100，200，400，600 和800，針對每個類別計算P、R和F1值，再計算分類系統的平均P、R和F1值。KNN分類算法中，鄰居個數K取值為100，表示保留和待分類文檔最近的100篇訓練文檔，7種特征選擇算法得到的分類評估結果如表2至表4以及圖l，圖2所示。

表2 7種特征選擇算法分類P值結果

表3 7種特征選擇算法分類R值結果

表4 7種特征選擇算法分類F1值結果

圖1 CHI和IG等4種算法分類F1值結果

圖2 ECE，WET和DF等5種算法分類F1值結果

從表2至表4以及圖l，圖2可以看出：

（1）MI算法的效果最差，原因是MI忽略了單詞的分散度和集中度，在計算特征詞對分類貢獻時，僅考慮特征詞在每個類別中的出現頻度與它在整個語料庫中的出現頻度的比值，從而使稀有單詞具有較大的互信息，這就導致MI算法不是選擇高頻的有用詞，而是選擇稀有詞作為最佳特征。

（2）CHI算法和IG算法。維度較低時，IG好于CHI，隨著維度的增加，CHI和IG分類的結果逐漸變好，二者總體性能表現不相上下。當特征選擇維度超過200時，二者總體性能趨于穩定。

（3）ECE算法和WET算法。當特征選擇維度不超過100時，WET算法的總體性能略高于ECE算法。當特征選擇維度超過200時，ECE算法的分類P值和R值都高于WET算法，總體性能也比WET算法強。隨著維度的增加，ECE算法的總體性能逐漸變好，WET算法的總體性能逐漸穩定且略有下降。

（4）DF算法。DF算法的分類效果除了比MI算法好以外，在所有其他算法中是最差的。從圖中可以看出，DF算法的P值、R值和F1測試值比ECE和WET算法都低，原因是DF算法只用到了特征詞的文檔頻率信息。但對于大規模數據集而言，當其他特征選擇算法的計算代價太高而變得不可用時，DF算法可以代替它們。

（5）LLR算法。無論特征選擇維度如何變化，LLR算法分類結果都比較穩定，分類P值、R值和F1測試值都比其他特征選擇算法要高，且特征選擇維度取值增加時，LLR算法的三個評估指標曲線有進一步上升的趨勢。

3 結束語

通過引入對數似然比統計量，提出對數似然比中文文本分類特征選擇算法。針對MI算法評估函數過分傾向于低頻單詞的缺陷，LLR算法計算低頻單詞的貢獻更準確；針對CHI算法中，低頻單詞導致的稀有事件使得CHI統計結果會出現偏差，LLR算法消除了這種偏差，計算低頻單詞對分類的正面貢獻更準確，消除了低頻單詞對分類的噪音，提高了分類系統的總體分類性能，且不受特征空間維數變化的影響，是一種較好的特征選擇方法。

需要進一步研究的問題：針對現有特征選擇算法的不足進行改進，以提高分類算法性能；針對特征選擇算法的穩定性問題，對集成特征選擇方法進行研究；對貝葉斯分類和支持向量機分類算法進行研究，通過不同的特征選擇算法，融合多種分類方法進行集成學習，最終構建一個分類效果良好的文本分類系統。

參考文獻：

[1]SALTON G,WONG A,YANG C S.A vector space model for automatic indexing[J].Communications of the ACM,1975,18(11)：613-620.

[2]SUN Z H,BEBIS G,Miller R.Object detection using feature subset selection[J].Pattern Recognition,2004,37(11)：2165-2176.

[3]HAURY A C,GESTRAUD P,VERT J P.The influence of feature selection methods on accuracy,stability and interpretability of molecular signatures[J].PLoS One,2011,6(12)：e28210.

[4]SOMOL P,NOVOVICOVA J.Evaluating stability and comparing output of feature selectors that optimize feature subset cardinality[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2010,32(11)：1921-1939.

[5]FENG Y,MAO K Z.Robust feature selection for microarray data based on multicriterion fusion[J].ACM Transactions on Computational Biology and Bioinformatics,2011,8(4)：1080-1092.

[6]尚文倩.文本分類及其相關技術研究[D].北京：北京交通大學,2007.

[7]MITEHELL T.Machine learning[M].NewYork：McGraw-Hill,1997：292-294.

[8]LEWIS D D,RINGUETTE M.A Comparison of two learning algorithms for text categorization[C].In Proceedings of the Third Annual Symposium on Document Analysis and Information Retrieval.Las Vegas,USA,1994：81-93.

[9]JOACHIMS T.Text categorization with support vector machines：learning with many relevant features[C].In ECML 1998，Chemnitz,German,1998：137-142.

[10]郭亞維,劉曉霞.文本分類中信息增益特征選擇方法的研究[J].計算機工程與應用,2012,48(27)：119-122，127.

[11]劉海峰,陳琦,張以皓.一種基于互信息的改進文本特征選擇[J].計算機工程與應用,2012,48(25)：1-4，97.

[12]YANG YM,PEDERSEN JO.A comparative study on feature selection in text categorization[C].Proceeding of the Fourteenth International Conference on Machine Learning(ICML97).San Francisco,USA：Morgan Kaufmann Publishers,1997：412-420.

[13]TED Dunning.Accurate methods for the statistics of surprise and coincidence[J].Computational Linguistics,1993,19(1)：61-74.

[14]LIU Tao,LIU Shengping,CHEN Zheng.An evaluation on feature selection for text clustering[C].Proceedings of the 20th International Conference on Machine Learning,Washington DC,USA,2003：488-495.

[15]梁伍七,李斌,許磊.基于類別的CHI特征選擇方法[J].安徽廣播電視大學學報,2015(3)：124-128.

[16]COVER T M,HART P E.Nearest neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1)：21-27.

[17]中文分類語料庫[EB/OL].(2012-03-21)[2015-12-04].http：//www.sogou.com/labs/dl/tce.html.