/*
 * 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 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.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * This class implements the Borderline extension of the {@link SMOTE} algorithm
 * for dealing with class imbalance. SMOTE over-samples from the minority class
 * at random points in the space. Borderline smote attempts to estimate which
 * points are on the border of the class bounder, and over-samples only from the
 * points on the boarder. Boarderline-SMOTE can also choose to
 * {@link #setMajorityInterpolation(boolean) perform interpolation using samples for the majority class},
 * which can sometimes improve performance. The border is impacted by changes to
 * the number of {@link #setSmoteNeighbors(int) neighbors} used. In the rare
 * event that a boarder can't be estimated, this implementation will fall back
 * to standard SMOTE.
* This implementation extends the original SMOTE algorithm to the * multi-class case.
*
* See: Han, H., Wang, W.-Y., & Mao, B.-H. (2005). Borderline-SMOTE: A New * Over-sampling Method in Imbalanced Data Sets Learning. In Proceedings of the * 2005 International Conference on Advances in Intelligent Computing - Volume * Part I (pp. 878–887). Berlin, Heidelberg: Springer-Verlag. * DOI:10.1007/11538059_91 * @author Edward Raff */ public class BorderlineSMOTE extends SMOTE { private boolean majorityInterpolation; /** * Creates a new Borderline-SMOTE model that will over-sample the minority * classes so that there is a balanced number of data points in each class. * It will not use majority interpolation. * * @param baseClassifier the base classifier to use after the SMOTEing is * done. */ public BorderlineSMOTE(Classifier baseClassifier) { this(baseClassifier, false); } /** * Creates a new Borderline-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 majorityInterpolation {@code true} if synthetic examples should * use the majority class as well, or {@code false} to use only the minority * class. */ public BorderlineSMOTE(Classifier baseClassifier, boolean majorityInterpolation) { this(baseClassifier, new EuclideanDistance(), majorityInterpolation); } /** * Creates a new Borderline-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 * @param majorityInterpolation {@code true} if synthetic examples should * use the majority class as well, or {@code false} to use only the minority * class. */ public BorderlineSMOTE(Classifier baseClassifier, DistanceMetric dm, boolean majorityInterpolation) { this(baseClassifier, dm, 1.0, majorityInterpolation); } /** * Creates a new Borderline-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. * @param majorityInterpolation {@code true} if synthetic examples should * use the majority class as well, or {@code false} to use only the minority * class. */ public BorderlineSMOTE(Classifier baseClassifier, DistanceMetric dm, double targetRatio, boolean majorityInterpolation) { this(baseClassifier, dm, 5, targetRatio, majorityInterpolation); } /** * 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. * @param majorityInterpolation {@code true} if synthetic examples should * use the majority class as well, or {@code false} to use only the minority * class. */ public BorderlineSMOTE(Classifier baseClassifier, DistanceMetric dm, int smoteNeighbors, double targetRatio, boolean majorityInterpolation) { super(baseClassifier, dm, smoteNeighbors, targetRatio); setMajorityInterpolation(majorityInterpolation); } /** * Copy constructor * @param toCopy the object to copy */ public BorderlineSMOTE(BorderlineSMOTE toCopy) { super((SMOTE)toCopy); this.majorityInterpolation = toCopy.majorityInterpolation; } /** * Sets whether the generation of synthetic samples can make use of the * majority samples (i.e., from other classes) or not. The use of majority * samples is "Borderline-SMOTE2" in the original paper. If majority samples * are not used, it is equivalent to "Borderline-SMOTE1". * * @param majorityInterpolation {@code true} if majority samples should be * used for interpolation, and {@code false} if only minority samples should * be used. */ public void setMajorityInterpolation(boolean majorityInterpolation) { this.majorityInterpolation = majorityInterpolation; } /** * * @return {@code true} if majority samples should be * used for interpolation, and {@code false} if only minority samples should * be used. */ public boolean isMajorityInterpolation() { return majorityInterpolation; } @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<>(); //Put ALL the vectors intoa single VC paired with their class label VectorCollection VC_all = new DefaultVectorCollection<>(dm, vAll, parallel); //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); //Step 1. For every p ii =( 1,2,..., pnum) in the minority class P, //we calculate its m nearest neighbors from the whole training set T List> allNeighbors = new ArrayList<>(); List> allDistances = new ArrayList<>(); VC_all.search(V_id, smoteNeighbors+1, allNeighbors, allDistances, parallel); /** * A list of the vectors for only the neighbors who were not members * of the same class. Used when majorityInterpolation is true */ final List> otherClassSamples = new ArrayList<>(); if(majorityInterpolation) for(List tmp : allNeighbors) otherClassSamples.add(new ArrayList<>(smoteNeighbors)); //Step 2. final IntList danger_id = new IntList(); for(int i = 0; i < VC_id.size(); i++) { int same_class = 0; List neighors_of_i = allNeighbors.get(i); for(int j = 1; j < smoteNeighbors+1; j++) { if(classID == dataSet.getDataPointCategory(neighors_of_i.get(j))) same_class++; else { if(majorityInterpolation) otherClassSamples.get(i).add(VC_all.get(neighors_of_i.get(j))); } } //are you in the DANZER ZONE!? //ratio of how many "majority" examples vs minority //we treat any other class as the "majority" to generalize to the multi-class case //for binary, will be equivalent to original paper double sOm = 1.0-same_class/(double)smoteNeighbors; if(0.5 <= sOm && sOm < 1.0) danger_id.add(i); //else, you are either easily misclassified or easily classified - and thus skipped } //find all the nearest neighbors for each point so we know who to interpolate with List> idNeighbors = new ArrayList<>(); List> idDistances = new ArrayList<>(); VC_id.search(VC_id, smoteNeighbors+1, idNeighbors, idDistances, 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; if (danger_id.isEmpty())//danger zeon was empty? Fall back to SMOTE style sampleIndex = i % V_id.size(); else sampleIndex = danger_id.getI(i % danger_id.size()); Vec vec_nn; //which of the neighbors should we use? //Shoulwe we interpolate withing class or outside of or class? boolean useOtherClass = rand.nextBoolean() && majorityInterpolation && !danger_id.isEmpty(); if (useOtherClass) { List candidates = otherClassSamples.get(sampleIndex); vec_nn = candidates.get(rand.nextInt(candidates.size())); } else { int nn = rand.nextInt(smoteNeighbors) + 1;//index 0 is ourself vec_nn = VC_id.get(idNeighbors.get(sampleIndex).get(nn)); } double gap = rand.nextDouble(); if (useOtherClass) gap /= 2;//now in the range of [0, 0.5), so that the synthetic point is mostly of the minority class of interest // 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 BorderlineSMOTE clone() { return new BorderlineSMOTE(this); } }

Ads help maintain this website.