◆陶 晶

?

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

◆陶 晶

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

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

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

0 引言

V-detector算法作為否定選擇算法中的一種，因其首次提出用可變半徑的檢測器替代以往固定半徑的否定選擇算法，有效提高了檢測器覆蓋率，并使用了更少數(shù)量的檢測器覆蓋了更多的非自體區(qū)域。使得后來廣大學(xué)者對(duì)否定選擇算法的研究中，大多在V-detector之上加以改進(jìn)，采用zhouji的人造二維數(shù)據(jù)集進(jìn)行數(shù)據(jù)訓(xùn)練，并以V-detector作為實(shí)驗(yàn)的比對(duì)算法。因自體半徑為影響檢測器生成，繼而影響著最終檢測效果。因此對(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è)階段：檢測器的生成和非自體檢測。檢測器的生成階段，即訓(xùn)練數(shù)據(jù)隨機(jī)生成候選檢測器并與自體數(shù)據(jù)進(jìn)行距離比較，若覆蓋任何自體區(qū)域則舍棄并重新生成候選檢測器，在檢測器集訓(xùn)練成熟之后可覆蓋非自體空間。

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

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

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

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

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

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

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

則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)練生成檢測器，其中包含2000個(gè)自體數(shù)據(jù)與200個(gè)異常數(shù)據(jù)。因在現(xiàn)實(shí)應(yīng)用中，對(duì)網(wǎng)絡(luò)異常數(shù)據(jù)的初次檢測是沒有異常數(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ū)域的覆蓋，增大檢測率的覆蓋空間。

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

表1 自體半徑迭代

3 結(jié)論

本章通過引入文獻(xiàn)[3]的MV-detector的自體檢測率P、非自體檢測率P、總真實(shí)檢測率P等參數(shù)，通過迭代的方式獲得最佳自體半徑。對(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]李棟,劉樹林,劉穎慧,張宏利.基于自適應(yīng)超環(huán)檢測器的設(shè)備異常度檢測方法[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ī)森林分類的入侵檢測算法研究[J].信息網(wǎng)絡(luò)安全,2017(11):50-54.