基于馬爾可夫時變模型的流量數據挖掘

葉德忠+巫忠正+蔣勇

摘要：隨著網絡技術的快速發展，目前網絡的規模很大且有較大的復雜性，因此網絡管理變得越來越困難和復雜，因此流量預測在網絡管理中發揮越來越重要的作用。針對實際網絡中收集到的大量實際流量數據，提出了一種基于時變網絡的自適應網絡流量預測算法，采用自適應學習率法，根據總誤差增減變化趨勢以及不同的改變來調整適應率；然后根據正向和反向的計算來校正各層的權重。仿真結果表明，與傳統的時變網絡相比，基于傳播時變網絡的自適應流量預測算法在預測結果中具有更好的性能，并具有較小的誤差。

引言

傳統的網絡流量模型對數據中存在的大量冗余屬性和噪聲數據處理并不到位，使得模型系統存在占用資源多，運行效率不高等缺點。因此需要研究出能對數據特征進行約減，同時保證較高精度的流量模型。受人類大腦中的學習過程的啟發，時變網絡（TNN）在許多科學領域被采用，它利用互連的數學節點或時變神經元來形成網絡來建模復雜的函數關系，可以幫助認知科學家了解時變神經系統的復雜性。時變網絡模型中最受關注的是馬氏反饋時變網絡，它使用三層形式的時變網絡結構，輸入時變神經元層，隱藏時變神經元層和輸出時變神經元層。

本文考慮到MARKOV可以以更好的泛化和容錯能力操作，在網絡流量異常后，提取特征向量，根據這些異常數據流的分析和處理，可以完全準確地表示數據流，然后將這些特征向量作為時變網絡輸入提交給時變網絡引擎。時變網絡引擎分析和處理這個特征向量以確定行為是否是入侵，如果是攻擊，則它將向用戶發送警告消息并將該信息記錄在日志文件中。如果攻擊者提高和更新樣本庫的報警信息具有很大的價值，例如，發現了一種新型的攻擊行為，可以在攻擊樣本庫中添加報警以準備進一步學習，從而可以增加時變網絡的處理能力。本文方法可以解決傳統流量模型和算法會受到屬性冗余影響的缺陷，在保證運行效率的情況下，提供了較高的準確率。

1 MARKOV時變網絡模型

MARKOV時變網絡模型是一個全連接的時變網絡，包括輸入層，隱層和輸出層。訓練過程的目的是找到最小化一些總體誤差測量的權重、平方誤差（SSE）或均方誤差（MSE）。網絡訓練實際上是一個無約束非線性最小化問題。

對于網絡流量的預測，網絡流量的序列號與多步相關聯，即當前采樣流和過去采樣周期之間存在一定的關系。設x_k（k=l，2...N）表示第k個采樣間隔的p個流（p≥1）的預測模型，則步驟k+l（1≥1）定義為：

即，f是第k+1個采樣間隔的第k+1個流和其之前的p個流之間的關系，f是非線性函數。

由于時變網絡層中的連接權重的初始值是任意的，必須訓練時變網絡以確保期望輸出值和實際值之間的偏差盡可能小，MARKOV時變網絡反向發送實際輸出的樣本到層的時變神經元，不斷地使用梯度下降法調整層的權重，以減少由權重引起的誤差，確保訓練樣本的實際輸出和時變網絡的輸出之間的誤差在設定范圍內的限制或訓練的數量是最大的。其中n是樣本數。調整權重。采用梯度下降法求解最小誤差函數，

為了測試預測性能，本文使用一些指標等來測試預測性能，包括平均絕對誤差（MAE），均方誤差（MSE），誤差平方和（SSE），標準均方誤差（NMSE）。

2 分離預測

本文采用白適應學習率法和改進的訓練算法對各層進行分離預測。自適應學習率法的基本原則是：當學習率（η）增加時，會降低學習時間；學習率越高，越難收斂，在這種條件下，應該降低學習率直到訓練過程收斂。通過誤差和梯度的變化以及根據誤差函數的學習速率的梯度來調整學習速率，此外，通過啟發式調整來進行總誤差的改變，規則如下：

（1）如果總誤差（E）降低且變化比τ△w_ij要大，則學習率就會增加；否則學習率不變。

（2）如果總誤差（E）增加且變化比τ△w_ij要大，則學習率就需要降低。即：

其中d是E（k+1）和E（k）差的絕對值，叩是學習率；k是訓練時間：E是公式（6）所示的誤差函數。

（2）數據預處理

所有的訓練數據重新調整到一個特定范圍的時間序列來預測問題。當利用取值為極端值時，傳遞函數的梯度將接近零，因此會使得訓練放慢.為了克服極端事件，一些研究表明將數據縮放轉換成小間隔[0.1，0.85]（或[0.1，0.9]）。本文運用實驗數據處理方法，能將所有的訓練集縮放到[0.1，0.9]的范圍內，如下：

其中x，是觀察到的值，xmin和xmax分別表示數據系列的最小和最大值。

綜上所述，改進的訓練算法描述如下：

步驟一：初始化方向傳播時變網絡層的全重w^m/_ij；

步驟二：使用訓練集去訓練馬氏反饋時變網絡。重復以下的步驟直到滿足規定誤差為止；

第一：計算每一層時變神經元的aik，bik和X。重復操作過程：在m層計算你每個時變神經元的δik。

第二：使用以下公式校正權重：

這里的η（k+l）是學習率，可由公式（12）計算得到，根據誤差函數和變化的趨勢，它可以動態的調整每一個k。

步驟三：（X_k，x_k-1，X_k-p+1）是馬氏反饋時變網絡的輸入，輸出是第k+l個流量差分的預測。

步驟四：樣本的描述向前移動一步，到第二步繼續預測。

3 實驗驗證

為了比較預測的誤差，在相同的情況下，分別運行了10次傳統MARKOV時變網絡和改進的MARKOV時變網絡，并假設在實驗中誤差為0.0001，得到10次預測值的平均值，傳統MARKOV算法的MES為0.0163，MAE為0.1973，SSE為0.3261，改進的MARKOV算法的MES為0.0038.MAE為0.0521，SSE為0.0762。其中，MSE是均方誤差，SSE是誤差平方和，MAE是絕對平均誤差，NMSE是歸一化均方誤差。實驗l使用傳統MARKOV時變網絡算法預測網絡流量，圖2是預測試驗曲線。實驗2使用改進的馬氏反饋時變網絡算法預測網絡流，圖3是預測試驗曲線。其中實線代表網絡流量的實際值，虛線代表的是預測值。

結果可看出，改進的MARKOV時變網絡算法在網絡流量預測中有更好的性能。其中，如果MSE和SSE更小，這表示它對網絡流量有更高的適應性；如果MAE變低了，這就意味著網絡模型的預測效果更好，最大相對誤差能代表預測方式的風險程度。表l的實驗結果表示該改進的MARKOV時變網絡算法具有最大MSE，意味著它具有比傳統的MARKOV時變網絡算法更加穩定可靠。從圖2和圖3測試結果能有效反映的兩種算法的趨勢，改進的MARKOV時變網絡算法的預測更準確。

4 結語

針對實際網絡中收集到的大量實際流量數據，提出了一種基于時變網絡的白適應網絡流量預測算法，采用白適應學習率法，根據總誤差增減變化趨勢以及不同的改變來調整適應率；然后根據正向和反向的計算來校正各層的權重。仿真結果表明，與傳統的時變網絡相比，基于傳播時變網絡的自適應流量預測算法在預測結果中具有更好的性能，并具有較小的誤差。endprint