李澤安

（南通大學 計 算機科學與技術(shù)學院，江蘇 南 通 226019）

高維數(shù)據(jù)挖掘在采用傳統(tǒng)數(shù)據(jù)挖掘算法時，會遇到“維災”的問題［1－3］，許多挖掘算法的計算復雜度將隨著維數(shù)的增加呈指數(shù)增長。隨著維數(shù)增加，傳統(tǒng)相似性度量在高維空間中也變得無意義，這使得基于傳統(tǒng)相似度量的挖掘算法（如聚類算法）無法在高維空間中實現(xiàn)。高維數(shù)據(jù)的共同特征是具有變量的稀疏性，利用稀疏性特征，可以從成百上千維變量中有效地選擇出真實的影響變量，從而達到提取特征、提高推斷和預測精度的目的。解決高維數(shù)據(jù)挖掘問題最直接的方法是將數(shù)據(jù)從高維降到低維，用低維數(shù)據(jù)的處理辦法進行處理［3－5］。

多元統(tǒng)計中的降維方法有主成分分析、探索性因子分析和多維標度分析［6］。另外可以利用統(tǒng)計學中回歸分析模型和估計方法，其基本思想是通過創(chuàng)建的模型，用1個或多個自變量的變化去解釋因變量的變化，通過檢驗模型、估計預測等環(huán)節(jié)找出自變量與因變量的關(guān)系，挖掘出有用信息。

在實際問題中，首先對收集到的數(shù)據(jù)進行數(shù)據(jù)清理，例如填充空缺值，識別孤立點，糾正數(shù)據(jù)中的不一致性；再對預處理后的數(shù)據(jù)進行回歸建模，本文采用的線性回歸模型為：

其中，yi為因變量；xij為解釋變量；α為常數(shù)項；βj（j＝1，…，p）為回歸系數(shù)；εi為模型誤差，假定εi～N（0，σ2），σ2為誤差的方差。

為了方便，本文先對數(shù)據(jù)中解釋變量進行中心化，再進行線性回歸建模，此時可以略去常數(shù)項α。在初始建模時，通常會引入可能與之相關(guān)的變量（特征），其目的是減小模型誤差。為了提高模型的預測精度，增強模型的可解釋性，選擇對因變量有顯著影響的重要解釋變量。因此，變量選擇（特征提?。┦歉呔S數(shù)據(jù)進行有效數(shù)據(jù)挖掘的一個很重要的步驟［6］。

1 正則化估計方法

變量選擇是處理高維數(shù)據(jù)的統(tǒng)計模型基礎(chǔ)，經(jīng)典的變量選擇方法（如AIC、BIC及Cp準則）由于要求解一個NP組合優(yōu)化問題，在處理高維與海量數(shù)據(jù)時計算過于復雜，并且很難得到其樣本性質(zhì)，當協(xié)變量個數(shù)較多時，其局限性有：

（1）當解釋變量個數(shù)很多時，由于要估計的參數(shù)多，計算量巨大。

（2）在逐步選取模型過程中，存在累積的隨機誤差。

（3）在縮減的過程中缺乏穩(wěn)定性［7］。

為克服經(jīng)典變量選擇方法的弱點，文獻 ［7］針對模型（1）提出用懲罰函數(shù)的方法同時進行變量選擇和系數(shù)估計，表示為：

其中，β＝（β1，…，βp）T；‖β‖｜；λ 為懲罰因子；為 正 則 化 LASSO （Least Absolute Shrinkage and Selection Operator）估計。LASSO估計是一種連續(xù)縮減的正則化估計，其基本思想是在回歸系數(shù)的絕對值之和小于一個常數(shù)的約束條件下，使殘差平方和最小化，從而能夠產(chǎn)生某些嚴格等于0的回歸系數(shù)，得到可以解釋的模型。針對LASSO估計，文獻［8］提出了角回歸算法（LARS），懲罰函數(shù)對于不同的回歸系數(shù)采用相同的懲罰因子λ，文獻［9］提出了可適應LASSO的估計方法 （Adaptive LASSO），表示為：

通常取權(quán)ωj＝1／為模型（1）的最小二乘估計，γ＞0。當?shù)趈個變量是不重要或不相干變量時，第j個估計較小，此時懲罰的權(quán)ωj較大，對最終第j個正則化估計壓縮影響很大，很可能就直接壓縮估計到0，此時可以剔除第j個變量；當?shù)趈個變量是重要變量時，其系數(shù)估計較大，懲罰的權(quán)ωj較小，對最終第j個正則化估計壓縮效果較小。簡單地說，用較小的權(quán)懲罰系數(shù)較大的變量，較大的權(quán)懲罰系數(shù)較小的變量，從而使一些較小的系數(shù)自動趨于0甚至等于0，實現(xiàn)變量選擇（特征提?。Ｔ谶@一過程中，同時實現(xiàn)了模型選擇和非零參數(shù)的估計，而且所得估計量具有oracle性質(zhì)［9－10］。

典型的高維數(shù)據(jù)挖掘中，變量維數(shù)遠高于觀測樣本數(shù)目，文獻［11］提出了坐標下降算法（coordinate－wise descent），該算法在極小化（或極大化）某個目標函數(shù)時，每步只對參數(shù)的一個分量坐標進行極小化，參數(shù)的其他分量值固定不變，不斷進行循環(huán)迭代直至每個參數(shù)的分量都收斂為止。另外文獻［12］發(fā)展了坐標算法的R語言軟件包，受到高維數(shù)據(jù)挖掘應用工作者的青睞。

2 高維數(shù)據(jù)挖掘正則化估計的新算法

目前變量選擇的正則化估計主要針對回歸系數(shù)，在模型（1）中，未考慮數(shù)據(jù)的波動性（方差）對正則化路徑的影響。若數(shù)據(jù)對象集是高維數(shù)據(jù)，除了需要對回歸系數(shù)估計，σ2也是一個重要的參數(shù)［2］。因此在（3）式的極小化過程中改進原始算法，增加了σ2的極小化估計，提出的估計為：

其中，lnL（β，σ2；y1，…，yn）為模型（1）的對數(shù)似然函數(shù)。（4）式可表示為：

（5）式采用的懲罰是可適應的懲罰，雖然（5）式中僅懲罰了回歸系數(shù)，但由于同時對β和σ2進行極小化，方差參數(shù)的估計直接受懲罰因子和估計值的影響。

顯然，（6）式解決了尺度不變性問題。本文作如下參數(shù)變換：φj＝βj／σ，ρ＝σ，故（6）式轉(zhuǎn)化為：

其中，φ＝（φ1，…，φp）T。此時目標函數(shù)為凸函數(shù)。

3 算法的實現(xiàn)步驟

本算 法 將 坐 標 算 法 （ coordinate－wise）［11］與KKT（Karush－Kuhn－Tucker）條件結(jié)合，獲得正則化估計，實現(xiàn)變量選擇。

根據(jù)KKT條件，可得以下命題1。

（1）如果＝0，則

（2）如果≠0，則

其中，Y＝（y1，…，yn）為n維 向量；X＝（x1，…，xn）T為n×p維矩陣；Xj為矩陣X的 第j列；sgn（·）為符號函數(shù)；〈·，·〉為向量的內(nèi)積；‖·‖2為向量的歐式距離。

命題1可以根據(jù)KKT條件進行證明。根據(jù)命題1的結(jié)論，本文提出新的坐標算法如下。

計算λmax＝ max〈Xj，Y〉／‖Y‖ ，令λk＝j＝1，…，p1，…，100），通 常 取δ＝0.01，假設k＝0。

（1）令k＝k＋1，對λ＝λk，利用坐標算法［11］獲得β的初始估計，利用方差估計＝計 算σ2的初始估計，并令

（2）令ωj

（4）計算

（5）重復步驟（2）～（4），直至收斂。

（6）若k＜100，返回 步驟 （ 1）；否則，循環(huán)結(jié)束。

對每個λk，上述算法可獲得到σ2和β的估計值，再利用AIC、BIC準則或GCV方法選出最優(yōu)的λopt，從而獲得最優(yōu)的λopt所對應的β和σ2的估計，同時實現(xiàn)估計和變量選擇。本文使用BIC準則選取最優(yōu)的λopt，即

4 算法的有效性驗證

為驗證本文提出變量選擇算法的有效性，本文利用計算機模擬生成的隨機數(shù)據(jù)進行仿真。

（1）p＝200，β1＝…＝β5＝2，β6＝…＝β200＝0，ρ＝0.5。

（2）p＝500，β1＝3，β2＝1.5，β3＝2，β4＝…＝β500＝0，ρ＝0.5。

（3）p＝500，β1＝…＝β10＝3，β11＝…＝β500＝0，ρ＝0.8。

由以上方式生成的數(shù)據(jù)集中p?n，因此是高維數(shù)據(jù)集。重復以上生成過程100次，每次生成的數(shù)據(jù)利用本文算法進行估計和變量選擇，并將變量選擇的效果（100次的平均值）與其真值比較，主要包括正確選擇0的個數(shù)、正確選擇非0的個數(shù)和方差參數(shù)估計的均值。利用文獻［11］方法和新算法得到的結(jié)果見表1所列。從表1可看出，新算法結(jié)果要優(yōu)于坐標算法［11］。

表1 仿真數(shù)據(jù)的估計和變量選擇效果

本文隨機地選取了情形2和情形3下100次模擬中某一次的回歸系數(shù)估計，其估計的路徑如圖1和圖2所示，實驗結(jié)果表明，無論是參數(shù)估計值還是變量選擇效果，本文提出的算法都更為理想，能更有效地解決高維數(shù)據(jù)挖掘中重要變量的選擇問題。

圖1 情形2系數(shù)估計的路徑圖

圖2 情形3系數(shù)估計的路徑圖

5 結(jié)束語

針對高維數(shù)據(jù)挖掘的任務和特點，本文基于回歸分析的正則化估計方法提出了一種新的有效的變量選擇（特征提?。┓椒?，并給出了估計算法。從實驗結(jié)果可以看出，該方法能更加有效地進行變量選擇，并且能精確地估計出數(shù)據(jù)模型中的方差（或噪聲）大小，為高維數(shù)據(jù)挖掘提供了一種新思路和新方法。

由于實際問題中數(shù)據(jù)的復雜性，數(shù)據(jù)可能是異性的，即方差（或噪聲）是異方差的，或者與有些解釋變量有關(guān)，此時為提高估計和變量選擇的精確性，可進一步考慮基于均值和方差的聯(lián)合建模并進行變量選擇，基于以下模型考慮β和γ的變量選擇問題，即

另外，當高維數(shù)據(jù)中因變量是離散型數(shù)據(jù)，直接利用本文提出的方法進行變量選擇，效果有時很差，需要對該方法進一步地拓展研究［13］。

［1］ Hastie T，Tibshirani R，F(xiàn)riedman J.統(tǒng)計學習基礎(chǔ)：數(shù)據(jù)挖掘、推理與預測［M］.范 明，柴玉梅，昝紅英，等，譯.北京：電子工業(yè)出版社，2004：1－45.

［2］ Bühlmann P，van de Geer S.Statistics for high－dimensional data：methods，theory and applications［M］／／Springer Series in Statistics.Berlin：Springer－Verlag，2011：1－320.

［3］ 呂占強，孫玉寶.稀疏性正則化的圖像Laplace去噪及PR算子分裂算法［J］.計算機應用研究，2011（9）：3542－3544.

［4］ 閆德勤，劉勝藍，李燕燕.一種基于稀疏嵌入分析的降維方法［J］.自動化學報，2011，37（11）：1306－1312.

［5］ 呂國豪，黃雅平，羅四維，等.一種自適應正則化參數(shù)和模數(shù)的圖像去卷積方法［J］.北京交通大學學報，2011，35（5）：84－88.

［6］ 張俊妮.數(shù)據(jù)挖掘與應用［M］.北京：北京大學出版社，2009：53－69.

［7］ Tibshirani R.Regression shrinkage and selection via the LASSO［J］.Journal of the Royal Statistical Society：Series B，1996，58：267－288.

［8］ Efron B，Hastie T，Johnstone I，et al.Least angle regression［J］.The Annals of Statistics，2004，32：407－489.

［9］ Zou H.The adaptive LASSO and its oracle properties［J］.Journal of the American Statistical Association，2006，101：1418－1429.

［10］ 崔 靜，郭鵬江，夏志明.自適應Lasso在Poisson對數(shù)線性回歸模型下的性質(zhì)［J］.西北大學學報：自然科學版，2011，41（4）：565－568.

［11］ Friedman J，Hattie T T，Hofling T R.Pathwise coordinate optimization［J］. Annals of Applied Statistics，2007（1）：302－332.

［12］ Friedman J，Hattie T，Tibshirani R.Regularization paths for generalized linear models via coordinate descent［J］.Journal of Statistical Software，2010，33：1－22.

［13］ 支永安，歐陽一鳴.回歸分析在安徽電信差異化服務中的應用［J］.合肥工業(yè)大學學報：自然科學版，2011，34（3）：375－378.