面向大規(guī)模網(wǎng)絡(luò)測量的數(shù)據(jù)恢復(fù)算法：基于關(guān)聯(lián)學(xué)習(xí)的張量填充

歐陽與點(diǎn)，謝 鯤，謝高崗，文吉?jiǎng)偅?

（1.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙 410006；2.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100089；3.中國科學(xué)院大學(xué)，北京 100089；4.湖南友道信息技術(shù)有限公司，湖南長沙 410006）

1 引言

網(wǎng)絡(luò)吞吐量記錄了端到端網(wǎng)絡(luò)成功傳輸數(shù)據(jù)的速率，是衡量網(wǎng)絡(luò)性能的重要指標(biāo).獲取全網(wǎng)端到端吞吐量對于了解網(wǎng)絡(luò)狀態(tài)、跟蹤服務(wù)等級協(xié)議和定位網(wǎng)絡(luò)故障等應(yīng)用［1～3］至關(guān)重要.然而，由于測量代價(jià)大，現(xiàn)有的網(wǎng)絡(luò)監(jiān)控系統(tǒng)難以獲得完整準(zhǔn)確的全網(wǎng)吞吐量測量值.本文中吞吐量定義為單位時(shí)間內(nèi)端到端網(wǎng)絡(luò)源節(jié)點(diǎn)成功向目的節(jié)點(diǎn)傳輸?shù)膶?shí)際數(shù)據(jù)量，不包括包頭，并且重傳的數(shù)據(jù)包只計(jì)算一次［4］.測量網(wǎng)絡(luò)吞吐量通常需要從源端向目的端傳輸一個(gè)大的文件，并測量完成文件傳輸所需要的時(shí)間，再將文件大小除以傳輸時(shí)間來計(jì)算吞吐量［5］.這種方法會產(chǎn)生大量測試流量，影響網(wǎng)絡(luò)性能.一些數(shù)據(jù)包流級別的直接測量技術(shù)［6，7］通過跟蹤經(jīng)過設(shè)備的數(shù)據(jù)包將具有相同源-目的地址的數(shù)據(jù)包匯聚成一個(gè)流作為該源-目的地址之間的流量即吞吐量，這種方法可以做到準(zhǔn)確測量，不會被背景流量干擾.但是由于缺乏支持設(shè)備以及測量開銷等原因，直接測量只能夠測量部分源-目的地址之間的吞吐量［8］.盡管現(xiàn)在已經(jīng)有成熟的網(wǎng)絡(luò)監(jiān)控系統(tǒng)可以實(shí)時(shí)測量網(wǎng)絡(luò)時(shí)延，比如微軟Pingmesh［9］通過發(fā)送探測數(shù)據(jù)包能夠測量大規(guī)模數(shù)據(jù)中心網(wǎng)絡(luò)中任意兩個(gè)服務(wù)器之間任何時(shí)刻的時(shí)延，獲取每對節(jié)點(diǎn)之間任意時(shí)刻的吞吐量測量值仍然很困難.

近年來，有研究表明端到端網(wǎng)絡(luò)性能數(shù)據(jù)具有隱藏的時(shí)空相關(guān)性［10］，提出了稀疏網(wǎng)絡(luò)測量技術(shù).稀疏網(wǎng)絡(luò)測量技術(shù)基于采樣的方式降低測量代價(jià)，僅測量部分路徑和時(shí)隙的數(shù)據(jù)，推測全部數(shù)據(jù)，將網(wǎng)絡(luò)測量問題轉(zhuǎn)換成從部分測量值估計(jì)全部測量值的數(shù)據(jù)恢復(fù)問題.目前主要有3 種典型的稀疏重構(gòu)技術(shù)：壓縮傳感、矩陣填充和張量填充.作為一維向量和二維矩陣的高階推廣，張量模型可以充分利用多線性結(jié)構(gòu)，挖掘高維數(shù)據(jù)之間隱藏的內(nèi)在聯(lián)系，達(dá)到更好的數(shù)據(jù)恢復(fù)精度.盡管前景光明，現(xiàn)有的張量填充算法針對網(wǎng)絡(luò)性能數(shù)據(jù)恢復(fù)的研究現(xiàn)狀仍然具有很大局限性，具體表現(xiàn)在其算法只考慮了單個(gè)網(wǎng)絡(luò)性能指標(biāo)的數(shù)據(jù)恢復(fù)，忽略了多個(gè)網(wǎng)絡(luò)測量指標(biāo)的關(guān)聯(lián)信息.

實(shí)際的網(wǎng)絡(luò)監(jiān)控系統(tǒng)通常會涉及多個(gè)網(wǎng)絡(luò)性能指標(biāo)的測量，包括吞吐量、往返時(shí)延、丟包率等.有些指標(biāo)的測量開銷比較小，如測量往返時(shí)延只需要在源端記錄探測數(shù)據(jù)包發(fā)送和到達(dá)的時(shí)刻，并計(jì)算時(shí)間戳之間的差值即可.現(xiàn)有的稀疏測量技術(shù)沒有考慮多指標(biāo)測量的應(yīng)用場景，為了保證數(shù)據(jù)恢復(fù)的準(zhǔn)確性仍然需要一定比例的吞吐量測量值，為網(wǎng)絡(luò)帶來較大的負(fù)擔(dān).由于網(wǎng)絡(luò)中存在低測量開銷的指標(biāo)，同時(shí)考慮多個(gè)指標(biāo)間的關(guān)系和測量代價(jià)，利用低開銷的指標(biāo)推測高開銷的指標(biāo)能夠減少高開銷指標(biāo)的測量數(shù)量，進(jìn)一步降低網(wǎng)絡(luò)測量代價(jià).此外，稀疏測量技術(shù)對單個(gè)指標(biāo)在進(jìn)行數(shù)據(jù)恢復(fù)時(shí)忽略了其他測量指標(biāo)帶來的附加信息，考慮到不同的指標(biāo)之間具有相關(guān)性，在利用時(shí)空相關(guān)性進(jìn)行稀疏重構(gòu)的同時(shí)加入其他測量指標(biāo)的外部輔助信息可以提高恢復(fù)精度.

基于上述思路，本文提出了一個(gè)面向大規(guī)模網(wǎng)絡(luò)測量的數(shù)據(jù)恢復(fù)算法——基于關(guān)聯(lián)學(xué)習(xí)的張量填充（Association Learning based Tensor Completion，ALTC）.在多指標(biāo)聯(lián)合測量背景下，構(gòu)建從低測量開銷指標(biāo)到高測量開銷指標(biāo)的關(guān)聯(lián)模型，在高開銷指標(biāo)吞吐量數(shù)據(jù)極少的情況下，盡可能測量低開銷指標(biāo)往返時(shí)延，借助關(guān)聯(lián)模型從往返時(shí)延推測吞吐量，降低網(wǎng)絡(luò)測量代價(jià).在傳統(tǒng)張量填充的框架中加入多指標(biāo)關(guān)聯(lián)信息，同時(shí)挖掘吞吐量內(nèi)部的時(shí)空相關(guān)性和外部關(guān)聯(lián)模型的輔助信息，進(jìn)一步提高數(shù)據(jù)恢復(fù)精度.本文主要貢獻(xiàn)總結(jié)如下：

（1）對真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，分析了吞吐量與往返時(shí)延之間的關(guān)聯(lián)，發(fā)現(xiàn)它們之間相關(guān)性強(qiáng)，但是關(guān)系復(fù)雜，難以用普通線性函數(shù)建模.針對該挑戰(zhàn)，設(shè)計(jì)了一個(gè)基于神經(jīng)網(wǎng)絡(luò)的吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型，捕獲兩個(gè)指標(biāo)之間的關(guān)聯(lián)，使用低開銷的往返時(shí)延推測高開銷的吞吐量，降低網(wǎng)絡(luò)測量代價(jià).

（2）由于吞吐量測量數(shù)據(jù)的內(nèi)部也具有潛在的時(shí)空相關(guān)性，可以通過張量填充算法從部分測量推測全部數(shù)據(jù).為了同時(shí)利用內(nèi)部時(shí)空相關(guān)性和其他指標(biāo)的外部輔助信息，使用關(guān)聯(lián)學(xué)習(xí)模型的推測值對吞吐量的測量值進(jìn)行預(yù)填充，并設(shè)計(jì)一個(gè)新的張量填充模型，同時(shí)擬合吞吐量的測量值和關(guān)聯(lián)模型的推測值，設(shè)置關(guān)鍵參數(shù)誤差平衡權(quán)重控制模型對測量值和對推測值的擬合程度，提高數(shù)據(jù)恢復(fù)精度.

（3）真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果展示了所提算法ALTC 在同樣的吞吐量測量代價(jià)下可以顯著提高數(shù)據(jù)恢復(fù)的精度.在采樣率為2%的極低情況下，ALTC的恢復(fù)誤差在傳統(tǒng)線性張量填充算法的結(jié)果上改善了1.5倍，比目前主流的神經(jīng)網(wǎng)絡(luò)張量填充算法的誤差降低了13%.

2 相關(guān)工作

從網(wǎng)絡(luò)性能數(shù)據(jù)的部分測量值恢復(fù)未測量的缺失數(shù)據(jù)依賴于稀疏網(wǎng)絡(luò)測量技術(shù).最開始的壓縮傳感技術(shù)使用單純的空間或時(shí)間信息重構(gòu)缺失數(shù)據(jù)［11，12］.由于壓縮傳感主要作用于一維向量數(shù)據(jù)，應(yīng)用范圍受限，發(fā)展了矩陣填充技術(shù)使用簡單的時(shí)空信息從低秩矩陣中恢復(fù)缺失數(shù)據(jù)［13，14］.然而，二維矩陣的形式在捕獲數(shù)據(jù)潛在相關(guān)性上的作用仍然很有限，當(dāng)數(shù)據(jù)缺失率較高時(shí)，恢復(fù)性能會受很大影響.為了克服基于矩陣方法的不足，一些新的研究基于張量填充技術(shù)，利用張量的多線性結(jié)構(gòu)捕獲網(wǎng)絡(luò)測量數(shù)據(jù)更豐富的時(shí)空信息達(dá)到更精確的恢復(fù)效果［15～19］.張量填充算法依賴于張量分解，使用最廣泛的張量分解模型有CANDECOMP/PARAFAC（CP）分解［20，21］和Tucker 分解［22］，其他模型都是對這兩個(gè)模型的改進(jìn).

近年來有大量基于張量填充的網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)研究.Xie等人［15］尋找數(shù)據(jù)的更強(qiáng)局部相關(guān)性來形成和填充更低秩的子張量，恢復(fù)網(wǎng)絡(luò)流量數(shù)據(jù).Deng 等人［16］提出了一種基于杠桿分?jǐn)?shù)采樣的自適應(yīng)張量填充方案估計(jì)個(gè)人設(shè)備網(wǎng)絡(luò)的延遲數(shù)據(jù).Wang 等人［17］考慮網(wǎng)絡(luò)數(shù)據(jù)中的噪聲和異常，將L2，1范數(shù)和LF范數(shù)引入張量填充模型中，估計(jì)網(wǎng)絡(luò)流量.Xie 等人［18］基于Expectile 回歸對張量填充不同數(shù)據(jù)點(diǎn)的擬合誤差設(shè)置兩種不同的權(quán)重，提高大象流的恢復(fù)精度.除了這些基于CP 分解或者Tucker分解的線性張量填充模型，Xie 等人［19］使用神經(jīng)網(wǎng)絡(luò)模型擴(kuò)展傳統(tǒng)張量填充算法的交互函數(shù)恢復(fù)網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)，取得了很好的恢復(fù)精度.

然而，上述所有的模型或算法全都僅考慮單個(gè)網(wǎng)絡(luò)性能指標(biāo)，忽略了多個(gè)網(wǎng)絡(luò)性能指標(biāo)之間的關(guān)聯(lián)，不僅數(shù)據(jù)恢復(fù)的精度受限，測量代價(jià)仍然很高.不同于現(xiàn)有研究，本文認(rèn)為同時(shí)考慮多個(gè)網(wǎng)絡(luò)性能指標(biāo)的測量指標(biāo)，多測量低開銷指標(biāo)、少測量高開銷指標(biāo)，挖掘指標(biāo)之間的關(guān)聯(lián)，利用低開銷的指標(biāo)輔助高開銷的指標(biāo)進(jìn)行填充，同時(shí)使用數(shù)據(jù)內(nèi)部的時(shí)空信息和指標(biāo)外部的輔助信息，可以降低測量代價(jià)并提高數(shù)據(jù)恢復(fù)的精度.

3 問題建模和整體框架

3.1 問題建模

張量是高維數(shù)組，數(shù)組的維數(shù)又稱為張量的?；蛘唠A.如圖1所示，本文將網(wǎng)絡(luò)測量數(shù)據(jù)建模成I×J×K的三維張量，其中I，J和K分別表示網(wǎng)絡(luò)中源節(jié)點(diǎn)的個(gè)數(shù)、目的節(jié)點(diǎn)的個(gè)數(shù)和測量的時(shí)間總數(shù).令X 表示吞吐量張量，其元素xijk記錄了源節(jié)點(diǎn)i與目的節(jié)點(diǎn)j之間在時(shí)間k的吞吐量測量值；令Y 表示往返時(shí)延張量，其元素yijk表示源節(jié)點(diǎn)i與目的節(jié)點(diǎn)j之間在時(shí)間k的往返時(shí)延測量值.如果源節(jié)點(diǎn)i與目的節(jié)點(diǎn)j之間在時(shí)間k沒有吞吐量或往返時(shí)延測量數(shù)據(jù)，則X 或Y 中對應(yīng)的元素為空.

圖1 網(wǎng)絡(luò)測量數(shù)據(jù)的三維張量模型

由于吞吐量的測量代價(jià)大，X 通常是帶缺失值的稀疏測量張量.令Ω表示張量X 的測量樣本索引集合，表示缺失樣本索引集合.如果xijk已測量，則(i，j，k)∈Ω，反之(i，j，k)∈由于往返時(shí)延的測量方式簡單，Y 為具有大量測量值的稠密測量張量.本文給出網(wǎng)絡(luò)測量數(shù)據(jù)恢復(fù)問題如圖2 所示，給定稀疏測量的吞吐量張量X在Ω上的少量測量值，與稠密測量的往返時(shí)延張量Y，建立吞吐量張量X 與往返時(shí)延張量Y 之間的關(guān)聯(lián)，利用吞吐量的部分測量值和往返時(shí)延的關(guān)聯(lián)估計(jì)X 的缺失值，恢復(fù)整個(gè)吞吐量張量.

圖2 網(wǎng)絡(luò)測量數(shù)據(jù)恢復(fù)問題

3.2 整體框架

為了充分利用多個(gè)網(wǎng)絡(luò)性能指標(biāo)之間的關(guān)聯(lián)達(dá)到更高的吞吐量數(shù)據(jù)恢復(fù)精度和更低的測量代價(jià)，本文提出了一個(gè)面向大規(guī)模網(wǎng)絡(luò)測量的數(shù)據(jù)恢復(fù)算法，即基于關(guān)聯(lián)學(xué)習(xí)的張量填充（ALTC）.整體框架如圖3 所示，首先研究了真實(shí)數(shù)據(jù)集中吞吐量與往返時(shí)延之間的關(guān)聯(lián)，設(shè)計(jì)了一個(gè)使用往返時(shí)延推測吞吐量的神經(jīng)網(wǎng)絡(luò)關(guān)聯(lián)學(xué)習(xí)模型（Y →X′），然后使用關(guān)聯(lián)學(xué)習(xí)模型的輸出對部分測量的吞吐量進(jìn)行預(yù)填充（X，X′→），并在傳統(tǒng)張量填充的架構(gòu)上設(shè)計(jì)了一個(gè)組合的加權(quán)損失函數(shù)，同時(shí)利用預(yù)填充張量中往返時(shí)延的外部輔助信息和吞吐量測量數(shù)據(jù)的內(nèi)部時(shí)空相關(guān)性更精確地重構(gòu)完整的吞吐量張量

圖3 基于關(guān)聯(lián)學(xué)習(xí)的張量填充算法的整體框架

4 基于關(guān)聯(lián)學(xué)習(xí)的張量填充算法

4.1 吞吐量與往返時(shí)延的關(guān)聯(lián)

為了研究吞吐量與往返時(shí)間之間的關(guān)聯(lián)模型，本文首先對真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，分析吞吐量與往返時(shí)延之間的關(guān)聯(lián).WS-DREAM［23］數(shù)據(jù)集記錄了142個(gè)用戶在64個(gè)連續(xù)時(shí)間片（以15分鐘為間隔）上的4 500 個(gè)Web 服務(wù)的服務(wù)質(zhì)量測量結(jié)果，包括了吞吐量和往返時(shí)延.隨機(jī)選取了數(shù)據(jù)集中的若干個(gè)源目的（即用戶-服務(wù)）節(jié)點(diǎn)對，并繪制了其中4 組源目的節(jié)點(diǎn)對沿著64個(gè)時(shí)間片的測量值大小.如圖4所示，橫坐標(biāo)為時(shí)間片的索引，縱坐標(biāo)為測量值的大小，0 軸的上方為吞吐量大小，0 軸的下方為往返時(shí)延大小.圖片顯示當(dāng)吞吐量持平時(shí)，往返時(shí)延也相對穩(wěn)定；當(dāng)吞吐量較大時(shí)，往返時(shí)延相對較??；當(dāng)吞吐量較小時(shí)，往返時(shí)延相對較大.尤其當(dāng)吞吐量極小時(shí)，往返時(shí)延很大，可能是由于發(fā)生了擁塞.

圖4 吞吐量-往返時(shí)延關(guān)聯(lián)

由此可知，同一網(wǎng)絡(luò)結(jié)構(gòu)下的吞吐量與往返時(shí)延之間存在強(qiáng)相關(guān)性，而且大體上成負(fù)相關(guān).然而，由于在實(shí)際網(wǎng)絡(luò)中不同的用戶或服務(wù)具有不同的屬性特征，難以使用簡單的線性模型直接建模復(fù)雜的吞吐量和往返時(shí)延關(guān)系.這種復(fù)雜關(guān)系直觀地表現(xiàn)在節(jié)點(diǎn)行為復(fù)雜，如兩個(gè)具有相同大小的吞吐量源目的節(jié)點(diǎn)對的往返時(shí)延不一定相同.

4.2 吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型

學(xué)習(xí)吞吐量與往返時(shí)延之間的復(fù)雜關(guān)系、從往返時(shí)延推測吞吐量的任務(wù)，直覺上類似于自然語言處理中的機(jī)器翻譯，可以看作是序列到序列的問題，應(yīng)用編碼-解碼（Encoder-Decoder）模型求解，即輸入往返時(shí)延序列，輸出對應(yīng)的吞吐量序列.然而由于數(shù)據(jù)是部分缺失的，無論是提取吞吐量張量的切片矩陣還是纖維向量，都無法形成完整的吞吐量序列，使得編碼-解碼模型難以訓(xùn)練，推測精度不高.

根據(jù)3.2 節(jié)的分析，給定源節(jié)點(diǎn)i、目的節(jié)點(diǎn)j和時(shí)間k，在往返時(shí)延張量中與吞吐量xijk的值最相關(guān)的是對應(yīng)位置上的yijk.然而，僅通過點(diǎn)對點(diǎn)的關(guān)系建模吞吐量與往返時(shí)延之間的復(fù)雜關(guān)聯(lián)存在2 個(gè)局限性：（1）無法利用上下文信息，具體包括同一個(gè)源-目的節(jié)點(diǎn)對的測量值在不同時(shí)刻的變化以及同一時(shí)刻下不同源節(jié)點(diǎn)或目的節(jié)點(diǎn)類型對測量值的影響；（2）對異常和噪聲敏感，當(dāng)網(wǎng)絡(luò)發(fā)生異常時(shí)會導(dǎo)致時(shí)延發(fā)生抖動，進(jìn)一步導(dǎo)致對應(yīng)吞吐量的預(yù)測值誤差大.

在張量建模下，對于往返時(shí)延張量Y任意一個(gè)點(diǎn)yijk，分別保留下標(biāo)i，j和k可變，而其他下標(biāo)固定，可以提取3個(gè)纖維向量y：jk∈RI×1、yi：k∈RJ×1和yij：∈RK×1［24］.這3 個(gè)向量在張量Y中的交匯點(diǎn)為yijk，且分別對應(yīng)了3 個(gè)坐標(biāo)軸的上下文信息，其中y：jk表示不同源節(jié)點(diǎn)類型對當(dāng)前目的節(jié)點(diǎn)和時(shí)間的影響，yi：k表示不同目的節(jié)點(diǎn)類型對當(dāng)前源節(jié)點(diǎn)和時(shí)間的影響，yij：表示當(dāng)前源-目的節(jié)點(diǎn)對在不同時(shí)刻下的變化.

基于以上分析，為了準(zhǔn)確地建立吞吐量與往返時(shí)延之間的關(guān)聯(lián)，通過往返時(shí)延推測吞吐量，本文設(shè)計(jì)了一個(gè)吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型（Association Learning Model，ALM），提出了從纖維到元素（fibers to element）的推測框架.如圖5 所示，給定源節(jié)點(diǎn)-目的節(jié)點(diǎn)-時(shí)間三元組(i，j，k)，關(guān)聯(lián)學(xué)習(xí)模型首先提取纖維向量y：jk、yi：k和yij：作為輸入，其中y：jk、yi：k和yij：分別代表源節(jié)點(diǎn)類型的影響、目的節(jié)點(diǎn)類型的影響、時(shí)序變化的影響，然后依次通過一個(gè)特征對齊模塊和一個(gè)非線性映射模塊來推測吞吐量xijk.

圖5 吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型(圖中例子:特征維度D=4,卷積通道數(shù)C=5)

在特征對齊模塊中，y：jk、yi：k和yij：首先各自進(jìn)行一個(gè)線性變換提取特征，

其中，h1，h2，h3∈RD×1分別表 示y：jk、yi：k和yij：通過線性變換提取的特征向量，W1∈RI×D，W2∈RJ×D，W3∈RK×D為權(quán)重矩陣，b1，b2，b3∈RD×1為偏置項(xiàng)，D為特征維度.線性變換的主要目的是對齊3 個(gè)纖維向量的特征維度，為了最大程度保留纖維的原始特征，此處沒有使用激活函數(shù).再對特征向量h1，h2，h3進(jìn)行拼接和維度擴(kuò)展（expand_dims）操作，得到特征張量H.H 包含了往返時(shí)延yijk沿著張量3 個(gè)模的聚合信息，用于輸入非線性映射模塊來擬合吞吐量xijk.

非線性映射模塊由2 個(gè)二維卷積層和1 個(gè)全連接層組成.第一層卷積核的大小為1×3，第二層卷積核的大小為D×1.令C表示通道數(shù)，即每一層卷積核的個(gè)數(shù)，θ1和θ2分別表示兩層卷積的卷積核參數(shù)，ReLU(·)=max(·，0)表示激活函數(shù)，則卷積層的計(jì)算可形式化為

令x′ijk=f(y：jk，yi：k，yij：|Θ)表示式（1）～（4）的 吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型，其中，Θ={W1，W2，W3，b1，b2，b3，θ1，θ2，w，b} 表示所有可訓(xùn)練參數(shù)的集合，選用均方誤差（Mean Squared Error，MSE）作為損失函數(shù)，模型的優(yōu)化目標(biāo)可以形式化為

其中，|Ω|表示索引集合Ω的基數(shù).梯度下降等算法可用于優(yōu)化式（5），所有測量元素xijk，(i，j，k)∈Ω，可作為標(biāo)簽對模型進(jìn)行點(diǎn)對點(diǎn)的有監(jiān)督訓(xùn)練.在訓(xùn)練階段完成后，對于吞吐量張量的任意缺失點(diǎn)(i，j，k)∈，可以提取往返時(shí)延張量Y 對應(yīng)的纖維，輸入訓(xùn)練好的模型，計(jì)算缺失點(diǎn)的吞吐量值，最終獲取從往返時(shí)延推測出來的吞吐量張量X′.

4.3 基于關(guān)聯(lián)學(xué)習(xí)的張量填充算法

在學(xué)習(xí)了往返時(shí)延和吞吐量之間的關(guān)聯(lián)之后，如何有效地結(jié)合關(guān)聯(lián)學(xué)習(xí)模型與張量填充算法，同時(shí)利用數(shù)據(jù)內(nèi)部時(shí)空相關(guān)性和外部關(guān)聯(lián)信息來提高吞吐量的恢復(fù)精度成為了關(guān)鍵.為此，本文提出了基于關(guān)聯(lián)學(xué)習(xí)的張量填充模型.首先將由往返時(shí)延和關(guān)聯(lián)學(xué)習(xí)模型推測出來的吞吐量張量X′與部分測量的吞吐量張量X合并為完整的預(yù)填充吞吐量張量

其中，PΩ表達(dá)到Ω的正交投影，如果(i，j，k)∈Ω，則[PΩ(X)]ijk=xijk；其他情況下，[PΩ(X)]ijk=0.PΩˉ同理.式（6）中，預(yù)填充的吞吐量張量保留了原始吞吐量張量的測量值，僅使用關(guān)聯(lián)學(xué)習(xí)模型對缺失點(diǎn)的推測值，即當(dāng)(i，j，k)∈Ω時(shí)，吞吐量在該位置具有測量值當(dāng)時(shí)，吞吐量測量值在該位置缺失，使用往返時(shí)延和關(guān)聯(lián)學(xué)習(xí)模型的推測值進(jìn)行預(yù)填充

為了挖掘吞吐量測量數(shù)據(jù)內(nèi)部的潛在特征，使用CP分解將預(yù)填充的吞吐量張量分解為3 個(gè)因子矩陣A∈RI×R，B∈RJ×R和C∈RK×R的形式，即其中R為張量的秩.令ai∈R1×R，bj∈R1×R和ck∈R1×R分別表示A的第i行，B的第j行和C的第k行，其物理意義分別為源節(jié)點(diǎn)i，目的節(jié)點(diǎn)j和時(shí)間k在潛在特征空間R1×R下的因子向量的每一個(gè)元素可用因子矩陣對應(yīng)行向量的內(nèi)積近似表示，即

在基于CP 分解的張量填充算法中，網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)問題被轉(zhuǎn)換為張量填充問題，訓(xùn)練潛在因子向量ai，bj和ck，計(jì)算其交互，即內(nèi)積，用于估計(jì)缺失的網(wǎng)絡(luò)數(shù)據(jù).傳統(tǒng)張量填充算法通常以最小化測量點(diǎn)的測量值與CP分解的估計(jì)值之間的均方誤差作為優(yōu)化目標(biāo)，如式（7）所示.對于每一個(gè)源節(jié)點(diǎn)-目的節(jié)點(diǎn)-時(shí)間三元組，式（7）基于源節(jié)點(diǎn)潛在特征因子、目的節(jié)點(diǎn)潛在因子和時(shí)間潛在因子之間的交互來建模吞吐量的值.

然而，傳統(tǒng)CP 分解模型僅使用測量點(diǎn)的數(shù)據(jù)進(jìn)行訓(xùn)練，無法有效地利用往返時(shí)延及其與吞吐量之間的關(guān)聯(lián).本文提出了一個(gè)組合的加權(quán)損失函數(shù)，在原有的目標(biāo)函數(shù)中加入了往返時(shí)延的輔助信息.所提損失函數(shù)如式（8）所示，其中ρ表示關(guān)于(i，j，k)的二值函數(shù)：如果(i，j，k)∈Ω，則ρ(i，j，k)=1；反之如 果(i，j，k)∈，則ρ(i，j，k)=λ，λ∈(0，1)為事先指定的誤差平衡權(quán)重.

式（8）整體上利用CP 分解因子向量ai，bj和ck的交互值對預(yù)填充張量進(jìn)行逼近，不僅追求對測量值的最小重構(gòu)誤差，還追求對往返時(shí)延和關(guān)聯(lián)學(xué)習(xí)模型所推測數(shù)據(jù)的最小重構(gòu)誤差，達(dá)到了同時(shí)利用時(shí)空相關(guān)性和關(guān)聯(lián)信息的效果.細(xì)節(jié)上使用二值函數(shù)對兩部分的重構(gòu)誤差分配了不同的權(quán)重進(jìn)行區(qū)分，使得模型的訓(xùn)練更靈活.類似于同時(shí)執(zhí)行的多任務(wù)學(xué)習(xí)模型，主任務(wù)是學(xué)習(xí)吞吐量測量值的特征，輔助任務(wù)是學(xué)習(xí)往返時(shí)延關(guān)聯(lián)信息的特征.輔助任務(wù)與主任務(wù)的目標(biāo)是一致的，因?yàn)榻柚禃r(shí)延和關(guān)聯(lián)學(xué)習(xí)模型預(yù)先推測的吞吐量也是由吞吐量測量數(shù)據(jù)訓(xùn)練獲得的.加權(quán)的輔助任務(wù)是必要的，它可以充分利用輔助信息往返時(shí)延及其與吞吐量之間的關(guān)聯(lián)，并且能夠擴(kuò)充訓(xùn)練數(shù)據(jù)集，提高模型泛化能力，改善主任務(wù)的重構(gòu)精度.

圖6 為所提框架求解張量填充問題的主要步驟，包括：（1）組合測量張量與推測張量獲得預(yù)填充張量；（2）基于CP 分解，使用測量樣本和推測樣本同時(shí)訓(xùn)練潛在因子向量；（3）使用訓(xùn)練好的潛在因子向量估計(jì)張量元素.在獲得了3 個(gè)因子矩陣A，B和C之后，吞吐量張量可以用恢復(fù)，其元素為

圖6 基于關(guān)聯(lián)學(xué)習(xí)的張量填充算法的步驟

4.4 詳細(xì)算法流程

算法1 總結(jié)了基于關(guān)聯(lián)學(xué)習(xí)的張量填充算法的完整流程，其中超參數(shù)的設(shè)置將在實(shí)驗(yàn)部分詳細(xì)說明.在讀取數(shù)據(jù)之后，首先訓(xùn)練吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型，獲得通過關(guān)聯(lián)推測的吞吐量張量.再預(yù)填充吞吐量張量，訓(xùn)練基于關(guān)聯(lián)學(xué)習(xí)的張量填充模型，最后計(jì)算吞吐量的估計(jì)值.

5 實(shí)驗(yàn)評估

5.1 實(shí)驗(yàn)設(shè)置

數(shù)據(jù)集為了評估所提算法的性能，本文在WSDREAM 數(shù)據(jù)集上執(zhí)行了大量對比實(shí)驗(yàn)，將其建模成大小為142×4 500×64 的吞吐量張量和往返時(shí)延張量.原始數(shù)據(jù)集中，吞吐量的數(shù)據(jù)點(diǎn)占比為62.72%，往返時(shí)延的數(shù)據(jù)點(diǎn)占比為73.79%.仿真實(shí)驗(yàn)中，吞吐量張量的所有數(shù)據(jù)點(diǎn)按照p∶p∶1-2p的比例被劃分為訓(xùn)練集、驗(yàn)證集和測試集，其中p∈｛2%，4%，6%，8%，10%｝為訓(xùn)練集所占比例，又稱為采樣率.吞吐量的采樣率與吞吐量的測量代價(jià)成正比，采樣率越高，測量代價(jià)越大.訓(xùn)練集對應(yīng)于測量樣本，測試集模擬缺失樣本，驗(yàn)證集用于參數(shù)調(diào)優(yōu)和計(jì)算迭代停止條件.往返時(shí)延的所有數(shù)據(jù)都用于訓(xùn)練關(guān)聯(lián)學(xué)習(xí)模型，并在訓(xùn)練之前使用CP 分解對少量的缺失值進(jìn)行預(yù)填充，使得應(yīng)用場景更靈活.

評價(jià)指標(biāo)本文使用2 個(gè)評價(jià)指標(biāo)來評估數(shù)據(jù)恢復(fù)的準(zhǔn)確性，分別是歸一化的平均絕對誤差（Normalized Mean Absolute Error，NMAE）和歸一化的均方根誤差（Normalized Root Mean Square Error，NRMSE），計(jì)算方式分別如式（9）和式（10）所示.

所有的實(shí)驗(yàn)結(jié)果都報(bào)告在測試集上，式（9）和式（10）中缺失樣本索引集合特指測試集的樣本索引，xijk為實(shí)際測量值為估計(jì)值.NMAE與NRMSE越小表示模型恢復(fù)性能越好.

實(shí)驗(yàn)條件所提模型部署在Pytorch 上，使用NVIDIA GPU，GeForce RTX 2060 上運(yùn)行的CUDA 10.1對訓(xùn)練過程進(jìn)行加速、Adam 小批量梯度下降算法對模型進(jìn)行優(yōu)化，ALM 的批大小設(shè)置為128，ALTC 的批大小為1 024，學(xué)習(xí)率都為10-4.實(shí)驗(yàn)中設(shè)置了2 個(gè)迭代停止條件，滿足其一即可：（1）達(dá)到最大迭代次數(shù)1 000；（2）驗(yàn)證集上的損失函數(shù)連續(xù)50輪沒有下降.

對比算法對比算法覆蓋了傳統(tǒng)的線性張量填充算法，包括CPals［25］、CPnmu［26］、CPwopt［27］、TKals［25］，前3個(gè)算法基于CP 分解，最后一個(gè)算法基于Tucker 分解；以及目前主流的神經(jīng)網(wǎng)絡(luò)張量填充算法，包括NTC［19］、NTF［28］、NTM［29］、CoSTCo［30］.

5.2 與傳統(tǒng)線性算法對比恢復(fù)性能

圖7 繪制了ALTC 與4 種傳統(tǒng)線性張量填充算法在不同采樣率下缺失數(shù)據(jù)的恢復(fù)誤差曲線.隨著采樣率的增加，測量樣本的增加，所有算法的恢復(fù)性能都隨著NMAE 和NRMSE 的減少而增加.在所有的采樣率下，ALTC 以更小的NMAE 和NRMSE 達(dá)到了更好的恢復(fù)性能.即使在數(shù)據(jù)非常稀疏（采樣率2%）的情況下，ALTC的NMAE 和NRMSE 約為0.43 和0.45，而傳統(tǒng)線性算法（CPwopt）的NMAE 和NRMSE 約為0.64 和0.76，分別是ALTC的1.5倍和1.7倍.這些結(jié)果表明，ALTC能夠有效地挖掘并利用多指標(biāo)的輔助信息，達(dá)到更好的恢復(fù)性能.

圖7 ALTC在不同采樣率下與傳統(tǒng)線性算法對比恢復(fù)性能

5.3 與神經(jīng)網(wǎng)絡(luò)算法對比恢復(fù)性能

表1、表2記錄了ALTC與4種神經(jīng)網(wǎng)絡(luò)張量填充算法在不同采樣率下的缺失數(shù)據(jù)的恢復(fù)性能，其中表1為NMAE，表2 為NRMSE.如表所示，所有算法的恢復(fù)性能都隨著采樣率的增加變得更好，表現(xiàn)為越來越小的NMAE 和NRMSE.對比其他算法，ALTC 在當(dāng)前采樣率和評價(jià)指標(biāo)下都達(dá)到了更低的恢復(fù)誤差，說明在相同的吞吐量測量代價(jià)下，ALTC 的恢復(fù)效果更好.在采樣率2%的情況下，ALTC 比目前主流的神經(jīng)網(wǎng)絡(luò)填充結(jié)果改進(jìn)了(0.493 1-0.429 0)/0.493 1 ≈13%的NMAE 以及(0.528 6-0.447 8)/0.528 6 ≈15%的NRMSE.這進(jìn)一步證實(shí)了所提算法的有效性，即使ALTC 是基于CP 分解架構(gòu)的線性填充算法，訓(xùn)練參數(shù)也遠(yuǎn)小于復(fù)雜的神經(jīng)網(wǎng)絡(luò)模型，但由于很好地利用了多指標(biāo)輔助信息，表現(xiàn)出了優(yōu)異的性能.

表1 不同采樣率下與神經(jīng)網(wǎng)絡(luò)算法比較NMAE

表2 不同采樣率下與神經(jīng)網(wǎng)絡(luò)算法比較NRMSE

5.4 吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型分析

圖8 給出了僅使用關(guān)聯(lián)學(xué)習(xí)模型ALM 通過往返時(shí)延推測吞吐量在不同吞吐量采樣率下的推測效果.為了更直觀地展示，同樣繪制了ALTC 的恢復(fù)性能用于對比.通過圖8 可以觀察到，ALTC 比ALM 對于吞吐量指標(biāo)的估計(jì)效果更好，因?yàn)锳LTC 是在ALM 架構(gòu)上的改進(jìn)，驗(yàn)證了所提的基于關(guān)聯(lián)學(xué)習(xí)的張量填充的有效性.對比表1、表2與圖8中的結(jié)果，可以發(fā)現(xiàn)ALM與目前主流的神經(jīng)網(wǎng)絡(luò)張量填充算法相比仍然取得了非常有競爭力的性能，這表明了本文所提的關(guān)聯(lián)學(xué)習(xí)模型在挖掘吞吐量-往返時(shí)延關(guān)聯(lián)上的優(yōu)越性.

圖8 關(guān)聯(lián)學(xué)習(xí)模型在不同采樣率下的推測效果

如4.2 節(jié)所示，為了考慮上下文信息，關(guān)聯(lián)學(xué)習(xí)模型輸入為張量3個(gè)維度的纖維，對應(yīng)于時(shí)間維度的變化以及不同源節(jié)點(diǎn)（用戶）、目的節(jié)點(diǎn)（服務(wù)）類型的影響.為了研究最終的吞吐量值與不同上下文信息的關(guān)聯(lián)性強(qiáng)度，固定采樣率為10%，在圖9 給出了考慮不同上下文信息的關(guān)聯(lián)學(xué)習(xí)模型的推測效果.圖9中，ALM 為原始模型，同時(shí)考慮了3 個(gè)維度的上下文信息，其他3 個(gè)模型是ALM 的變種：ALM-w/o-time 表示在輸入時(shí)去掉時(shí)間纖維，僅考慮不同節(jié)點(diǎn)類型的影響；ALM-w/o-user表示在輸入時(shí)去掉用戶纖維，僅考慮不同服務(wù)節(jié)點(diǎn)類型和時(shí)間變化的影響；ALM-w/o-service 表示在輸入時(shí)去掉服務(wù)纖維，僅考慮不同用戶節(jié)點(diǎn)類型和時(shí)間變化的影響.可以觀察到，在四個(gè)模型中，ALM的誤差最小，說明三個(gè)維度的上下文信息對推測吞吐量的值都非常有效；ALM-w/o-user 的誤差最大，說明考慮不同的用戶節(jié)點(diǎn)類型對恢復(fù)效果的收益最大，即不同的用戶節(jié)點(diǎn)類型與最終的吞吐量預(yù)測值最相關(guān).

圖9 考慮不同上下文信息的關(guān)聯(lián)學(xué)習(xí)模型的推測效果

5.5 超參數(shù)研究

本節(jié)描述了關(guān)鍵超參數(shù)（ALM 的特征數(shù)D、通道數(shù)C和ALTC 的秩R、誤差平衡權(quán)重λ）對模型性能的影響，其中采樣率固定為10%.為了避免繁瑣的超參數(shù)搜索，設(shè)定以下條件：（1）對ALM 和ALTC 的超參數(shù)進(jìn)行單獨(dú)調(diào)優(yōu)，即ALM 的參數(shù)僅根據(jù)其對吞吐量的推測效果決定，不依賴于后續(xù)的ALTC 的填充效果；在找到了ALM的最優(yōu)參數(shù)之后，再固定ALM 搜索ALTC 的最優(yōu)參數(shù)；（2）固定ALM 的特征數(shù)等于通道數(shù)；（3）每次僅變化一個(gè)超參數(shù)而固定其他，找到可以達(dá)到最佳恢復(fù)性能的值.

特征數(shù)D、通道數(shù)C 的影響特征數(shù)D和通道數(shù)C都表示了模型將往返時(shí)延纖維轉(zhuǎn)換成吞吐量值時(shí)設(shè)定的特征數(shù).D和C越大，可表示的特征數(shù)越多，模型的參數(shù)規(guī)模越大.圖10（a）繪制不同特征數(shù)和通道數(shù)對ALM 推測性能的影響.隨著D和C的增大，模型的推測性能隨著NMAE 和NRMSE 的減少而提高.一開始誤差快速下降，當(dāng)D和C超過30 后，誤差下降速度變緩.考慮到模型復(fù)雜度與精度的平衡，本文根據(jù)結(jié)果設(shè)定ALM的特征值和通道數(shù)D=C=30.

張量秩R 的影響張量秩R也表示了模型可以捕獲的潛在因子的特征維度，它直接影響了模型的參數(shù)規(guī)模.R越大，提取的特征維度越多，模型需要訓(xùn)練的參數(shù)也越多.圖10（b）繪制了不同的秩對ALTC 恢復(fù)性能的影響.一開始隨著R值的增加，模型的恢復(fù)性能隨著NMAE 和NRMSE 的減少而提高.當(dāng)R超過20 后，隨著R值的增加，模型的恢復(fù)性能反而會降低.這是由網(wǎng)絡(luò)測量數(shù)據(jù)的低秩特征決定的，R表示使用CP 分解表示吞吐量張量的秩，恰當(dāng)?shù)牡椭瓤梢愿玫財(cái)M合完整的張量數(shù)據(jù)，而過大的秩會導(dǎo)致參數(shù)量增大，模型對訓(xùn)練集的擬合能力變強(qiáng)、泛化能力變差，即過擬合.因此，在ALTC的設(shè)定中，R=20.

誤差平衡權(quán)重λ 的影響如式（8）所示，損失函數(shù)中的λ是為了在模型訓(xùn)練過程中平衡對測量值的擬合程度和對推測值的擬合程度.λ越小，模型擬合測量值的程度越大；λ越大，模型擬合推測值的程度越大.圖10（c）繪制了不同的誤差平衡權(quán)重對模型恢復(fù)性能的影響.一開始隨著λ的增大，模型的恢復(fù)性能得到了提高.當(dāng)λ超過0.01 之后，恢復(fù)性能隨著λ的增大開始下降.這說明了為模型選擇合適的λ可以幫助提高模型的恢復(fù)精度和泛化能力.因此，在ALTC 的設(shè)定中，λ=0.01.

圖10 不同的超參數(shù)對模型性能的影響

5.6 復(fù)雜度分析

如算法1所示，本文提出的模型可以分為獨(dú)立的兩個(gè)訓(xùn)練步驟：ALM 和ALTC.由于ALTC 是基于CP 分解架構(gòu)的線性填充算法，相比于傳統(tǒng)的線性張量填充算法，僅需要額外的開銷用于訓(xùn)練ALM，其訓(xùn)練參數(shù)集合Θ的總數(shù)據(jù)量為(I+J+K+C+3)D+4C+1.表3給出了采樣率10%下不同模型的訓(xùn)練時(shí)間.ALM 訓(xùn)練一批數(shù)據(jù)的時(shí)間最長，即單位訓(xùn)練時(shí)間最長，因?yàn)樾枰嗟臅r(shí)間學(xué)習(xí)從往返時(shí)延到吞吐量復(fù)雜的映射關(guān)系，而且在實(shí)際應(yīng)用中，可以用歷史數(shù)據(jù)事先將ALM 訓(xùn)練好，在數(shù)據(jù)恢復(fù)時(shí)直接使用，大大加快填充速度.ALTC 訓(xùn)練一輪全部數(shù)據(jù)需要的時(shí)間比CP 分解需要的時(shí)間更長，即全部訓(xùn)練時(shí)間最長，因?yàn)橛?xùn)練數(shù)據(jù)更多，當(dāng)采樣率為10%時(shí)，CP分解只有10%的吞吐量測量值用于訓(xùn)練，而ALTC 有10%的吞吐量測量值和90%的吞吐量推測值用于訓(xùn)練，是CP分解的10倍.

表3 訓(xùn)練時(shí)間對比

6 結(jié)論

本文提出了一種新的面向大規(guī)模網(wǎng)絡(luò)測量的數(shù)據(jù)恢復(fù)算法，即基于關(guān)聯(lián)學(xué)習(xí)的張量填充（ALTC），針對網(wǎng)絡(luò)監(jiān)控系統(tǒng)難以獲得全網(wǎng)吞吐量測量數(shù)據(jù)的問題，利用吞吐量內(nèi)部的時(shí)空相關(guān)性和外部指標(biāo)的關(guān)聯(lián)，以低測量代價(jià)獲取全部吞吐量數(shù)據(jù).首先研究網(wǎng)絡(luò)性能指標(biāo)的實(shí)際關(guān)聯(lián)，設(shè)計(jì)了吞吐量-往返時(shí)延關(guān)聯(lián)學(xué)習(xí)模型，使用低開銷的往返時(shí)延推測高開銷的吞吐量，降低測量代價(jià).為了利用多指標(biāo)關(guān)聯(lián)模型輔助吞吐量填充，提高數(shù)據(jù)恢復(fù)的精度，進(jìn)一步將吞吐量的測量值與通過往返時(shí)延和關(guān)聯(lián)學(xué)習(xí)模型的推測值合并為新的張量填充擬合目標(biāo)，并設(shè)計(jì)新的張量填充模型，同時(shí)學(xué)習(xí)吞吐量測量值和來自于往返時(shí)延的推測值的信息，設(shè)置誤差平衡參數(shù)平衡兩部分誤差的權(quán)重.真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明在相同的吞吐量測量代價(jià)下，本文所提的數(shù)據(jù)恢復(fù)算法ALTC 的恢復(fù)誤差在傳統(tǒng)線性張量填充算法的結(jié)果上改善了1.5 倍，而且比目前主流的神經(jīng)網(wǎng)絡(luò)張量填充算法的恢復(fù)結(jié)果降低了13%的誤差.