package jsat.datatransform.featureselection;

import java.util.*;

import jsat.DataSet;
import jsat.classifiers.*;
import jsat.datatransform.*;
import static jsat.datatransform.featureselection.SFS.addFeature;
import static jsat.datatransform.featureselection.SFS.removeFeature;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;

/**
 * Sequential Backward Selection (SBS) is a greedy method of selecting a subset 
 * of features to use for prediction. It starts from the set of all features and 
 * attempts to remove the least informative feature from the set at each 
 * iteration
 * 
 * @author Edward Raff
 */
public class SBS extends RemoveAttributeTransform
{

    private static final long serialVersionUID = -2516121100148559742L;
    private double maxDecrease;
    private int folds;
    private int minFeatures, maxFeatures;
    private Object evaluator;

    
    /**
     * Copy constructor
     * @param toClone the version to copy
     */
    private SBS(SBS toClone)
    {
        super(toClone);
        this.maxDecrease = toClone.maxDecrease;
        this.folds = toClone.folds;
        this.minFeatures = toClone.minFeatures;
        this.maxFeatures = toClone.maxFeatures;
        this.evaluator = toClone.evaluator;
        
    }
    
    /**
     * Performs SBS 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 folds the number of cross validation folds to use in selection
     * @param maxDecrease the maximum tolerable decrease in accuracy in accuracy
     * when a feature is removed
     */
    public SBS(int minFeatures, int maxFeatures, Classifier evaluater, double maxDecrease)
    {
        this(minFeatures, maxFeatures, evaluater, 3, maxDecrease);
    }

    private SBS(int minFeatures, int maxFeatures, Object evaluater, int folds, double maxDecrease)
    {
        super();
        setMaxDecrease(maxDecrease);
        setMinFeatures(minFeatures);
        setMaxFeatures(maxFeatures);
        setEvaluator(evaluater);
        setFolds(folds);
    }
    
    /**
     * Performs SBS 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 cds 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 maxDecrease the maximum tolerable decrease in accuracy in accuracy
     * when a feature is removed
     */
    public SBS(int minFeatures, int maxFeatures, ClassificationDataSet cds, Classifier evaluater, int folds, double maxDecrease)
    {
        this(minFeatures, maxFeatures, evaluater, folds, maxDecrease);
        search(cds, evaluater, minFeatures, maxFeatures, folds);
    }
    
    /**
     * Performs SBS 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 evaluater the regressor to use in determining accuracy given a
     * feature subset
     * @param maxDecrease the maximum tolerable increase in the error rate when
     * a feature is removed
     */
    public SBS(int minFeatures, int maxFeatures, Regressor evaluater, double maxDecrease)
    {
        this(minFeatures, maxFeatures, evaluater, 3, maxDecrease);
    }
    /**
     * Performs SBS 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 rds the data set to perform feature selection on 
     * @param evaluater the regressor to use in determining accuracy given a
     * feature subset
     * @param folds the number of cross validation folds to use in selection
     * @param maxDecrease the maximum tolerable increase in the error rate when
     * a feature is removed
     */
    public SBS(int minFeatures, int maxFeatures, RegressionDataSet rds, Regressor evaluater, int folds, double maxDecrease)
    {
        this(minFeatures, maxFeatures, evaluater, folds, maxDecrease);
        search(rds, evaluater, minFeatures, maxFeatures, folds);
    }

    @Override
    public void fit(DataSet data)
    {
        search(data, evaluator, minFeatures, maxFeatures, folds);
    }
    
    private void search(DataSet dataSet, Object learner, int minFeatures, int maxFeatures, int folds)
    {
        Random rand = RandomUtil.getRandom();
        int nF = dataSet.getNumFeatures();
        int nCat = dataSet.getNumCategoricalVars();
        
        Set available = new IntSet();
        ListUtils.addRange(available, 0, nF, 1);
        Set catSelected = new IntSet(dataSet.getNumCategoricalVars());
        Set numSelected = new IntSet(dataSet.getNumNumericalVars());
        
        Set catToRemove = new IntSet(dataSet.getNumCategoricalVars());
        Set numToRemove = new IntSet(dataSet.getNumNumericalVars());

        //Start will all selected, and prune them out
        ListUtils.addRange(catSelected, 0, nCat, 1);
        ListUtils.addRange(numSelected, 0, nF-nCat, 1);
        
        double[] bestScore = new double[]{Double.POSITIVE_INFINITY};

        while(catSelected.size() + numSelected.size() > minFeatures)
        {
            
            if(SBSRemoveFeature(available, dataSet, catToRemove, numToRemove, 
                    catSelected, numSelected, learner, folds, rand, 
                    maxFeatures, bestScore, maxDecrease) < 0)
                break;

        }
        
        int pos = 0;
        catIndexMap = new int[catSelected.size()];
        for(int i : catSelected)
            catIndexMap[pos++] = i;
        Arrays.sort(catIndexMap);
        
        pos = 0;
        numIndexMap = new int[numSelected.size()];
        for(int i : numSelected)
            numIndexMap[pos++] = i;
        Arrays.sort(numIndexMap);
    }
    
    @Override
    public SBS clone()
    {
        return new SBS(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(IntList.view(catIndexMap, catIndexMap.length));
    }
    
    /**
     * 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(IntList.view(numIndexMap, numIndexMap.length));
    }

    /**
     * Attempts to remove one feature from the list while maintaining its
     * accuracy
     *
     * @param available the set of available features from [0, n) to consider 
     * for removal
     * @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 maxFeatures the maximum allowable number of features
     * @param PbestScore an array to behave as a pointer to the best score seen 
     * so far
     * @param maxDecrease the maximum allowable decrease in accuracy from the 
     * best accuracy we see
     * @return the feature that was selected to be removed, or -1 if none were 
     * removed
     */
    protected static int SBSRemoveFeature(Set available, DataSet dataSet,
            Set catToRemove, Set numToRemove, 
            Set catSelecteed, Set numSelected, 
            Object evaluater, int folds, Random rand, int maxFeatures, 
            double[] PbestScore, double maxDecrease)
    {
        int curBest = -1;
        int nCat = dataSet.getNumCategoricalVars();
        double curBestScore = Double.POSITIVE_INFINITY;
        for(int feature : available)
        {
            DataSet workOn = dataSet.shallowClone();
            addFeature(feature, nCat, catToRemove, numToRemove);
            
            RemoveAttributeTransform remove = new RemoveAttributeTransform(workOn, catToRemove, numToRemove);
            workOn.applyTransform(remove);
            
            double score = SFS.getScore(workOn, evaluater, folds, rand);
            
            if(score < curBestScore)
            {
                curBestScore = score;
                curBest = feature;
            }
            removeFeature(feature, nCat, catToRemove, numToRemove);
        }
        if (catSelecteed.size() + numSelected.size() > maxFeatures
                 || PbestScore[0] - curBestScore > -maxDecrease)
        {
            PbestScore[0] = curBestScore;
            removeFeature(curBest, nCat, catSelecteed, numSelected);
            addFeature(curBest, nCat, catToRemove, numToRemove);
            available.remove(curBest);
            return curBest;
        }
        else
            return  -1; //No possible improvment & weve got enough
    }

    /**
     * Sets the maximum allowable decrease in accuracy (increase in error) from
     * the previous set of features to the new current set.
     *
     * @param maxDecrease the maximum allowable decrease in the accuracy from
     * removing a feature
     */
    public void setMaxDecrease(double maxDecrease)
    {
        if (maxDecrease < 0)
            throw new IllegalArgumentException("Decarese must be a positive value, not " + maxDecrease);
        this.maxDecrease = maxDecrease;
    }

    /**
     * Returns the maximum allowable decrease in accuracy from one set of
     * features to the next
     *
     * @return the maximum allowable decrease in accuracy from one set of
     * features to the next
     */
    public double getMaxDecrease()
    {
        return maxDecrease;
    }

    /**
     * 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;
    }
}

 

Ads help maintain this website.