局部加權(quán)回歸LSTM的帶寬異常值預(yù)測①

張 戈,翟劍鋒

(中國社會科學(xué)院大學(xué) 計算機(jī)教研部,北京 102488)

在中國互聯(lián)網(wǎng)迅猛發(fā)展的大背景下,網(wǎng)絡(luò)視頻的需求量激增,各大網(wǎng)站已經(jīng)紛紛采用CDN 網(wǎng)絡(luò)架構(gòu)以應(yīng)對在運營中遇到的各種難題,比如網(wǎng)站訪問量激增問題、如何提升網(wǎng)站的訪問速度問題、以及網(wǎng)站帶寬嚴(yán)重不足導(dǎo)致用戶無法正常訪問等問題.本文的研究目標(biāo)是根據(jù)帶寬時間序列數(shù)據(jù),可以準(zhǔn)確地預(yù)測下一時刻的帶寬值,依此對時間序列中的每個時間節(jié)點進(jìn)行實時監(jiān)控,發(fā)現(xiàn)并反饋異常點及其異常情況,及時向運維人員發(fā)出告警,從而幫助運維人員采取相應(yīng)后續(xù)措施,進(jìn)而有效地避免和解決運營中出現(xiàn)的各類問題和帶寬成本不可控制等難題.

本文提出了一個新的帶寬預(yù)測時序模型—局部加權(quán)回歸串行長短期記憶網(wǎng)絡(luò)(long short term memory network,LSTM)預(yù)測模型.針對原始帶寬數(shù)據(jù)具有的長時間依賴和數(shù)據(jù)單一等特點,使用按時序插值采樣的方法構(gòu)造數(shù)據(jù)集,擬合局部加權(quán)最小二乘法回歸模型,將其預(yù)測結(jié)果作為訓(xùn)練集串行LSTM 時序模型進(jìn)行最終帶寬異常值預(yù)測.使用4sigma 原則判斷某時刻帶寬是否為異常,并按等級標(biāo)準(zhǔn)發(fā)出異常告警.通過實驗證明,本文提出的模型泛化能力較強,可以較準(zhǔn)確地預(yù)測異常時刻,并按異常值的級別向運維人員發(fā)出準(zhǔn)確告警.

1 相關(guān)算法原理與分析

目前異常值的檢測方法有統(tǒng)計的方法、聚類的方法以及一些專門的異常值檢測算法[1]:基于概率分布模型[2]的異常值檢測,它把具有低概率的數(shù)據(jù)點判斷為異常值,該算法對于多元高維數(shù)據(jù)的異常檢測效果較差;基于K 近鄰(KNN)的離群點檢測,它依據(jù)數(shù)據(jù)點的距離以及K 值判斷出異常值[3],該算法過度依賴K 值的選擇,對密度不均衡的樣本數(shù)據(jù)不適用;基于密度的離群點檢測方法,使用DBSCAN 聚類算法[4]計算密度,依據(jù)密度定義異常值,該算法同樣依賴參數(shù)的選擇,且時間復(fù)雜度相對較高;基于聚類的方法判斷異常值,如果一個數(shù)據(jù)不強屬于任何一個簇,則該數(shù)據(jù)點為異常值,該算法對離群點的判斷依賴簇的個數(shù)和質(zhì)量;基于滑動窗口的異常檢測方法,該方法使用滑動窗口對原始時間序列進(jìn)行分割,利用擴(kuò)展的Frobenius 范數(shù)來判斷異常子序列,但面對大數(shù)據(jù)量的時間序列,算法的時間復(fù)雜度過高[5].這些異常值的檢測方法均不適用于本研究的數(shù)據(jù)異常值檢測情況.

在時間序列預(yù)測中,循環(huán)神經(jīng)網(wǎng)絡(luò)RNN是一種非常強大的對序列數(shù)據(jù)進(jìn)行建模和預(yù)測的神經(jīng)網(wǎng)絡(luò)工具[6].本研究嘗試使用RNN 模型進(jìn)行訓(xùn)練,但是在實際訓(xùn)練過程中,發(fā)現(xiàn)RNN 模型隨著其模型深度的不斷增加,會發(fā)生梯度爆炸或者梯度消失的現(xiàn)象.

LSTM 算法是誤差反向傳播算法[7],包括3 個步驟:前向計算每個神經(jīng)元的輸出值、反向計算每個神經(jīng)元的誤差項、根據(jù)相應(yīng)的誤差項計算每個權(quán)重的梯度[8].在LSTM的3 種門中,遺忘門是LSTM的關(guān)鍵組成部分,它決定了上一時刻的單元狀態(tài)Ct–1有多少信息可以保留到當(dāng)前時刻Ct.遺忘門的權(quán)重Wf的權(quán)重梯度,可以根據(jù)其相應(yīng)的誤差項δf,t計算獲得[9].通過反向調(diào)整誤差機(jī)制,LSTM 算法可以有效地解決循環(huán)神經(jīng)網(wǎng)絡(luò)的梯度消失或者梯度爆炸的問題.

1.1 最小二乘法

線性回歸是利用數(shù)理統(tǒng)計中回歸分析,來確定兩種或兩種以上變量間相互依賴的定量關(guān)系的一種統(tǒng)計分析方法[10].其表達(dá)形式為y=w′x+e,e為誤差服從均值為0的正態(tài)分布,使用最小二乘法[11]來確定模型的系數(shù).最小二乘法通過最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配.

1.2 局部加權(quán)最小二乘法

局部加權(quán)l(xiāng)owess (locally weighted regression)[12]是一種用于局部回歸分析的非參數(shù)方法.之所以我們這里采取加權(quán)最小二乘法,是因為我們發(fā)現(xiàn)離擬合點越近的樣本點,它的取值對擬合線的影響應(yīng)該更大,損失函數(shù)的定義應(yīng)該優(yōu)先降低與擬合直線距離近的點的誤差.

1.3 時間序列算法LSTM

長短期記憶網(wǎng)絡(luò)LSTM是一種特殊的遞歸神經(jīng)網(wǎng)絡(luò),它能夠?qū)W習(xí)長期依賴性,尤其是在長序列預(yù)測問題中表現(xiàn)不俗[13].標(biāo)準(zhǔn)LSTM 由遺忘門、輸入門、輸出門和隱藏狀態(tài)組成[14].LSTM的單元結(jié)構(gòu)如圖1[15]所示.LSTM 對時間序列的前期信息的存儲和更新是由這些門控來決定的.門控由Sigmoid 函數(shù)和點乘運算實現(xiàn),實質(zhì)是一個全連接層,它的一般公式為式(1)[16]:

圖1 LSTM 單元結(jié)構(gòu)圖

其中,σ(x)是Sigmoid 函數(shù),即非線性激活函數(shù)[17],可以將計算結(jié)果映射到[0,1]的區(qū)間中,當(dāng)它為0 時,代表沒有信息可以通過,當(dāng)它為1 時,代表所有信息都可以通過.W表示權(quán)重矩陣[7],b表示偏置值.

2 局部加權(quán)回歸LSTM 時序算法設(shè)計

帶寬異常值預(yù)測是高度依賴長距離時刻數(shù)據(jù)的時序問題,采用LSTM 作為模型進(jìn)行預(yù)測最為合適.LSTM框架中每一時刻的輸出誤差可以反向傳遞給前一時刻,使用梯度下降調(diào)整網(wǎng)絡(luò)參數(shù)[7].但是在實踐中我們發(fā)現(xiàn)帶寬預(yù)測中原始數(shù)據(jù)是真實帶寬值,其中包含異常值,異常值如果作為訓(xùn)練集會讓機(jī)器誤以為是正常值進(jìn)行學(xué)習(xí),因此非常有必要找到這些異常值,也就是噪點,并對他們進(jìn)行處理,處理后的數(shù)據(jù)再使用LSTM 進(jìn)行訓(xùn)練,會得到更為準(zhǔn)確的異常檢測結(jié)果.為此,本文提出了一個新的帶寬預(yù)測時序模型框架:首先采局部加權(quán)最小二乘法回歸擬合初始模型,使用初始模型的預(yù)測結(jié)果作為LSTM的訓(xùn)練集,真實值作為LSTM的驗證集,串行LSTM 時序算法進(jìn)行預(yù)測,然后使用4sigma方法比對原始真實值和現(xiàn)在的預(yù)測值的偏差,判斷異常等級,做出相應(yīng)級別的異常告警,包括以下幾個步驟:

1)數(shù)據(jù)預(yù)處理;

2)插值采樣生成回歸模型樣本點;

3)對樣本點數(shù)據(jù)進(jìn)行l(wèi)owess 局部加權(quán);

4)最小二乘法回歸擬合模型得出預(yù)測結(jié)果;

5)調(diào)整回歸系數(shù)λ 優(yōu)化模型;

6)將預(yù)測結(jié)果作為LSTM的輸入進(jìn)行訓(xùn)練;

7)采用4sigma 原則判斷帶寬異常值;

8)根據(jù)實際偏差與訓(xùn)練偏差的比例等級標(biāo)準(zhǔn)發(fā)出相應(yīng)異常警告.局部加權(quán)回歸LSTM 時序算法活動圖如圖2所示.

圖2 局部加權(quán)回歸LSTM 時序算法活動圖

2.1 插值采樣

本文在帶寬預(yù)測時,將訓(xùn)練集數(shù)據(jù)按照每43 個時刻點為一組進(jìn)行采樣,在每組時間序列中,前42 列作為訓(xùn)練集樣本點的特征,第43 列為其對應(yīng)的y,之后的樣本點均采用按時間梯形重疊的方法進(jìn)行插值采樣,具體過程如下:

1)原始數(shù)據(jù)的帶寬值是每間隔3 s的真實數(shù)據(jù),本文對處理后的4 萬多原始數(shù)據(jù)每間隔15 min 進(jìn)行一次插值采樣;

2)采樣過程使用時序重疊的方法:用第1 個時刻到第42 個時刻的帶寬數(shù)據(jù)作為預(yù)測模型的訓(xùn)練集樣本點的特征值,即x1,第43 個時刻的帶寬數(shù)據(jù)作為這個樣本點對應(yīng)的結(jié)果真實值y1;然后用第2 個時刻到第43 個時刻的帶寬數(shù)據(jù)作為第2 個訓(xùn)練集樣本點x2的特征值,第44 個時刻的帶寬數(shù)據(jù)作為第2 個樣本點對應(yīng)的真實值y2.以此類推,一共采樣出1 000 個樣本點,即1000 行42 列的X和1 000 行1 列的y,X具有42 個特征,X矩陣如式(2).

其中,m為1 000,n為42.插值采樣獲取時間序列如圖3所示.

圖3 插值采樣獲取時間序列示意圖

2.2 局部加權(quán)最小二乘法擬合模型

局部加權(quán)最小二乘法擬合模型流程如下:

1)使用每組時間序列(x1,x2,…,xn)(n=43)的前42 個時刻點作為一個擬合點的特征向量;

2)采用lowess 算法為擬合點數(shù)據(jù)局部加權(quán),距離擬合點遠(yuǎn)的樣本點權(quán)重低,距離近的樣本點權(quán)重高.距離公式為:

其中,xi是擬合點,xj是訓(xùn)練集的樣本點.權(quán)值函數(shù)有二次函數(shù)B和三次函數(shù)W[18],在經(jīng)過數(shù)據(jù)實驗后,發(fā)現(xiàn)三次函數(shù)下降速度過快,縮小了異常點閾值,本文使用二次函數(shù)B,函數(shù)公式為:

3)對數(shù)據(jù)進(jìn)行歸一化處理;

4)使用最小二乘法擬合模型[19],公式為:

其中,為預(yù)測值,X和Y為訓(xùn)練集x_train和y_train[20].

5)對模型進(jìn)行測評,評估指標(biāo)MSE 不滿足要求則調(diào)整回歸系數(shù)λ優(yōu)化模型[20].

上述過程完成后,調(diào)用LSTM 模型進(jìn)行后續(xù)操作.

2.3 異常值判斷算法和告警等級標(biāo)準(zhǔn)設(shè)計

2.3.1 異常值判斷算法設(shè)計

本文算法框架對帶寬值的預(yù)測依賴帶寬時序,對于帶寬預(yù)測這一獨立事件其結(jié)果影響因素單一,偏差是異常值的判斷依據(jù),偏差值屬于正態(tài)分布,目前對于此類情況通常采用“正態(tài)分布3sigma 原則”作為異常值判斷依據(jù)[21].偏差是指預(yù)測結(jié)果與真實值之間的差異.根據(jù)正態(tài)分布我們知道,測量值范圍在[x–σ,x+σ]的概率為0.682 7.在[x–3σ,x+3σ]的概率為0.997[21],其中x表示測量的平均值,σ表示偏差.本文經(jīng)過調(diào)節(jié)參數(shù),最終采用“4sigma 原則”作為異常值檢測方法:將4 個標(biāo)準(zhǔn)差作為基準(zhǔn),用驗證集的差值和測試集的4 個標(biāo)準(zhǔn)差相比,如果大于1,則說明這個值是異常值,表示帶寬異常,發(fā)出告警.

2.3.2 告警等級設(shè)計

實際的偏差與訓(xùn)練的偏差之間的絕對偏差表示了是否異常.而異常的程度可以用相對偏差表示,也就是實際偏差與訓(xùn)練偏差的比例,根據(jù)該比例值的大小設(shè)置了8 個告警級別,告警級別用變量 表示,告警級別如表1所示.

表1 異常告警級別

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

在局部加權(quán)最小二乘法模型預(yù)測部分,使用Matlab R2016a 作為開發(fā)平臺;在LSTM 時序模型部分,使用Keras+TensorFlow 框架,Spyder+Python 編程環(huán)境.

3.1 插值采樣數(shù)據(jù)集

原始數(shù)據(jù)是真實帶寬值,約為45 000 個數(shù)據(jù).首先進(jìn)行數(shù)據(jù)處理將數(shù)據(jù)單位轉(zhuǎn)換為GB,然后進(jìn)行插值采樣.每隔15 min 采樣一次.

3.2 局部加權(quán)最小二乘法擬合模型實驗

局部加權(quán)最小二乘法擬合模型預(yù)測結(jié)果如圖4所示,圖中紅色有“陡峭波峰”的曲線為真實值,藍(lán)色曲線為模型預(yù)測值.我們可以認(rèn)為明顯高于預(yù)測值的“凸點”為異常值,在模型中我們將他們作為噪點,用此刻的預(yù)測值進(jìn)行替代,作為LSTM的訓(xùn)練集和測試集.

圖4 局部加權(quán)最小二乘法擬合模型預(yù)測結(jié)果

3.3 LSTM 訓(xùn)練實驗

設(shè)置LSTM 網(wǎng)絡(luò)隱藏層神經(jīng)元個數(shù)為100,輸入特征維度為1,激活函數(shù)使用linear,樣本訓(xùn)練次數(shù)設(shè)置為100 次,網(wǎng)絡(luò)使用 Adam 優(yōu)化器,每批次處理100 條樣本,validation_split 訓(xùn)練集驗證集的分割值為0.33.LSTM 網(wǎng)絡(luò)結(jié)構(gòu)部分代碼如圖5所示.

圖5 LSTM 網(wǎng)絡(luò)結(jié)構(gòu)

3.3.1 模型評價

本文采用loss 曲線對模型進(jìn)行評價,并給出算法的時間復(fù)雜度對算法可行性加以說明.

使用loss 曲線作為評價標(biāo)準(zhǔn),損失函數(shù)loss 使用均方誤差MSE (mean squared error),其公式為:

圖6是模型的100 次完整訓(xùn)練過程,可以看出從第1 次完整訓(xùn)練到第100 次完整訓(xùn)練,訓(xùn)練集loss 值從0.016 4 降到了4.65e–04.

圖6 LSTM 執(zhí)行過程

圖7是100 次訓(xùn)練過程模型訓(xùn)練集和驗證集損失loss的對比圖,其中藍(lán)色(靠下)曲線是訓(xùn)練集loss 值隨著迭代過程的變化曲線,橙色(靠上)曲線是驗證集loss 值的變化曲線,可以看出訓(xùn)練集數(shù)據(jù)在大約第10 次訓(xùn)練之后loss 值已經(jīng)迅速降至趨近于0的數(shù)值,之后的訓(xùn)練其loss 均平緩趨近于0,訓(xùn)練集loss和驗證集loss 都已經(jīng)收斂并且它們之間相差不大,說明既沒有過擬合也沒有欠擬合,模型學(xué)習(xí)充分,效果良好.

圖7 訓(xùn)練集loss和驗證集loss 對比

模型算法主要包括局部加權(quán)最小二乘和LSTM 兩個部分.最小二乘法的時間復(fù)雜度正比于n2×k,其中n是特征數(shù),k是樣本數(shù)量.LSTM 算法的時間復(fù)雜度為n×d2,其中n為時間序列長度,d為向量長度.兩個部分的時間復(fù)雜度數(shù)量級都是O(n2),取兩個部分值大的作為模型的時間復(fù)雜度.因此按LSTM 進(jìn)行計算,模型時間復(fù)雜度為42×1002.經(jīng)過實驗,1728 個樣本數(shù)據(jù)的執(zhí)行時間穩(wěn)定在0:01:05.942850 左右,約1 min.1728 個樣本數(shù)據(jù)是取的3 天的帶寬監(jiān)測值,在實際應(yīng)用中,數(shù)據(jù)池維持在9 天的帶寬數(shù)據(jù)進(jìn)行預(yù)測,系統(tǒng)采用IntelR710 服務(wù)器,還可以提高約20%的執(zhí)行效率,該算法在實際應(yīng)用中具有可行性.

圖8是使用測試集對模型進(jìn)行準(zhǔn)確度計算的結(jié)果,模型預(yù)測準(zhǔn)確度為0.774 19,即約為77%.

圖8 模型準(zhǔn)確度

3.3.2 參數(shù)調(diào)整

(1)調(diào)整參數(shù)batch_size

如果batch_size 值設(shè)置過大,比如200,那么代碼執(zhí)行速度會快很多,但是預(yù)測精確度會降低;如果該值設(shè)置過小,比如5,精確度會較高但是代碼執(zhí)行速度會變慢.因此設(shè)置batch_size為100.

(2)調(diào)整參數(shù)epochs

從圖9可以看出,epochs為200 時,模型在第10 次訓(xùn)練之后訓(xùn)練集loss 值降為9.2092e–04.epochs為100 時,模型在第10 次訓(xùn)練之后訓(xùn)練集loss 值也已到達(dá)9.0460e–04,說明epochs為100 已經(jīng)足夠,模型訓(xùn)練已經(jīng)非常充分,不需要增至200.

圖9 epochs 設(shè)置為200和100 執(zhí)行過程

圖10是epochs 設(shè)置為50 時的驗證集loss和訓(xùn)練集loss(高線)對比曲線圖.可以看出驗證集loss和訓(xùn)練集loss 曲線間距generalization gap 增大,且訓(xùn)練集loss 在第14 次才降至8.6938e–04,后續(xù)仍有起伏,說明模型訓(xùn)練不充分,出現(xiàn)欠擬合的風(fēng)險比較大,因此epochs 值最后設(shè)置為100.

圖10 epochs 設(shè)置為50 驗證集和訓(xùn)練集loss

在異常值的判斷中結(jié)合預(yù)測值和真實值的偏差.圖11是每時刻預(yù)測結(jié)果和真實值的偏差,該值接近于0 說明偏差小.從圖中可見約在5:00、7:10、9:25、12:30 幾個時刻出現(xiàn)了明顯偏差,根據(jù)4sigma 原則判斷這4 個時刻為異常值,結(jié)果見圖12.除此4 個時刻外,其他時刻也有出現(xiàn)偏差的情況,比如在6:00 時刻也發(fā)生了偏差,但是其不符合4sigma的異常定量,所以模型判斷該時刻帶寬正常.

圖11 預(yù)測值和真實值的偏差

根據(jù)異常時刻實際偏差與訓(xùn)練偏差的比例Rela_BiasLevel 按值的大小分為8 個告警級別,值越大告警級別越高.圖12是模型測評的3 個異常時刻點的Rela_BiasLevel 定量告警示意圖.

圖12 異常值告警示意圖

4 結(jié)論與展望

本文以帶寬異常值預(yù)測為目標(biāo),從解決實際問題出發(fā),構(gòu)造了一套適用于研究目標(biāo)的異常值預(yù)測算法.該算法將局部加權(quán)l(xiāng)owess 融入最小二乘法回歸模型,使模型曲線更為平滑,有效的解決了回歸模型的欠擬合問題.該算法將局部加權(quán)最小二乘法擬合模型的輸出結(jié)果作為LSTM的訓(xùn)練集,起到了剔除噪點的作用,使得LSTM 預(yù)測結(jié)果更為準(zhǔn)確.從實驗結(jié)果來看,本文提出的異常值預(yù)測模型算法具有很高的實用價值,異常值預(yù)測結(jié)果較為準(zhǔn)確,有效地避免和解決了網(wǎng)絡(luò)運營中帶寬異常帶來的各類問題和帶寬成本不可控制等難題.

另外,本文的研究尚未結(jié)束,算法中仍有一些內(nèi)容有待研究.第一,局部加權(quán)回歸模型產(chǎn)生的誤差和LSTM 模型產(chǎn)生的誤差,會不會有疊加放大的情況,要如何消化這些誤差.第二,局部加權(quán)回歸模型的預(yù)測結(jié)果是否可以和原始樣本按一定比例合成數(shù)據(jù)作為LSTM的訓(xùn)練集.第三,可否在LSTM 每次反向傳播調(diào)整網(wǎng)絡(luò)參數(shù)時,加入局部加權(quán)的思想干預(yù)網(wǎng)絡(luò)參數(shù)的調(diào)整尤其是遺忘門的權(quán)重函數(shù)Wf.本課題將針對上述這些內(nèi)容展開后續(xù)研究.