基于條件信息熵的超高維分類數(shù)據(jù)特征篩選

程國勝，孫超男，宋鳳麗，來 鵬

（南京信息工程大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，南京 210044）

0 引言

隨著現(xiàn)代技術(shù)的迅猛發(fā)展，大量的高維數(shù)據(jù)出現(xiàn)在各類領(lǐng)域中，比如生物影像、高頻時間序列數(shù)據(jù)、腫瘤分類和經(jīng)濟預(yù)測等。在這些高維分類數(shù)據(jù)中，變量的個數(shù)p遠(yuǎn)大于樣本量n，這種情形被稱作“大p小n”。在高維數(shù)據(jù)分析中，經(jīng)常引用稀疏性假設(shè)，即假設(shè)只有少量的協(xié)變量與響應(yīng)變量相關(guān)，基于這樣的假設(shè)，研究者們提出了一系列正則化的方法用于解決一般的高維回歸分析，例如lasso[1]、SCAD[2]、elastic net[3]等方法。但這些方法均是處理當(dāng) p適中的情形，當(dāng)處理超高維數(shù)據(jù)時，在計算花費、統(tǒng)計準(zhǔn)確性和算法穩(wěn)定性方面都面臨很大的問題。受到這些挑戰(zhàn)的啟發(fā)，研究者們嘗試把邊緣特征篩選應(yīng)用在超高維數(shù)據(jù)中，通過簡便快速的方法進行超高維數(shù)據(jù)的初步降維，然后再利用一般的高維降維方法進行分析處理。Fan和Lv[4]提出用Pearson相關(guān)系數(shù)來進行特征篩選，并且證明了在線性模型假設(shè)下該方法具有確定篩選性質(zhì)。Li等[5]提出根據(jù)距離相關(guān)系數(shù)將協(xié)變量排序，并證明出該方法（DC-SIS）在自由模型下同樣具有確定篩選性質(zhì)。Mai等[6]針對兩類判別分析問題，提出基于Kolmogorov距離進行超高維變量特征篩選的方法，并且在模型假設(shè)很弱的情況下仍然具有確定篩選性質(zhì)。Huang等[7]針對協(xié)變量與響應(yīng)變量均為多類別變量的問題，提出一種基于自由模型用Pearson卡方檢驗進行特征篩選的方法，該方法具有確定篩選性質(zhì)。

目前，大多數(shù)超高維變量篩選的文獻都是基于協(xié)變量與響應(yīng)變量之間的相關(guān)性構(gòu)造相應(yīng)的統(tǒng)計量來度量變量間是否獨立，是否存在關(guān)聯(lián)。Shannon[8]將信息熵和交互信息應(yīng)用到信息論中，信息熵值越高意味著系統(tǒng)具有越高的不確定性或者可變性。2011年，Reshef等[9]在《Science》上發(fā)表了基于互信息進行相關(guān)性分析的文章，可有效地刻畫了變量之間的非線性關(guān)系。于是，Ni等[10]提出一種基于互信息的超高維多類別變量的特征篩選方法，體現(xiàn)出互信息作為度量變量之間的非線性的有效性。

本文提出一種基于條件信息熵進行重要變量的篩選方法，從信息量的角度來構(gòu)造相應(yīng)的統(tǒng)計量進行相關(guān)性分析，證明了在自由模型下該方法具有確定篩選性質(zhì)，且具有計算簡單快速的優(yōu)點。從模擬的結(jié)果來看，針對響應(yīng)變量與協(xié)變量均為離散型類別數(shù)據(jù)，篩選結(jié)果相對于其他一些方法有更好的效果。

1 條件信息熵（CIES）

眾所周知，在信息系統(tǒng)中，信息熵是描述信息內(nèi)容的有效方法。德國物理學(xué)家Clausius在1850年首次提出用熵來測量空間中能量分布的均勻程度，能量分布越均勻，那么對應(yīng)的熵值越大[11]。根據(jù)該原理，信息熵之父Shanon提出用信息熵來描述平均信息量[8]，同時也用數(shù)學(xué)語言對信息熵進行了描述，即離散型隨機變量X的信息熵為，其中 pk為隨機變量 X=xk的概率pk=P（X=xk）。本文提出用條件信息熵來衡量給定響應(yīng)變量條件下，協(xié)變量所包含的信息量，進一步篩選出與響應(yīng)變量相關(guān)性較強的協(xié)變量。

設(shè)響應(yīng)變量Y 為二元變量，即Y=0，1,且 X=(X1，X2，…，Xp)T為 p維協(xié)變量，由于變量維數(shù) p關(guān)于樣本量n成指數(shù)型增長要從這p維協(xié)變量中篩選出與響應(yīng)變量Y相關(guān)性比較強的變量。通常會有稀疏性假設(shè)，即假設(shè)只有少量協(xié)變量與響應(yīng)變量相關(guān)。設(shè)重要變量子集和不重要變量子集分別為D和Dc為重要變量集合的大小，其中 D={j:對某些Y=y，Xj與 F(Y|y)相關(guān)}，

本文利用信息熵從信息量的角度出發(fā)來討論協(xié)變量Xj與響應(yīng)變量Y之間的相關(guān)性。協(xié)變量Xj的信息熵為其中pj，l=P(Xj=l),j=1，…，p;l=1，…，L為協(xié)變量Xj的概率分布。相應(yīng)地，給定Y條件下Xj的條件信息熵H(Xj|Y)為：

其中 pj，ly=P(Xj=l|Y=y)表示給定Y=y條件下 Xj=l的條件概率分布。

據(jù)此，定義如下的篩選指標(biāo)來衡量Xj與Y之間的獨立性：

從信息熵角度考慮，如果協(xié)變量Xj與響應(yīng)變量Y獨立，則有給定Y=0條件下Xj的條件信息熵與給定Y=1條件下Xj的條件信息熵相等，即ωj=0；如果不獨立，則有ωj＞0。因此可以根據(jù)ωj的大小來篩選與響應(yīng)變量相關(guān)性較強的協(xié)變量。為了計算ωj，需要給出其樣本估計量。假設(shè)給定n組觀測值，有：

其中dn為預(yù)設(shè)的模型大小，滿足dn≤n。在一些特征篩選文章中，閾值dn一般設(shè)為[n/logn]，其中[a]表示a的整數(shù)部分。

為了驗證簡化模型D是否包含所有真實的重要協(xié)變量，下面研究條件信息熵篩選（CIES）的確定篩選性質(zhì)。首先，建立確定篩選性質(zhì)需滿足以下三個正則化條件：

（C1）協(xié)變量 X的維數(shù) p和樣本量n滿足logp=na，其中

（C2）存在兩個正常數(shù)0＜c1＜c2＜1使得

注：Cui,H.等[12]在所寫的超高維自由模型判別分析文章中也做出了（C2）同樣的假設(shè)，該條件確保響應(yīng)變量Y和協(xié)變量X每個類別的比例不會太小也不會太大。（C3）這類型的假設(shè)條件在特征篩選文獻中非常典型，例如文獻[12]中的（C2）都是這類的假設(shè)。

定理 1（確定篩選性）:在（C1）、（C2）條件下。對0≤τ＜1/2，存在正常數(shù)c有：

其中p為協(xié)變量X的維數(shù)，n為樣本量，L為變量Xj的類別數(shù)。

2 數(shù)值模擬

協(xié)變量X為離散型變量，響應(yīng)變量Y為服從均勻分布的兩類別離散型變量，真實模型D={1 ，2，3} ，設(shè)定預(yù)測模型大小。在給定 yi=r的條件下，定義相關(guān)的類別變量概率為r=1，2，1≤k≤d0，表1給出了 θrk的取值。對于任意的r=1，2，d0＜k≤p，設(shè) θrk=0.5。分別考慮 n=100;150;200，p=1000;2000幾種情形。

表1 模擬的參數(shù)設(shè)定

本文通過以下準(zhǔn)則將CIES的模擬效果與PC-SIS、IG-SIS進行比較：MMS，即包含所有重要變量的最小模型大小；P，當(dāng)估計模型大小為12時，其包含所有重要變量的概率。

表2（見下頁）給出了三種方法模擬500次，5%，25%，50%，75%，95%分位點的MMS值，以及所選模型包含所有真實重要變量的覆蓋比。從模擬結(jié)果來看，CIES方法的模擬效果比較好，隨著樣本量n的增加，MMS值更加接近真實模型大小，并且覆蓋比P趨近于1。對于兩類別的離散型協(xié)變量，CIES方法的效果相對于PC-SIS、IG-SIS方法好一些，尤其是當(dāng)樣本量較少時，CIES方法更加適合用來進行超高維特征篩選。

3 定理證明

為了證明定理1，首先介紹下面的引理。

引理1（Hoeffding’s不等式）：設(shè) X1，X2，…，Xn為獨立隨機變量。假設(shè)，其中ai，bi為常數(shù)。設(shè)，則對于正常數(shù)t有下面的等式成立：

表2 模擬結(jié)果

引理2：假設(shè)a和b為兩個有界隨機變量，也就是說，存在常數(shù)M1＞0,M2＞0使得。給定樣本大小分別為a和b的估計值。假設(shè)對于，存在正常數(shù) c1，c2和 s，使得：

此外，假設(shè) b有界且不為0，即存在 M3＞0使得，那么有：

c5和M4均為正常數(shù)，且在證明中有所定義。

對定理1的證明：根據(jù)ωj和的定義，有：

那么有：

下面來證明如下不等式：

利用每類樣本的頻率來估計概率，這樣有：

此外，有：

結(jié)合式（4）和式（5），進一步有：

根據(jù)引理2，證明將進一步轉(zhuǎn)化為證明Sn，Tn為sn，tn的估計值。由引理1，可得：

因此對于概率函數(shù) p*及其估計值 p*，有 p*依概率收斂到 p*。同樣可以證明logp*依概率收斂到logp*：

同樣地，可以簡單地證明Ej2部分，有：

因此：

對0≤τ＜1/2，存在正常數(shù) c，當(dāng)0＜a＜1-2τ時隨著n→+∞有

4 結(jié)論

本文提出了一種基于條件信息熵進行超高維自由模型特征篩選的方法，證明其具有確定篩選性質(zhì)。從模擬的結(jié)果來看，當(dāng)協(xié)變量X和響應(yīng)變量Y均為兩類別時，此方法相對于其他篩選方法有更好的篩選效果。在后續(xù)的工作中，將考慮協(xié)變量X和響應(yīng)變量Y均為多類別離散型隨機變量或者連續(xù)型隨機變量的情形，嘗試用區(qū)間分割將變量離散化，基于條件信息熵進行超高維特征篩選。

參考文獻：

[1]Tibshirani R.Regression Shrinkage and Selection via the Lasso[J].Joumal of the Royal Statistical Society,1996,58(1).

[2]Fan J Q,Li R Z.Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties[J].Journal of the American Statistical Association,2001,(96).

[3]Zou H.Hastie T.Regularization and Variable Selection Via the Elastic Net[J].Journal of the Royal Statistical Society,2005,67(2).

[4]Fan J Q,Lü J C.Sure Independence Screening for Ultrahigh Dimensional Feature Space[J].Journal of the Royal Statistical Society,2008,70(5).

[5]Li R,Zhong W,Zhu L.Feature Screening via Distance Correlation Learning[J]Journal of the American Statistical Association,2012,107(499).

[6]Mai Q,Zou H.The Kolmogorov Filter for Variable Screening in High-dimensional Binary Classification[J].Biometrika,2013,(1).

[7]Huang D,Li R,Wang H.Feature Screening for Ultrahigh Dimensional Categorical Data With Applications[J].Journal of Business&Economic Statistics,2014,32(2).

[8]Shannon C E.A Mathematical Theory of Communication[M].New York:McGraw-Hill,1974.

[9]Reshef D N,Reshef Y A,Finucane H K,et al.Detecting Novel Associations in Large Data Sets[J].Science,2011,(344).

[10]Ni L,Fang F.Entropy-based Model-free Feature Screening for Ultrahigh-dimensional Multiclass Classification[J].Journal of Nonparametric Statistics,2016.

[11]Clausius R.Ueberverschiedene Fur Die an Wendungbequenme formen der Hauptgleichungen der Mechanischenwarmetheorie[J].Annalen Der Physik,2006,201(7).

[12]Cui H,Li R,Zhong W.Model-Free Feature Screening for Ultrahigh Dimensional Discriminant Analysis[J].Journal of the American Statistical Association,2015,110(510).