基于改進的網(wǎng)格搜索SVR的話務預測模型＊

郭美麗，覃錫忠，賈振紅，陳 麗

（1.新疆大學信息科學與工程學院，新疆 烏魯木齊 830046；2.中國移動通信集團新疆有限公司，新疆 烏魯木齊 830063)

基于改進的網(wǎng)格搜索SVR的話務預測模型＊

郭美麗1，覃錫忠1，賈振紅1，陳 麗2

（1.新疆大學信息科學與工程學院，新疆 烏魯木齊 830046；2.中國移動通信集團新疆有限公司，新疆 烏魯木齊 830063)

話務預測是整個通信保障工作的基礎(chǔ)，其預測精度決定了整個規(guī)劃的合理性和科學性。而節(jié)假日話務量，具有歷史樣本量較小和非線性強的特點，傳統(tǒng)的預測方法很難實現(xiàn)精確的預測。支持向量機在解決小樣本和非線性問題時表現(xiàn)出許多特有的優(yōu)勢。提出了一種改進的網(wǎng)格搜索法和交叉驗證法對支持向量回歸機（SVR)參數(shù)優(yōu)化選擇，并對節(jié)假日忙時話務進行預測，并與BP神經(jīng)網(wǎng)絡、基本的SVR和網(wǎng)格搜索SVR三種預測模型進行比較。而且用免疫算法和粒子群算法優(yōu)化SVR參數(shù)與本文算法作比較來預測普通日子的話務量。實驗結(jié)果表明，基于改進的網(wǎng)格搜索SVR預測精度高、耗時少、穩(wěn)定性強，具有很好的實用性和推廣性。

節(jié)假日話務預測；支持向量回歸機；改進的網(wǎng)格搜索法

1 引言

每逢重大節(jié)假日，如春節(jié)、國慶節(jié)等，移動通信網(wǎng)絡都面臨著高話務的沖擊。雖然給通信公司帶來了巨額的收入，但同時也帶來了巨大的壓力，因為過高的話務量極易造成交換系統(tǒng)過載，出現(xiàn)電路擁塞、話音接通率下降等現(xiàn)象，給用戶也帶了極大的不便。而話務量預測是整個通信保障工作的基礎(chǔ)，也是移動運營商進行網(wǎng)絡規(guī)劃和建設的依據(jù)，其預測精度決定了整個規(guī)劃的合理性和科學性。因此，移動運營商對話務量預測技術(shù)的需求非常急迫。

目前，對回歸預測的研究方法有時間序列法、神經(jīng)網(wǎng)絡預測法、支持向量機SVM（Support Vector Machine)［1］等，實際應用中上述方法對月平均話務量、月忙時話務量等能取得較好的效果。但是，節(jié)假日當天忙時話務量存在較強的非線性，主要表現(xiàn)在話務量增長在區(qū)域分布上不均衡、互聯(lián)互通話務量增長與本地營銷策略關(guān)系大和長途話務量的增長幅度大等方面。針對上述問題，傳統(tǒng)的預測方法很難實現(xiàn)精確的預測，本文采用優(yōu)化參數(shù)的支持向量回歸機建立預測模型。

支持向量機以統(tǒng)計學習理論SLT（Statistical Learning Theory)為基礎(chǔ)，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數(shù)擬合等其他機器學習問題中［2］。近幾年，支持向量機作為一種預測工具，已經(jīng)應用在了醫(yī)療診斷［3］、電力負荷預測［4］以及能量輸出預測［5］等方面。但是，在實際使用支持向量機時，支持向量機參數(shù)的尋優(yōu)非常重要，合適的參數(shù)可以直接提高方法性能。本文主要研究的節(jié)假日話務量是非線性強的小樣本問題，所以本文提出一種改進的網(wǎng)格搜索算法來提高參數(shù)優(yōu)化的準確率，進而提高其優(yōu)化速度。該方法用于新疆各地區(qū)節(jié)日話務預測，取得了比較滿意的結(jié)果，在非節(jié)假日的小樣本話務預測中也取得了較好的結(jié)果。

2 ε－支持向量回歸機（ε-SVR)理論［6］

支持向量機是基于Vapnik提出的小樣本統(tǒng)計學習理論建立的，以訓練誤差作為優(yōu)化問題的約束條件，以置信范圍最小化為優(yōu)化目標。它最終是求解一個凸規(guī)劃問題，或者是一個二次規(guī)劃（QP)問題。對于一組給定的數(shù)據(jù)集T＝｛（x1，y1)，…，（xi，yi)｝?Rd×R，i＝1，…，n，回歸問題就是要估計出xi與yi的關(guān)系：

其中〈·，·〉對應Rd空間的內(nèi)積。Φ（·)為核函數(shù)，可以把訓練數(shù)據(jù)映射到高維空間F上，因此在原空間上解決非線性問題就等同于在新的高維空間上解決線性回歸問題。

機器學習理論對這一問題可以表述為在一組函數(shù)｛f（x，ω)｝中尋求一個最優(yōu)的函數(shù)｛f（x，ω＊)｝，使得預期的期望風險R（ω)達到最小。

其中，n為樣本容量，h為VC維。支持向量機理論把式（2)轉(zhuǎn)化為尋求如下問題的最優(yōu)解：

其中，ε由不敏感損失函數(shù)L（y，f（x，a))來定義，決定了回歸曲線的平坦程度，這里是事先取定的一個正數(shù)，且0＜ε＜1。當x點的觀察值y 與預測值f（x)之差不超過事先給定的ε時，則認為在該點的預測值f（x)是無損失的，盡管預測值f（x)和觀測值y可能并不完全相等。

式（3)中C為懲罰因子，表示對錯分樣本的懲罰。

由此支持向量機所求得的回歸函數(shù)可以表示為：

在SVR建模中，考慮到RBF核函數(shù)所體現(xiàn)出的較好的性能［7］，本文選取式（4)RBF來進行建模研究。實際應用中大多憑經(jīng)驗確定參數(shù)或采用試算法，導致由于參數(shù)選擇不準確而使最后的預測精度低于目標精度。因此，核函數(shù)參數(shù)和懲罰系數(shù)C的選擇對SVR的性能至關(guān)重要，只有選擇合適的模型參數(shù)，SVR的優(yōu)越性才能更好地發(fā)揮出來。

3 SVR參數(shù)選擇方法

3.1 SVR模型選擇的研究現(xiàn)狀

SVR的參數(shù)選擇問題，其實質(zhì)就是一個優(yōu)化問題。在ε-SVR算法中，參數(shù)γ、C、ε對支持向量機的性能有著十分重要的影響。參數(shù)γ影響數(shù)據(jù)在高維空間中分布的復雜度；參數(shù)C是經(jīng)驗風險和置信范圍的裁決；參數(shù)ε確保對偶變量的稀疏性，同時確保全局最小解和可靠泛化界的優(yōu)化。比較常用的三種參數(shù)尋優(yōu)方法是遺傳算法、粒子群優(yōu)化算法和網(wǎng)格搜索法［7］。前兩種算法容易陷入局部極值，無法保證得到最優(yōu)參數(shù)。近幾年發(fā)展起來的人工智能新方法——免疫算法［8］，克服了遺傳算法的缺陷，能夠?qū)さ饺肿顑?yōu)解，但其運算耗時較長?；镜木W(wǎng)格搜索遍歷了在搜索范圍內(nèi)所有的參數(shù)組合，可搜索到最優(yōu)參數(shù)，但是運算量大、耗時長。

對于支持向量機的參數(shù)優(yōu)化問題要根據(jù)實際問題具體解決，本文選擇網(wǎng)格搜索SVR參數(shù)具有以下優(yōu)勢：（1)可以搜索到最優(yōu)參數(shù)；（2)本文只需搜索兩個參數(shù)（因為由話務預測的先驗知識可知SVR的最優(yōu)參數(shù)ε均在［0.0098，0.0109］，所以為了節(jié)省搜索時間，本文設定ε＝0.01)，因此運行時間相對較少；（3)每組參數(shù)（C，γ)都是獨立的，因此很容易實現(xiàn)并行計算。為了使網(wǎng)格搜索能更快更精確地尋到最優(yōu)參數(shù)，本文提出交叉驗證與改進的網(wǎng)格搜索法進行SVR參數(shù)選擇，進而對樣本小、非線性強的節(jié)假日忙時話務量進行預測。

3.2 網(wǎng)格搜索法

網(wǎng)格搜索算法是一種窮舉法，在參數(shù)空間每維上取若干分格，遍歷輸入空間中所有網(wǎng)格交叉點，得到最優(yōu)解。該算法首先確定每個參數(shù)的取值范圍，然后對每個參數(shù)取值范圍按照一定規(guī)律插值，得出若干組參數(shù)組合；對每組參數(shù)組合進行一次計算，應用交叉驗證計算其預測誤差；對應于預測誤差最小的參數(shù)組合，就是最優(yōu)的參數(shù)取值。網(wǎng)格搜索法計算過程中各組參數(shù)相互解耦，便于并行計算，運行效率高［9］。本文提出一種改進的網(wǎng)格搜索法來提高優(yōu)化準確率和優(yōu)化速度。

3.3 改進的網(wǎng)格搜索法

傳統(tǒng)的網(wǎng)格搜索比較耗時，且不一定能搜索到滿足精度要求的最優(yōu)參數(shù)組合，改進的網(wǎng)格搜索算法通過自動改變搜索范圍和搜索步長來更精細地搜索最優(yōu)參數(shù)，最終預測出符合要求的預測精度。該方法選擇最佳參數(shù)（C，γ)的具體步驟如下：

步驟1設定參數(shù)C和γ的取值范圍，再設定比較大的搜索步長，以2的冪次方沿著兩個參數(shù)的不同增長方向生成網(wǎng)格。這樣既能遍歷所有的參數(shù)，又能方便網(wǎng)格的收縮與增長。由此參數(shù)將區(qū)間分別分為M、N等分，網(wǎng)格中的節(jié)點即為給定范圍內(nèi)所有可能得到的參數(shù)對。

步驟2針對所有分割組合（Ci，γj)（i＝1，…，M，j＝1，…，N)，對樣本集進行訓練和測試，比較得到使評價函數(shù)最小的參數(shù)組合（Ci，γj)，判斷是否滿足精度要求或結(jié)果穩(wěn)定，如果是則轉(zhuǎn)到步驟4，否則轉(zhuǎn)到步驟3。

步驟3選取參數(shù)（Ci，γj)相鄰的兩個區(qū)間作為新 的 參 數(shù) 范 圍 C∈ ［Ci－1，Ci＋1］，γ∈ ［γj－1，γj＋1］，并且分別減少搜索步長的2倍 （可使用其他的收縮率，但因子－2－收縮率是方便的，因為網(wǎng)格數(shù)是2的冪次方)；再次搜索最優(yōu)參數(shù)組合，判斷是否滿足精度要求或結(jié)果穩(wěn)定，如果是則轉(zhuǎn)到步驟4，否則在這一步不斷循環(huán)直到尋找到最優(yōu)的一組參數(shù)組合。

步驟4存儲參數(shù)，參數(shù)優(yōu)化結(jié)束。

4 實例分析

4.1 樣本選擇

歷史數(shù)據(jù)是話務預測的基石，但歷史數(shù)據(jù)并非越多越好。在進行預測時，一定要選取具有較大相關(guān)性的歷史數(shù)據(jù)，數(shù)據(jù)的相關(guān)性越強，對預測準確性的幫助就越大。所謂相關(guān)性，是指歷史數(shù)據(jù)所依存的業(yè)務環(huán)境與現(xiàn)有環(huán)境具有較大的相似性。但是，在選取預測基準數(shù)據(jù)時，往往沒有足夠的相關(guān)性數(shù)據(jù)。這其中很重要的一個原因是：直接從ACDSee獲得的數(shù)據(jù)往往存在著各種異常因素。如：系統(tǒng)故障等原因引起的數(shù)據(jù)缺失，促銷活動、異常天氣等引起的話務量異動等。為了解決相關(guān)性數(shù)據(jù)缺乏的問題，通常需要對歷史數(shù)據(jù)進行清洗，如剔除缺失數(shù)據(jù)、修正異常數(shù)據(jù)等，這個過程其實就是要提高數(shù)據(jù)的相關(guān)性，使之更能反映業(yè)務現(xiàn)狀的特點。本文主要研究的是節(jié)假日的話務量，節(jié)假日話務量往往具有峰值特性，因此，我們只需選擇相關(guān)性大的數(shù)據(jù)也就是峰值周圍的數(shù)據(jù)做樣本，并對這些樣本做異常數(shù)據(jù)修正，從而導入到話務預測模型中進行預測。

本文實驗的數(shù)據(jù)是實時新疆移動通信話務量數(shù)據(jù)，話務量歷史數(shù)據(jù)包括新疆16個地州從2004年1月～2012年5月每天每小時的話務量。為了使移動運營商能夠根據(jù)預測出的節(jié)日忙時話務量對話務信道及時做處理，保障話務高峰期的正常通信，并且能降低誤差和減少訓練時間，達到最佳的預測效果，本文剔除掉節(jié)日前10天的話務數(shù)據(jù)，選取每年節(jié)日10天前的20天最忙時話務量做輸入樣本，歷年節(jié)日當天話務做輸出樣本，同時橫向和縱向訓練，建立預測模型，最終預測出要預測的節(jié)日當天最忙時話務量。本文以預測2012年元旦忙時話務量為例，隨機選取新疆五個地區(qū)做預測分析。

4.2 話務預測步驟

改進的網(wǎng)格搜索優(yōu)化支持向量機進行節(jié)假日話務預測的步驟如下：

步驟1對話務數(shù)據(jù)進行預處理，主要是對一些缺失數(shù)據(jù)和異常數(shù)據(jù)進行相應處理，如對這些數(shù)據(jù)取相近的數(shù)據(jù)填補；

步驟2將選用的話務量數(shù)據(jù)劃分為訓練樣本和測試樣本，并將這些數(shù)據(jù)進行歸一化處理；

步驟3本文設定ε＝0.01，設定網(wǎng)格搜索的C、γ值的初始搜索范圍和步長，這里設置為γ∈［2－8，28］，步長為1，C∈［2－8，28］，步長為1；

步驟4根據(jù)樣本集，利用改進的網(wǎng)格搜索法和交叉驗證［8］找出最佳參數(shù)組合（Ci，γj)（交叉驗證誤差是推廣誤差的一種近似無偏估計，在很多情況下表現(xiàn)出比其他估計量更好的性能［10］，本文采用5－折交叉驗證)；

步驟5根據(jù)樣本集和最優(yōu)的（Ci，γj)組合，建立基于網(wǎng)格搜索的支持向量機話務預測模型；

步驟6利用建立好的模型對話務量進行預測。

4.3 預測結(jié)果及分析

本文采用MATLAB編寫改進的網(wǎng)格搜索尋參程序，結(jié)合libsvm支持向量機工具箱，用均方誤差MSE作為評價指標。

其中，Xi（i＝1，2，…，n)是真實值，Yi（i＝1，2，…，n)是預測值，MSE越接近于零，預測效果越好。輸入向量的維數(shù)選取8，則支持向量回歸機的輸入值與目標值可以表述為：

SVR參數(shù)選擇效果如圖1所示。得到的最優(yōu)參數(shù)建立SVR預測模型，代入預測樣本數(shù)據(jù)進行運算，預測效果如圖2所示。

Figure 1 SVR parameters choice圖1 SVR參數(shù)選擇圖（3D視圖)

為了說明該方法的優(yōu)越性，本文首先選取了BP網(wǎng)絡、傳統(tǒng)SVR和網(wǎng)格搜索SVR與之進行對比，對新疆五個地區(qū)元旦當天忙時話務量進行預測。預測誤差用相對誤差Erep表示，結(jié)果如表1所示。

其中，Xi（i＝1，2，…，n)是真實值，Yi（i＝1，2，…，n)是預測值。

通過表1可知，本文基于改進的網(wǎng)格搜索SVR取得了較好的預測結(jié)果，其誤差均小于5%，且穩(wěn)定，運行時間均在3秒左右，符合規(guī)范預測精度，完全滿足實際預測的需求。而SVR模型雖然運行速度很快，但很難尋到最優(yōu)模型參數(shù)，需人手動多次試驗，若有豐富的經(jīng)驗知識，可能會得到較理想的預測結(jié)果；BP網(wǎng)絡效果要略好于SVR，但由于BP網(wǎng)絡易陷入局部極小，預測值波動很大，所以很難對每個地區(qū)做精確的預測。基本的網(wǎng)格搜索SVR雖然取得了比較穩(wěn)定的結(jié)果，但會出現(xiàn)個別地州達不到實際要求的精度，即沒有搜索到最優(yōu)參數(shù)組合。而本文算法通過改變搜索范圍和搜索步長更精細地搜索最優(yōu)參數(shù)直到滿足要求的精度才停止。因此，無論是從預測精度還是耗時來說，基于改進的網(wǎng)格搜索的SVR模型均優(yōu)于傳統(tǒng)的SVR模型、網(wǎng)格搜索SVR模型和BP神經(jīng)網(wǎng)絡模型。

Table 1 Comparison of forecast result 1表1 預測結(jié)果分析表1

該話務預測模型不僅適合于非線性強的節(jié)假日忙時話務預測，也適合平常話務（非節(jié)假日)的預測。目前支持向量機參數(shù)的選擇方法有很多，仍沒有形成一個統(tǒng)一的模式，一般視具體情況而定。本文隨機選取五個地區(qū)的某個平常日子代入話務模型進行預測，另選免疫算法（IA)和粒子群算法（PSO)對SVR尋優(yōu)并應用于話務預測模型。與本文算法比較，由于前兩種算法每次運行的結(jié)果不同，某次結(jié)果可能是陷入局部極值時所得，不能代表整體預測效果，所以前兩種算法均運行50次，取結(jié)果的平均值，各算法的誤差和運行時間結(jié)果如表2所示。

由表2可知，三種算法誤差因地區(qū)的不同而不同，總體效果差不多。但是，由于PSO-SVR易陷入局部極值，且運行次數(shù)多，消耗時間長，IA-SVR能夠搜索到全局最優(yōu)解，但其運算耗時還是較長，在實際應用中影響工作效率；而本文提出的改進的網(wǎng)格搜索法能安全地搜索到SVR的最優(yōu)參數(shù)，不會陷入局部極值且每次運行的結(jié)果是相同的。所以，本文提出的算法模型只需運行一次就可得到穩(wěn)定的值。因此本文算法在穩(wěn)定性和運行時間上都有很大優(yōu)勢。

Table 2 Comparison of forecast result 2表2 預測結(jié)果分析表2

5 結(jié)束語

本文利用改進的網(wǎng)格搜索法對支持向量機的關(guān)鍵參數(shù)進行尋優(yōu)，然后進行交叉驗證，找出使交叉驗證精確度最高的（C，γ)對，進而建立模型并預測話務量，實現(xiàn)了支持向量回歸機參數(shù)的自動優(yōu)化選擇，避免了通過實驗人工選擇的盲目性。實驗結(jié)果表明，本文算法在穩(wěn)定性、準確率和運行速度等方面明顯優(yōu)于現(xiàn)有算法，是一種預測忙時話務量的有效方法。當然，本文提出的改進的網(wǎng)格搜索法還處于研究的初步階段，對于參數(shù)較少的模型能有效地搜索到最優(yōu)值，但對于參數(shù)多的模型，搜索復雜度加大，可能比較耗時，有待進一步探索。

［1］ Vapnik V.Statistical learning theory［M］.New York：John Wiley＆Sons，1998.

［2］ Zhang Xue-gong.About the statistical learning theory and support vector machine［J］.ACTA Automatica SINICA，2000，26（1)：32-42.（in Chinese)

［3］ Khandoker A H，Palaniswami M，Karmakar C K.Support vector machines for automated recognition of obstructive sleep apnea syndrome from ECG recordings［J］.IEEE Transactions on Information Technology in Biomedicine，2009，13（1)：37-48.

［4］ Elattar E E，Goulermas J Y，Wu Q H.Electric load forecasting based on locally weighted support vector regression［J］.IEEE Transactions on Systems， Man and Cybernetics，2010，40（1)：438-447.

［5］ Shi Jie，Lee Wei-Jen，Liu Yong－qian，et al.Forecasting power output of photovoltaic systems based on weather classification and support vector machines［C］∥Proc of the IEEE Annual Meeting on Industry Applications（IAS)，2011：1-6.

［6］ Deng Nai-yang，Tian Ying－jie.A new method of data mining：Support vector machine［M］.Beijing：Science Press，2004.（in Chinese)

［7］ Wu Hai-wei，Yu Hai-ye，Zhang Lei.The net photosynthetic rate prediction model based on the optimized support vector machine［J］.Spectroscopy and Spectrum Analysis，2011，31（5)：1414-1418.（in Chinese)

［8］ Huang Yan-qiu.The IA -SVM algorithm research in network intrusion detection［J］.The Computer Simulation，2011，28（1)：182-186.（in Chinese)

［9］ Feng Guo-he.The large sample support vector research based on the clustering［J］.Computer Science，2006，33（4)：145-147.（in Chinese)

［10］ Duan K，Keerthi S S，Poo A N.Evaluation of simple performance measures for tuning SVM hyperparameters［J］.Neurocomputing，2003，51：41-59.

附中文參考文獻：

［2］ 張學工.關(guān)于統(tǒng)計學習理論與支持向量機［J］.自動化學報，2000，26（1)：32-42.

［6］ 鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法：支持向量機［M］.北京：科學出版社，2004.

［7］ 武海巍，于海業(yè)，張蕾.基于參數(shù)優(yōu)化支持向量機的林下參凈光合速率預測模型［J］.光譜學與光譜分析，2011，31（5)：1414-1418.

［8］ 黃艷秋.IA-SVM算法在網(wǎng)絡入侵檢測中的研究［J］.計算機仿真，2011，28（1)：182-186.

［9］ 奉國和.基于聚類的大樣本支持向量研究［J］.計算機科學，2006，33（4)：145-147.

The prediction model of traffic based on improved grid search SVR

GUO Mei-li1，QIN Xi-zhong1，JIA Zhen-hong1，CHEN Li2
（1.College of Information Science and Engineering，Xinjiang University，Urumqi 830046；2.China Mobile Group Xinjiang Company Limited，Urumqi 830063，China)

The traffic prediction is the basis of the whole communication＇s security work，whose prediction accuracy determines the rationality and scientificity of the entire plan.While the prediction of holiday＇s traffic has the characteristics of small historical sample size and strong nonlinear，it is hard to realize accurate prediction for the traditional prediction method.An improved grid search method for selecting the optimized parameter of Support Vector Regression machine（SVR)and then predicting the busy traffic in holidays is proposed and compared with BP neural network，SVR and grid search SVR.And the traffic of general days is predicted by comparing our method with Immune algorithm and Particle Swarm Optimization algorithm in optimizing SVR parameters.The experimental results show that the improved grid search SVR has a higher forecast precision，a less time－consuming and a strong stability，thus having good practicality and promotion.

prediction of holiday＇s traffic；support vector regression machine；improved grid search method

1007-130X（2014)04-0707-06

TP181

A

10.3969/j.issn.1007-130X.2014.04.023

2012-09-11；

2012-12-19

中國移動通信集團新疆有限公司發(fā)展基金項目（XJM2011-11)

通訊地址：830046新疆烏魯木齊市勝利路14號新疆大學信息科學與工程學院

Address：College of Information Science and Engineering，Xinjiang University，14Shengli Rd，Urumqi 830046，Xinjiang，P.R.China

郭美麗（1987-)，女，新疆塔城人，碩士生，研究方向為人工智能和移動通信。E-mail：guomeili314＠126.com

GUO Mei-li，born in 1987，MS candidate，her research interests include artificial intelligence，and mobile communications.

覃錫忠（1964-)，男，重慶人，碩士，副教授，研究方向為通信與信息處理。E-mail：qmqqxz＠163.com

QIN Xi-zhong，born in 1964，MS，associate professor，his research interest includes communication and information processing.

賈振紅（1964-)，男，河南洛陽人，博士，教授，研究方向為光通信和信號處理。E-mail：jzhh＠xju.edu.cn

JIA Zhen-hong，born in 1964，PhD，professor，his research interests include optical communication，and signal processing.

陳麗（1980-)，女，新疆烏魯木齊人，碩士，高級工程師，研究方向為移動通信。E-mail：chenli＠xj.chinamobile.com

CHEN Li，born in 1980，MS，senior engineer，her research interest includes mobile communication.