面向單調(diào)特征選擇的改進(jìn)模糊排序互信息

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

1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065

2.西南交通大學(xué)計(jì)算機(jī)與人工智能學(xué)院，成都611756

從不同決策值之間是否存在有序結(jié)構(gòu)的角度，可將分類問(wèn)題分為有序分類及名義分類[1]。對(duì)于有序分類任務(wù)，不同決策值之間存在著有序關(guān)系。例如，學(xué)生的成績(jī)可以分為5 個(gè)等級(jí)，分別是不合格、合格、中等、良好、優(yōu)秀，在這5 個(gè)等級(jí)中存在有序關(guān)系，優(yōu)秀表示最好的等級(jí)，而不合格則是最差的等級(jí)。當(dāng)兩個(gè)樣本的條件特征值存在優(yōu)劣關(guān)系，并且其決策特征值也存在對(duì)應(yīng)的優(yōu)劣關(guān)系，那么這兩個(gè)樣本之間存在單調(diào)約束。在有序分類的基礎(chǔ)上，假設(shè)所有條件特征與決策特征之間都存在單調(diào)性依賴約束，那么該有序分類問(wèn)題稱為單調(diào)分類問(wèn)題。單調(diào)分類任務(wù)廣泛存在于信用評(píng)價(jià)、醫(yī)療診斷、風(fēng)險(xiǎn)評(píng)估等決策領(lǐng)域，具有重要的研究意義和實(shí)際應(yīng)用價(jià)值。

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

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

1 基本概念

本章介紹了單調(diào)有序分類、有序關(guān)系以及模糊排序互信息等相關(guān)基本概念。

1.1 單調(diào)有序分類

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

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

?xi∈U，樣本xi關(guān)于決策特征D的有序信息?？杀硎緸椋?/p>

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

（2）當(dāng)v(xi,a)=v(xj,a)時(shí)，rij=0.5；

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

使用Logsig Sigmoid 函數(shù)來(lái)計(jì)算樣本xi和xj之間的有序隸屬度rij：

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

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

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

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

2 單調(diào)分類決策系統(tǒng)中的模糊排序互信息

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

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

因此，模糊條件排序熵能夠?qū)憺槿缦滦问剑?/p>

由上述討論可以看出函數(shù)g(x,y)分別關(guān)于兩個(gè)變量單調(diào)遞增。

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

為了比較5種模型的具體預(yù)測(cè)精度，采用均方差(Mean Square Error， MSE)和決定系數(shù)(Determination Coefficient， R2)作為模型的評(píng)價(jià)指標(biāo)。MSE是預(yù)測(cè)數(shù)據(jù)和原始數(shù)據(jù)對(duì)應(yīng)點(diǎn)誤差的平方和的均值，MSE越接近于0，代表數(shù)據(jù)預(yù)測(cè)結(jié)果越精確。R2是通過(guò)數(shù)據(jù)的變化來(lái)表示擬合結(jié)果的好壞，R2越接近于1，代表輸入變量對(duì)輸出變量的解釋能力越強(qiáng)，對(duì)數(shù)據(jù)擬合的效果也越好。

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

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

3 特征選擇的模糊排序互信息準(zhǔn)則

本章首先討論單調(diào)分類決策系統(tǒng)中模糊排序互信息用于特征選擇的有效性，接下來(lái)介紹基于模糊排序互信息的特征選擇算法。

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

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

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

上述章節(jié)提出了用于單調(diào)分類決策系統(tǒng)的基于模糊排序互信息的特征度量準(zhǔn)則，接下來(lái)討論基于該準(zhǔn)則的特征選擇算法。

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

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

算法1模糊決策系統(tǒng)的特征排序

算法2選擇最優(yōu)特征子集的Wrapper算法

輸出：最優(yōu)特征子集B*。

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

2.fork=1 tondo

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

4.在給定分類器下計(jì)算數(shù)據(jù)集DSk的分類性能

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

6.令B*=Bk0

7.返回B*

4 實(shí)驗(yàn)分析

本章將通過(guò)實(shí)驗(yàn)驗(yàn)證所提方法的有效性及高效性。本文將第3 章提出的評(píng)價(jià)準(zhǔn)則nFRMI與Hu 等提出的FRMI進(jìn)行比較。

在接下來(lái)的實(shí)驗(yàn)部分，本文共使用兩種單調(diào)分類器對(duì)所提方法的分類精度進(jìn)行性能評(píng)測(cè)，分別是OLM（ordered learning model）[18]和OCC（ordinal class classifier），均在Weka 中得以實(shí)現(xiàn)。這兩種分類器用于在Wrapper 階段計(jì)算特征子集的分類性能，并由此選擇出具有最優(yōu)分類性能的特征子集。

本章的所有實(shí)驗(yàn)均采用10 折交叉驗(yàn)證法，將數(shù)據(jù)集分為10 份，輪流將其中9 份用作訓(xùn)練數(shù)據(jù)，剩余1 份用作測(cè)試數(shù)據(jù)。每次測(cè)試將得到對(duì)應(yīng)的分類精度。10 次測(cè)試的結(jié)果平均值作為最終的算法評(píng)價(jià)指標(biāo)。本文選取了4 組單調(diào)分類數(shù)據(jù)集進(jìn)行性能實(shí)驗(yàn)，數(shù)據(jù)集詳細(xì)信息如表1 所示。

表1 數(shù)據(jù)集描述Table 1 Description of datasets

表2 和表3 的數(shù)據(jù)描述了本文算法與對(duì)比算法在不同單調(diào)分類器作用下所得到的最優(yōu)特征子集在10折交叉驗(yàn)證中的平均分類精度及標(biāo)準(zhǔn)差，每行中的最優(yōu)分類精度用粗體表示。FRMI表示該列實(shí)驗(yàn)結(jié)果是基于Hu等所提出的度量函數(shù)的特征選擇算法所得到的，nFRMI則表示實(shí)驗(yàn)結(jié)果是基于本文算法得到的。

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

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

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

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

圖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 結(jié)束語(yǔ)

本文針對(duì)單調(diào)有序分類任務(wù)，提出了一種新穎的基于改進(jìn)模糊排序互信息的特征選擇算法，該算法能夠有效克服已存在的模糊排序互信息在不一致性單調(diào)分類任務(wù)中不滿足單調(diào)性約束的缺點(diǎn)。在特征選擇過(guò)程中，使用最大相關(guān)最小冗余準(zhǔn)則來(lái)確保所選特征之間的低冗余以及與決策特征之間的高相關(guān)性。實(shí)驗(yàn)部分，將本文算法與基于傳統(tǒng)模糊排序互信息的特征選擇算法在四個(gè)不一致性單調(diào)分類數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，分析了兩種算法得到的特征子集在兩種單調(diào)分類器OLM 和OCC 下的分類精度性能比較。實(shí)驗(yàn)結(jié)果表明，與基于已存在模糊排序互信息的特征選擇算法相比，本文算法在大部分?jǐn)?shù)據(jù)集下能得到更優(yōu)的分類精度，因此本文算法對(duì)于不一致性單調(diào)分類任務(wù)是有效的。

在后續(xù)工作中，將對(duì)本文所提出的改進(jìn)模糊排序互信息在噪聲數(shù)據(jù)干擾下的魯棒性問(wèn)題進(jìn)行分析。并針對(duì)所提算法的計(jì)算效率問(wèn)題進(jìn)行優(yōu)化，將其進(jìn)一步擴(kuò)展到面向動(dòng)態(tài)單調(diào)分類的高效特征選擇。