基于壓縮感知的航空貨運量模型研究

游慶山, 徐海文, 雷開洪, 王 麗

(1. 中國民用航空飛行學院 計算機學院, 四川 廣漢 618307; 2. 電子科技大學 電子工程學院, 四川 成都 611731)

航空貨運量是反映國民經(jīng)濟發(fā)展水平和航空運輸經(jīng)濟發(fā)展水平的一項重要經(jīng)濟指標,也是航空運輸企業(yè)進行生產(chǎn)計劃與組織需要考慮的重要內(nèi)容之一.同時,關(guān)注航空貨運量的未來動態(tài)變化趨勢,并根據(jù)其內(nèi)在的動態(tài)變化趨勢采取相應(yīng)的措施,是航空運輸業(yè)持續(xù)健康發(fā)展的有效保障,是航空運輸各級決策部門制定發(fā)展戰(zhàn)略和規(guī)劃的重要依據(jù)[1-2].因此,航空貨運量的建模與預測受到國內(nèi)外學者的廣泛關(guān)注.

針對航空貨運量預測問題,很多學者做了大量而深入的研究.比如,林小平等[3]通過實際數(shù)據(jù)與預測結(jié)果的比較,證明灰色模型對于雙流機場貨、郵吞吐量的預測具備可行性；文軍等[1]研究灰色GM(1,1)理論和回歸分析理論在我國航空貨運量預測中應(yīng)用,并建立基于誘導有序幾何加權(quán)平均(IOWGA)算子的航空貨運量組合預測模型,驗證結(jié)果表明組合預測模型是有效、可靠的,且具有較高的預測精度；周葉等[4]利用我國航空貨運量的發(fā)展變化具有明顯的上升趨勢和季節(jié)性等特點,建立我國航空貨運量的ARIMA模型；方文清等[5]采用基于分形理論的研究方法,從非線性的角度對我國航空貨運量進行建模,得到相應(yīng)的分數(shù)維模型.此外,回歸分析法、灰色馬爾可夫鏈[2]、分形理論[3]等數(shù)學方法同樣被用于我國航空貨運量的預測問題.

最近十幾年,壓縮感知(CS)理論[6]得到快速發(fā)展,并廣泛應(yīng)用于圖像重建、信道估計以及譜估計等不同領(lǐng)域.本文采用壓縮感知理論對我國航空貨運量進行建模,并以1991～2006年我國航空貨運量的統(tǒng)計數(shù)據(jù)(數(shù)據(jù)來源于中國統(tǒng)計年鑒)為基礎(chǔ),利用OMP算法得到對航空貨運量的壓縮感知模型,以期為航空運力市場調(diào)控和發(fā)展提供理論參考.

1 壓縮感知理論

20世紀90年代初,D. L. Donoho等[7]研究小波變換在圖像壓縮中的應(yīng)用時,發(fā)現(xiàn)用極少數(shù)模較大的小波系數(shù)就可以獲得令人滿意的效果.此現(xiàn)象引起了學者對稀疏信號重建的研究.D. L. Donoho等[7]從不同的角度研究信號的稀疏表示,其研究成果指出在一定條件下信號的稀疏表示可以通過非自適應(yīng)的壓縮采樣準確重構(gòu).從此壓縮感知理論,無論是理論研究,還是具體算法設(shè)計以及實際應(yīng)用方面,均得到廣泛關(guān)注,并在不同應(yīng)用領(lǐng)域取得滿意結(jié)果,比如圖像處理[8-11]、機器學習[12-13]、波達方向估計[14]、雷達成像[15]、語音處理[16]等.

1.1壓縮感知模型假設(shè)測量向量y∈Rm滿足y=Ax+e,求滿足測量條件x∈Rn稀疏解的問題即為壓縮感知問題,其中,m

min‖x‖0

subject to‖y-Ax‖2≤ε,

(1)

其中,‖x‖0表示向量x的非零個數(shù).

文獻[17]從理論上闡述：如果采用組合優(yōu)化方法求解(1)式最優(yōu)化問題,則求解過程是多項式復雜程度非確定性(NP)問題.顯然(1)式最優(yōu)化問題是欠定問題,求解欠定線性方程組傳統(tǒng)的算法是以l2范數(shù)最小為目標函數(shù).最小范數(shù)解可以得到測量向量y在列向量ai中的線性表示,但是最小l2范數(shù)解通常不是稀疏解.因此,在求解過程中必須充分利用稀疏性約束.目前求解(1)式最優(yōu)化問題的常用方法主要分兩類:貪婪算法、基于凸優(yōu)化方法.其中,貪婪算法基本結(jié)構(gòu)是G. Davis等[18]提出的匹配追蹤(MP)算法.由于MP算法對信號擬合采用的方法不是正交投影,同時在尋找最優(yōu)列向量時可能出現(xiàn)重復選擇現(xiàn)象,因此,Y. Pati等[19]加以改進,并提出正交匹配追蹤(OMP)算法.OMP算法的偽代碼如下：

Input:

矩陣A∈Rm×n并進行列歸一化處理,觀測量y∈Rm,誤差限制ε,最大迭代次數(shù)Kmax.

初始化r0=y,x0=0,Λ0=?,l=0.

while not converge do

compute1:hl=ATrl

compute2:Λl+1=Λl∪sup(hard(hl,1))

compute4:rl+1=y-Axl+1

end while

1.2準確重建條件(1)式最優(yōu)化問題是NP問題,目前所有算法均是近似最優(yōu)的算法,OMP算法也不例外,因此研究OMP算法準確求解(1)式最優(yōu)化問題的條件(準確重建條件)成為學術(shù)的熱點.J. Tropp[20]利用矩陣范數(shù)推導了OMP算法的準確重建條件(ERC)；M. A. Davenport等[21]利用算子的嚴格等距性推導了OMP算法的嚴格等距條件(RIP).這些工作進一步為OMP算法的稀疏重建性能提供了理論上的支持.總之,在一定條件下,OMP算法能準確重建稀疏向量.

為敘述OMP算法的準確重建條件,假設(shè)向量y在列向量集ai上的最稀疏表示為：

采用AΛopt表示由指標在集合Λopt中的列向量aλ組成的矩陣,即

AΛopt=[aλ1,aλ2,…,aλm],

其中,λ∈Λopt.采用xΛ表示列由指標在集合Λ中的元素組成的向量,顯然有

y=Ax=AΛoptxΛopt.

定理(準確重建條件) 假設(shè)向量y能表示成矩陣A中m個列向量的線性疊加,即

y=Ax=AΛoptxΛopt,

如果

(2)

證明假設(shè)OMP算法在前k

rk=AΛopth.

根據(jù)OMP算法的向量選擇準則(compute3)可知,要使算法在第(k+1)步準確地選擇AΛopt中的列向量,則要滿足

擬合殘差rk在非最優(yōu)列向量投影的最大值小于在最優(yōu)列向量投影的最大值,則有

其中

即任意向量x具有‖Bx‖∞≤‖B‖∞,∞‖x‖∞.利用矩陣范數(shù)的性質(zhì)‖BH‖∞,∞=‖B‖1,1可知

由條件(2)可知結(jié)果成立.

2 航空貨運量的壓縮感知模型

下面重點討論壓縮感知理論在我國航空貨運量建模中的應(yīng)用,并通過OMP算法得到航空貨運量的壓縮感知模型.在壓縮感知模型、灰色理論模型以及回歸分析模型的基礎(chǔ)上進行組合優(yōu)化,建立了基于誘導有序幾何加權(quán)平均IOWGA算子的航空貨運量組合預測模型.

2.1壓縮感知模型文獻[1,22]利用回歸分析法對航空貨運量進行建模,并得到航空貨運量的回歸分析模型,采用回歸分析法分析職工平均工資、人均GDP、GDP和人均消費支出4項指標對航空貨運量的影響,得到如下模型

y=195.841-0.043 1x1-0.708 7x2+

0.054 9x3+0.098 5x4,

其中,y∈Rm表示航空貨運量,x1、x2、x3和x4分別表示職工平均工資、人均GDP、GDP和人均消費支出.

上述回歸分析存在不足之處,其一,作者僅僅考慮職工平均工資、人均GDP、GDP和人均消費支出4個指標,并沒有給出選擇指標的理論依據(jù)；同時每個指標下均存在許多細化指標,作者并沒有考慮細化指標對航空貨運量的影響；其二,各指標單位不同,上述回歸模型不能直接反映各指標對航空貨運量的影響程度.

本文并非簡單地擴展指標個數(shù)達到精確擬合的效果,而是綜合考慮多項指標對航空貨運量的影響,并給出選擇主要指標的理論依據(jù),得到相對簡潔并且擬合精度高的壓縮感知模型.

假設(shè)極少因素決定我國航空貨運量的變化,則航空貨運量建模問題可轉(zhuǎn)化為(1)式優(yōu)化問題.采用OMP算法求解相應(yīng)問題可得航空貨運量的壓縮感知模型

y=736.574 3x1+7.713 1x2,

(3)

其中,x1表示城鎮(zhèn)集體平均工資的歸一化向量,x2表示財政支出增長幅度的歸一化向量.模型各變量的系數(shù)在一定程度上反映該因素影響我國航空貨運量的重要程度.模型表明影響我國航空貨運量的主要因素是城鎮(zhèn)集體平均工資,以及財政支出增長幅度.

利用(3)式航空貨運量的壓縮感知模型可以預測2007年我國的航空貨運量.預測值為416.57萬t,2007年真實的航空貨運量為401.8萬t,預測誤差為3.67%.預測的結(jié)果表明壓縮感知模型可應(yīng)用于短期內(nèi)我國航空貨運量的預測,可以為進一步的航空貨運市場調(diào)控提供有效理論依據(jù).

2.2IOWGA算子的組合優(yōu)化模型在航空貨運量預測問題中,假設(shè)x1t、x2t、x3t分別表示3種不同方法在t時刻的擬合值,l1、l2、l3分別為誘導有序幾何加權(quán)平均的權(quán)系數(shù),Pit表示第i擬合方法在t時刻的擬合精度,其定義如下

顯然Pit∈[0,1].

將第t時刻預測精度與其對應(yīng)的預測值關(guān)聯(lián)可得3個二維數(shù)組〈P1t,x1t〉、〈P2t,x2t〉、〈P3t,x3t〉,其中,t=1997,…,2006.假設(shè)L=(l1,l2,l3)表示權(quán)系數(shù)向量,并對預測精度Pit按從大到小排列,設(shè)Pindex(ix)表示第i個較大預測精度的下標,則有

IOWGAL(〈P1t,x1t〉,〈P2t,x2t〉,〈P3t,x3t〉)=

稱上式為由預測精度序列Pit所產(chǎn)生的t時刻的IOWGA組合預測值[1,23].顯然n期組合預測對數(shù)總誤差平方和S為

其中

eaindex(it)=lnxt-lnxPindex(ix).

用Eij簡記

則可得三階組合預測對數(shù)誤差信息矩陣E=(Eij).

使n期組合預測對數(shù)總誤差平方和S最小可以得到組合預測權(quán)系數(shù)l1、l2、l3,即L可以通過如下非線性規(guī)劃模型求得

minS(L)=LTEL,

(4)

將航空貨運量的灰色理論模型、回歸分析模型以及基于壓縮感知模型進行誘導有序幾何加權(quán)平均可得IOWGA組合模型.

假設(shè)x1t、x2t、x3t分別為灰色理論擬合值、回歸分析擬合值以及基于壓縮感知的擬合值,l1、l2、l3表示組合擬合中的權(quán)系數(shù).將擬合值代入(4)式模型,可以得到優(yōu)化問題

采用壓縮感知理論得到的預測模型具有如下優(yōu)點：第一,模型非常簡潔；第二,模型中各分量的系數(shù)可以體現(xiàn)各分量在航空貨運量中的比重；第三,從模型比較可知,基于壓縮感知的模型具有更高的精度.

3 模型分析與比較

文獻[1]提出基于灰色理論的航空貨運量預測模型,同時進一步給出基于回歸分析、灰色理論的我國航空貨運量IOWGA組合擬合值(簡記為2-IOWGA),其中,基于灰色理論預測模型如下

下面將詳細比較壓縮感知模型、灰色理論模型、回歸模型對我國航空貨運量的擬合效果,并進一步比較2-IOWGA、3-IOWGA對我國航空貨運量的擬合效果.

擬合圖1給出航空貨運量的真實值以及基于壓縮感知模型、灰色理論模型、回歸模型等不同方法所得擬合結(jié)果.圖1結(jié)果表明,基于壓縮感知模型是可靠的,并具有較高的擬合精度,可應(yīng)用于實際預測.圖2結(jié)果表明,3-IOWGA相對于2-IOWGA具有較高的擬合精度.

按照擬合效果評價原則和慣例,采用5項擬合誤差指標[22,24](平方和誤差(SSE)、均方誤差(MSE)、平均絕對誤差(MAEstro)、平均絕對百分比誤差(MAPE)和均方百分比誤差(MSPE))作為評判準則,對基于壓縮感知模型、灰色理論模型、回歸模型、2-IOWGA組合模型、3-IOWGA組合模型進行評價.各方法的擬合誤差指標如表1所示.

對預測效果進行綜合性評價,通過不同擬合模型的擬合值比較(圖1和圖2所示)和各擬合模型的擬合誤差指標(表1所示),可以得到：單種擬合方法中,基于壓縮感知的擬合模型相對于灰色理論、回歸分析方法的擬合模型具有模型相對簡潔、擬合精度高、誤差小等特點.擬合誤差指標結(jié)果表明,基于壓縮感知方法的擬合精度高于灰色理論與回歸分析方法,同時3-IOWGA組合模型擬合精度高于2-IOWGA組合模型擬合精度.

表 1 擬合誤差指標

4 結(jié)語

本文將壓縮感知理論引入航空貨運量預測領(lǐng)域,通過OMP算法得到基于壓縮感知理論的航空貨運量預測模型,并給出基于壓縮感知模型的2007年預測值.預測結(jié)果表明,壓縮感知模型可應(yīng)用于短期內(nèi)我國航空貨運量的預測.本文重點比較壓縮感知模型、灰色理論模型、回歸分析模型在航空貨運量的擬合效果.通過對預測誤差以及擬合誤差指標的比較,得到壓縮感知模型具有模型相對簡潔、精度高、誤差小等優(yōu)點.同時給出基于壓縮感知模型、灰色理論模型、回歸模型3種方法的IOWGA組合優(yōu)化模型,實驗表明,3-IOWGA組合模型相對于2-IOWGA具有更好的統(tǒng)計特性.

[1] 文軍,蔣由輝,方文清. 航空貨運量的優(yōu)化組合預測模型[J]. 計算機工程與應(yīng)用,2010,46(15):215-217.

[2] 文軍. 基于灰色馬爾可夫鏈模型的航空貨運量預測研究[J]. 武漢理工大學學報:交通科學與工程版,2010,34(4):695-698.

[3] 林小平,袁捷. 基于灰色模型的成都雙流機場物流預測[J]. 武漢理工大學學報:交通科學與工程版,2007,31(3):457-459.

[4] 周葉,肖靈機. 基于ARIMA 模型的我國航空貨運量預測分析[J]. 南昌航空大學學報:社會科學版,2010,12(3):22-27.

[5] 方文清,蔣由輝,文軍. 分形理論用于航空貨運量的預測[J]. 交通科技與經(jīng)濟,2009,11(2):105-106.

[6] You Q S, Wan Q, Liu Y P. A short note on strongly convex programming for exact matrix completion and robust principal component analysis[J]. Inverse Problems and Imaging,2012,6(2):357-372.

[7] Donoho D L, Johnstone I. Wavelet Shrink-age: Asymptopia[R]. Stanford:Stanford University,1993.

[8] Ellenberg J. Fill in the blanks: using math to turn lores datasets into hiressamples[J/OL]. Wired Magazine,2010,18(3). http://www.docin.com/p-62893506.html.

[9] 王良君,石光明,李甫,等. 多稀疏空間下的壓縮感知圖像重構(gòu)[J]. 西安電子科技大學學報:自然科學版,2013,40(3):88-98.

[10] Duarte M, Davenport M, Takhar D, et al. Single-pixel Imaging via compressive sampling[J]. IEEE Signal Processing Magazine,2008,25(2):83-91.

[11] Shi G M, Gao D H, Song X X, et al. High-resolution imaging via moving random exposure and its simulation[J]. IEEE Transactions on Image Processing,2011,20(1):276-282.

[12] Zeng B, Fu J. Directional discrete cosine transforms: a new framework for image coding[J]. IEEE Trans Circuits Syst Video Technol,2011,18(13):305-313.

[13] Ji H, Liu C Q, Shen Z W, et al. Robust video denoising using low rank matrix completion[J]. Comput Vision and Pattern Recognition,2010:1791-1798.

[14] Malioutov D, Cetin M, Willsky A S. A sparse signal reconstruction perspective for source location with sensor arrays[J]. IEEE Transaction on Signal Processing,2005,53(8):3010-3022.

[15] Matthew H, Thomas S. Compressed sensing radar[J]. IEEE International Conference on Acous-tics, Speech and Signal Processing,2008:1509-1512.

[16] 梁瑞宇,鄒采榮,趙力,等. 語音壓縮感知及其重構(gòu)算法[J]. 東南大學學報:自然科學版,2011,41(1):1-5.

[17] Natarajan B K. Sparse approximate solutions to linear systems[J]. SIAM J Comput,1995,24(2):227-234.

[18] Davis G, Mallat S, Zhang Z. Adaptive time-frequency decompositions[J]. SPIE J Opt Eng,1994,33(7):2183-2191.

[19] Pati Y, Rezaifar R, Krishnaprasad P. Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[C]//The 27th Annual Asilomar Conference on Signals, Systems, and Computers. Pacific Grove,CA,1993.

[20] Tropp J. Greed is good: algorithmic results for sparse approximation[J]. IEEE Trans Inform Theory,2004,50(10):2231-2242.

[21] Davenport M A, Wakin M B. Analysis of orthogonal matching pursuit using the restricted isometry property[J]. IEEE Trans Inform Theory,2010,56(9):4395-4401.

[22] 方文清. 我國航空貨運業(yè)發(fā)展若干問題研究[D]. 廣漢:中國民航飛行學院,2009.

[23] Chou K C, Zhang C T. Predicting protein folding types by distance functions that make allowances for amino acid interactions[J]. J Biol Chem,1994,269:22014-22020.

[24] 王洋. 組合預測模型在成都市房價中的應(yīng)用研究[D]. 成都:成都理工大學,2010.