Addressing Optimisation Challenges for Datasets with Many Variables, Using Genetic Algorithms to Implement Feature Selection

2.1.

Classical features selection

All feature selection algorithms typically consist of four steps (see figure 1), namely:

1. 1.

   a subset generation step;

2. 2.

   evaluation of the subset;

3. 3.

   a step to check against the stopping criteria, and once this is met, finally

4. 4.

   a result validation step [5, 16], and [17].

Classically, a heuristic method is employed to generate subsets of features for evaluation procedures, where each subset is evaluated to determine the “goodness” of the selected features. The validation is done by carrying out different tests and comparisons with the previous subset. If a new subset has worse performance, then the previous subset is retained. This process is repeated until a stopping criterion is reached, as shown in figure 1. A feature is a variable in a dataset, and as mentioned previously, if the number of variables is large, this can lead to problems that are intractable, i.e. cannot be solved in polynomial time. One approach that can aid in finding solutions is to reduce the number of features by selecting features, to drop those features that are deemed unnecessary, or that may actually impede the predictive performance of a model.

A general feature selection problem, with n features and a fixed subset size of d, would require (nd) subsets to be examined to get the optimal result. Considering all subset sizes, it would generally require 2ⁿ subsets to be evaluated, and it has been shown that no non-exhaustive sequential search can be guaranteed to produce an optimal subset [18]. However, by creating an ordered sequence of errors for each of the subsets, a branch-and-bound feature selection algorithm can be used to find an optimal subset more quickly than an exhaustive search [19]. The problem of feature selection can be stated as follows [20]:

Given a set F of features (variables or attributes) and a set C of classes; and where m is the number of features, let be the dataset, where is the set of features, and f_i ∈ Rⁿ, and C_i ∈ Z₂ are the set of features describing a possible class C. For simplicity, we assume two classes, but this can be extended to more classes. The problem learning classifier can be stated as follows: find a set of parameters 𝜃 such that

where , and g is the model predictor function, The cost function is an error squared function of the form ; where 𝜃 ∈ Rⁿ is the vector of parameters for the model.

Given the ease of data collection, a particular issue is that they often have far more variables than are strictly necessary to achieve a correct result. This is more acute in clinical datasets. The problem becomes one of reconstructing the data set with a reduced, optimal, number of features, F_i ⊆ F;

Definition 1.

A feature set F_i ⊆ F, is said to be optimal if:

1. a.

   the relationships between F & C are maintained using F_i

2. b.

   F_i ⋂ F^C = ∅; where F^C is the complement of F_i.

Such a formulation lends itself to a combinatorial search for an optimal set of features (see [21–23]). An alternative approach is to consider the two problems of feature selection and classification together [24], through the use of scaling variables 𝜔_i ∈ Z₂, i = 1, 2, … , n.. for the features, such that the feature selection problem becomes one of optimising an objective function over 𝜔. Thus, a particular feature f_i is removed if 𝜔_i = 0. The overall problem becomes one of optimising for both 𝜃 and 𝜔 and can be written as

Remark.

The length of 𝜔_i ∈ Z₂, i = 1, 2, … , n is equal to the length of the number of features in the data set, where 𝜔_i is equal to 1 if the feature is present, and 0 if the feature is to be ignored. Thus, the vector is a binary bit-string, and as will be seen later is essentially the chromosome utilised in the genetic algorithm, where , i = 1, 2, 3, … , P is a set of chromosomes and P is the population size.

In order to investigate the properties of (2), we need the following proposition:

Proposition 1.

Let

(3)

Then for 𝜔 ∈𝛺;

The problem D (𝜔); s.t. 𝜔 ∈𝛺 is equivalent to solving equation (2).

The proof is routine and follows the methodology that can be found in [21] & [24]. The approach taken by a feature search algorithm for selecting optimal feature sets is often an iterative one, where two problems are repeatedly solved, these are:

1. 1.
   (4)
2. 2.
   (5)

2.2.

Feature selection using genetic algorithms (GAs)

A Genetic Algorithm ensures that over successive generations, the population “evolves” toward an optimal solution based on the principle of survival of the fittest (see [3, 9, 17]). GAs allow the combining of different solutions generation after generation to extract the best solution in the quickest time [25]. Generally, the search method used by Genetic Algorithms has lower complexity than the more formal approaches mentioned earlier [26].

The individuals in the genetic space are called chromosomes. The chromosome is a collection of genes where a real value or a binary encoding can generally represent genes. The number of genes is the total number of features in the data set. Thus, the vector is a chromosome, and 𝜔_i is the ith gene. The collection of all chromosomes is called the “population”, P. Typically, a set P of chromosomes, are generated randomly. The problem FSP2 is then solved iteratively through the use of two operators, namely Crossover and Mutation (see figure 2).

Every iteration or generation, a new set of chromosomes are evaluated through the use of a fitness function. This is typically the cost function used in FSP1. Given the population, P, there are essentially P subsets of features being evaluated at every iteration. In this approach, the chromosomes with the least performance (or fitness) are also eliminated, thus not available for the cross over or mutation operations. In this manner, good subsets are “evolved” over time [22]. The commonly used methods for selection are Roulette-wheel selection, Boltzmann selection, Tournament selection, Rank selection, and Steady-state selection. The selected subset is ready for reproduction using crossover and mutation. The idea of a crossover operator is that some combination of the best features of the best set of chromosomes would yield a better subset. On the other hand, mutation takes one chromosome and randomly changes the value of a gene. Thus, adding or deleting features in a subset. This process is repeated until there is no improvement, or as is often the case, a set number of iterations or generations is reached. This is illustrated in figure 3.

The general structure of the algorithm is as follows

Step 0 :

Choose an initial population, M, of chromosomes of length n

Step 1 :

Evaluate the fitness of each chromosome

Step 2 :

Perform Selection

Step 3a :

Perform Crossover

Step 3b :

Perform Mutation

Step 4 :

Evaluate fitness,

if stopping criteria satisfied Stop; Else go to Step 2.

Steps 1 and 4 solve PSP2, steps 3a and 3b solve FSP1.

The solution to both FSP1 and FSP2, can be considered to be a set of Kuhn-Tucker points, i.e. points that satisfy the K_T conditions for FSP1 and FSP2, but never together at the same time [22].

For most optimisation techniques, there is often a requirement that the cost function is monotone. However, there is no guarantee that this is satisfied globally. However, if the cost function is not locally monotone somewhere, a solution to the problem will not exist. It is possible to estimate the number of generations required to arrive at an optimal set of features of the requirement of monotonicity is enforced in the GAs. Thus, if it were made explicit that from one generation to generation the best subset is an improvement on the previous best, the sequence of cost function values would be monotone. One of the consequences of the monotone requirement is that the initial population of chromosomes and the final set of chromosomes are disjointed.

This condition can be satisfied for the initial population only; for subsequent generations, this may be not possible, for the same operation on two different pairs of chromosomes may result in the same set of chromosomes as children. However, given this restriction, it is interesting to use this to gain an insight into the operation of GAs.

Definition 2.

A generation g is an ordered set of M chromosomes, where M is the initial population of chromosomes. Thus if , then the fitness function J has the property

(6)

Definition 3.

The fitness function J (.) is said to be genetically monotone if for the i’th generation

(7)

The second definition is interesting and required for further analysis. It essentially focuses on the first or leading chromosome of any generation, since for each generation, the chromosomes are ordered (definition 2). This definition also suggests that with every successive generation, the fitness of the leading chromosome of the i’th generation is better than the previous generation.

Definition 4.

Two generations gⁱ and gⁱ⁺¹ are said to be generationally disjoint if gⁱ ∩ gⁱ⁺¹ = ∅.

This definition is required to keep in line with the requirements of analysis based on graph searches.

Proposition 2.

For a given fixed M, where M is the number of chromosomes, and a genetically monotone fitness function J (.), if the genetic operators are such that every generation is generationally disjoint, the maximum number of generations, N_g, needed to determine the fittest chromosome is then given by

(8)

The proof follows from the definitions. The conditions (assumptions) here are often difficult to satisfy. Getting an ordered set for a generation is already present in the algorithm, and so is the presence of a genetically monotone function in the form of a fitness function. However, the genetically disjoint requirement is difficult to satisfy, and there is no guarantee it will be fulfilled at all during a given run of the algorithm. Thus, often the terminating criteria of a genetic algorithm are the number of generations. In most random search algorithms, the function J (.) is guaranteed to be monotone.

Definition 5.

Two generations gⁱ and gⁱ⁺¹ are said to be partially generationally disjoint if gⁱ ∩ gⁱ⁺¹ ≠∅ and |gⁱ ∩ gⁱ⁺¹| < M.

Proposition 3.

If the sequence of generation sets g¹, g², g³, …, g^N, where N is the Nth generations are all partially genetically disjoint, and given a monotone fitness function, then as N → ℵ∕M the top feature subset is given by is that that where is the optimal feature subset.

The proposition is both intuitive and follows the fact that every generation set gⁱ is ordered and that the fitness function is genetically monotone thus for all i. Essentially this proposition is suggesting that in the limit the maximum number of generations leads to an exhaustive search through all subsets of features. In practice there are feature sets, which can be discounted, these the sets with no features, all the features and one feature; therefore, the number of subsets to be evaluated is 2ⁿ − (n +2). Simultaneously, if M is sufficiently large, the number of generations is reduced significantly. However, this is a technological limitation rather than an algorithmic limitation. In the limiting case as M → n what is obtained is nothing more than an exhaustive search.

Louis and Rawlins [27] have shown that the crossover operator has no role to play in the convergence of the algorithms, as the average Hamming distance of the population in every generation is maintained. Their analysis indicated that the selection criteria are on which dictates the convergence rate of the genetic algorithm. Their analysis shows that the traditional crossover operation, like 1-point, two-point l-point, uniform crossover, does not change the average Hamming distance of the chromosomes within a generation, and thus, the difference of the distance from generation to generation is maintained. They suggested that selection criteria are the main parameter for determining convergence. However, Greenhalgh and Marshall [27], showed that irrespective of the coding (binary or otherwise), the key controller of convergence (or the ability of the genetic algorithm to have visited all the possible points available) is given by the mutation probability. They indicated, following on from Aytug et al. (1996) [28] that a mutation rate of ; where K is the cardinality of coding rate 𝜇 ≤0.5, allows for convergence in the worst case (it is essentially an upper bound). However, most implementations of genetic algorithms allow for a mutation rate far smaller than this. This then leads to the following.

Proposition 4.

For a given 0 ≤𝛾 <1, and 𝜇 ≤0.5 (where 𝛾 is the crossover parameter) the genetic algorithm generates feature subsets which are generationally disjoint. i.e.

(9)

The proof is intuitive. Even though crossover may lead to all the subsets of a particular generation being identical, the presence of mutation changes this. However, with both present, it is always the case [27]. These two conditions imply that every generation has a set of chromosomes which have not been evaluated in the previous generation, that the crossover operations do not generate the same solutions within a generation, and we would need at most generations to arrive at a solution. Within the definitions of the GAs, it is not possible to guarantee both of these can be satisfied. If they are, it is feasible to determine the number of generations required to arrive at a solution given the initial population size.

2.3.

Complexity of the GAs

In order to assess the complexity of the Genetic Algorithms, we need to consider the following:

1. (a)

   The initial population size, and

2. (b)

   The number of generations required to satisfy the performance criteria.

GAs can often reach a state of stagnation, a possible reason for this that the above two points act as constraints, and it becomes feasible that the same population is generated at every generation. In order to get a deeper insight into the process, consider the following:

Since n-features means that each chromosome consists of n-bits, the total number of possible chromosomes is 2ⁿ. However, two of these can be discarded—these are when all the genes are either 0 or 1. If we consider these 2ⁿ chromosomes as the vertices of an n-dimensional hypercube, an exhaustive search by the Genetic Algorithm will cover all the possible vertices, given by

However, the problem of the search can be reduced in complexity if searching vertices can be interpreted as a search through a graph [26].

3.1.

Population size

In most evolutionary methods, and Genetic Algorithms in particular, the population size—i.e. the number of chromosomes—is of particular interest. This often influences the quality of the solution and computing time and is also dependent on the available memory [32–34]. There have been a number of studies on appropriate population sizes, see [35, 36], with many suggesting that a “small” population size would result in poor solutions [37–39], while a “large” population size would result in greater complexity in finding a solution [40, 41]. Indeed, this is apparent if the problem is viewed as a search through the 2ⁿ vertices of the n-dimensional hypercube. However, none have so far suggested an appropriate size, or at least an effective estimate.

3.2.

Selection of chromosomes for genetic operations

The chromosomes are evaluated using a fitness function based on Oluleye’s fitness function [31]. Here the function is minimising the error while at the same time reducing the number of features (see equation (2)). The fitness function which evaluates the chromosomes is based on the kNN-function [31]. The chromosomes are ranked based on the kNN based fitness. In this case, chromosomes with the lowest fitness have a better chance of surviving.

A roulette wheel selection approach was used for selecting the chromosomes for the crossover operations where each individual is assigned as a “slice” of the wheel in proportion to the fitness value of the individual. Therefore, the fitter an individual is, the larger the slice of the wheel. The wheel is simulated by a normalisation of fitness values of the population of individuals as discussed in FSP2. The selection process is shown below

Step 1

Determine the sector angles for each chromosome

Step 2

Generate a random number r ∈ [0,2𝜋]

Step 3

Select the i’th chromosome

Step 4

And repeat.

It should be noted that the chromosomes are a bit string, clearly for such representation we could use a single point or a n-point crossover. Of course, a single point crossover would be limiting if the number of variables is large. However, an n-point crossover strategy would be more suitable for a large set of variables [42–44].