面向單調特征選擇的改進模糊排序互信息

皮 洪，羅 川+，李天瑞，陳紅梅

1.四川大學計算機學院，成都610065

2.西南交通大學計算機與人工智能學院，成都611756

從不同決策值之間是否存在有序結構的角度，可將分類問題分為有序分類及名義分類[1]。對于有序分類任務，不同決策值之間存在著有序關系。例如，學生的成績可以分為5 個等級，分別是不合格、合格、中等、良好、優秀，在這5 個等級中存在有序關系，優秀表示最好的等級，而不合格則是最差的等級。當兩個樣本的條件特征值存在優劣關系，并且其決策特征值也存在對應的優劣關系，那么這兩個樣本之間存在單調約束。在有序分類的基礎上，假設所有條件特征與決策特征之間都存在單調性依賴約束，那么該有序分類問題稱為單調分類問題。單調分類任務廣泛存在于信用評價、醫療診斷、風險評估等決策領域，具有重要的研究意義和實際應用價值。

特征選擇是從原始特征中選擇最具類別辨識性的特征以降低特征維度的數據處理過程[2-4]。近年來，面向單調分類任務的特征選擇方法逐漸成為了人們關注的熱點問題，并取得了一些研究成果。Hu等將最大決策邊界準則引入到具有單調性約束的有序分類問題中，提出了基于ReliefF 和Simba 的單調特征選擇算法[5]。Pan 等定義了特征的單調依賴度并提出了通過使用梯度下降最大化模糊偏好依賴的特征選擇算法[6]?？紤]到同時含有名義分類特征和單調分類特征的異構有序分類問題，Pan 和Hu 進一步定義了基于異構單調分類一致性的特征相關性度量函數，并利用基因算法對異構單調數據集中的最優特征子集進行求解[7]。Villela 等基于最大決策邊界稀疏分類器，提出了一種基于容許有序搜索策略的包裹式有序特征選擇算法[8]。

互信息作為信息論中一種常用的度量，通常用于評估兩個隨機變量之間的相關性。在名義分類任務中，已經提出了大量基于互信息的特征選擇算法[2,9-13]。Qian 等針對不完備數據集提出了一種基于互信息的特征選擇算法，并證明了互信息的單調性[2]。Kwak等提出了一種計算連續輸入特征及離散輸出類別間的互信息的方法，并將其應用到輸入特征貪心選擇算法中[11]。Battiti探討了互信息準則在評估候選特征集的應用場景，并利用互信息準則來選擇一組具有高度代表性的特征，將其作為神經網絡分類器的輸入數據[12]。Peng 等結合mRMR（minimal-redundancymaximal-relevance）及其他方法（如包裝器）提出了一種兩階段的特征選擇方法，能夠以極低的代價選出一組具有高度代表性的特征[13]。為了將基于互信息的特征相關性度量準則引入到基于單調性約束的有序分類問題中，Hu 等定義了排序互信息（rank mutual information，RMI）及模糊排序互信息（fuzzy rank mutual information，FRMI），以評估單調分類任務中條件特征與決策特征之間的單調一致性，并基于這兩種度量提出了面向單調分類的特征選擇算法[1]。許行等在Hu 的算法的基礎上，首先利用雙向有序互信息生成不同的決策樹，然后集成其分類規則得到最終的決策結果[14]。然而，實際應用中由于低質信息的存在，使得單調分類任務中往往存在決策不一致性。Hu 等所定義的基于RMI 及FRMI 的特征一致性度量準則在處理不一致單調分類任務時不滿足特征集合與度量準則之間的單調性限制關系，進而影響特征重要性排序的啟發式搜索過程。鑒于此，本文在Hu 等提出的RMI 和FRMI 的基礎上提出了一種新穎的不一致單調分類中滿足單調性限制關系的模糊排序條件熵以及模糊排序互信息，并將這種模糊排序互信息與最大相關最小冗余準則結合起來，實現了不一致單調分類任務的特征選擇問題。在UCI 公開數據集上的仿真實驗進一步驗證了本文提出的特征選擇算法具有更好的單調分類性能。

1 基本概念

本章介紹了單調有序分類、有序關系以及模糊排序互信息等相關基本概念。

1.1 單調有序分類

在粗糙集理論中，三元組DS=U,A,D是一個決策系統，其中U被稱為論域，表示樣本的非空有限集合；A表示條件特征的非空有限集；D表示決策特征集。令決策特征集為D={d1,d2,…,dk}，若任意di∈D是名義型特征，則U,A,D是一個名義分類決策系統。若決策特征滿足關系d1＜d2＜…＜dk，則稱U,A,D是一個有序分類決策系統。進一步，若樣本的條件特征與決策特征之間存在單調約束關系，即對?x∈U，v(x,A)≤v(x′,A) 有f(x)≤f(x′)，其中v(x,A)表示樣本x在特征集A上的取值，f為決策函數。那么，就稱U,A,D是一個單調分類決策系統。為了便于討論，本文僅討論有序關系增加的相關問題。

?xi∈U，樣本xi關于特征子集B的有序信息?？杀硎緸椋?/p>

?xi∈U，樣本xi關于決策特征D的有序信息粒可表示為：

（1）當v(xi,a)＞v(xj,a)時，rij∈[0,0.5)；

（2）當v(xi,a)=v(xj,a)時，rij=0.5；

（3）當v(xi,a)＜v(xj,a)時，rij∈(0.5,1.0]。

使用Logsig Sigmoid 函數來計算樣本xi和xj之間的有序隸屬度rij：

樣本xi的模糊有序集可表示為：

其中，rij能夠反映樣本xi劣于xj的程度[15]。

1.2 已存在的模糊排序互信息

為了處理單調分類決策系統中的特征選擇問題，Hu 等[1]從信息論的角度定義了一種模糊排序條件熵和模糊排序互信息。

2 單調分類決策系統中的模糊排序互信息

本章將給出一種模糊排序互信息的定義，用于度量單調分類任務中的條件特征與決策特征間的單調一致性。這種新的定義能夠克服單調分類任務不一致時模糊排序互信息不單調的缺點[16-17]。

為了定義新的模糊排序互信息，本文首先給出新的模糊排序熵及模糊條件排序熵的定義以及相關性質。

因此，模糊條件排序熵能夠寫為如下形式：

由上述討論可以看出函數g(x,y)分別關于兩個變量單調遞增。

由上述兩式可得g′≥0 且g′單增。

為了比較5種模型的具體預測精度，采用均方差(Mean Square Error， MSE)和決定系數(Determination Coefficient， R2)作為模型的評價指標。MSE是預測數據和原始數據對應點誤差的平方和的均值，MSE越接近于0，代表數據預測結果越精確。R2是通過數據的變化來表示擬合結果的好壞，R2越接近于1，代表輸入變量對輸出變量的解釋能力越強，對數據擬合的效果也越好。

這與已有條件矛盾，故假設不成立，即D完全依賴于B。

在給出上述定義及性質后，下面將定義新的模糊排序互信息。

3 特征選擇的模糊排序互信息準則

本章首先討論單調分類決策系統中模糊排序互信息用于特征選擇的有效性，接下來介紹基于模糊排序互信息的特征選擇算法。

3.1 模糊排序互信息的有效性

從定理4 中可以得出新定義的模糊排序互信息在一致單調分類決策系統中及不一致單調分類決策系統中均滿足單調性。

3.2 基于模糊排序互信息的特征選擇算法

上述章節提出了用于單調分類決策系統的基于模糊排序互信息的特征度量準則，接下來討論基于該準則的特征選擇算法。

在特征選擇過程中，需要考慮兩方面：所選特征間的冗余度要盡可能小以及所選特征與決策特征之間的相關性要盡可能大。從相關性及冗余度的角度來說，最優的m個特征是與分類最相關的特征。但是最優m個特征之間可能存在冗余，因此最相關的m個特征不一定比其他m個特征得到更好的分類準確率。因此，特征選擇應該被分為兩個過程：如何度量特征與決策特征之間的相關性以及如何處理特征間的冗余性。特征相關性可以利用本文定義的模糊排序互信息來度量。第二個問題可由下述定義4 解決，即采用最大相關最小冗余（mRMR）準則來選擇當前第|B|+1個特征。

本文提出了一種兩階段的特征選擇算法。第一個階段根據特征評價函數對所有條件特征進行排序。將從候選特征集中選擇最大化e(aj)的特征。被選擇的特征與之前所選的特征冗余度小且與決策特征的相關性大。第一階段的具體過程見算法1。在第二個階段，利用算法2 選擇出一個最具類別辨識性的特征子集。該特征子集具有最好的分類性能。

算法1模糊決策系統的特征排序

算法2選擇最優特征子集的Wrapper算法

輸出：最優特征子集B*。

1.將B分為如下子集：B1={ai1},B2={ai1,ai2},Bn={ai1,ai2,…,ain}

2.fork=1 tondo

3.從數據集DS中移除不包含在Bk中的特征，并將這個新得到的數據集記為DSk

4.在給定分類器下計算數據集DSk的分類性能

5.從所有數據子集中選出分類性能最好的數據集DSk0

6.令B*=Bk0

7.返回B*

4 實驗分析

本章將通過實驗驗證所提方法的有效性及高效性。本文將第3 章提出的評價準則nFRMI與Hu 等提出的FRMI進行比較。

在接下來的實驗部分，本文共使用兩種單調分類器對所提方法的分類精度進行性能評測，分別是OLM（ordered learning model）[18]和OCC（ordinal class classifier），均在Weka 中得以實現。這兩種分類器用于在Wrapper 階段計算特征子集的分類性能，并由此選擇出具有最優分類性能的特征子集。

本章的所有實驗均采用10 折交叉驗證法，將數據集分為10 份，輪流將其中9 份用作訓練數據，剩余1 份用作測試數據。每次測試將得到對應的分類精度。10 次測試的結果平均值作為最終的算法評價指標。本文選取了4 組單調分類數據集進行性能實驗，數據集詳細信息如表1 所示。

表1 數據集描述Table 1 Description of datasets

表2 和表3 的數據描述了本文算法與對比算法在不同單調分類器作用下所得到的最優特征子集在10折交叉驗證中的平均分類精度及標準差，每行中的最優分類精度用粗體表示。FRMI表示該列實驗結果是基于Hu等所提出的度量函數的特征選擇算法所得到的，nFRMI則表示實驗結果是基于本文算法得到的。

表2 OLM 分類器下的分類精度比較Table 2 Comparison of classification accuracy by OLM 單位：%

表3 OCC 分類器下的分類精度比較Table 3 Comparison of classification accuracy by OCC 單位：%

從表2、表3 可以看出，分類器的選擇會影響最終的分類精度。當選擇分類器OLM 時，本文算法所得到的特征子集的分類精度在所有數據集上均優于原始數據集。與基于FRMI 的特征選擇算法相比，基于nFRMI 的特征選擇算法所得特征子集的分類精度在Crx、Ionosphere 及MachineCPU 三個數據集上是更優的，而在Pima 數據集上分類精度是相等的。當選擇OCC 分類器時，基于nFRMI 的特征子集的分類精度在所有數據集上均優于原始數據集。與FRMI 相比，nFRMI 在Ionosphere、MachineCPU 及Pima 數據集上分類精度更優。

圖1 和圖2 分別展示了采用不同特征選擇算法進行特征選擇時，隨著特征數量的增大基于OLM 和OCC 分類器的平均分類精度的變化趨勢。從實驗結果可以看出，除了OCC 分類器下的Crx 數據集，由基于nFRMI 的特征選擇算法所得特征子集的分類精度優于或等于基于FRMI 的特征選擇算法。另一方面，選用OLM 分類器的Ionosphere 數據集以及選用OCC分類器的MachineCPU 數據集，基于nFRMI 特征選擇算法得到的特征子集在特征個數及分類精度兩方面均優于基于FRMI 的特征選擇算法。從數據集Ionosphere 可以看出，在特征選擇的初始階段，nFRMI的分類精度劣于原始數據集。隨著特征選擇的進行，nFRMI 的分類精度整體呈現上升趨勢，直至優于原始數據集。從上述實驗結果可得，基于nFRMI的特征選擇算法在不同分類器、不同數據集下均能夠提升分類精度并降低數據維度，且在大部分數據集下分類精度優于傳統的基于FRMI的特征選擇算法。這表明本文算法對于面向不一致性單調分類任務的特征降維問題是有效的。

圖1 OLM 分類器下所選特征的分類精度比較Fig.1 Comparison of classification accuracies with different number of selected features by OLM

圖2 OCC 分類器下所選特征的分類精度比較Fig.2 Comparison of classification accuracies with different number of selected features by OCC

5 結束語

本文針對單調有序分類任務，提出了一種新穎的基于改進模糊排序互信息的特征選擇算法，該算法能夠有效克服已存在的模糊排序互信息在不一致性單調分類任務中不滿足單調性約束的缺點。在特征選擇過程中，使用最大相關最小冗余準則來確保所選特征之間的低冗余以及與決策特征之間的高相關性。實驗部分，將本文算法與基于傳統模糊排序互信息的特征選擇算法在四個不一致性單調分類數據集上進行了對比實驗，分析了兩種算法得到的特征子集在兩種單調分類器OLM 和OCC 下的分類精度性能比較。實驗結果表明，與基于已存在模糊排序互信息的特征選擇算法相比，本文算法在大部分數據集下能得到更優的分類精度，因此本文算法對于不一致性單調分類任務是有效的。

在后續工作中，將對本文所提出的改進模糊排序互信息在噪聲數據干擾下的魯棒性問題進行分析。并針對所提算法的計算效率問題進行優化，將其進一步擴展到面向動態單調分類的高效特征選擇。