歐陽與點，謝鯤

湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410006

引 言

網(wǎng)絡(luò)性能數(shù)據(jù)的監(jiān)測是網(wǎng)絡(luò)設(shè)計、運(yùn)維和管理的核心問題[1-2]。獲取全網(wǎng)端到端的性能數(shù)據(jù)對于有效地進(jìn)行異常檢測、排除網(wǎng)絡(luò)故障、確定故障位置至關(guān)重要。但是，由于以下兩種原因，當(dāng)前的網(wǎng)絡(luò)監(jiān)測系統(tǒng)存在數(shù)據(jù)不完整的問題：

節(jié)約測量成本。在實際的網(wǎng)絡(luò)監(jiān)測系統(tǒng)中，全網(wǎng)的監(jiān)測會帶來較高的測量成本。對于規(guī)模為的網(wǎng)絡(luò)，如果要測量全網(wǎng)端到端路徑的性能，需在每對網(wǎng)絡(luò)節(jié)點之間發(fā)送探測數(shù)據(jù)包，測量代價為O(n2)[3-5]。為了降低成本，稀疏網(wǎng)絡(luò)測量技術(shù)[6]利用網(wǎng)絡(luò)性能數(shù)據(jù)之間的時空相關(guān)性來實現(xiàn)基于樣本的測量，僅在一定的時間間隙內(nèi)隨機(jī)測量部分節(jié)點對之間的數(shù)據(jù)，其他路徑的數(shù)據(jù)則通過稀疏數(shù)據(jù)重構(gòu)來推測。

不可避免的傳輸丟失。在惡劣的通信和系統(tǒng)條件下，如網(wǎng)絡(luò)擁塞、節(jié)點的惡意行為、監(jiān)測設(shè)備故障，使用不可靠的傳輸協(xié)議傳輸性能信息會導(dǎo)致測量樣本數(shù)據(jù)進(jìn)一步丟失。

異常檢測[7]和故障恢復(fù)作為網(wǎng)絡(luò)狀態(tài)跟蹤和預(yù)測[8]的應(yīng)用，對數(shù)據(jù)缺失非常敏感。無論是由于未測量還是傳輸丟失導(dǎo)致的性能數(shù)據(jù)缺失，從部分性能數(shù)據(jù)精確恢復(fù)缺失數(shù)據(jù)非常重要且具有挑戰(zhàn)性。

從部分性能數(shù)據(jù)恢復(fù)完整數(shù)據(jù)的質(zhì)量，高度依賴于推測技術(shù)，現(xiàn)已存在大量研究。傳統(tǒng)的推測技術(shù)僅基于單空間信息[9-10]或單時間信息[11]設(shè)計，數(shù)據(jù)的恢復(fù)精度都很低。為了同時利用空間和時間信息，不少研究使用矩陣填充技術(shù)從低秩矩陣中恢復(fù)缺失的數(shù)據(jù)[6,12-16]。盡管這些方法在低數(shù)據(jù)缺失率下表現(xiàn)出了良好的效果，但是當(dāng)缺失率較大時，由于基于二維矩陣的數(shù)據(jù)分析在提取信息方面存在局限性，恢復(fù)精度會受到影響。

為了更好地恢復(fù)數(shù)據(jù)，最近有一小部分研究開始將網(wǎng)絡(luò)性能數(shù)據(jù)建模為更高維的數(shù)組——張量，并提出基于張量填充的算法以更精確地恢復(fù)缺失數(shù)據(jù)。張量是向量和矩陣的高階泛化。基于張量的多線性數(shù)據(jù)分析[17-18]表明，張量模型可以充分利用數(shù)據(jù)中的多線性結(jié)構(gòu)，提供更好的數(shù)據(jù)解讀和信息精度。

為了利用張量強(qiáng)大的數(shù)據(jù)表達(dá)和信息提取能力，本文將網(wǎng)絡(luò)性能數(shù)據(jù)建模為3 維張量，其表示K個時間間隙內(nèi)I個源節(jié)點到J個目的節(jié)點之間的性能數(shù)據(jù)，由于性能數(shù)據(jù)是部分觀測的，因此是存在缺失元素的稀疏張量。本文的目的是通過張量填充恢復(fù)缺失的性能數(shù)據(jù)。

為了建模網(wǎng)絡(luò)性能數(shù)據(jù)的交互，現(xiàn)有的張量填充算法通常將源節(jié)點、目的節(jié)點和時間間隙的特征域投影到一個共享的子空間中，然后使用子空間的潛在因子向量的內(nèi)積表示源節(jié)點和目的節(jié)點在特定時間間隙的關(guān)系。因此，它假設(shè)源節(jié)點、目的節(jié)點和時間間隙之間的關(guān)系是線性的。然而，實際的性能數(shù)據(jù)之間的關(guān)系更復(fù)雜[19]，不能被簡單的線性模型精確表達(dá)，導(dǎo)致數(shù)據(jù)恢復(fù)的精度不高。

深度學(xué)習(xí)作為捕獲復(fù)雜關(guān)系的有力工具，已經(jīng)在計算機(jī)視覺[20-21]、自然語言處理[22-23]和語音識別[24-25]領(lǐng)域取得了巨大的成就。自編碼器[25-26]利用神經(jīng)網(wǎng)絡(luò)去學(xué)習(xí)輸入數(shù)據(jù)的潛在表達(dá)（壓縮編碼），然后從壓縮的編碼重構(gòu)原始輸入。本文基于自編碼器設(shè)計了一個缺失數(shù)據(jù)恢復(fù)算法，將部分觀測到的性能數(shù)據(jù)輸入到自編碼器中，通過重構(gòu)輸出恢復(fù)的數(shù)據(jù)作為缺失元素的估計值。

為了克服現(xiàn)有張量填充算法的缺陷，我們通過充分利用自動編碼器的數(shù)據(jù)重構(gòu)能力來研究和設(shè)計高精度張量填充的潛力和算法。盡管深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network, DNN）在圖像領(lǐng)域上取得了良好的成績，但基于深度神經(jīng)網(wǎng)絡(luò)設(shè)計張量填充算法恢復(fù)缺失數(shù)據(jù)仍面臨一些挑戰(zhàn)：

由于網(wǎng)絡(luò)性能數(shù)據(jù)的低秩性，每個時間間隙的網(wǎng)絡(luò)測量矩陣存在復(fù)雜的非線性局部相關(guān)性和全局關(guān)聯(lián)。如何在保證恢復(fù)精度的同時，準(zhǔn)確地學(xué)習(xí)內(nèi)部關(guān)聯(lián)，且最小化模型的參數(shù)規(guī)模成為挑戰(zhàn)。

網(wǎng)絡(luò)性能數(shù)據(jù)存在缺失，只有部分觀測到的樣本元素，這給使用深度神經(jīng)網(wǎng)絡(luò)帶來了挑戰(zhàn)。由于DNN 中沒有標(biāo)準(zhǔn)的方法來處理稀疏的輸入數(shù)據(jù)，因此應(yīng)緩和缺失值對神經(jīng)網(wǎng)絡(luò)的影響。

鑒于上述挑戰(zhàn)，我們提出一個深度卷積自編碼器（Deep Convolution AutoEncoder, DCAE）的張量填充模型，它包含如下幾種技術(shù)：

用少量共享的參數(shù)，學(xué)習(xí)非線性局部和全局特征。與傳統(tǒng)的全連接網(wǎng)絡(luò)相比，DCAE 基于卷積以局部連接和參數(shù)共享的方式使用更少的參數(shù)。隨著網(wǎng)絡(luò)層次的加深，DCAE 可以利用CNN 以分層的方式學(xué)習(xí)從局部范圍到全局范圍的復(fù)雜關(guān)系。

設(shè)計良好的技術(shù)，減輕神經(jīng)網(wǎng)絡(luò)訓(xùn)練中缺失值的影響。我們使用經(jīng)驗損失函數(shù)，阻止缺失值為反向傳播過程提供錯誤信息。

我們在三個公開的真實網(wǎng)絡(luò)性能數(shù)據(jù)集上的實驗結(jié)果，證明了DCAE 的有效性。除了DCAE，我們還實現(xiàn)了其他4 種張量填充算法作為性能評估的基準(zhǔn)，并討論了DCAE 的收斂行為。

本文的其余部分組織如下：第1 節(jié)和第2 節(jié)分別介紹了相關(guān)工作和系統(tǒng)模型；第3 節(jié)介紹了DCAE 的詳細(xì)設(shè)計；第4 節(jié)中通過實驗評估了算法性能；第5節(jié)總結(jié)了本文的工作。

1 相關(guān)工作

稀疏網(wǎng)絡(luò)測量技術(shù)采用基于樣本的網(wǎng)絡(luò)測量，只隨機(jī)在一定時間間隙的部分節(jié)點對之間進(jìn)行測量，再利用網(wǎng)絡(luò)性能數(shù)據(jù)中的時空相關(guān)性，推斷其他路徑的數(shù)據(jù)。近期一些研究基于時間信息[9-10,27]或空間信息[11,28]恢復(fù)網(wǎng)絡(luò)性能數(shù)據(jù)，然而這類算法僅利用空間信息或時間信息，恢復(fù)精度較低。

為了能夠充分捕獲網(wǎng)絡(luò)性能數(shù)據(jù)中的時間與空間特征，SRMF[16]針對網(wǎng)絡(luò)流量矩陣提出了一種時空模型，利用流量矩陣的稀疏表征，結(jié)合流量矩陣進(jìn)行時間與空間約束（即相同時刻或相鄰地理位置之間的網(wǎng)絡(luò)測量數(shù)據(jù)相似）進(jìn)行數(shù)據(jù)推測。隨后，一些其他矩陣恢復(fù)算法被提出來進(jìn)行數(shù)據(jù)推測[6,12-15,29-30]。相較于基于向量的恢復(fù)方法，基于矩陣的算法通常能夠從性能數(shù)據(jù)中獲取更多的信息從而達(dá)到更好的恢復(fù)精度。然而，二維的矩陣模型仍然無法充分獲取網(wǎng)絡(luò)性能數(shù)據(jù)中高階結(jié)構(gòu)化信息，例如，SRMF[16]中定義的流量矩陣盡管能夠捕獲網(wǎng)絡(luò)數(shù)據(jù)在不同時刻的時間相關(guān)性以及源-目的對之間的空間相關(guān)性，卻無法捕獲網(wǎng)絡(luò)中各節(jié)點之間的空間相關(guān)性。因此，基于矩陣模型的數(shù)據(jù)恢復(fù)算法精度依然較低。

近期的研究表明，相比于矩陣填充，更高維度的張量填充算法可以捕捉更多維度的特征?；趶埩康臄?shù)據(jù)恢復(fù)算法通常可以充分捕獲數(shù)據(jù)內(nèi)部的高階結(jié)構(gòu)化信息，并用更少的采樣數(shù)目獲得更高的數(shù)據(jù)推測精度。目前，張量填充已經(jīng)應(yīng)用于很多領(lǐng)域中，如信號處理[31]、多分類學(xué)習(xí)[32]、圖像壓縮、數(shù)據(jù)挖掘與計算機(jī)視覺[18,33]等。

近年來，一些張量恢復(fù)算法[17-18,34-35]被提出用于數(shù)據(jù)恢復(fù)。文獻(xiàn)[36]提出將測量數(shù)據(jù)建模成三維張量，并設(shè)計了恢復(fù)算法。由于張量分解需要大量的計算，采用現(xiàn)有的張量分解算法進(jìn)行性能數(shù)據(jù)恢復(fù)非常困難。文獻(xiàn)[36]提出了一個連續(xù)的張量填充算法來快速解決這一問題。實際應(yīng)用中網(wǎng)絡(luò)數(shù)據(jù)的采樣速率會隨著網(wǎng)絡(luò)中的數(shù)據(jù)流量的變化而變化，當(dāng)采樣速率變化時，每一天的采樣數(shù)據(jù)矩陣大小都不一樣，無法形成規(guī)則的張量，因此，文獻(xiàn)[37]提出了一種面向動態(tài)網(wǎng)絡(luò)的張量填充方案以解決由于不同采樣速率形成的不規(guī)則的網(wǎng)絡(luò)數(shù)據(jù)張量模型。另外，實際的網(wǎng)絡(luò)流量數(shù)據(jù)中，局部數(shù)據(jù)間存在較強(qiáng)的相關(guān)性，利用這一性質(zhì)可以提高數(shù)據(jù)恢復(fù)的精度。文獻(xiàn)[38]提出局部子張量填充算法，利用子張量的低秩性來實現(xiàn)更加精確的數(shù)據(jù)恢復(fù)。

然而，上述算法都基于源節(jié)點、目的節(jié)點和時間間隙線性關(guān)系的假設(shè)，用潛在因子的內(nèi)積表示張量的元素值，無法表示具有復(fù)雜內(nèi)部結(jié)構(gòu)的實際網(wǎng)絡(luò)性能數(shù)據(jù)。

2 缺失數(shù)據(jù)恢復(fù)的張量填充模型

本節(jié)首先介紹缺失數(shù)據(jù)恢復(fù)的張量填充模型，然后介紹其局限性。如圖1所示，我們使用張量來表示由個網(wǎng)絡(luò)性能矩陣構(gòu)成的三維數(shù)組，其中表示第個時間間隙的性能矩陣。矩陣的大小是和分別對應(yīng)源節(jié)點和目的節(jié)點的數(shù)量。元素表示第個時隙內(nèi)從源節(jié)點到目的節(jié)點的網(wǎng)絡(luò)性能數(shù)據(jù)。

圖1 3 維網(wǎng)絡(luò)測量張量Fig.1 3-way network monitoring tensor

如圖2所示，通過張量分解進(jìn)行張量填充恢復(fù)缺失數(shù)據(jù)通常包含兩步：（1）使用觀測到的部分樣本基于CP 分解[39-40]訓(xùn)練潛在因子向量；（2）使用訓(xùn)練好的因子向量推測張量的缺失元素。

圖2 通過張量填充恢復(fù)缺失元素的兩個步驟Fig.2 Two steps to recover the missing data through tensor completion

3 DCAE 的詳細(xì)設(shè)計

為了解決現(xiàn)有算法恢復(fù)網(wǎng)絡(luò)性能數(shù)據(jù)的缺陷，本文提出一個深度卷積自編碼器（DCAE）的張量填充模型。自編碼器是由Kramer[26]提出的一種前饋神經(jīng)網(wǎng)絡(luò)，其以無監(jiān)督的方式重構(gòu)輸入數(shù)據(jù)并輸出。DCAE 的主要任務(wù)是給定部分觀測數(shù)據(jù)，學(xué)習(xí)其內(nèi)部的非線性復(fù)雜特征，估計缺失數(shù)據(jù)。

3.1 基于自編碼器估計缺失數(shù)據(jù)

圖3展示了基于自編碼器估計缺失數(shù)據(jù)的基本思路。為了恢復(fù)不完整的性能張量，我們將每個時間間隙內(nèi)部分觀測的數(shù)據(jù)矩陣輸入自編碼器，然后輸出已估計出缺失元素的矩陣。該框架包括兩個部分，編碼器和解碼器。編碼器將部分觀測的性能矩陣作為輸入，并通過一系列隱藏的神經(jīng)網(wǎng)絡(luò)層將其轉(zhuǎn)換為潛在表達(dá)。在解碼器端，通過另一組隱藏層，從中生成的密集重構(gòu)，來預(yù)測缺失的數(shù)據(jù)元素。

圖3 基于自編碼器估計缺失數(shù)據(jù)Fig.3 Estimating the missing data based on autoencoder

我們使用觀測樣本的均方誤差(Mean Squared Error, MSE)表示填充問題的誤差函數(shù)：

3.2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

卷積自編碼器將自編碼器中的全連接層更改為卷積層，擴(kuò)展了傳統(tǒng)簡單自編碼器的基本結(jié)構(gòu)。由于以下兩個目的，本文設(shè)計基于卷積自編碼器的數(shù)據(jù)缺失恢復(fù)算法：

為了更好地利用網(wǎng)絡(luò)性能矩陣中隱藏的相關(guān)性，更準(zhǔn)確地恢復(fù)缺失數(shù)據(jù)。卷積神經(jīng)網(wǎng)絡(luò)使用過濾器，因此，卷積操作可以處理多維數(shù)據(jù)且保留數(shù)據(jù)的局部特征。如果我們使用傳統(tǒng)全連接網(wǎng)絡(luò)，則應(yīng)首先將性能矩陣向量化，這會損失矩陣中的隱藏相關(guān)性。

為了構(gòu)建更深的卷積自動編碼器。卷積自編碼器以局部連接和參數(shù)共享的方式、多層神經(jīng)網(wǎng)絡(luò)堆疊的形式組成，與傳統(tǒng)的自動編碼器相比，它使用的參數(shù)要少得多。傳統(tǒng)的全連接自編碼器需要較大的存儲空間和更多的訓(xùn)練數(shù)據(jù)。因此，我們可以使用卷積自編碼器構(gòu)建更深的神經(jīng)網(wǎng)絡(luò)模型。

圖4 網(wǎng)絡(luò)結(jié)構(gòu)Fig.4 Network architecture

為更好地利用性能數(shù)據(jù)中的非線性復(fù)雜特征以更準(zhǔn)確地恢復(fù)缺失數(shù)據(jù)，我們使用卷積和反卷積過濾器設(shè)計了對稱的卷積自編碼器，即編碼過程與解碼過程對稱，如圖4所示。編碼器端對輸入矩陣進(jìn)行下采樣（即減小輸入的大?。獯a器端對矩陣進(jìn)行上采樣（即增大矩陣的大?。榱藢崿F(xiàn)編碼器的下采樣，DCAE 采用了帶步長的卷積。對于解碼器，采用帶步長的反卷積，這是卷積運(yùn)算的逆過程。卷積過濾器和反卷積過濾器通過特征映射進(jìn)行2D 卷積運(yùn)算逐層提取特征。由于一個卷積過濾器只能從輸入矩陣中提取一種類型的特征，因此，DCAE 中采用了多個卷積過濾器來提取更多類型的特征。連續(xù)的下采樣/上采樣操作會降低重構(gòu)矩陣的質(zhì)量。因此，我們提出了由一對步長分別為1 和2 的卷積/反卷積過濾器組成的下采樣/上采樣單元。我們使用ReLU[41]和Sigmoid 作為非線性激活函數(shù)。另外，為了構(gòu)建更深的神經(jīng)網(wǎng)絡(luò)，除了輸出層以外，每一層都使用層歸一化（Layer normalization[42]）幫助模型收斂。

4 實驗評估

本節(jié)評估所提模型DCAE 的性能，并對其收斂性進(jìn)行了描述。

4.1 實驗環(huán)境設(shè)置

數(shù)據(jù)描述。評估使用三個真實的網(wǎng)絡(luò)性能數(shù)據(jù)集Abilene[43]、GèANT[44]和WS-DREAM[45]。Abilene由12 個網(wǎng)絡(luò)節(jié)點組成，記錄了168 天內(nèi)每5 分鐘測量一次的流量，原始數(shù)據(jù)的觀測率為100%。GèANT 由23 個網(wǎng)絡(luò)節(jié)點組成，記錄了112 天內(nèi)每15 分鐘測量一次的流量，原始數(shù)據(jù)的觀測率為88%。WS-DREAM 記錄142 個用戶和4500 個網(wǎng)絡(luò)服務(wù)之間15 分鐘一次共64 個時間間隙的流量，原始數(shù)據(jù)的觀測率為63%。

性能指標(biāo)。如表1所示，3 種評價指標(biāo)誤差率(Error Ratio, ER)、平均絕對誤差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Square Error,RMSE)用于評估DCAE。和分別表示性能數(shù)據(jù)張量的第個元素的原始值和恢復(fù)值，其中1 ≤i≤I，1 ≤j≤J，1 ≤k≤K。表示缺失元素的索引集合，所有算法都在缺失值上評估效果。

表1 性能指標(biāo)Table 1 Performance metric

比較基準(zhǔn)。除了DCAE，我們還實現(xiàn)了其他4種張量填充算法CPals[46]，CPnmu[47]，CPopt[35]和TKals[46]用于比較，其中前三個算法基于CP 分解模型，最后一個算法基于Tucker 分解模型。

參數(shù)配置。DCAE 由5 個卷積層和5 個反卷積層組成，卷積核大小為5×5，每層的卷積核數(shù)目分別 為[32,64,128,256,512,256,128,64,32,1]。DCAE 使用TensorFlow 的優(yōu)化器Adam 進(jìn)行小批量梯度下降更新，三個數(shù)據(jù)集Abilene、GèANT 和WS-DREAM的學(xué)習(xí)率分別是10-3，10-2和10-3。

所有的張量填充算法都是迭代執(zhí)行的，以訓(xùn)練所需的參數(shù)。為了公平比較，我們采用兩個相同的迭代停止條件：(1)連續(xù)兩次迭代之間的損失函數(shù)差值小于給定的閾值10-6；(2)達(dá)到最大迭代次數(shù)500。實驗表明該設(shè)置可以保證各算法收斂到預(yù)期狀態(tài)，見4.3，對于比較的傳統(tǒng)算法這里不再贅述。為了獲得更可靠的評估結(jié)果，我們重復(fù)每組實驗20 次，并展示平均結(jié)果。

4.2 恢復(fù)性能比較

圖5 DCAE 與線性張量填充算法比較Fig.5 Compare our DCAE with linear tensor completion algorithms

圖5顯示了5 種張量填充算法的對比實驗結(jié)果。實驗過程中，我們對每個數(shù)據(jù)集的現(xiàn)有數(shù)據(jù)進(jìn)行10%-50%的隨機(jī)采樣，模擬數(shù)據(jù)缺失。意料之中，所有算法都隨著采樣率的增大達(dá)到更好的恢復(fù)效果。DCAE 的ER，MAE 和RMSE 明顯更小，勝過所有其他傳統(tǒng)的張量填充算法。即使當(dāng)采樣率非常低（10%）時，DCAE 的ER 約為0.3(Abilene)，而其他傳統(tǒng)的張量填充算法的ER 為0.99(Abilene)，是DCAE 誤差的3 倍。這些結(jié)果表明，DCAE 在提取測量數(shù)據(jù)中隱藏的復(fù)雜關(guān)系方面非常有效，可以顯著提高恢復(fù)性能。

4.3 DCAE 的收斂性說明

本文使用損失函數(shù)的值評估所提算法的收斂行為，圖6顯示了DCAE 的收斂曲線。為了更清楚地觀察DCAE 的收斂行為，因此該實驗中將采樣率固定為30%，且不設(shè)置迭代停止條件。顯然，對于3 個不同的數(shù)據(jù)集，DCAE 的損失值都隨著迭代輪數(shù)的增加而逐漸趨近于0 且穩(wěn)定。注意到損失函數(shù)在收斂過程中有小幅抖動，這是小批梯度下降訓(xùn)練神經(jīng)網(wǎng)絡(luò)特性所致，最終網(wǎng)絡(luò)的權(quán)值會收斂到局部最優(yōu)，且在附近震蕩。另外，三個數(shù)據(jù)集Abilene、GèANT 和WS-DREAM 分別在第491 輪、第478 輪和第382 輪達(dá)到迭代停止條件，充分說明了迭代停止條件的合理性。

圖6 DCAE 的收斂曲線Fig.6 Convergence curve of DCAE

5 總結(jié)與展望

本文提出了一種新的張量填充算法DCAE，可以為高層網(wǎng)絡(luò)應(yīng)用恢復(fù)缺失的測量數(shù)據(jù)。它可以捕獲測量數(shù)據(jù)之間的非線性關(guān)系，具有高數(shù)據(jù)恢復(fù)精度，優(yōu)于當(dāng)前數(shù)據(jù)恢復(fù)算法。據(jù)我們所知，這是利用卷積自編碼器解決張量形式的測量數(shù)據(jù)恢復(fù)問題的第一項工作。我們期望DCAE 強(qiáng)大的學(xué)習(xí)能力和張量表示高維數(shù)據(jù)隱藏結(jié)構(gòu)的能力為高性能數(shù)據(jù)恢復(fù)和分析開辟新的途徑。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。