基于馬爾可夫時(shí)變模型的流量數(shù)據(jù)挖掘

葉德忠+巫忠正+蔣勇

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

引言

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

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

1 MARKOV時(shí)變網(wǎng)絡(luò)模型

MARKOV時(shí)變網(wǎng)絡(luò)模型是一個(gè)全連接的時(shí)變網(wǎng)絡(luò)，包括輸入層，隱層和輸出層。訓(xùn)練過程的目的是找到最小化一些總體誤差測量的權(quán)重、平方誤差（SSE）或均方誤差（MSE）。網(wǎng)絡(luò)訓(xùn)練實(shí)際上是一個(gè)無約束非線性最小化問題。

對于網(wǎng)絡(luò)流量的預(yù)測，網(wǎng)絡(luò)流量的序列號與多步相關(guān)聯(lián)，即當(dāng)前采樣流和過去采樣周期之間存在一定的關(guān)系。設(shè)x_k（k=l，2...N）表示第k個(gè)采樣間隔的p個(gè)流（p≥1）的預(yù)測模型，則步驟k+l（1≥1）定義為：

即，f是第k+1個(gè)采樣間隔的第k+1個(gè)流和其之前的p個(gè)流之間的關(guān)系，f是非線性函數(shù)。

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

為了測試預(yù)測性能，本文使用一些指標(biāo)等來測試預(yù)測性能，包括平均絕對誤差（MAE），均方誤差（MSE），誤差平方和（SSE），標(biāo)準(zhǔn)均方誤差（NMSE）。

2 分離預(yù)測

本文采用白適應(yīng)學(xué)習(xí)率法和改進(jìn)的訓(xùn)練算法對各層進(jìn)行分離預(yù)測。自適應(yīng)學(xué)習(xí)率法的基本原則是：當(dāng)學(xué)習(xí)率（η）增加時(shí)，會(huì)降低學(xué)習(xí)時(shí)間；學(xué)習(xí)率越高，越難收斂，在這種條件下，應(yīng)該降低學(xué)習(xí)率直到訓(xùn)練過程收斂。通過誤差和梯度的變化以及根據(jù)誤差函數(shù)的學(xué)習(xí)速率的梯度來調(diào)整學(xué)習(xí)速率，此外，通過啟發(fā)式調(diào)整來進(jìn)行總誤差的改變，規(guī)則如下：

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

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

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

（2）數(shù)據(jù)預(yù)處理

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

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

綜上所述，改進(jìn)的訓(xùn)練算法描述如下：

步驟一：初始化方向傳播時(shí)變網(wǎng)絡(luò)層的全重w^m/_ij；

步驟二：使用訓(xùn)練集去訓(xùn)練馬氏反饋時(shí)變網(wǎng)絡(luò)。重復(fù)以下的步驟直到滿足規(guī)定誤差為止；

第一：計(jì)算每一層時(shí)變神經(jīng)元的aik，bik和X。重復(fù)操作過程：在m層計(jì)算你每個(gè)時(shí)變神經(jīng)元的δik。

第二：使用以下公式校正權(quán)重：

這里的η（k+l）是學(xué)習(xí)率，可由公式（12）計(jì)算得到，根據(jù)誤差函數(shù)和變化的趨勢，它可以動(dòng)態(tài)的調(diào)整每一個(gè)k。

步驟三：（X_k，x_k-1，X_k-p+1）是馬氏反饋時(shí)變網(wǎng)絡(luò)的輸入，輸出是第k+l個(gè)流量差分的預(yù)測。

步驟四：樣本的描述向前移動(dòng)一步，到第二步繼續(xù)預(yù)測。

3 實(shí)驗(yàn)驗(yàn)證

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

結(jié)果可看出，改進(jìn)的MARKOV時(shí)變網(wǎng)絡(luò)算法在網(wǎng)絡(luò)流量預(yù)測中有更好的性能。其中，如果MSE和SSE更小，這表示它對網(wǎng)絡(luò)流量有更高的適應(yīng)性；如果MAE變低了，這就意味著網(wǎng)絡(luò)模型的預(yù)測效果更好，最大相對誤差能代表預(yù)測方式的風(fēng)險(xiǎn)程度。表l的實(shí)驗(yàn)結(jié)果表示該改進(jìn)的MARKOV時(shí)變網(wǎng)絡(luò)算法具有最大MSE，意味著它具有比傳統(tǒng)的MARKOV時(shí)變網(wǎng)絡(luò)算法更加穩(wěn)定可靠。從圖2和圖3測試結(jié)果能有效反映的兩種算法的趨勢，改進(jìn)的MARKOV時(shí)變網(wǎng)絡(luò)算法的預(yù)測更準(zhǔn)確。

4 結(jié)語

針對實(shí)際網(wǎng)絡(luò)中收集到的大量實(shí)際流量數(shù)據(jù)，提出了一種基于時(shí)變網(wǎng)絡(luò)的白適應(yīng)網(wǎng)絡(luò)流量預(yù)測算法，采用白適應(yīng)學(xué)習(xí)率法，根據(jù)總誤差增減變化趨勢以及不同的改變來調(diào)整適應(yīng)率；然后根據(jù)正向和反向的計(jì)算來校正各層的權(quán)重。仿真結(jié)果表明，與傳統(tǒng)的時(shí)變網(wǎng)絡(luò)相比，基于傳播時(shí)變網(wǎng)絡(luò)的自適應(yīng)流量預(yù)測算法在預(yù)測結(jié)果中具有更好的性能，并具有較小的誤差。endprint