基于檢測(cè)器集層次聚類的否定選擇算法

王韞燁,孔 珊

(鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院,鄭州 450044)

0 概述

異常檢測(cè)是在網(wǎng)絡(luò)和大數(shù)據(jù)安全分析中廣泛使用的關(guān)鍵技術(shù)。由于異常檢測(cè)系統(tǒng)與人體免疫系統(tǒng)有著高度的相似性,基于免疫機(jī)制的否定選擇算法在異常檢測(cè)中得到了深入應(yīng)用并取得良好的效果[1],成為解決異常檢測(cè)問題的主要算法之一。檢測(cè)器的生成是否定選擇算法中的重點(diǎn)部分,對(duì)檢測(cè)效率和準(zhǔn)確度具有重要影響[2]。因此,設(shè)計(jì)高效的檢測(cè)器生成算法是否定選擇算法研究的關(guān)鍵和熱點(diǎn)[3]。

否定選擇算法一般用字符串(含二進(jìn)制字符串)和實(shí)值表示[4]。實(shí)值否定選擇算法將自體與檢測(cè)器的各項(xiàng)屬性值表示為n維[0,1]實(shí)數(shù)范圍([0,1]n)內(nèi)的超立方體,更適合對(duì)現(xiàn)實(shí)問題進(jìn)行描述,因而得到廣泛應(yīng)用[5]。由于半徑固定的實(shí)值否定選擇算法存在許多黑洞區(qū)域無(wú)法被檢測(cè)器覆蓋和檢測(cè),文獻(xiàn)[6]提出V-detector算法,該算法是一種半徑可變的實(shí)值否定選擇算法,可以顯著提高算法的檢測(cè)率,為實(shí)值否定選擇算法中最具代表性的算法,眾多后續(xù)研究與應(yīng)用都基于該算法展開[7-16]。

文獻(xiàn)[7]提出改進(jìn)的否定選擇算法,該算法增加了檢測(cè)器的覆蓋半徑。文獻(xiàn)[8]通過二次否定過程提高了檢測(cè)器生成性能。文獻(xiàn)[9]基于自體分布由遠(yuǎn)及近分層次產(chǎn)生檢測(cè)器,優(yōu)化了否定選擇算法的性能。文獻(xiàn)[10]在小型樣本空間中分離自體與非自體空間,提高了檢測(cè)器的檢測(cè)效率。文獻(xiàn)[11]通過分析抗原空間的密度,提升了實(shí)值否定選擇算法的性能。文獻(xiàn)[12]采用基于子空間密度搜索的改進(jìn)否定選擇算法提高了空間覆蓋率。文獻(xiàn)[13]對(duì)否定選擇算法性能參數(shù)進(jìn)行分析，指出各參數(shù)對(duì)檢測(cè)性能的影響。文獻(xiàn)[14]將主動(dòng)學(xué)習(xí)和否定選擇算法進(jìn)行集成后應(yīng)用于垃圾郵件分類，增加了垃圾郵件分類準(zhǔn)確性。文獻(xiàn)[15]將改進(jìn)的否定選擇算法用于故障檢測(cè)，提升了檢測(cè)率。文獻(xiàn)[16]用否定選擇算法生成測(cè)試數(shù)據(jù)，有效提高了測(cè)試數(shù)據(jù)路徑覆蓋率。

上述否定選擇算法均取得了較好的效果,顯著提高了檢測(cè)器的生成效率。但采用否定選擇算法對(duì)數(shù)據(jù)進(jìn)行異常檢測(cè)時(shí),需要對(duì)所有的檢測(cè)器進(jìn)行距離計(jì)算,這降低了檢測(cè)效率,增加了檢測(cè)時(shí)間,不利于快速檢測(cè)。

本文提出一種基于檢測(cè)器集層次聚類的否定選擇算法,對(duì)檢測(cè)器集進(jìn)行從上到下的層次聚類處理,只計(jì)算待檢測(cè)數(shù)據(jù)與聚類中心檢測(cè)器之間的距離,以減少計(jì)算時(shí)間和能耗,對(duì)未被檢測(cè)器匹配的數(shù)據(jù)進(jìn)行分類,并分別從檢測(cè)率、誤檢率及檢測(cè)時(shí)間等方面將本文否定選擇算法與V-detector算法和免疫實(shí)值否定選擇算法進(jìn)行對(duì)比分析。

1 算法關(guān)鍵技術(shù)

1.1 否定選擇算法的檢測(cè)過程

否定選擇算法的檢測(cè)過程由兩個(gè)階段構(gòu)成:一是訓(xùn)練階段,即檢測(cè)器的生成階段;二是檢測(cè)階段,即將待測(cè)數(shù)據(jù)通過檢測(cè)器按照是否正常進(jìn)行分類的階段[17]。

在檢測(cè)階段,待檢測(cè)數(shù)據(jù)需要與檢測(cè)器進(jìn)行匹配,因此,需要匹配的檢測(cè)器數(shù)量越少,對(duì)數(shù)據(jù)做出異常檢測(cè)的判斷就越快。

V-detector算法及其改進(jìn)算法檢測(cè)階段的過程為[6-11]:對(duì)任一需要檢測(cè)的數(shù)據(jù),計(jì)算其與所有檢測(cè)器的距離,若待檢測(cè)數(shù)據(jù)被任一檢測(cè)器覆蓋,則該待檢測(cè)數(shù)據(jù)被標(biāo)記為異常,否則該待檢測(cè)數(shù)據(jù)被標(biāo)記為正常。對(duì)于n維空間中待檢測(cè)數(shù)據(jù)t=(ct,rt)而言,將其與檢測(cè)器d=(cd,rd)之間距離記為dis=(t,d),其中ct為待檢測(cè)數(shù)據(jù)的中點(diǎn),rt為待檢測(cè)數(shù)據(jù)的半徑,cd為檢測(cè)器的中點(diǎn),rd為檢測(cè)器的半徑。為判斷待檢測(cè)數(shù)據(jù)是否異常,需要計(jì)算各待檢測(cè)數(shù)據(jù)ti(ti∈t)與所有的檢測(cè)器di(di∈d)之間的距離,其計(jì)算公式如下:

dis(ct,cd)=

(1)

若dis(ct,cd)

由否定選擇算法的檢測(cè)過程可以看出,該過程計(jì)算會(huì)耗費(fèi)較多的計(jì)算時(shí)間,這不利于該算法的廣泛應(yīng)用。

1.2 改進(jìn)的否定選擇算法

本文在上述否定選擇算法的基礎(chǔ)上進(jìn)行改進(jìn),改進(jìn)后算法的主要思想為:對(duì)檢測(cè)器集D進(jìn)行從上到下的層次聚類處理,只計(jì)算待檢測(cè)數(shù)據(jù)t與聚類中心檢測(cè)器C之間的距離,不再計(jì)算待檢測(cè)數(shù)據(jù)t與所有聚類成員檢測(cè)器集D之間的距離,減少了計(jì)算時(shí)間和能耗。

1.3 檢測(cè)器集的層次聚類

本文設(shè)計(jì)的檢測(cè)器層次聚類過程為:

1)對(duì)否定選擇過程生成的成熟檢測(cè)器集D進(jìn)行層次聚類處理,每層生成的聚類中心構(gòu)成新的檢測(cè)器集C。

2)對(duì)于每個(gè)檢測(cè)集T中的數(shù)據(jù)t=(ct,rt),分別計(jì)算其與檢測(cè)器集C中每個(gè)檢測(cè)器Ci的距離,從而判斷該待檢測(cè)數(shù)據(jù)是否正常并進(jìn)行分類。其中,ct為待檢測(cè)數(shù)據(jù)的坐標(biāo),cc為檢測(cè)器Ci的坐標(biāo),rci為檢測(cè)器Ci的半徑。具體的判斷方法為:若dis(ct,cc)

在二維實(shí)值空間[0,1]2進(jìn)行仿真驗(yàn)證如下:

由上述可見,層次聚類方法中聚類半徑逐漸減半,從而使得檢測(cè)更精確,在減少檢測(cè)時(shí)間的同時(shí)提高了檢測(cè)率。

1.4 孔洞數(shù)據(jù)的判定

在二維實(shí)值空間[0,1]2中,孔洞區(qū)是指沒有被任何檢測(cè)器覆蓋的檢測(cè)區(qū)域[18]。對(duì)于處于孔洞區(qū)的待檢測(cè)(分類)數(shù)據(jù),可以通過否定選擇算法將其分類為正常數(shù)據(jù)。然而未被檢測(cè)器覆蓋的區(qū)域有可能存在異常數(shù)據(jù)并導(dǎo)致分類錯(cuò)誤,造成算法誤檢率升高[19]。在改進(jìn)后的否定選擇算法中,不再將待檢測(cè)數(shù)據(jù)簡(jiǎn)單標(biāo)識(shí)為正常數(shù)據(jù),其性質(zhì)由檢測(cè)器與自體集的位置共同定量決定,即待檢測(cè)數(shù)據(jù)的異常性由該數(shù)據(jù)到最近檢測(cè)器的歐氏距離和最近自體的歐氏距離共同判定,分別表示為:

Dis1=min dis(t,ci),ci∈C

(2)

Dis2=min dis(t,si),si∈S

(3)

其中,Dis1為待分類數(shù)據(jù)t到檢測(cè)器集合C中所有檢測(cè)器ci的最短距離,Dis2為待分類數(shù)據(jù)t到自體集合S中所有自體si的最短距離。若Dis1>aDis2,則該待檢測(cè)數(shù)據(jù)為正常數(shù)據(jù),否則為異常數(shù)據(jù)。大量實(shí)驗(yàn)研究結(jié)果表明,a的取值為自體半徑rs的20倍[18]。

2 算法流程

改進(jìn)后否定選擇算法的檢驗(yàn)過程分為檢測(cè)器生成階段與異常檢測(cè)階段,該算法的基本步驟如下:

1)使用文獻(xiàn)[6]中V-detector算法生成成熟檢測(cè)器集D。

2)對(duì)檢測(cè)器集D進(jìn)行層次聚類處理,得到檢測(cè)器集C。

3)輸入數(shù)據(jù)集T進(jìn)行異常檢測(cè)(計(jì)算T中數(shù)據(jù)和檢測(cè)器集C中檢測(cè)器之間的距離。

4)進(jìn)行異常檢測(cè)判斷:如果被檢測(cè)數(shù)據(jù)與檢測(cè)器集C中的任一檢測(cè)器匹配,則為異常數(shù)據(jù),直接進(jìn)行第6步;如果被檢測(cè)數(shù)據(jù)未與檢測(cè)器集C中的任一檢測(cè)器匹配,進(jìn)行第5步。

5)如果被檢測(cè)數(shù)據(jù)未與檢測(cè)器集C中的任一檢測(cè)器匹配,則認(rèn)為其處于孔洞區(qū),需進(jìn)一步測(cè)試以判定其是否為正常數(shù)據(jù)并進(jìn)行標(biāo)識(shí)。

6)算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

在Windows 10環(huán)境下,使用JAVA對(duì)本算法進(jìn)行編程實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)集為廣泛使用的人造二維數(shù)據(jù)集,對(duì)實(shí)驗(yàn)結(jié)果以五角星形自體集為例進(jìn)行分析,并與經(jīng)典的V-detector算法[6]和免疫實(shí)值否定選擇算法[9]結(jié)果進(jìn)行對(duì)比。參數(shù)取值與所對(duì)比的文獻(xiàn)保持一致:數(shù)據(jù)取自二維實(shí)值空間[0,1]2,訓(xùn)練數(shù)據(jù)集容量為1 000個(gè),測(cè)試數(shù)據(jù)集容量為1 000個(gè),目標(biāo)覆蓋率分別為90%、95%和99%。分別從檢測(cè)率、誤檢率及檢測(cè)時(shí)間三方面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

選擇實(shí)驗(yàn)?zāi)繕?biāo)覆蓋率為95%,自體半徑的取值區(qū)間為[0.01,0.30](每隔0.05取一個(gè)值),每個(gè)自體半徑進(jìn)行100次實(shí)驗(yàn)并取結(jié)果的平均值。

由圖1可以看出,3種不同算法的檢測(cè)率均隨著自體半徑的增大而降低,本文否定選擇算法的檢測(cè)率降幅比其他兩種算法更小。這是因?yàn)榭锥磪^(qū)數(shù)據(jù)隨著自體半徑的增大而增加,本文否定選擇算法由于對(duì)孔洞區(qū)數(shù)據(jù)的異常性進(jìn)行了判定,提高了孔洞區(qū)數(shù)據(jù)檢測(cè)的準(zhǔn)確性,從而提升了算法的檢測(cè)率。

圖1 檢測(cè)率隨自體半徑變化曲線

由圖2可以看出,3種不同算法的誤檢率均隨著自體半徑的增大而降低,本文否定選擇算法誤檢率的降幅比其他兩種算法的更大。這是因?yàn)榭锥磪^(qū)數(shù)據(jù)隨著自體半徑的增大而增加,在V-detector算法和免疫實(shí)值否定選擇算法中,孔洞區(qū)數(shù)據(jù)(部分?jǐn)?shù)據(jù)可能為異常數(shù)據(jù))全部被定義為正常數(shù)據(jù),而本文否定選擇算法對(duì)孔洞區(qū)數(shù)據(jù)異常性進(jìn)行了判定,有效降低了算法的誤檢率。

圖2 誤檢率隨自體半徑變化曲線

由圖1和圖2可知,檢測(cè)性能與自體半徑密切相關(guān),隨著自體半徑的增大,算法的檢測(cè)率和誤檢率均降低。因此,需根據(jù)實(shí)際問題選擇適合的自體半徑來(lái)調(diào)整算法的檢測(cè)性能。

由圖3和圖4可以看出,當(dāng)自體半徑為0.2時(shí),3種算法的檢測(cè)率和誤檢率均隨著目標(biāo)覆蓋率的增大而增加;和其他兩種算法相比,本文否定選擇算法的檢測(cè)率更高且誤檢率更低;當(dāng)目標(biāo)覆蓋率為99%時(shí),3種算法的檢測(cè)性能較接近,這是因?yàn)楫?dāng)目標(biāo)覆蓋率為99%時(shí),所需成熟檢測(cè)器的數(shù)量顯著增加,對(duì)非自體區(qū)域的覆蓋增大,處于孔洞區(qū)域的數(shù)據(jù)減少,此時(shí)本文否定選擇算法的優(yōu)勢(shì)不明顯。

圖3 檢測(cè)率隨期望覆蓋率變化曲線

圖4 誤檢率隨期望覆蓋率變化曲線

由表1可以看出,V-Detector算法在采用不同形狀檢測(cè)器時(shí)檢測(cè)時(shí)間均最長(zhǎng),免疫實(shí)值否定選擇算法的次之,本文、否定選擇算法最短;當(dāng)檢測(cè)器形狀為環(huán)形時(shí),本文否定選擇算法的檢測(cè)時(shí)間最短。這是因?yàn)閂-Detector算法由于需要計(jì)算各待檢測(cè)數(shù)據(jù)與檢測(cè)器集D中所有檢測(cè)器之間的距離以判斷數(shù)據(jù)是否異常,因而所需的檢測(cè)時(shí)間最長(zhǎng)。

表1 不同算法的檢測(cè)時(shí)間結(jié)果對(duì)比

免疫實(shí)值否定選擇算法采用了檢測(cè)器分級(jí)生成方式,在同樣的檢測(cè)率下,需要的檢測(cè)器數(shù)量減少,因而所需的檢測(cè)時(shí)間比V-Detector算法要短。本文否定選擇算法由于用聚類中心檢測(cè)器C代替檢測(cè)器集D進(jìn)行距離計(jì)算(C的數(shù)量遠(yuǎn)小于D),因而所需的檢測(cè)時(shí)間最短。圓形檢測(cè)器與環(huán)形自體集的形狀較相似,匹配度較高,此時(shí)孔洞區(qū)待檢測(cè)數(shù)據(jù)較少,因而檢測(cè)時(shí)間最短。

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

為提高異常檢測(cè)的效率,本文提出一種基于檢測(cè)器集層次聚類的否定選擇算法,通過對(duì)檢測(cè)器集進(jìn)行層次聚類,以聚類中心檢測(cè)器代替初始檢測(cè)器集進(jìn)行距離計(jì)算,減少計(jì)算時(shí)間并對(duì)未被檢測(cè)器覆蓋的孔洞區(qū)域?qū)傩赃M(jìn)行進(jìn)一步判斷。實(shí)驗(yàn)結(jié)果表明,本文否定選擇算法較V-detector算法和免疫實(shí)值否定選擇算法所需時(shí)間大幅減少,檢測(cè)效率提高且誤檢率降低。下一步將在本文算法的基礎(chǔ)上對(duì)聚類中心集和檢測(cè)器集的數(shù)量關(guān)系進(jìn)行研究。