一種面向海量數(shù)據(jù)的spilt-and-conquer方法

溫 焜，蘭曉然

（1.南昌大學(xué) 管理學(xué)院，南昌 330029；2.江西行政學(xué)院，南昌 330003；3.中國人民銀行滄州市中心支行，河北 滄州 061000）

0 引言

變量選擇[1，2]在對維數(shù)過大樣本量過多的的數(shù)據(jù)集進(jìn)行降維的時候，通常會遇到兩個問題：計算開銷太大和欠學(xué)習(xí)。就目前而言大多特征選擇算法的時間復(fù)雜度是樣本數(shù)的二次甚至更高次，同時與維數(shù)成正比，導(dǎo)致在對高維海量數(shù)據(jù)集進(jìn)行變量選擇時消耗的時間就會過長；在面對樣本數(shù)遠(yuǎn)遠(yuǎn)大于特征維數(shù)的高維小樣本數(shù)據(jù)集時，進(jìn)行特征選擇就容易出現(xiàn)欠學(xué)習(xí)問題。因此如何有效的對高維海量數(shù)據(jù)集進(jìn)行變量選擇，是變量選擇研究要迫切解決的問題。

在進(jìn)行變量選擇時可以選擇Lasso[3]，LARS算法[4]SCAD估計方法[5]和MCP估計算法[6]等，本文選擇了Lasso方法進(jìn)行變量選擇[3]。這種算法通過構(gòu)造一個懲罰函數(shù)獲得一個精煉的模型，通過最終確定一些指標(biāo)的系數(shù)為零，LASSO算法實現(xiàn)了指標(biāo)集合精簡的目的。這是一種處理具有復(fù)共線性數(shù)據(jù)的有偏估計[7]。

1 Lasso方法

LARS算法，SCAD估計方法和MCP估計算法都可以用來進(jìn)行變量選擇，而Lasso算法在某些方面具有一定的優(yōu)越性，所以本文采用Lasso方法進(jìn)行研究。Lasso方法是很常用的一種變量選擇的方法，是1996年Tibshirani提出的。它既能對變量進(jìn)行選擇,又能得出參數(shù)估計值的一種方法，而且選擇出的變量具有很好的解釋性。

考慮如下普通線性方程：

其中 Y=(y1，y2，…,yn)T為響應(yīng)變量，n 為樣本容量，X=(X1，X2，…，Xn) 為 p 維 預(yù) 測 變 量 ，假 設(shè) 觀 測 數(shù) 據(jù)(yi，xij)，i=1，2，…，n ，j=1，2，…，p 已經(jīng)過中心標(biāo)準(zhǔn)化處理，即：

除特別說明外，在下文出現(xiàn)的數(shù)據(jù)（X,Y）均為經(jīng)過中心標(biāo)準(zhǔn)化處理的。

設(shè)對固定非負(fù)數(shù)，Lasso方法定義如下:

R統(tǒng)計軟件的Lars算法的軟件包提供了Lasso算法。根據(jù)模型改進(jìn)的需要，數(shù)據(jù)挖掘工作者可以借助于Lasso算法，利用AIC準(zhǔn)則和BIC準(zhǔn)則精煉簡化統(tǒng)計模型的變量集合，達(dá)到降維的目的，因此，Lasso算法是可以應(yīng)用到數(shù)據(jù)挖掘中的實用算法。

2 spilt-and-conquer方法

spilt-and-conquer方法[8]，經(jīng)過變量選擇在組合選擇后，它不僅能夠很好的去除錯誤模型選擇帶來的偽相關(guān)，而且可以極大地降低計算時間。變量選擇的時間復(fù)雜度一致于O(napb)，a＞1，b≥0 。

對應(yīng)的懲罰估計為:

其中 ρ(β;λk)訓(xùn)練參數(shù) λk的懲罰函數(shù)，可參見Fan和Lv（2011）。

本文考慮 p是有限的，β是非稀疏的，假設(shè)XTX是可逆的，那么使用全數(shù)據(jù)進(jìn)行最小二乘估計為，這里把數(shù)據(jù)集分成K份。

假設(shè)XkTXk是可逆的，那么從kth份得到的最小二乘估計為：

公式(7)中Xk是正交矩陣，yk是數(shù)據(jù)集kth份的響應(yīng)向量，由K個部分可以結(jié)合成一個新的估計，如下：

3 實驗分析

3.1 實驗數(shù)據(jù)

為了檢驗spilt-and-conquer方法在高維海量或高維小樣本數(shù)據(jù)集表現(xiàn)的優(yōu)越性，本文選擇了三個高維數(shù)據(jù)集，三個低維數(shù)據(jù)集。本文數(shù)據(jù)集來自UCI數(shù)據(jù)庫、17年數(shù)學(xué)建模、R庫，為了便于比較本文抽取了部分?jǐn)?shù)據(jù)。數(shù)據(jù)庫具體描述如表1所示。

表1 實驗數(shù)據(jù)集描述

針對以上數(shù)據(jù)集，首先將分而治之的Lasso方法用在三個低維的數(shù)據(jù)集上，并與傳統(tǒng)的Lasso方法進(jìn)行對比，表明其并沒有降低分類精度。然后在高維的數(shù)據(jù)上將改進(jìn)的Lasso方法與傳統(tǒng)Lasso方法進(jìn)行對比，發(fā)現(xiàn)spilt-and-conquer方法不僅在預(yù)測精度上不受影響，對一些數(shù)據(jù)集還會提高其預(yù)測精度。實驗表明，spilt-and-conquer方法能夠有效解決高維數(shù)據(jù)中遇到的過學(xué)習(xí)和計算時間過長、計算消耗過大的問題。本文選擇SVM、隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)做分類器，并采用5倍交叉驗證的方式進(jìn)行實驗。

3.2 實驗過程

（1）使用SVM、隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)做分類器，將三種預(yù)測結(jié)果求平均值。在R語言加載包，以實現(xiàn)這三種分類器。

（2）調(diào)整參數(shù)lambda的確定：對lambda的格點值，進(jìn)行10折交叉驗證，選取交叉驗證均方誤差誤差最小的lambda值。然后，按照得到的lambda值，用全部數(shù)據(jù)重新擬合模型。

（3）對三個低維的數(shù)據(jù)集進(jìn)行特征選擇，設(shè)K為2、3、4以均分的原則進(jìn)行劃分，分別用Lasso方法spilt-and-conquer方法進(jìn)行變量選擇，并使用三種分類器進(jìn)行預(yù)測，比較預(yù)測精度。

（4）對高維的數(shù)據(jù)集進(jìn)行變量選擇，設(shè)K分別為1、2、4、6，然后分別用兩種方法進(jìn)行變量選擇并比較預(yù)測精度。

3.3 實驗結(jié)果

3.3.1 在低維數(shù)據(jù)集上的實驗比較

對三個低維數(shù)據(jù)集分別用Lasso和spilt-and-conquer方法進(jìn)行處理，將結(jié)果運(yùn)行100次取平均值，結(jié)果如表2所示。

表2 低維數(shù)據(jù)集預(yù)測精度對比表

通過表中的結(jié)果，可以得出spilt-and-conquer算法與傳統(tǒng)的Lasso算法相比，精度相差不大。在wdbc和Adult數(shù)據(jù)集中，分別當(dāng)K=2、K=4時預(yù)測結(jié)果還相對較好。由于數(shù)據(jù)量比較小，計算時間相差不大。基本在一分鐘之內(nèi)可以計算出結(jié)果。

3.3.2 在高維數(shù)據(jù)集上的實驗比較

對三個高維海量數(shù)據(jù)集分別用Lasso和spilt-and-conquer方法進(jìn)行處理，將結(jié)果運(yùn)行100次取平均值，為了方便比較本文對數(shù)據(jù)集的維數(shù)和樣本數(shù)進(jìn)行了選取。結(jié)果如表3所示。

表3 高維數(shù)據(jù)集預(yù)測精度對比表

在表3中，K=1意味用全數(shù)據(jù)集進(jìn)行Lasso估計，為了比較本文使用了K=2、4、6。Lasso算法試圖保留更多相關(guān)變量。由表3列出的計算時間和預(yù)測精度可以看出，spilt-and-conquer方法不僅提高了預(yù)測精度，而且很大程度的節(jié)省了計算時間，減少了電腦消耗。原理上來說，spilt-and-conquer方法進(jìn)行分塊，刪除了冗余變量，結(jié)合后再次進(jìn)行變量選擇，只留下對結(jié)果影響較大的變量，使預(yù)測結(jié)果有一定提高。將變量分開，就相當(dāng)于用計算機(jī)并行計算，可以有效縮短計算機(jī)運(yùn)行時間。

3.3.3 在高維數(shù)據(jù)集上的運(yùn)行時間比較

固定數(shù)據(jù)集的維數(shù)，記錄三個數(shù)據(jù)集與測試運(yùn)行時間如圖1所示。

圖1 計算機(jī)運(yùn)行時間對比圖

由圖1可知，當(dāng)維數(shù)固定時，樣本量越大，計算機(jī)運(yùn)行時間越長。所以隨著分塊個數(shù)增加計算機(jī)耗費(fèi)時間減短，且樣本個數(shù)越多，時間減少的越快。

spilt-and-conquer方法，將數(shù)據(jù)集進(jìn)行分塊處理，并行運(yùn)算，很大程度上縮短的運(yùn)行時間。通過多次變量選擇排除冗余變量，也提高的預(yù)測精度。所以spilt-and-conquer方法能很好的適用于高維海量數(shù)據(jù)集。

3.3.4 在低高維數(shù)據(jù)集上的預(yù)測精度比較

將三種預(yù)測算法對每個數(shù)據(jù)集預(yù)測效果取平均得到預(yù)測結(jié)果，如表4所示。

表4 spilt-and-conquer方法和Lasso方法預(yù)測精度對比表

由表4可以看出，在低維和高維的海量數(shù)據(jù)上，除了diabetes和dexder數(shù)據(jù)集的所有分塊的平均預(yù)測精度，spilt-and-conquer方法稍低于Lasso方法，其他數(shù)據(jù)集的預(yù)測精度明顯更好。綜上可以得出spilt-and-conquer方法使用于低高維海量數(shù)據(jù)集上時，不僅可以很大程度上節(jié)省時間，而且可以是預(yù)測效果更好。

4 結(jié)論

Lasso方法在變量選擇時具有好的表現(xiàn)，但是在處理海量的數(shù)據(jù)集時，會出現(xiàn)費(fèi)時，計算機(jī)消耗過大的問題。于是為了更好地在海量數(shù)據(jù)集進(jìn)行選擇，本文提出spilt-and-conquer方法，此方法除了具有Lasso的優(yōu)良性質(zhì)外，還具有強(qiáng)穩(wěn)定性，易排除偽相關(guān)變量的特性。為了驗證spilt-and-conquer方法的優(yōu)良性質(zhì)，本文使用SVM、隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)對數(shù)據(jù)集進(jìn)行預(yù)測并記錄運(yùn)行時間。實驗結(jié)果表明，spilt-and-conquer方法不僅可以有效的提高預(yù)測精度，而且能夠很大程度上節(jié)省運(yùn)行時間。說明spilt-and-conquer方法能夠很好地適用于高維海量或低維海量數(shù)據(jù)集。