/*
* Copyright (C) 2017 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.classifiers.imbalance;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
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.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.linear.vectorcollection.VectorCollectionUtils;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.FakeExecutor;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* This class implements the Synthetic Minority Over-sampling TEchnique (SMOTE)
* for dealing with class imbalance. It does this by over-sampling the minority
* classes to bring their total count up to parity (or some target ratio) with
* the majority class. This is done by interpolating between minority points and
* their neighbors to create new synthetic points that are not present in the
* current dataset. For this reason SMOTE only works with numeric feature
* vectors.
*
* See: Chawla, N., Bowyer, K., Hall, L., & Kegelmeyer, P. (2002). SMOTE:
* synthetic minority over-sampling technique. Artificial Intelligence Research,
* 16, 321–357. Retrieved from here
* @author Edward Raff
*/
public class SMOTE implements Classifier, Parameterized
{
@ParameterHolder
protected Classifier baseClassifier;
protected DistanceMetric dm;
protected int smoteNeighbors;
protected double targetRatio;
/**
* Creates a new SMOTE model that will over-sample the minority classes so
* that there is a balanced number of data points in each class.
* This implementation extends the original SMOTE algorithm to the
* multi-class case.
*
*
* @param baseClassifier the base classifier to use after the SMOTEing is
* done.
*/
public SMOTE(Classifier baseClassifier)
{
this(baseClassifier, new EuclideanDistance());
}
/**
* Creates a new SMOTE model that will over-sample the minority classes so
* that there is a balanced number of data points in each class.
*
* @param baseClassifier the base classifier to use after the SMOTEing is
* done.
* @param dm the distance metric to use for determining nearest neighbors
*/
public SMOTE(Classifier baseClassifier, DistanceMetric dm)
{
this(baseClassifier, dm, 1.0);
}
/**
* Creates a new SMOTE model.
*
* @param baseClassifier the base classifier to use after the SMOTEing is
* done.
* @param dm the distance metric to use for determining nearest neighbors
* @param targetRatio the desired ratio of samples for each class with respect to the majority class.
*/
public SMOTE(Classifier baseClassifier, DistanceMetric dm, double targetRatio)
{
this(baseClassifier, dm, 5, targetRatio);
}
/**
* Creates a new SMOTE object
* @param baseClassifier the base classifier to use after the SMOTEing is done.
* @param dm the distance metric to use for determining nearest neighbors
* @param smoteNeighbors the number of neighbors to look at when interpolating points
* @param targetRatio the desired ratio of samples for each class with respect to the majority class.
*/
public SMOTE(Classifier baseClassifier, DistanceMetric dm, int smoteNeighbors, double targetRatio)
{
setBaseClassifier(baseClassifier);
setDistanceMetric(dm);
setSmoteNeighbors(smoteNeighbors);
setTargetRatio(targetRatio);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public SMOTE(SMOTE toCopy)
{
this.baseClassifier = toCopy.baseClassifier.clone();
this.dm = toCopy.dm.clone();
this.smoteNeighbors = toCopy.smoteNeighbors;
this.targetRatio = toCopy.targetRatio;
}
/**
* Sets the metric used to determine the nearest neighbors of each point.
* @param dm the distance metric to use.
*/
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
/**
*
* @return the distance metric to use
*/
public DistanceMetric getDistanceMetric()
{
return dm;
}
/**
* Sets the number of neighbors that will be used to be candidates for
* interpolation. The default value recommended in the original paper is 5.
*
* @param smoteNeighbors the number of candidate neighbors to select from
* when creating synthetic data points.
*/
public void setSmoteNeighbors(int smoteNeighbors)
{
if(smoteNeighbors < 1)
throw new IllegalArgumentException("number of neighbors considered must be a positive value");
this.smoteNeighbors = smoteNeighbors;
}
/**
*
* @return the number of candidate neighbors to select from
* when creating synthetic data points.
*/
public int getSmoteNeighbors()
{
return smoteNeighbors;
}
/**
* Sets the desired ratio of samples for each class compared to the majority
* class. A ratio of 1.0 will oversample the minority classes until they
* have just as many data points as the majority class. If any minority
* class already exists at a ratio equal to or above this ratio, no over
* samples will be created for that class. If the target ratio is greater
* than one, all classes including the majority class will be
* over-sampled to the desired ratio.
*
* @param targetRatio the target ratio between each class and the majority
* class
*/
public void setTargetRatio(double targetRatio)
{
this.targetRatio = targetRatio;
}
/**
*
* @return the target ratio between each class and the majority
* class
*/
public double getTargetRatio()
{
return targetRatio;
}
/**
* Sets the classifier to use after the dataset has been modified
* @param baseClassifier the classifier to use for training and prediction
*/
public void setBaseClassifier(Classifier baseClassifier)
{
this.baseClassifier = baseClassifier;
}
/**
*
* @return the classifier used by the model
*/
public Classifier getBaseClassifier()
{
return baseClassifier;
}
@Override
public CategoricalResults classify(DataPoint data)
{
return baseClassifier.classify(data);
}
@Override
public void train(final ClassificationDataSet dataSet, boolean parallel)
{
if(dataSet.getNumCategoricalVars() != 0)
throw new FailedToFitException("SMOTE only works with numeric-only feature values");
List vAll = dataSet.getDataVectors();
IntList[] classIndex = new IntList[dataSet.getClassSize()];
for(int i = 0; i < classIndex.length; i++)
classIndex[i] = new IntList();
for(int i = 0; i < dataSet.getSampleSize(); i++)
classIndex[dataSet.getDataPointCategory(i)].add(i);
double[] priors = dataSet.getPriors();
Vec ratios = DenseVector.toDenseVec(priors).clone();//yes, make a copy - I want the priors around too!
/**
* How many samples does it take to reach parity with the majority class
*/
final int majorityNum = (int) (dataSet.getSampleSize()*ratios.max());
ratios.mutableDivide(ratios.max());
final List> synthetics = new ArrayList<>();
//Go through and perform oversampling of each class
for(final int classID : ListUtils.range(0, dataSet.getClassSize()))
{
final int samplesNeeded = (int) (majorityNum * targetRatio - classIndex[classID].size());
if(samplesNeeded <= 0)
continue;
//collect the vectors we need to interpolate with
final List V_id = new ArrayList<>();
for(int i : classIndex[classID])
V_id.add(vAll.get(i));
VectorCollection VC_id = new DefaultVectorCollection<>(dm, V_id, parallel);
//find all the nearest neighbors for each point so we know who to interpolate with
List> neighbors = new ArrayList<>();
List> distances = new ArrayList<>();
VC_id.search(VC_id, smoteNeighbors+1, neighbors, distances, parallel);
ParallelUtils.run(parallel, samplesNeeded, (start, end)->
{
Random rand = RandomUtil.getRandom();
List local_new = new ArrayList<>();
for (int i = start; i < end; i++)
{
int sampleIndex = i % V_id.size();
//which of the neighbors should we use?
int nn = rand.nextInt(smoteNeighbors) + 1;//index 0 is ourselve
Vec vec_nn = VC_id.get(neighbors.get(sampleIndex).get(nn));
double gap = rand.nextDouble();
// x ~ U(0, 1)
//new = sample + x * diff
//where diff = (sample - other)
//equivalent to
//new = sample * (x+1) + other * x
Vec newVal = V_id.get(sampleIndex).clone();
newVal.mutableMultiply(gap + 1);
newVal.mutableAdd(gap, vec_nn);
local_new.add(new DataPoint(newVal));
}
synchronized (synthetics)
{
for (DataPoint v : local_new)
synthetics.add(new DataPointPair<>(v, classID));
}
});
}
ClassificationDataSet newDataSet = new ClassificationDataSet(ListUtils.mergedView(synthetics, dataSet.getAsDPPList()), dataSet.getPredicting());
baseClassifier.train(newDataSet, parallel);
}
@Override
public void train(ClassificationDataSet dataSet)
{
train(dataSet, false);
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public SMOTE clone()
{
return new SMOTE(this);
}
}
Ads help maintain this website.