基于條件信息熵的超高維分類數據特征篩選

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

（南京信息工程大學 數學與統計學院，南京 210044）

0 引言

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

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

本文提出一種基于條件信息熵進行重要變量的篩選方法，從信息量的角度來構造相應的統計量進行相關性分析，證明了在自由模型下該方法具有確定篩選性質，且具有計算簡單快速的優點。從模擬的結果來看，針對響應變量與協變量均為離散型類別數據，篩選結果相對于其他一些方法有更好的效果。

1 條件信息熵（CIES）

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

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

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

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

據此，定義如下的篩選指標來衡量Xj與Y之間的獨立性：

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

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

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

（C1）協變量 X的維數 p和樣本量n滿足logp=na，其中

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

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

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

其中p為協變量X的維數，n為樣本量，L為變量Xj的類別數。

2 數值模擬

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

表1 模擬的參數設定

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

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

3 定理證明

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

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

表2 模擬結果

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

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

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

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

那么有：

下面來證明如下不等式：

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

此外，有：

結合式（4）和式（5），進一步有：

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

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

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

因此：

對0≤τ＜1/2，存在正常數 c，當0＜a＜1-2τ時隨著n→+∞有

4 結論

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

參考文獻：

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