package jsat.datatransform.featureselection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.ClassificationDataSet;
import jsat.datatransform.RemoveAttributeTransform;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.utils.FakeExecutor;
import jsat.utils.IndexTable;
import jsat.utils.IntSet;
import jsat.utils.SystemInfo;
import jsat.utils.random.RandomUtil;
/**
* Provides an implementation of the ReliefF algorithm for feature importance computing.
* Because JSAT does not support neighbor searching for categorical values, it does not
* provides weights for categorical variables.
* Weight values are in the range [-1, 1]. The value is a measure of corelation, so the
* absolute value of the individual weights would form its relative importance to the
* others.
* The ReliefF algorithm is meant for classification problems, and is computed in a
* nearest neighbor fashion.
* See:
Kononenko, I., Simec, E.,&Robnik-Sikonja, M. (1997).
*
* Overcoming the myopia of inductive learning algorithms with RELIEFF.
* Applied Intelligence, 7, 39–55.
*
* @author Edward Raff
*/
public class ReliefF extends RemoveAttributeTransform
{
private static final long serialVersionUID = -3336500245613075520L;
private double[] w;
private int featureCount;
private int iterations;
private int neighbors;
private DistanceMetric dm;
private VectorCollection vc = new DefaultVectorCollection<>();
/**
* Creates a new ReliefF object to measure the importance of the variables
* with respect to a classification task. Only numeric features will be
* removed. Categorical features will be ignored and left in tact by the
* transformation
*
* @param featureCount the number of features to keep
*/
public ReliefF(int featureCount)
{
this(featureCount, 100, 15, new EuclideanDistance(), new DefaultVectorCollection());
}
/**
* Creates a new ReliefF object to measure the importance of the variables with
* respect to a classification task. Only numeric features will be removed.
* Categorical features will be ignored and left in tact by the transformation
*
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
*/
public ReliefF(int featureCount, final int m, final int n, final DistanceMetric dm)
{
this(featureCount, m, n, dm, new DefaultVectorCollection());
}
/**
* Creates a new ReliefF object to measure the importance of the variables with
* respect to a classification task. Only numeric features will be removed.
* Categorical features will be ignored and left in tact by the transformation
*
* @param cds the data set to measure numeric variable importance from
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
*/
public ReliefF(final ClassificationDataSet cds, int featureCount, final int m, final int n, final DistanceMetric dm)
{
this(cds, featureCount, m, n, dm, new DefaultVectorCollection());
}
/**
* Creates a new ReliefF object to measure the importance of the variables with
* respect to a classification task. Only numeric features will be removed.
* Categorical features will be ignored and left in tact by the transformation
*
* @param cds the data set to measure numeric variable importance from
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
* @param threadPool the source of threads to use for the computation
*/
public ReliefF(final ClassificationDataSet cds, int featureCount, final int m, final int n, final DistanceMetric dm, ExecutorService threadPool)
{
this(cds, featureCount, m, n, dm, new DefaultVectorCollection(), threadPool);
}
/**
* Creates a new ReliefF object to measure the importance of the variables with
* respect to a classification task. Only numeric features will be removed.
* Categorical features will be ignored and left in tact by the transformation
*
* @param cds the data set to measure numeric variable importance from
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
* @param vc the vector collection to create accelerating structures for nearest neighbor
*/
public ReliefF(final ClassificationDataSet cds, int featureCount, final int m, final int n, final DistanceMetric dm, VectorCollection vc)
{
this(cds, featureCount, m, n, dm, vc, null);
}
/**
* copy constructor
* @param toCopy the object to copy
*/
protected ReliefF(ReliefF toCopy)
{
super(toCopy);
if(toCopy.w != null)
this.w = Arrays.copyOf(toCopy.w, toCopy.w.length);
this.dm = toCopy.dm.clone();
this.featureCount = toCopy.featureCount;
this.iterations = toCopy.iterations;
this.neighbors = toCopy.neighbors;
this.vc = toCopy.vc.clone();
}
/**
* Creates a new ReliefF object to measure the importance of the variables
* with respect to a classification task. Only numeric features will be
* removed. Categorical features will be ignored and left in tact by the
* transformation
*
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
* @param vc the factor to create accelerating structures for nearest neighbor
*/
public ReliefF(int featureCount, final int m, final int n, final DistanceMetric dm, VectorCollection vc)
{
super();
setFeatureCount(featureCount);
setIterations(m);
setNeighbors(n);
setDistanceMetric(dm);
this.vc = vc;
}
/**
* Creates a new ReliefF object to measure the importance of the variables with
* respect to a classification task. Only numeric features will be removed.
* Categorical features will be ignored and left in tact by the transformation
*
* @param cds the data set to measure numeric variable importance from
* @param featureCount the number of features to keep
* @param m the number of learning iterations to perform
* @param n the number of neighbors to measure importance from
* @param dm the distance metric to use
* @param vcf the factor to create accelerating structures for nearest neighbor
* @param threadPool the source of threads to use for the computation
*/
public ReliefF(final ClassificationDataSet cds, int featureCount, final int m, final int n, final DistanceMetric dm, VectorCollection vcf, ExecutorService threadPool)
{
this(featureCount, m, n, dm, vcf);
fit(cds, threadPool);
}
@Override
public void fit(DataSet data)
{
fit(data, null);
}
public void fit(DataSet data, ExecutorService threadPool)
{
if(!(data instanceof ClassificationDataSet))
throw new FailedToFitException("RelifF only works with classification datasets, not " + data.getClass().getSimpleName());
final ClassificationDataSet cds = (ClassificationDataSet) data;
this.w = new double[cds.getNumNumericalVars()];
final double[] minVals = new double[w.length];
Arrays.fill(minVals, Double.POSITIVE_INFINITY);
final double[] normalizer = new double[w.length];
Arrays.fill(normalizer, Double.NEGATIVE_INFINITY);
final double[] priors = cds.getPriors();
final List allVecs = cds.getDataVectors();
for(Vec v : allVecs)
for(int i = 0; i < v.length(); i++)
{
minVals[i] = Math.min(minVals[i], v.get(i));
normalizer[i] = Math.max(normalizer[i], v.get(i));
}
for(int i = 0; i < normalizer.length; i++)
normalizer[i] -= minVals[i];
final List> classVC = new ArrayList<>(priors.length);
TrainableDistanceMetric.trainIfNeeded(dm, cds, threadPool);
int curStart = 0;
for (int i = 0; i < priors.length; i++)
{
int classCount = cds.classSampleCount(i);
classVC.add(vc.clone());
classVC.get(i).build(threadPool != null, allVecs, dm);
curStart += classCount;
}
final int m = iterations;
final int n = neighbors;
final int toUse = threadPool == null ? 1 : SystemInfo.LogicalCores;
if(threadPool == null)
threadPool = new FakeExecutor();
final int blockSize = m/toUse;
final CountDownLatch latch = new CountDownLatch(toUse);
for(int id = 0; id < toUse; id++)
{
final int mm;
if(id < m%toUse)
mm = blockSize+1;
else
mm = blockSize;
threadPool.submit(new Runnable()
{
@Override
public void run()
{
double[] wLocal = new double[w.length];
Random rand = RandomUtil.getRandom();
for(int iter = 0; iter < mm; iter++)
{
final int k = rand.nextInt(cds.getSampleSize());
final Vec x_k = allVecs.get(k);
final int y_k = cds.getDataPointCategory(k);
for (int y = 0; y < priors.length; y++)//# classes = C
{
int searchFor = y == y_k ? n + 1 : n;//+1 so we dont search for ourselves
List extends VecPaired> nNearestC = classVC.get(y).search(x_k, searchFor);
if (searchFor != n)
nNearestC = nNearestC.subList(1, searchFor);//chop off the first value which is ourselves
for (int i = 0; i < w.length; i++)
for (VecPaired x_jy : nNearestC)// j loop
{
if (y == y_k)
wLocal[i] -= diff(i, x_k, x_jy.getVector(), normalizer)/(m*n);
else
wLocal[i] += priors[y]/(1-priors[y_k])*diff(i, x_k, x_jy.getVector(), normalizer)/(m*n);
}
}
}
synchronized(w)
{
for(int i = 0; i < w.length; i++)
w[i] += wLocal[i];
}
latch.countDown();
}
});
}
try
{
latch.await();
}
catch (InterruptedException ex)
{
Logger.getLogger(ReliefF.class.getName()).log(Level.SEVERE, null, ex);
}
IndexTable it = new IndexTable(w);
Set numericalToRemove = new IntSet(w.length*2);
for(int i = 0; i < w.length-featureCount; i++)
numericalToRemove.add(it.index(i));
setUp(cds, Collections.EMPTY_SET, numericalToRemove);
}
/**
* Returns accesses to the learned weight data. Altering the values will be
* reflected in this original ReliefF object.
* @return access to the raw weight values
*/
public Vec getWeights()
{
return new DenseVector(w);
}
private double diff(int i, Vec xj, Vec xk, double[] normalzer)
{
if(normalzer[i] == 0)
return 0;
return Math.abs(xj.get(i) - xk.get(i))/normalzer[i];
}
@Override
public ReliefF clone()
{
return new ReliefF(this);
}
/**
* 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 sue
*
* @return the number of features to sue
*/
public int getFeatureCount()
{
return featureCount;
}
/**
* Sets the number of iterations of the ReliefF algorithm that will be run
*
* @param iterations the number of iterations to run
*/
public void setIterations(int iterations)
{
if (iterations < 1)
throw new IllegalArgumentException("Number of iterations must be positive, not " + iterations);
this.iterations = iterations;
}
/**
* Returns the number of iterations to use
*
* @return the number of iterations to use
*/
public int getIterations()
{
return iterations;
}
/**
* Sets the number of neighbors to use to infer feature importance from
*
* @param neighbors the number of neighbors to use
*/
public void setNeighbors(int neighbors)
{
if (neighbors < 1)
throw new IllegalArgumentException("Number of neighbors must be positive, not " + neighbors);
this.neighbors = neighbors;
}
/**
* Returns the number of neighbors that will be used at each step of the
* algorithm.
*
* @return the number of neighbors that will be used
*/
public int getNeighbors()
{
return neighbors;
}
/**
* Sets the distance metric to infer the feature importance with
*
* @param dm the distance metric to use
*/
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
/**
* Returns the distance metric to use
*
* @return the distance metric to use
*/
public DistanceMetric getDistanceMetric()
{
return dm;
}
}
Ads help maintain this website.