# A Clone Selection Based Real-Valued Negative Selection Algorithm

Authors: Ruirui Zhang; Xin Xiao
Journal: Complexity
 (2018)

---

## Abstract

Excessive detectors, high time complexity, and loopholes are main problems which current negative selection algorithms have face and greatly limit the practical applications of negative selection algorithms. This paper proposes a real-valued negative selection algorithm based on clonal selection. Firstly, the algorithm analyzes the space distribution of the self set and gets the set of outlier selves and several classification clusters. Then, the algorithm considers centers of clusters as antigens, randomly generates initial immune cell population in the qualified range, and executes the clonal selection algorithm. Afterwards, the algorithm changes the limited range to continue the iteration until the non-self space coverage rate meets expectations. After the algorithm terminates, mature detector set and boundary self set are obtained. The main contributions lie in (1) introducing the clonal selection algorithm and randomly generating candidate detectors within the stratified limited ranges based on clustering centers of self set; generating big-radius candidate detectors first and making them cover space far from selves, which reduces the number of detectors; then generating small-radius candidate detectors and making them gradually cover boundary space between selves and non-selves, which reduces the number of holes; (2) distinguishing selves and dividing them into outlier selves, boundary selves, and internal selves, which can adapt to the interference of noise data from selves; (3) for anomaly detection, using mature detector set and boundary self set to test at the same time, which can effectively improve the detection rate and reduce the false alarm rate. Theoretical analysis and experimental results show that the algorithm has better time efficiency and detector generation quality according to classic negative selection algorithms.


---

## Body

## 1. Introduction

The negative selection algorithm (NSA) first proposed by American scholar Forrest [1] is one of the most important anomaly detection algorithms in artificial immune field. The idea of negative selection algorithm comes from the negative selection behavior of T lymphocytes in immune tolerance of thymus [2]. An immune explanation for this behavior is as follows. In the thymus tolerance issue, T lymphocytes which identify self antigens will be in apoptosis or inactivated, and those cells which do not identify selves will mature after a period of tolerance and exercise their immune function in peripheral lymphoid tissues. The proposition of negative selection algorithm greatly promotes research and application in the anomaly detection field of artificial immune systems. Specifically, the idea of negative selection algorithm is often applied in these areas such as fault detection, virus detection, network intrusion detection, and machine learning [2–4].The negative selection algorithm put forward by Forrest used binary string to represent antigen and antibody adopted r-continuous matching rule to compute matching degree between antibody and antigen and was successfully applied to anomaly detection system. Then, Balthrop et al. [5] pointed out holes of r-continuous matching rule and put forward the improved r-chunk matching mechanism. Zhang [6] proposed r-variable negative selection algorithm, and He [7] proposed negative selection algorithm with variable-length detectors.But the binary representation has insufficiency in dealing with numeric data and multidimensional space problems; Gonzalez and Dasgupta [8] proposed a real-valued negative selection algorithm with position-developed detectors (RNSA). The study of real-valued negative selection algorithm is introduced in the following. The work in [9] introduced the super ellipsoid detector into the negative selection algorithm, the work in [10] introduced the super rectangle detector, and they needed less detectors to achieve the same coverage compared to spherical detectors. Ji [11] and Ji and Dasgupta [12] put forward a variable-sized real-valued negative selection algorithm (V-Detector). The algorithm dynamically determined the radius of a mature detector by calculating the smallest distance between the center of candidate detector and the self antigen. The work in [13, 14] proposed a negative selection algorithm based on grid. The algorithms adopted certain method to divide space into several grids, which reduced the tolerance range of randomly generated candidate detectors. The work in [15] proposed a negative selection algorithm based on hierarchical clustering of self sets, which improved the coverage rate of non-self space for detectors through the self set preprocessing. The work in [16] divided detectors into self detectors and non-self detectors which cover self space and non-self space, respectively, and used self detector instead of self elements to reduce the computational cost.Some studies introduced other artificial intelligence technologies into the negative selection algorithm to improve the efficiency of detector generation. The work in [17–19] proposed a negative selection algorithm based on genetic principles. The work in [20] combined particle swarm optimization strategy and the negative selection algorithm. The work in [21] introduced the wavelet transform to the negative selection algorithm.Many problems in negative selection algorithms such as the representation of detectors, the affinity calculation method, and detector generation mechanisms were studied. There are many achievements, but some problems have not been solved effectively.(  1) Loopholes. Loopholes generally refer to all the non-self space which is not covered by detectors in the negative selection algorithms and can be specifically divided into two categories: the first kind of vulnerability is the non-self space which cannot be covered by detectors in theory due to restricted detector coding and implementation way; the second is the non-self space which is not covered by detectors but theoretically feasible. Figure 1 illustrates two kinds of holes when the detector size is immutable.Figure 1
Two kinds of holes.In order to obtain good detection performance, it is necessary to reduce loopholes. For the first kind of holes, regardless of specific differences of detector representations (binary string or real value expression), there are two main solutions: one is the variable detector shape scheme [9, 10] and the second is variable detector size scheme [11, 12]. As shown in Figure 2, two schemes can eliminate the first kind of vulnerability in theory. Although the first solution is possible in theory, its implementation is very difficult. In comparison, the second solution is more feasible, and its concrete implementation effect is better [11–16].Figure 2
Solutions for the first kind of holes.For the second kind of loopholes, there are two solutions at present. One is the exhaustive method to generate all the detectors [22], and the second is to randomly generate detectors which satisfy certain requirements [11, 12]. Main problems of the first solution include the high time complexity and excessive detectors. It can only be applied to the situation that the number of detectors may be limited and cannot be used in many practical applications (for instance, detectors use real-valued coding, and the number is unlimited as a result). The second solution is widely used in the practical applications, but the scheme has random uncertain problems and cannot completely eliminate the existence of loopholes. While the second type of vulnerability can be covered by detectors in theory, the effective covering of holes which locate in the areas between self and non-self space is very difficult. Figure 3 shows a schematic diagram. In the figure, the self space is expressed by a self element, and it can be found that, even in the simplest environment, using a finite number of detectors cannot completely cover all the loopholes in the second category in theory.Figure 3
A situation of the second type of holes.(  2) Too Many Detectors. The work in [11, 22] pointed out that, in the negative selection algorithm proposed by Forrest et al., the detector generation efficiency is very low. Candidate detectors become mature by negative selection. It is assumed that Ns is the size of self training set, P′ is the matching probability between any antigen and antibody, and Pf is the failure rate (the probability of a non-self antigen cannot be matched by any antibody). The number of candidate detectors is Nc=-ln⁡(Pf)/(P′1-P′Ns), and the algorithm’s time complexity is O(Nc∙Ns). Therefore, with the increase of the size of the training set, the number of candidate detectors increases exponentially, the time cost in detector generation phase is higher, and the time cost in detection phase is higher as well. In addition, excessive detectors can cause redundant cover between detectors. Some negative selection algorithms made mature detectors to merge or cluster, which formed big-radius detectors instead of original detectors [19].(  3) Contradiction between Detection Rate and False Alarm Rate. For anomaly detection, high detection rate and low false alarm rate are two directions. Existing negative selection algorithms focused on improving the efficiency of detector generation in order to cover the non-self space as much as possible. They did not consider the balance of the detection rate and the false alarm rate, which lacked a good adjustment mechanism of the two rates. The classic algorithm V-Detector [11, 12] proposed two solutions, which were point-aware and boundary-aware, respectively. The two solutions have problems. The detection rate of point-aware solution is low, and the false alarm rate of boundary-aware solution is too high.(  4) Not Considering Noise Data in Self Training Set. In many anomaly detection applications, self training set contains noise data. And negative selection algorithms are on the basis of reliable training data; it is widespread that they cannot adapt to the existence of noise data.How to generate efficient detector set is the key to the negative selection algorithms. This paper proposes a real-valued negative selection algorithm based on clonal selection, named CB-RNSA. The main contributions lie in(1) introducing the clonal selection algorithm and randomly generating candidate detectors within the stratified limited ranges based on clustering centers of self set; generating big-radius candidate detectors first and making them cover space far from selves, which reduces the number of detectors; then generating small-radius candidate detectors and making them gradually cover boundary space between selves and non-selves, which reduces the number of holes; (2) distinguishing selves and dividing them into outlier selves, boundary selves, and internal selves, which can adapt to the interference of noise data from selves; (3) for anomaly detection, using mature detector set and boundary self set to test at the same time, which can effectively improve the detection rate and reduce the false alarm rate.In this paper, the rest of the sections are arranged as follows. The second section introduces the background of this paper, including the typical real-valued negative selection algorithm RNSA, the variable-sized real-valued negative selection algorithm (V-Detector), and immune theory-clonal selection algorithm. The third section introduces the implementation strategies of the algorithm, including the basic idea, outlier selves discovery mechanism, cluster discovery mechanism, clonal selection mechanism, etc. The fourth section analyzes the algorithm, including time complexity analysis and detector self-reaction rate analysis. The fifth section verifies the effectiveness of the algorithm through experiments which use 2D comprehensive data sets and UCI data sets and compare with classic negative selection algorithms. Conclusions are given in the sixth section.


## 2. Related Work

### 2.1. Basic Concepts of NSA

The system state can be expressed by the feature vectorx=(x1,x2,…,xn).n is the system dimension, and each feature of the vector is normalized to the real-valued interval [0,1]. The entire state space of the system can be expressed as Ω=0,1n. The system state space can be further divided into self spaceSelf and non-self spaceNonself. In anomaly detection, self spaceSelf is composed of states when the system is normal, and non-self spaceNonself consists of states when the system is abnormal.In artificial immune systems, antigens are on behalf of the entire state of the system, the self set represents self space of the system, and the non-self set represents non-self space, which are defined respectively as follows.Definition 1 (antigens).
A g = {ag∣ag = x,rs= x1,x2,…,xn,rs, xi∈ [0,1], 1 ≤ i ≤ n, rs∈[0,1]} represents all the samples in the space. The parameter ag is an antigen in the set and consists of two parts, x and rs. The parameter x is the position of sample ag in the real-valued space. The parameter rs is the radius of ag and represents change threshold. Therefore, ag is a hypersphere in space.Definition 2 (self set).
S e l f ⊂ A g represents all the normal samples in the antigen set. Self = {ag∣ag⊂Ag∩agisnormal}.Definition 3 (non-self set).
Nonself ⊂ A g represents all the abnormal samples in the antigen set.Nonself = {ag∣ag⊂Ag∩agisabnormal}. The self/non-self has different meanings in different areas. For network intrusion detection, non-self represents network anomalies, and self represents normal network activities. For virus detection, non-self represents virus signatures, and self represents legal codes.SelfandNonself meet (1).(1)Self∩Nonself=∅,Self∪Nonself=AgDefinition 4 (training set).
T r a i n ⊂ S e l f is a subset ofSelf and is the a priori knowledge for testing.Definition 5 (detector set).
={d∣d = y,rd= y1,y2,…,yn,rd, yj∈[0,1], 1 ≤ j ≤ n, rd∈ [0,1]}. The parameter d is one of the elements from the detector set, and its structure is the same as antigen which consists of two parts,y and rd, respectively. The parameter y represents the position of detectord, and the parameter rd is the radius of detectord.Definition 6 (matching rule).
f(ag, d) represents the affinity between antigen ag and detectord, that is, the matching degree between data structures. In real-valued space, we can measure the affinity by calculating the distance between two feature vectors, which is usually expressed by Minkowski distance. For two vectors x and y inn-dimensional space,m-order Minkowski distance function is as (2)fdag,d=∑i=1nxi-yim1/mMinkowski distance is often called them-order norm. For real-valued negative selection algorithms, it is thought that, for different values ofm, test range of detectors has different geometry. This paper adopts the 2-order norm to express the matching rule, namely, the Euclidean distance. Then, (2) is rewrote as(3)fag,d=∑i=1nag.xi-d.yi2Definition 7 (detection system).
DS consists of three parts, namely, DS=(D,Self,f). In the process of detector generation, iff(ag, d) ≤ rs+ rd, detector d causes the immune self-reaction and cannot be a mature detector. In the process of detector testing, iff(ag, d) ≤ rd, detector d recognizes ag as a non-self. It is assumed that A is mapping from self setSelf and candidate detector d to a classification {0,1}, where 0 indicates that d is immature, and 1 means that d is mature.A is such a function as (4)ASelf,d=0,∃ag′∈Self,fd,ag′≤rs+rd1,otherwiseSupposeB is mapping from detector set D and antigen ag to be identified to a classification {0,1}, where 0 indicates that ag is self, and 1 means that ag is non-self.B is such a function as (5)BD,ag=1,∃d′∈D,fd′,ag≤rd0,otherwiseWhen the detection system is working,TP is set as correct positive, that is, the number of non-selves correctly recognized by detectors;TN is set as correct negative, that is, the number of selves correctly recognized by detectors. Two kinds of errors may occur. False positiveFP happens when a self sample is identified as a non-self. False negativeFN occurs when a non-self sample is identified as a self. They can be defined as follows. Given a test set, Utest⊏Ag which consists of two sets, selfStest and non-selfNtest. WhenFP happens, the pattern collection ε+ can be defined as (6)ε+=ag∣ag∈Stest∧BD,ag=1WhenFN happens, the pattern collection ε- can be defined as (7)ε-=ag∣ag∈Ntest∧BD,ag=0WhenTP happens, the pattern collection ζ+ can be defined as (8)ζ+=ag∣ag∈Ntest∧BD,ag=1WhenTN happens, the pattern collection ζ- can be defined as (9)ζ-=ag∣ag∈Stest∧BD,ag=0Definition 8 (detection rate).
DR is the ratio of the number of non-self samples being correctly identified by detectors to the total number of non-selves and is expressed as (10)DR=TPTP+FNDefinition 9 (false alarm rate).
F A R is the ratio of the number of self samples being wrongly identified by detectors to the total number of selves and is expressed as (11)FAR=FPFP+TN


### 2.2. RNSA

The artificial immune system removes those immune cells which respond to selves through the negative selection algorithm, so as to realize the self tolerance. RNSA adopts real-valued vector to describe the configuration space and uses fixed-size detectors. The termination condition of the algorithm is reaching the default number of detectors [8]. Algorithm 1 shows the process of the negative selection algorithm.Algorithm 1:The process of RNSA.
Procedure. The negative selection algorithm RNSA Begin Generate a large number of candidate detectors at random; While a given size detector set has not been generated do Calculate affinities between the candidate detector and every self element; If the candidate matches any element of self set; Then clear the candidate; Else put the candidate in the detector set; End; Use the collection of resistant detectors to test abnormal variations; End.Figure4 shows the relationships between the self set, the non-self set, the detector set, etc. Ag is the antigen space; Ud is the detector space. Although in many cases Ag=Ud, we draw them, respectively, in order to describe clearly.Self is the self set,Nonself is the non-self set,CD is the candidate detector set,D is the detector set which is selected fromCD,NonselfCD is non-selves which are identified by candidate detectors, andNonselfD is non-selves which are identified by detectors. Therefore, collection of holes isNonself-NonselfCD, and collection of non-selves which cannot be tested by detectors isNonself-NonselfD.Figure 4
Relationships between sets.


### 2.3. V-Detector

V-Detector uses vectors in real-valued space to express detectors and antigens, and the radius of detectors is variable [11, 12]. Firstly, the algorithm randomly generates the center y of the candidate detectord =y,rd and then calculates distancef(ag, d)between y and every self ag=x,rs in the training set. If min⁡(f(ag,d))>rs, accept the detector. The radius of the detector is calculated by the following formula:(12)rd=min⁡fag,d-rs,ifpoint-awaremin⁡fag,d,ifboundary-awarePoint-aware and boundary-aware are two technologies to determine detector radius. The algorithm of boundary-aware has high detection rate and high false alarm rate. This is because the boundary-aware makes detection range of detectors and coverage of some selves overlap. Non-self space is basically covered, which improves the detection rate, but is contrary to the assumptions of negative selection algorithm “vectors close to selves are selves, and vectors far from selves are non-selves [1, 11]”, which can lead to high false alarm rate. Therefore, this article uses the point-aware technology.Figure5 shows the contrast of RNSA and V-Detector when the expectation coverage is 50%. The self data are top 25 elements of classification “Iris-versicolor” from IRIS data set [23]. In order to display conveniently in two-dimensional space, we take the element’s sepalL and sepalW as self antigen’s properties. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. In RNSA, the detector size is constant and is difficult to determine accurately, which causes many loopholes in the non-self space and low detection rate. In V-Detector, the detector size is variable, and the algorithm makes big detectors cover most of the non-self space and small detectors cover holes, which not only reduces the number of detectors, but also reduces the number of vulnerabilities. But, these two algorithms have faced problems proposed in the introduction section, such as loopholes which influence the detection rate, too many candidate detectors, redundant cover between mature detectors, and high time cost of testing.Figure 5
Contrast of RNSA and V-Detector.


### 2.4. Clonal Selection Algorithm

Clonal selection principle is used to illustrate basic features of the immune response to antigen stimulation in the immune system [24–26]. When external bacteria or virus invades the body, B cells begin to a large number of cloning and destroy invaders. Those cells who can identify antigens will achieve the purpose of hyperplasia by asexual reproduction according to the degree of recognition. The higher the affinity between cells and antigens is, the more cells can produce offspring. In the process of cell division, individual cells also experience a variation process, which results in higher affinity with antigens; the higher the affinity between parent cells and antigens is, the less parent cells experience variation. Algorithm 2 shows the process of clonal selection algorithm.Algorithm 2:The process of clonal selection algorithm.
Procedure. Clonal selection algorithm Begin Randomly generate a population of immune cells; While not meet the convergence condition do While not search all antigens do Choose those cells which have high affinity with antigen; Generate copies of immune cells; the higher the affinity is, the more copies are. Mutate according to the affinity; the higher the affinity is, the smaller the variation is; End; End; End.


## 2.1. Basic Concepts of NSA

The system state can be expressed by the feature vectorx=(x1,x2,…,xn).n is the system dimension, and each feature of the vector is normalized to the real-valued interval [0,1]. The entire state space of the system can be expressed as Ω=0,1n. The system state space can be further divided into self spaceSelf and non-self spaceNonself. In anomaly detection, self spaceSelf is composed of states when the system is normal, and non-self spaceNonself consists of states when the system is abnormal.In artificial immune systems, antigens are on behalf of the entire state of the system, the self set represents self space of the system, and the non-self set represents non-self space, which are defined respectively as follows.Definition 1 (antigens).
A g = {ag∣ag = x,rs= x1,x2,…,xn,rs, xi∈ [0,1], 1 ≤ i ≤ n, rs∈[0,1]} represents all the samples in the space. The parameter ag is an antigen in the set and consists of two parts, x and rs. The parameter x is the position of sample ag in the real-valued space. The parameter rs is the radius of ag and represents change threshold. Therefore, ag is a hypersphere in space.Definition 2 (self set).
S e l f ⊂ A g represents all the normal samples in the antigen set. Self = {ag∣ag⊂Ag∩agisnormal}.Definition 3 (non-self set).
Nonself ⊂ A g represents all the abnormal samples in the antigen set.Nonself = {ag∣ag⊂Ag∩agisabnormal}. The self/non-self has different meanings in different areas. For network intrusion detection, non-self represents network anomalies, and self represents normal network activities. For virus detection, non-self represents virus signatures, and self represents legal codes.SelfandNonself meet (1).(1)Self∩Nonself=∅,Self∪Nonself=AgDefinition 4 (training set).
T r a i n ⊂ S e l f is a subset ofSelf and is the a priori knowledge for testing.Definition 5 (detector set).
={d∣d = y,rd= y1,y2,…,yn,rd, yj∈[0,1], 1 ≤ j ≤ n, rd∈ [0,1]}. The parameter d is one of the elements from the detector set, and its structure is the same as antigen which consists of two parts,y and rd, respectively. The parameter y represents the position of detectord, and the parameter rd is the radius of detectord.Definition 6 (matching rule).
f(ag, d) represents the affinity between antigen ag and detectord, that is, the matching degree between data structures. In real-valued space, we can measure the affinity by calculating the distance between two feature vectors, which is usually expressed by Minkowski distance. For two vectors x and y inn-dimensional space,m-order Minkowski distance function is as (2)fdag,d=∑i=1nxi-yim1/mMinkowski distance is often called them-order norm. For real-valued negative selection algorithms, it is thought that, for different values ofm, test range of detectors has different geometry. This paper adopts the 2-order norm to express the matching rule, namely, the Euclidean distance. Then, (2) is rewrote as(3)fag,d=∑i=1nag.xi-d.yi2Definition 7 (detection system).
DS consists of three parts, namely, DS=(D,Self,f). In the process of detector generation, iff(ag, d) ≤ rs+ rd, detector d causes the immune self-reaction and cannot be a mature detector. In the process of detector testing, iff(ag, d) ≤ rd, detector d recognizes ag as a non-self. It is assumed that A is mapping from self setSelf and candidate detector d to a classification {0,1}, where 0 indicates that d is immature, and 1 means that d is mature.A is such a function as (4)ASelf,d=0,∃ag′∈Self,fd,ag′≤rs+rd1,otherwiseSupposeB is mapping from detector set D and antigen ag to be identified to a classification {0,1}, where 0 indicates that ag is self, and 1 means that ag is non-self.B is such a function as (5)BD,ag=1,∃d′∈D,fd′,ag≤rd0,otherwiseWhen the detection system is working,TP is set as correct positive, that is, the number of non-selves correctly recognized by detectors;TN is set as correct negative, that is, the number of selves correctly recognized by detectors. Two kinds of errors may occur. False positiveFP happens when a self sample is identified as a non-self. False negativeFN occurs when a non-self sample is identified as a self. They can be defined as follows. Given a test set, Utest⊏Ag which consists of two sets, selfStest and non-selfNtest. WhenFP happens, the pattern collection ε+ can be defined as (6)ε+=ag∣ag∈Stest∧BD,ag=1WhenFN happens, the pattern collection ε- can be defined as (7)ε-=ag∣ag∈Ntest∧BD,ag=0WhenTP happens, the pattern collection ζ+ can be defined as (8)ζ+=ag∣ag∈Ntest∧BD,ag=1WhenTN happens, the pattern collection ζ- can be defined as (9)ζ-=ag∣ag∈Stest∧BD,ag=0Definition 8 (detection rate).
DR is the ratio of the number of non-self samples being correctly identified by detectors to the total number of non-selves and is expressed as (10)DR=TPTP+FNDefinition 9 (false alarm rate).
F A R is the ratio of the number of self samples being wrongly identified by detectors to the total number of selves and is expressed as (11)FAR=FPFP+TN


## 2.2. RNSA

The artificial immune system removes those immune cells which respond to selves through the negative selection algorithm, so as to realize the self tolerance. RNSA adopts real-valued vector to describe the configuration space and uses fixed-size detectors. The termination condition of the algorithm is reaching the default number of detectors [8]. Algorithm 1 shows the process of the negative selection algorithm.Algorithm 1:The process of RNSA.
Procedure. The negative selection algorithm RNSA Begin Generate a large number of candidate detectors at random; While a given size detector set has not been generated do Calculate affinities between the candidate detector and every self element; If the candidate matches any element of self set; Then clear the candidate; Else put the candidate in the detector set; End; Use the collection of resistant detectors to test abnormal variations; End.Figure4 shows the relationships between the self set, the non-self set, the detector set, etc. Ag is the antigen space; Ud is the detector space. Although in many cases Ag=Ud, we draw them, respectively, in order to describe clearly.Self is the self set,Nonself is the non-self set,CD is the candidate detector set,D is the detector set which is selected fromCD,NonselfCD is non-selves which are identified by candidate detectors, andNonselfD is non-selves which are identified by detectors. Therefore, collection of holes isNonself-NonselfCD, and collection of non-selves which cannot be tested by detectors isNonself-NonselfD.Figure 4
Relationships between sets.


## 2.3. V-Detector

V-Detector uses vectors in real-valued space to express detectors and antigens, and the radius of detectors is variable [11, 12]. Firstly, the algorithm randomly generates the center y of the candidate detectord =y,rd and then calculates distancef(ag, d)between y and every self ag=x,rs in the training set. If min⁡(f(ag,d))>rs, accept the detector. The radius of the detector is calculated by the following formula:(12)rd=min⁡fag,d-rs,ifpoint-awaremin⁡fag,d,ifboundary-awarePoint-aware and boundary-aware are two technologies to determine detector radius. The algorithm of boundary-aware has high detection rate and high false alarm rate. This is because the boundary-aware makes detection range of detectors and coverage of some selves overlap. Non-self space is basically covered, which improves the detection rate, but is contrary to the assumptions of negative selection algorithm “vectors close to selves are selves, and vectors far from selves are non-selves [1, 11]”, which can lead to high false alarm rate. Therefore, this article uses the point-aware technology.Figure5 shows the contrast of RNSA and V-Detector when the expectation coverage is 50%. The self data are top 25 elements of classification “Iris-versicolor” from IRIS data set [23]. In order to display conveniently in two-dimensional space, we take the element’s sepalL and sepalW as self antigen’s properties. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. In RNSA, the detector size is constant and is difficult to determine accurately, which causes many loopholes in the non-self space and low detection rate. In V-Detector, the detector size is variable, and the algorithm makes big detectors cover most of the non-self space and small detectors cover holes, which not only reduces the number of detectors, but also reduces the number of vulnerabilities. But, these two algorithms have faced problems proposed in the introduction section, such as loopholes which influence the detection rate, too many candidate detectors, redundant cover between mature detectors, and high time cost of testing.Figure 5
Contrast of RNSA and V-Detector.


## 2.4. Clonal Selection Algorithm

Clonal selection principle is used to illustrate basic features of the immune response to antigen stimulation in the immune system [24–26]. When external bacteria or virus invades the body, B cells begin to a large number of cloning and destroy invaders. Those cells who can identify antigens will achieve the purpose of hyperplasia by asexual reproduction according to the degree of recognition. The higher the affinity between cells and antigens is, the more cells can produce offspring. In the process of cell division, individual cells also experience a variation process, which results in higher affinity with antigens; the higher the affinity between parent cells and antigens is, the less parent cells experience variation. Algorithm 2 shows the process of clonal selection algorithm.Algorithm 2:The process of clonal selection algorithm.
Procedure. Clonal selection algorithm Begin Randomly generate a population of immune cells; While not meet the convergence condition do While not search all antigens do Choose those cells which have high affinity with antigen; Generate copies of immune cells; the higher the affinity is, the more copies are. Mutate according to the affinity; the higher the affinity is, the smaller the variation is; End; End; End.


## 3. The Algorithm Theory

### 3.1. The Process of the Algorithm

The main idea of the algorithm is as follows. Firstly, the algorithm analyzes the space distribution of the self set and gets the set of outlier selves and several classification clusters. Then, the algorithm considers centers of clusters as antigens, randomly generates initial immune cell population in the qualified range, and executes the clonal selection algorithm. That is to say, the algorithm carries out the immune selection operation, clonal amplification operation, and hypermutation operation on the immune cell population. The affinity between antigens and immune cells is inversely proportional to their distance, and the convergence condition of clone selection algorithm is to achieve the expected coverage of non-self space. At this point, the finite range for generating immune cells is far from self space, where the coverage rate is low. At the end of the clonal selection algorithm, immune cell population is viewed as candidate detectors of the first level. The radius of the candidate detector is dynamically determined by computing the distance between its center and the closest self, and then the candidate detector joins the mature detector set through tolerance. In addition, the algorithm adds selves which are closest to detectors into boundary self set. The candidate detectors of this level have biggest radius and cover non-self space away from selves. Afterwards, the algorithm changes the limited scope to make the range of next level more convergent. The algorithm continues to consider centers of clusters as antigens, randomly generates initial immune cell population in the qualified scope, and executes the clonal selection algorithm. When the clonal selection algorithm ends, immune cell population is the candidate detectors of the second level. The candidate detectors of this level have larger radius, are close to detectors of the first level, and cover the non-self space a bit near selves. Then repeat the process until candidate detectors cover non-self space close to selves which are, namely, the boundary areas between self space and non-self space. When the algorithm terminates, mature detector set and boundary self set are obtained. Algorithm3 shows the process of CB-RNSA.Algorithm 3:The process of CB-RNSA.
Procedure. CB-RNSA Input: self training setTrain, expected coverage ratep0 Output: detector setD, boundary self set Selfo, outlier self set Selfd n 0: the sampling frequency of non-self space, n0>max⁡(5/p0,5/(1-p0)) i: the number of non-self samples m: the number of non-self samples which are covered by detectors C D: candidate detector set CD = {d∣d = y,rd = y1,y2,…,yn,rd, yj∈[0,1], 1≤j≤n,  rd∈[0,1]} Clusters: cluster set Clusters= {cluster} l: the number of candidate detector level Begin Initialize self training set Train, i= 0, m= 0, CD=∅, Selfo=∅, n0 = max⁡(5/p0,5/(1-p0)); Initialize outlier self set Selfd according to Procedure outlier selves discovery algorithm; Initialize cluster set Clustersaccording to Procedure clusters discovery algorithm; While l does not reach the maximum number of levels for candidate detectors do Consider centers of Clustersas antigens, randomly generate initial immune cell population in the qualified range; While true do Select immune cells; Generate copies of immune cells; Mutate according to affinities; Compute distances between mutated individual dnew and every self in the training set Train; If dnew is recognized by some self Then discard dnew; Else Find the closest self ag to dnew, and add it to boundary self set Selfo; i ++; Compute distances between dnew and every detector in the detector set D; If dnew is not identified by any detector Then put it into the candidate detector set CD; Else m ++; End if; If the number of non-self samples i reaches the sample times n0 Then Compute current coverage rate p; If p reaches the expected coverage rate p0, break; Else incorporate candidate detector set CD with D, reset i, m, CD; End if; End; l++; Changes the limited range of candidate detectors; End; End.The main contributions lie in(1) introducing the clonal selection algorithm and randomly generating candidate detectors within the stratified limited ranges based on clustering centers of self set; generating big-radius candidate detectors first and making them cover space far from selves, which reduces the number of detectors; then generating small-radius candidate detectors and making them gradually cover boundary space between selves and non-selves, which reduces the number of holes; (2) distinguishing selves and dividing them into outlier selves, boundary selves, and internal selves, which can adapt to the interference of noise data from selves; (3) for anomaly detection, using mature detector set and boundary self set to test at the same time, which can effectively improve the detection rate and reduce the false alarm rate. Theoretical analysis and experimental results show that the algorithm has better time efficiency and detector generation quality according to classic negative selection algorithms.Figures6 and 7 show the contrast between CB-RNSA, RNSA, and V-Detector. The self data are top 25 elements of classification “Iris-versicolor” from IRIS data set [23]. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. In RNSA and V-Detector, with rise of coverage rate, redundant cover between mature detectors in non-self space increases, which causes excessive detector quantity and unnecessary self tolerance. In CB-RNSA, because the clonal selection algorithm is introduced to limit the range of randomly generated candidate detectors, it is preferred that detectors are generated in space of low coverage, which reduces the number of detectors and redundancy.Figure 6
Contrast between CB-RNSA, RNSA, and V-Detector (five mature detectors are produced at the same time).Figure 7
Contrast between CB-RNSA, RNSA, and V-Detector (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 357, 81, and 35 mature detectors, respectively, where the self radius is 0.05, and the detector radius of RNSA is 0.05).


### 3.2. Classification of Selves

Most of the negative selection algorithms do not distinguish between selves. But for the continuous space of selves, information within different self is different. We divide selves into three groups, outlier selves, boundary selves, and internal selves, as shown in Figure8. Magenta filled circles are outlier selves, cyan filled circles are boundary selves, and blue filled circles are internal selves.Figure 8
Self classification.Suppose the collection of elementsNei(ag, r) whose distance with self ag is less than r is expressed as (13), and they are called neighbors.(13)Neiag,r=ag′∣ag′∈Self∧fag,ag′<rDefinition 10 (outlier self set).
S e l f d ⊂ S e l f. The outliers may be caused by noise data. Selfd={ag∣ag∈Self∧|Neiag,r|<ρ∙|Self|} means that when the number of neighbors of a self is less than a certain value, the self is classified as an outlier. ρ is the parameter for outlier.Definition 11 (boundary self set).
S e l f o ⊂ S e l f, and they are distributed in edges of self space and non-self space. The boundary self quantity is far less than the number of internal selves, and a lot of false positives and omissions appear in the borders. Because self space and non-self space are complementary, we use detector set to define boundary self set; that is to say, the self which is closest to a detector is boundary. Selfo={ag|ag∈Self∧(∃d∈D,fag,d=min⁡(∀ag′∈Self,fag′,d))}.Definition 12 (internal self set).
S e l f i ⊂ S e l f, and they are surrounded by boundary selves. Selfi=Self-Selfd-Selfo.


### 3.3. Outlier Selves Discovery Mechanism

As one of the important research fields of knowledge discovery, there are many effective outlier detection algorithms at present [27–29]. This paper adopts the algorithm based on distance proposed by Knorr [27], and Algorithm 4 shows the process of the algorithm.Algorithm 4:The process of outlier selves discovery algorithm.
Procedure. Outlier selves discovery algorithm Input: the self training setTrain Output: outlier self setSelfd Begin While self ag is not detected do m = 0; for other self ag′ in the self training set Train do Compute the distance between ag and ag′f(ag, ag′); If f(ag, ag′) < rthen m++; End; If m<ρ∙|Self|then add ag into the outlier self set Selfd; End; End.


### 3.4. Clusters Discovery Mechanism

In anomaly detection, it is thought that most of these data are normal, and abnormal data are the minority. In this paper, the algorithm first analyzes the space distribution of selves and performs a clustering pretreatment on the self set. Similar selves are classified in the same cluster, and then a number of clusters are generated. Centers of clusters are used as a benchmark to generate candidate detectors. The purpose of self set clustering is to determine the randomly generation scope of candidate detectors, and candidates are generated in the qualified range in order to avoid detector redundancy in high coverage.Definition 13 (cluster).
cluster = {c∣c = x,rc,C = x1,x2,…,xn,rc,{ag∣ag∈Self}, xi∈[0,1], 1 ≤ i ≤ n}. The parameter x is the center vector of the cluster inn-dimensional space, the parameter rc is the radius of the cluster, and the parameter C is the collection of selves within the cluster. rc is computed by the following formula:(14)cluster.rc=∑ag∈Self∑ag′∈Self-agfag,ag′Self∙Self-1The algorithm randomly selects a self as an initial element for a cluster at first and then judges whether any element in the cluster and other selfag are neighbors, that is to say, whether meeting ∃ag′∈Cluster.C,ag∈Nei(ag′,rc), if so, self ag will be within the cluster. After other selves are judged, if there is a self which does not belong to any cluster, that means Self-∑cluster′∈Clusters{ag∣ag∈cluster′.C}≠∅, the algorithm continues to randomly select a self as an initial element of a new cluster. The above operations are performed until all the selves belong to a cluster. The cluster center x is computed by the following formula (15). Algorithm 5 shows the process of clusters discovery algorithm.(15)cluster.xi=∑ag∈cluster.Cag.xinAlgorithm 5:The process of clusters discovery algorithm.
Procedure. Clusters discovery algorithm Input: the self training setTrain Output: cluster setClusters={cluster} Begin While self ag is not belong to any cluster do Generate a new cluster for ag; For other self ag′ in selves which are not classified do If ag′ is neighbor to any element in cluster, then put ag′ into cluster; End; End; End.


### 3.5. Clonal Selection Mechanism

Clonal selection algorithm is often used for solving the optimization problems. This paper adopts the clonal selection algorithm to search optimal detectors in the non-self space. The center of each cluster is viewed as an antigen. Initial immune cell population is randomly generated in limited scope, and the clonal selection algorithm is performed on the group. The limits control the position of vectorx of immune cell ag in each dimension and are defined as a super sphere loop based on the center of the clustercluster.x. The distance between immune cell and the center of the cluster should be limited between [rlow,rhigh], that means,rlow ≤f(ag,cluster) ≤rhigh.rlow is the minimum distance between immune cell and cluster center,rlow = 0, andrhigh is the maximum distance between these two,rhigh = n. Candidates will be generated by layer. According to the detector radius, from big to small, a detector of larger coverage will be in priority to be produced, to avoid repeated coverage with existing mature detectors and achieve less detectors covering as much as possible non-self area. Set level isl, and the limited scope of the l level is to meet (16), where the value of l should be satisfied (17); that is, max⁡(l)=log2⁡n/rs+1.(16)n2l≤fag,cluster≤n2l-1(17)n2l-1≥rsFigure9 shows limited scopes of the first level, second level, and third level of candidate detectors based on one of the clusters and generations of candidate detectors. Figure 10 shows limited scopes of the top three levels based on all the clusters and the generation of candidate detectors. Blue filled circles and green filled circles are self elements, cyan filled circles are mature detectors, and regions between two concentric dotted circles are the randomly generation scopes.Figure 9
Limited scopes and generations of candidate detectors (based on the cluster of blue filled circles).
(a) (b) (c)Figure 10
Limited scopes and generations of candidate detectors.
(a) (b) (c)In the clonal selection algorithm, the main operations include immune selectionTs, clonal amplification Tc, and hypermutation Tm. Immune selection operation is to choose a certain number of immune cells with high-affinity in order to search in more valuable space. In this algorithm, because immune cells should cover the non-self space as much as possible, it is not necessary to choose by affinity, and the population of all immune cells go into the next operation. Set AB as the population of immune cells and AB′ as the population after this operation, and the probability of selection is as (18)PTsAB=AB′=1Clonal amplification operation simulates cloning mechanism of the immune response, and the higher affinity with antigens the cell has, the more offspring the cell can produce. In this algorithm, the number of copiesncis related to the level l where candidate detector is.nc is computed by (19), wherencmax is the maximum number of copies andncmin is the minimum.(19)nc=ncmin+ncmax-ncmin1-1lThe above formula reflects the clone expansion scales for immune cells in different limited scopes. When the hierarchy is small, candidate detectors are in low-coverage areas and the radius is larger. We hope to cover more non-self space with less detectors, so the cloning scale is smaller. When the hierarchy is big, candidate detectors are in high coverage areas and the radius is smaller. We hope to cover holes in the boundary of self space and non-self space, so the cloning scale is larger.Hypermutation operation is to produce immune cells with higher affinity and enhance the diversity of the population. Mutation operator usually can produce small disturbance and can also produce a wide range of disturbance, which makes the mutation have abilities of local search and global search and makes the algorithm have stronger optimal search performance. In this paper, Gauss mutation is adopted and the formula is as(20)ag′.xi=ag.xi+α∙N0,1whereag′ is the mutated immune cell, N(0,1) is the Gaussian random variable, the mean is 0, and the deviation is 1. α is the control parameter to adjust the variation amplitude. In this paper, a dynamic adaptive α is adopted and only related to candidate detector level l. The mutation mechanism is as (21). In the process of the generation of candidate detectors, when the level is small, individuals search with larger probability, which is good for global search. When the level is large, individuals search with smaller probability, which is more conducive to local search.(21)α=11+el-k0k 0 is the cut-off point for α that means the cut-off for the algorithm from global search of big probability to local search of small probability.After immune cells perform mutation, they also need to meet (16). So, new cells should meet the formula, or they will be discarded. This will produce a large number of useless cells, which needs a large amount of calculations. Set ag.x as the origin, we use n-spherical coordinates to rewrite (16) by (22).(22)ag′.x1=ag.x1+ρ∙cos⁡θ1ag′.x2=ag.x2+ρ∙sin⁡θ1cos⁡θ2ag′.xn-1=ag.xn-1+ρ∙sin⁡θ1sin⁡θ2…cos⁡θn-1ag′.xn=ag.xn+ρ∙sin⁡θ1⁡sin⁡θ2…sin⁡θn-1where the parameterρ is random variable between [n/2l,n/2l-1], the parameters θ1,θ2,…,θn-2 are random variables between [0,π], and the parameter θn-1 is random variable between [0,2π]. They are expressed as (23), (24), and (25).(23)ρ=n2l+n2l-1-n2l∙α∙N0,1(24)θi=π∙α∙N0,11≤i≤n-2(25)θn-1=2π∙α∙N0,1


### 3.6. Anomaly Detection

Anomaly detection is used to determine whether data is abnormal. In this paper, the anomaly detection process combines the detector setD and boundary self set Selfo together for testing. So, we modify the definition ofB, and B is expressed as (26).B is mapping from detector setD, boundary self set Selfo, and antigen ag to be identified to a classification {0,1}, where 0 indicates that ag is self, and 1 means that ag is non-self.(26)BD,Selfo,ag=1,∃ag′∈Selfo,fag′,ag>rs⋀∃d∈D,fd,ag≤rd0,otherwise


### 3.7. Coverage Rate of Non-Self Space

The greater the coverage of detectors for the non-self space is, the greater the probability of detecting non-self is. Due to overlaps between detectors, direct calculation of coverage ratep for non-self space is very difficult. Monte Carlo method is used to calculate the approximate value p^. Suppose a randomly generated non-self set N∈Nonself, the calculation formula of non-self space coverage rate of detector set D is as (27)p=∫x→∈Ddx→∫x→∈Nonselfdx→≈p^=∑ag∈N∃d∈D,fd,ag≤rdNSetp0 as the target coverage rate. When the estimated value p^ is greater than or equal to p0, it is thought that detectors meet the requirements of the target coverage. Because p^ is a random variable, it is inevitable that the actual coverage rate p is less than p0. To reduce the probability of this situation, the algorithm introduces the hypothesis test for processing.Setα as the significance of hypothesis test, za as the α quantile of standard normal distribution, n0 as the sample size, and x as the number of samples covered by detectors. The calculating formula of maximumxmax is as (28)xmax=zαn0p01-p0+n0p0Obviouslyn0>xmax, then n0>zαn0p0(1-p0)+n0p0, that is, n0>p0zα2/(1-p0). In order to meet the requirements and make the estimated coverage rate p^=x/n0 approximately obey the normal distribution, the calculation formula of sample size n0 is as (29)n0=max⁡5p0,51-p0,p0zα21-p0Because5>p0zα2, the above equation can be rewriting as n0=max⁡(5/p0,5/(1-p0)).The actual coverage rate of detectors for the non-space isp, the null hypothesis of hypothesis testing H0 is “p=p0”, and the alternative hypothesis H1 is “p>p0”. In the process of the algorithm, if x is less than or equal toxmax, receive H0 and update detector set; if x is greater than thexmax, accept H1 and exit.


## 3.1. The Process of the Algorithm

The main idea of the algorithm is as follows. Firstly, the algorithm analyzes the space distribution of the self set and gets the set of outlier selves and several classification clusters. Then, the algorithm considers centers of clusters as antigens, randomly generates initial immune cell population in the qualified range, and executes the clonal selection algorithm. That is to say, the algorithm carries out the immune selection operation, clonal amplification operation, and hypermutation operation on the immune cell population. The affinity between antigens and immune cells is inversely proportional to their distance, and the convergence condition of clone selection algorithm is to achieve the expected coverage of non-self space. At this point, the finite range for generating immune cells is far from self space, where the coverage rate is low. At the end of the clonal selection algorithm, immune cell population is viewed as candidate detectors of the first level. The radius of the candidate detector is dynamically determined by computing the distance between its center and the closest self, and then the candidate detector joins the mature detector set through tolerance. In addition, the algorithm adds selves which are closest to detectors into boundary self set. The candidate detectors of this level have biggest radius and cover non-self space away from selves. Afterwards, the algorithm changes the limited scope to make the range of next level more convergent. The algorithm continues to consider centers of clusters as antigens, randomly generates initial immune cell population in the qualified scope, and executes the clonal selection algorithm. When the clonal selection algorithm ends, immune cell population is the candidate detectors of the second level. The candidate detectors of this level have larger radius, are close to detectors of the first level, and cover the non-self space a bit near selves. Then repeat the process until candidate detectors cover non-self space close to selves which are, namely, the boundary areas between self space and non-self space. When the algorithm terminates, mature detector set and boundary self set are obtained. Algorithm3 shows the process of CB-RNSA.Algorithm 3:The process of CB-RNSA.
Procedure. CB-RNSA Input: self training setTrain, expected coverage ratep0 Output: detector setD, boundary self set Selfo, outlier self set Selfd n 0: the sampling frequency of non-self space, n0>max⁡(5/p0,5/(1-p0)) i: the number of non-self samples m: the number of non-self samples which are covered by detectors C D: candidate detector set CD = {d∣d = y,rd = y1,y2,…,yn,rd, yj∈[0,1], 1≤j≤n,  rd∈[0,1]} Clusters: cluster set Clusters= {cluster} l: the number of candidate detector level Begin Initialize self training set Train, i= 0, m= 0, CD=∅, Selfo=∅, n0 = max⁡(5/p0,5/(1-p0)); Initialize outlier self set Selfd according to Procedure outlier selves discovery algorithm; Initialize cluster set Clustersaccording to Procedure clusters discovery algorithm; While l does not reach the maximum number of levels for candidate detectors do Consider centers of Clustersas antigens, randomly generate initial immune cell population in the qualified range; While true do Select immune cells; Generate copies of immune cells; Mutate according to affinities; Compute distances between mutated individual dnew and every self in the training set Train; If dnew is recognized by some self Then discard dnew; Else Find the closest self ag to dnew, and add it to boundary self set Selfo; i ++; Compute distances between dnew and every detector in the detector set D; If dnew is not identified by any detector Then put it into the candidate detector set CD; Else m ++; End if; If the number of non-self samples i reaches the sample times n0 Then Compute current coverage rate p; If p reaches the expected coverage rate p0, break; Else incorporate candidate detector set CD with D, reset i, m, CD; End if; End; l++; Changes the limited range of candidate detectors; End; End.The main contributions lie in(1) introducing the clonal selection algorithm and randomly generating candidate detectors within the stratified limited ranges based on clustering centers of self set; generating big-radius candidate detectors first and making them cover space far from selves, which reduces the number of detectors; then generating small-radius candidate detectors and making them gradually cover boundary space between selves and non-selves, which reduces the number of holes; (2) distinguishing selves and dividing them into outlier selves, boundary selves, and internal selves, which can adapt to the interference of noise data from selves; (3) for anomaly detection, using mature detector set and boundary self set to test at the same time, which can effectively improve the detection rate and reduce the false alarm rate. Theoretical analysis and experimental results show that the algorithm has better time efficiency and detector generation quality according to classic negative selection algorithms.Figures6 and 7 show the contrast between CB-RNSA, RNSA, and V-Detector. The self data are top 25 elements of classification “Iris-versicolor” from IRIS data set [23]. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. In RNSA and V-Detector, with rise of coverage rate, redundant cover between mature detectors in non-self space increases, which causes excessive detector quantity and unnecessary self tolerance. In CB-RNSA, because the clonal selection algorithm is introduced to limit the range of randomly generated candidate detectors, it is preferred that detectors are generated in space of low coverage, which reduces the number of detectors and redundancy.Figure 6
Contrast between CB-RNSA, RNSA, and V-Detector (five mature detectors are produced at the same time).Figure 7
Contrast between CB-RNSA, RNSA, and V-Detector (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 357, 81, and 35 mature detectors, respectively, where the self radius is 0.05, and the detector radius of RNSA is 0.05).


## 3.2. Classification of Selves

Most of the negative selection algorithms do not distinguish between selves. But for the continuous space of selves, information within different self is different. We divide selves into three groups, outlier selves, boundary selves, and internal selves, as shown in Figure8. Magenta filled circles are outlier selves, cyan filled circles are boundary selves, and blue filled circles are internal selves.Figure 8
Self classification.Suppose the collection of elementsNei(ag, r) whose distance with self ag is less than r is expressed as (13), and they are called neighbors.(13)Neiag,r=ag′∣ag′∈Self∧fag,ag′<rDefinition 10 (outlier self set).
S e l f d ⊂ S e l f. The outliers may be caused by noise data. Selfd={ag∣ag∈Self∧|Neiag,r|<ρ∙|Self|} means that when the number of neighbors of a self is less than a certain value, the self is classified as an outlier. ρ is the parameter for outlier.Definition 11 (boundary self set).
S e l f o ⊂ S e l f, and they are distributed in edges of self space and non-self space. The boundary self quantity is far less than the number of internal selves, and a lot of false positives and omissions appear in the borders. Because self space and non-self space are complementary, we use detector set to define boundary self set; that is to say, the self which is closest to a detector is boundary. Selfo={ag|ag∈Self∧(∃d∈D,fag,d=min⁡(∀ag′∈Self,fag′,d))}.Definition 12 (internal self set).
S e l f i ⊂ S e l f, and they are surrounded by boundary selves. Selfi=Self-Selfd-Selfo.


## 3.3. Outlier Selves Discovery Mechanism

As one of the important research fields of knowledge discovery, there are many effective outlier detection algorithms at present [27–29]. This paper adopts the algorithm based on distance proposed by Knorr [27], and Algorithm 4 shows the process of the algorithm.Algorithm 4:The process of outlier selves discovery algorithm.
Procedure. Outlier selves discovery algorithm Input: the self training setTrain Output: outlier self setSelfd Begin While self ag is not detected do m = 0; for other self ag′ in the self training set Train do Compute the distance between ag and ag′f(ag, ag′); If f(ag, ag′) < rthen m++; End; If m<ρ∙|Self|then add ag into the outlier self set Selfd; End; End.


## 3.4. Clusters Discovery Mechanism

In anomaly detection, it is thought that most of these data are normal, and abnormal data are the minority. In this paper, the algorithm first analyzes the space distribution of selves and performs a clustering pretreatment on the self set. Similar selves are classified in the same cluster, and then a number of clusters are generated. Centers of clusters are used as a benchmark to generate candidate detectors. The purpose of self set clustering is to determine the randomly generation scope of candidate detectors, and candidates are generated in the qualified range in order to avoid detector redundancy in high coverage.Definition 13 (cluster).
cluster = {c∣c = x,rc,C = x1,x2,…,xn,rc,{ag∣ag∈Self}, xi∈[0,1], 1 ≤ i ≤ n}. The parameter x is the center vector of the cluster inn-dimensional space, the parameter rc is the radius of the cluster, and the parameter C is the collection of selves within the cluster. rc is computed by the following formula:(14)cluster.rc=∑ag∈Self∑ag′∈Self-agfag,ag′Self∙Self-1The algorithm randomly selects a self as an initial element for a cluster at first and then judges whether any element in the cluster and other selfag are neighbors, that is to say, whether meeting ∃ag′∈Cluster.C,ag∈Nei(ag′,rc), if so, self ag will be within the cluster. After other selves are judged, if there is a self which does not belong to any cluster, that means Self-∑cluster′∈Clusters{ag∣ag∈cluster′.C}≠∅, the algorithm continues to randomly select a self as an initial element of a new cluster. The above operations are performed until all the selves belong to a cluster. The cluster center x is computed by the following formula (15). Algorithm 5 shows the process of clusters discovery algorithm.(15)cluster.xi=∑ag∈cluster.Cag.xinAlgorithm 5:The process of clusters discovery algorithm.
Procedure. Clusters discovery algorithm Input: the self training setTrain Output: cluster setClusters={cluster} Begin While self ag is not belong to any cluster do Generate a new cluster for ag; For other self ag′ in selves which are not classified do If ag′ is neighbor to any element in cluster, then put ag′ into cluster; End; End; End.


## 3.5. Clonal Selection Mechanism

Clonal selection algorithm is often used for solving the optimization problems. This paper adopts the clonal selection algorithm to search optimal detectors in the non-self space. The center of each cluster is viewed as an antigen. Initial immune cell population is randomly generated in limited scope, and the clonal selection algorithm is performed on the group. The limits control the position of vectorx of immune cell ag in each dimension and are defined as a super sphere loop based on the center of the clustercluster.x. The distance between immune cell and the center of the cluster should be limited between [rlow,rhigh], that means,rlow ≤f(ag,cluster) ≤rhigh.rlow is the minimum distance between immune cell and cluster center,rlow = 0, andrhigh is the maximum distance between these two,rhigh = n. Candidates will be generated by layer. According to the detector radius, from big to small, a detector of larger coverage will be in priority to be produced, to avoid repeated coverage with existing mature detectors and achieve less detectors covering as much as possible non-self area. Set level isl, and the limited scope of the l level is to meet (16), where the value of l should be satisfied (17); that is, max⁡(l)=log2⁡n/rs+1.(16)n2l≤fag,cluster≤n2l-1(17)n2l-1≥rsFigure9 shows limited scopes of the first level, second level, and third level of candidate detectors based on one of the clusters and generations of candidate detectors. Figure 10 shows limited scopes of the top three levels based on all the clusters and the generation of candidate detectors. Blue filled circles and green filled circles are self elements, cyan filled circles are mature detectors, and regions between two concentric dotted circles are the randomly generation scopes.Figure 9
Limited scopes and generations of candidate detectors (based on the cluster of blue filled circles).
(a) (b) (c)Figure 10
Limited scopes and generations of candidate detectors.
(a) (b) (c)In the clonal selection algorithm, the main operations include immune selectionTs, clonal amplification Tc, and hypermutation Tm. Immune selection operation is to choose a certain number of immune cells with high-affinity in order to search in more valuable space. In this algorithm, because immune cells should cover the non-self space as much as possible, it is not necessary to choose by affinity, and the population of all immune cells go into the next operation. Set AB as the population of immune cells and AB′ as the population after this operation, and the probability of selection is as (18)PTsAB=AB′=1Clonal amplification operation simulates cloning mechanism of the immune response, and the higher affinity with antigens the cell has, the more offspring the cell can produce. In this algorithm, the number of copiesncis related to the level l where candidate detector is.nc is computed by (19), wherencmax is the maximum number of copies andncmin is the minimum.(19)nc=ncmin+ncmax-ncmin1-1lThe above formula reflects the clone expansion scales for immune cells in different limited scopes. When the hierarchy is small, candidate detectors are in low-coverage areas and the radius is larger. We hope to cover more non-self space with less detectors, so the cloning scale is smaller. When the hierarchy is big, candidate detectors are in high coverage areas and the radius is smaller. We hope to cover holes in the boundary of self space and non-self space, so the cloning scale is larger.Hypermutation operation is to produce immune cells with higher affinity and enhance the diversity of the population. Mutation operator usually can produce small disturbance and can also produce a wide range of disturbance, which makes the mutation have abilities of local search and global search and makes the algorithm have stronger optimal search performance. In this paper, Gauss mutation is adopted and the formula is as(20)ag′.xi=ag.xi+α∙N0,1whereag′ is the mutated immune cell, N(0,1) is the Gaussian random variable, the mean is 0, and the deviation is 1. α is the control parameter to adjust the variation amplitude. In this paper, a dynamic adaptive α is adopted and only related to candidate detector level l. The mutation mechanism is as (21). In the process of the generation of candidate detectors, when the level is small, individuals search with larger probability, which is good for global search. When the level is large, individuals search with smaller probability, which is more conducive to local search.(21)α=11+el-k0k 0 is the cut-off point for α that means the cut-off for the algorithm from global search of big probability to local search of small probability.After immune cells perform mutation, they also need to meet (16). So, new cells should meet the formula, or they will be discarded. This will produce a large number of useless cells, which needs a large amount of calculations. Set ag.x as the origin, we use n-spherical coordinates to rewrite (16) by (22).(22)ag′.x1=ag.x1+ρ∙cos⁡θ1ag′.x2=ag.x2+ρ∙sin⁡θ1cos⁡θ2ag′.xn-1=ag.xn-1+ρ∙sin⁡θ1sin⁡θ2…cos⁡θn-1ag′.xn=ag.xn+ρ∙sin⁡θ1⁡sin⁡θ2…sin⁡θn-1where the parameterρ is random variable between [n/2l,n/2l-1], the parameters θ1,θ2,…,θn-2 are random variables between [0,π], and the parameter θn-1 is random variable between [0,2π]. They are expressed as (23), (24), and (25).(23)ρ=n2l+n2l-1-n2l∙α∙N0,1(24)θi=π∙α∙N0,11≤i≤n-2(25)θn-1=2π∙α∙N0,1


## 3.6. Anomaly Detection

Anomaly detection is used to determine whether data is abnormal. In this paper, the anomaly detection process combines the detector setD and boundary self set Selfo together for testing. So, we modify the definition ofB, and B is expressed as (26).B is mapping from detector setD, boundary self set Selfo, and antigen ag to be identified to a classification {0,1}, where 0 indicates that ag is self, and 1 means that ag is non-self.(26)BD,Selfo,ag=1,∃ag′∈Selfo,fag′,ag>rs⋀∃d∈D,fd,ag≤rd0,otherwise


## 3.7. Coverage Rate of Non-Self Space

The greater the coverage of detectors for the non-self space is, the greater the probability of detecting non-self is. Due to overlaps between detectors, direct calculation of coverage ratep for non-self space is very difficult. Monte Carlo method is used to calculate the approximate value p^. Suppose a randomly generated non-self set N∈Nonself, the calculation formula of non-self space coverage rate of detector set D is as (27)p=∫x→∈Ddx→∫x→∈Nonselfdx→≈p^=∑ag∈N∃d∈D,fd,ag≤rdNSetp0 as the target coverage rate. When the estimated value p^ is greater than or equal to p0, it is thought that detectors meet the requirements of the target coverage. Because p^ is a random variable, it is inevitable that the actual coverage rate p is less than p0. To reduce the probability of this situation, the algorithm introduces the hypothesis test for processing.Setα as the significance of hypothesis test, za as the α quantile of standard normal distribution, n0 as the sample size, and x as the number of samples covered by detectors. The calculating formula of maximumxmax is as (28)xmax=zαn0p01-p0+n0p0Obviouslyn0>xmax, then n0>zαn0p0(1-p0)+n0p0, that is, n0>p0zα2/(1-p0). In order to meet the requirements and make the estimated coverage rate p^=x/n0 approximately obey the normal distribution, the calculation formula of sample size n0 is as (29)n0=max⁡5p0,51-p0,p0zα21-p0Because5>p0zα2, the above equation can be rewriting as n0=max⁡(5/p0,5/(1-p0)).The actual coverage rate of detectors for the non-space isp, the null hypothesis of hypothesis testing H0 is “p=p0”, and the alternative hypothesis H1 is “p>p0”. In the process of the algorithm, if x is less than or equal toxmax, receive H0 and update detector set; if x is greater than thexmax, accept H1 and exit.


## 4. Analysis of the Algorithm

### 4.1. Time Complexity Analysis

Theorem 14.
The time complexity of CB-RNSA for detectors generation is O(ng∙log2⁡n/rs+1+ncmax+ncmax∙n+Self∙D/1-P+|D|2), wheren is the spatial dimension, Self is the size of self set, D is the size of detector set,Pis the self-reaction rate of detectors, ng is the scale of initial immune cell population, andncmax is the maximum number of clonal copies.Proof.
CB-RNSA carries out preprocessing operations on the self set in the first place and then executes clonal selection algorithm in every qualified level to generate candidate detectors.
The number of computation times of the outlier selves discovery algorithm is not exceeded|Self|∙(|Self|-1)/2, and the time complexity is O(|Self|∙(|Self|-1)/2). The number of computation times of the clusters discovery algorithm does not exceed |Self|∙(|Self|-1)/2, and the time complexity is O(|Self|∙(|Self|-1)/2). We mainly consider the time complexity of the detector generation process and do not consider the time complexity of preprocessing operations.
In thei layer, the time complexity of randomly generating initial immune cell group is O(ng). Immune selection operation chooses the entire immune cells, and the time complexity is not considered. For each immune cell, the calculation number of the clonal amplification operation is not more thanncmax, the time complexity is O(ncmax) which is a constant value, and the time complexity of hypermutation operation is O(ncmax∙n). The time complexity of calculating whether immune cells fall into self space is O(Self). Suppose the probability of immune cells falling into self space is Pi, the number of immune cells in level i is Ni, and then the number of immune cells which are not excluded in this step is Ni∙(1-Pi). The time complexity of computing whether immune cells are covered by mature detectors is O(|D|). Then viewing this immune cell as a candidate detector, the time complexity of calculating the radius is O(Self). Results of previous operations can be used for this operation, so, we do not consider the time complexity.
Therefore, the overall time complexity of generating detectors in thei level is O(ng+Ni∙ncmax+ncmax∙n+Self+(1-Pi)∙Ni∙|D|). The maximum number of i is l=log2⁡n/rs+1; the overall time complexity of generating detectors for CB-RNSA is O(∑i=1l(ng+Ni∙ncmax+ncmax∙n+Self+(1-Pi)∙Ni∙|D|)). Suppose P is the average self-reaction rate of detectors, the number of candidate detectors is N0=∑i=1lNi≈|D|/(1-P), and then the time complexity of CB-RNSA is O(ng∙log2⁡n/rs+1+ncmax+ncmax∙n+Self∙D/1-P+|D|2). Proved.NSA, RNSA, and V-Detector are the influential negative selection algorithms and are widely used in intrusion detection, abnormal diagnosis, pattern recognition, etc. Table1 lists the time complexity contrast of the three negative selection algorithms and CB-RNSA, where Pm is the probability of detectors identifying any antigen and Pf is the detection failure rate. As can be seen from the table, the time complexity of the traditional negative selection algorithms is in exponential relationship with self set size |Self|. When the size of self elements increases, the time spending increases rapidly, even to the unbearable point. The time complexity of CB-RNSA is related to the spatial dimensionn, the size of self set |Self|, the detector set size |D|, and the self-reaction rate P. There is no exponential relationship with Self, and the size of the detector set |D| is far less than the other three algorithms, which reduces the time complexity and improves the detectors generation efficiency.Table 1
Contrast of time complexity.
Algorithms Time complexities NSA O - ln ⁡ P f ∙ S e l f P m ∙ 1 - P m S e l f[1] RNSA O D ∙ S e l f 1 - P S e l f[3] V-Detector O D ∙ S e l f 1 - P S e l f[4, 5] CB-RNSA Ong∙log2⁡nrs+1+ncmax+ncmax∙n+Self∙D1-P+D2⁡


### 4.2. Self-Reaction Rate Analysis of Detectors

Under the established matching rules, the matching probabilityP of any given detector with any antigen is a constant [1]. For the r-continuous matching rule of NSA, it satisfies P=2-r(l-r/2+1), wherel is the length of the string andr is the consecutive matching digits.In the real-valued algorithm, calculation is different. The work in [3, 4] pointed out that, in RNSA and V-Detector,Pcan be acquired by calculating the ratio of self capacity to the total antigen capacity, and P is also known as the reaction rate of detectors, which means the probability of detectors covering self space. In addition, we can use the number of all candidate detectors to measure detector generation cost. Suppose achieving desired non-self space coverage rate, the number of detectors is |D|, and the candidate detectors can be calculated by N0=|D|/(1-P)num, where the number of selves isnum. The larger the self-reaction rate of detectors is, the greater the number of candidate detectors for generating |D| mature detectors is, and the higher the detector generation cost is. To simplify the discussion, it is assumed that there is no overlap between selves.For RNSA and V-Detector, detectors are randomly generated in0,1n space. Therefore, the self-reaction rate of detectors P1 is the ratio of |Self| hypersphere volumes to unit hypercube volume. Suppose Vself is the volume of a self. P1 is expressed as (30)P1=Self∙Vself1=Self∙πn/2∙rsnΓn/2+1For CB-RNSA, detectors are randomly generated within different limited space. Therefore, the self-reaction rate of detectorsP2 is the ratio of volumes of the limited space which are covered by selves to volumes of the limited space. In the l layer, the limited space is a super sphere loop between two spheres with radiuses n/2l and n/2l-1, respectively. Selves may or may not intersect with this loop. Suppose the number of selves within this loop is nl. To simplify the discussion, suppose there is no element half intersecting with the loop. The self-reaction rate of detectors P2 is as (31). Suppose Vl is the volume of a sphere for the l layer.(31)P2=nl∙VselfVl-Vl+1=nl∙rsn∙πn/2/Γn/2+1n/2l-1n∙πn/2/Γn/2+1-n/2ln∙πn/2/Γn/2+1=nl∙rsnn/2l-1n-n/2lnTo compare the self-reaction rates of the three algorithms, setθ=P2/P1 and is expressed as (32)
θ
=
P
2
P
1
=
n
l
∙
r
s
n
/
n
/
2
l
-
1
n
-
n
/
2
l
n
S
e
l
f
∙
π
n
/
2
∙
r
s
n
/
Γ
n
/
2
+
1
=
n
l
S
e
l
f
∙
Γ
n
/
2
+
1
π
n
/
2
n
/
2
l
-
1
n
-
n
/
2
l
nWhenl is small, the super sphere loop is far from the center of the cluster. Selves of this cluster are disjoint with the loop and selves of other clusters may intersect with the loop. With the increase of l, the loop will be more and more near the center of cluster, selves of this cluster are likely to intersect with the loop, and other selves are disjoint with the loop. So, nl<|Self|. When θ is less than 1, the self-reaction rate of CB-RNSA is less than RNSA and V-Detector, that means the detector generation cost of CB-RNSA is less. Figure 11 shows the variation of θ with changes of the data dimension n and the limited level l. As can be seen from the figure, when n and l are small, θ is far less than 1.Figure 11
Influences ofn and l on θ (set nl/|Self|=0.2).


## 4.1. Time Complexity Analysis

Theorem 14.
The time complexity of CB-RNSA for detectors generation is O(ng∙log2⁡n/rs+1+ncmax+ncmax∙n+Self∙D/1-P+|D|2), wheren is the spatial dimension, Self is the size of self set, D is the size of detector set,Pis the self-reaction rate of detectors, ng is the scale of initial immune cell population, andncmax is the maximum number of clonal copies.Proof.
CB-RNSA carries out preprocessing operations on the self set in the first place and then executes clonal selection algorithm in every qualified level to generate candidate detectors.
The number of computation times of the outlier selves discovery algorithm is not exceeded|Self|∙(|Self|-1)/2, and the time complexity is O(|Self|∙(|Self|-1)/2). The number of computation times of the clusters discovery algorithm does not exceed |Self|∙(|Self|-1)/2, and the time complexity is O(|Self|∙(|Self|-1)/2). We mainly consider the time complexity of the detector generation process and do not consider the time complexity of preprocessing operations.
In thei layer, the time complexity of randomly generating initial immune cell group is O(ng). Immune selection operation chooses the entire immune cells, and the time complexity is not considered. For each immune cell, the calculation number of the clonal amplification operation is not more thanncmax, the time complexity is O(ncmax) which is a constant value, and the time complexity of hypermutation operation is O(ncmax∙n). The time complexity of calculating whether immune cells fall into self space is O(Self). Suppose the probability of immune cells falling into self space is Pi, the number of immune cells in level i is Ni, and then the number of immune cells which are not excluded in this step is Ni∙(1-Pi). The time complexity of computing whether immune cells are covered by mature detectors is O(|D|). Then viewing this immune cell as a candidate detector, the time complexity of calculating the radius is O(Self). Results of previous operations can be used for this operation, so, we do not consider the time complexity.
Therefore, the overall time complexity of generating detectors in thei level is O(ng+Ni∙ncmax+ncmax∙n+Self+(1-Pi)∙Ni∙|D|). The maximum number of i is l=log2⁡n/rs+1; the overall time complexity of generating detectors for CB-RNSA is O(∑i=1l(ng+Ni∙ncmax+ncmax∙n+Self+(1-Pi)∙Ni∙|D|)). Suppose P is the average self-reaction rate of detectors, the number of candidate detectors is N0=∑i=1lNi≈|D|/(1-P), and then the time complexity of CB-RNSA is O(ng∙log2⁡n/rs+1+ncmax+ncmax∙n+Self∙D/1-P+|D|2). Proved.NSA, RNSA, and V-Detector are the influential negative selection algorithms and are widely used in intrusion detection, abnormal diagnosis, pattern recognition, etc. Table1 lists the time complexity contrast of the three negative selection algorithms and CB-RNSA, where Pm is the probability of detectors identifying any antigen and Pf is the detection failure rate. As can be seen from the table, the time complexity of the traditional negative selection algorithms is in exponential relationship with self set size |Self|. When the size of self elements increases, the time spending increases rapidly, even to the unbearable point. The time complexity of CB-RNSA is related to the spatial dimensionn, the size of self set |Self|, the detector set size |D|, and the self-reaction rate P. There is no exponential relationship with Self, and the size of the detector set |D| is far less than the other three algorithms, which reduces the time complexity and improves the detectors generation efficiency.Table 1
Contrast of time complexity.
Algorithms Time complexities NSA O - ln ⁡ P f ∙ S e l f P m ∙ 1 - P m S e l f[1] RNSA O D ∙ S e l f 1 - P S e l f[3] V-Detector O D ∙ S e l f 1 - P S e l f[4, 5] CB-RNSA Ong∙log2⁡nrs+1+ncmax+ncmax∙n+Self∙D1-P+D2⁡


## 4.2. Self-Reaction Rate Analysis of Detectors

Under the established matching rules, the matching probabilityP of any given detector with any antigen is a constant [1]. For the r-continuous matching rule of NSA, it satisfies P=2-r(l-r/2+1), wherel is the length of the string andr is the consecutive matching digits.In the real-valued algorithm, calculation is different. The work in [3, 4] pointed out that, in RNSA and V-Detector,Pcan be acquired by calculating the ratio of self capacity to the total antigen capacity, and P is also known as the reaction rate of detectors, which means the probability of detectors covering self space. In addition, we can use the number of all candidate detectors to measure detector generation cost. Suppose achieving desired non-self space coverage rate, the number of detectors is |D|, and the candidate detectors can be calculated by N0=|D|/(1-P)num, where the number of selves isnum. The larger the self-reaction rate of detectors is, the greater the number of candidate detectors for generating |D| mature detectors is, and the higher the detector generation cost is. To simplify the discussion, it is assumed that there is no overlap between selves.For RNSA and V-Detector, detectors are randomly generated in0,1n space. Therefore, the self-reaction rate of detectors P1 is the ratio of |Self| hypersphere volumes to unit hypercube volume. Suppose Vself is the volume of a self. P1 is expressed as (30)P1=Self∙Vself1=Self∙πn/2∙rsnΓn/2+1For CB-RNSA, detectors are randomly generated within different limited space. Therefore, the self-reaction rate of detectorsP2 is the ratio of volumes of the limited space which are covered by selves to volumes of the limited space. In the l layer, the limited space is a super sphere loop between two spheres with radiuses n/2l and n/2l-1, respectively. Selves may or may not intersect with this loop. Suppose the number of selves within this loop is nl. To simplify the discussion, suppose there is no element half intersecting with the loop. The self-reaction rate of detectors P2 is as (31). Suppose Vl is the volume of a sphere for the l layer.(31)P2=nl∙VselfVl-Vl+1=nl∙rsn∙πn/2/Γn/2+1n/2l-1n∙πn/2/Γn/2+1-n/2ln∙πn/2/Γn/2+1=nl∙rsnn/2l-1n-n/2lnTo compare the self-reaction rates of the three algorithms, setθ=P2/P1 and is expressed as (32)
θ
=
P
2
P
1
=
n
l
∙
r
s
n
/
n
/
2
l
-
1
n
-
n
/
2
l
n
S
e
l
f
∙
π
n
/
2
∙
r
s
n
/
Γ
n
/
2
+
1
=
n
l
S
e
l
f
∙
Γ
n
/
2
+
1
π
n
/
2
n
/
2
l
-
1
n
-
n
/
2
l
nWhenl is small, the super sphere loop is far from the center of the cluster. Selves of this cluster are disjoint with the loop and selves of other clusters may intersect with the loop. With the increase of l, the loop will be more and more near the center of cluster, selves of this cluster are likely to intersect with the loop, and other selves are disjoint with the loop. So, nl<|Self|. When θ is less than 1, the self-reaction rate of CB-RNSA is less than RNSA and V-Detector, that means the detector generation cost of CB-RNSA is less. Figure 11 shows the variation of θ with changes of the data dimension n and the limited level l. As can be seen from the figure, when n and l are small, θ is far less than 1.Figure 11
Influences ofn and l on θ (set nl/|Self|=0.2).


## 5. Experimental Results and Analysis

This section verified the effectiveness of GB-RNSA through experiments. Experiments chose the representative real-valued negative selection algorithms RNSA and V-Detector for comparisons. Experimental data adopt two types of data sets which are commonly used in the study, including 2D comprehensive data sets [30] and UCI data sets [23]. 2D comprehensive data sets are provided by the team of professor Dasgupta from the university of Memphis and are authoritative for the real-valued negative selection algorithm performance test [11, 12, 14]. UCI data sets are classical in machine learning and are widely used in the performance tests and detector generating efficiency tests [8–16].In specific comparisons, in order to avoid the influence of different exit conditions on the algorithms, all algorithms adopt the same exit criteria “to reach the expected non-self space coverage rate”. The number of mature detectorsDN, detection rateDR, false alarm rateFAR, and time cost of detector generationDT are adopted to measure the effectiveness of algorithms.


### 5.1. 2D Comprehensive Data Sets

The data sets contain a number of subdata sets; Figure12 shows distributions in the two-dimensional space of self data from three subdata sets, Cross, Intersection, and Ring. Without loss of generality, experiments chose the three data sets.Figure 12
Distributions of Cross, Intersection, and Ring.Self set size of these three data sets|Self| = 1000. The training set is composed of randomly selected selves, and the test data are composed of random points in the [0,1] space. The experiments repeat 20 times and averaged values were obtained. Tables 2 and 3 show the results of the experiments, and values in parentheses are variances. Table 2 lists contrasts of detection rate and false positive rate of CB-RNSA under the same expected coverage rate 90%, the same training set size Ns =500, and different radiuses of selves. It can be seen that detectors trained from the smaller radius of selves have higher detection rate and false positive rate, and detectors trained from the bigger radius have lower detection rate and false positive rate. Therefore, we should adopt smaller radius of selves to train detectors for applications whose environment is sensitive to abnormal data, and bigger radius for applications whose environment is sensitive to false positives. Table 3 lists contrasts of detection rate and false positive rate of CB-RNSA under the same expected coverage rate 90%, the same radius of selves rs = 0.05, and different training set sizes. It can be seen that, with the rise of training set size, the detection rate increases gradually, and the false positive rate reduces gradually. This is because more selves participating in training is good for effective screening of detectors, which can reduce the number of self-reacted detectors, and makes detectors cover non-self space more accurately.Table 2
Influence of different self radiuses on CB-RNSA.
Data sets r s = 0.02 r s = 0.05 r s = 0.1 r s = 0.2 D R% F A R% D R% F A R% D R% F A R% D R% F A R% Ring 93.31(1.32) 24.24(1.44) 86.43(1.01) 9.22(1.15) 71.14(1.55) 0.00(0.00) 43.21(2.42) 0.00(0.00) Cross 94.19(1.16) 24.76(1.71) 88.02(1.24) 8.28(1.72) 72.52(1.41) 0.00(0.00) 46.29(2.76) 0.00(0.00) Intersection 90.11(1.68) 26.63(1.82) 84.91(1.51) 9.45(1.14) 63.13(1.89) 0.00(0.00) 38.64(2.53) 0.00(0.00)Table 3
Influence of different training set sizes on CB-RNSA.
Data sets N s = 100 N s = 500 N s = 800 N s = 1000 D R% F A R% D R% F A R% D R% F A R% D R% F A R% Ring 24.87(1.21) 69.32(1.74) 86.43(1.01) 9.22(1.15) 97.92(1.01) 0.00(0.00) 98.87(1.00) 0.00(0.00) Cross 26.46(1.45) 67.41(2.01) 88.02(1.24) 8.28(1.72) 98.19(1.05) 0.00(0.00) 99.42(0.31) 0.00(0.00) Intersection 21.51(1.87) 71.23(2.17) 84.91(1.51) 9.45(1.14) 96.58(1.10) 0.00(0.00) 98.08(1.13) 0.00(0.00)Figures13 and 14 are comparisons of a run of RNSA, V-Detector and CB-RNSA in Cross data set and Intersection data set, respectively. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. As can be seen from the figures, there is less redundant coverage between detectors of CB-RNSA, and detector quantity is less, which makes less detectors achieve the same coverage expectation.Figure 13
Comparisons of RNSA, V-Detector, and CB-RNSA in Cross (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 289, 61, and 37 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).Figure 14
Comparisons of RNSA, V-Detector, and CB-RNSA in Intersection (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 590, 85, and 40 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).2D comprehensive data sets are clean. In order to test conditions of self set containing noise data, we added a small amount of noise data in the Ring data set. Figure15 shows comparison of a run of RNSA, V-Detector, and CB-RNSA in Ring data set. Blue filled circles are self elements, white filled circles are noise data, cyan filled circles are mature detectors, and unfilled area is holes. CB-RNSA detects the outlier selves and ignores them because they are noise data. In the case of noisy data interference, detectors of CB-RNSA fully covered the non-self space, and RNSA and V-Detector cannot effectively handle it.Figure 15
Comparisons of RNSA, V-Detector, and CB-RNSA in Ring (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 477, 51, and 17 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).


### 5.2. UCI Data Sets

Experiments selected four standard UCI data sets, including Haberman’s Survival, Abalone, Breast Cancer Wisconsin Original (BCW1 for short), and Breast Cancer Wisconsin Diagnostic (BCW2 for short), and experimental parameters are shown in Table4. Of these four data sets, self set and non-self set were randomly selected; training set and testing set were randomly selected as well. Experiments were repeated 20 times and averaged values were gained.Table 4
Experimental parameters.
Data sets Number of records Dimension Type Self set Non-self set Training set and its size Testing set and its size Haberman’s Survival 306 3 Integer Survived: 225 Died: 81 Survived: 150 Survived: 50Died: 50 Abalone 4177 8 Real, integer M: 1528 F: 1307I: 1342 M: 1000 M: 500F: 500  I: 500 BCW1 683 9 Integer Benign: 444 Malignant: 239 Benign: 200 Benign: 150Malignant: 150 BCW2 569 30 Real Benign: 357 Malignant: 212 Benign: 200 Benign: 150 Malignant: 150


#### 5.2.1. Comparisons of the Number of Detectors

Figure16 shows comparisons of the number of mature detectors of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate increases, the number of mature detectors of three algorithms rises correspondingly. But the efficiency of CB-RNSA is superior to the other algorithms. For Haberman’s Survival data set, in order to achieve the expected coverage rate of 99%, RNSA needs 1033.1 mature detectors, V-Detector needs 351.4 detectors, and CB-RNSA needs 165.2 detectors which declines by 84.0% and 53.0%, respectively. For large data set Abalone, in order to achieve the expected coverage rate of 99%, RNSA needs 12893.2 mature detectors, V-Detector needs 1194.0 detectors, and CB-RNSA needs 615.4 detectors which declines by 95.2% and 48.5%, respectively. So, in the expectation of the same coverage rate, under different data dimensions and different training sets, the number of mature detectors of CB-RNSA has greatly reduced compared to RNSA and V-Detector.Figure 16
Comparisons of the number of detectors of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


#### 5.2.2. Comparisons of the Cost of Detectors Generation

Figure17 shows comparisons of the cost of detectors generation of RNSA, V-Detector, and CB-RNSA. For Haberman’s Survival data set, when the expected coverage rate rises from 90% to 99%, the time price of RNSA increases from 7.7s to 291.0s, the time price of V-Detector increases from 0.6s to 29.8s, and the time price of CB-RNSA increases from 0.4s to 13.7s. For Abalone data set, when the expected coverage rate rises from 90% to 90%, the time price of RNSA increases from 241.7s to 2412.8s, the time price of V-Detector increases from 2.4s to 228.6s, and the time price of CB-RNSA increases from 1.3s to 82.5s. Therefore, with the rise of expected coverage rate, the time costs of RNSA and V-Detector increase very quickly, and the time cost of GB-RNSA increases more slowly.Figure 17
Comparisons of time costs of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


#### 5.2.3. Comparisons of Detection Rate and False Alarm Rate

Figures18 and 19 show comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate is greater than 90%, detection rates of three algorithms have little differences, and that of RNSA is lower; false alarm rate of CB-RNSA is obviously lower than that of RNSA and V-Detector. For BCW1 data set, when the expected coverage rate is 99%, false alarm rate of RNSA is 55.2%, false alarm rate of V-Detector is 30.1%, and false alarm rate of CB-RNSA is 20.1% which declines by 63.6% and 33.2%, respectively. For high dimensional data set BCW2, when the expected coverage rate is 99%, false alarm rate of RNSA is 25.1%, false alarm rate of V-Detector is 20.5%, and false alarm rate of CB-RNSA is 12.6% which declines by 49.8% and 38.5%, respectively. On the one hand, CB-RNSA introduced clonal selection algorithm and limited the generation range of detectors, which made detectors generated in the low-coverage non-self space and improved the coverage rate. On the other hand, detectors and boundary selves were adopted for testing at the same time, the definition of anomaly was stricter, which reduced the rate of false positive.Figure 18
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW1).
(a) (b)Figure 19
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW2).
(a) (b)The ROC curve is a graphical method for classification model based on detection rates and false alarm rates. Figure20 shows comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA under two kinds of data sets, BCW1 and BCW2. A good classification mode curve should be distributed in the left-top of graphic as soon as possible. As can be seen from the diagram, CB-RNSA is superior to RNSA and V-Detector.Figure 20
Comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA.
(a)
BCW1 (b)
BCW2


## 5.1. 2D Comprehensive Data Sets

The data sets contain a number of subdata sets; Figure12 shows distributions in the two-dimensional space of self data from three subdata sets, Cross, Intersection, and Ring. Without loss of generality, experiments chose the three data sets.Figure 12
Distributions of Cross, Intersection, and Ring.Self set size of these three data sets|Self| = 1000. The training set is composed of randomly selected selves, and the test data are composed of random points in the [0,1] space. The experiments repeat 20 times and averaged values were obtained. Tables 2 and 3 show the results of the experiments, and values in parentheses are variances. Table 2 lists contrasts of detection rate and false positive rate of CB-RNSA under the same expected coverage rate 90%, the same training set size Ns =500, and different radiuses of selves. It can be seen that detectors trained from the smaller radius of selves have higher detection rate and false positive rate, and detectors trained from the bigger radius have lower detection rate and false positive rate. Therefore, we should adopt smaller radius of selves to train detectors for applications whose environment is sensitive to abnormal data, and bigger radius for applications whose environment is sensitive to false positives. Table 3 lists contrasts of detection rate and false positive rate of CB-RNSA under the same expected coverage rate 90%, the same radius of selves rs = 0.05, and different training set sizes. It can be seen that, with the rise of training set size, the detection rate increases gradually, and the false positive rate reduces gradually. This is because more selves participating in training is good for effective screening of detectors, which can reduce the number of self-reacted detectors, and makes detectors cover non-self space more accurately.Table 2
Influence of different self radiuses on CB-RNSA.
Data sets r s = 0.02 r s = 0.05 r s = 0.1 r s = 0.2 D R% F A R% D R% F A R% D R% F A R% D R% F A R% Ring 93.31(1.32) 24.24(1.44) 86.43(1.01) 9.22(1.15) 71.14(1.55) 0.00(0.00) 43.21(2.42) 0.00(0.00) Cross 94.19(1.16) 24.76(1.71) 88.02(1.24) 8.28(1.72) 72.52(1.41) 0.00(0.00) 46.29(2.76) 0.00(0.00) Intersection 90.11(1.68) 26.63(1.82) 84.91(1.51) 9.45(1.14) 63.13(1.89) 0.00(0.00) 38.64(2.53) 0.00(0.00)Table 3
Influence of different training set sizes on CB-RNSA.
Data sets N s = 100 N s = 500 N s = 800 N s = 1000 D R% F A R% D R% F A R% D R% F A R% D R% F A R% Ring 24.87(1.21) 69.32(1.74) 86.43(1.01) 9.22(1.15) 97.92(1.01) 0.00(0.00) 98.87(1.00) 0.00(0.00) Cross 26.46(1.45) 67.41(2.01) 88.02(1.24) 8.28(1.72) 98.19(1.05) 0.00(0.00) 99.42(0.31) 0.00(0.00) Intersection 21.51(1.87) 71.23(2.17) 84.91(1.51) 9.45(1.14) 96.58(1.10) 0.00(0.00) 98.08(1.13) 0.00(0.00)Figures13 and 14 are comparisons of a run of RNSA, V-Detector and CB-RNSA in Cross data set and Intersection data set, respectively. Blue filled circles are self elements, cyan filled circles are mature detectors, and unfilled area is holes. As can be seen from the figures, there is less redundant coverage between detectors of CB-RNSA, and detector quantity is less, which makes less detectors achieve the same coverage expectation.Figure 13
Comparisons of RNSA, V-Detector, and CB-RNSA in Cross (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 289, 61, and 37 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).Figure 14
Comparisons of RNSA, V-Detector, and CB-RNSA in Intersection (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 590, 85, and 40 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).2D comprehensive data sets are clean. In order to test conditions of self set containing noise data, we added a small amount of noise data in the Ring data set. Figure15 shows comparison of a run of RNSA, V-Detector, and CB-RNSA in Ring data set. Blue filled circles are self elements, white filled circles are noise data, cyan filled circles are mature detectors, and unfilled area is holes. CB-RNSA detects the outlier selves and ignores them because they are noise data. In the case of noisy data interference, detectors of CB-RNSA fully covered the non-self space, and RNSA and V-Detector cannot effectively handle it.Figure 15
Comparisons of RNSA, V-Detector, and CB-RNSA in Ring (to achieve the expected coverage rate 90%, RNSA, V-Detector, and CB-RNSA need 477, 51, and 17 mature detectors, respectively, where the training set size is 500, the self radius is 0.03, and the detector radius of RNSA is 0.03).


## 5.2. UCI Data Sets

Experiments selected four standard UCI data sets, including Haberman’s Survival, Abalone, Breast Cancer Wisconsin Original (BCW1 for short), and Breast Cancer Wisconsin Diagnostic (BCW2 for short), and experimental parameters are shown in Table4. Of these four data sets, self set and non-self set were randomly selected; training set and testing set were randomly selected as well. Experiments were repeated 20 times and averaged values were gained.Table 4
Experimental parameters.
Data sets Number of records Dimension Type Self set Non-self set Training set and its size Testing set and its size Haberman’s Survival 306 3 Integer Survived: 225 Died: 81 Survived: 150 Survived: 50Died: 50 Abalone 4177 8 Real, integer M: 1528 F: 1307I: 1342 M: 1000 M: 500F: 500  I: 500 BCW1 683 9 Integer Benign: 444 Malignant: 239 Benign: 200 Benign: 150Malignant: 150 BCW2 569 30 Real Benign: 357 Malignant: 212 Benign: 200 Benign: 150 Malignant: 150


### 5.2.1. Comparisons of the Number of Detectors

Figure16 shows comparisons of the number of mature detectors of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate increases, the number of mature detectors of three algorithms rises correspondingly. But the efficiency of CB-RNSA is superior to the other algorithms. For Haberman’s Survival data set, in order to achieve the expected coverage rate of 99%, RNSA needs 1033.1 mature detectors, V-Detector needs 351.4 detectors, and CB-RNSA needs 165.2 detectors which declines by 84.0% and 53.0%, respectively. For large data set Abalone, in order to achieve the expected coverage rate of 99%, RNSA needs 12893.2 mature detectors, V-Detector needs 1194.0 detectors, and CB-RNSA needs 615.4 detectors which declines by 95.2% and 48.5%, respectively. So, in the expectation of the same coverage rate, under different data dimensions and different training sets, the number of mature detectors of CB-RNSA has greatly reduced compared to RNSA and V-Detector.Figure 16
Comparisons of the number of detectors of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


### 5.2.2. Comparisons of the Cost of Detectors Generation

Figure17 shows comparisons of the cost of detectors generation of RNSA, V-Detector, and CB-RNSA. For Haberman’s Survival data set, when the expected coverage rate rises from 90% to 99%, the time price of RNSA increases from 7.7s to 291.0s, the time price of V-Detector increases from 0.6s to 29.8s, and the time price of CB-RNSA increases from 0.4s to 13.7s. For Abalone data set, when the expected coverage rate rises from 90% to 90%, the time price of RNSA increases from 241.7s to 2412.8s, the time price of V-Detector increases from 2.4s to 228.6s, and the time price of CB-RNSA increases from 1.3s to 82.5s. Therefore, with the rise of expected coverage rate, the time costs of RNSA and V-Detector increase very quickly, and the time cost of GB-RNSA increases more slowly.Figure 17
Comparisons of time costs of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


### 5.2.3. Comparisons of Detection Rate and False Alarm Rate

Figures18 and 19 show comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate is greater than 90%, detection rates of three algorithms have little differences, and that of RNSA is lower; false alarm rate of CB-RNSA is obviously lower than that of RNSA and V-Detector. For BCW1 data set, when the expected coverage rate is 99%, false alarm rate of RNSA is 55.2%, false alarm rate of V-Detector is 30.1%, and false alarm rate of CB-RNSA is 20.1% which declines by 63.6% and 33.2%, respectively. For high dimensional data set BCW2, when the expected coverage rate is 99%, false alarm rate of RNSA is 25.1%, false alarm rate of V-Detector is 20.5%, and false alarm rate of CB-RNSA is 12.6% which declines by 49.8% and 38.5%, respectively. On the one hand, CB-RNSA introduced clonal selection algorithm and limited the generation range of detectors, which made detectors generated in the low-coverage non-self space and improved the coverage rate. On the other hand, detectors and boundary selves were adopted for testing at the same time, the definition of anomaly was stricter, which reduced the rate of false positive.Figure 18
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW1).
(a) (b)Figure 19
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW2).
(a) (b)The ROC curve is a graphical method for classification model based on detection rates and false alarm rates. Figure20 shows comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA under two kinds of data sets, BCW1 and BCW2. A good classification mode curve should be distributed in the left-top of graphic as soon as possible. As can be seen from the diagram, CB-RNSA is superior to RNSA and V-Detector.Figure 20
Comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA.
(a)
BCW1 (b)
BCW2


## 5.2.1. Comparisons of the Number of Detectors

Figure16 shows comparisons of the number of mature detectors of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate increases, the number of mature detectors of three algorithms rises correspondingly. But the efficiency of CB-RNSA is superior to the other algorithms. For Haberman’s Survival data set, in order to achieve the expected coverage rate of 99%, RNSA needs 1033.1 mature detectors, V-Detector needs 351.4 detectors, and CB-RNSA needs 165.2 detectors which declines by 84.0% and 53.0%, respectively. For large data set Abalone, in order to achieve the expected coverage rate of 99%, RNSA needs 12893.2 mature detectors, V-Detector needs 1194.0 detectors, and CB-RNSA needs 615.4 detectors which declines by 95.2% and 48.5%, respectively. So, in the expectation of the same coverage rate, under different data dimensions and different training sets, the number of mature detectors of CB-RNSA has greatly reduced compared to RNSA and V-Detector.Figure 16
Comparisons of the number of detectors of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


## 5.2.2. Comparisons of the Cost of Detectors Generation

Figure17 shows comparisons of the cost of detectors generation of RNSA, V-Detector, and CB-RNSA. For Haberman’s Survival data set, when the expected coverage rate rises from 90% to 99%, the time price of RNSA increases from 7.7s to 291.0s, the time price of V-Detector increases from 0.6s to 29.8s, and the time price of CB-RNSA increases from 0.4s to 13.7s. For Abalone data set, when the expected coverage rate rises from 90% to 90%, the time price of RNSA increases from 241.7s to 2412.8s, the time price of V-Detector increases from 2.4s to 228.6s, and the time price of CB-RNSA increases from 1.3s to 82.5s. Therefore, with the rise of expected coverage rate, the time costs of RNSA and V-Detector increase very quickly, and the time cost of GB-RNSA increases more slowly.Figure 17
Comparisons of time costs of RNSA, V-Detector, and CB-RNSA.
(a)
Haberman’s Survival (b)
Abalone


## 5.2.3. Comparisons of Detection Rate and False Alarm Rate

Figures18 and 19 show comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA. As can be seen from the diagram, while the expected coverage rate is greater than 90%, detection rates of three algorithms have little differences, and that of RNSA is lower; false alarm rate of CB-RNSA is obviously lower than that of RNSA and V-Detector. For BCW1 data set, when the expected coverage rate is 99%, false alarm rate of RNSA is 55.2%, false alarm rate of V-Detector is 30.1%, and false alarm rate of CB-RNSA is 20.1% which declines by 63.6% and 33.2%, respectively. For high dimensional data set BCW2, when the expected coverage rate is 99%, false alarm rate of RNSA is 25.1%, false alarm rate of V-Detector is 20.5%, and false alarm rate of CB-RNSA is 12.6% which declines by 49.8% and 38.5%, respectively. On the one hand, CB-RNSA introduced clonal selection algorithm and limited the generation range of detectors, which made detectors generated in the low-coverage non-self space and improved the coverage rate. On the other hand, detectors and boundary selves were adopted for testing at the same time, the definition of anomaly was stricter, which reduced the rate of false positive.Figure 18
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW1).
(a) (b)Figure 19
Comparisons of detection rates and false alarm rates of RNSA, V-Detector, and CB-RNSA (BCW2).
(a) (b)The ROC curve is a graphical method for classification model based on detection rates and false alarm rates. Figure20 shows comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA under two kinds of data sets, BCW1 and BCW2. A good classification mode curve should be distributed in the left-top of graphic as soon as possible. As can be seen from the diagram, CB-RNSA is superior to RNSA and V-Detector.Figure 20
Comparisons of ROC curves of RNSA, V-Detector, and CB-RNSA.
(a)
BCW1 (b)
BCW2


## 6. Conclusions

Excessive detectors, high time complexity, and loopholes are main problems which current negative selection algorithms have face and greatly limit the practical applications of negative selection algorithms. This paper proposes a real-valued negative selection algorithm, named CB-RNSA. The algorithm introduces the clonal selection algorithm and randomly generates candidate detectors within stratified limited ranges based on clustering centers of self set, which reduces the number of detectors and the number of holes. Selves are divided into outlier selves, boundary selves, and internal selves, which adapts to the interference of noise data. When the algorithm runs for anomaly detection, mature detector set and boundary self set are used at the same time, which effectively improves the detection rate and reduces the false alarm rate. Theoretical analysis and experimental results show that the algorithm has better time efficiency and detector generation quality according to classic negative selection algorithms.



---

*Source: 2520940-2018-12-03.xml*