基于鄰域互信息的三支特征選擇

卓永泰，董又銘，高 燦

1.深圳大學(xué) 計算機(jī)與軟件學(xué)院，廣東 深圳 518060

2.廣東省智能信息處理重點實驗室（深圳大學(xué)），廣東 深圳 518060

現(xiàn)實問題數(shù)據(jù)，如文本語音或圖像，通常包含較多的特征，然而過多的特征將導(dǎo)致計算速度慢、可解釋性差和模型過擬合等問題。特征選擇能在保持?jǐn)?shù)據(jù)的分類能力不變的條件下有效去除數(shù)據(jù)的冗余和不相關(guān)特征，因此成為機(jī)器學(xué)習(xí)、模式識別和數(shù)據(jù)挖掘的重要預(yù)處理過程[1]。

互信息是一種有效的不確定性度量方法，其能夠依據(jù)變量的概率分布，來衡量變量間互相依賴的程度。傳統(tǒng)互信息主要適用于度量離散型隨機(jī)變量，而現(xiàn)實中往往存在大量連續(xù)型變量，需對連續(xù)型變量離散化，然而離散化將造成原始數(shù)據(jù)的信息損失。針對該問題，Hu等[2]提出了鄰域互信息概念，能直接處理連續(xù)型特征。Liu等[3]將鄰域互信息與粒子群優(yōu)化算法結(jié)合，獲得了更好的特征選擇效果。Lin等[4]在一般鄰域互信息的基礎(chǔ)上拓展了三種適用于多標(biāo)簽學(xué)習(xí)的鄰域互信息。Wang等[5]基于鄰域互信息，提出了一種對標(biāo)簽缺失數(shù)據(jù)進(jìn)行多標(biāo)簽特征選擇的算法。Liu等[6]提出了局部鄰域互信息概念。Sun等[7]將多標(biāo)簽ReliefF和鄰域互信息結(jié)合，提高了特征選擇算法的穩(wěn)定性和預(yù)測精度。

雖然以上方法利用鄰域互信息獲得了較好的特征選擇效果，但均采用了貪婪策略。貪婪策略并不能保證找到一個最小的特征子集，其搜索過程有可能向著更大的特征子集的方向發(fā)展。三支決策理論[8-9]是一種處理不確定信息的有效方法，在不確定決策及近似推理中有著重要的應(yīng)用。李嫻等[10]將三支決策理論應(yīng)用于圖神經(jīng)網(wǎng)絡(luò)推薦算法，提高了推薦質(zhì)量。胡峰等[11]將三支決策理論應(yīng)用于不平衡數(shù)據(jù)過采樣，有效解決了不平衡數(shù)據(jù)的二分類問題。本文將三支決策思想引入特征選擇，以達(dá)到原始特征的鄰域互信息為迭代終止條件，利用鄰域互信息度量迭代，拓展生成三個具有差異性的特征子集，以保證特征選擇有更大的機(jī)會選擇到最優(yōu)特征子集。同時對三個特征子集進(jìn)行集成，構(gòu)建了三支協(xié)同決策模型，以獲得更好的分類學(xué)習(xí)效果。UCI實驗結(jié)果顯示了模型的有效性。

1 基本知識

1.1 互信息

假設(shè)離散隨機(jī)變量為A={a1,a2,…,an}，記p(ai)為A=ai發(fā)生的概率，則A的信息熵為：

假設(shè)兩離散隨機(jī)變量為A={a1,a2,…,an}，B={b1,b2,…,bm}，記p( ai,bj)為A=ai,B=bj同時發(fā)生的概率，則A、B的聯(lián)合熵為：

已知變量B的取值，A的條件熵為：

A和B的互信息為：

1.2 鄰域粗糙集

給定樣本集合U={ x1,x2,…,xn},xi∈RN,Δ表示為RN上的距離，通常使用歐氏距離。對于U上的任意樣本xi，其δ鄰域定義為：

如δ()xi中的所有樣本決策值都相同，則xi在δ鄰域內(nèi)一致，否則稱為不一致樣本。

給定鄰域決策信息系統(tǒng)NDS=(U,C?D,δ)，假設(shè)決策特征D將U劃分為m個等價類D1,D2,…,Dm，則決策類Dj相對于條件特征集合C的鄰域下近似和上近似分別表示為：

則所有決策類的下近似和上近似分別為：

邊界為：

由于NC()D=U，當(dāng)決策特征D的下近似越大，邊界越小，當(dāng)前所選的特征子集S?C則可以更加精確地描述此分類任務(wù)。因此可將定義為決策特征D對特征子集S的依賴度，依賴度越大，說明特征子集S的描述能力越強。

1.3 鄰域互信息

給定鄰域決策信息系統(tǒng)NDS=(U,C?D,δ)，特征子集S的鄰域熵表示為：

給定另一特征子集R，聯(lián)合鄰域熵表示為：

已知特征子集S、R的條件鄰域熵表示為：

R、S的鄰域互信息表示為：

2 基于鄰域互信息的三支特征選擇

首先闡述啟發(fā)式鄰域互信息特征選擇策略存在的問題，其次描述利用三支決策的思想進(jìn)行特征選擇方法。

2.1 啟發(fā)式特征選擇

由于求取最小子集是NP難題，一般采用啟發(fā)式搜索算法獲取特征子集。文獻(xiàn)[2]設(shè)計了MD策略，其啟發(fā)式特征評價函數(shù)是：

其中，C為初始特征集合，S為已選擇的特征子集，D為決策特征，f為一個候選特征。

特征選擇的目的是在保持特征子集的描述能力的條件下，獲取具有最少特征的特征子集。MD采用貪心策略即每一步添加一個使得Ψ最大的候選特征，使特征子集與類別的互信息盡量快速地增加，其搜索只能保證局部最優(yōu)。選擇的特征子集可能偏大且存在冗余，特征子集的質(zhì)量難以保證。

2.2 基于三支決策的特征選擇

為了盡量避免貪心策略帶來的問題，使特征子集在整體上更優(yōu)，本文提出了基于三支決策的特征選擇策略。

在三支搜索中，一般每一層保持有3個特征子集，由它們分別生成排序前三的新特征子集，合計9個候選的特征子集。然后從這9個特征子集中再選擇排序前三，并且約束它們不來源于同一分支，以此作為下一層的3個特征子集。三支特征選擇最終將生成3個較優(yōu)的特征子集。

特征選擇并生成后繼的方法如式：

其中，C為條件特征集合，i表示分支的序號，則Si表示第i個分支已選擇的特征，fi表示第i分支的候選特征。

三支特征選擇的思路如圖1所示。圖中的圓形結(jié)點表示一個特征子集。實線箭頭指向的結(jié)點表示該特征子集將繼續(xù)拓展，虛線箭頭指向的結(jié)點表示該特征子集不拓展。結(jié)點G表示該特征子集已經(jīng)達(dá)到了停止條件。

三支特征選擇算法的具體描述如下：

算法1基于三支決策的特征選擇

輸入：鄰域決策信息系統(tǒng)NDS=U,C?D,δ，分支的數(shù)目w=3。

輸出：redlist-子集列表。

1.計算NMI( )

F;D，生成空列表Queue

2.從初始特征集F中選擇NMI前三大的特征分別構(gòu)成大小為1的3個特征子集，放入redlist

3.對redlist的尾部w個特征子集中的每一個特征子集S：

如果NMI(S;D)≥NMI(F;D)，轉(zhuǎn)步驟3.1；否則，轉(zhuǎn)步驟3.2

/*判斷特征子集是否滿足終止條件*/

3.1 將S移至redlist的頭部，w=w-1；如果w為0，輸出redlist

3.2 由S生成Ψ前三大的特征子集，放入Queue，將S從redlist中移除

4.從Queue中找到w個Ψ最大的不源自同一支的特征子集，放入redlist尾，清空Queue隊列，轉(zhuǎn)步驟3

算法首先從空集?開始，選擇NMI值前三大的特征構(gòu)成大小為1的特征子集。其次測試當(dāng)前各特征子集是否滿足終止條件，如果滿足條件則將該特征子集加入redlist；不滿足的特征子集分別拓展其Ψ最大的3個特征，合計形成w×3個新的特征子集。然后從這些特征子集中選擇Ψ最大的w個特征子集。為了保持差異性，算法約束w個特征子集不能來自同一個分支。算法不斷迭代以上過程，以達(dá)到原始特征的鄰域互信息為分支迭代終止條件，直到獲得3個滿足條件的特征子集。

設(shè)數(shù)據(jù)集有N個初始特征。在第k輪，一個特征子集已經(jīng)選擇了k個特征，計算剩余的N-k個特征的Ψ帶來的時間復(fù)雜度為O( )N-k。那么在最壞情況下，即所有特征都被選取的情況下，一個特征子集的總復(fù)雜度為，3個特征子集的總復(fù)雜度近似為O(N2)。

在獲得3個特征子集后，將3個特征子集分別構(gòu)建同質(zhì)學(xué)習(xí)器，形成三支協(xié)同決策模型，以獲得更好的學(xué)習(xí)性能。

3 實驗與結(jié)果

3.1 數(shù)據(jù)集和參數(shù)設(shè)置

實驗選用了12個UCI數(shù)據(jù)集，具體信息如表1所示。其中，有6個連續(xù)型數(shù)據(jù)集，2個離散型數(shù)據(jù)集，4個混合型數(shù)據(jù)集。在“特征數(shù)”一列中，括號內(nèi)的數(shù)值表示連續(xù)型特征的數(shù)量。在實驗中，對連續(xù)特征進(jìn)行歸一化，離散特征則進(jìn)行數(shù)值化預(yù)處理。有3個數(shù)據(jù)集包含有缺失值，對于連續(xù)型特征采用均值填充，離散型特征用眾數(shù)補全。

表1 實驗數(shù)據(jù)集Table 1 Experimental data sets

所有實驗采用10次隨機(jī)10折交叉驗證方法，實驗的平均結(jié)果作為數(shù)據(jù)集的最終性能。

根據(jù)文獻(xiàn)[2]實驗結(jié)果，基于鄰域互信息的方法在鄰域半徑取值[0.1，0.2]時提取的特征子集較好，本實驗鄰域半徑采用中間值0.15。因為NMI度量隨著特征的添加不具備單調(diào)性，所以設(shè)置算法停止條件為：特征子集的NMI大于等于初始特征集合的NMI時。根據(jù)文獻(xiàn)[12]的分析，NRS模型采用鄰域半徑0.125較優(yōu)，因此實驗中NRS模型采用的鄰域半徑參數(shù)為0.125。當(dāng)最優(yōu)重要度非正時，停止拓展，表示算法找到了目標(biāo)的特征子集。

3.2 特征選擇分析

在所選數(shù)據(jù)集上的特征提取結(jié)果如表2所示。在表2中，第2列表示原始數(shù)據(jù)集的特征數(shù)量，第3列表示NRS算法得到的特征子集的大小，第4列表示NMI-MD算法得到的特征子集的大小，第5列表示本文算法NMITWD得到的特征子集的大小，第6列NMI-TWD-Best表示本文算法得到的最小的特征子集的大小。第7列展示了NMI-TWD獲得的3個特征子集，加粗部分表示存在差異的特征。

表2 NMI-MD和NMI-TWD特征提取的結(jié)果Table 2 Results of feature selection of NMI-MD and NMI-TWD

本文提出的NMI-TWD算法在2個數(shù)據(jù)集中獲得了較NMI-MD更小的特征子集，在6個數(shù)據(jù)集中獲得了較NRS更小的特征子集。anneal、segment、cardio、family、genus數(shù)據(jù)集的3個特征子集僅存在特征順序上的差異。

3.3 算法性能對比分析

各算法所得特征子集分別利用KNN和SVM分類器進(jìn)行實驗。集成學(xué)習(xí)采用Stacking方法[13]，其元分類器采用LogisticRegression分類器（最大迭代次數(shù)10 000），LR將3個初級分類器輸出的3組預(yù)測概率水平堆疊在一起，再與原樣本的決策相結(jié)合作為新的樣本進(jìn)行學(xué)習(xí)。當(dāng)初級分類器為SVM時，通過CalibratedClassifierCV將SVM的預(yù)測轉(zhuǎn)化為概率形式，再交給元分類器學(xué)習(xí)。算法的性能取10次隨機(jī)10折交叉驗證的平均值。

在表3和表4中，第2列表示數(shù)據(jù)集不進(jìn)行特征選擇時的性能，第5至7列表示在指定分類器下三支特征選擇獲得的各特征子集的性能，第8列表示NMI-TWD算法獲得的3個特征子集通過集成后的性能。各數(shù)據(jù)集上的最優(yōu)性能加粗表示。另外，各方法在所選數(shù)據(jù)集上的平均性能在表格的“Avg”行顯示。

表3 KNN分類器的分類準(zhǔn)確率Table 3 Classification accuracy using KNN 單位：%

表4 SVM分類器的分類準(zhǔn)確率Table 4 Classification accuracy using SVM 單位：%

從表3和表4可見，NMI-TWD獲得了較NRS和MNIMD更好的分類性能。NMI-TWD基于三支決策的思想，利用鄰域互信息生成了3個具有一定差異的特征子集。這3個特征子集獨立來看，就已經(jīng)與其他方法的特征子集的分類性能相近，甚至有所提高。而這3個具有差異性的特征子集，可以從不同角度描述數(shù)據(jù)的本質(zhì)信息，對它們進(jìn)行三支協(xié)同學(xué)習(xí)能夠獲得更好的性能。

NMI-TWD的準(zhǔn)確率在anneal、segment、cardio、family、genus這5個數(shù)據(jù)集上較NMI-W1、NMI-W2、NMIW3上也有小幅提升。準(zhǔn)確率的提升主要源于Stacking方法集成機(jī)制，其元分類器可以對初級分類器難以區(qū)分的決策做進(jìn)一步的區(qū)分。

在KNN分類器下，NMI-TWD在所選的12個數(shù)據(jù)集中，有9個獲得了最高的性能。其性能較其他三種方法平均提升約7個百分點。在8個數(shù)據(jù)集中，NMI-TWD至少獲得了一個性能最優(yōu)的特征子集。在SVM分類器下，NMI-TWD在10個數(shù)據(jù)集中獲得了最高的性能，較其他三種方法平均提升約2.75個百分點。在6個數(shù)據(jù)集中，NMI-TWD至少獲得了一個性能最優(yōu)的特征子集。這說明了本文算法優(yōu)于NRS和NMI-MD，顯示了本文算法的有效性。

4 總結(jié)

本文將三支決策的思想引入基于鄰域互信息的特征選擇，在獲得較優(yōu)的特征子集的同時，通過集成學(xué)習(xí)進(jìn)一步提升了分類性能。UCI數(shù)據(jù)集上的實驗表明，本文方法在準(zhǔn)確率方面，優(yōu)于現(xiàn)有的鄰域粗糙集和鄰域互信息方法，說明了新方法的有效性。進(jìn)一步將嘗試研究新的連續(xù)特征重要性度量方法，同時對三支特征子集引入更好的多樣性，以進(jìn)一步提升三支特征選擇的性能。