Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Genetic algorithms: fitness function for feature selection algorithm

I have data set n x m where there are n observations and each observation consists of m values for m attributes. Each observation has also observed result assigned to it. m is big, too big for my task. I am trying to find a best and smallest subset of m attributes that still represents the whole dataset quite well, so that I could use only these attributes for teaching a neural network.

I want to use genetic algorithm for this. The problem is the fittness function. It should tell how well the generated model (subset of attributes) still reflects the original data. And I don't know how to evaluate certain subset of attributes against the whole set. Of course I could use the neural network(that will later use this selected data anyway) for checking how good the subset is - the smaller the error, the better the subset. BUT, this takes a looot of time in my case and I do not want to use this solution. I am looking for some other way that would preferably operate only on the data set.

What I thought about was: having subset S (found by genetic algorithm), trim data set so that it contains values only for subset S and check how many observations in this data ser are no longer distinguishable (have same values for same attributes) while having different result values. The bigger the number is, the worse subset it is. But this seems to me like a bit too computationally exhausting.

Are there any other ways to evaluate how well a subset of attributes still represents the whole data set?

like image 599
agnieszka Avatar asked Nov 03 '11 09:11

agnieszka


People also ask

How genetic algorithm is used for feature selection?

Genetic algorithms use an approach to determine an optimal set based on evolution. For feature selection, the first step is to generate a population based on subsets of the possible features. From this population, the subsets are evaluated using a predictive model for the target task.

What is the role of fitness function in genetic algorithm?

A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims. Fitness functions are used in genetic programming and genetic algorithms to guide simulations towards optimal design solutions.

What is the best fitness in genetic algorithm?

The best fitness curve will always be "above" the average fitness curve. If the fitness vs no. of generations curve decreases, then this generally means that the Genetic Algorithm is probably not exploring the solution space adequately and this is typically due to inappropriate mutation and cross-over operations.

What is fitness scaling in genetic algorithm?

Fitness scaling converts the raw fitness scores that are returned by the fitness function to values in a range that is suitable for the selection function. The selection function uses the scaled fitness values to select the parents of the next generation.


1 Answers

This cost function should do what you want: sum the factor loadings that correspond to the features comprising each subset.

The higher that sum, the greater the share of variability in the response variable that is explained with just those features. If i understand the OP, this cost function is a faithful translation of "represents the whole set quite well" from the OP.

Reducing to code is straightforward:

  1. Calculate the covariance matrix of your dataset (first remove the column that holds the response variable, i.e., probably the last one). If your dataset is m x n (columns x rows), then this covariance matrix will be n x n, with "1"s down the main diagonal.

  2. Next, perform an eigenvalue decomposition on this covariance matrix; this will give you the proportion of the total variability in the response variable, contributed by that eigenvalue (each eigenvalue corresponds to a feature, or column). [Note, singular-value decomposition (SVD) is often used for this step, but it's unnecessary--an eigenvalue decomposition is much simpler, and always does the job as long as your matrix is square, which covariance matrices always are].

  3. Your genetic algorithm will, at each iteration, return a set of candidate solutions (features subsets, in your case). The next task in GA, or any combinatorial optimization, is to rank those candiate solutions by their cost function score. In your case, the cost function is a simple summation of the eigenvalue proportion for each feature in that subset. (I guess you would want to scale/normalize that calculation so that the higher numbers are the least fit though.)

A sample calculation (using python + NumPy):

>>> # there are many ways to do an eigenvalue decomp, this is just one way
>>> import numpy as NP
>>> import numpy.linalg as LA

>>> # calculate covariance matrix of the data set (leaving out response variable column)
>>> C = NP.corrcoef(d3, rowvar=0)
>>> C.shape
     (4, 4)
>>> C
     array([[ 1.  , -0.11,  0.87,  0.82],
            [-0.11,  1.  , -0.42, -0.36],
            [ 0.87, -0.42,  1.  ,  0.96],
            [ 0.82, -0.36,  0.96,  1.  ]])

>>> # now calculate eigenvalues & eivenvectors of the covariance matrix:
>>> eva, evc = LA.eig(C)
>>> # now just get value proprtions of each eigenvalue:
>>> # first, sort the eigenvalues, highest to lowest:
>>> eva1 = NP.sort(eva)[::-1]
>>> # get value proportion of each eigenvalue:
>>> eva2 = NP.cumsum(eva1/NP.sum(eva1))   # "cumsum" is just cumulative sum
>>> title1 = "ev value proportion"
>>> print( "{0}".format("-"*len(title1)) )
-------------------
>>> for row in q :
        print("{0:1d} {1:3f} {2:3f}".format(int(row[0]), row[1], row[2]))

   ev value  proportion    
   1   2.91   0.727
   2   0.92   0.953
   3   0.14   0.995
   4   0.02   1.000

so it's the third column of values just above (one for each feature) that are summed (selectively, depending on which features are present in a given subset you are evaluating with the cost function).

like image 52
doug Avatar answered Nov 05 '22 15:11

doug