一種基于數(shù)據(jù)補(bǔ)全的大象流檢測(cè)方法

許藝凡,李宜錚,王光耀,段靖海,王科翔,陶 軍,4

1(東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,南京 211189)

2(中航工業(yè)沈陽飛機(jī)設(shè)計(jì)研究所,沈陽 110036)

3(中國(guó)航空研究院,北京 100029)

4(網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室,南京 211189)

0 引 言

近年來,伴隨著互聯(lián)網(wǎng)的高速發(fā)展和其信息資源規(guī)模不斷擴(kuò)大,網(wǎng)絡(luò)擁塞控制、網(wǎng)絡(luò)資源調(diào)度、網(wǎng)絡(luò)異常檢測(cè)等研究領(lǐng)域引發(fā)越來越多的關(guān)注,而大象流的精準(zhǔn)檢測(cè)是實(shí)現(xiàn)上述任務(wù)的有效手段和必要前提.

在真實(shí)的網(wǎng)絡(luò)流量中,流量分布往往是高度傾斜的[1-4],即絕大多數(shù)網(wǎng)絡(luò)流量是老鼠流,少數(shù)是大象流.

由于現(xiàn)有高速流量采集方法常難以應(yīng)對(duì)互聯(lián)網(wǎng)的海量流量,且在流量測(cè)量中存在數(shù)據(jù)丟失的情況,因此在將數(shù)據(jù)提供給流量分析前,迫切需要對(duì)不完整的數(shù)據(jù)進(jìn)行精確的補(bǔ)全和填充.當(dāng)前,關(guān)于網(wǎng)絡(luò)流量補(bǔ)全的研究主要包含3類:基于壓縮感知的方法,基于矩陣補(bǔ)全的方法和基于張量補(bǔ)全的方法.

關(guān)于壓縮感知的工作主要集中在向量數(shù)據(jù)上,而在面向矩陣時(shí)需要將矩陣分割成多個(gè)向量,這破壞了矩陣兩個(gè)維度之間的關(guān)聯(lián)性,存在很大的改進(jìn)空間,基于矩陣補(bǔ)全、向量補(bǔ)全的方法應(yīng)運(yùn)而生.

M.Roughan等[5]借助壓縮感知和矩陣補(bǔ)全領(lǐng)域的思想提出SRMF算法,利用網(wǎng)絡(luò)流量的時(shí)空特征,尋找流量矩陣的全局稀疏低秩近似.而E.J.Candes等[6]表明絕大多數(shù)的低秩矩陣可以通過解決一個(gè)簡(jiǎn)單凸優(yōu)化問題來精確重構(gòu)缺失值,同時(shí)指出在適當(dāng)?shù)臈l件下,可以通過求解一個(gè)簡(jiǎn)單的凸優(yōu)化問題[7],即數(shù)據(jù)約束下的核范數(shù)最小化問題,實(shí)現(xiàn)從最小數(shù)據(jù)集中恢復(fù)出低秩矩陣.Y.Liao等[8]將大規(guī)模網(wǎng)絡(luò)中端到端距離預(yù)測(cè)問題歸結(jié)為矩陣補(bǔ)全問題,即對(duì)由網(wǎng)絡(luò)數(shù)據(jù)構(gòu)造的兩兩距離矩陣中的未知項(xiàng)進(jìn)行預(yù)測(cè).J.Cheng等[9]利用低秩特征,提出了基于矩陣補(bǔ)全的傳感器網(wǎng)絡(luò)數(shù)據(jù)采集算法,避免了必須為特定傳感器網(wǎng)絡(luò)定制采集策略的問題.F.Nie等[10]提出一種新的基于非凸低秩近似的矩陣補(bǔ)全方法,利用它構(gòu)造了兩個(gè)矩陣補(bǔ)全模型,并開發(fā)了一種具有收斂性的高效優(yōu)化方法以有效地求解所構(gòu)建的模型,與傳統(tǒng)方法相比,該方法具有更快的收斂速度.A.Mongia等[11]對(duì)于傳統(tǒng)的矩陣分解和核范數(shù)最小化方法進(jìn)行拓展,通過在行和列上合并多個(gè)圖,提出基于矩陣補(bǔ)全的協(xié)同過濾策略.

與傳統(tǒng)的基于矢量或基于矩陣的方法不同,F.Liu and Q.Wang[12]提出了一種基于稀疏張量的高光譜圖像分類算法.X.Chen等[13]受上限核范數(shù)魯棒性的啟發(fā),利用張量奇異值分解,提出面向圖像和視頻修復(fù)的低秩張量補(bǔ)全方法.K.Xie等[14,15]中將網(wǎng)絡(luò)流量數(shù)據(jù)建模成一個(gè)三階張量,除了時(shí)間、空間之外還加入了周期維度,在數(shù)據(jù)補(bǔ)全過程挖掘出更深層次的結(jié)構(gòu)關(guān)系,獲取更精準(zhǔn)的數(shù)據(jù)補(bǔ)全結(jié)果;同時(shí)利用正常網(wǎng)絡(luò)流量的低秩性特征和異常網(wǎng)絡(luò)流量的稀疏性特征,將異常檢測(cè)問題表述為一個(gè)魯棒張量修復(fù)問題[16];在此基礎(chǔ)上,提出的張量修復(fù)模型[17],挖掘出了數(shù)據(jù)各個(gè)維度中的非線性關(guān)系,從而獲取更高的檢測(cè)精準(zhǔn)度.J.Wang等[18]旨在恢復(fù)多維圖像的缺失信息,提出了一種基于耦合變換的低秩張量表示算法,該算法充分利用空間多尺度特性以及時(shí)空維度、光譜/時(shí)間維度上的冗余性,從而實(shí)現(xiàn)了更好的張量低秩近似.

1 理論基礎(chǔ)

為了更好的理解本文中的張量補(bǔ)全過程,在此將對(duì)本文中所使用到的張量分解理論基礎(chǔ)進(jìn)行必要的解釋說明.

定義1.張量是一個(gè)多維數(shù)組,也可以看作是向量(一階張量)和矩陣(二階張量)的高階泛化.一個(gè)N階張量(表示為χ∈RI1×I2×…×In)是N向量空間的張量積,N稱為張量χ的階數(shù).

定義2.如果一個(gè)3階張量χ可以表示為3個(gè)列向量的外積,例如χ=a°b°c,那么3階張量χ就是一個(gè)秩1張量.

定義4.一個(gè)3階張量的切片是一組二維子序列,例如在圖1中,一個(gè)3階張量χ可以被拆分為垂直切片,側(cè)面切片和前向切片,分別表示為Xi:：,Xj:：和Xk:：.在本文中將前向切片X::k表示為Xk.

圖1 張量切片F(xiàn)ig.1 Tensor slice

2 矩陣補(bǔ)全算法研究

2.1 矩陣奇異值分解

對(duì)于任意的矩陣M,其中M的維度為n×m,M可以被分解為如下3個(gè)矩陣:

M=U∑VT

(1)

其中,VT表示V的轉(zhuǎn)置,U是一個(gè)n×n的酉矩陣(UTU=UUT=I),V是一個(gè)m×m的酉矩陣(VTV=VVT=I),∑是一個(gè)維度為n×m的對(duì)角矩陣,對(duì)角線上的元素σi為M的奇異值,通常奇異值的排列順序?yàn)棣襥≥σi+1.矩陣的秩為矩陣中線性獨(dú)立的行數(shù)或列數(shù),等于非零奇異值的數(shù)量.

為了便于理解奇異值分解在矩陣補(bǔ)全中的應(yīng)用,可以參考奇異值分解的如下解釋.因?yàn)榫仃嚒剖且粋€(gè)對(duì)角矩陣,所以矩陣M的奇異值分解可以被重寫為如下形式:

(2)

(3)

(4)

2.2 矩陣補(bǔ)全過程

在上一小節(jié)中,本文詳細(xì)介紹了矩陣的奇異值分解,接下來將利用這一工具實(shí)現(xiàn)矩陣補(bǔ)全.通過對(duì)最初的奇異值分解進(jìn)行變化,公式(1)可以轉(zhuǎn)化為如下形式:

M=U∑VT=LRT

(5)

其中,L=U∑1/2,R=V∑1/2,在接下來的推導(dǎo)過程中本文將主要使用這種形式.

(6)

其中,τ是控制已知項(xiàng)誤差范圍的參數(shù).將公式(5)代入(6)中可以進(jìn)一步得到如下公式:

minrank(LRT),.s.t‖M-LRT‖F(xiàn)≤τ,

(7)

秩最小化問題的目標(biāo)函數(shù)是一個(gè)非凸目標(biāo)函數(shù),直接求解很難實(shí)現(xiàn).根據(jù)之前壓縮感知領(lǐng)域的研究,對(duì)于一個(gè)低秩矩陣,其秩最小化問題等價(jià)于其核范數(shù)最小化問題[19-21],因此公式(7)可以進(jìn)一步轉(zhuǎn)化為如下形式:

(8)

將公式(8)中的兩個(gè)部分結(jié)合起來,可以得到最終的優(yōu)化目標(biāo):

(9)

3 張量補(bǔ)全算法研究

3.1 張量補(bǔ)全過程

張量補(bǔ)全是一種通過多維數(shù)據(jù)結(jié)構(gòu)分析缺失數(shù)據(jù)的有效途徑,其通用性和有效性被用于多個(gè)領(lǐng)域.本小節(jié)就如何實(shí)現(xiàn)張量補(bǔ)全展開必要的理論推導(dǎo).根據(jù)定義5張量的CP分解,任意張量M可以表示成如下形式:

(10)

A=[a(1),a(2),…,a(R)]∈RI×R、B=[b(1),b(2),…,b(R)]∈RJ×R、C=[c(1),c(2),…,c(R)]∈RK×R、為張量M的因子矩陣,R表示張量的秩.

(11)

其中,τ是控制已知項(xiàng)誤差范圍的參數(shù).將公式(10)代入(11)中可以進(jìn)一步將張量補(bǔ)全問題轉(zhuǎn)化如下:

minrank([A,B,C]),.s.t‖M-[A,B,C]‖F(xiàn)≤τ,

(12)

根據(jù)之前的分析,在低秩條件下,秩最小化問題等價(jià)于其核范數(shù)最小化問題,因此公式(12)可以進(jìn)一步轉(zhuǎn)化為如下形式:

(13)

在公式(13)中,M是一個(gè)張量,A,B,C都是因子矩陣,可以根據(jù)他們中的元素將公式(13)進(jìn)一步轉(zhuǎn)化:

(14)

其中,ai,bj,ck分別為A的第i行,B的第j行,C的第k行.λ表示正則化系數(shù),防止在補(bǔ)全的過程中出現(xiàn)過擬合問題,即觀測(cè)項(xiàng)的張量元素誤差很小,而補(bǔ)全項(xiàng)的張量元素誤差很大的問題.因子矩陣A、B、C分別對(duì)應(yīng)源域特征、目的域特征、時(shí)間域特征.

3.2 張量補(bǔ)全算法實(shí)現(xiàn)

這里主要給出對(duì)于目標(biāo)函數(shù)的求解方法,展示算法實(shí)現(xiàn)過程.需要強(qiáng)調(diào)的是,張量CP分解的秩R與矩陣的秩有所不同,對(duì)于一個(gè)給定的張量,沒有一種直接的算法來確定該張量的秩,因?yàn)檫@已經(jīng)被證明是一個(gè)NP復(fù)雜問題[22].

因此,對(duì)于目標(biāo)函數(shù)(13),可以使用交替最小二乘法來求解因子矩陣變量A、B、C.具體來說,可以先將因子矩陣A、B、C初始化,然后通過固定矩陣B、C的值,只把因子矩陣A看作變量,這樣目標(biāo)函數(shù)就變成了一個(gè)標(biāo)準(zhǔn)的線性最小二乘問題,可以很容易的求得因子矩陣A的值.同理,通過固定矩陣A、C可以得到因子矩陣B的值,固定矩陣A、B可以得到因子矩陣C的值.一直循環(huán)上述過程,直到結(jié)果收斂,便可以得到最終的因子矩陣A、B、C.

張量補(bǔ)全算法的具體實(shí)現(xiàn)過程如算法1所示.

算法1.張量補(bǔ)全算法

輸入:觀測(cè)到的流量{mijk|(i,j,k)∈Ω}
張量的秩R

輸出:張量分解結(jié)果A∈I×R,B∈J×R,C∈T×R,

1.初始化A,B,C

2.WHILEnot convergedo

3.FORi=1 toIdo

5.ENDFOR

6.FORj=1 toJdo

7. /*更新bj的方法同上*/

8.ENDFOR

9.FORk=1 toTdo

10. /*更新ck的方法同上*/

11.ENDFOR

12.ENDWHILE

13.RetureA,B,C

通過對(duì)目標(biāo)函數(shù)的不斷優(yōu)化,在獲得因子矩陣A、B、C后,張量中的補(bǔ)全項(xiàng)可以表示為:

(15)

4 實(shí)驗(yàn)仿真及性能分析

本文使用WS-DREAM[23]、CAIDA[24]、Abilene[25]公開網(wǎng)絡(luò)流量數(shù)據(jù)集.雖然實(shí)驗(yàn)主要在這3個(gè)數(shù)據(jù)集上開展,但因?yàn)榫W(wǎng)絡(luò)流量普遍存在時(shí)間穩(wěn)定性和空間相關(guān)性特征,所以相關(guān)研究也可以推廣到其他的網(wǎng)絡(luò)流量數(shù)據(jù)集中.

4.1 評(píng)估指標(biāo)

在仿真過程中首先通過數(shù)據(jù)補(bǔ)全算法實(shí)現(xiàn)對(duì)于數(shù)據(jù)的補(bǔ)全,之后在補(bǔ)全數(shù)據(jù)的基礎(chǔ)上實(shí)現(xiàn)對(duì)大象流的檢測(cè).因此在評(píng)估指標(biāo)選取時(shí),本文主要選取針對(duì)大象流檢測(cè)效果的評(píng)估指標(biāo).

具體地,本文選取歸一化折損累計(jì)增益(Normalized Discounted Cumulative Gain,NDCG)和精準(zhǔn)度(Precision)作為主要的評(píng)估指標(biāo),詳細(xì)介紹如下.

歸一化折損累計(jì)增益(NDCG)指標(biāo)通常是用來衡量和評(píng)價(jià)搜索結(jié)果算法的,在推薦算法和搜索引擎性能評(píng)估中經(jīng)常用到,本文利用這一指標(biāo)評(píng)估大象流檢測(cè)結(jié)果的歸一化折損累計(jì)增益.

折損累計(jì)增益DCG提出在搜索結(jié)果列表的較低位置上出現(xiàn)相關(guān)性較高的記錄時(shí),應(yīng)該對(duì)評(píng)測(cè)得分施加懲罰,懲罰比例與條目的所在位置的對(duì)數(shù)值相關(guān).DCG主要的兩個(gè)思想包括:1、高關(guān)聯(lián)度的結(jié)果比一般關(guān)聯(lián)度的結(jié)果更影響最終的指標(biāo)得分;2、有高關(guān)聯(lián)度的結(jié)果出現(xiàn)在更靠前的位置的時(shí)候,指標(biāo)會(huì)越高.給定一個(gè)結(jié)果列表的排序位置k,DCG可定義為:

(16)

其中reli表示相關(guān)性得分.

令y∈{k,…,1}表示真實(shí)的大象流記錄相關(guān)性向量,即最大的大象流相關(guān)性為k,最小的大象流相關(guān)性為1,用π表示通過計(jì)算測(cè)量得到的大象流記錄向量,yπi表示該向量中第i個(gè)元素在y中的相關(guān)性,reli即用yπi表示.則公式(16)可以轉(zhuǎn)換為:

(17)

例如在i=2時(shí),π2=5表示通過計(jì)算得到的第二大的大象流實(shí)際上是第五大的大象流,當(dāng)k=20時(shí),則yπ2=16,表示計(jì)算得到第二大的大象流的相關(guān)性為16.

而NDCG則表示歸一化折損累計(jì)增益,在DCG的基礎(chǔ)上進(jìn)行了如下的歸一化處理:

(18)

其中IDCGk為理想情況下的DCG,即通過計(jì)算測(cè)量得到的大象流記錄向量恰好就是真實(shí)的大象流記錄向量情況下的DCG,NDCG的值域范圍在0到1之間.

精準(zhǔn)度(Precision)指標(biāo)用來評(píng)估通過計(jì)算測(cè)量得到的大象流記錄中有多少是真實(shí)的大象流.用φk表示真實(shí)的Top-k的大象流,用φk表示測(cè)量得到的Top-k的大象流,則精準(zhǔn)度可以通過公式(19)表示:

(19)

實(shí)驗(yàn)對(duì)于不同的數(shù)據(jù)集設(shè)置不同的k值,對(duì)于WS-DREAM數(shù)據(jù)集和CAIDA數(shù)據(jù)集,將k設(shè)置為100,即分析每一個(gè)時(shí)間間隙中Top-100的大象流,之后對(duì)每一個(gè)時(shí)間間隙中的評(píng)估結(jié)果做均值處理.而對(duì)于Abilene數(shù)據(jù)集,由于數(shù)據(jù)量較小,故將k設(shè)置為20.

4.2 超參數(shù)R的影響評(píng)估

在分析過程中,用R來表示張量的秩.張量秩與數(shù)據(jù)補(bǔ)全的性能緊密相關(guān),從而在較大程度上影響著大象流檢測(cè)的結(jié)果.正如之前所論述的,對(duì)于一個(gè)給定的張量,沒有一種直接的算法來確定該張量的秩,因?yàn)檫@已經(jīng)被證明是一個(gè)NP復(fù)雜問題.所以本文將張量秩作為一個(gè)超參數(shù),本實(shí)驗(yàn)主要觀測(cè)評(píng)估指標(biāo)隨張量秩R的變化情況,仿真結(jié)果如圖2所示.

圖2 評(píng)估指標(biāo)隨張量秩R的變化Fig.2 Change of the evaluation index with the tensor rank R

從圖2看出,在開始階段,隨著張量秩的提升,評(píng)估指標(biāo)的性能得到了顯著的提升,但當(dāng)張量的秩到達(dá)了一個(gè)閾值之后,評(píng)估指標(biāo)的性能趨于穩(wěn)定,不再隨著張量秩的變化而變化.對(duì)于WS-DREAM數(shù)據(jù)集,在張量秩達(dá)到102時(shí),評(píng)估指標(biāo)取得較好的評(píng)估效果,之后隨著R值增加,張量秩R對(duì)評(píng)估指標(biāo)的影響不大,但卻會(huì)帶來計(jì)算損耗的提升.所以在接下來的實(shí)驗(yàn)中,將WS-DREAM數(shù)據(jù)集的張量秩設(shè)置為102.同樣,將CAIDA數(shù)據(jù)集的張量秩設(shè)置為124,將Abilene數(shù)據(jù)集的張量秩設(shè)置為37.

4.3 檢測(cè)精準(zhǔn)度對(duì)比

本節(jié)針對(duì)使用的各種算法對(duì)大象流檢測(cè)的精準(zhǔn)度的影響展開對(duì)比.根據(jù)4.2節(jié)對(duì)于超參數(shù)的分析結(jié)果,將各數(shù)據(jù)集的超參數(shù)張量秩R設(shè)為預(yù)設(shè)值,比較基于無數(shù)據(jù)補(bǔ)全Original、基于矩陣分解的數(shù)據(jù)補(bǔ)全MC(Matrix Completion)算法、基于張量分解的數(shù)據(jù)補(bǔ)全TC(Tensor Completion)算法,在不同數(shù)據(jù)缺失條件下的大象流檢測(cè)精準(zhǔn)度,檢測(cè)結(jié)果如圖3和圖4所示.

圖3 歸一化折損累計(jì)增益對(duì)比Fig.3 Comparison of normalized loss cumulative gain

圖4 檢測(cè)精準(zhǔn)度對(duì)比Fig.4 Comparison of detection accuracy

從圖3和圖4的對(duì)比實(shí)驗(yàn)中可以看出,隨著數(shù)據(jù)缺失率的提高,各種算法的檢測(cè)性能都有不同程度的下降.同時(shí),雖然各算法的檢測(cè)性能在各個(gè)數(shù)據(jù)集上不完全一樣,但整體表現(xiàn)趨勢(shì)大致相同,驗(yàn)證了各算法的通用性.

對(duì)于所有的數(shù)據(jù)集,無數(shù)據(jù)補(bǔ)全Original的大象流檢測(cè)精準(zhǔn)度最差.因?yàn)檫@種方法直接使用原始觀測(cè)數(shù)據(jù)來檢測(cè)大象流,而原始觀測(cè)數(shù)據(jù)中存在較大范圍的數(shù)據(jù)缺失,且這些缺失數(shù)據(jù)中包含部分大象流,直接從原始觀測(cè)數(shù)據(jù)中檢測(cè)大象流完全忽略了這部分誤差,故而精準(zhǔn)度較差.

基于矩陣補(bǔ)全MC算法補(bǔ)全數(shù)據(jù)場(chǎng)景下的大象流檢測(cè)的精準(zhǔn)度相較于無數(shù)據(jù)補(bǔ)全有了很大的提升,但從圖中的對(duì)比可以看出,MC算法在數(shù)據(jù)缺失率較低時(shí)性能較好,但當(dāng)數(shù)據(jù)缺失率較高時(shí)性能下降嚴(yán)重.例如在圖3(b)中,對(duì)于CAIDA數(shù)據(jù)集,在數(shù)據(jù)缺失率較低時(shí),大象流檢測(cè)的精準(zhǔn)度較高,與TC算法基本持平,但當(dāng)數(shù)據(jù)缺失率超過50%時(shí),MC算法檢測(cè)精準(zhǔn)度有了明顯的下降.

基于張量補(bǔ)全TC算法補(bǔ)全數(shù)據(jù)情況下的大象流檢測(cè)精準(zhǔn)度最好,且在數(shù)據(jù)缺失率升高時(shí)依然可以維持較高的性能.例如在圖4(c)中,當(dāng)數(shù)據(jù)缺失率升高時(shí),其他兩種情況下的檢測(cè)精準(zhǔn)度已經(jīng)有了明顯的下降,但TC算法下大象流檢測(cè)精準(zhǔn)度依然穩(wěn)定在較高水平.這是因?yàn)閺埩垦a(bǔ)全算法作為矩陣補(bǔ)全算法的高階泛化,通過充分挖掘隱藏在流量數(shù)據(jù)內(nèi)部的時(shí)間穩(wěn)定性和空間相關(guān)性特征,精準(zhǔn)補(bǔ)全出部分缺失的大象流,從而在較大程度上獲得了精準(zhǔn)度的提升.

4.4 時(shí)間性能

本節(jié)關(guān)注TC算法的時(shí)間性能.實(shí)驗(yàn)運(yùn)行在一臺(tái)臺(tái)式機(jī)中,內(nèi)存16GB,硬盤1TB,CPU的運(yùn)行頻率最高可達(dá)3.4GHz.實(shí)驗(yàn)關(guān)注點(diǎn)在時(shí)間資源消耗變化趨勢(shì),即WS-DREAM數(shù)據(jù)集、CAIDA數(shù)據(jù)集、Abilene數(shù)據(jù)集在TC算法下時(shí)耗變化.3個(gè)數(shù)據(jù)集在TC算法下,運(yùn)行時(shí)間隨張量秩的變化情況如圖5所示.

圖5 TC算法計(jì)算時(shí)間隨張量秩的變化Fig.5 TC algorithm calculation time changes with tensor rank

從圖5中可以看出,伴隨著張量秩R的增加,時(shí)間消耗也在不斷的增加,這主要是因?yàn)镽的提升會(huì)帶來張量分解和張量補(bǔ)全過程中計(jì)算量的提升.因此,在之前對(duì)超參數(shù)R進(jìn)行參數(shù)評(píng)估時(shí),本文選取讓檢測(cè)性能首次趨于穩(wěn)定的張量秩.例如,對(duì)于WS-DREAM數(shù)據(jù)集,雖然在R到達(dá)102之后還有一些位置處能夠取得略高的檢測(cè)效果,但也帶來了計(jì)算量的大幅增加.

可以看到,通過這種張量補(bǔ)全的方式實(shí)現(xiàn)大象流檢測(cè)雖然可以實(shí)現(xiàn)較高的檢測(cè)效果,但時(shí)間資源上的消耗也很大.

在離線場(chǎng)景下,對(duì)于存在大量數(shù)據(jù)缺失的數(shù)據(jù),如果目標(biāo)是精準(zhǔn)檢測(cè)每一個(gè)時(shí)間間隙中的大象流,那么這種算法能夠很好的滿足需求.

具體地,各數(shù)據(jù)集在預(yù)設(shè)超參數(shù)下,使用TC算法補(bǔ)全數(shù)據(jù)并實(shí)現(xiàn)大象流檢測(cè)的平均時(shí)間消耗如表1所示.

表1 運(yùn)行時(shí)間表Table 1 Runing time

5 總 結(jié)

本文的主要關(guān)注點(diǎn)在于基于數(shù)據(jù)補(bǔ)全的離線大象流檢測(cè)算法研究.首先采用基于矩陣分解的數(shù)據(jù)補(bǔ)全模型,將流量數(shù)據(jù)補(bǔ)全問題轉(zhuǎn)化為一個(gè)低秩矩陣奇異值分解問題.接下來為實(shí)現(xiàn)更高的檢測(cè)精準(zhǔn)度,本文對(duì)矩陣補(bǔ)全方法進(jìn)行高維擴(kuò)展,利用張量CP分解實(shí)現(xiàn)數(shù)據(jù)補(bǔ)全,將原問題轉(zhuǎn)化為通過最小化張量秩來恢復(fù)缺失條目的張量補(bǔ)全問題.最后對(duì)上面使用的矩陣補(bǔ)全算法和張量補(bǔ)全算法進(jìn)行了仿真實(shí)驗(yàn),評(píng)估算法中的超參數(shù)影響,對(duì)比各算法的檢測(cè)精準(zhǔn)度,并展示了張量補(bǔ)全算法的時(shí)間開銷,仿真結(jié)果證明本文的方法取得了較好的效果.