package jsat.datatransform.featureselection;
import java.util.*;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.datatransform.*;
import jsat.regression.*;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
/**
* Sequential Forward Selection (SFS) is a greedy method of selecting a subset
* of features to use for prediction. It starts from the set of no features and
* attempts to add the next best feature to the set at each iteration.
*
* @author Edward Raff
*/
public class SFS implements DataTransform
{
private static final long serialVersionUID = 140187978708131002L;
private RemoveAttributeTransform finalTransform;
private Set catSelected;
private Set numSelected;
private double maxIncrease;
private Classifier classifier;
private Regressor regressor;
private int minFeatures, maxFeatures;
private int folds;
private Object evaluator;
/**
* Copy constructor
* @param toClone the SFS to copy
*/
private SFS(SFS toClone)
{
if(toClone.catSelected != null)
{
this.finalTransform = toClone.finalTransform.clone();
this.catSelected = new IntSet(toClone.catSelected);
this.numSelected = new IntSet(toClone.numSelected);
}
this.maxIncrease = toClone.maxIncrease;
this.folds = toClone.folds;
this.minFeatures = toClone.minFeatures;
this.maxFeatures = toClone.maxFeatures;
this.evaluator = toClone.evaluator;
if (toClone.classifier != null)
this.classifier = toClone.classifier.clone();
if (toClone.regressor != null)
this.regressor = toClone.regressor.clone();
}
/**
* Performs SFS feature selection for a classification problem
*
* @param minFeatures the minimum number of features to find
* @param maxFeatures the maximum number of features to find
* @param evaluater the classifier to use in determining accuracy given a
* feature subset
* @param maxIncrease the maximum tolerable increase in error when a feature
* is added
*/
public SFS(int minFeatures, int maxFeatures, Classifier evaluater, double maxIncrease)
{
this(minFeatures, maxFeatures, evaluater.clone(), 3, maxIncrease);
}
/**
* Performs SFS feature selection for a classification problem
*
* @param minFeatures the minimum number of features to find
* @param maxFeatures the maximum number of features to find
* @param dataSet the data set to perform feature selection on
* @param evaluater the classifier to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
* @param maxIncrease the maximum tolerable increase in error when a feature
* is added
*/
public SFS(int minFeatures, int maxFeatures, ClassificationDataSet dataSet, Classifier evaluater, int folds, double maxIncrease)
{
this(minFeatures, maxFeatures, evaluater.clone(), folds, maxIncrease);
search(minFeatures, maxFeatures, dataSet, folds);
}
/**
* Creates SFS feature selection for a regression problem
*
* @param minFeatures the minimum number of features to find
* @param maxFeatures the maximum number of features to find
* @param regressor the regressor to use in determining accuracy given a
* feature subset
* @param maxIncrease the maximum tolerable increase in error when a feature
* is added
*/
public SFS(int minFeatures, int maxFeatures, Regressor regressor, double maxIncrease)
{
this(minFeatures, maxFeatures, regressor.clone(), 3, maxIncrease);
}
/**
* Performs SFS feature selection for a regression problem
*
* @param minFeatures the minimum number of features to find
* @param maxFeatures the maximum number of features to find
* @param dataSet the data set to perform feature selection on
* @param regressor the regressor to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
* @param maxIncrease the maximum tolerable increase in error when a feature
* is added
*/
public SFS(int minFeatures, int maxFeatures, RegressionDataSet dataSet, Regressor regressor, int folds, double maxIncrease)
{
this(minFeatures, maxFeatures, regressor.clone(), folds, maxIncrease);
search(minFeatures, maxFeatures, dataSet, folds);
}
private SFS(int minFeatures, int maxFeatures, Object evaluator, int folds, double maxIncrease)
{
setMinFeatures(minFeatures);
setMaxFeatures(maxFeatures);
setFolds(folds);
setMaxIncrease(maxIncrease);
setEvaluator(evaluator);
}
@Override
public void fit(DataSet data)
{
search(minFeatures, maxFeatures, data, minFeatures);
}
private void search(int minFeatures, int maxFeatures, DataSet dataSet, int folds)
{
Random rand = RandomUtil.getRandom();
int nF = dataSet.getNumFeatures();
int nCat = dataSet.getNumCategoricalVars();
Set available = new IntSet();
ListUtils.addRange(available, 0, nF, 1);
catSelected = new IntSet(dataSet.getNumCategoricalVars());
numSelected = new IntSet(dataSet.getNumNumericalVars());
Set catToRemove = new IntSet(dataSet.getNumCategoricalVars());
Set numToRemove = new IntSet(dataSet.getNumNumericalVars());
ListUtils.addRange(catToRemove, 0, nCat, 1);
ListUtils.addRange(numToRemove, 0, nF-nCat, 1);
double[] bestScore = new double[]{Double.POSITIVE_INFINITY};
Object learner = regressor;
if (dataSet instanceof ClassificationDataSet)
learner = classifier;
while (catSelected.size() + numSelected.size() < maxFeatures)
{
if (SFSSelectFeature(available, dataSet,
catToRemove, numToRemove, catSelected, numSelected,
learner, folds, rand, bestScore, minFeatures) < 0)
break;
}
this.finalTransform = new RemoveAttributeTransform(dataSet, catToRemove, numToRemove);
}
/**
*
* @param curBest the value of curBest
* @param nCat the value of nCat
* @param catF the value of catF
* @param numF the value of numF
*/
static protected void addFeature(int curBest, int nCat, Set catF, Set numF)
{
if(curBest >= nCat)
numF.add(curBest-nCat);
else
catF.add(curBest);
}
/**
*
* @param feature the value of feature
* @param nCat the value of nCat
* @param catF the value of catF
* @param numF the value of numF
*/
static protected void removeFeature(int feature, int nCat, Set catF, Set numF)
{
if(feature >= nCat)
numF.remove(feature-nCat);
else
catF.remove(feature);
}
@Override
public DataPoint transform(DataPoint dp)
{
return finalTransform.transform(dp);
}
@Override
public SFS clone()
{
return new SFS(this);
}
/**
* Returns a copy of the set of categorical features selected by the search
* algorithm
*
* @return the set of categorical features to use
*/
public Set getSelectedCategorical()
{
return new IntSet(catSelected);
}
/**
* Returns a copy of the set of numerical features selected by the search
* algorithm.
*
* @return the set of numeric features to use
*/
public Set getSelectedNumerical()
{
return new IntSet(numSelected);
}
/**
* Attempts to add one feature to the list of features while increasing or
* maintaining the current accuracy
*
* @param available the set of available features from [0, n) to consider
* for adding
* @param dataSet the original data set to perform feature selection from
* @param catToRemove the current set of categorical features to remove
* @param numToRemove the current set of numerical features to remove
* @param catSelecteed the current set of categorical features we are keeping
* @param numSelected the current set of numerical features we are keeping
* @param evaluater the classifier or regressor to perform evaluations with
* @param folds the number of cross validation folds to determine performance
* @param rand the source of randomness
* @param PbestScore an array to behave as a pointer to the best score seen
* so far
* @param minFeatures the minimum number of features needed
* @return the feature that was selected to add, or -1 if none were added.
*/
static protected int SFSSelectFeature(Set available,
DataSet dataSet, Set catToRemove, Set numToRemove,
Set catSelecteed, Set numSelected,
Object evaluater, int folds, Random rand, double[] PbestScore,
int minFeatures)
{
int nCat = dataSet.getNumCategoricalVars();
int curBest = -1;
double curBestScore = Double.POSITIVE_INFINITY;
for(int feature : available)
{
removeFeature(feature, nCat, catToRemove, numToRemove);
DataSet workOn = dataSet.shallowClone();
RemoveAttributeTransform remove = new RemoveAttributeTransform(workOn, catToRemove, numToRemove);
workOn.applyTransform(remove);
double score = getScore(workOn, evaluater, folds, rand);
if(score < curBestScore)
{
curBestScore = score;
curBest = feature;
}
addFeature(feature, nCat, catToRemove, numToRemove);
}
if(curBestScore <= 1e-14 && PbestScore[0] <= 1e-14
&& catSelecteed.size() + numSelected.size() >= minFeatures )
return -1;
if (curBestScore < PbestScore[0]
|| catSelecteed.size() + numSelected.size() < minFeatures
|| Math.abs(PbestScore[0]-curBestScore) < 1e-3)
{
PbestScore[0] = curBestScore;
addFeature(curBest, nCat, catSelecteed, numSelected);
removeFeature(curBest, nCat, catToRemove, numToRemove);
available.remove(curBest);
return curBest;
}
else
return -1; //No possible improvment & weve got enough
}
/**
* The score function for a data set and a learner by cross validation of a
* classifier
*
* @param workOn the transformed data set to test from with cross validation
* @param evaluater the learning algorithm to use
* @param folds the number of cross validation folds to perform
* @param rand the source of randomness
* @return the score value in terms of cross validated error
*/
protected static double getScore(DataSet workOn, Object evaluater, int folds, Random rand)
{
if(workOn instanceof ClassificationDataSet)
{
ClassificationModelEvaluation cme =
new ClassificationModelEvaluation((Classifier)evaluater,
(ClassificationDataSet)workOn);
cme.evaluateCrossValidation(folds, rand);
return cme.getErrorRate();
}
else if(workOn instanceof RegressionDataSet)
{
RegressionModelEvaluation rme =
new RegressionModelEvaluation((Regressor)evaluater,
(RegressionDataSet)workOn);
rme.evaluateCrossValidation(folds, rand);
return rme.getMeanError();
}
return Double.POSITIVE_INFINITY;
}
/**
* Sets the maximum allowable the maximum tolerable increase in error when a
* feature is added
*
* @param maxIncrease the maximum allowable the maximum tolerable increase
* in error when a feature is added
*/
public void setMaxIncrease(double maxIncrease)
{
if (maxIncrease < 0)
throw new IllegalArgumentException("Decarese must be a positive value, not " + maxIncrease);
this.maxIncrease = maxIncrease;
}
/**
*
* @return the maximum allowable the maximum tolerable increase in error
* when a feature is added
*/
public double getMaxIncrease()
{
return maxIncrease;
}
/**
* Sets the minimum number of features that must be selected
*
* @param minFeatures the minimum number of features to learn
*/
public void setMinFeatures(int minFeatures)
{
this.minFeatures = minFeatures;
}
/**
* Returns the minimum number of features to find
*
* @return the minimum number of features to find
*/
public int getMinFeatures()
{
return minFeatures;
}
/**
* Sets the maximum number of features that must be selected
*
* @param maxFeatures the maximum number of features to find
*/
public void setMaxFeatures(int maxFeatures)
{
this.maxFeatures = maxFeatures;
}
/**
* Returns the maximum number of features to find
*
* @return the maximum number of features to find
*/
public int getMaxFeatures()
{
return maxFeatures;
}
/**
* Sets the number of folds to use for cross validation when estimating the error rate
* @param folds the number of folds to use for cross validation when estimating the error rate
*/
public void setFolds(int folds)
{
if(folds <= 0 )
throw new IllegalArgumentException("Number of CV folds must be positive, not " + folds);
this.folds = folds;
}
/**
*
* @return the number of folds to use for cross validation when estimating the error rate
*/
public int getFolds()
{
return folds;
}
private void setEvaluator(Object evaluator)
{
this.evaluator = evaluator;
if(evaluator instanceof Classifier)
this.classifier = (Classifier) evaluator;
if(evaluator instanceof Regressor)
this.regressor = (Regressor) evaluator;
}
}
Ads help maintain this website.