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

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

0 引言

隨著現(xiàn)代技術(shù)的迅猛發(fā)展，大量的高維數(shù)據(jù)出現(xiàn)在各類領(lǐng)域中，比如生物影像、高頻時間序列數(shù)據(jù)、腫瘤分類和經(jīng)濟(jì)預(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ù)中，通過簡便快速的方法進(jìn)行超高維數(shù)據(jù)的初步降維，然后再利用一般的高維降維方法進(jìn)行分析處理。Fan和Lv[4]提出用Pearson相關(guān)系數(shù)來進(jìn)行特征篩選，并且證明了在線性模型假設(shè)下該方法具有確定篩選性質(zhì)。Li等[5]提出根據(jù)距離相關(guān)系數(shù)將協(xié)變量排序，并證明出該方法（DC-SIS）在自由模型下同樣具有確定篩選性質(zhì)。Mai等[6]針對兩類判別分析問題，提出基于Kolmogorov距離進(jìn)行超高維變量特征篩選的方法，并且在模型假設(shè)很弱的情況下仍然具有確定篩選性質(zhì)。Huang等[7]針對協(xié)變量與響應(yīng)變量均為多類別變量的問題，提出一種基于自由模型用Pearson卡方檢驗進(jìn)行特征篩選的方法，該方法具有確定篩選性質(zhì)。

目前，大多數(shù)超高維變量篩選的文獻(xiàn)都是基于協(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ā)表了基于互信息進(jìn)行相關(guān)性分析的文章，可有效地刻畫了變量之間的非線性關(guān)系。于是，Ni等[10]提出一種基于互信息的超高維多類別變量的特征篩選方法，體現(xiàn)出互信息作為度量變量之間的非線性的有效性。

本文提出一種基于條件信息熵進(jìn)行重要變量的篩選方法，從信息量的角度來構(gòu)造相應(yīng)的統(tǒng)計量進(jìn)行相關(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é)語言對信息熵進(jìn)行了描述，即離散型隨機(jī)變量X的信息熵為，其中 pk為隨機(jī)變量 X=xk的概率pk=P（X=xk）。本文提出用條件信息熵來衡量給定響應(yīng)變量條件下，協(xié)變量所包含的信息量，進(jìn)一步篩選出與響應(yīng)變量相關(guān)性較強(qiáng)的協(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)性比較強(qiáng)的變量。通常會有稀疏性假設(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)性較強(qiáng)的協(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è)條件在特征篩選文獻(xiàn)中非常典型，例如文獻(xiàn)[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進(jìn)行比較：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方法更加適合用來進(jìn)行超高維特征篩選。

3 定理證明

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

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

表2 模擬結(jié)果

引理2：假設(shè)a和b為兩個有界隨機(jī)變量，也就是說，存在常數(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ìn)一步有：

根據(jù)引理2，證明將進(jìn)一步轉(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é)論

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

參考文獻(xiàn)：

[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).