來 鵬，孫 鑫，高羽飛，趙英序

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

0 引言

隨著網(wǎng)絡(luò)與通信技術(shù)的飛速發(fā)展，人們常會(huì)遇到各種超高維復(fù)雜數(shù)據(jù)問題，如證券市場(chǎng)的交易數(shù)據(jù)、X射線斷層攝影數(shù)據(jù)、生物基因表達(dá)數(shù)據(jù)、文檔詞頻數(shù)據(jù)等。在分析超高維數(shù)據(jù)問題時(shí)，最大的難點(diǎn)是隨著維數(shù)的膨脹，分析和處理數(shù)據(jù)的復(fù)雜度、成本以及所需的空間樣本數(shù)都將呈指數(shù)級(jí)增長(zhǎng)。傳統(tǒng)的多元統(tǒng)計(jì)方法在處理超高維數(shù)據(jù)問題時(shí)會(huì)遇到如計(jì)算效率無(wú)法滿足、計(jì)算存儲(chǔ)空間需求變高、傳統(tǒng)統(tǒng)計(jì)指標(biāo)不再適用、方法的假設(shè)條件不再滿足等困難，所以構(gòu)建適用于超高維數(shù)據(jù)的新統(tǒng)計(jì)方法是很有必要的。

特征篩選是目前最常見的處理超高維數(shù)據(jù)問題的手段之一，一般遵循“兩步走”的篩選過程：第一步在稀疏性假設(shè)下對(duì)超高維數(shù)據(jù)進(jìn)行大規(guī)模粗略的變量篩選，將超高維數(shù)據(jù)降到一個(gè)小得多的低維空間中；第二步再用傳統(tǒng)的統(tǒng)計(jì)方法進(jìn)行建模分析。由此可見，初步特征篩選的準(zhǔn)確降維直接影響到后續(xù)建模。Fan和Lv[1]、Fan等[2]、Fan和Song[3]、Fan等[4]、Liu等[5]在參數(shù)或半?yún)?shù)模型下提出了多種特征篩選方法。然而在超高維數(shù)據(jù)分析過程中，想要找到合適的模型是很困難的，因此，Li等[6]、He等[7]、Mai和Zou[8]提出了無(wú)模型下基于多種統(tǒng)計(jì)度量指標(biāo)的特征篩選方法。

在超高維數(shù)據(jù)分析中，有一類特殊的超高維數(shù)據(jù)類型，其響應(yīng)變量和協(xié)變量都為分類變量。對(duì)于該類問題，Huang等[9]提出了超高維分類數(shù)據(jù)的特征篩選方法Pearson卡方檢驗(yàn)算法（PC-SIS），對(duì)超高維數(shù)據(jù)，利用χ2統(tǒng)計(jì)量檢驗(yàn)協(xié)變量與響應(yīng)變量是否具有顯著的相關(guān)關(guān)系，即對(duì)指標(biāo)進(jìn)行排序。

盡管PC-SIS方法擁有很多優(yōu)點(diǎn)，但其不足也顯而易見：Pearson卡方檢驗(yàn)要求樣本量大于40，樣本量越大，得到的效果越好。然而實(shí)際情況中這些條件可能無(wú)法確保滿足，為了對(duì)其改進(jìn)，本文提出了似然比統(tǒng)計(jì)篩選方法（LR-SIS）。與PC-SIS相比，似然比統(tǒng)計(jì)量是反映靈敏度和特異度的復(fù)合指標(biāo)，不僅非常穩(wěn)定，而且可用于有20%以上的單元格的期望頻數(shù)小于5或者最小為1的樣本數(shù)據(jù)。此外，LR-SIS也是一種無(wú)模型算法，通過適當(dāng)分組變換可應(yīng)用于連續(xù)型變量的分組篩選問題。下文將給出LR-SIS特征篩選過程和漸近理論性質(zhì)，并通過蒙特卡羅數(shù)值模擬和實(shí)例分析進(jìn)行有限樣本研究。

1 似然比特征篩選（LR-SIS）

超高維數(shù)據(jù)中，變量維數(shù)p遠(yuǎn)大于樣本量n，通常只有少數(shù)的協(xié)變量與Y有關(guān)，滿足稀疏性假設(shè)。令Y∈{1，2，…，R} 表 示 具 有R類 的 離 散 分 類 變 量 ，X=(X1，X2，…，Xp)T∈Rp表示p維離散協(xié)變量，其中Xi可取值為{1，2，…，K}，i=1，…，p。超高維特征篩選關(guān)鍵在于通過分析協(xié)變量與響應(yīng)變量之間的邊際相關(guān)性，來篩選出可能的重要協(xié)變量進(jìn)行快速降維。為此，令F(y|X)為Y關(guān)于X的條件分布函數(shù)，定義重要變量集合與不重要變量集合分別為：

其中φy為Y的取值范圍。則變量篩選的目的，就是找到一個(gè)估計(jì)?使得D??且||盡可能小，其中||表示集合?中的元素個(gè)數(shù)。

為了改進(jìn)Huang等[9]所提出PC-SIS方法，本文提出了更穩(wěn)健的似然比統(tǒng)計(jì)量作為特征篩選指標(biāo)。定義，則似然比統(tǒng)計(jì)量可定義為：

若Xj與Y獨(dú)立，則P(Y=r|Xj=k)=P(Y=r)，那么ln(Pj，rk/Pr)=0，即wj=0。若響應(yīng)變量Y與協(xié)變量Xj不獨(dú)立，則存在某些r∈{1，2，…，R}使P(Y=r|Xj=k)≠P(Y=r)，即 ln(Pj，rk/Pr)≠0 ，從而wj≠0 。所以|wj|越大說明Xj與Y相關(guān)性越強(qiáng)，因此可以利用|wj|的值評(píng)估Xj的重要性。

利用隨機(jī)樣本{Yi，Xi=(Xi1，Xi2，…，Xip)T}，i=1，2，…，n，可求出wj的估計(jì)為：

接下來探討所提出特征篩選方法的理論性質(zhì)。為方便后續(xù)的證明，給出以下條件：

（C1）存在兩正數(shù) 0＜c1＜c2＜1，使的c1＜Pr，Pj，rk＜c2，1≤j≤p，1≤r≤R，1≤k≤K。

（C2）存在正數(shù)，使得 min∈Dj|wj|≥2cn-τ。

（C3）假設(shè)lnp≤na，0＜a＜1-2τ。

條件（C1）要求每個(gè)類別的響應(yīng)變量和協(xié)變量取值的概率都是有界的，因此排除了那些可能具有特定分類概率過大或過小的取值情況。條件（C2）要求所有重要變量的指標(biāo)最小值有下界，并隨樣本量趨向于無(wú)窮大時(shí)以n-τ的速度趨向于0，在Fan和Lv[1]的文章中也有相似的假設(shè)。條件（C3）允許特征維度p隨樣本量n呈指數(shù)級(jí)發(fā)散，表明了其超高維特性。

定理1（確定篩選性）：在條件（C1）至條件（C3）下，對(duì)于任意，有：

其中c3-c5為正數(shù)，sn為D的基數(shù)。

2 數(shù)值模擬

為了研究所提出似然比特征篩選方法LR-SIS的有限樣本性質(zhì)，本文將利用蒙特卡洛模擬，參考Ni和Fang[10]的例 1 對(duì) LR-SIS 方法與 SIS[1]、PC-SIS[9]、IG[10]、KF[8]等方法進(jìn)行比較。首先生成Yi∈{1，2，…，K}其中K=2，同時(shí)對(duì)于任意1≤k≤K，P(Yi=k)=1/k。同時(shí)生成二元協(xié)變量向量X={X1，X2，…，Xn} ，其中Xi={Xi1，Xi2，…，Xip}T，定義真實(shí)的重要變量集為D={1，…，10}，|D|=d0。在Yi的條件下，生成Xij滿足P(Xij=1|Yi=k)=θkj，1≤k≤K且j∈D，詳細(xì)數(shù)值見表1。其次，對(duì)于1≤k≤K且j?D，本文定義θkj=0.5。設(shè)協(xié)變量的維度p=2000，樣本量n=160，240，320。

表1 模擬所用參數(shù)規(guī)格

為了便于比較，仿照Ni和Fang[10]，定義下列結(jié)果評(píng)估標(biāo)準(zhǔn)：MMS，包含所有重要變量的最小模型尺寸；P，在給定模型尺寸為[n/logn]的情況下是否包含所有重要變量的指標(biāo)；MS，模型尺寸d，由Ni和Fang[10]中所提出的d值算法所得的篩選變量個(gè)數(shù)，其中dmin=1，dmax=n；dc表示被正確挑選出的重要變量的數(shù)量；di=d-dc表示被挑選出的不重要變量的數(shù)量；CZ，在所有p-d0個(gè)不重要變量中，沒有被挑選出的不重要變量所占的比例；IZ，在所有d0個(gè)重要變量中，沒有被正確篩選出的重要變量所占的比例；CP1，表明所選出的模型包含所有的重要變量的比率；CP2=dcd0，表示所篩選出的重要變量占所有重要變量的比率。

表2記錄了500次模擬中MMS的5%、25%、50%、75%和95%的分位數(shù)值以及其他評(píng)價(jià)指標(biāo)的平均值。從表2中可以看到當(dāng)樣本量和維數(shù)相同時(shí)，LR-SIS方法的效果最好，MMS中每個(gè)指標(biāo)都接近10，說明LR-SIS能夠更有效地篩選出所有重要的協(xié)變量；IG方法僅次于LR-SIS，與其他方法相比，其優(yōu)越性主要體現(xiàn)在篩選重要協(xié)變量的錯(cuò)誤率更低，PC-SIS與SIS效果近似，他們的優(yōu)勢(shì)在于具有較好的MMS指標(biāo)；KF方法的MMS結(jié)果比較差，但其篩選重要協(xié)變量的正確率更高。隨著樣本量n的不斷增大，LR-SIS方法在各指標(biāo)的收斂速度最快，與其他方法相比更加穩(wěn)定，計(jì)算效率較高。因此可見LR-SIS方法具有較顯著的優(yōu)越性。

表2 模擬結(jié)果

3 實(shí)例分析

在研究文本分類問題的過程當(dāng)中，特征篩選是最重要的環(huán)節(jié)之一，能夠降低特征向量空間維數(shù)，簡(jiǎn)化計(jì)算。本文從UCI機(jī)器學(xué)習(xí)庫(kù)收集到亞馬遜網(wǎng)站關(guān)于電影的大量評(píng)論（http://archive.ics.uci.edu/ml/datasets/Sentiment+Labelled+Sentences#）。該評(píng)論集中包含正面評(píng)論(Y=1)和負(fù)面評(píng)論(Y=0)（部分評(píng)價(jià)如表3所示）。則所要研究的問題為利用評(píng)論中出現(xiàn)來源于詞庫(kù)的關(guān)鍵詞X=(X1，…，Xp)T，來預(yù)測(cè)評(píng)論的類別Y，這是一個(gè)超高維文本分類問題。

表3 亞馬遜電影評(píng)論文本

經(jīng)過數(shù)據(jù)整理，利用LR-SIS方法對(duì)此評(píng)論集進(jìn)行關(guān)鍵詞篩選。表4根據(jù)ωj值對(duì)影響評(píng)價(jià)分類的關(guān)鍵詞進(jìn)行了排序。從這些排名靠前的關(guān)鍵詞可以看出，評(píng)論者主要從電影本身、演員、演技以及音樂等方面對(duì)電影進(jìn)行評(píng)價(jià)，重點(diǎn)關(guān)注這些方面的質(zhì)量、好壞、趣味性等，來對(duì)電影做出正面或負(fù)面的評(píng)價(jià)。

表4 電影評(píng)價(jià)分類與關(guān)鍵詞篩選結(jié)果

通過LR-SIS方法進(jìn)行特征篩選后，利用決策樹模型進(jìn)行判別分類，對(duì)整個(gè)數(shù)據(jù)集270條負(fù)面評(píng)論、240條正面評(píng)論進(jìn)行判別的分類結(jié)果見表5?？梢园l(fā)現(xiàn)總共510條評(píng)論，LR-SIS結(jié)合決策樹的錯(cuò)判率為0.126。錯(cuò)判率比較低，說明LR-SIS方法的篩選效果不錯(cuò)，利用LR-SIS方法來進(jìn)行降維和判斷評(píng)論的正負(fù)性是合理可行的。

表5 LR-SIS方法預(yù)測(cè)結(jié)果

4 定理證明

因此有：I1與I2擁有相同的結(jié)構(gòu)，下面只處理

由Hoeffding不等式：

通過積分中值定理，知在Pr與間存在使得。 當(dāng)時(shí)，有，又因?yàn)?Pr≥c1，所以，且當(dāng)時(shí)，有。故由Bernstein不等式：

類似Liu等[5]引理4的證明，可得存在正數(shù)c3和c4，有：

因此存在正常數(shù)滿足：

同理可得：

其中c3-c9都為正數(shù)。最終，由式（5）、式（9）、式（10）得到：

其中c10-c12為正數(shù)。

下面證明公式（3）。由條件（C2）可得對(duì)于某些j∈D，，若 D?，則必存在某些 j∈D 使得＜cn-τ，即。所以：

其中sn為D的基數(shù)。所以P(D?)→1。

5 結(jié)論

針對(duì)傳統(tǒng)統(tǒng)計(jì)分析方法在超高維數(shù)據(jù)特征篩選方面的不足之處，本文在卡方檢驗(yàn)特征篩選方法（PC-SIS）的基礎(chǔ)上，提出了基于似然比檢驗(yàn)的特征篩選方法（LR-SIS），LR-SIS具有無(wú)模型假設(shè)、計(jì)算簡(jiǎn)便、穩(wěn)健性高的特點(diǎn)，允許響應(yīng)變量與協(xié)變量之間存在任意回歸關(guān)系，避免了篩選初期尋找準(zhǔn)確回歸模型的困難。在樣本量較大時(shí)，LR-SIS的準(zhǔn)確程度與PC-SIS方法相當(dāng)，而在小樣本情況下效果要優(yōu)于PC-SIS。從數(shù)值模擬以及實(shí)例數(shù)據(jù)的分析結(jié)果表明，此方法對(duì)于高維數(shù)據(jù)特征篩選工作是合理有效的。