Robust,interpretable and high quality fuzzy rule discovery using krill herd algorithm

2.1 Datasets

People in the medicine usually do not have a great knowledge of data mining. They need the output of a data mining tool to be near natural language, and to have high quality and robust, so that no confusion takes place. Because our method has a high quality and is interpretable and robust, we have chosen the medical data.

In the paper, four UCI medical datasets are used (PIMA, Breast cancer, Heart, CMC). We try to extract the fuzzy rules to determine the presence or absence of diabetes in a way to minimize variance, on the PIMA dataset. Despite the fact that many forms of heart diseases can be prevented or treated with healthy lifestyle choices, we will try to take a step in the early detection of the heart diseases. In fact, every human is likely to control his breeding and we try to extract mining fuzzy rules that suggest better contraceptive methods with low variance. Most doctors feel that early detection of breast cancer saves thousands of lives each year and we are happy to do our work in this area. Table 1 shows our datasets with their characteristics that are used in this paper. All of the features are numeric in the paper.

2.2 Fuzzy reasoning method

For n-dimensional pattern classification problems, the following fuzzy if–then rules are applied in the design of our robust algorithm: R j : if X 1 = A j 1 and X 2 = A j 2 and … and X n = A jn then class is C j with CF j , j = 1 , 2 , … , N where R _j is rule index, X _i denotes a linguistic variable, A _ji is a linguistic fuzzy term, c is number of classes and C _j  = 1, 2, …,  h demonstrate consequent class and CF _j is a certainty grade of this rule in the unit interval [0, 1], and N is a number of rules. All attributes of datasets are converted to numeric attributes, so are normalized between [0, 1].

To improve interpretability of fuzzy rules we used linguistic variables in this study. Variable X _i has a linguistic set U = {VL,  L,  M,  H,  VH} that is illustrated in Fig. 1; each value of X _i uniformly shows 1/5 of domain [0, 1]. We also used don’t care value as all of those values. The total number of if - then rules with n features is 6 ⁿ and we decided to select a best rule set from them. Selecting a rule set enlarges the search space and solving this problem with large space computationally is very expensive.

Our work is a c-class problem in the n-dimensional space with numeric attributes. Also we have m real instances X _p  = (X_p1,  X_p2,   … ,  X _pn ) ,  p = 1, 2, 3, … m are given as training patterns.

In this classification system, the result C _j and certainty grade of rule CF _j will be calculated by the following: first we calculate the compatibility of each training pattern with the fuzzy if - then rule R _j by the following then we calculate the whole compatibility grades for each class: β class h ( R j ) = ∑ x p ∈ class h ∏ i = 1 i = n μ Aji ( x p ) , p = 1 , 2 , … m h = 1 , 2 , … , c(1) where μ _Rj is the membership function of A _ji . In next step find the consequent class C _j that has maximum β_class h (R _j ):

β class c j = max { β class 1 ( R j ) , β class 2 ( R j ) , … , β class h ( R j ) }(2)

If there is more than one class with maximum value for β_class h (R _j ), we do not assign any consequent class for R _j . Then we can calculate certainty grade of R _j and for an input pattern X _p  = (X_p1,  X_p2, …,  X _pn ) the winner rule R _j will be calculated by following: μ j * ( x p ) . CF j = max { μ j * ( x p ) . β class c j - ( ∑ h ≠ c j β class h ( R j ) / c - 1 ) ∑ h = 1 c β class h ( R j ) : j = 0 , 1 , … , N }(3)

Thus, we can identify the consequent class of input pattern with the aforementioned formula.

We apply Krill Herd (KH) [13] algorithm as our evolutionary algorithm that is suggested more recently. KH has high exploration and exploitation ability on the search space. The position of the krill individuals is formulated by three main actions: movement induced by the presence of other individuals, foraging activity, and random diffusion [13]. KH has the particle swarm nature with the genetic characteristics. We explain more about KH in the Section 3.1. We modify the KH to suggest a robust learning algorithm to learn high quality FRBSs. Unfortunately, the KH is offered to optimize the continuous problems and not applied in the discrete problems and data mining context, especially on learning FRBSs, until now. In this paper we propose a binary KH for extraction fuzzy rules in the medical domain according to the binary particle swarm optimization concepts [14] with innovation.

In this section we explain the behavior of KH and in the Section 3 we introduce a novel binary KH to generate fuzzy rule sets in which it follows our measures: Maximization of accuracy and minimization of SRL, NR, and standard deviations of these measures.

The general policy of the KH is that krills are moving toward food and spaces with more congestion. In the natural system, the fitness of each individual is supposed to be a combination of the distance from the food and from the highest density of the krill swarm [13]. The time-dependent position of an individual krill in 2D surface is explained by the following three main actions [15]: for ith krill we have dX i dt = N i + F i + D i(4) where N _i is the motion induced by other krill individuals; F _i is the foraging motion, and D _i is the physical diffusion of the ith krill individuals; these are explained as following:

A. Movement induced by other krill individuals (N)

According to theoretical arguments, the krill tries to keep a high density and move due to their mutual effects [15]. The direction of motion induced, is calculated from local effect of swarm density, a target effect of swarm density, and a repulsive effect [15].

B. Foraging activity (F)

First, we define a virtual food and then we calculate the foraging motion in terms of two main effective parameters. The first one is the food location and the second one is the previous experience about the food location [13].

The food effect is defined in terms of its location. The center of food should be found at first and then try to formulate food attraction. This cannot be determined but can be estimated.

C. Random diffusion (D)

The physical diffusion of the krill individuals is considered to be a random process [13]. This motion can be express in terms of a maximum diffusion speed and a random directional vector. The following Lagrangian model is generalized to an n dimensional decision space: X i ( t + Δ t ) = X i ( t ) + Δ t dX i dt(5) Δ t = C t ∑ j = 1 NV UB j - LB j(6) where NV is the total number of variables, and LB _j and UB _j are lower and upper bounds of the jth variables (j = 1, 2, …,  NV), respectively. C _t is a constant number between [0, 2].

After new positions of krill are determined, genetic operators (crossover and mutation) are applied. For more information about KH algorithm, especially the parameters descriptions, you can refer to [13]. It should be noted that everyone can be use own algorithm rather than KH algorithm in stage 1 and 2 of our proposed method that is suggested to extracting low number of the high quality rules in robust way.

3.1 Generating candidate rules (Stage 1)

Here, we will explain binary KH and describe that how MP is filled. Binary KH algorithm to generate high quality candidate rules is illustrated in the Fig. 2, step by step. In step 1, a Random Pool (RP) is created that contains a fixed number of fuzzy if-then rules for each class in a random way. Each antecedent in if-then rules accept one of the fuzzy linguistic terms as very-low, low, medium, high, very high and don’t care. Fuzzy linguistic terms are randomly distributed into rules in a way that don’t care probability is higher than others. In the step 2 krills are initialized. The number of krills dimension is equal to number of rules of the random pool. 1 for ith binary dimension of krill, shows that ith rule in random pool is used in the krill and 0 shows that ith rule in the random pool is not used in the krill. So, each krill shows a rule set. After initialization in step 3, krills are evaluated and NCP and NMP of the krills are determined. Each krill represents a rule set and each rule set has some rules and rules have different NCPs in current rule set; The event that takes place in step 4 (RSA step) is that krills are analyzed using NCPs. In analyzing of a rule set, these three groups of rules are eliminated: first, the rules that their NCPs are lower than min-ncp (min-ncp is the one of the important input parameters) on validation dataset. The second group is consisted of a percent of worst rules in the rule set (percent-of-elimination is another input parameter) on validation dataset. The worst rules are determined by sorting the rules by their fitness. Fitness is calculated as follows: fitness = NCP i 2 NMP i(7)

RSA eliminate N (N = percent-of-elimination * number of rules in rule set) worst rules. It is possible to have duplicated rules in the rule set, and so, the third group of rules that should be eliminated, are the rules that are duplicated. After eliminating these three groups of rules, rule set is evaluated again. After an elimination process, the found rule set changes and should be evaluated again since elimination of a rule affects the entire rule set. RSA will be run until no pruning occurs. In step 5, best krill is determined. Determination of the best krill has a huge effect on results and objectives. Many modes of the best krill detection are examined and finally, we decide to use a policy that says: the krill that has best fitness, is the best krill; if there are two krill with equal fitness, the krill have lower NR will be selected and if NRs of them are equal too, the krill has lower SRL will be selected and if SRLs are equal, one of them are selected as best krill in random way. This policy gives the best accuracy, interpretability and robustness from other policies like giving any weight to each of the objectives in classic multi-objectivemethods.

Induced Motion, Foraging Motion, Physical diffusion (6, 7 and 8) steps of approach are similar to KH, but krill values are binary (1 or 0). In step 9, genetic operators are used. Crossover and Mutation are applied on each dimension of the problem. In Crossover, the approach uses tournament selection [16] and for Mutation in each dimension, mutation probability in changing 1 to 0 is higher than changing a 0 to 1; with this policy we have low NR and SRL. In the last step, new position of the krill should be determined. In the binary KH, the positions are updated as in continuous version. The major difference between binary KH with continuous version is that X _i  (t + Δt) is normalized by sigmoid function, then a random number between [0.5, 1] (that is experimentally obtained) is generated, if sigmoid (X _i  (t + Δt)) is higher than random number, 1, and else 0 is applied. Binary KH for generating the candidate rules is performed several times in a parallel way and each thread of parallelism generates a rule set. Rule sets accumulated in the MP and are sent to second stage of our algorithm. We should not change NCPs of rules in MP, until the first step of Stage 2 is finished.

We set global parameters of binary KH for generating the candidate rules according to follows: Population Size = 50; Number of parallel threads = 30; Max-Iteration = 300; w-inertia = 0.5; D-max = 0.002; N-max = 0.01; V-Food = 0.02; P-crossover = 0.9. All of the parameters are chosen by trial and error. These parameters are explained in [13]. The parameter values after tuning by trial and error are listed in Table 2.

First column in Table 2 shows dataset name; the second column shows number of the training patterns; the third column shows number of validation patterns; the fourth column shows number of the test patterns and the fifth column shows minimum NCP for each individual’s rules where, I _t is index of ith execution thread. I _t makes it possible to have elected rules that come from entire search space, since in each parallel thread we have a different value for min-NCP. The sixth column shows percent of individual rules that should be eliminated; next column shows the number of random rules in the initial and three lost columns shows probabilities of the mutation. Probability of the cross over on all datasets is set to 0.8.

We run 30 threads of binary KH for generating candidate rules on each four dataset, and results that are obtained are shown in Table 3. A-SD, SRL-SD and NR-SD shows standard deviations of accuracy, sum of rules length (SRL) and number of rules (NR) respectively. The number of MP rules shows the number of candidate rules that are obtained from all threads.

By minimizing Sum of SDs, our robust algorithm gives robust results that people can trust on it. In fact, our main innovation is in this stage, and we suggest a robust method that get the MP and give a rule set as a result that not only has high accuracy and interpretability, but also has low variance on results.