package jsat.datatransform.featureselection;
import java.util.*;
import jsat.DataSet;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.datatransform.DataTransform;
import jsat.datatransform.DataTransformBase;
import jsat.datatransform.RemoveAttributeTransform;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
/**
* Bidirectional Search (BDS) is a greedy method of selecting a subset
* of features to use for prediction. It performs both {@link SFS} and
* {@link SBS} search at the same time. At each step, a feature is greedily
* added to one set, and then a feature greedily removed from another set.
* Once a feature is added / removed in one set, it is unavailable for selection
* in the other. This can be used to select up to half of the original features.
*
* @author Edward Raff
*/
public class BDS implements DataTransform
{
private static final long serialVersionUID = 8633823674617843754L;
private RemoveAttributeTransform finalTransform;
private Set catSelected;
private Set numSelected;
private int featureCount;
private int folds;
private Object evaluator;
/**
* Copy constructor
*
* @param toClone
*/
public BDS(BDS toClone)
{
this.featureCount = toClone.featureCount;
this.folds = toClone.folds;
this.evaluator = toClone.evaluator;
if(toClone.finalTransform != null)
{
this.finalTransform = toClone.finalTransform.clone();
this.catSelected = new IntSet(toClone.catSelected);
this.numSelected = new IntSet(toClone.numSelected);
}
}
/**
* Creates a BDS feature selection for a classification problem
*
* @param featureCount the number of features to select
* @param dataSet the data set to perform feature selection on
* @param evaluator the classifier to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
*/
public BDS(int featureCount, Classifier evaluator, int folds)
{
setFeatureCount(featureCount);
setFolds(folds);
setEvaluator(evaluator);
}
/**
* Performs BDS feature selection for a classification problem
*
* @param featureCount the number of features to select
* @param dataSet the data set to perform feature selection on
* @param evaluator the classifier to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
*/
public BDS(int featureCount, ClassificationDataSet dataSet, Classifier evaluator, int folds)
{
search(dataSet, featureCount, folds, evaluator);
}
/**
* Creates a BDS feature selection for a regression problem
*
* @param featureCount the number of features to select
* @param evaluator the regressor to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
*/
public BDS(int featureCount, Regressor evaluator, int folds)
{
setFeatureCount(featureCount);
setFolds(folds);
setEvaluator(evaluator);
}
/**
* Performs BDS feature selection for a regression problem
*
* @param featureCount the number of features to select
* @param dataSet the data set to perform feature selection on
* @param evaluator the regressor to use in determining accuracy given a
* feature subset
* @param folds the number of cross validation folds to use in selection
*/
public BDS(int featureCount, RegressionDataSet dataSet, Regressor evaluator, int folds)
{
this(featureCount, evaluator, folds);
search(dataSet, featureCount, folds, evaluator);
}
@Override
public DataPoint transform(DataPoint dp)
{
return finalTransform.transform(dp);
}
@Override
public BDS clone()
{
return new BDS(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);
}
@Override
public void fit(DataSet data)
{
search(data, featureCount, folds, evaluator);
}
private void search(DataSet dataSet, int maxFeatures, int folds, Object evaluator)
{
Random rand = RandomUtil.getRandom();
int nF = dataSet.getNumFeatures();
int nCat = dataSet.getNumCategoricalVars();
//True selected, also used for SFS
catSelected = new IntSet(dataSet.getNumCategoricalVars());
numSelected = new IntSet(dataSet.getNumNumericalVars());
//Structs for SFS side
Set availableSFS = new IntSet();
ListUtils.addRange(availableSFS, 0, nF, 1);
Set catToRemoveSFS = new IntSet(dataSet.getNumCategoricalVars());
Set numToRemoveSFS = new IntSet(dataSet.getNumNumericalVars());
ListUtils.addRange(catToRemoveSFS, 0, nCat, 1);
ListUtils.addRange(numToRemoveSFS, 0, nF-nCat, 1);
///Structes fro SBS side
Set availableSBS = new IntSet();
ListUtils.addRange(availableSBS, 0, nF, 1);
Set catSelecteedSBS = new IntSet(dataSet.getNumCategoricalVars());
Set numSelectedSBS = new IntSet(dataSet.getNumNumericalVars());
Set catToRemoveSBS = new IntSet(dataSet.getNumCategoricalVars());
Set numToRemoveSBS = new IntSet(dataSet.getNumNumericalVars());
//Start will all selected, and prune them out
ListUtils.addRange(catSelecteedSBS, 0, nCat, 1);
ListUtils.addRange(numSelectedSBS, 0, nF-nCat, 1);
double[] pBestScore0 = new double[]{Double.POSITIVE_INFINITY};
double[] pBestScore1 = new double[]{Double.POSITIVE_INFINITY};
int max = Math.min(maxFeatures, nF/2);
for(int i = 0; i < max; i++)
{
//Find and keep one good one
int mustKeep = SFS.SFSSelectFeature(availableSFS, dataSet,
catToRemoveSFS, numToRemoveSFS, catSelected,
numSelected, evaluator, folds, rand, pBestScore0, max);
availableSBS.remove(mustKeep);
SFS.removeFeature(mustKeep, nCat, catToRemoveSBS, numToRemoveSBS);
//Find and remove one bad one
int mustRemove = SBS.SBSRemoveFeature(availableSBS, dataSet,
catToRemoveSBS, numToRemoveSBS, catSelecteedSBS,
numSelectedSBS, evaluator, folds, rand, max,
pBestScore1, 0.0);
availableSFS.remove(mustRemove);
SFS.addFeature(mustRemove, nCat, catToRemoveSFS, numToRemoveSFS);
}
catSelecteedSBS.clear();
numToRemoveSBS.clear();
ListUtils.addRange(catSelecteedSBS, 0, nCat, 1);
ListUtils.addRange(numSelectedSBS, 0, nF-nCat, 1);
catSelecteedSBS.removeAll(catSelected);
numSelectedSBS.removeAll(numSelected);
finalTransform = new RemoveAttributeTransform(dataSet, catSelecteedSBS, numSelectedSBS);
}
/**
* Sets the number of features to select for use from the set of all input
* features
*
* @param featureCount the number of features to use
*/
public void setFeatureCount(int featureCount)
{
if (featureCount < 1)
throw new IllegalArgumentException("Number of features to select must be positive, not " + featureCount);
this.featureCount = featureCount;
}
/**
* Returns the number of features to use
*
* @return the number of features to use
*/
public int getFeatureCount()
{
return featureCount;
}
/**
* 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;
}
}
Ads help maintain this website.