一種面向海量數據的spilt-and-conquer方法

溫 焜，蘭曉然

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

0 引言

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

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

1 Lasso方法

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

考慮如下普通線性方程：

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

除特別說明外，在下文出現的數據（X,Y）均為經過中心標準化處理的。

設對固定非負數，Lasso方法定義如下:

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

2 spilt-and-conquer方法

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

對應的懲罰估計為:

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

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

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

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

3 實驗分析

3.1 實驗數據

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

表1 實驗數據集描述

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

3.2 實驗過程

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

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

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

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

3.3 實驗結果

3.3.1 在低維數據集上的實驗比較

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

表2 低維數據集預測精度對比表

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

3.3.2 在高維數據集上的實驗比較

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

表3 高維數據集預測精度對比表

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

3.3.3 在高維數據集上的運行時間比較

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

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

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

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

3.3.4 在低高維數據集上的預測精度比較

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

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

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

4 結論

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