◆陶 晶

?

用于異常檢測(cè)的負(fù)選擇算法的自體半徑分析

◆陶 晶

（沈陽(yáng)理工大學(xué)現(xiàn)代教育中心 遼寧 110159）

負(fù)選擇算法是用于異常檢測(cè)的一種有效方法?？勺儼霃降呢?fù)選擇算法中，檢測(cè)器的半徑對(duì)算法性能影響較大。本文通過(guò)實(shí)驗(yàn)分析并驗(yàn)證了在不同的應(yīng)用下，自體半徑的最佳取值。

異常檢測(cè)；負(fù)選擇算法；自體半徑

0 引言

V-detector算法作為否定選擇算法中的一種，因其首次提出用可變半徑的檢測(cè)器替代以往固定半徑的否定選擇算法，有效提高了檢測(cè)器覆蓋率，并使用了更少數(shù)量的檢測(cè)器覆蓋了更多的非自體區(qū)域。使得后來(lái)廣大學(xué)者對(duì)否定選擇算法的研究中，大多在V-detector之上加以改進(jìn)，采用zhouji的人造二維數(shù)據(jù)集進(jìn)行數(shù)據(jù)訓(xùn)練，并以V-detector作為實(shí)驗(yàn)的比對(duì)算法。因自體半徑為影響檢測(cè)器生成，繼而影響著最終檢測(cè)效果。因此對(duì)于V-detector訓(xùn)練集半徑的研究具有重要的意義。本文使用MV-detector算法，在初始自體集半徑的選取上加以改進(jìn)，以得到V-detector算法的訓(xùn)練集的最優(yōu)自體參數(shù)，為后續(xù)研究提供更優(yōu)的自體集參數(shù)選擇。

在MV-detector算法中，自體數(shù)據(jù)集的初始半徑采用訓(xùn)練集中自體點(diǎn)到非自體點(diǎn)的最近距離，因在大多數(shù)實(shí)際應(yīng)用中，初始訓(xùn)練集只有正常數(shù)據(jù)且zhouji的訓(xùn)練數(shù)據(jù)集合全部為自體（正常）數(shù)據(jù)，因此本章將初始自體半徑加以改進(jìn)，在實(shí)驗(yàn)階段的自體初始距離采用0.01。

1 MV-detector算法的基本定義

否定選擇算法（NSA）可分為兩個(gè)階段：檢測(cè)器的生成和非自體檢測(cè)。檢測(cè)器的生成階段，即訓(xùn)練數(shù)據(jù)隨機(jī)生成候選檢測(cè)器并與自體數(shù)據(jù)進(jìn)行距離比較，若覆蓋任何自體區(qū)域則舍棄并重新生成候選檢測(cè)器，在檢測(cè)器集訓(xùn)練成熟之后可覆蓋非自體空間。

檢測(cè)器的實(shí)際檢測(cè)性能的好壞會(huì)受多個(gè)參數(shù)影響，如自體樣本半徑、檢測(cè)器半徑、檢測(cè)器生成階段的終止條件。在大多數(shù)學(xué)者的研究實(shí)驗(yàn)中，自體樣本數(shù)據(jù)集的大小都根據(jù)前人的經(jīng)驗(yàn)所設(shè)置，因此自體半徑是最容易被忽略的影響參數(shù)。公茂果和陳文分別通過(guò)建立自體集檢測(cè)器和對(duì)自體集進(jìn)行層次聚類，以對(duì)NSA進(jìn)行優(yōu)化。在本文中，由自體樣本和自體半徑覆蓋的空間被定義為自身區(qū)域。如果自體半徑過(guò)小，則自體空間覆蓋率過(guò)低。通過(guò)自體半徑擴(kuò)展，使得同樣數(shù)量的自體樣本覆蓋更多的自體空間，然而一些非自身區(qū)域?qū)⒈诲e(cuò)誤地覆蓋到自體區(qū)域中，且兩側(cè)自體邊界的不平整導(dǎo)致產(chǎn)生檢測(cè)器不能覆蓋的孔洞區(qū)域過(guò)多。因此，對(duì)于NSA選擇合適的自體半徑非常重要。

免疫系統(tǒng)的功能是對(duì)身體的正常狀態(tài)維持，人體中使用抗體來(lái)區(qū)分自體和非自體抗原。在NSA中，抗體被定義為用于識(shí)別非自體區(qū)域的檢測(cè)器。因此，生成檢測(cè)器的質(zhì)量決定了檢測(cè)性能。以下是一些基本的NSA定義：

（1）從特征空間中提取的所有樣本特征構(gòu)成抗原集。

盡管NSA中檢測(cè)器被不斷改進(jìn)，但檢測(cè)性能仍受自體半徑、預(yù)期覆蓋率、檢測(cè)器半徑、檢測(cè)器體積等多個(gè)參數(shù)的影響。陳文等人通過(guò)研究證明了大的自體半徑會(huì)降低誤檢率；Zhouji預(yù)估了檢測(cè)器的非自體覆蓋率，并使用非自體覆蓋率作為檢測(cè)器終止生成條件；J.Q Zeng 提出ANSA算法可根據(jù)檢測(cè)結(jié)果定期更新改進(jìn)檢測(cè)器半徑。近年來(lái)廣大學(xué)者在異常檢測(cè)算法的參數(shù)研究中都取得較好的成績(jī)，并使用檢測(cè)率與誤檢率作為檢測(cè)器效果的衡量標(biāo)準(zhǔn)，然而大多數(shù)學(xué)者仍忽略了訓(xùn)練集中自體半徑對(duì)檢測(cè)結(jié)果的影響。

在以往的否定選擇算法中，采用檢測(cè)率DR(detection rate)與虛警率FA(false alarm rate)作為檢測(cè)器檢測(cè)質(zhì)量的衡量標(biāo)準(zhǔn)：

其中，、、、分別指檢測(cè)器正確識(shí)別的自體數(shù)量、正確識(shí)別的非自體數(shù)量、錯(cuò)誤識(shí)別的自體數(shù)量、錯(cuò)誤識(shí)別的非自體數(shù)量。

陳文在文獻(xiàn)[3]中提出一種新的評(píng)估方法，在原有的檢測(cè)率與誤檢率基礎(chǔ)之上，提出自體檢出率p，自體誤檢率p，非自體檢出率p，非自體誤檢率p，預(yù)期自體檢出率率p，預(yù)期非自體檢出率p，檢出率p，誤檢率p八個(gè)指標(biāo)，并以此共同衡量檢測(cè)效果。

則p，p，p，p與公式(2)(3)對(duì)比可得：

本文在文獻(xiàn)[3]中的算法思想的基礎(chǔ)之上，在實(shí)驗(yàn)階段對(duì)訓(xùn)練集合加以改進(jìn)，并改變初試自體半徑的選擇，以動(dòng)態(tài)迭代的方式定量的計(jì)算最佳自體半徑，以得到V-detector算法的最優(yōu)數(shù)據(jù)集。

在文獻(xiàn)[3]中選用樣本大小為2200的數(shù)據(jù)集，訓(xùn)練生成檢測(cè)器，其中包含2000個(gè)自體數(shù)據(jù)與200個(gè)異常數(shù)據(jù)。因在現(xiàn)實(shí)應(yīng)用中，對(duì)網(wǎng)絡(luò)異常數(shù)據(jù)的初次檢測(cè)是沒(méi)有異常數(shù)據(jù)進(jìn)行初始訓(xùn)練的，因此本章將陳文的MV-detector算法進(jìn)行訓(xùn)練集的改進(jìn)，使用大小為1000的初始自體集，且1000個(gè)樣本全部為自體（正常）數(shù)據(jù)。

在MV-detector算法中，自體數(shù)據(jù)集的初始半徑采用訓(xùn)練集中自體點(diǎn)到非自體點(diǎn)的最近距離，因zhouji的訓(xùn)練數(shù)據(jù)集合全部為自體數(shù)據(jù)，因此本文在實(shí)驗(yàn)階段的自體初始距離采用0.01，樣本空間為二維實(shí)值空間[0,1]2。

2 MV-detector算法的自體樣本半徑分析

此時(shí)應(yīng)將自體半徑減去r以收縮自體樣本空間，避免對(duì)非自體區(qū)域的覆蓋，增大檢測(cè)率的覆蓋空間。

在MV-detector算法中，得到基礎(chǔ)自體半徑之后，基于局部數(shù)據(jù)密度調(diào)整自體元素s的半徑的方法如下：

表1 自體半徑迭代

3 結(jié)論

本章通過(guò)引入文獻(xiàn)[3]的MV-detector的自體檢測(cè)率P、非自體檢測(cè)率P、總真實(shí)檢測(cè)率P等參數(shù)，通過(guò)迭代的方式獲得最佳自體半徑。對(duì)于zhouji在經(jīng)典算法V-detector中所使用二維實(shí)值數(shù)據(jù)集，當(dāng)自體空間為交叉十字形、環(huán)形、三角形三種自體分布空間時(shí)，自體半徑=0.2時(shí)為最佳自體半徑。

[1]Ji Zhou, Dasgupta D. V-detector: an efficient negative selection algorithm with probably adequate detector coverage. Inform sciences, 2009, 179(10): 1390–1406

[2]李棟,劉樹(shù)林,劉穎慧,張宏利.基于自適應(yīng)超環(huán)檢測(cè)器的設(shè)備異常度檢測(cè)方法[J].機(jī)械工程學(xué)報(bào),2014,50(12):17-24.

[3]Wen Chen ,Tao Li .Parameter analysis of negative selection algorithm[J]. Information Sciences, 2017, 420(12):218-234.

[4]Xin Xiao, Tao Li, Ruirui Zhang. An immune optimiz-ation based real-valued negative selection algorithm[M]. Klu-wer Academic Publishers, 2015

[5]Chen Wen, Tao Li, Xiaojie Liu, et al. A negative sel-ection algorithm based on hierarchical clustering of self set[J]. 2013, 56(8):1-13..

[6]Ji Zhou, Dasgupta D. V-detector:an efficient negativeselection algorithm with probably adequate detector coverage. Inform sciences, 2009, 179(10): 1390–1406

[7]Jinquan Zeng, Xiaojie Liu, Tao Li ,et al. A self-adap-tive negative selection algorithm used for anomaly detection[J]. Progress in Natural Science, 2009, 19(2):261-266.

[8]林偉寧,陳明志,詹云清,劉川葆.一種基于PCA和隨機(jī)森林分類的入侵檢測(cè)算法研究[J].信息網(wǎng)絡(luò)安全,2017(11):50-54.