基于方差分析的[χ2]統(tǒng)計特征選擇改進算法研究

唐亞娟++張德賢++楊琳

摘要：特征選擇是中文文本分類的一個重要研究領域，是提高學習算法性能的一個重要手段，也是模式識別中數(shù)據(jù)預處理的關鍵步驟。該文對特征提取的定義及其分類進行了深入分析，介紹了幾種常用的經典特征選擇方法，并針對特征選擇研究過程中存在的不足，提出了基于方差分析的[χ2]統(tǒng)計特征選擇改進算法。該算法在引入方差分析思想的基礎上，向傳統(tǒng)的[χ2]統(tǒng)計特征選擇算法融入特征頻數(shù)、文檔間均衡因子和文檔內均衡因子三個元素和一個制約條件，對于提高其性能方面起到很大作用。

關鍵詞：特征選擇；[χ2]統(tǒng)計；方法分析

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）11-0012-04

在中文文本處理的過程中，人們通常采用詞條作為最小的獨立語義單元。如果一個中文文本向量空間中包含在文章中出現(xiàn)過的全部詞條，那么對于一個一般規(guī)模的語料庫而言，其包含的詞條數(shù)可能達到數(shù)十萬甚至數(shù)百萬。另外，兩個具有很好的分類信息的特征在合并成一個特征向量時，可能會因為其相關性而幾乎得不到任何信息。對于所謂的維數(shù)災難，并且從計算復雜型和分類器的通用性考慮，特征選擇是必要的。特征選擇作為一種常見的降維算法，其目的是解決文本向量表示低密度性和特征空間高維度性之間的矛盾。因此，特征選擇是中文文本分類的一個重要研究領域，具有重要的應用價值和學術價值。

1 特征選擇

1.1 定義

特征選擇（Feature Selection）也叫特征子集選擇（ FSS ， Feature Subset Selection ）。是從一組特征中挑選出一些最有效的特征以降低特征空間維數(shù)的過程[1]。它是提高學習算法性能的一個重要手段，也是模式識別中數(shù)據(jù)預處理的關鍵步驟。

目前，很多學者從不同角度定義過特征選擇：Koller等人[2]以分布為出發(fā)點定義特征選擇為：在確保原始類分布與結果類分布盡量相近的前提下，選擇盡量小的特征子集。John等人[3]以提升預測精確程度為出發(fā)點定義特征選擇是一個能夠增加分類精確程度，或者在不降低分類精確程度的前提下降低特征維數(shù)的過程； Dash等人[4]定義特征選擇是應同時滿足不顯著改變類分布和不顯著降低分類精確程度兩個條件的情況下，選擇盡可能小的特征子集。Kira等人[5]定義特征選擇是在沒有外界因素干擾的情況下找到必不可少的并且足以辨別目標的最小特征子集。雖然上述各種定義的角度不同，但是它們的最終目的都是尋找一個能夠有效識別目標的最優(yōu)最小特征子集。

1.2分類

特征選擇算法可以[4]分為四個步驟：搜索特征子集、評價函數(shù)、停止準則和檢驗過程。目前，國際上主要從搜索特征子集的過程和評價函數(shù)兩個方面研究特征選擇方法。因此，本文將從在特征空間的搜索方式和對特征子集的評價標準兩個方面對特征選擇方法進行分類。

根據(jù)在特征空間的搜索方式的不同，可將特征選擇分為全局最優(yōu)搜索式特征選擇、啟發(fā)搜索式特征選擇和隨機搜索式特征選擇。

在以上三種特征選擇方式中，只有全局最優(yōu)搜索式特征選擇能得到最有結果。但是，由于其本身存在的確定優(yōu)化特征子集數(shù)目、設計滿足單調性的可分性判據(jù)和較高的時間復雜度等問題難以有效解決，導致其難以得到廣泛應用。

啟發(fā)搜索式特征選擇主要有一下八種：浮動搜索方法、單獨最優(yōu)特征組合、序列后向選擇方法（SBS）、廣義序列后向選擇方法（GSBS）、增L去R特征選擇方法，、廣義增L去R特征選擇方法、序列前向選擇方法（SFS）和廣義序列前向選擇方法（GSFS）。該方法易于實現(xiàn)且效率高，應用廣泛，但是它的問題是不能得到全局最優(yōu)。

隨機搜索式特征選擇以采樣過程和概率推理作為算法的依據(jù)。該方法通常與某些算法相結合，為每個特征賦予權重并根據(jù)閾值對其重要性進行評價。該方法可以得到近似最優(yōu)解并且應用廣泛，但是存在參數(shù)選擇和時間復雜度問題。

根據(jù)對特征子集評價標準的不同，可將特征選擇分為封裝式評價（Wrapper）特征選擇和過濾式評價（Filter）特征選擇[6]。

封裝式評價特征選擇在篩選特征的過程中依賴后續(xù)機器學習算法性能函數(shù)評價特征子集，并用所選特征子集訓練學習器，特征子集優(yōu)劣的評價標準是以測試集在學習器上的性能表現(xiàn)作為依據(jù)的。封裝式評價特征選擇雖然計算速率和泛化程度劣于過濾式評價特征選擇，但其縮小優(yōu)化特征子集規(guī)模的能力和選擇準確率都略勝一籌。

過濾式評價特征選擇在評價特征子集時獨立于具體的學習算法，該方法根據(jù)基于信息統(tǒng)計的啟發(fā)式準則[7-8]選取預測能力較優(yōu)的特征組成特征子集，其評價函數(shù)有依賴性、信息、距離和一致性四個方面設定評價標準[4]。過濾式評價特征選擇可以縮小優(yōu)化特征子集的搜索范圍，并且快速排除部分非關鍵性噪聲特征，因此，其可作為特征的預篩選器，但是該方法不能保證選擇出一個合理規(guī)模的優(yōu)化特征子集。

1.3 常用特征選擇方法

常用的特征選擇方法有TF-IDF、信息增益、互信息、文本證據(jù)權、期望交叉熵以及[χ2]統(tǒng)計量等等。下面將對這幾種特征選擇方法做詳細介紹。

1.3.1 TF-IDF

TF-IDF[9]（Term Frequency-Inverse Document Frequency）將特征出現(xiàn)的頻率和分布范圍兩方面相結合作為特征重要性的衡量標準。特征出現(xiàn)的頻率越高，選用特征的分類結果越好；特征出現(xiàn)的范圍越廣，選用特征的分類結果越差。TF-IDF可表示為：

TFIDF（ti） = [tfi×log（Nni+0.1）I=1n（tfi）2×[log（Nni+0.1）]2] （1）

其中，tfi是特征ti在類別A中出現(xiàn)的頻數(shù)，N是類別A中的文檔數(shù)，ni是出現(xiàn)特征ti的文檔數(shù)。

1.3.2 信息增益

信息增益（Information Gain： IG）[10]將特征能夠給分類系統(tǒng)帶來的信息量作為特征重要性的衡量標準。這里所謂的信息量就是信息論中的熵。熵體現(xiàn)一個體系的混亂程度，是不確定性的一種量度。信息增益越大，選用特征的分類結果越好。

對于一個分類器，類別Ai（1≤i≤n）視為一個變量，我們不考慮類別A的取值，只考慮類別A可能取值的種類數(shù)n和相應取值P（Ai）概率是多少。類別Ai 的信息熵Info（A）可表示為：

Info（A） = - [i=1nP（Ai）log2P（Ai）] （2）

將特征t用于分類后的類別Ai以后，類別Ai的條件信息熵Info（A|t）可表示為：

Info（A|t） = - [i=1nP（Ai|t）log2P（Ai|t）] （3）

類別Ai的信息增益為選用特征t前后類別Ai的信息熵變化量，用Gain（A|t）可表示為：

Gain（A|t） = Info（A）-Info（A|t） =-[i=1nP（Ai）log2P（Ai）]+[i=1nP（Ai|t）log2P（Ai|t）] （4）

1.3.3 互信息

互信息（Mutual Information：MI）將特征t和類別A之間的關聯(lián)程度作為特征重要性的衡量標準。特征t和類別A之間的關聯(lián)程度越強，兩者的互信息量就越大，選用特征的分類結果越好。特征t和類別A之間的互信息量MI（t，A）可表示為：

MI（t，A） = [log2P（t，A）P（t）×P（A）] （5）

其中，P（t|A）是特征t在類別A中的文檔頻數(shù)占訓練集的比例；P（t）是特征t在訓練集中的文檔頻數(shù)占訓練集的比例；P（A）是類別A在訓練集中的文檔頻數(shù)占訓練集的比例。

1.3.4 文本證據(jù)權

文本證據(jù)權（Weight of Evidence for Text：WET）將特征t給定與否時類別Ai（1≤i≤n）出現(xiàn)的概率差別作為特征重要性的衡量標準。特征t給定與否時類別A出現(xiàn)的概率差別越大，WET的值就越大，選用特征的分類結果越好。文本證據(jù)權（WET）可表示為：

WET（t） = [P（t）×i=1n[p（Ai）×|logPAi|t×（1-P（Ai））PAi×（1-PAi|t）|]] （6）

1.3.5 期望交叉熵

期望交叉熵（Expected Cross Entropy：ECE）將特征t出現(xiàn)的頻率和其類別Ai（1≤i≤n）之間的關聯(lián)程度兩方面相結合作為特征重要性的衡量標準。該方法與信息增益類似，不同的是它只考慮特征出現(xiàn)的情況。期望交叉熵越大，選用特征的分類結果越好。期望交叉熵ECE（t）可表示為：

ECE（t） = [P（t）×i=1n[PAi|t×log2PAi|tPAi]] （7）

1.3.6 [χ2]統(tǒng)計

[χ2]統(tǒng)計（CHI） 來自于列聯(lián)表檢驗（CTT， Contingency Table Test），它是在被假定服從一階自由度的[χ2]分布的基礎上，將特征t和類別A之間的關聯(lián)程度作為特征重要性的衡量標準。該方法與互信息相似，不同的是它同時考慮了正相關和負相關對特征重要性的影響。特征t對于類別A的[χ2]統(tǒng)計[χ2（t，A）]可表示為：

[χ2]（t，A） = [m×（MQ-NP）2M+P×N+Q×M+N×（P+Q）] （8）

其中，M是訓練集中包含特征t且屬于類別A的文檔數(shù)，N是包含特征t但不屬于類別A的文檔數(shù)，P是不包含特征t但屬于類別A的文檔數(shù)，Q是不包含特征t且不屬于類別A的文檔數(shù)，m是訓練集中的所有文檔數(shù)，且有m=M+N+P+Q。

特征t對于類別A的[χ2]統(tǒng)計值[χ2]（t，A）越大，特征t和類別A之間的關聯(lián)程度就越強，選用特征的分類結果越好。當特征t對于類別A的[χ2]（t，A）=0時，表示特征t與類別A相互獨立，完全無關的。

2 基于方差分析的[χ2]統(tǒng)計特征選擇改進研究

2.1 [χ2]統(tǒng)計方法分析及其缺陷

假定在一個訓練集中有n個類別，可用Ai（1≤i≤n）表示，分別計算特征t對于類別Ai的[χ2]值，那么特征t就會有n個[χ2]值，需要通過[χ2]MAX（t）選出一個最大值作為特征t對于語料庫的[χ2]值，并設定一個特定閾值來判定特征t是否可以作為類別Ai的特征詞。若特征t的[χ2]值高于閾值則保留作為類別Ai的特征詞，否則將t從原始特征空間中舍棄。

[χ2]MAX（t） = [max1≤i≤n{χ2（t，Ai）}] （9）

[χ2]統(tǒng)計方法是在中文文本分類系統(tǒng)中使用最多的一種特征選擇方法[11]。但是，該方法仍有一些不足之處，導致其概率估計誤差的靈敏度有待提高，特征選擇性能差強人意。

從[χ2]（t，A）計算公式可以看出，傳統(tǒng)[χ2]統(tǒng)計方法只考慮了特征在所有文檔中出現(xiàn)與否和是否屬于類別Ai時的文檔頻數(shù)，并沒有考慮其在每個文檔中出現(xiàn)的詞條頻數(shù)以及類別Ai的所有文檔之間和每個文檔中的分布均勻程度。文檔中存在一些在每個文檔中出現(xiàn)的詞條頻數(shù)以及類別的所有文檔之間和每個文檔中的分布均勻程度都很高的詞條，這些詞條中一部分可能對文本分類幾乎沒有貢獻率如“我們、的”等，而這些對文本分類幾乎沒有貢獻率詞條會在文本預處理的過程中利用停用詞表篩選出來并丟棄，而另一部分則可能是文本分類所需要的特征詞，這些特征詞可能會因為[χ2]統(tǒng)計公式的缺陷無法被選出。

如果公式中包含特征t但不屬于類別A的文檔數(shù)或者不包含特征t但屬于類別A的文檔數(shù)較大，而包含特征t且屬于類別A的文檔數(shù)和不包含特征t且不屬于類別A的文檔數(shù)相對較小，那么即便是特征t的MQ-NP<0不滿足我們期望的選出特征的要求，特征t也會因為（MQ-NP）2的值很大而導致[χ2]值很大被誤選為類別特征詞，從而影響選出特征詞的分類結果。