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

溫 焜，蘭曉然

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

0 引言

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

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

1 Lasso方法

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

考慮如下普通線性方程：

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

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

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

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

2 spilt-and-conquer方法

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

對應的懲罰估計為:

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

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

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

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

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ù)學建模、R庫，為了便于比較本文抽取了部分數(shù)據(jù)。數(shù)據(jù)庫具體描述如表1所示。

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

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

3.2 實驗過程

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

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

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

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

3.3 實驗結果

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

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

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

通過表中的結果，可以得出spilt-and-conquer算法與傳統(tǒng)的Lasso算法相比，精度相差不大。在wdbc和Adult數(shù)據(jù)集中，分別當K=2、K=4時預測結果還相對較好。由于數(shù)據(jù)量比較小，計算時間相差不大?；驹谝环昼娭畠?nèi)可以計算出結果。

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

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

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

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

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

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

圖1 計算機運行時間對比圖

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

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

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

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

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

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

4 結論

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