基于序lasso的時間序列分析方法

王金甲，陳　春，洪文學(.燕山大學信息科學與工程學院，河北秦皇島066004;2.燕山大學電氣工程學院，河北秦皇島066004;3.東北大學秦皇島分校大數據可視化分析技術中心，河北秦皇島066004)

基于序lasso的時間序列分析方法

王金甲1，陳春1，洪文學2，3，*
(1.燕山大學信息科學與工程學院，河北秦皇島066004;
2.燕山大學電氣工程學院，河北秦皇島066004;
3.東北大學秦皇島分校大數據可視化分析技術中心，河北秦皇島066004)

摘要:傳統的lasso法因其解的稀疏性、變量選擇的穩定性被廣泛應用在高維、復雜、多變的大數據的降維及分類中，但在處理時序大數據時，lasso法因不考慮變量的時序關系而受限制。鑒于這一缺點，本文在處理時序數據時采用序lasso方法。序lasso將不同特征的不同時間點的數據作為輸入變量，能夠有效地估計出每個特征最合適的時滯間隔，它的優點是在恢復真實系數上消除了尾部的波動性。基于實際的時序數據上的實驗結果證明了本文的模型和算法。

關鍵詞:時序大數據;序lasso;塊坐標下降;保序回歸

0　引言

隨著移動互聯網、物聯網和云計算技術的迅速發展，各個領域都出現了大規模的數據增長。在過去的兩年中，每天都會產生大概2.5×109個字節的數據［1］。大數據這一術語正是產生在數據爆炸增長的背景下。李國杰院士等［2］對大數據的定義為:大數據是指無法在可容忍的時間內用傳統的IT技術和軟硬件工具對其進行感知、獲取、管理、處理和服務的數據集合。

由于大數據存在復雜、高維、多變等特性，造

成存儲分析挖掘等多個環節的困難［3］。傳統的非線性機器學習算法諸如壓縮最近鄰、近鄰等方法［4］由于計算量大，算法的收斂速度慢等缺點只適用于較小規模的數據集。1996年Robert Tibshirani提出了一種新的變量選擇方法(least absolute shrinkage and selection operator，lasso)［5］。該方法用模型系數的1范數作為懲罰來壓縮模型系數，使絕對值較小的系數自動壓縮為0，從而同時實現顯著性變量選擇和對應參數的估計，很好地克服了傳統方法在選擇特征上的不足［6］。lasso方法不僅能夠準確地選擇出重要特征，而且具有特征選擇的穩定性，這些優點使得它在生物醫學、光學等背景下的大數據集上得到廣泛的應用［7］。此外，將lasso方法運用到p階自回歸模型AR(p)的時序大數據上，就可以將模型的定階和參數估計這兩個步驟合二為一，簡化計算過程，提高計算效率［8］。但在處理時序大數據時，lasso方法并不考慮數據的時序關系，這會造成數據潛在信息的浪費，也可能對后續的分析產生誤導［9］。因此本文采用序lasso(ordered lasso)方法分析時序數據，序lasso方法在恢復真實系數上能夠有效地消除尾部的波動性，估計出每個特征最合適的時滯間隔。

1　基于序lasso的大數據處理流程

整個大數據處理流程如圖1所示。經數據源獲取的數據，因為其數據結構不同，用特殊方法進行數據處理和集成，將其轉變為統一標準的數據格式方便以后對其進行處理，然后用合適的數據分析方法對其進行處理分析，并將分析的結果利用可視化等技術展現給用戶。在整個處理過程中，數據分析是最核心的部分，因為在數據分析的過程中會發現數據的價值所在。經過數據的處理與集成后，所得的數據便成為數據分析的原始數據，根據所需數據的應用需求對數據進行進一步的處理和分析。傳統的數據處理分析方法有數據挖掘、機器學習、智能算法、統計分析等。

圖1　大數據處理基本流程Fig.1　Basic framework of big data processing

2　lasso方法

2.1基本原理及算法

假定有N對觀測數據(xi，yi)，其中i = 1，2，…，N，xi= (xi1，xi2，…，xip)是p維的特征向量，yi是相應的響應向量值。并且假定xij是標準化的，即有。線性模型在lasso罰下的參數估計可以描述為

本文運用坐標下降法針對固定的λ值求解式(1)。假設已估計出β槇0和β槇l(l≠j)，僅對βj進行部分優化，計算βj=β槇j處的梯度，要求β槇j≠0，否則梯度不存在。記分3種情況(βj＞0，βj＜0，βj= 0)分別對式(2)求導，求其最小值，結果總結如下:

式(4)即為lasso罰的線性回歸模型參數估計的迭代更新公式。

2.2lasso在時序大數據上的應用

線性滾動預測模型的主要思路是利用近期數據的線性形式來預測數據變化趨勢。在這兒假定數據形式{ yt，xt1，…，xtp}，其中t = 1，2，…，N。記錄的是在N個不同的時間點的每個預測變量的值及輸出結果。考慮一個最大時延為K的時滯回歸模型，即K階滾動線性預測模型: yt=β0+，其中，E(εi) = 0，Var(εi) = σ2。在該模型的基礎上加罰:

為了解決這一問題，建立一個大小為N×(Kp)的特征矩陣Z，特征矩陣Z每一行的形式為{ xt-1，1，xt-2，1，…，xt-K，1xt-1，2，xt-2，2，…，xt-K，2…xt-1，p，xt-2，p，…，xt-k，p}。矩陣Z有N行這樣的值。根據新構建的特征矩陣Z及響應向量y，運用式(4)求解滾動預測模型的參數值。

3　序lasso方法

3.1基本原理

在特征存在自然順序的問題中，在lasso罰中再添加單調非遞增約束條件是很有必要的，即

式(6)即為本文介紹的序lasso方法(Ordered lasso)。然而，由于順序約束條件的加入使得這一問題非凸。為求解式(6)，將每一個βj都寫成如下形式:βj=β+j－βj，且β+j，βj≥0。正負組件的使用將非凸問題(6)轉換為凸問題:

式(7)可用一階廣義梯度算法求解。用保序回歸中的PAVA算法作為它的近鄰算子即可。

3.2算法細節

為求解方便，假定截距^β0= 0。令X是N×p的數據矩陣，y是長度為N的響應向量。首先考慮如下問題:

s.t.β1≥β2≥…≥βp≥0，將帶有單調非遞增約束條件的式(7)記作minf(β) + h(β)，其中，f(β)

‖C(β)，‖是一個指示函數，C是由{β∈Rp|β1≥β2≥…≥βp≥0}給定的凸集。采用一階廣義梯度算法，可以得到β的迭代更新公式為

其中，L是Lipschitz系數，γ＞0是步長，要求它在每一步的更新過程中，目標函數都是遞減的。下面接著計算h(β)的近鄰映射，即

將式(10)轉化為以下問題:

采用經典的保序回歸算法(Pool Adjacent Violators Algorithm，PAVA)得到保序回歸{ yi－λ}的解{i} = {λi}，那么{λi.‖(λi＞0) }是式(11)的解。因此式(10)的解為

將該式應用到一階廣義梯度梯度算法中，那么求解式(8)的更新β的步驟為

以上過程完成了單獨的β+(β－)的求解，為了求解式(7)，需要把每一個預測變量Xij擴展成x*ij=－xij，那么有xijβj= xijβj++ x*ijβj－，定義擴展變量對(β+，β－)，并把近鄰算子(13)式分別運用到X、X*來得到最小的擴展變量對(+，－)。

3.3在時序大數據上的應用

仍假定數據形式{ yt，xt1，…，xtp}，其中t = 1，2，…，N。令βkj=βk+j－βk－

j，求解下式:

同2.2節類似，仍然建立矩陣Z，并將每一行的數據分為p塊，每一塊對應單個預測變量延遲1，2，…，K個時間單位的值。故Z 每一行的形式仍然擴展每一個預測變量xt-K，j，令x*t-k，j=－xt-k，j。選擇一個有效的最大延時K，令每個預測變量在K個時間點之外的系數為0。用塊坐標下降法［10］求解式(14)。

4　實驗結果與分析

在自回歸時間序列模型中，最大延時為k時，可從yt-1，yt-2，…，yt-k預測yt，這符合滾動預測模型框架。只是回歸變量是它自身的不同的時間點的時間序列。這一例子使用公開的sunspot.year數據，它包含了289個觀測值，代表的是從1700年到1988年每年的太陽黑子的數量。該數據的時序圖、自相關圖、偏相關圖分別如圖2的(a)～(c)所示，圖中藍色虛線表示置信區間。從圖中可以看出，該時間序列的自相關圖拖尾，偏相關圖截尾，且偏相關圖在滯后9階之后縮至為0，所以初步判定可以使用AR(9)模型。本文中，將lasso、序lasso和傳統的AR模型擬合進行了比較，AR擬合的階數是由最小二乘和AIC計算得到，lasso和序lasso中，假定最大時滯為20，采用10倍交叉驗證獲得最佳模型。圖3給出的是將自回歸模型應用到太陽黑子數據上的結果。

從實驗結果可以看出，標準的AR擬合得到的是9階AR模型，序lasso的階數是10，并能得到一個較好的系數序列。而lasso則因尾部的波動不能確定模型的確切階數。

圖2　太陽黑子數據示意圖Fig.2　Sunspot data sketches

圖3　lasso、序lasso、AR模型在太陽黑子上的系數估計Fig.3　Sunspot data: estimated coefficients of the ordered lasso，the lasso and the standard AR fit

5　結論

lasso方法不僅能夠準確地選擇出重要特征，而且具有特征選擇的穩定性，這些優點使得它廣泛應用在大數據的降維及分類中。但在處理時序大數據時，lasso方法并不考慮數據的時序關系，會造成數據潛在信息的浪費，也可能對后續的分析產生誤導。采用序lasso方法處理時序數據，能有效地改進lasso法的不足。本文將lasso、序lasso方法應用到太陽黑子數據上，從實驗結果可以看出，序lasso和lasso在自回歸模型上能取得和標準的AR模型擬合相近的性能，而序lasso更因其尾部的穩定性勝于lasso。這也充分證明了將序lasso應用到基于時滯回歸模型的預測問題上是可行的，為將來在金融問題、臨床醫學問題等大數據的處理上提供了可能。

參考文獻

［1］Wu Xindong.Data mining with big data［J］.IEEE Transactionss on Knowledge and Data Engineering，2014，26(1) : 97-98.

［2］李國杰，程學旗.大數據研究:未來科技及經濟社會發展的重大戰略領域-大數據的研究現狀與科學思考［J］.中國科學院院刊，2012，27(6) : 647-657.

［3］王元卓，靳曉龍，程學旗.網絡大數據:現狀與展望［J］.計算機學報，2013，36(6) : 1126-1127.

［4］Muja M.Lowe D G.Scalable nearest neighbor algorithms for high dimensional data［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36(11) : 2227-2230.

［5］Robert Tibshirani.Regression shrinkage and selection via the Lasso ［J］.Journal of the Royal Statistical Society，Series B(statistical methodology)，1996，58(1) : 267-288.

［6］Yamada M.High-dimensional feature selection by feature-wise kernelized lasso［J］.Neural Computation，2014，26(1) : 185-187.

［7］Liu Fayao.Multiple kernel learning in the primal for multimodal alzheimer's disease Classification［J］.Journal of Biomedical and Health Informattics，2014，18(3) : 984-985.

［8］謝儀，高雪，景英川.基于Lasso及Adaptive Lasso的AR(p)模型定階及參數估計［J］.浙江工業大學學報，2014，42 (4) : 463-465.

［9］姜高霞，王文劍.時序數據曲線排齊的相關性分析方法［J］.軟件學報，2014，25(9) : 2003-2004.

［10］Li Haifeng，Fu Yuli，Hu Rui，et al.Perturbation analysis of greedy block coordinate descent under RIP［J］.IEEE Transactions on Signal Processing Letters，2014，21(5) : 519-520.

Time series analysis method based on ordered lasso

WANG Jin-jia1，CHEN Chun1，HONG Wen-xue2，3
(1.College of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China; 2.College of Electrical Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China; 3.Big Data Visualization Technology Center，Northeastern University at Qinhuangdao，Qinhuangdao，Hebei 066004，China)

Abstract:When doing data mining on high dimensional，complex，and changeable data，it is necessary to reduce the dimension of primal data at first.Traditional lasso method is widely used for reducing the dimensionality and classification because of the sparsity of its solution and the stability of variable selection.However，when dealing with time-series data，it doesn't consider temporal relations of variables，so its application is limited.Given this shortcoming，ordered lasso of handling time-series data is proposed in this paper.The input variables of ordered lasso are the different time points according to different predictors.For each predictor，the ordered lasso can estimate the best suitable time-lag interval.The advantage of ordered lasso in recovering real coefficients is that it can eliminate the fluctuations in the tails.Experimental results on real time-series data have proved ordered lasso method is feasible.

Key words:time-series big data; ordered lasso; block coordinate descent; isotonic regression

作者簡介:王金甲(1978-)，男，河南商丘人，博士，副教授，主要研究方向為信號處理和模式識別; *通信作者:洪文學(1953-)，男，黑龍江依安人，教授，博士生導師，主要研究方向為大數據偏序結構理論、復雜概念網絡、可視化模式識別和中醫工程學，Email: hongwx@ ysu.edu.cn。

基金項目:國家自然科學基金資助項目(61473339) ;中國博士后科學基金資助項目(2014M561202) ;河北省2014年度博士后專項資助項目(B2014010005) ;首批“河北省青年拔尖人才”資助項目

收稿日期:2014-07-05

文章編號:1007-791X(2015) 01-0030-05

DOI:10.3969/j.issn.1007-791X.2015.01.005

文獻標識碼:A

中圖分類號:TP18; TP391