基于有監(jiān)督判別投影的網(wǎng)絡(luò)安全數(shù)據(jù)降維算法

郭方方，呂宏武，任威霖，王瑞妮

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

1 引言

網(wǎng)絡(luò)空間安全已成為互聯(lián)網(wǎng)發(fā)展的核心挑戰(zhàn)，從系統(tǒng)漏洞、隱私泄露到網(wǎng)絡(luò)詐騙，各種安全威脅日益增多，網(wǎng)絡(luò)安全分析中所需要收集和統(tǒng)計(jì)的網(wǎng)絡(luò)安全數(shù)據(jù)量正在以指數(shù)級(jí)增長(zhǎng)，所以?xún)?yōu)化分析處理網(wǎng)絡(luò)安全數(shù)據(jù)的效率對(duì)于提高網(wǎng)絡(luò)安全與服務(wù)質(zhì)量有著非常重大的意義。然而，網(wǎng)絡(luò)安全數(shù)據(jù)的高維數(shù)據(jù)空間具備本征稀疏性，使多元密度估計(jì)問(wèn)題更加復(fù)雜，難以直接對(duì)其進(jìn)行求解。這一問(wèn)題于1957 年在Bellman 的著作序言中被提出，稱(chēng)作“維度災(zāi)難”。該問(wèn)題導(dǎo)致在分析原始的高維網(wǎng)絡(luò)安全數(shù)據(jù)時(shí)，會(huì)產(chǎn)生巨大的計(jì)算量，嚴(yán)重影響研究效率。為了更好地理解和處理這些高維復(fù)雜的網(wǎng)絡(luò)安全數(shù)據(jù)，人們開(kāi)始關(guān)注如何有效地降低數(shù)據(jù)的維度從而提高數(shù)據(jù)分析模型的性能。數(shù)據(jù)降維技術(shù)通過(guò)分析網(wǎng)絡(luò)安全數(shù)據(jù)不同維度之間的內(nèi)在聯(lián)系，在高維空間中發(fā)掘出其隱藏的低維映射，且能夠在一定程度上等效替代原有的高維結(jié)構(gòu)，從而降低網(wǎng)絡(luò)安全分析的時(shí)間復(fù)雜度[1]。為了提高網(wǎng)絡(luò)安全分析能力，十分有必要對(duì)網(wǎng)絡(luò)安全數(shù)據(jù)進(jìn)行降維處理[2]。

近年來(lái)，流形學(xué)習(xí)方法的研究方興未艾，國(guó)內(nèi)外不斷涌現(xiàn)出新的研究成果[3]。流形學(xué)習(xí)方法在特征空間內(nèi)建立的映射能夠?qū)?shù)據(jù)從高維度投影至低維度，有效去除了冗余信息，讓人們能夠更加直觀、清晰地理解數(shù)據(jù)的含義。在網(wǎng)絡(luò)安全分析領(lǐng)域，使用流形學(xué)習(xí)方法能夠有效降低網(wǎng)絡(luò)數(shù)據(jù)特征雜亂、冗余信息過(guò)多對(duì)模型帶來(lái)的負(fù)面影響，使模型的性能得以突破[4]。傳統(tǒng)流形學(xué)習(xí)方法為了保留數(shù)據(jù)的幾何信息，便于觀察，大多采用無(wú)監(jiān)督的方式。這雖然增強(qiáng)了數(shù)據(jù)的可視性，但沒(méi)有考慮原始數(shù)據(jù)的類(lèi)別信息，會(huì)使降維后數(shù)據(jù)的聚類(lèi)效果偏低，分類(lèi)不明顯，流量分析準(zhǔn)確率變低，潛藏網(wǎng)絡(luò)安全漏洞。近年來(lái)，隨著網(wǎng)絡(luò)面臨的安全威脅日益增加，越來(lái)越多的學(xué)者開(kāi)始將目光轉(zhuǎn)向聚類(lèi)效果更強(qiáng)的有監(jiān)督流形學(xué)習(xí)方法。網(wǎng)絡(luò)安全數(shù)據(jù)的有監(jiān)督學(xué)習(xí)方法具備一定的理論基礎(chǔ)，目前國(guó)內(nèi)外的網(wǎng)絡(luò)安全數(shù)據(jù)分析技術(shù)已較成熟，如美國(guó)麻省理工學(xué)院林肯實(shí)驗(yàn)室的DARPA 98、DARPA 99、DARPA 2000 數(shù)據(jù)分析項(xiàng)目，加利福尼亞大學(xué)網(wǎng)絡(luò)安全實(shí)驗(yàn)室[5]、斯坦福大學(xué)計(jì)算機(jī)安全實(shí)驗(yàn)室[6]等團(tuán)隊(duì)提出的較全面的網(wǎng)絡(luò)安全數(shù)據(jù)集和網(wǎng)絡(luò)安全數(shù)據(jù)分析方法，對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的絕大部分安全特征均有所研究。因此，即使對(duì)于未知的網(wǎng)絡(luò)安全數(shù)據(jù)，也能夠通過(guò)對(duì)現(xiàn)有數(shù)據(jù)特征的掌握和一定的數(shù)據(jù)分析技術(shù)手段，初步獲取必要的類(lèi)別信息，從而實(shí)現(xiàn)有監(jiān)督學(xué)習(xí)。因此，本文針對(duì)網(wǎng)絡(luò)安全數(shù)據(jù)分析中尚存的問(wèn)題，提出了一種有監(jiān)督判別投影（SDP,supervised discriminant projection）降維算法，在局部保留投影（LPP,locality preserving projection）等傳統(tǒng)方法的基礎(chǔ)上，根據(jù)高維數(shù)據(jù)的歐氏距離建立有監(jiān)督判別矩陣，并根據(jù)矩陣對(duì)局部近鄰圖賦值，建立有監(jiān)督全局散度矩陣和局部散度矩陣來(lái)尋找最佳投影子空間，挖掘高維數(shù)據(jù)的幾何結(jié)構(gòu)信息來(lái)對(duì)數(shù)據(jù)進(jìn)行降維。實(shí)驗(yàn)結(jié)果表明，與原有算法相比，經(jīng)該算法降維后的數(shù)據(jù)聚類(lèi)程度和算法效率均有所提高。

2 相關(guān)工作

近年來(lái)，數(shù)據(jù)降維技術(shù)的研究已取得很大進(jìn)展。這些研究主要分為線性降維方法和非線性降維方法，其主要區(qū)別在于分別適用于不同結(jié)構(gòu)類(lèi)型的數(shù)據(jù)。本節(jié)將對(duì)二者分別說(shuō)明，并詳細(xì)介紹非線性降維方法中的流形學(xué)習(xí)方法。

在數(shù)據(jù)降維技術(shù)發(fā)展早期，主流的研究方向是全局線性數(shù)據(jù)的降維方法，如主成分分析（PCA,principal component analysis）、線性判別分析（LDA,linear discriminant analysis）以及多維尺度分析（MDS,multiple dimensional scaling）等。文獻(xiàn)[7]提出了基于PCA 的分布式并行數(shù)據(jù)降維算法。作為最具代表性的線性算法之一，PCA 算法不需要先驗(yàn)知識(shí)，而是尋找一個(gè)高維特征空間和低維特征空間之間的特殊映射，因此在降維后保持了原始數(shù)據(jù)的樣本模式。文獻(xiàn)[8]使用LDA 方法，通過(guò)尋找一個(gè)同時(shí)擁有最小局部散度和最大全局散度的降維投影來(lái)實(shí)現(xiàn)數(shù)據(jù)降維。這些算法都通過(guò)線性轉(zhuǎn)換矩陣建立了高維數(shù)據(jù)和低維數(shù)據(jù)之間的聯(lián)系。文獻(xiàn)[9]提出了一種MDS 方法，將PCA 與局部保留投影相結(jié)合，不再同等處理所有的數(shù)據(jù)點(diǎn)，而是保留了關(guān)鍵數(shù)據(jù)點(diǎn)的局部鄰域結(jié)構(gòu)和全局方差。這一類(lèi)方法雖然并沒(méi)有使用線性轉(zhuǎn)換矩陣，但其本質(zhì)仍是線性的，也均廣泛應(yīng)用在諸多領(lǐng)域。

線性降維方法固然有其局限性，但在線性結(jié)構(gòu)的數(shù)據(jù)集上，依然能夠獲得不錯(cuò)的效果。然而，近年來(lái)互聯(lián)網(wǎng)的發(fā)展使數(shù)據(jù)規(guī)模呈指數(shù)級(jí)增加，復(fù)雜度也日漸提高，很多數(shù)據(jù)并不符合線性的分布規(guī)律，對(duì)于這些數(shù)據(jù)，線性降維方法的實(shí)際效果十分有限。為了彌補(bǔ)這方面的不足，研究者將目光轉(zhuǎn)向了非線性降維方法，其中具有代表性的一類(lèi)是基于循環(huán)迭代求解的方法。這類(lèi)方法大多借助了人工神經(jīng)網(wǎng)絡(luò)（ANN,artificial neural network）的思想，如典型的自組織映射（SOM,self-organizing map）方法。SOM 具有理想的拓?fù)浔４嫣匦裕Ａ袅溯斎肟臻g神經(jīng)元間的距離，被廣泛應(yīng)用于多元數(shù)據(jù)的投影、密度近似等問(wèn)題的研究中。文獻(xiàn)[10]利用現(xiàn)代計(jì)算機(jī)硬件優(yōu)勢(shì)引入了高分辨率SOM 的概念，并證明了其作為集成學(xué)習(xí)模型的預(yù)處理器，在網(wǎng)絡(luò)垃圾郵件、網(wǎng)絡(luò)入侵和惡意軟件檢測(cè)等領(lǐng)域的適用性。另一種典型的循環(huán)迭代降維方法是主曲線（PC,principal curve）方法，文獻(xiàn)[11]對(duì)主曲線方法的理論基礎(chǔ)以及發(fā)展脈絡(luò)進(jìn)行了詳細(xì)的介紹。基于循環(huán)迭代的方法能夠在一定程度上彌補(bǔ)線性降維方法的不足，但仍存在一些問(wèn)題：1) 在迭代求解過(guò)程中容易陷入局部最優(yōu)解；2) 迭代會(huì)造成誤差積累；3)在處理大型樣本集時(shí)計(jì)算代價(jià)過(guò)于高昂。

另一類(lèi)常見(jiàn)的非線性降維方法是基于特征值或廣義特征值的方法，其計(jì)算方式與基于循環(huán)迭代的方法完全不同，主要包括核變換方法和流形學(xué)習(xí)方法。核變換方法構(gòu)建一個(gè)核空間，通過(guò)在空間中尋找源數(shù)據(jù)的一個(gè)線性可分的投影來(lái)實(shí)現(xiàn)非線性數(shù)據(jù)的降維。文獻(xiàn)[12]提出了一種分布式環(huán)境下進(jìn)行核主成分分析（KPCA,kernel PCA）的高效通信算法，結(jié)合子空間嵌入和自適應(yīng)采樣技術(shù)，能夠根據(jù)任意配置的分布式數(shù)據(jù)集計(jì)算出一組全局核主成分，并保證其相對(duì)誤差與特征空間維數(shù)和數(shù)據(jù)點(diǎn)數(shù)目無(wú)關(guān)。文獻(xiàn)[13]提出了一種基于自適應(yīng)局部核Fisher 判別分析（KFDA,kernel Fisher discriminant analysis）的欺騙干擾識(shí)別方法，能夠應(yīng)用核技巧來(lái)減少非線性維數(shù)狀態(tài)，當(dāng)信噪比大于4 dB 時(shí)，該方法在距離門(mén)拖引（RGPO,range gate pull off）欺騙干擾算法下的識(shí)別精度大于90%。然而這類(lèi)算法也有不足之處，核函數(shù)的引入使這類(lèi)方法的計(jì)算通常較復(fù)雜，可能升高數(shù)據(jù)的維度；另外，方法的參數(shù)調(diào)優(yōu)沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)，依賴(lài)專(zhuān)家的先驗(yàn)知識(shí)，普適性較差。

流形學(xué)習(xí)方法由于能夠探索低維流形的內(nèi)在結(jié)構(gòu)，并根據(jù)拓?fù)鋵W(xué)等原理分析其本征維度，因此常被用于處理在高維空間中內(nèi)嵌的非線性低維流形數(shù)據(jù)。不過(guò)流形降維技術(shù)對(duì)于高維幾何數(shù)學(xué)原理具有天然的高依賴(lài)性，這導(dǎo)致其模型建構(gòu)通常十分復(fù)雜，使用成本較高。為解決這一困境，Tenenbaum和Roweis 對(duì)流形學(xué)習(xí)方法進(jìn)行了長(zhǎng)久深入的研究，最終提出了兩大經(jīng)典流形學(xué)習(xí)算法：局部線性嵌入（LLE,locally linear embedding）[14]和等度規(guī)映射（ISOMAP,isomatric mapping）[15]。之后，出現(xiàn)了越來(lái)越多的流形學(xué)習(xí)算法。文獻(xiàn)[16]在拉普拉斯特征映射（LE,Laplacian eigenmap）和John-Lindenstrauss 引理的基礎(chǔ)上，提出了一種稀疏低秩近似等距線性嵌入方法，用于對(duì)高光譜圖像進(jìn)行降維和特征提取。文獻(xiàn)[17]提出了一種基于局部切空間排列（LTSA,local tangent space alignment）的微陣列數(shù)據(jù)降維方法，證明了流形學(xué)習(xí)方法在醫(yī)療領(lǐng)域微陣列數(shù)據(jù)分析上的有效性。文獻(xiàn)[18]提出了一個(gè)統(tǒng)一的圖像復(fù)原?流形近似變換框架，在訓(xùn)練過(guò)程中流形學(xué)習(xí)方法會(huì)導(dǎo)致沿著低維數(shù)據(jù)流形的域變換稀疏的表示，極大地提升了抗噪性并減少了處理痕跡。為解決最大差異展開(kāi)（MVU,maximum variance unfolding）和最小體積嵌入（MVE,minimum volume embedding）等理論模型產(chǎn)生的流形結(jié)構(gòu)質(zhì)量無(wú)法保證的問(wèn)題，文獻(xiàn)[19]提出了一種歐氏距離矩陣的凸優(yōu)化模型，并證明了當(dāng)均勻樣本大小的排序使低秩矩陣的自由度達(dá)到對(duì)數(shù)因子時(shí)，該模型能夠產(chǎn)生高精度的矩陣估計(jì)值。與線性降維方法相比，這些方法通過(guò)保留輸入數(shù)據(jù)的局部結(jié)構(gòu)來(lái)提供更強(qiáng)大的非線性降維性能，為探索非線性分布數(shù)據(jù)的內(nèi)在拓?fù)浣Y(jié)構(gòu)提供了更優(yōu)的路徑。

原始的流形學(xué)習(xí)方法絕大多數(shù)都是無(wú)監(jiān)督學(xué)習(xí)過(guò)程，這導(dǎo)致降維后數(shù)據(jù)的聚類(lèi)程度偏低，不利于后續(xù)的數(shù)據(jù)處理。而有監(jiān)督學(xué)習(xí)則從已知的類(lèi)別信息出發(fā)，更注重降維后數(shù)據(jù)的分類(lèi)效果。因此，近年來(lái)監(jiān)督和半監(jiān)督流形學(xué)習(xí)方法受到了越來(lái)越多的重視，也出現(xiàn)了一些新的方法，其中具有代表性的是對(duì)LPP 方法進(jìn)行監(jiān)督學(xué)習(xí)的改進(jìn)算法——局部判別投影（LDP,locality discriminant projection）算法[20]。文獻(xiàn)[21]提出了有監(jiān)督流形學(xué)習(xí)分類(lèi)器，對(duì)于滿(mǎn)足條件的有監(jiān)督嵌入數(shù)據(jù)，其分類(lèi)誤差隨著訓(xùn)練樣本集的擴(kuò)大而呈指數(shù)級(jí)衰減，證明了以保持?jǐn)?shù)據(jù)低維幾何結(jié)構(gòu)為目標(biāo)的有監(jiān)督非線性嵌入數(shù)據(jù)的可分性。文獻(xiàn)[22]提出了基于圖嵌入概率半監(jiān)督判別分析維數(shù)化簡(jiǎn)的早期故障辨識(shí)方法，在利用局部幾何結(jié)構(gòu)搜索分類(lèi)的最優(yōu)映射子空間的同時(shí)，半監(jiān)督的訓(xùn)練方式還能使其充分利用原始數(shù)據(jù)的類(lèi)別信息作為參考，因此即使在規(guī)模較小、數(shù)據(jù)量不充分的情況下依然能夠發(fā)揮一定的作用。上述成果都對(duì)流形學(xué)習(xí)方法的有監(jiān)督改良起到了重要的推進(jìn)作用，但從領(lǐng)域整體發(fā)展進(jìn)程來(lái)看，對(duì)于有監(jiān)督流形學(xué)習(xí)方法的研究仍處于起步階段，依然存在聚類(lèi)效果不足、效率過(guò)低的缺陷。而在網(wǎng)絡(luò)安全數(shù)據(jù)分析領(lǐng)域，由于數(shù)據(jù)集規(guī)模大、維度高、樣本稀疏的特點(diǎn)，尤其看重降維后數(shù)據(jù)的聚類(lèi)效果，因此目前的算法無(wú)法較好地滿(mǎn)足需求。為解決上述問(wèn)題，本文對(duì)有監(jiān)督流形學(xué)習(xí)降維算法進(jìn)行了更深入的研究，將有監(jiān)督學(xué)習(xí)和判別投影算法相結(jié)合，提出了一種有監(jiān)督的判別投影降維算法。

3 有監(jiān)督判別投影的流形學(xué)習(xí)降維算法

為解決上述問(wèn)題，使流形學(xué)習(xí)降維方法更加貼合網(wǎng)絡(luò)安全數(shù)據(jù)處理需求，本節(jié)基于原始數(shù)據(jù)類(lèi)別信息，對(duì)無(wú)監(jiān)督判別投影方法進(jìn)行改造，提出了一種適用于網(wǎng)絡(luò)安全數(shù)據(jù)的有監(jiān)督判別投影降維算法（簡(jiǎn)稱(chēng)為SDP 算法）。

3.1 有監(jiān)督判別矩陣的建立

大部分經(jīng)典的流形學(xué)習(xí)方法，如LE、LDP 等，在建立近鄰圖時(shí)權(quán)值只能設(shè)置為0/1 或熱核函數(shù)值，但是這些權(quán)值并不能較好地體現(xiàn)數(shù)據(jù)的分類(lèi)信息。SDP 算法在建立近鄰圖時(shí)，結(jié)合原始數(shù)據(jù)的類(lèi)別信息建立有監(jiān)督判別矩陣，能夠更好地體現(xiàn)樣本數(shù)據(jù)的類(lèi)別特征。

有監(jiān)督判別矩陣方法的具體分析過(guò)程如下。

給定m個(gè)訓(xùn)練樣本x1,x2,x3,…,xm，首先根據(jù)數(shù)據(jù)集上高維空間數(shù)據(jù)的樣本點(diǎn)的局部近鄰關(guān)系，建立近鄰矩陣H，如式(1)所示。

其中，i∈Ns(j)且j∈Ns(i)代表樣本xi是樣本xj的近鄰且樣本xj是樣本xi的近鄰。

對(duì)于近鄰矩陣H的任意元素hi,j，當(dāng)hij=0 時(shí)，說(shuō)明xi與xj為近鄰關(guān)系；當(dāng)hi,j=1 時(shí)，說(shuō)明xi與xj為非近鄰關(guān)系。由于任意元素為0 或1 時(shí)，對(duì)于數(shù)據(jù)分類(lèi)而言沒(méi)有判別性，因而利用數(shù)據(jù)集的類(lèi)別標(biāo)簽信息，并結(jié)合近鄰矩陣H的近鄰關(guān)系，變流形無(wú)監(jiān)督學(xué)習(xí)為有監(jiān)督，并構(gòu)造有監(jiān)督判別矩陣S，如式(2)所示。

其中，‖xi?xj‖ 是兩點(diǎn)之間的歐氏距離，p是一個(gè)可以調(diào)節(jié)的常數(shù)。

3.2 降維算法原理

SDP 算法能夠有效消除原始數(shù)據(jù)產(chǎn)生的冗余干擾，縮減網(wǎng)絡(luò)安全數(shù)據(jù)的規(guī)模，使降維投影后同類(lèi)的數(shù)據(jù)距離更近，表現(xiàn)出明顯的集簇效果；異類(lèi)的簇之間彼此遠(yuǎn)離，界限較清晰。這一現(xiàn)象能夠顯著降低后續(xù)數(shù)據(jù)處理工作的難度。具體降維方法如下。

1) 根據(jù)近鄰點(diǎn)數(shù)量K建立局部近鄰圖，利用有監(jiān)督判別矩陣對(duì)局部近鄰圖的邊進(jìn)行賦值從而建立近鄰圖，再根據(jù)近鄰圖構(gòu)建局部散度矩陣SL，如式(3)所示。

其中，L為拉普拉斯矩陣，L=D?H，矩陣D如式(4)所示。

2) 構(gòu)建全局散度矩陣SN，如式(5)所示。

3) 為了尋找一個(gè)變換矩陣A=[a1,a2,…,ar]，使經(jīng)過(guò)判別向量a轉(zhuǎn)化后的低維投影子空間能夠同時(shí)具有最大全局散度矩陣SN和最小局部散度矩陣SL，建立一個(gè)關(guān)于A的函數(shù)模型J(A)，如式(6)所示。

在建立函數(shù)模型J(A)的基礎(chǔ)上，增加正交化約束，求解正交基向量a1,a2,…,ar，并構(gòu)建約束目標(biāo)函數(shù)模型。

4) 計(jì)算正交基函數(shù)。正交基為A=[a1,a2,…,ar]，令A(yù)r?1=[a1,a2,…,ar?1]，根據(jù)廣義特征方程XLXTa=λXLXTa，通過(guò)求解使式(7)取得最小值的向量a1，計(jì)算得到正交矩陣A的一個(gè)特征向量為

5) 求解在約束條件下使式(8)取得最小值的向量am，得到第m個(gè)特征值對(duì)應(yīng)的特征向量為

其中，I為單位矩陣。

通過(guò)求解以上方程獲得正交基向量a1,a2,…,am。

6) 在線性投影矩陣滿(mǎn)足正交化的約束下，構(gòu)建約束目標(biāo)函數(shù)模型為

根據(jù)以上步驟構(gòu)建約束目標(biāo)函數(shù)模型J(A)，利用特征分解獲得約束目標(biāo)函數(shù)的解，并輸出高維數(shù)據(jù)在低維空間的投影。

以上模型的構(gòu)建方式與傳統(tǒng)流形算法LPP 以及UDP 對(duì)于降維過(guò)程中鄰接矩陣權(quán)值的處理方式不同，但其模型數(shù)學(xué)原理基本一致，在實(shí)際計(jì)算過(guò)程中通常使用拉格朗日乘數(shù)法構(gòu)建輔助函數(shù)以加快計(jì)算速度，因此計(jì)算復(fù)雜度上，SDP 算法與經(jīng)典流形學(xué)習(xí)算法并沒(méi)有明顯差異。

3.3 降維算法流程

在3.2 節(jié)提出的有監(jiān)督判別投影算法中，首先根據(jù)輸入樣本點(diǎn)的近鄰關(guān)系，在考慮類(lèi)別信息的基礎(chǔ)上構(gòu)建有監(jiān)督判別矩陣，增加條件正交化約束，并尋找一個(gè)同時(shí)具有最大全局散度矩陣和最小局部散度矩陣的低維投影子空間，經(jīng)過(guò)有監(jiān)督判別降維后，數(shù)據(jù)的特征維度得到縮減，且異類(lèi)數(shù)據(jù)之間的界限明顯清晰。SDP 算法的實(shí)現(xiàn)過(guò)程如算法1 所示。

算法1SDP 算法

輸入高維數(shù)據(jù)x=[x1,x2,…,xm]∈RD×n，類(lèi)別信息C=[C1,C2,…,Cn]

輸出線性變換A∈RD×d和低維投影Y=ATX∈RD×d

步驟1建立近鄰圖。

步驟1.1根據(jù)近鄰點(diǎn)數(shù)量k，建立局部近鄰圖。

步驟1.2結(jié)合局部近鄰圖的近鄰關(guān)系，利用有監(jiān)督判別矩陣S計(jì)算xi與xj間的權(quán)值，并使用權(quán)值對(duì)近鄰圖的邊進(jìn)行賦值。

步驟2特征分解。

步驟2.1根據(jù)近鄰圖，計(jì)算局部散度矩陣SL。

步驟2.2根據(jù)近鄰圖，求得全局散度矩陣SN。

步驟2.3根據(jù)所計(jì)算的局部散度矩陣和全局散度矩陣，增加正交化約束，構(gòu)建約束目標(biāo)函數(shù)模型。

步驟2.4利用特征分解求得約束目標(biāo)函數(shù)的解。

步驟3低維投影。輸出高維數(shù)據(jù)在低維空間的投影Yt=ATXt，其中，下角標(biāo)t 表示低維空間。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境設(shè)置

降維算法的性能優(yōu)劣主要體現(xiàn)在其降維的效果和運(yùn)行算法所消耗的時(shí)間方面。研究者普遍認(rèn)為，在有效降低數(shù)據(jù)維度的前提下，如果經(jīng)過(guò)某種降維方法處理后的數(shù)據(jù)能夠保留更多的原有信息，并且產(chǎn)生更明顯的聚類(lèi)效果，那么就可以說(shuō)這種降維方法的效果是更優(yōu)秀的。而時(shí)間復(fù)雜度同樣是十分重要的評(píng)估標(biāo)準(zhǔn)，消耗時(shí)間過(guò)多的方法不適用于現(xiàn)實(shí)的網(wǎng)絡(luò)安全實(shí)踐。因此，本節(jié)將圍繞這2 個(gè)評(píng)價(jià)指標(biāo)，對(duì)SDP 算法和其他經(jīng)典的數(shù)據(jù)降維算法進(jìn)行對(duì)比實(shí)驗(yàn)，以評(píng)估SDP 算法的有效性。

本文中的實(shí)驗(yàn)依托于Hadoop 云環(huán)境，環(huán)境結(jié)構(gòu)如圖1 所示。

圖1 實(shí)驗(yàn)環(huán)境結(jié)構(gòu)

實(shí)驗(yàn)采用NSL KDD 異常入侵檢測(cè)數(shù)據(jù)集[23]，該數(shù)據(jù)集于2009 年由新布倫瑞克大學(xué)提出。與其前身KDD Cup 99 數(shù)據(jù)集相比，該數(shù)據(jù)集無(wú)冗余，無(wú)重復(fù)記錄，復(fù)雜度更低。NSL KDD 是關(guān)于網(wǎng)絡(luò)事件的公共數(shù)據(jù)集，包含一組完整的被標(biāo)記入侵事件，其實(shí)例和特征數(shù)量非常龐大，提供了事件分布和特性之間的依賴(lài)關(guān)系，這些特點(diǎn)使它更適合作為網(wǎng)絡(luò)安全分析研究的基準(zhǔn)。NSL KDD 的訓(xùn)練集包含21 種不同的網(wǎng)絡(luò)攻擊類(lèi)型，而測(cè)試集在此基礎(chǔ)上額外添加了17 種新的攻擊類(lèi)型。這些攻擊大體上可以分為4 類(lèi)：拒絕服務(wù)器（DoS,denial of service）、PROBE、R2L（remote-to-login）以及U2R（user-to-root），而非攻擊類(lèi)型的正常數(shù)據(jù)被標(biāo)記為Normal。實(shí)驗(yàn)數(shù)據(jù)集類(lèi)別分布如表2 所示。

4.2 對(duì)比實(shí)驗(yàn)

為了對(duì)于SDP 算法的性能進(jìn)行充分測(cè)試，本文選擇了降維算法PCA、LE、LDP 作為對(duì)照組。其中PCA 和LDP 分別為線性降維算法和有監(jiān)督流形學(xué)習(xí)算法中最具代表性的算法之一；LE 的最終目的是使高維空間中鄰近的點(diǎn)在低維嵌入中依然鄰近，這一思想與SDP 算法較相近，因此作為無(wú)監(jiān)督流形學(xué)習(xí)算法的代表。實(shí)驗(yàn)將從降維效果、時(shí)間消耗和綜合性能3 個(gè)方面來(lái)分析SDP 算法的性能。

表1 實(shí)驗(yàn)數(shù)據(jù)集類(lèi)別分布

1) 降維效果分析

分別使用PCA、LE、LDP 和SDP 算法對(duì)NSL KDD 數(shù)據(jù)集進(jìn)行降維，降維后的數(shù)據(jù)可視化投影如圖2 所示。由圖2 可以看出，通過(guò)PCA 降維后的數(shù)據(jù)，不同類(lèi)之間混雜在一起，結(jié)構(gòu)較混亂，這是由于線性降維算法自身的缺陷會(huì)導(dǎo)致處理后的數(shù)據(jù)維度丟失，拓?fù)浣Y(jié)構(gòu)遭到破壞。LE 降維后的數(shù)據(jù)結(jié)構(gòu)較分明，但大量邊緣數(shù)據(jù)混淆，部分區(qū)域數(shù)據(jù)十分密集。LDP 降維后的數(shù)據(jù)整體結(jié)構(gòu)清晰，不同類(lèi)別區(qū)分更加明顯，不過(guò)數(shù)據(jù)分布仍顯分散，聚類(lèi)程度較低。經(jīng)SDP 算法降維后的數(shù)據(jù)，不同類(lèi)別之間輪廓清晰，視覺(jué)效果上明顯優(yōu)于另外3 種算法。這是由于LDP 雖然與SDP 算法同為有監(jiān)督降維算法，但此類(lèi)算法在構(gòu)建近鄰圖時(shí)僅使用了熱核函數(shù)等手段作為聚類(lèi)的權(quán)值，這種方法對(duì)于樣本類(lèi)間距的描述能力不足。SDP 算法則構(gòu)建了完整的樣本距離判別矩陣，因此降維后的類(lèi)別間距更加精準(zhǔn)、清晰。

圖2 不同算法降維數(shù)據(jù)投影

為了更具體化地證明所觀察到的結(jié)論，本文引入“輪廓系數(shù)”的概念對(duì)4 種算法的降維效果進(jìn)行評(píng)估。輪廓系數(shù)是聚類(lèi)效果好壞的一種評(píng)價(jià)方式，由Rousseeuw 于1986 年提出。對(duì)于已經(jīng)處理過(guò)的數(shù)據(jù)，其輪廓系數(shù)可以表示為

其中，a(ix)為樣本點(diǎn)xi到所有它屬于的簇中其他點(diǎn)的平均距離；b(xi)為樣本點(diǎn)xi到與它相距最近的一個(gè)異類(lèi)簇內(nèi)的所有點(diǎn)的平均距離，具體到本文的二分類(lèi)聚類(lèi)問(wèn)題，則是樣本點(diǎn)xi到數(shù)據(jù)集中所有與其異類(lèi)的樣本點(diǎn)的平均距離；數(shù)據(jù)集整體的輪廓系數(shù)S為所有樣本輪廓系數(shù)的均值，即

可以看出，輪廓系數(shù)S的值為[?1,1]，越接近1 則證明數(shù)據(jù)的聚類(lèi)程度越高。

分別對(duì)上述4 種算法降維后的數(shù)據(jù)計(jì)算輪廓系數(shù)，結(jié)果如圖3 所示。

由圖3 可知，計(jì)算得出的輪廓系數(shù)基本和上文對(duì)于數(shù)據(jù)的視覺(jué)觀測(cè)保持一致，其中線性算法PCA的效果最差，僅為0.007 7，這表明經(jīng)其降維后的數(shù)據(jù)基本丟失了原有的類(lèi)別信息。LE 和LDP 雖同為流形學(xué)習(xí)算法，但由于LE 為無(wú)監(jiān)督算法，LDP 為有監(jiān)督算法，因此輪廓系數(shù)相差較大，LE 的輪廓系數(shù)僅為0.016 3，而LDP 的輪廓系數(shù)卻達(dá)到了0.093 2。改良后的SDP 算法在降維后的數(shù)據(jù)類(lèi)別信息完整度方面不僅遠(yuǎn)超過(guò)PCA 和LE，和同為有監(jiān)督算法的LDP 相比也表現(xiàn)出了一定的優(yōu)勢(shì)，其輪廓系數(shù)達(dá)到了0.140 8，證明了SDP 在降維后數(shù)據(jù)聚類(lèi)效果的優(yōu)勢(shì)。

圖3 4 種算法降維數(shù)據(jù)的輪廓系數(shù)

為了測(cè)試SDP 算法在網(wǎng)絡(luò)安全分析領(lǐng)域的適用性，本文針對(duì)NSL KDD 中4 種不同的攻擊方式：DoS、PROBE、U2R 和R2L，分別在這些訓(xùn)練集上使用SDP 算法對(duì)其降維，實(shí)驗(yàn)結(jié)果如圖4 所示。

從圖4 可以看出，對(duì)于4 種攻擊方式數(shù)據(jù)，SDP算法的降維效果都較理想。降維后的數(shù)據(jù)基本保留了原本的類(lèi)別屬性，正常流量數(shù)據(jù)和異常流量數(shù)據(jù)在視覺(jué)效果上有著顯著的區(qū)分，且異常數(shù)據(jù)的聚類(lèi)效果明顯。由此可見(jiàn)，SDP 算法在網(wǎng)絡(luò)安全分析領(lǐng)域具有較強(qiáng)的適用性。

圖4 不同攻擊數(shù)據(jù)集的數(shù)據(jù)降維投影

2) 時(shí)間消耗分析

SDP 算法為了強(qiáng)化降維的效果，使用了有監(jiān)督的學(xué)習(xí)方式，上文的實(shí)驗(yàn)數(shù)據(jù)表明這一改動(dòng)是成功的。但在實(shí)際的網(wǎng)絡(luò)安全分析實(shí)踐中，算法的效率也同樣重要，如果這項(xiàng)改動(dòng)帶來(lái)了不可接受的時(shí)間消耗，那么也無(wú)法稱(chēng)之為成功的降維算法。因此，本節(jié)對(duì)SDP 算法的時(shí)間消耗進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)比算法仍然選擇PCA、LE 和LDP。為了保證數(shù)據(jù)的準(zhǔn)確性，降維時(shí)間測(cè)試設(shè)置了7 組不同數(shù)據(jù)規(guī)模的對(duì)照組，其樣本數(shù)分別為300、600、1 200、2 400、4 800、9 600、19 200 測(cè)試，以驗(yàn)證SDP 算法在不同規(guī)模的安全數(shù)據(jù)集下的時(shí)間消耗量。實(shí)驗(yàn)結(jié)果如表2 和圖5 所示。

圖5 4 種算法在不同數(shù)據(jù)規(guī)模下的時(shí)間消耗曲線

表2 4 種算法在不同數(shù)據(jù)規(guī)模下的時(shí)間消耗

通過(guò)分析數(shù)據(jù)可以得知，與線性算法相比，流形學(xué)習(xí)算法消耗的時(shí)間明顯更多，這是由于流形學(xué)習(xí)算法為非線性算法，需要尋找高維空間的局部結(jié)構(gòu)，并利用K 近鄰運(yùn)算進(jìn)行判斷，每一步都會(huì)顯著增加算法的時(shí)間復(fù)雜度，但這也讓流形學(xué)習(xí)算法能提供線性算法無(wú)法比擬的降維效果。在3 種流形學(xué)習(xí)算法中，LDP 雖然在降維效果上優(yōu)于LE，但消耗時(shí)間卻是LE 的5～10 倍。SDP 在降維效果上明顯領(lǐng)先于其他算法，但消耗時(shí)間與LDP 基本持平，而且在較大規(guī)模的數(shù)據(jù)集上，消耗時(shí)間甚至少于LDP。出現(xiàn)這種現(xiàn)象是由于SDP 算法在定義鄰接圖權(quán)值時(shí)，采用的有監(jiān)督判別矩陣計(jì)算方式較穩(wěn)定，只需在求解降維變換函數(shù)之前計(jì)算一次即可滿(mǎn)足后續(xù)使用；LDP 在求解過(guò)程中使用的熱核函數(shù)計(jì)算方式雖然在單項(xiàng)復(fù)雜度上基本與SDP 算法持平，但在算法運(yùn)行過(guò)程中可能會(huì)出現(xiàn)變化，導(dǎo)致需要多次重復(fù)計(jì)算，因此計(jì)算量偏高。

這項(xiàng)實(shí)驗(yàn)表明，SDP 算法在時(shí)間消耗方面并沒(méi)有超出原有流形學(xué)習(xí)算法的范疇，并且在某些特定的情況下體現(xiàn)了一定的優(yōu)勢(shì)。

3) 綜合性能分析

為了綜合考量上述測(cè)試的結(jié)果，本文定義了綜合性能指數(shù)P作為評(píng)估降維算法綜合性能（效費(fèi)比）的標(biāo)準(zhǔn)，進(jìn)一步驗(yàn)證SDP 算法在降維效果和時(shí)間消耗2 個(gè)方面的表現(xiàn)，即驗(yàn)證算法能否在可接受的時(shí)間消耗內(nèi)取得性能上的優(yōu)勢(shì)。P的定義為

其中，n為測(cè)試數(shù)據(jù)的規(guī)模，T為算法運(yùn)行的時(shí)間消耗。結(jié)合上文中3 種流形學(xué)習(xí)算法的輪廓系數(shù)和時(shí)間消耗數(shù)據(jù)，得到的綜合性能指數(shù)如表3 所示。

表3 3 種流形學(xué)習(xí)算法的綜合性能指數(shù)

實(shí)驗(yàn)結(jié)果如圖6 所示。實(shí)驗(yàn)結(jié)果表明，與LE相比，SDP 算法雖然在時(shí)間開(kāi)銷(xiāo)上占據(jù)劣勢(shì)，但由于在以輪廓系數(shù)為代表的降維效果上顯著優(yōu)于LE，因此依然能夠保持領(lǐng)先地位。在與LDP 的對(duì)比中，SDP 算法不僅降維效果較優(yōu)，而且在小規(guī)模數(shù)據(jù)集上的時(shí)間開(kāi)銷(xiāo)也和LSP 基本保持一致，甚至在較大規(guī)模數(shù)據(jù)集上的時(shí)間開(kāi)銷(xiāo)小于LSP，因此在綜合性能上取得了穩(wěn)定的優(yōu)勢(shì)。

圖6 3 種流形學(xué)習(xí)算法的綜合性能指數(shù)曲線

5 結(jié)束語(yǔ)

本文針對(duì)網(wǎng)絡(luò)安全數(shù)據(jù)降維領(lǐng)域的算法聚類(lèi)效果差、效率低的問(wèn)題，在傳統(tǒng)數(shù)據(jù)降維技術(shù)的基礎(chǔ)上，提出了一種有監(jiān)督判別投影的流形學(xué)習(xí)降維算法——SDP 算法。SDP 算法利用一個(gè)有監(jiān)督判別矩陣，找到同時(shí)具有最大全局散度矩陣和最小局部散度矩陣的低維投影子空間，最終實(shí)現(xiàn)數(shù)據(jù)的降維。實(shí)驗(yàn)證明，SDP 算法僅需消耗與傳統(tǒng)流形學(xué)習(xí)算法接近的時(shí)間，但降維后數(shù)據(jù)的聚類(lèi)效果顯著優(yōu)于線性降維算法和其他流形學(xué)習(xí)算法，且對(duì)于網(wǎng)絡(luò)安全數(shù)據(jù)有較強(qiáng)的適應(yīng)性，因此很適合被用于網(wǎng)絡(luò)安全分析領(lǐng)域的數(shù)據(jù)降維工作中。

由于篇幅和時(shí)間的限制，本文僅討論了如何在降維中保留更多的原始數(shù)據(jù)類(lèi)別信息，未能深入研究如何進(jìn)一步提高算法的效率，也沒(méi)有涉及如何進(jìn)一步提高后續(xù)的網(wǎng)絡(luò)入侵檢測(cè)精度。這些問(wèn)題都有待于在未來(lái)工作中探索。