基于成對約束分的特征選擇及穩定性評價?

趙 帥 張 雁 徐海峰

（西南林業大學大數據與智能工程學院 昆明 650224）

1 引言

特征選擇是一種重要的數據預處理方法，它廣泛應用于機器學習、模式識別和數據挖掘等領域。它主要是利用特征間的相關性和冗余度從原數據集中選出子集的過程［1］。特征子集可以劃分為4種類別：1）完全不相關的特征和噪音特征；2）弱相關特征和冗余特征；3）弱相關和非冗余特征；4）強相關特征［1］。一個最優的特征子集理論上包含3）和4），強相關特征在特征選擇過程中對于提高判別力和預測精度起著重要的作用；但是有時候，如果特征不是冗余的且和評估方法一致的話，那么弱相關特征在提高預測精度方面將是非常有幫助的［2］。因此，為了建立一個好的預測模型，所有的強相關特征和某些弱相關特征都需要選擇，而不相關的、冗余的或者噪音特征則應該被剔除［3］。特征選擇在知識發現中起著重要的作用，它不僅提高了預測效果和分類器的泛化能力，而且還降低了計算復雜度和存儲，提供了更快和更有效的模型［4］。

特征選擇方法分為過濾式、封裝式和嵌入式［5］。過濾式方法主要是利用訓練數據本身固有的特征去評估特征的好壞，而且不依賴于任何學習算法，封裝式方法則是直接使用提前確定好的學習算法去評估特征［6］。就精度而言，雖然封裝式比起過濾式能獲得更好的表現，但是卻有很高的計算復雜度。嵌入式方法則是將特征選擇過程嵌入到某個算法中，在相同的性能表現下，嵌入式方法比起封裝式效率更高而且更易處理［7］。在本文中，我們主要研究過濾式方法。

2 特征選擇

特征選擇的過程可以大致分為四個階段，主要包括特征子集的選取、特征子集的評價、訓練學習模型和測試學習模型。特征子集的選取主要是利用不同的搜索策略挑選出不同的特征子集，特征子集的評價則是通過各種度量方法來評價特征子集的優劣。訓練學習模型是利用訓練數據對建立好的模型進行訓練，測試學習模型則是利用測試數據對模型進行測試，以分類準確率的好壞來評價模型的好壞。在這四個階段中，每個階段的數據處理過程都對特征選擇的最終結果產生著重要影響（見圖1），但是最重要的一個階段就是特征子集的評價。

2.1 特征選擇的方向

特征選擇的第一個階段是特征子集的選取，對于特征子集的選取，有很多種方法。在進行特征子集的選取時，首先要考慮的問題就是特征選擇搜索的方向，不同的搜索方向會產生不同的結果。在這里，根據搜索方向的不同可以將特征選擇分為正向搜索、反向搜索［2］。正向搜索是利用循環每次向空集里面連續不斷的增加新的特征，而反向搜索則是利用循環每次把原特征集里較差的特征逐個剔除。

2.2 特征子集的評價

特征子集的評價對建立學習模型的好壞產生著重要的影響，因此如何評價子集的好壞在整個特征選擇過程中顯得至關重要。度量方法主要有兩類：1）依靠數據一般屬性的測度；2）把分類規則作為評價特征一部分的測度［8］。在特征選擇過程中，常以信息增益的大小和分類算法來作為評價準則。給定數據集D，假定D 中第i 類樣本所占的比例為pi(i=1，2，…，|Y|)。假定樣本屬性均為離散型。對屬性子集A，假定根據其取值將D 分成了V個子集｛D1，D2，…DV｝，每個子集中的樣本在A 上取值相同，于是可以計算屬性子集A 的信息增益，其中信息熵定義為信息增益Gain（A）越大，意味著特征子集A 包含的有助于分類的信息越多［9］。因此，對于每個候選特征子集，都可以基于訓練數據集D來計算其信息增益。

特征子集A 實際上確定了對數據集D 的一個劃分，每個劃分區域對應著A 上的一個取值，而樣本標記信息Y則對應著對D的真實劃分，通過估算這兩個劃分的差異，就能對A進行評價。與Y對應的劃分的差異越小，則說明A 越好，進而可以評價特征子集的好壞。常用的分類算法有Relief［10］、Las Vegas［11］和LASSO［12］。Relief方法設計了一個相關統計量來度量特征的重要性，Las Vegas 則使用隨機策略來進行子集搜索，并以最終分類器的誤差為特征子集評價準則，LASSO通過構造一個懲罰函數獲得一個精煉的模型，通過最終確定一些指標的系數為零，進而對子集進行評價。除了上面這幾種評價方法外，還有一種通過成對約束來對特征子集進行評價的方法。

3 成對約束分特征選擇

數據的先驗知識可以通過類別標記和成對約束這兩種不同的方法來獲取，在進行特征選擇時，需要知道類別標記的詳細信息才能準確地預測樣本數據的類別，而成對約束分則是通過成對的數據樣本去判斷它們是否是同一類（必聯的）或者不同類（勿聯的）［13～14］。

約束分特征選擇法是利用成對約束中的部分監督信息去選出最有代表性的特征子集，其中的關鍵一步是C、M 的產生。首先給定一個數據集X，，兩個子集C 和M和

xj屬于相同的類別｝屬于不同的類別｝，然后利用成對約束C 和M 中的監督信息去找出初始數據集X 中的n 個特征集。為了評估第r個特征的好壞，利用了式（3）、（4）兩個公式去計算其中fri表示第i 個樣本xi的第r 個特征，i=1，…，m；r=1，…，n。λ表示相關系數，在同一類中，兩個樣本間的距離一定小于不同類別的樣本間的距離，在這里設置λ=0.1。兩個樣本間的約束分越低，則表明它們之間的特征相關性越大。在本文中主要利用式（4）［15］，約束分特征選擇法見圖2。

4 實驗系統

4.1 實驗數據

實驗共選用了5 組數據集進行訓練和測試，其中Sonar、Ionosphere 和Vehicle 三組數據集來源于UCI［16］機器學習庫，RS為遙感影像數據，EnAudio為環境音數據。其中環境音數據包括五類，如不同種類的鳥叫聲、蛙聲、風聲、雨聲和雷聲。數據集的信息如表1所示。

表1 數據集的特征信息

4.2 實驗方法

Step1：分別對5 組數據集利用原始數據，按照比例設置訓練集和測試集（訓練集和測試集的屬性一致），分類方法選擇決策樹，按照默認參數設置，求出每組數據集原始數據的準確率。

Step2：利用約束分特征選擇法對5 組數據集各選出一半最優的屬性進行實驗，得到每組數據的準確率，由于約束分方法存在不穩定性，實驗對5組數據集分別測試10 次，然后求取準確率的平均值作為實驗結果。

Step3：對weka 平臺中的六種屬性選擇方法Correlation、GainRatio、InfoGain、OneR、ReliefF 和SymmetricalUncert 按照默認參數設置，選出最優的一半屬性，并計算出其準確率（見表2）。

表2 幾種方法在5組數據集上的準確率比較

對于準確率來說，從表2 可以看出，對于Sonar數據集，在同樣選擇一半特征的情況下，約束分特征選擇法能取得較好的效果，完全優于其他六種方法和原始數據訓練法。對于Ionosphere 數據集，約束分特征選擇法只優于其他三種方法和原始數據訓練方法。對于Vehicle 數據集，同樣的約束分特征選擇法比較占優勢，準確率完全高于其他六種方法和原始數據訓練法。對于RS 數據集，約束分特征選擇法準確率高于其他三種算法且優于原始訓練法。對于EnAudio 數據集，約束分特征選擇法的準確率并不如其他6 種方法，但是高于原始數據訓練法。總的來說約束分特征選擇法在大部分數據集上都能取得較好的表現。

4.3 穩定性評估

約束分特征選擇法不穩定的問題給實驗過程帶來了很大的影響，穩定性評估在特征選擇算法中起著重要的作用。文獻［17～18］中給出了特征選擇算法穩定性評估的常用方法，主要有三個公式，如下所示。

對于式（5），SW是皮爾遜相關系數，它是用來度量兩個權值w、之間的相關性的，SW的取值范圍為［-1，1］，取值為1 時表示兩個權值完全相關，取值為0 時表示不相關，取值為-1 時表示成反相關。

對于式（6），SR是斯皮爾曼等級相關系數，它是用來衡量兩個相關系數之間的相似度的。ri代表特征i在r中的等級，表示特征i在中的等級，它們的取值范圍為［-1，1］，取值為1 時表示兩個排名是相同的，取值為0 時表示兩個等級之間沒有相關性，取值為-1 時表示它們之間順序完全相反。

對于式（7），Ss為Tanimoto（又稱廣義Jaccard系數）距離，它是用來度量兩個特征子集間的相似度的。Ss取值范圍為［0，1］，取值為0 時表示兩個集合之間沒有交集，取值為1 時表示兩個集合完全一樣。

對表1 中的數據集利用bootstrapping［19］重采樣技術，對5 組數據集各選取一半的特征進行實驗，得出了每組數據的穩定性評估實驗結果（見表3～表7）。

從表3 可以看出，對于Snoar 數據集，約束分特征選擇法在Sonar 數據的穩定性上表現最好，三項評估標準均高于其他幾種方法，OneR 方法的穩定性最差。在表4中，對于Ionosphere數據集，Correlation 方法和約束分特征選擇法穩定性表現最好，最差的是SymmetricalUncert 方法。從表5 可以看出，對于Vehicle 數據集，同樣的是約束分特征選擇法的穩定性最好，接著是ReliefF 算法，表現最差的是OneR 方法。在表6 中，對于RS 數據集，Correlation方法穩定性最好，最差的是約束分特征選擇法。從表7可以看出，對于EnAudio數據集，穩定性表現最好的是約束分特征選擇法，GainRatio 方法的穩定性最差。

影響特征選擇方法穩定性主要有三個原因：小樣本容量、樣本順序和數據分割。在實驗中，可能是由于環境音數據集的樣本容量較大，所以它的穩定性較高，但是具體影響因素仍待進一步研究。

表3 幾種方法在Snoar上的穩定性比較

表4 幾種方法在Ionosphere上的穩定性比較

表5 幾種方法在Vehicle上的穩定性比較

表6 幾種方法在RS上的穩定性比較

表7 幾種方法在EnAudio上的穩定性比較

5 結語

本文通過利用約束分特征選擇法與其他6 種方法做對比，通過最優特征子集的選擇和穩定性的比較，對UCI 的3 組數據集和另外的兩組遙感數據集和環境音數據集，分別做了測試。實驗結果表明，在選取到足夠的特征時，約束分特征選擇法還是能取得較好的效果的，尤其是在穩定性方面，與其他各種方法相比，其在多組數據集上均有較好的表現。

但約束分特征選擇法也存在較多問題，如算法運行效率低下，選取較少特征時，準確率不高的問題。下一步的工作，嘗試使用多種分類器集成［20］的方法來進一步改進約束分特征選擇法，來進一步提高其性能表現。