局部加權回歸LSTM的帶寬異常值預測①

張 戈,翟劍鋒

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

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

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

1 相關算法原理與分析

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

在時間序列預測中,循環神經網絡RNN是一種非常強大的對序列數據進行建模和預測的神經網絡工具[6].本研究嘗試使用RNN 模型進行訓練,但是在實際訓練過程中,發現RNN 模型隨著其模型深度的不斷增加,會發生梯度爆炸或者梯度消失的現象.

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

1.1 最小二乘法

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

1.2 局部加權最小二乘法

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

1.3 時間序列算法LSTM

長短期記憶網絡LSTM是一種特殊的遞歸神經網絡,它能夠學習長期依賴性,尤其是在長序列預測問題中表現不俗[13].標準LSTM 由遺忘門、輸入門、輸出門和隱藏狀態組成[14].LSTM的單元結構如圖1[15]所示.LSTM 對時間序列的前期信息的存儲和更新是由這些門控來決定的.門控由Sigmoid 函數和點乘運算實現,實質是一個全連接層,它的一般公式為式(1)[16]:

圖1 LSTM 單元結構圖

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

2 局部加權回歸LSTM 時序算法設計

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

1)數據預處理;

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

3)對樣本點數據進行lowess 局部加權;

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

5)調整回歸系數λ 優化模型;

6)將預測結果作為LSTM的輸入進行訓練;

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

8)根據實際偏差與訓練偏差的比例等級標準發出相應異常警告.局部加權回歸LSTM 時序算法活動圖如圖2所示.

圖2 局部加權回歸LSTM 時序算法活動圖

2.1 插值采樣

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

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

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

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

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

2.2 局部加權最小二乘法擬合模型

局部加權最小二乘法擬合模型流程如下:

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

2)采用lowess 算法為擬合點數據局部加權,距離擬合點遠的樣本點權重低,距離近的樣本點權重高.距離公式為:

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

3)對數據進行歸一化處理;

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

其中,為預測值,X和Y為訓練集x_train和y_train[20].

5)對模型進行測評,評估指標MSE 不滿足要求則調整回歸系數λ優化模型[20].

上述過程完成后,調用LSTM 模型進行后續操作.

2.3 異常值判斷算法和告警等級標準設計

2.3.1 異常值判斷算法設計

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

2.3.2 告警等級設計

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

表1 異常告警級別

3 實驗結果和分析

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

3.1 插值采樣數據集

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

3.2 局部加權最小二乘法擬合模型實驗

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

圖4 局部加權最小二乘法擬合模型預測結果

3.3 LSTM 訓練實驗

設置LSTM 網絡隱藏層神經元個數為100,輸入特征維度為1,激活函數使用linear,樣本訓練次數設置為100 次,網絡使用 Adam 優化器,每批次處理100 條樣本,validation_split 訓練集驗證集的分割值為0.33.LSTM 網絡結構部分代碼如圖5所示.

圖5 LSTM 網絡結構

3.3.1 模型評價

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

使用loss 曲線作為評價標準,損失函數loss 使用均方誤差MSE (mean squared error),其公式為:

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

圖6 LSTM 執行過程

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

圖7 訓練集loss和驗證集loss 對比

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

圖8是使用測試集對模型進行準確度計算的結果,模型預測準確度為0.774 19,即約為77%.

圖8 模型準確度

3.3.2 參數調整

(1)調整參數batch_size

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

(2)調整參數epochs

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

圖9 epochs 設置為200和100 執行過程

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

圖10 epochs 設置為50 驗證集和訓練集loss

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

圖11 預測值和真實值的偏差

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

圖12 異常值告警示意圖

4 結論與展望

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

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