key: cord-0044834-as97zq6d
authors: Abdelkhalek, Rihab; Elouedi, Zied
title: A Belief Classification Approach Based on Artificial Immune Recognition System
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_25
sha: fd8a8ebcd236733b4fddb55f91627c8bee41fd21
doc_id: 44834
cord_uid: as97zq6d

Artificial Immune Recognition Systems (AIRS) are supervised classification methods inspired by the immune system metaphors. They enjoy a great popularity in the filed of machine learning by achieving good and competitive classification results. Nonetheless, while these approaches work properly under a certain framework, they present some weaknesses basically related to their inability to deal with uncertainty. This is considered as an important challenge in real-world classification problems. Furthermore, using traditional AIRS approaches, all memory cells are considered with the same importance during the classification process which may affect the final generated results. To tackle these issues, we propose in this paper a new AIRS approach under the belief function framework. Our approach tends to handle the uncertainty pervaded in the classification stage while taking into account the number of training antigens represented by each memory cell. The performance of the proposed evidential AIRS approach is validated on real-world data sets and compared to state of the art AIRS under certain and uncertain frameworks.

Artificial Immune Recognition System (AIRS) [1] is considered as a popular supervised classification method fully inspired by the biological immune system metaphors. It allows us to make suitable decisions related to various types of problems. Yet, the AIRS technique has achieved better and competitive classification results when compared to other well-established classification techniques like Naive Bayes, decision trees and artificial neural networks classifiers [2] . That is why, it has attracted a great deal of attention in different areas such as pattern recognition, computer virus detection, anomaly detection, optimization and robotics [3] . Different AIRS approaches have been proposed in the literature aiming to improve the classification accuracy [4] . However, while these approaches work properly under a certain framework, they present some weaknesses basically related to their inability to deal with uncertainty. In fact, uncertainty may undoubtedly spread throughout the classification process, which may deeply affect the classification results. Thus, managing uncertainty in AIRS systems becomes a widespread interest.

In this context, various theories like the fuzzy set and the possibility theories [5, 6] can be adopted to deal with imperfection within AIRS. The belief function theory [7, 8] is considered among the most appropriate and powerful theories for representing and reasoning under uncertainty. It presents a flexible and rich framework for handling imperfection in different levels ranging from the complete ignorance to the total certainty. Indeed, some works have focused on the problem of managing uncertainty in the field of AIRS, either by means of fuzzy set theory [10] [11] [12] [13] or possibility theory [14] . For instance, a new medical decision making system conceived by fuzzy-AIRS was proposed in [10] for the task of lymph diseases diagnosis. In such work, the resource allocation mechanism of AIRS was replaced by fuzzy resource allocation in order to improve its classification performance. However, Golzari et al. [11] performed a statistical study that proved that the integration of fuzzy resource allocation causes significant improvement in a minority of data sets. On this basis, they assumed that investigating the more accurate fuzzy memberships, fuzzy rules and fuzzy values may increase the accuracy in more data sets. Later, authors in [12] proposed a fuzzy weighted pre-processing strategy before the application of AIRS which is based on sample means of each feature values. More specifically, they defined two membership functions known as input and output membership functions which are allowed to allocate a new feature value for each feature in accordance with its old value. An extended version of AIRS with Fuzzy-KNN has been proposed in [13] where classes memberships have been assigned as a function of the vectors distance from the K-nearest neighbors. On the other hand, authors in [14] have introduced a new classification technique combining the AIRS method within the possibility theory, where the training instances have been represented via possibility distributions. More recently, a very preliminary work has been proposed under the belief function theory [15] where the K-nearest antigens are considered as different pieces of evidence contributing to the final class assignment. Nonetheless, in such AIRS approaches, all memory cells are considered with the same importance during the classification process which may affect the generated results. Actually, an improved version of AIRS, called AIRS3, has been proposed in this context. Despite its good performance, such approach is not able to deal with the uncertainty pervaded in the final classification results. That is why, we propose in this paper a new AIRS3 approach under the belief function framework. Our aim in this work is not only to handle the uncertainty pervaded throughout the classification process, but also to take into account the number of training antigens represented by each memory cell.

The remainder of this paper is organized as follows: Sect. 2 recalls the belief function theory basic concepts. Section 3 introduces the Artificial Immune Recognition System. Our proposed Evidential AIRS approach is described in Sect. 4. Section 5 illustrates its experimental results conducted on real-world data sets. Finally, the paper is concluded in Sect. 6.

The belief function theory, also called evidence theory, is a flexible and rich framework for dealing with uncertainty [7, 8] . In this section, we recall its basic concepts and operations as interpreted in the Transferable Belief Model [9] .

In the belief function theory, a problem domain is represented by a finite set of elementary events called the frame of discernment, denoted by Θ, which contains hypotheses concerning the given problem [9] such that: Θ = {θ 1 , θ 2 , · · · , θ n }. In fact, all the possible values that each subset of Θ can take is called the power set of Θ and denoted by 2 Θ , where 2 Θ = {A : A ⊆ Θ}.

A basic belief assignment (bba) is an expression of the belief committed to the elements of the frame of discernment Θ [8] . It is a mapping function such that:

Each mass m(A), called a basic belief mass (bbm), quantifies the degree of belief exactly assigned to the event A of Θ.

The bba which has at most one focal element aside from the frame of discernment Θ is called simple support function. It is defined as follows:

where A is the focal element and w ∈ [0,1].

Considering two bba's m 1 and m 2 induced from two reliable and independent information sources, the evidence can be combined using Dempster's rule of combination defined as:

where

To make decisions, beliefs can be represented by pignistic probabilities such as:

Artificial Immune Recognition System (AIRS) is a resource limited supervised learning algorithm inspired by immune metaphors [1] . In what follows, we recall the two improved versions of AIRS namely AIRS2 [19] and AIRS3 [20] .

Two major phases characterize the AIRS2 method namely, the learningreduction procedure and the classification procedure.

The learning-reduction procedure represents the main phase in the AIRS algorithm. The input data present the training set T where each object is considered as an antigen following the same representation as an antibody [20] . Each antigen is represented by a set of attributes values and class values. The output of this procedure is a reduced data set called memory cell pool (MC) containing memory cells, which are later used in the classification process. This phase is divided into four stages: initialization step, memory cell identification and Artificial Recognition Balls (ARB ) generation, competition for resources and development of a candidate memory cell, and memory cell introduction.

The initialization step can be considered as a pre-processing stage and it is performed on the following three steps:

-Data normalization This step consists in normalizing all numeric attributes of the training data in order to make sure that the Euclidean distance between two training items is in the range of [0,1]. The normalized Euclidean distance is also used as an affinity measure between two cells. It is computed as follows:

Where ag 1 and ag 2 are the two attribute vectors representing two cells (data samples) and m is the number of attributes. -Computing the affinity threshold After normalization has been performed, the af f inity threshold is then computed based on Eq. (6).

Where n is the number of antigens in the training set, ag i and ag j are receptively the i th and j th antigens and affinity (ag i , ag j ) represents the affinity measure between the two antigens ag i and ag j .

The final stage is the initialization of the memory cell pool (MC) and the ARB pool. This is done by randomly selecting 0 or more antigens from the training set to be included in the MC and ARB sets.

At this level, only one antigen from the training instances is required in the training process and the following steps outlined below are applied.

mc match identification For each memory cell in the MC pool having the same class as the training antigen ag, we calculate the stimulation according to Eq. (7) below:

The cell having the greatest stimulation is selected as the best match memory cell denoted as mc match. It will be employed in the affinity maturation process. If there is no mc in the MC pool having the same class as the training antigen, this antigen will be integrated directly to MC.

Once the mc match is selected, this memory cell is used to generate a number of mutated clones added to ARB pool. The number of clones is proportional to the affinity between mc match and the presented antigen ag and it is computed as follows:

At this point, a set of ARB s which includes mc match and mutations of mc match is considered. We aim in this phase to extract a candidate memory cell (mc candidate) which better recognizes the given antigen ag. To this end, a computation of the normalized stimulation between each ARB and the antigen is first performed and a finite number of resources is then allocated to each ARB such as:

Each class has a restricted number of resources allowed to be allocated. If the total number of resources of all the ARB s overcomes the allowed limit, the surplus resources are eliminated from the weakest ARB and then empty ARB s will be deleted from the system. Therefore, only ARB s with the highest stimulation level are able to compete for resources. After this competition, a testing process of the stopping criterion is performed. This latter is achieved if the mean affinity value for all the existing ARB s with the antigen surpasses the Stimulation threshold which is a pre-defined parameter. Otherwise, ARB s will be mutated and the new mutated clones will be included into the ARB pool. Then, the competition for resources processes will be held and only survived ARB s are going to move through the clonal expansion and the mutation procedures until the stopping criterion is reached. The number of clones corresponding to each ARB is measured using the following equation:

Finally, the ARB having the highest stimulation level will be picked up as the candidate memory cell (mc candidate).

This step corresponds to the final stage of the training process where the memory cell pool is revised. If the affinity between the extracted mc candidate and the antigen ag is higher than that of the mc match, the mc candidate will be integrated to MC, becoming a long-lived memory cell. Moreover, if the affinity measure between mc match and mc candidate is also lower than the product of the affinity threshold and affinity threshold scalar, mc match will be replaced by mc candidate in the set of memory cells.

Step Once the training phase is achieved, the resulting MC pool will be used for the classification process. In this context, the K-Nearest Neighbors (KNN) technique is adopted and the test antigen is classified by the majority vote of the K nearest memory cells.

In order to improve the performance of AIRS2, a new version called AIRS3 has been proposed in [20] . The main idea of the AIRS3 is to add a new component allowing to keep the number of represented antigens (numRepAg) for each memory cell in the resulting memory cell pool. This number is preserved during the training phase and will be used in the classification stage. An extended version of the K-Nearest Neighbors is then applied in the classification process to take into account numRepAg. In this version, the K value becomes the number of training antigens represented by some memory cells in MC instead of the number of selected memory cells. The sum of numRepAg of all chosen cells must be equal to K. Thereafter, for each class label, the sum of numRepAg of all the selected cells having the same class label will be computed. Finally, the new unlabeled antigen will be assigned to the class with the highest sum of numRepAg.

The two standard versions of AIRS2 and AIRS3 show a good performance under a certain context. However, these two AIRS approaches are not able to deal with the uncertainty pervaded in the final classification results. Hence, we propose a new version of AIRS3, where we embrace the belief function theory for handling such uncertainty while taking into account the number of training antigens represented by each memory cell. The proposed approach is called the Evidential AIRS3, that we introduce in the next section.

Inspired by the standard AIRS3 method, we propose a new classification version of AIRS under the belief function framework. Our main goal is to improve the classification performance of the existing AIRS approaches under certain and uncertain frameworks. For this purpose, we opt for the Evidential K-Nearest Neighbors (EKNN) [16, 17] in order to take into account the uncertain aspect of the final classes assignment. Instead of the standard K-Nearest Neighbors [18] commonly used in AIRS, the EKNN formalism is adapted within the AIRS3 where different belief function tools come into play. The proposed approach, that we denote by Evidential AIRS3 (EAIRS3), is based on two consecutive reduction phases. The first one is performed during the learning-reduction procedure where we obtain the first reduced memory cell pool (MC pool). Otherwise, the second reduction is performed during the selection of the best-stimulated samples, taking into account the number of represented antigens by each memory cell denoted by numRepAg. Hence, we get in the end a new reduced MC poll called R-MC pool. The obtained R-MC pool will be considered as the input for the EKNN and the classification task will be performed accordingly. Figure 1 below illustrates the flowchart of the Evidential AIRS3 approach.

In order to better explain our contribution, let us first define and clarify the basic notations to be used in our approach. 

The classification process of the Evidential AIRS3 is based on two parameters, α and γ = (γ 1 , · · · , γ p ) which will be used in the next stages. Therefore, the first step consists in initializing and computing these two parameters. We assign to the parameter α the value 0.95 as mentioned in the EKNN formalism [16] . In fact, this value is highly recommended in order to have good results and to obtain a best classification accuracy. Otherwise, in order to compute the γ p parameter, we extract the set of the training samples having the same class C p and we calculate the inverse of the mean distance between each pair of antigens in this set. This computation is executed based on the normalized Euclidean distance defined by:

Where ag 1 and ag 2 are the two attribute vectors representing two data samples and dim is the number of attributes. In the end of this step, we store the values of γ p computed for each class in a vector γ. This latter will be further employed in the creation of the basic belief assignment (bba).

The second phase of the Evidential AIRS3 approach is the collection of the beststimulated antigens while taking into account the number of represented antigens (numRepAg) by each memory cell in the MC pool. That is why, we calculate first the similarity between the unlabeled antigen and the whole samples in the MC pool. According to the computed distances, we have to pick out the memory cells having the lowest distances. Unlike the evidential approach proposed in [15] , the selection procedure is achieved when the sum of the numRepAg corresponding to the selected cells is equal to K. Hence, the result of this step is a new reduced MC pool, named R-MC pool, containing the nearest neighbors to the test antigen having in total: numRepAg = K.

Traditional methods in this step, generate the basic belief assignments (bba's) of all the K-nearest neighbors which could be too complicated for a large value of K. In our approach, we aim to alleviate this problem by generating only the bba's of the obtained cells in the R-MC pool. In other words, these extracted cells will be the pieces of evidence on which we will rely on the classification and the decision making processes. By exploring the R-MC pool obtained in the previous step, we have to generate the basic belief assignment (bba) for the n selected memory cells such that:

Where d i = d(ag, mc (i) ) is the euclidean distance between the antigen ag and each memory cell mc (i) ∈ I n , c p is the class of mc (i) (i.e. c i = c p ), φ p is a decreasing function verifying:

A popular choice for the decreasing function φ p (d (i) ) is:

We recall here that γ p and α are the two parameters already computed in the first step.

Once the bba's are generated for each memory cell in the R-MC pool, we combine these bba's using the Dempster's rule of combination as illustrated in Fig. 2 such that: m = m(.|mc (1) 

In order to get the final bba corresponding to the unlabeled antigen, the evidence of the n memory cells are aggregated using the following expression:

Where N is a normalized factor [16] .

The last step of our approach is the decision making process where we should provide an appropriate class to the test antigen. That is why, we opt for the pignistic transformation function, denoted by BetP , which allows us to create a probability function from the n generalized basic belief assignments. Once the pignistic probability distribution is derived, the test antigen is assigned to the class having the maximum degree of pignistic probability.

In order to evaluate the performance of our Evidential AIRS3 approach, we performed various experiments on real world data sets selected from the U.C.I repository. In these tests, we compare the Evidential AIRS3 with the two standard AIRS methods under a certain framework namely, AIRS2 and AIRS3. Furthermore, two other AIRS approaches working under uncertainty have been compared namely the Fuzzy AIRS2 and the Evidential AIRS2.

Five real data sets have been used in our experiments namely, Cryotherapy (C), Wine (W), Fertility (F), Somerville Happiness Survey (SHS) and Pima Indians Diabetes (PID). The specifications of each data set are shown in Table 1 below, where # nbInstances is the number of antigens, # nbAttributes represents the number of attributes and # nbclass is the number of class labels of a data set. For all these data sets, we used the following parameter values for all the diverse versions of AIRS employed in our comparison: AIRS2, AIRS3, Fuzzy AIRS2, Evidential AIRS2 (EAIRS2), and Evidential AIRS3 (EAIRS3):

Clonal rate = 10, Mutation rate = 0.4, HyperClonal Rate = 2, Number of resources = 200, Stimulation threshold = 0.3, Affinity threshold scalar = 0.2.

In addition, we have tested with different values of K = [3, 5, 7, 8, 9, and 10] .

In order to evaluate our approach, we rely on one of the most frequent metrics which is the Percent Correct Classification (PCC). This evaluation metric computes the classification accuracy using the following expression:

P CC = N umber of correctly classif ied instances T otal number of classif ied instances (17) Therefore, during our experiments, we opt to the cross-validation technique in order to assess the performance of our method. More specifically, we choose to use the 10-fold cross-validation where we estimate the efficiently of our approach by averaging the accuracies derived in all the 10 cases of cross validation.

Considering different versions of AIRS, we compare the accuracy of our method to the traditional AIRS2, AIRS3, Fuzzy AIRS2 and EAIRS2. Our comparison is based on the PCC of the several used K-values. The experimental results through the different K values are illustrated in Fig. 3.   Fig. 3 . Accuracy of used data sets through different K-values Accordingly, we observe that our approach EAIRS3, outperforms the other versions of AIRS in most data sets through the various selected K-values. For example, for the data set W with K = 10, the PCC reaches 85.95% with EAIRS3, while it corresponds respectively to 54.35% with AIRS2, 84.18% with AIRS3, 68.01% with Fuzzy AIRS2 and 55.03% with EAIRS2.

In Table 2 , we represent the comparison results of the average PCC obtained for each data set with the different employed K-values.

We can notice through the results shown in Table 2 , that EAIRS3 surpasses all the other versions of AIRS in term of classification accuracy for all the used 

In this paper, we have proposed a new AIRS approach under the belief function theory. Our Evidential AIRS3 approach allows not only to deal with the uncertainty pervaded in the classification process, but also to take into account the number of training antigens represented by each memory cell. Experimental results have shown an improvement of the classification performance over state of the art AIRS methods under certain an uncertain frameworks.

A resource limited artificial immune classifier

A new classification method for breast cancer diagnosis: feature selection artificial immune recognition system (FS-AIRS)

Artificial Immune Systems: A New Computational Intelligence Approach

Artificial immune recognition system (AIRS)-a review and analysis

Fuzzy sets

Possibility theory: an approach to computerized processing of uncertainty

A generalization of Bayesian inference

A Mathematical Theory of Evidence

The transferable belief model for quantified belief representation

Automated identification of diseases related to lymph system from lymphography data using artificial immune recognition system with fuzzy resource allocation mechanism (fuzzy-AIRS)

Effect of fuzzy resource allocation method on AIRS classifier accuracy

Principles component analysis, fuzzy weighting pre-processing and artificial immune recognition system based diagnostic system for diagnosis of lung cancer

Diagnosis of diabetes diseases using an artificial immune recognition system2 (AIRS2) with fuzzy k-nearest neighbor

Possibilistic AIRS induction from uncertain data

Evidential artificial immune recognition system

A k-nearest neighbor classification rule based on Dempster-Shafer theory

An evidence theoretic kNN rule with parameter optimization

Nearest Neighbour NN Norms: NN Pattern Classification Techniques

Artificial immune recognition system (AIRS): revisions and refinements

Re-visiting the artificial immune recognition system: a survey and an improved version