# A Quick Negative Selection Algorithm for One-Class Classification in Big Data Era

Authors: Fangdong Zhu; Wen Chen; Hanli Yang; Tao Li; Tao Yang; Fan Zhang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Negative selection algorithm (NSA) is an important kind of the one-class classification model, but it is limited in the big data era due to its low efficiency. In this paper, we propose a new NSA based on Voronoi diagrams: VorNSA. The scheme of the detector generation process is changed from the traditional “Random-Discard” model to the “Computing-Designated” model by VorNSA. Furthermore, we present an immune detection process of VorNSA under Map/Reduce framework (VorNSA/MR) to further reduce the time consumption on massive data in the testing stage. Theoretical analyses show that the time complexity of VorNSA decreases from the exponential level to the logarithmic level. Experiments are performed to compare the proposed technique with other NSAs and one-class classifiers. The results show that the time cost of the VorNSA is averagely decreased by 87.5% compared with traditional NSAs in UCI skin dataset.


---

## Body

## 1. Introduction

NSA was proposed by Forrest et al. in 1994 [1], which generates immune detectors based on the “Random-Discard” model. Initially, massive immature detectors are randomly generated, and then the ones covering the self-areas are discarded. González et al. presented the real-valued negative selection algorithm (RNSA) in 2003 [2], in which the detectors and antigens are studied in the real-value space. Ji and Dasgupta proposed V-Detector algorithm [3, 4]. It turns the fixed-length detectors in RNSA into the variable-sized detectors to enlarge the detection areas. In 2015, Cui et al. developed BIORV-NSA [5]. In their work, the self-radius can be variable and the detectors, which are recognized by other mature detectors, are replaced by new ones to eliminate the “detection holds.”In big data era, the low efficiency of NSA becomes an important challenge, which largely limits its applications. In this paper, we design a new NSA based on Voronoi diagrams, named VorNSA. In the VorNSA, a restrained Voronoi diagram is constructed based on the whole training set in the first step. Then, two types of detectors are generated in the specific location of the Voronoi diagram separately. In order to accelerate the test stage of NSA, in particular for large scale dataset, a new testing strategy VorNSA/MR (VorNSA with Map-Reduce) is proposed. Unlike the testing stage of classic NSAs, data are divided into small groups and calculated to generate the labels separately in Map stage. Then the final labels can be obtained after merging and sorting in the Reduce stage.The contributions of this work can be summarized as follows. (1) Based on Voronoi diagrams, the optimal position of detectors is calculated directly rather than in a stochastic way. Therefore, the time consumption wasted on excessive invalid detectors is avoided. (2) In the Map/Reduce framework, data are partitioned into several small parts by VorNSA/MR and can be processed in parallel to enhance the self/non-self-discrimination efficiency.The rest of the paper is organized as follows. In Section2, we describe the definitions of VorNSA. The original contribution of the paper is presented in Section 3. Experimental results on synthetic datasets and real-world datasets are shown and discussed in Section 4. Conclusions appear in Section 5.


## 2. Basic Definition of VorNSA

VorNSA is designed based on Voronoi, which is derived from computation geometry to search the nearest neighbors, and it has been widely utilized in the fields of life sciences [6], material sciences [7], and mobile navigation [8]. The basic definitions are listed as follows.Definition 1 (site).
Site is a set ofn distinct points in the feature space. In VorNSA, all the training samples are defined as site points: S=S1,S2,…,Sn.Definition 2 (Voronoi diagram).
V
o
r
S divides the feature space into n unoverlapped cells based on the given site set S, and each cell νSi only contains one site Si in S, such that any point q in νSi satisfies distq,Si<dist(q,Sj)∀Sj∈S, j≠i, and dist can be any distance metrics.Definition 3 (cell).
All the cells construct a mathematic partition of the feature space, and the cell corresponding to siteSi is denoted by νSi.Definition 4 (largest empty circle).
The largest circle with centerp, which does not contain any site in S, is denoted by CSp.Theorem 5.
A pointp is a vertex of VorS iff CSp contains at least three sites on its boundary [9].Definition 6 (I-detector).
c
,
r, where c is the detector position in the feature space, and r is the detector radius, satisfies that c corresponds to one vertex of the Voronoi diagram.Theorem 7.
Givenp is the center of an I-detector, there are at least three sites located on the boundary of CSp, and these sites are the nearest neighbors of each other.Proof.
According to ‎Definitions2 and 6, it can be inferred that the center of the I-detectorp is an intersection of three or more cells. Suppose that p is intersected by three cells νSi, νSj, νSk, while the sites of these cells are Si, Sj, Sk. According to ‎Definition 4 and ‎Theorem 5, there is a largest empty circle CSp that does not contain any site of S, and Si, Sj, Sk are located on its boundary. So Si, Sj, and Sk are the nearest sites of p among the site sets S.Theorem 8.
The bisector between sitesSi and Sj defines an edge of VorS iff there is a point q on the bisector such that CSq contains both Si and Sj on its boundary with no other site [9].Definition 9 (II-detector).
c
,
r, where c is the detector position in the feature space, and r is the detector radius, satisfies that c corresponds to the junction of the edges of VorS and the unit hypercube 0,1d.Theorem 10.
Givenq is the center of II-detector, there are two sites located on the boundary of CSp, and these sites are the nearest neighbors of each other.Proof.
According to ‎‎Definitions2 and 9, it can be inferred that the center of II-detector q is an intersection of two cells. Suppose that q is intersected by two cells νSi, νSj, while the sites of these cells are Si, Sj. According to ‎Definition 4 and ‎Theorem 8, there is a largest empty circle CSq that does not contain any site of S, and Si, Sj are located on its boundary. So Si and Sj are the nearest sites of q among the site sets S.As an example in Figure1, there are 10 sites S1–S10 in set S, and the space is divided into 10 cells νS1–νS10 by the Voronoi diagram VorS. The green circle is CSP, and three sites (S2, S8, S10) are located on its boundary. The red circle is CSQ, and two sites (S8, S10) are located on the boundary. The purple circle is CST, and two sites (S2, S8) are located on the boundary. P is the center of I-detector, while Q and T are the centers of II-detector.Figure 1
The red cross is the site. The blue line is the Voronoi diagram. The circle is the largest empty circle.


## 3. The Details of VorNSA

### 3.1. The Detector Generation Process of VorNSA

#### 3.1.1. Space Partition Stage

First of all, all the training data are normalized to0,1d feature space, where d is the data dimension. The normalized training set is denoted by S. Secondly, a bounded Voronoi diagram VorS is constructed based on S, to divide the unit feature space 0,1d into n cells, where n = S. Finally, the set VS={VetSi,Si∣i=1,…,n}, where VetSi, Si are the vertex and site in a cell νSi, can be constructed.


#### 3.1.2. I-Detector Generation Stage

According to ‎Definition6 and ‎Theorem 7, the center of I-detector p is designated by the intersection of three or more cells, and the sites located in the cells are the nearest neighbors of each other. So a new set VS1={VetSj,Sj|j=1⋯}, where VetSj is the position of I-detector and Sj is the nearest sites, can be obtained by VetSj=x∣x=VetSp∩VetSq∩VetSt,p≠q≠t, where VetSp, VetSq, and VetSt are the vertex sets of cell. Then, generating a mature detector is just through self-tolerating with Sj. According to the principle of self-tolerance, the radius of I-detector can be calculated with (1)RP=distVetSj,Sj-RS,where RP is the radius of I-detector, VetSj is the center of I-detector, Sj is the nearest sites, and RS is the radius of self-antigens.Furthermore, a thresholdδ of detector radius is introduced in case of overfitting: If the detector radius RP is less than δ, the detector will be discarded. Otherwise, it will mature.


#### 3.1.3. II-Detector Generation Stage

The main difference between the I-detector and the II-detector is the location of detector centers. According to ‎Definition9 and ‎Theorem 10, the position of II-detector q is located on the junction of two cells and the unit hypercube. The sites in the two cells are the nearest neighbors of each other. So a new set VS2={VetSk,Sk∣k=1⋯}, where VetSk is the position of II-detector and Sk is the nearest sites, can be obtained by VetSk=x∣x=VetSp∩VetSq,p≠q, where VetSp and VetSq are the vertex sets of cell. Similarly, the radius of II-detector can be computed by (2), and a threshold δ of detector radius is introduced in case of overfitting.(2)RQ=distVetSk,Sk-RS,where RQ is the radius of II-detector, VetSk is the position of II-detector and Sk is the nearest sites, and RS is the radius of self-antigens.Details of the VorNSA can be found in Algorithm1.Algorithm 1:VorNSA (S,RS,δ).
Input: Training setS, Self radius RS, Minimum detector radius δ
Output: Detector setD
(1) normalize S into 0,1d
(2) construct voronoi diagram VorS by sites S
(3) get all cells νSi in VorS
(4) construct VS={VetSi,Si∣i=1,…,n} by νSi
(5) foreach VetSi,Si in VS
(6)   if VetSi has three or more same values in VS
(7)   then VS1=VS1∪VetSi,Si
(8) foreach VetSj,Sj in VS1
(9)   compute the detector radius RP using Eq. (1)
(10)   if RP>δ then DI=DI∪VetSj,RP
(11) foreach VetSi,Si in VS
(12)   if VetSi has two same values in VS
(13)   then VS2=VS2∪VetSi,Si
(14) foreach VetSk,Sk in VS2
(15)   compute the detector radius RQ using Eq. (2)
(16)   if RQ>δ then DII=DII∪Qi,RQi
(17) return D=DI∪DII


### 3.2. The Immune Detection Process of VorNSA under Map/Reduce Framework

In the testing stage of traditional NSAs, each piece of data has to be compared with all the detectors to label its classification. This strategy is too time-consuming to be applied in big data era due to its low efficiency. In order to enhance the efficiency in testing stage, an immune detection process of VorNSA under Map/Reduce framework (VorNSA/MR) is proposed. Map/Reduce is a parallel computation framework, which splits the sample set into a group of small datasets and handles them on many cluster nodes simultaneously.Details of VorNSA/MR (Figure2) are mainly divided into two parts: Map stage and Reduce stage. First of all, the testing datasets are split into n parts by VorNSA/MR. In the Map stage, each cluster node selects a part of split data to compute the distance with matured detectors. If any distance is less than the detection radius, the testing sample is labeled with the non-self-antigens; otherwise it is labeled with the self-antigens. Then cluster nodes put results to the intermediate value. The Reducer receives the intermediate values, sorts them, and merges them into the final results.Figure 2
The details of VorNSA/MR.The implements of Map and Reduce stage can be found in Algorithms2 and 3.Algorithm 2:Mapper (D,T).
Input: Detector setD, Split data T
Output: Intermediate Value IV
(1) foreach Ti in T
(2)    foreach Dk in D
(3)      Compute the Euclidean distance distTi,Dk between Ti and Dk
(4)      if Dk.r  < distTi,Dk
(5)        Ti is Noself Antigen, Ti.Label = 0
(6)        go to line (2)
(7)      Ti is Self Antigen, Ti.Label = 1
(8) IV.Value = T.no,T.Label
(9) return IVAlgorithm 3:Reducer (IV).
Input: Intermediate Value IV
Output: Final Value FV
(1) While IV.next ~= END
(2)    add IV.Value to FV.Value
(3) Sort FV.Value by no
(4) return FV


### 3.3. Theoretical Analysis

Theorem 11.
The time complexity of VorNSA isNSlog⁡NS+NSd/2+D, where NS is the size of training dataset, d is the dimension of training dataset, and D is the size of detectors.Proof.
Since VorNSA is divided into three stages, we could analyze the time complexity separately.
The main work in space partition stage is to build a Voronoi diagram, so we borrow the analysis from Voronoi diagrams to estimate the time complexity. The literatures [9–12] prove that a Voronoi diagram with n sites can be computed in Onlog⁡n+nd/2 optimal time under d-dimension space. Therefore, the time complexity can be denoted by ONSlog⁡NS+NSd/2, where NS is the size of training set, and d is the dimension of training set.
In the second and third stage, the main work is to compute the distance between detectors and sites. Though several detectors are discarded by the thresholdδ, the quantity is very small compared with the whole size, so we use the size of detectors D instead. According to (1) and (2), we can infer that the time complexity is OD in the two stages.
Combining the abovementioned, the time complexity of VorNSA isONSlog⁡NS+NSd/2+D.The time complexity of traditional NSAs is shown in Table1, where Pm is the match probability between detectors and antigens, Pf is the failure rate, NS is the size of self-set, D is the size of detectors, and d is the data dimension. As shown in Table 1, the time complexity of VorNSA is in logarithmic level with NS, which is much less than the traditional exponential level compared with NNSA [1], RNSA [2], and V-Detector [4].Table 1
The complexity of NSAs.
Algorithm
Time complexity
NNSA [1]
O
-
ln
⁡
P
f
∗
N
S
P
m
1
-
P
m
N
S
RNSA [2]
O
D
∗
N
S
1
-
P
m
N
S
V-Detector [4]
O
D
∗
N
S
1
-
P
m
N
S
VorNSA
O
N
S
log
⁡
N
S
+
N
S
d
/
2
+
D


## 3.1. The Detector Generation Process of VorNSA

### 3.1.1. Space Partition Stage

First of all, all the training data are normalized to0,1d feature space, where d is the data dimension. The normalized training set is denoted by S. Secondly, a bounded Voronoi diagram VorS is constructed based on S, to divide the unit feature space 0,1d into n cells, where n = S. Finally, the set VS={VetSi,Si∣i=1,…,n}, where VetSi, Si are the vertex and site in a cell νSi, can be constructed.


### 3.1.2. I-Detector Generation Stage

According to ‎Definition6 and ‎Theorem 7, the center of I-detector p is designated by the intersection of three or more cells, and the sites located in the cells are the nearest neighbors of each other. So a new set VS1={VetSj,Sj|j=1⋯}, where VetSj is the position of I-detector and Sj is the nearest sites, can be obtained by VetSj=x∣x=VetSp∩VetSq∩VetSt,p≠q≠t, where VetSp, VetSq, and VetSt are the vertex sets of cell. Then, generating a mature detector is just through self-tolerating with Sj. According to the principle of self-tolerance, the radius of I-detector can be calculated with (1)RP=distVetSj,Sj-RS,where RP is the radius of I-detector, VetSj is the center of I-detector, Sj is the nearest sites, and RS is the radius of self-antigens.Furthermore, a thresholdδ of detector radius is introduced in case of overfitting: If the detector radius RP is less than δ, the detector will be discarded. Otherwise, it will mature.


### 3.1.3. II-Detector Generation Stage

The main difference between the I-detector and the II-detector is the location of detector centers. According to ‎Definition9 and ‎Theorem 10, the position of II-detector q is located on the junction of two cells and the unit hypercube. The sites in the two cells are the nearest neighbors of each other. So a new set VS2={VetSk,Sk∣k=1⋯}, where VetSk is the position of II-detector and Sk is the nearest sites, can be obtained by VetSk=x∣x=VetSp∩VetSq,p≠q, where VetSp and VetSq are the vertex sets of cell. Similarly, the radius of II-detector can be computed by (2), and a threshold δ of detector radius is introduced in case of overfitting.(2)RQ=distVetSk,Sk-RS,where RQ is the radius of II-detector, VetSk is the position of II-detector and Sk is the nearest sites, and RS is the radius of self-antigens.Details of the VorNSA can be found in Algorithm1.Algorithm 1:VorNSA (S,RS,δ).
Input: Training setS, Self radius RS, Minimum detector radius δ
Output: Detector setD
(1) normalize S into 0,1d
(2) construct voronoi diagram VorS by sites S
(3) get all cells νSi in VorS
(4) construct VS={VetSi,Si∣i=1,…,n} by νSi
(5) foreach VetSi,Si in VS
(6)   if VetSi has three or more same values in VS
(7)   then VS1=VS1∪VetSi,Si
(8) foreach VetSj,Sj in VS1
(9)   compute the detector radius RP using Eq. (1)
(10)   if RP>δ then DI=DI∪VetSj,RP
(11) foreach VetSi,Si in VS
(12)   if VetSi has two same values in VS
(13)   then VS2=VS2∪VetSi,Si
(14) foreach VetSk,Sk in VS2
(15)   compute the detector radius RQ using Eq. (2)
(16)   if RQ>δ then DII=DII∪Qi,RQi
(17) return D=DI∪DII


## 3.1.1. Space Partition Stage

First of all, all the training data are normalized to0,1d feature space, where d is the data dimension. The normalized training set is denoted by S. Secondly, a bounded Voronoi diagram VorS is constructed based on S, to divide the unit feature space 0,1d into n cells, where n = S. Finally, the set VS={VetSi,Si∣i=1,…,n}, where VetSi, Si are the vertex and site in a cell νSi, can be constructed.


## 3.1.2. I-Detector Generation Stage

According to ‎Definition6 and ‎Theorem 7, the center of I-detector p is designated by the intersection of three or more cells, and the sites located in the cells are the nearest neighbors of each other. So a new set VS1={VetSj,Sj|j=1⋯}, where VetSj is the position of I-detector and Sj is the nearest sites, can be obtained by VetSj=x∣x=VetSp∩VetSq∩VetSt,p≠q≠t, where VetSp, VetSq, and VetSt are the vertex sets of cell. Then, generating a mature detector is just through self-tolerating with Sj. According to the principle of self-tolerance, the radius of I-detector can be calculated with (1)RP=distVetSj,Sj-RS,where RP is the radius of I-detector, VetSj is the center of I-detector, Sj is the nearest sites, and RS is the radius of self-antigens.Furthermore, a thresholdδ of detector radius is introduced in case of overfitting: If the detector radius RP is less than δ, the detector will be discarded. Otherwise, it will mature.


## 3.1.3. II-Detector Generation Stage

The main difference between the I-detector and the II-detector is the location of detector centers. According to ‎Definition9 and ‎Theorem 10, the position of II-detector q is located on the junction of two cells and the unit hypercube. The sites in the two cells are the nearest neighbors of each other. So a new set VS2={VetSk,Sk∣k=1⋯}, where VetSk is the position of II-detector and Sk is the nearest sites, can be obtained by VetSk=x∣x=VetSp∩VetSq,p≠q, where VetSp and VetSq are the vertex sets of cell. Similarly, the radius of II-detector can be computed by (2), and a threshold δ of detector radius is introduced in case of overfitting.(2)RQ=distVetSk,Sk-RS,where RQ is the radius of II-detector, VetSk is the position of II-detector and Sk is the nearest sites, and RS is the radius of self-antigens.Details of the VorNSA can be found in Algorithm1.Algorithm 1:VorNSA (S,RS,δ).
Input: Training setS, Self radius RS, Minimum detector radius δ
Output: Detector setD
(1) normalize S into 0,1d
(2) construct voronoi diagram VorS by sites S
(3) get all cells νSi in VorS
(4) construct VS={VetSi,Si∣i=1,…,n} by νSi
(5) foreach VetSi,Si in VS
(6)   if VetSi has three or more same values in VS
(7)   then VS1=VS1∪VetSi,Si
(8) foreach VetSj,Sj in VS1
(9)   compute the detector radius RP using Eq. (1)
(10)   if RP>δ then DI=DI∪VetSj,RP
(11) foreach VetSi,Si in VS
(12)   if VetSi has two same values in VS
(13)   then VS2=VS2∪VetSi,Si
(14) foreach VetSk,Sk in VS2
(15)   compute the detector radius RQ using Eq. (2)
(16)   if RQ>δ then DII=DII∪Qi,RQi
(17) return D=DI∪DII


## 3.2. The Immune Detection Process of VorNSA under Map/Reduce Framework

In the testing stage of traditional NSAs, each piece of data has to be compared with all the detectors to label its classification. This strategy is too time-consuming to be applied in big data era due to its low efficiency. In order to enhance the efficiency in testing stage, an immune detection process of VorNSA under Map/Reduce framework (VorNSA/MR) is proposed. Map/Reduce is a parallel computation framework, which splits the sample set into a group of small datasets and handles them on many cluster nodes simultaneously.Details of VorNSA/MR (Figure2) are mainly divided into two parts: Map stage and Reduce stage. First of all, the testing datasets are split into n parts by VorNSA/MR. In the Map stage, each cluster node selects a part of split data to compute the distance with matured detectors. If any distance is less than the detection radius, the testing sample is labeled with the non-self-antigens; otherwise it is labeled with the self-antigens. Then cluster nodes put results to the intermediate value. The Reducer receives the intermediate values, sorts them, and merges them into the final results.Figure 2
The details of VorNSA/MR.The implements of Map and Reduce stage can be found in Algorithms2 and 3.Algorithm 2:Mapper (D,T).
Input: Detector setD, Split data T
Output: Intermediate Value IV
(1) foreach Ti in T
(2)    foreach Dk in D
(3)      Compute the Euclidean distance distTi,Dk between Ti and Dk
(4)      if Dk.r  < distTi,Dk
(5)        Ti is Noself Antigen, Ti.Label = 0
(6)        go to line (2)
(7)      Ti is Self Antigen, Ti.Label = 1
(8) IV.Value = T.no,T.Label
(9) return IVAlgorithm 3:Reducer (IV).
Input: Intermediate Value IV
Output: Final Value FV
(1) While IV.next ~= END
(2)    add IV.Value to FV.Value
(3) Sort FV.Value by no
(4) return FV


## 3.3. Theoretical Analysis

Theorem 11.
The time complexity of VorNSA isNSlog⁡NS+NSd/2+D, where NS is the size of training dataset, d is the dimension of training dataset, and D is the size of detectors.Proof.
Since VorNSA is divided into three stages, we could analyze the time complexity separately.
The main work in space partition stage is to build a Voronoi diagram, so we borrow the analysis from Voronoi diagrams to estimate the time complexity. The literatures [9–12] prove that a Voronoi diagram with n sites can be computed in Onlog⁡n+nd/2 optimal time under d-dimension space. Therefore, the time complexity can be denoted by ONSlog⁡NS+NSd/2, where NS is the size of training set, and d is the dimension of training set.
In the second and third stage, the main work is to compute the distance between detectors and sites. Though several detectors are discarded by the thresholdδ, the quantity is very small compared with the whole size, so we use the size of detectors D instead. According to (1) and (2), we can infer that the time complexity is OD in the two stages.
Combining the abovementioned, the time complexity of VorNSA isONSlog⁡NS+NSd/2+D.The time complexity of traditional NSAs is shown in Table1, where Pm is the match probability between detectors and antigens, Pf is the failure rate, NS is the size of self-set, D is the size of detectors, and d is the data dimension. As shown in Table 1, the time complexity of VorNSA is in logarithmic level with NS, which is much less than the traditional exponential level compared with NNSA [1], RNSA [2], and V-Detector [4].Table 1
The complexity of NSAs.
Algorithm
Time complexity
NNSA [1]
O
-
ln
⁡
P
f
∗
N
S
P
m
1
-
P
m
N
S
RNSA [2]
O
D
∗
N
S
1
-
P
m
N
S
V-Detector [4]
O
D
∗
N
S
1
-
P
m
N
S
VorNSA
O
N
S
log
⁡
N
S
+
N
S
d
/
2
+
D


## 4. Experiments and Discussion

In the experiments, we use two evaluation criteria of performance: DR (Detection Rate) and FAR (False Alarm Rate) which is reported in varied literature [2, 3, 13], and they are defined as(3)DR=TPTP+FN,FAR=FPFP+TN,where TP and FN are the counts of true positive and false negative of non-self-antigens, respectively, and TN and FP represent the number of true negative and false positive of self-antigens, respectively.


### 4.1. Experiments on Synthetic Dataset (SDS)

In order to determine the performance of VorNSA among different datasets, 4 SDS proposed by the intelligence security laboratory of Memphis University are introduced in this section. The records of original datasets [3] are 1000, respectively. We expand the number of pieces of data to 10,000 to simulate the environment of big data better. The distributions of datasets are depicted as Figure 3 in which self-antigens are represented by red dots and non-self-antigens are shown by blue points. The details of datasets are listed in Table 2. Additionally, experiment parameters are set as follows: the self-radius is 0.04, self-antigens are randomly obtained from 50 to 1000, and the minimum radius of detectors is 0.005. Each experiment is repeated 25 times independently.Table 2
The detail of 4 SDS.
Dataset
Records number
Self-antigens
Non-self-antigens
Cross
10,000
5,531
4,469
Ring
10,000
3,710
6,290
Pentagram
10,000
2,850
7,150
Triangle
10,000
1,476
8,524Figure 3
The distribution of 4 SDS.As Figure4 shows, the trends of experiment results on 4 SDS are approximately the same. It indicates that VorNSA could achieve a high degree of applicability on different datasets. In Figure 4(a), it can be observed that the DR decreases from 95% to 80% with the increment of self-antigens. Besides, in Figure 4(b), the FAR drops from 60% to zeros. The reasons of this phenomenon can be explained as follows: when less self-antigens are trained, some self-antigens cannot be covered by the scope of self. So these self-antigens are identified as non-self-antigens in VorNSA. Due to its strong ability in detecting, the DR and FAR are both high. With the increase of the training numbers, all self-antigens will be covered. Furthermore, the non-self-antigens are covered and identified as self-antigens, in particular those located in the edge of self-set. Therefore, the DR decreases slightly while FAR sharply drops to zeros.Figure 4
Results with different training samples.
(a)
Detection rate
(b)
False alarm rate
(c)
Detector number
(d)
Detector train timeFigure4(c) shows the quantity of detectors generated by VorNSA is not increasing remarkably with the growth of train set but maintains a relatively stable range. It is implied that VorNSA can effectively control the expansion of detectors. According to ‎Definition 2, with the increment of training samples, the space will be partitioned into smaller cells. We introduce the minimum detector radius δ. Thus, the inefficient tiny detectors are discarded.In Figure4(d), it can be noted that the time consumption of VorNSA on different datasets is similar, and time cost rises slowly even with enormous self-antigens. It suggests that the performance of VorNSA is less affected by the distribution of dataset, because the optimal position of detectors is calculated directly rather than in a stochastic way.To sum up, we can see that VorNSA can generate fewer but more effective detectors. Besides, the less self-antigens are trained, the higher FAR will be. With the number of self-antigens increasing, the FAR is decreased significantly. Increasing the training set will lead to a rise of the time consumption, and the DR will be slightly decreased. Hence, a smaller self-set will be a smart choose in VorNSA.


### 4.2. Experiments on Skin Segmentation Dataset

In this section, VorNSA is tested by a group of comparison experiments. The compared algorithms include the classic NSAs (RNSA, V-Detector), a newly proposed NSA (BIORV-NSA) in 2015. To study the different methods, we introduce a classic statistics algorithm for one-class classification: OC-SVM [14], which is implemented by LibSVM [15]. All algorithms run in a computer deployed with Intel Pentium E6600@3.06 G, while the implement of VorNSA refers to an open source toolbox of computational geometry, called MPT 3.0 [16].The Skin Segmentation dataset is a UCI dataset. It is collected by randomly sampling B, G, and R values of skin texture, which derives from FERET database and PAL database. Total sample size is 245,057 in which 50,859 records are the skin samples and 194,198 records are non-skin ones.In this experiment, 50 skin samples are randomly obtained as self-antigens. Meanwhile, to verify the performances of VorNSA and VorNSA/MR in large scale dataset, we use all 245,057 records in the datasets. The experiments are preformed 20 times independently, and the evaluation criteria include DR, FAR, detector number (DN), data training time (DT), and data testing time (DTT). The parameters of simulation are set as follows: the OC-SVM uses the RBF kernel functions, and nu is 0.5 and gamma is 0.33. The self-radius of RNSA, V-Detector, and VorNSA are set as the same value (0.1). The maximum number of detectors is 3000 in RNSA, and detector radius is 0.1. The estimated coverage and the maximum self-coverage are 99%. The maximum number of detectors is 1000 in BIORV-NSA, and the self-set edge inhibition parameter is 0.8 and the detector self-inhibition parameter is 1.2. The minimum radius of detectors is 0.005 in VorNSA and VorNSA/MR. The results of experiments are shown in Table3.Table 3
Results in skin segmentation.
Algorithm
DR (%)
FAR (%)
DN
DT (s)
DTT (s)
Mean
SD
Mean
SD
Mean
SD
Mean
SD
Mean
SD
OC-SVM
99.09
0.7
51.20
6.67
—
—
—
—
—
—
RNSA
98.42
0.63
0.66
1.48
3000.00
0
8.68
0.13
7501.59
400.49
V-Detector
99.05
0.27
1.31
1.22
469.85
174.66
32.12
23.86
948.55
325.50
BIORV-NSA
99.42
0.34
3.29
2.72
1000.00
0
20.00
0.11
1919.83
59.46
VorNSA
99.20
0.16
1.48
1.49
172.25
11.06
1.91
0.77
671.15
89.36
VorNSA/MR∗
99.43
0.24
1.56
1.37
176.90
11.96
1.79
0.07
426.70
31.97
∗The VorNSA/MR is deployed at 2 nodes: one is Intel Pentium E6600@3.06 G (2 Core); the other is Inter Core i5-2450M@2.5 G (2 Core).From Table3, it can be seen that the FAR of OC-SVM is 51.2%, reaching an unacceptable level. As OC-SVM implemented in a different platform, the time consumption is not counted in this paper. The DR of VorNSA (99.2%) is closed to the BIORV-NSA (99.42%), and better than the classic NSAs. Besides, the FAR of VorNSA (1.48%) is lower than BIORV-NSA (3.29%). It indicates that the detectors generated by VorNSA are more applicable than BIORV-NSA and more effective than classic NSAs.Moreover, the DN, DT, and DTT of VorNSA are significantly lower than other NSAs, especially when it integrates the Map-Reduce Testing Framework. For example, the average number of detectors generated by VorNSA is 172.25, lower 63.3% by V-Detector and 82.8% by BIORV-NSA. The average training time of VorNSA is 1.91, lower 78% by RNSA, 94.1% by V-Detector, and 90.5% by BIORV-NSA. So the efficiency of VorNSA is averagely decreased by 87.5% compared with traditional NSAs. The testing time of VorNSA/MR is 426.7, lower 36.4% by VorNSA, 55% by V-Detector, 77.8% by BIORV-NSA, and 94.3% by RNSA.The main reasons of above results can be explained as follows. In traditional NSAs, a large number of immature detectors are randomly generated without any optimal way and must self-tolerate with all self-antigens to decide whether they are matured or not. As a result, much time has been wasted. The scheme of detector generation of VorNSA is quite different with other NSAs. The optimal position of detectors is directly calculated. Thus, the time consumption on discarding many randomly generated but inappropriate detectors is avoided.


## 4.1. Experiments on Synthetic Dataset (SDS)

In order to determine the performance of VorNSA among different datasets, 4 SDS proposed by the intelligence security laboratory of Memphis University are introduced in this section. The records of original datasets [3] are 1000, respectively. We expand the number of pieces of data to 10,000 to simulate the environment of big data better. The distributions of datasets are depicted as Figure 3 in which self-antigens are represented by red dots and non-self-antigens are shown by blue points. The details of datasets are listed in Table 2. Additionally, experiment parameters are set as follows: the self-radius is 0.04, self-antigens are randomly obtained from 50 to 1000, and the minimum radius of detectors is 0.005. Each experiment is repeated 25 times independently.Table 2
The detail of 4 SDS.
Dataset
Records number
Self-antigens
Non-self-antigens
Cross
10,000
5,531
4,469
Ring
10,000
3,710
6,290
Pentagram
10,000
2,850
7,150
Triangle
10,000
1,476
8,524Figure 3
The distribution of 4 SDS.As Figure4 shows, the trends of experiment results on 4 SDS are approximately the same. It indicates that VorNSA could achieve a high degree of applicability on different datasets. In Figure 4(a), it can be observed that the DR decreases from 95% to 80% with the increment of self-antigens. Besides, in Figure 4(b), the FAR drops from 60% to zeros. The reasons of this phenomenon can be explained as follows: when less self-antigens are trained, some self-antigens cannot be covered by the scope of self. So these self-antigens are identified as non-self-antigens in VorNSA. Due to its strong ability in detecting, the DR and FAR are both high. With the increase of the training numbers, all self-antigens will be covered. Furthermore, the non-self-antigens are covered and identified as self-antigens, in particular those located in the edge of self-set. Therefore, the DR decreases slightly while FAR sharply drops to zeros.Figure 4
Results with different training samples.
(a)
Detection rate
(b)
False alarm rate
(c)
Detector number
(d)
Detector train timeFigure4(c) shows the quantity of detectors generated by VorNSA is not increasing remarkably with the growth of train set but maintains a relatively stable range. It is implied that VorNSA can effectively control the expansion of detectors. According to ‎Definition 2, with the increment of training samples, the space will be partitioned into smaller cells. We introduce the minimum detector radius δ. Thus, the inefficient tiny detectors are discarded.In Figure4(d), it can be noted that the time consumption of VorNSA on different datasets is similar, and time cost rises slowly even with enormous self-antigens. It suggests that the performance of VorNSA is less affected by the distribution of dataset, because the optimal position of detectors is calculated directly rather than in a stochastic way.To sum up, we can see that VorNSA can generate fewer but more effective detectors. Besides, the less self-antigens are trained, the higher FAR will be. With the number of self-antigens increasing, the FAR is decreased significantly. Increasing the training set will lead to a rise of the time consumption, and the DR will be slightly decreased. Hence, a smaller self-set will be a smart choose in VorNSA.


## 4.2. Experiments on Skin Segmentation Dataset

In this section, VorNSA is tested by a group of comparison experiments. The compared algorithms include the classic NSAs (RNSA, V-Detector), a newly proposed NSA (BIORV-NSA) in 2015. To study the different methods, we introduce a classic statistics algorithm for one-class classification: OC-SVM [14], which is implemented by LibSVM [15]. All algorithms run in a computer deployed with Intel Pentium E6600@3.06 G, while the implement of VorNSA refers to an open source toolbox of computational geometry, called MPT 3.0 [16].The Skin Segmentation dataset is a UCI dataset. It is collected by randomly sampling B, G, and R values of skin texture, which derives from FERET database and PAL database. Total sample size is 245,057 in which 50,859 records are the skin samples and 194,198 records are non-skin ones.In this experiment, 50 skin samples are randomly obtained as self-antigens. Meanwhile, to verify the performances of VorNSA and VorNSA/MR in large scale dataset, we use all 245,057 records in the datasets. The experiments are preformed 20 times independently, and the evaluation criteria include DR, FAR, detector number (DN), data training time (DT), and data testing time (DTT). The parameters of simulation are set as follows: the OC-SVM uses the RBF kernel functions, and nu is 0.5 and gamma is 0.33. The self-radius of RNSA, V-Detector, and VorNSA are set as the same value (0.1). The maximum number of detectors is 3000 in RNSA, and detector radius is 0.1. The estimated coverage and the maximum self-coverage are 99%. The maximum number of detectors is 1000 in BIORV-NSA, and the self-set edge inhibition parameter is 0.8 and the detector self-inhibition parameter is 1.2. The minimum radius of detectors is 0.005 in VorNSA and VorNSA/MR. The results of experiments are shown in Table3.Table 3
Results in skin segmentation.
Algorithm
DR (%)
FAR (%)
DN
DT (s)
DTT (s)
Mean
SD
Mean
SD
Mean
SD
Mean
SD
Mean
SD
OC-SVM
99.09
0.7
51.20
6.67
—
—
—
—
—
—
RNSA
98.42
0.63
0.66
1.48
3000.00
0
8.68
0.13
7501.59
400.49
V-Detector
99.05
0.27
1.31
1.22
469.85
174.66
32.12
23.86
948.55
325.50
BIORV-NSA
99.42
0.34
3.29
2.72
1000.00
0
20.00
0.11
1919.83
59.46
VorNSA
99.20
0.16
1.48
1.49
172.25
11.06
1.91
0.77
671.15
89.36
VorNSA/MR∗
99.43
0.24
1.56
1.37
176.90
11.96
1.79
0.07
426.70
31.97
∗The VorNSA/MR is deployed at 2 nodes: one is Intel Pentium E6600@3.06 G (2 Core); the other is Inter Core i5-2450M@2.5 G (2 Core).From Table3, it can be seen that the FAR of OC-SVM is 51.2%, reaching an unacceptable level. As OC-SVM implemented in a different platform, the time consumption is not counted in this paper. The DR of VorNSA (99.2%) is closed to the BIORV-NSA (99.42%), and better than the classic NSAs. Besides, the FAR of VorNSA (1.48%) is lower than BIORV-NSA (3.29%). It indicates that the detectors generated by VorNSA are more applicable than BIORV-NSA and more effective than classic NSAs.Moreover, the DN, DT, and DTT of VorNSA are significantly lower than other NSAs, especially when it integrates the Map-Reduce Testing Framework. For example, the average number of detectors generated by VorNSA is 172.25, lower 63.3% by V-Detector and 82.8% by BIORV-NSA. The average training time of VorNSA is 1.91, lower 78% by RNSA, 94.1% by V-Detector, and 90.5% by BIORV-NSA. So the efficiency of VorNSA is averagely decreased by 87.5% compared with traditional NSAs. The testing time of VorNSA/MR is 426.7, lower 36.4% by VorNSA, 55% by V-Detector, 77.8% by BIORV-NSA, and 94.3% by RNSA.The main reasons of above results can be explained as follows. In traditional NSAs, a large number of immature detectors are randomly generated without any optimal way and must self-tolerate with all self-antigens to decide whether they are matured or not. As a result, much time has been wasted. The scheme of detector generation of VorNSA is quite different with other NSAs. The optimal position of detectors is directly calculated. Thus, the time consumption on discarding many randomly generated but inappropriate detectors is avoided.


## 5. Conclusions

In this paper, we propose a new one-class classification algorithm based on Voronoi diagrams (VorNSA) and an immune detection process of VorNSA under Map/Reduce framework (VorNSA/MR) to cope with the challenge of big data. VorNSA alters the generative mechanism of detector from the “Random-Discard” model to the “Computing-Designated” model. VorNSA/MR can divide the sample set into several small parts and can be processed in parallel. Theoretical analyses show that the time complexity of VorNSA decreases from the exponential level to the logarithmic level. Experiments results show that the time consumption of VorNSA is significantly declined.



---

*Source: 3956415-2017-06-12.xml*