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

王韞燁,孔 珊

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

0 概述

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

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

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

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

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

1 算法關鍵技術

1.1 否定選擇算法的檢測過程

否定選擇算法的檢測過程由兩個階段構成:一是訓練階段,即檢測器的生成階段;二是檢測階段,即將待測數據通過檢測器按照是否正常進行分類的階段[17]。

在檢測階段,待檢測數據需要與檢測器進行匹配,因此,需要匹配的檢測器數量越少,對數據做出異常檢測的判斷就越快。

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

dis(ct,cd)=

(1)

若dis(ct,cd)

由否定選擇算法的檢測過程可以看出,該過程計算會耗費較多的計算時間,這不利于該算法的廣泛應用。

1.2 改進的否定選擇算法

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

1.3 檢測器集的層次聚類

本文設計的檢測器層次聚類過程為:

1)對否定選擇過程生成的成熟檢測器集D進行層次聚類處理,每層生成的聚類中心構成新的檢測器集C。

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

在二維實值空間[0,1]2進行仿真驗證如下:

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

1.4 孔洞數據的判定

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

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

(2)

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

(3)

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

2 算法流程

改進后否定選擇算法的檢驗過程分為檢測器生成階段與異常檢測階段,該算法的基本步驟如下:

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

2)對檢測器集D進行層次聚類處理,得到檢測器集C。

3)輸入數據集T進行異常檢測(計算T中數據和檢測器集C中檢測器之間的距離。

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

5)如果被檢測數據未與檢測器集C中的任一檢測器匹配,則認為其處于孔洞區,需進一步測試以判定其是否為正常數據并進行標識。

6)算法結束。

3 實驗結果與分析

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

選擇實驗目標覆蓋率為95%,自體半徑的取值區間為[0.01,0.30](每隔0.05取一個值),每個自體半徑進行100次實驗并取結果的平均值。

由圖1可以看出,3種不同算法的檢測率均隨著自體半徑的增大而降低,本文否定選擇算法的檢測率降幅比其他兩種算法更小。這是因為孔洞區數據隨著自體半徑的增大而增加,本文否定選擇算法由于對孔洞區數據的異常性進行了判定,提高了孔洞區數據檢測的準確性,從而提升了算法的檢測率。

圖1 檢測率隨自體半徑變化曲線

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

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

由圖1和圖2可知,檢測性能與自體半徑密切相關,隨著自體半徑的增大,算法的檢測率和誤檢率均降低。因此,需根據實際問題選擇適合的自體半徑來調整算法的檢測性能。

由圖3和圖4可以看出,當自體半徑為0.2時,3種算法的檢測率和誤檢率均隨著目標覆蓋率的增大而增加;和其他兩種算法相比,本文否定選擇算法的檢測率更高且誤檢率更低;當目標覆蓋率為99%時,3種算法的檢測性能較接近,這是因為當目標覆蓋率為99%時,所需成熟檢測器的數量顯著增加,對非自體區域的覆蓋增大,處于孔洞區域的數據減少,此時本文否定選擇算法的優勢不明顯。

圖3 檢測率隨期望覆蓋率變化曲線

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

由表1可以看出,V-Detector算法在采用不同形狀檢測器時檢測時間均最長,免疫實值否定選擇算法的次之,本文、否定選擇算法最短;當檢測器形狀為環形時,本文否定選擇算法的檢測時間最短。這是因為V-Detector算法由于需要計算各待檢測數據與檢測器集D中所有檢測器之間的距離以判斷數據是否異常,因而所需的檢測時間最長。

表1 不同算法的檢測時間結果對比

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

4 結束語

為提高異常檢測的效率,本文提出一種基于檢測器集層次聚類的否定選擇算法,通過對檢測器集進行層次聚類,以聚類中心檢測器代替初始檢測器集進行距離計算,減少計算時間并對未被檢測器覆蓋的孔洞區域屬性進行進一步判斷。實驗結果表明,本文否定選擇算法較V-detector算法和免疫實值否定選擇算法所需時間大幅減少,檢測效率提高且誤檢率降低。下一步將在本文算法的基礎上對聚類中心集和檢測器集的數量關系進行研究。