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

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

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

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

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

1 壓縮感知理論

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

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

min‖x‖0

subject to‖y-Ax‖2≤ε,

(1)

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

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

Input:

矩陣A∈Rm×n并進(jìn)行列歸一化處理,觀測(cè)量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準(zhǔn)確重建條件(1)式最優(yōu)化問(wèn)題是NP問(wèn)題,目前所有算法均是近似最優(yōu)的算法,OMP算法也不例外,因此研究OMP算法準(zhǔn)確求解(1)式最優(yōu)化問(wèn)題的條件(準(zhǔn)確重建條件)成為學(xué)術(shù)的熱點(diǎn).J. Tropp[20]利用矩陣范數(shù)推導(dǎo)了OMP算法的準(zhǔn)確重建條件(ERC)；M. A. Davenport等[21]利用算子的嚴(yán)格等距性推導(dǎo)了OMP算法的嚴(yán)格等距條件(RIP).這些工作進(jìn)一步為OMP算法的稀疏重建性能提供了理論上的支持.總之,在一定條件下,OMP算法能準(zhǔn)確重建稀疏向量.

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

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

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

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

y=Ax=AΛoptxΛopt.

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

y=Ax=AΛoptxΛopt,

如果

(2)

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

rk=AΛopth.

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

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

其中

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

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

2 航空貨運(yùn)量的壓縮感知模型

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

2.1壓縮感知模型文獻(xiàn)[1,22]利用回歸分析法對(duì)航空貨運(yùn)量進(jìn)行建模,并得到航空貨運(yùn)量的回歸分析模型,采用回歸分析法分析職工平均工資、人均GDP、GDP和人均消費(fèi)支出4項(xiàng)指標(biāo)對(duì)航空貨運(yùn)量的影響,得到如下模型

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

0.054 9x3+0.098 5x4,

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

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

本文并非簡(jiǎn)單地?cái)U(kuò)展指標(biāo)個(gè)數(shù)達(dá)到精確擬合的效果,而是綜合考慮多項(xiàng)指標(biāo)對(duì)航空貨運(yùn)量的影響,并給出選擇主要指標(biāo)的理論依據(jù),得到相對(duì)簡(jiǎn)潔并且擬合精度高的壓縮感知模型.

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

y=736.574 3x1+7.713 1x2,

(3)

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

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

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

顯然Pit∈[0,1].

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

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

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

其中

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

用Eij簡(jiǎn)記

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

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

minS(L)=LTEL,

(4)

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

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

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

3 模型分析與比較

文獻(xiàn)[1]提出基于灰色理論的航空貨運(yùn)量預(yù)測(cè)模型,同時(shí)進(jìn)一步給出基于回歸分析、灰色理論的我國(guó)航空貨運(yùn)量IOWGA組合擬合值(簡(jiǎn)記為2-IOWGA),其中,基于灰色理論預(yù)測(cè)模型如下

下面將詳細(xì)比較壓縮感知模型、灰色理論模型、回歸模型對(duì)我國(guó)航空貨運(yùn)量的擬合效果,并進(jìn)一步比較2-IOWGA、3-IOWGA對(duì)我國(guó)航空貨運(yùn)量的擬合效果.

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

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

對(duì)預(yù)測(cè)效果進(jìn)行綜合性評(píng)價(jià),通過(guò)不同擬合模型的擬合值比較(圖1和圖2所示)和各擬合模型的擬合誤差指標(biāo)(表1所示),可以得到：?jiǎn)畏N擬合方法中,基于壓縮感知的擬合模型相對(duì)于灰色理論、回歸分析方法的擬合模型具有模型相對(duì)簡(jiǎn)潔、擬合精度高、誤差小等特點(diǎn).擬合誤差指標(biāo)結(jié)果表明,基于壓縮感知方法的擬合精度高于灰色理論與回歸分析方法,同時(shí)3-IOWGA組合模型擬合精度高于2-IOWGA組合模型擬合精度.

表 1 擬合誤差指標(biāo)

4 結(jié)語(yǔ)

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

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

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

[3] 林小平,袁捷. 基于灰色模型的成都雙流機(jī)場(chǎng)物流預(yù)測(cè)[J]. 武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版,2007,31(3):457-459.

[4] 周葉,肖靈機(jī). 基于ARIMA 模型的我國(guó)航空貨運(yùn)量預(yù)測(cè)分析[J]. 南昌航空大學(xué)學(xué)報(bào):社會(huì)科學(xué)版,2010,12(3):22-27.

[5] 方文清,蔣由輝,文軍. 分形理論用于航空貨運(yùn)量的預(yù)測(cè)[J]. 交通科技與經(jīng)濟(jì),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]. 西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,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] 梁瑞宇,鄒采榮,趙力,等. 語(yǔ)音壓縮感知及其重構(gòu)算法[J]. 東南大學(xué)學(xué)報(bào):自然科學(xué)版,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] 方文清. 我國(guó)航空貨運(yùn)業(yè)發(fā)展若干問(wèn)題研究[D]. 廣漢:中國(guó)民航飛行學(xué)院,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ù)測(cè)模型在成都市房?jī)r(jià)中的應(yīng)用研究[D]. 成都:成都理工大學(xué),2010.