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

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）11-0012-04

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

1 特征選擇

1.1 定義

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

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

1.2分類

特征選擇算法可以[4]分為四個(gè)步驟：搜索特征子集、評(píng)價(jià)函數(shù)、停止準(zhǔn)則和檢驗(yàn)過(guò)程。目前，國(guó)際上主要從搜索特征子集的過(guò)程和評(píng)價(jià)函數(shù)兩個(gè)方面研究特征選擇方法。因此，本文將從在特征空間的搜索方式和對(duì)特征子集的評(píng)價(jià)標(biāo)準(zhǔn)兩個(gè)方面對(duì)特征選擇方法進(jìn)行分類。

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

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

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

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

根據(jù)對(duì)特征子集評(píng)價(jià)標(biāo)準(zhǔn)的不同，可將特征選擇分為封裝式評(píng)價(jià)（Wrapper）特征選擇和過(guò)濾式評(píng)價(jià)（Filter）特征選擇[6]。

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

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

1.3 常用特征選擇方法

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

1.3.1 TF-IDF

TF-IDF[9]（Term Frequency-Inverse Document Frequency）將特征出現(xiàn)的頻率和分布范圍兩方面相結(jié)合作為特征重要性的衡量標(biāo)準(zhǔn)。特征出現(xiàn)的頻率越高，選用特征的分類結(jié)果越好；特征出現(xiàn)的范圍越廣，選用特征的分類結(jié)果越差。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)帶來(lái)的信息量作為特征重要性的衡量標(biāo)準(zhǔn)。這里所謂的信息量就是信息論中的熵。熵體現(xiàn)一個(gè)體系的混亂程度，是不確定性的一種量度。信息增益越大，選用特征的分類結(jié)果越好。

對(duì)于一個(gè)分類器，類別Ai（1≤i≤n）視為一個(gè)變量，我們不考慮類別A的取值，只考慮類別A可能取值的種類數(shù)n和相應(yīng)取值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之間的關(guān)聯(lián)程度作為特征重要性的衡量標(biāo)準(zhǔn)。特征t和類別A之間的關(guān)聯(lián)程度越強(qiáng)，兩者的互信息量就越大，選用特征的分類結(jié)果越好。特征t和類別A之間的互信息量MI（t，A）可表示為：

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

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

1.3.4 文本證據(jù)權(quán)

文本證據(jù)權(quán)（Weight of Evidence for Text：WET）將特征t給定與否時(shí)類別Ai（1≤i≤n）出現(xiàn)的概率差別作為特征重要性的衡量標(biāo)準(zhǔn)。特征t給定與否時(shí)類別A出現(xiàn)的概率差別越大，WET的值就越大，選用特征的分類結(jié)果越好。文本證據(jù)權(quán)（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）之間的關(guān)聯(lián)程度兩方面相結(jié)合作為特征重要性的衡量標(biāo)準(zhǔn)。該方法與信息增益類似，不同的是它只考慮特征出現(xiàn)的情況。期望交叉熵越大，選用特征的分類結(jié)果越好。期望交叉熵ECE（t）可表示為：

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

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

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

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

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

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

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

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

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

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

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

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

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