多維數(shù)據(jù)特征相似性測量的目標預測方法

李國祥,夏國恩,王繼軍

（廣西財經(jīng)學院a.教務處；b.信息與統(tǒng)計學院，南寧 530003）

0 引言

目標變量預測廣泛應用于工業(yè)過程控制、經(jīng)濟數(shù)據(jù)處理、政府宏觀規(guī)劃等領(lǐng)域。比如GDP的預測、區(qū)域物流需求量的預測、交通流預測等。目前根據(jù)對于預測目標變量所采取的數(shù)據(jù)類型，可以將目標變量分為兩類，一類是與屬性變量強關(guān)聯(lián)的目標變量，該類目標變量理論上認為是由多維屬性變量建立線性或非線性關(guān)系共同作用的結(jié)果[1，2]。該類目標變量的預測通常選用不同的模型建立屬性變量與目標變量的映射關(guān)系并擬合。這一類方法考慮了目標變量和屬性變量間的關(guān)聯(lián)關(guān)系及各因子間的相互制約等，但是屬性變量獲取的滯后性，使得目標變量很難有效地在時間軸上進行拓展。另外一類目標變量則是與其他變量沒有關(guān)聯(lián)映射關(guān)系的單獨數(shù)據(jù)個體，通過對其在時間軸上的前后延伸，形成該變量的時間序列，進而建立模型探尋歷史數(shù)據(jù)的規(guī)律來完成其時間軸上未來幾點的預測。一些經(jīng)典的時間序列預測方法，諸如AMIMA、灰色系統(tǒng)理論、SVM（支持向量機）等，便是該類方法的代表。但是這種以目標向量構(gòu)造時間序列的預測方法，自身數(shù)據(jù)源既是訓練樣本又是測試樣本，其數(shù)據(jù)節(jié)點預測依賴于前期若干維數(shù)據(jù)節(jié)點，該結(jié)果又作為下一節(jié)點預測的數(shù)據(jù)基礎(chǔ)，預測誤差也容易傳遞下去，而造成最后結(jié)果的偏離。

以上預測方法不同的適用范圍，使得廣大研究人員開始對不同方法的集成和新算法的融合進行研究，文獻[3]構(gòu)建ARIMA和SVR組合預測模型，對道路交通事故相關(guān)指標進行趨勢預測。文獻[4]提出了一種基于快速子空間分解方法的回聲狀態(tài)網(wǎng)絡預測模型。文獻[5]利用隱馬爾科夫模型中的隱狀態(tài)來表示產(chǎn)生時間序列數(shù)據(jù)時的系統(tǒng)內(nèi)部狀態(tài)，實現(xiàn)對多步時間序列的預測。這些研究方法進一步拓展了目標變量的預測理論，但是不難看出，當前的研究方法都集中在預測模型建立的方法論上，鮮有文獻對多維屬性數(shù)據(jù)特征本身進行研究，而數(shù)據(jù)源本身才是整個目標預測的基礎(chǔ)。究其原因，一方面可以歸結(jié)為全數(shù)據(jù)特征的高維數(shù)容易使智能學習算法陷入維數(shù)災難，另一方面是難以在大數(shù)據(jù)環(huán)境下尋找屬性特征與目標變量間的映射關(guān)系。

為此，本文以目標數(shù)據(jù)關(guān)聯(lián)的高維屬性特征為研究對象，通過比對不同屬性特征直方圖的相似性差異，將其轉(zhuǎn)化為線性規(guī)劃的運輸問題，探尋高維數(shù)據(jù)特征與目標變量的非線性關(guān)系。

1 相似性測量

目前相似性測量的研究主要集中在時間序列的數(shù)據(jù)挖掘和模式識別領(lǐng)域。在數(shù)據(jù)挖掘方面，時間序列的相似性測量的重點是不同序列間的匹配程度，主要包括子序列匹配(Subsequence Matching)和整體序列匹配(Whole Sequence Matching)，在此基礎(chǔ)上進而聚類、分類、以及關(guān)聯(lián)規(guī)則的抽取。文獻[6]通過比較兩個地震序列的L1距離與設定閾值的大小并加權(quán)，完成不同地區(qū)地震序列相似性判斷。文獻[7]根據(jù)查詢序列和數(shù)據(jù)庫時間序列中的不確定性進行組合，分別提出對應組合的相似性匹配算法。文獻[8]提出了基于斜率表示的時間序列相似性度量方法。文獻[9]則通過對時間序列逐段線性化,取兩序列的最長公共子序列LCSS(longest common subsequence)，作為其距離度量方法并進行相似性搜索。伴隨著人工智能技術(shù)的不斷發(fā)展，多種智能算法組合優(yōu)化的研究也得到了廣泛的開展。文獻[10]基于二維奇異值分解進行了多元時間序列相似性匹配。文獻[11]提出了一種基于形態(tài)特征相似性度量的方法來近似度量時間序列。但是這些方法主要研究對象往往為不同序列間的匹配，對既包含時間變量又包含屬性變量的多維度面板數(shù)據(jù)研究較少。

在模式識別方面，相似性測量的研究主要應用于高維特征比對中，通過測量不同特征向量的相似性程度進而對不同模式分類。Adrian Ion[12]使用L2距離對特征向量做分類，Marcin Marsza?ek[13]采用重疊區(qū)域比率的方法衡量其特征shape mask的差異距離。Julien Rabin[14]針對于部分二三維圖像研究了不同相似性測量方法的有效性。目前相似性測量主要通過距離函數(shù)來計算，如MinkowskiDistance、Euclidean Distance、x2Distance、Kullback-Leibler Divergence等，但是這些計算方式依賴于相對應屬性或時間節(jié)點的特征，從局部地絕對運算來比較序列的相似，因此對于特征波動較為敏感，或者對于屬性的一致性要求較高。為了能夠更好地在屬性變量之間進行平衡，越來越多的高維優(yōu)化算法也得到了廣泛的研究，從全局的角度對比序列的相似[15-17]，且取得了較好的測量效果。同時，也不難發(fā)現(xiàn)無論是時間序列還是模式識別領(lǐng)域，相似性測量的本質(zhì)都是N維向量的不同距離函數(shù)的比對計算。

2 基于相似性測量的目標預測方法

在多維屬性特征與目標向量強關(guān)聯(lián)的預測中，不同的研究方法對于指標的選取往往不同，以物流需求量的預測為例，文獻[1]選用第一、二、三產(chǎn)業(yè)產(chǎn)值等六個指標，文獻[18]采用GDP作為主要指標。文獻[19]則采用物流成本比例作為指標。上述文獻對于指標的選取并沒有量化選擇，主觀分析居多，其主要原因在于全指標數(shù)據(jù)維數(shù)較高，當前的機器學習方法難以把握各屬性特征間的映射關(guān)系且計算量大。而直方圖是高維特征的有效表示方法，結(jié)合目標預測的特點，本文通過將高維屬性特征的相似性測量問題轉(zhuǎn)換至模式識別中圖形特征分類的解決方案，實現(xiàn)時間序列和模式識別的有效結(jié)合。

2.1 屬性直方圖的相似性測量

令某不同時間節(jié)點下歸一化后的各數(shù)據(jù)特征向量直方圖分布分別為p={(p1，wp1)}，…(pm，wpm)}，Q={(q1，ωq1)，…(qn，ωqn)}，分別包含m和n個聚類中心，其中w表示其聚類權(quán)重。D=[dij]表示特征向量間的測度矩陣，dij表示向量聚類pi和qj中心間的測度距離，其距離的定義根據(jù)所求問題而具體化。Ruber[15]將特征向量比對問題轉(zhuǎn)化為線性規(guī)劃的運輸問題，通過找到雙向網(wǎng)絡最優(yōu)路徑的選擇方案F=[fij]，計算兩類特征分布的差異程度，fij表示供

給i到需求j的運輸量，從而使運輸費用最小。

滿足以下約束條件：

對于歸一化后的多維屬性分布，設其分布特征H存在m×n個柵格，柵格坐標集合定義為I={(i，j)，i≤i≤m，1≤j≤n}，運輸流方向表示為J={(i，j，k，l):(i，j)∈I，(k，l)∈I}，即從柵格 (i，j)運輸至 (k，l)，待匹配直方圖矩陣P={pij：(i，j)∈I}，Q={qij:(i，j

)∈I}，且其約束條件

從而屬性特征的相似性測量問題轉(zhuǎn)化為線性規(guī)劃的運輸問題：

其中的距離可以是任意的距離計算方法，考慮到目標預測的實際情況，本文采用簡單的L1距離即：

其模型如圖1所示：

圖1 經(jīng)EMD轉(zhuǎn)化后的運輸問題模型

2.2 屬性直方圖的測量優(yōu)化

定義集合：Js={(i，j，k，l):(i，j，k，l)∈I，di，k，l=1}表示直方圖分布中相鄰屬性柵格運輸流，且相鄰距離為1。通過將直方圖中兩點間的測度距離L1分解為相鄰點的累積和，非相鄰屬性柵格間距離轉(zhuǎn)化相鄰屬性柵格距離之和，即進一步減少變量數(shù)目和約束條件，這樣任何非相鄰屬性柵格距離fi;k，l可以被相鄰柵格距離路徑 [(i，j)，(i，j+1)，…，(i，l)，(i+1，l)，…，(k，l)]所取代[20]。

最終得優(yōu)化后的EMD模型：

相對于原算法，其變量數(shù)量減少至4N，約束條件也減少了一半，線性規(guī)劃的運算復雜度和空間復雜度就得到了明顯的下降。

2.3 構(gòu)建多維數(shù)據(jù)特征的相似性序列

設不同時間下的屬性直方圖分布為H(i≤n)，計算兩兩時間節(jié)點相似性距離：

其中i=1，2，…，n-1。令E0=0，對上述序列累加求和：

從而將高維數(shù)據(jù)約簡為多維屬性特征的相似性序列：

2.4 利用支持向量回歸機對該序列與目標向量擬合預測

擬合預測算法流程如圖2所示。

圖2 算法流程圖

3 實驗結(jié)果與分析

為了驗證上述算法的有效性，本文以區(qū)域物流需求預測為研究對象，以文獻[21]構(gòu)建的指標體系作為目標預測的屬性變量，以廣西、廣東兩個地區(qū)數(shù)據(jù)集為例，考慮到數(shù)據(jù)的完整性，最終構(gòu)成橫軸25個屬性變量，縱軸為1990—2012年的時間序列二維面板數(shù)據(jù)。采用平方和誤差(SSE）、平均絕對誤差(MAE)、均方誤差(MSE)、平均絕對百分比誤差(MAPE)、均方百分比誤差(MSPE)作為誤差檢驗指標。

該算法主要將屬性數(shù)據(jù)歸一化為直方圖分布，將預測問題轉(zhuǎn)化為模式識別的差異性分類問題，測量兩兩年份的相似性差異，構(gòu)建新的差異性序列代替原高維數(shù)據(jù)特征，最后利用支持向量回歸機對該序列與目標向量擬合預測。

實驗一：廣西區(qū)域物流預測

（1）對該二維面板數(shù)據(jù)消除量綱歸一化，將25個屬性指標轉(zhuǎn)換為5*5二維直方圖分布。如圖3所示。

（2）利用上文的方法橫向測量時間縱軸兩兩年份屬性分布的相似性差異，如表1所示。

（3）令序列首期基數(shù)為0，對相似度測量值累加減運算，構(gòu)建相似性序列，如表2所示。

圖3 屬性特征的直方圖分布

表1 不同時間節(jié)點間的相似性距離

表2 相似性序列

（4）利用相似性序列對貨運量進行擬合預測。

為了驗證該預測算法的有效性，本文分別與傳統(tǒng)預測算法（灰色模型）、人工智能學習算法（廣義回歸神經(jīng)網(wǎng)絡、原始支持向量回歸機和PCA降維的支持向量回歸機）做了比較。如下頁表3和表4所示。

實驗二：廣東區(qū)域物流預測

同理，在廣東地區(qū)數(shù)據(jù)集上進行實驗，結(jié)果如下頁表5所示：

實驗三：不同距離函數(shù)的擬合精度

本文分別采取MinkowskiDistance、Euclidean Distance、χ2Distance、Kullback-Leibler Divergence構(gòu)建相似性序列，同樣采用SVR在兩廣地區(qū)數(shù)據(jù)集中進行擬合預測，結(jié)果如

表3 區(qū)域物流預測精度比較

表4 預測評價

表5 廣東區(qū)域物流評價表

表6所示：

表6 不同距離函數(shù)的預測評價

通過上述實驗數(shù)據(jù)可以看出基于相似性測量的預測方法所提取的新的時間序列特征表達意義強，較之原始SVR和主成分分析的SVR，在保證精度的情況下，能夠有效降低大規(guī)模樣本數(shù)據(jù)的計算維度，避免“維數(shù)災難”和“過學習”的問題，預測精度較高。而傳統(tǒng)的灰色模型則對數(shù)據(jù)的平穩(wěn)性要求較高，實驗中數(shù)據(jù)的突然變化，對于灰度模型影響較大，可見灰色模型對于數(shù)據(jù)波動的適應性較差。而人工智能算法中的GRNN神經(jīng)網(wǎng)絡較之BP神經(jīng)網(wǎng)絡的逼近能力、學習速度等方面有著較強優(yōu)勢，但是該類學習算法神經(jīng)元個數(shù)的確定，參數(shù)的選擇優(yōu)化一直是其使用的難點，且其預測精度也是有限的。在與傳統(tǒng)的距離函數(shù)構(gòu)建的相似性序列比對中，也證明了該算法對于全局指標特征的把握能力和良好的預測效果。

4 結(jié)束語

本文以與目標預測值強關(guān)聯(lián)的多維數(shù)據(jù)特征為基礎(chǔ)，將目標預測問題通過屬性特征直方圖分布的形式轉(zhuǎn)化為模式識別的相似性測量問題，與傳統(tǒng)方法相比，該算法不再從預測模型的層面上進行改進，而是回歸至數(shù)據(jù)源本身特征，通過數(shù)據(jù)特征的相似性測量，有效結(jié)合時間序列和模式識別方法的優(yōu)勢。優(yōu)化后的測量方法能夠更好地從全局的角度比對直方圖特征差異，兼顧了全數(shù)據(jù)特征與目標變量之間的映射關(guān)系，使得在大數(shù)據(jù)環(huán)境下全數(shù)據(jù)特征的運算成為了可能，避免了特征選擇主觀性對于目標預測的偏差，大量試驗證明了該方法的有效性，為目標預測問題提供一種新的思路。

參考文獻：

[1] 常飛,喬欣,張申,許華棟.基于MFCC特征提取的故障預測與評價方法[J].計算機應用研究,2015，32（6）.

[2] 鐘煒,宋洋.基于FCM的小波神經(jīng)網(wǎng)絡模型在徑流預測中的應用[J].系統(tǒng)工程學報,2009,(1).

[3] 孫軼軒,邵春福,計尋,朱亮.基于ARIMA與信息粒化SVR組合模型的交通事故時序預測[J].清華大學學報:自然科學版,2014,(3).

[4] 韓敏,許美玲,王新迎.多元時間序列的子空間回聲狀態(tài)網(wǎng)絡預測模型[J].計算機學報,2014,(11).

[5] 章登,歐陽黜霏,吳文李.針對時間序列多步預測的聚類隱馬爾科夫模型[J].電子學報,2014,(12).

[6] 鄭華.基于時間序列相似性匹配算法的地震預測研究[J].四川地震，2010，26（2）.

[7] 吳紅花,劉國華,王偉.不確定時間序列的相似性匹配問題[J].計算機研究與發(fā)展,2014,(8).

[8] 張建業(yè),潘泉,張鵬等.基于斜率表示的時間序列相似性度量方法[J].模式識別與人工智能,2007,(2).

[9] Vlanhos M H M,Gunopulos D,Keogh E J.Index?ing Multi-dimensional Time-series With Sup?ports of Rmultiple Distance Measures[C].Pro?ceedings of the In:Procof the 9th ACM SIGKDD,Washington,F,2003.

[10] 吳虎勝,張鳳鳴,鐘斌.基于二維奇異值分解的多元時間序列相似匹配方法[J].電子與信息學報,2014,(4).

[11] 李海林,郭崇慧.基于多維形態(tài)特征表示的時間序列相似性度量[J].系統(tǒng)工程理論與實踐,2011,(31).

[12] Ion A,Peyre G,Haxhimusa Y,et al.Shapematching Using the Geode?sic Eccentricity Transform-a study[C].Proceedings of the In:Proc Workshopof the Austrian Association for Pattern Recognition,,F,2007.

[13] Marszalek M,Schmid C.Accurate Object Recognition With Shape Masks[J].International Journal of Computer Vision,2012,97(2).

[14] Rabin J,Peyre G,Cohen L D.Geodesic Shape Retrieval via Optimal Mass Transport[M].Amstedam：Computer Vision-Eccv,2010.

[15] Rubner Y,Tomasi C,Guibas L J.The Earth Mover's Distance as a Metric for Image Retrieval[J].International Journal of Computer Vi?sion,2000,40(2).

[16] Haibin L,Okada K.Diffusion Distance for Histogram Comparison[C].proceedings of the Computer Vision and Pattern Recognition,2006 IEEE Computer Society Conference on,F 17-22 June 2006.

[17] Bronstein M M,Bronstein A M.Shape Recognition With Spectral Distances[J].Ieee Transactions on Pattern Analysis and Machine In?telligence,2011,33(5).

[18] 劉秉鐮.基于價值量的物流需求分析與預測方法研究[J].中國軟科學,2004,(5).

[19] 孫有望,周福東.我國宏觀物流市場預測與分析方法研究[J].同濟大學學報：自然科學版,2005,(1).

[20] Ling H,Okada K.An Efficient Earth Mover's Distance Algorithm for robust Histogram Comparison[J].Ieee Transactions on Pattern Analy?sis and Machine Intelligence,2007,29(5).

[21] 李國祥,夏國恩,高榮等.基于屬性約簡的區(qū)域物流需求預測[J].計算機應用與軟件,2013,(11).