[發(fā)明專利]基于多層局部敏感哈希表的網(wǎng)絡(luò)流量異常快速檢測方法

有效

• 申請?zhí)枺?/td>: 201710001459.7
• 申請日: 2017-01-03
• 公開（公告）號: CN107070867B
• 公開（公告）日: 2020-06-16
• 發(fā)明（設(shè)計）人: 黃俊;謝鯤;陳宇翔;文吉剛
• 申請（專利權(quán)）人: 湖南大學(xué)
• 主分類號: H04L29/06
• 分類號: H04L29/06
• 代理公司: 長沙正奇專利事務(wù)所有限責(zé)任公司 43113
• 代理人: 馬強;王娟

1.一種基于多層局部敏感哈希表的網(wǎng)絡(luò)流量異常快速檢測方法，其特征在于，包括以下步驟：

1)輸入帶噪聲流量矩陣X，初始化異常矩陣S；

2)反復(fù)迭代(2)式和(3)式，得到(2)式和(3)式的最優(yōu)解：

其中，C為去噪流量數(shù)據(jù)矩陣；L為低秩逼近矩陣；e為異常矩陣S非零項的最大值；k為低秩逼近矩陣分解的最大秩；為二范數(shù)；

3)輸出低秩逼近矩陣L和異常矩陣S，即得到帶噪聲流量矩陣X的低秩逼近矩陣L和異常矩陣S，完成異常檢測；其中，

所述2)式的求解過程包括以下步驟：

A.將2)式轉(zhuǎn)化為如下問題：

其中，V_k表示維度為k的子空間，C_k表示C在V_k上的投影矩陣；O^n×k中的O表示子空間的符號，該子空間的大小為n行k列，即該子空間包含k個列向量，每個列向量的維度為n；

B.設(shè)計用于存儲OD對向量的多層局部敏感哈希表：頂層哈希表表示基本哈希表，基本哈希表對應(yīng)基本局部敏感哈希函數(shù)的桶寬為W，向下各層哈希表都是虛擬的，它們對應(yīng)的局部敏感哈希函數(shù)的桶寬依次為：2W,4W,8W,16W,…；

C.利用多層局部敏感哈希表，通過Subspace-NoReuse方法自適應(yīng)尋找子空間V_k，實現(xiàn)流量異常快速檢測；或者，利用多層局部敏感哈希表，通過LSH-subspace方法快速尋找子空間V_k，實現(xiàn)流量異常快速檢測。

2.根據(jù)權(quán)利要求1所述的基于多層局部敏感哈希表的網(wǎng)絡(luò)流量異常快速檢測方法，其特征在于，通過Subspace-NoReuse方法自適應(yīng)尋找子空間V_k的具體實現(xiàn)過程包括：

1)構(gòu)建多層局部敏感哈希表H；

2)初始化列表Q為空；

3)將第一層哈希表包含的哈希桶H[1,1]插入列表Q；

4)計算列表Q中各哈希桶包含OD對向量的平均值向量，然后進(jìn)行歸一化，設(shè)p＝1；

5)當(dāng)p＜k時，一直進(jìn)行如下循環(huán)，直到p＝k為止，尋找出子空間V_k：

5a)列表Q中哈希桶對應(yīng)的矩陣記為C_I，根據(jù)矩陣劃分原則，選擇投影誤差最大的子矩陣進(jìn)行劃分，即：V_p∈O^n×p；I＝1,2,…,p；m_I表示C_I的行數(shù)；O^n×p中的O表示子空間的符號，該子空間的大小為n行p列，即該子空間包含p個列向量，每個列向量的維度為n；

5b)從列表Q中移除C_I對應(yīng)的哈希桶，同時記錄C_I所在的層數(shù)索引值F以及對應(yīng)哈希桶索引值f；

5c)從子空間V_p中移除由C_I貢獻(xiàn)的基向量，更新子空間V_p；

5d)根據(jù)C_I所在的層數(shù)索引值F以及對應(yīng)哈希桶索引值f，將C_I一分為二，C_I一分為二后的兩個子矩陣所在的哈希層索引值為F*＝F+1，該兩個子矩陣對應(yīng)的哈希桶索引值分別為：2f-1,2f；

5e)對于f∈ID：將哈希桶H[F^*,f]插入列表Q；計算哈希桶H[F^*,f]對應(yīng)矩陣的平均值向量，通過Gram-Schmidt標(biāo)準(zhǔn)正交化，更新子空間V_p；哈希桶H[F^*,f]具體含義是指：第F^*層中的第f個哈希桶；ID＝{2f-1,2f}；

5f)當(dāng)步驟5e)完成后，設(shè)V_p+1＝V_p，p的值加1；

5g)繼續(xù)重復(fù)步驟5a)～5f)，當(dāng)p＝k時，整個循環(huán)結(jié)束，返回循環(huán)后得到的子空間。

3.根據(jù)權(quán)利要求2所述的基于多層局部敏感哈希表的網(wǎng)絡(luò)流量異常快速檢測方法，其特征在于，重用多層局部敏感哈希表快速尋找子空間V_k的具體實現(xiàn)過程包括：

1)已知帶噪聲流量矩陣X以及兩個連續(xù)迭代步驟中的異常矩陣S[t],S[t+1]，判斷從矩陣C[t]到C[t+1]所有可能發(fā)生變化的行，用R[t]和R[t+1]分別記錄S[t]和S[t+1]非零項的行索引；R＝R[t]∪R[t+1]；S[t],S[t+1]為連續(xù)兩個迭代步驟的異常矩陣；C[t]，C[t+1]為連續(xù)兩個迭代步驟的去噪流量數(shù)據(jù)矩陣；

2)對于r∈R：從多層局部敏感哈希表中刪除行C[t]_(r)，將行C[t+1]_(r)插入多層局部敏感哈希表；C[t]_(r)表示第t次迭代的去噪流量數(shù)據(jù)矩陣的第r行；

3)運用Subspace-NoReuse方法，求解C[t+1]對應(yīng)的子空間V_k。