劉倩玉，葉春明

(1. 安徽大學 計算機科學與技術學院 ，安徽 合肥 230601； 2. 合肥電子工程學院，安徽 合肥 246003)

?

一種基于最優(yōu)模型選擇的流量預測方法

劉倩玉1，葉春明2

(1. 安徽大學 計算機科學與技術學院 ，安徽 合肥 230601； 2. 合肥電子工程學院，安徽 合肥 246003)

摘要：本文提出一種基于ARMA(Auto-Regressive and Moving Average Model)最優(yōu)模型選擇的流量預測方法。該方法建立流量序列對應的ARMA模型集，利用OPTICS和K-Means兩種聚類算法對序列分類。通過對基于模型集的最佳預測結果和序列分類的分析，建立序列分類與模型之間的對應關系，并利用對應關系選擇針對序列類型的最優(yōu)模型預測。實驗表明該方法預測結果具有良好的精確度和穩(wěn)定性。

關鍵詞：流量預測；模型選擇；ARMA；K-means聚類算法；OPTICS聚類

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.013

網絡業(yè)務流量預測是進行網絡管理、資源分配和安全防護的重要手段。傳統(tǒng)的流量預測基于傳統(tǒng)時序分析手段，如基于AR(Autoregressive)、MA(Moving average)算法的自回歸移動平均模型(ARIMA[1])。以神經網絡為代表的機器學習算法將流量預測作為一類識別問題，對每個待預測值視其為若干前驅節(jié)點的分類值，通過訓練集建立分類模型后進行預測，并無需考慮流量短相關和長相關特征的影響，具有較好的預測效果，典型算法包括前饋(BP)網絡[2]、徑向基[3](RBF)網絡等。基于這些模型的方法從兩方面改進和提高預測效果：一是進行數據預測處理以提高模型的擬合度，二是改進模型的參數以提高模型預測精度。雖然這些方法在一定程度提高了預測效果，但是仍忽略了以下問題：(1)如何充分利用現有數據特點以建立更有效的模型；(2)類似機器學習算法的概念漂移問題仍存在，即由于訓練集和實際數據特征差別過大，致使預測模型與訓練集擬合程度較好，但仍可能對實際的數據預測效果較差。

針對這兩方面問題，本文提出一種基于最優(yōu)ARMA(Auto-Regressive and Moving Average Model)模型選擇的流量預測算法(OAMS，Optimal ARMA Model Selection)。算法利用序列的自相似性差異建立不同參數的ARMA模型集以彌補單一模型的不足，通過分析序列分類與模型集的預測結果，找出被測序列與最優(yōu)預測模型之間的關聯，對實際數據根據其序列分類選擇最佳模型預測。實驗結果顯示OAMS算法比傳統(tǒng)的模型在各項指標上都有明顯的提高。

1OAMS預測算法

OAMS算法利用序列的統(tǒng)計相似性對流量序列進行分類，并對同類的序列選擇特定的模型以期望獲得最佳的預測效果，算法基本步驟為

(1)劃分訓練集，選擇若干子序列建立模型集A；

(2)利用聚類算法分類待測序列；

(3)分析模型集A對待測序列的預測效果，得到待測序列類型與最佳預測模型之間的對應關系；

(4)根據待測序列的類型選擇最佳預測模型。

1.1建立待選模型集

OAMS算法預測部分利用ARMA模型進行計算，ARMA模型認為任意時刻的序列值xt由之前n個序列值和m個擾動決定，一般n階自回歸m階滑動平均模型記做ARMA(n,m)，n和m分別表示AR和MA部分的階次，ARMA計算方式[4]為

其中AR和MA各自模型的參數分別為φi(i=1,2,3,…,n),θj(j=1,2,3,…,m)。

OAMS算法利用已有數據建立多個ARMA模型并按照類別從中選擇最優(yōu)預測，以彌補單一模型預測能力的不足。按照統(tǒng)計特性差異最大的原則劃分原序列，利用序列自相似參數的差異從中選擇u個子序列用于建立模型集。如果u值為1則OAMS相當于傳統(tǒng)的ARMA算法；如果u值過大會影響預測的效率，一般綜合考慮原序列的長度和算法效率，選擇u的值為10左右，但可根據實際情況調整。自相似特性是流量序列基本的統(tǒng)計特征，表示不同尺度下序列自身各分段聚集之間的相似程度，可直觀理解為序列波形趨勢的差異，通常利用自相似參數H(也稱為Hurst參數)表示序列自相似性強弱。在ARMA模型中相關系數是對原序列中各分段預測效果的統(tǒng)計分析結果，利用自相似性可以選擇出波形差距最大的分段分別用于計算得出不同類型的模型系數。因此OAMS算法按照Hurst參數值差別最大化的原則選擇k個不同的子序列建立ARMA模型集，本文利用文獻[5]提出的q-moment方法計算Hurst參數。對于訓練集序列tr(t)(t=1,2,3…k)，從中挑選出Hurst值差別最大的u個長度為w的子序列，將tr的全部序列值也作為序列之一，共建立u+1個ARMA模型作為待選模型集A(i)(i=1,2, 3，…, u+1)。

1.2建立對應關系

建模的子序列由于統(tǒng)計特征的不同使得對應ARMA模型參數有較大差異，每個ARMA模型可能針對特定的待測序列有較好的預測效果，找出每個待測序列的最佳預測模型能大幅提高預測精度。OAMS算法首先對原序列進行劃分得到待測序列集S并進行分類，然后利用所有模型預測并從中提取部分較好的結果，進一步分析得出序列分類與最佳模型之間的關聯關系。具體步驟包括數據預處理、待測序列聚類分析、計算最優(yōu)預測模型矩陣和計算序列-模型對應關系索引表(SAI，Sequence-ARMAModelIndex)。

1.2.1基于聚類算法的待測序列分類

利用統(tǒng)計相似性可以對待測序列集S中所有序列進行分類，進而對同類的序列選擇效果最佳的ARMA模型預測。但實際監(jiān)測的網絡流量并非單一通信業(yè)務產生，多種業(yè)務數據疊加改變了業(yè)務流量的固有特征，本文首先利用基于密度的OPTICS聚類算法[6]，按照文獻[7]的可達圖方法挑選出聚集緊密的、最可能屬于同種業(yè)務的序列，再利用K-means算法對其余聚集特性稀疏、類型難以確定的序列(本文稱之為“噪聲序列”)進行分類，具體步驟如下

(1)利用OPTICS算法計算S集可達距離，得到有序節(jié)點對應的可達距離序列Rd(i)(i=1,2,3,…,n)；

(2)遍歷Rd，從中選擇每個波谷結構對應的簇。根據Rd的波形結構和斜率閾值，共找到k′個不同的簇；

(3)計算每個簇內所有對象的均值，作為對應分類向量c；

(4)計算每個分類向量與簇內所有序列的歐氏距離中的最大值，作為該分類的范圍D；

(5)利用K-means算法將剩下的對象分為k-k′類，得到分類向量集C(i)=[c(1), c(2),…, c(k)]T和對應的分類范圍D(i)(i=1,2,3,…,k)。為使分類的序列聚集程度更加緊密，可將D乘以系數y(0

(6)從S集中過濾掉上述已分類的高密度部分，得到其子集S′(i)=[s(1),s(2),…,s(j)]T；

(7)利用K-means聚類將S′集分為k-k′類，并得到分類向量集C′(i) =[c(1), c(2),…, c(k-k′)]T；

(8)計算每個分類所有序列與對應分類向量c(i)歐氏距離的均值，作為該分類的范圍D′(i)。

經過上述步驟，最終從待測序列集S中得到分類向量集C及對應的分類范圍集D，同時得到每個序列的類型列表K，其中C包括由OPTICS聚類生成的密度較大的分類對應的向量，以及由K-means聚類生成的密度較稀疏的分類對應的向量。分類范圍集D的值用于比較任意序列與對應分類向量的近似程度以判斷是否屬于該類。

1.2.2生成最優(yōu)預測模型矩陣

為找出單步預測下序列分類與模型之間的對應關系，利用模型集A中的所有u個模型對待測序列集S的所有序列進行預測，并將模型按照預測效果(即預測值最接近實際值)排序，生成最優(yōu)預測模型矩陣P(i,j) (i=1,2,3,…,n,j=1,2,3,…,u)，其中n為序列長度，u為模型數量，如圖1所示。矩陣P中任意行向量p(i)為針對S集中待測序列s(i)的預測結果，其中的元素為對應模型按照預測效果的排序，0代表利用全部訓練集數據建立的單一模型。P的第1列是利用A對待測序列集S預測理論上的最優(yōu)模型序列。由于建立模型集的方式不同，對應的最佳預測效果有差異，雖然這樣得出的并不是所有可能存在的最優(yōu)情況，但其效果已經遠遠超過利用相同數據建模和預測的其他常用方法，而且隨著訓練數據的增多，基于模型集的最優(yōu)預測結果越來越逼近真實值，但利用單一模型預測效果基本沒有變化。OAMS算法通過分析矩陣P(i,j)和序列集S(i,j)類別之間的關系，找出每種序列對應的最優(yōu)模型，使得每次預測能夠根據序列類別選擇最優(yōu)模型，使預測結果最大可能地逼近理論上的最優(yōu)值。

待測序列最佳預測模型矩陣

圖1待測序列和對應的最佳預測模型矩陣

1.2.3建立序列-模型對應關系

分析矩陣P，發(fā)現待測序列分類與最優(yōu)模型不存在嚴格的對應關系，可能受兩方面因素影響，一是序列分類方式；二是突發(fā)流量的隨機性使得同類序列可能存在不同的最優(yōu)預測模型。因此OAMS算法從矩陣P中選擇每種類型序列所占比例最高的模型作為最優(yōu)。建立序列-模型對應關系的SAI算法具體步驟如下

(1)針對k類待測序列，從第t類開始依次執(zhí)行以下操作，直到記錄序列類型與最優(yōu)模型對應關系的SAI表，其中t=1,2,3,…,k；

(2)選擇所有k類型序列及對應矩陣P(i,j) (i=1,2,3,…,n,j=1,2,3,…,u)中的最優(yōu)模型，得到新的矩陣Bk(i,j)(i=1,2,3,…,n′,j=1,2,3,…,u)，其中n′

(3)計算Bk(i,j)(i=1,2,3,…,n′,j=1,2,3,…,u/3)所有模型的比例并按降序排列，得到待選的最優(yōu)模型排列GA(i)(i=1,2,…u1,u1≤u)；

(4)計算Bk(i,j)(i=1,2,3,…,n′,j=2u/3+1, 2u/3+2,…,u)所有模型的比例并按降序排列，并只取其前1/3的部分，得到最差模型排列WA(i)(i=1,2,…u2,u2≤u/3)；

(5)依次檢測GA(i)(i=1,2,…,u1)，如果GA(i)?WA，則GA(i)為該類型序列對應的最佳模型，SAI(t)=GA(i)；如果GA(i)∈WA，則繼續(xù)檢測GA直至找到最佳模型。

1.3流量預測

OAMS利用訓練集數據生成預測模型集A，分類向量集C，分類范圍集D和SAI表，通過對任意待測序列分類和查詢SAI表，找出最優(yōu)模型進行預測。

按照上述分析同種類型序列其波形相近，OAMS算法計算序列與分類向量之間的歐氏距離并利用分類范圍D判斷是否屬于同類，對待測序列分類的算法ClassifySeq具體步驟如下

(1)對初始待測序列預處理，得新待測序列s；

(2)計算s與C中所有向量的歐氏距離，結果按升序排列，選擇最小距離d以及該對應的分類向量集C(i)。

(3)比較d和向量i對應的分類范圍D(i)，如果dD(i)，則表明s不在C(i)簇內，可能是噪聲序列，類別置為0；

(4)查找SAI表，按照待測序列s類別選擇A對應的最優(yōu)模型，若類別為0，對應的是單一模型；

(5)利用最優(yōu)模型預測s，計算得出預測結果。

2實驗驗證

為驗證算法的有效性，本實驗采用了兩種不同類型的數據[8-9]，分別以1 s、5 s、10 s和0.05 s作為時間周期計算其流量序列。取每個序列的前1 500個序列值進行分析，其中前400個序列值作為訓練集，并將第501-1 500個值分為等長的兩部分作為測試集(記為Ts1和Ts2)，各數據集分別記為Trace1，Trace2。

2.1實驗結果對比分析

2.1.1基本指標對比

分別選用BP神經網絡模型、OAMS(單純的K-means分類，簡稱K-OAMS)及結合OPTICS和K-means的OAMS模型(簡稱OK-OAMS)對上述數據集進行預測。實驗結果對比如表1-2所示，每個TS1的前100個預測序列值效果對比如圖2所示。

表2　Trace2預測結果對比 (k1=11，k=25)

從圖2可看出，OAMS算法的預測效果結合了兩者的特點，與單一的ARMA模型相比，保留了其基于序列趨勢變化的穩(wěn)定特性，因此基于統(tǒng)計特性的NMSE和RRMSE指標幾乎一直保持優(yōu)于其他算法的水平，同時提高了精確逼近的能力，RFA指標要明顯高于后者。

與BP神經網絡相比，OAMS算法很好地避免了因訓練集數據與測試集數據差別大造成模型訓練效果不佳的問題，例如在Trace2的預測結果中，BP算法出現了較大誤差，而OAMS算法受影響不大。另外受到參數的影響，BP算法難以同時兼顧流量突發(fā)性和平穩(wěn)性的特點，因此存在部分較大的誤差值，導致NMSE和RRMSE指標受到影響，而OAMS算法沒有此類問題。

雖然K-OAMS算法預測結果隨著聚類變化有差異，但總體效果仍優(yōu)于單一ARMA模型和BP算法，即便是較差的結果在多次實驗中也未發(fā)現各項指標均低于單一模型的情況，OK-OAMS算法預測結果相比更加穩(wěn)定。

2.1.2不同數據集預測結果分析

實驗結果表明，算法對不同類型數據預測效果存在差異。對Trace1常規(guī)的以太網流量，OAMS算法表現穩(wěn)定，各項指標處于較優(yōu)水平，特別對比BP算法有較大優(yōu)勢。Trace2的序列趨勢平穩(wěn)，但存在遠離一般趨勢的突發(fā)流量成分。因受到隨機分類的影響，K-OAMS算法預測效果起伏較大，當預測效果較好時各項指標領先于所有算法，但預測較差時與單一ARMA模型效果相仿，而OK-OAMS算法效果穩(wěn)定，接近K-OAMS預測的較好水平。BP預測算法受到訓練集影響預測效果遠差于其他幾種算法。

2.1.3預測誤差的穩(wěn)定性

除了預測的精確程度，誤差的波動也可用于衡量預測效果。如果預測算法性能穩(wěn)定，預測誤差將會落在更小的區(qū)間內，并且波動性更小。表3顯示的是幾種算法誤差值的標準差對比。

由表3可以看出，與ARMA算法相比，OAMS算法預測穩(wěn)定性更好，在所有情況下誤差更加穩(wěn)定，并且在大多數情況下穩(wěn)定性優(yōu)于BP算法。

表3　誤差結果的標準差對比

2.2實測數據驗證

為進一步驗證上述分析和仿真結果，利用Omnipeek采集了時長為180s，若干匿名用戶的802.11無線通信數據，分別利用BP模型和OK-OAMS模型進行流量預測分析，時間周期為0.1s，預測結果如圖3所示，指標對比如表4所示。

表4　實測數據預測結果對比

結果顯示，OK-OAMS模型對于實際數據的預測結果明顯優(yōu)于BP神經網絡模型等傳統(tǒng)方法。

(a)OK-OAMS模型預測 (b)BP模型預測

3結論

多數基于ARMA模型的預測算法只注重數據預處理和模型參數改進，而忽視了數據的自身特點對建立模型預測能力的影響，并且極少分析模型和待測序列之間的關聯。針對這一問題，本文從建立模型和選擇模型兩方面對預測方法進行改進，提出了基于最優(yōu)模型選擇的OAMS算法。仿真實驗和實際數據測試表明，OAMS算法的各項預測指標均顯著優(yōu)于一般的ARMA預測算法和BP神經網絡算法，并且預測階段的時間復雜度無明顯增加，預測結果具有較好的精確度和穩(wěn)定性。實驗結果顯示算法仍有較大的改進空間。下一步工作將對建模子序列的長度進行分析以提高理論最優(yōu)值的上限，研究待測序列的長度，并引入其他流量特征和分類方法以提高分類的精確度。對聚類的效果、分類的數量進行研究以進一步提高分類與模型的匹配度。

參考文獻:

[1]YuG，ZhangC.SwitchingARIMAmodelbasedforecastingfortrafficflow[C].IEEEInternationalConferenceonAcoustics,Montreal:IEEE,2004:c2004.

[2]DingL，SheJ，PengS.Anintegratedpredictionmodelfornetworktrafficbasedonwavelettransformation[J].ElectronicsandElectricalEngineering, 2013, 19(3): 73-76.

[3]郭通, 蘭巨龍, 李玉峰, 等. 基于量子自適應粒子群優(yōu)化徑向基函數神經網絡的網絡流量預測[J]. 電子與信息學報, 2013, 35(9): 2220-2226.

[4] 段智彬,孫恩昌,張延華,等. 基于ARMA模型的網絡流量預測[J]. 中國電子科學研究院學報，2009, 4(4): 352-356.

[5]MatteoTD，AsteT，DacorognaMM.Scalingbehaviorsindifferentlydevelopedmarkets[J].PhysicaA:StatisticalMechanicsandItsApplications, 2003, 324(1): 183-188.

[6]曾依靈, 許洪波, 白碩. 改進的OPTICS算法及其在文本聚類中的應用 [J]. 中文信息學報, 2008, 22(1): 51-60.

[7]AnkerstM，BreunigMM，KriegelHP,etal.OPTICS:Orderingpointstoidentifytheclusteringstructure[J].ACMSIGMODRecord, 1999, 28(2): 49-60.

[8]GeistR,SpicerK,WestallJ.Simulationmodelingofself-similarityinnetworktraffic[C].ProceedingsofCMG'99,1999.

[9]SchulmanA,LevinD,SpringN.CRAWDADdatasetumd/sigcomm2008[EB/OL].(2009-03-02)[2015-10-10].http://crawdad.org/umd/sigcomm2008/20090302.

Traffic Prediction Based on Optimal ARMA Model Selection

LIU Qian-yu1，YE Chun-ming2

(1.Computer Science and Technology College, Anhui University, Hefei, Anhui 230601, China 2. Electronic Engineering Institute, Hefei, Anhui 246003, China)

Abstract:Most traffic prediction schemes based on ARMA(Auto-Regressive and Moving Average Model) pay much attention to preprocessing data and model’s parameters rather than relationship between traffic sequences and prediction models. A novel method was proposed to find out more effective ARMA models according to their relationship. Short sequences were used to estimate ARMA models. Then these sequences were classified by OPTICS clustering and K-means algorithm. The correspondence between sequences and models were calculated with sequences’ type and prediction result. With the correspondence ARMA models were selected to predict certain sequence. The experiments show that prediction results of this method had good correctness and stability. Compared with other algorithms, this method has better performance for predicting different data traces.

Key words:traffic prediction; model selection; ARMA; K-means; OPTICS clustering

* 收稿日期：2015-10-18

作者簡介：劉倩玉，女，安徽合肥人，安徽大學計算機科學與技術學院學生，研究方向是信息安全技術等。 E-mail: lqytt0927@qq.com 通訊作者：葉春明，男，安徽安慶人，博士，電子工程學院講師，研究方向為網絡通信。E-mail:winshepherd@163.com

中圖分類號：TP393

文獻標識碼：A

文章編號：1007-4260(2016)02-0048-06

網絡出版時間：2016-06-08 12:57網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.013.html