package jsat.classifiers.neuralnetwork;
import static java.lang.Math.*;
import java.util.*;
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.*;
import jsat.distributions.empirical.kernelfunc.EpanechnikovKF;
import jsat.distributions.empirical.kernelfunc.KernelFunction;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.*;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.vectorcollection.*;
import jsat.math.decayrates.DecayRate;
import jsat.math.decayrates.ExponetialDecay;
import jsat.parameters.*;
import jsat.utils.*;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* An implementation of a Self Organizing Map, also called a Kohonen Map. It is
* linked to many other algorithms, and is an unsupervised learning algorithm
* that can perform classification.
*
* The SOM is useful for visualizing data sets, though this is not yet implemented.
*
* @author Edward Raff
*/
public class SOM implements Classifier, Parameterized
{
//TODO add code for visualizing the SOM
private static final long serialVersionUID = -6444988770441043797L;
public static final int DEFAULT_MAX_ITERS = 500;
public static final KernelFunction DEFAULT_KF = EpanechnikovKF.getInstance();
public static final double DEFAULT_LEARNING_RATE = 0.1;
public static final DecayRate DEFAULT_LEARNING_DECAY = new ExponetialDecay();
public static final DecayRate DEFAULT_NEIGHBOR_DECAY = new ExponetialDecay();
private int somWidth;
private int somHeight;
private int maxIters;
private KernelFunction kf;
private double initialLearningRate;
private DecayRate learningDecay;
private DecayRate neighborDecay;
private DistanceMetric dm;
private Vec[][] weights;
private CategoricalResults[] crWeightPairs;
private VectorCollection> vcCollection;
//Used for parallel varient
/**
* Contains the sum of all inputs that were the BMU for the given index.
* The final list of data point should be a synchronized list so that
* multiple threads can add to the list safely
*/
private List>> weightUpdates;
/**
* Creates a new SOM using the given parameters using the
* {@link EuclideanDistance}
*
* @param somHeight the height of the SOM lattice
* @param somWeight the weight of the SOM lattice
*/
public SOM(int somHeight, int somWeight)
{
this(new EuclideanDistance(), somHeight, somWeight);
}
/**
* Creates a new SOM using the given parameters
* @param dm the distance metric to use when comparing points
* @param somHeight the height of the SOM lattice
* @param somWeight the weight of the SOM lattice
*/
public SOM(DistanceMetric dm, int somHeight, int somWeight)
{
this(dm, somHeight, somWeight, new DefaultVectorCollection>());
}
/**
* Creates a new SOM using the given parameters
* @param dm the distance metric to use when comparing points
* @param somHeight the height of the SOM lattice
* @param somWeight the weight of the SOM lattice
* @param vcFactory the vector collection to use for containing points
*/
public SOM(DistanceMetric dm, int somHeight, int somWeight, VectorCollection> vcFactory)
{
this(DEFAULT_MAX_ITERS, DEFAULT_KF, DEFAULT_LEARNING_RATE, DEFAULT_LEARNING_DECAY, DEFAULT_NEIGHBOR_DECAY, dm, somHeight, somWeight, vcFactory);
}
private SOM(int maxIters, KernelFunction kf, double initialLearningRate, DecayRate learningDecay, DecayRate neighborDecay, DistanceMetric dm, int somHeight, int somWeight, VectorCollection> vcCollection)
{
this.somHeight = somHeight;
this.somWidth = somWeight;
this.maxIters = maxIters;
this.kf = kf;
this.initialLearningRate = initialLearningRate;
this.learningDecay = learningDecay;
this.neighborDecay = neighborDecay;
this.dm = dm;
this.vcCollection =vcCollection;
}
/**
* Sets the maximum number of iterations that will be used to converge
* @param maxIters the max iterations of the algorithm
*/
public void setMaxIterations(int maxIters)
{
if(maxIters < 1)
throw new ArithmeticException("At least one iteration must be performed");
this.maxIters = maxIters;
}
/**
* Returns the maximum number of iterations that will be used to converge
* @return the max iterations of the algorithm
*/
public int getMaxIterations()
{
return maxIters;
}
/**
* Sets the width of the SOM lattice to create
* @param somWidth the width of the lattice
*/
public void setSomWidth(int somWidth)
{
if(somWidth < 1)
throw new ArithmeticException("Lattice width must be positive, not " + somWidth);
this.somWidth = somWidth;
}
/**
* Sets the height of the SOM lattice to create
* @param somHeight the height of the lattice
*/
public void setSomHeight(int somHeight)
{
if(somHeight < 1)
throw new ArithmeticException("ALttice height must be positive, not " + somHeight);
this.somHeight = somHeight;
}
/**
* Returns the height of the SOM lattice to create
* @return the height of the lattice
*/
public int getSomHeight()
{
return somHeight;
}
/**
* Returns the width of the SOM lattice to create
* @return the width of the lattice
*/
public int getSomWidth()
{
return somWidth;
}
/**
* Sets the rate at which input is incorporated at each iteration of the SOM
* algorithm
*
* @param initialLearningRate the rate the SOM learns at
*/
public void setInitialLearningRate(double initialLearningRate)
{
if(Double.isInfinite(initialLearningRate) || Double.isNaN(initialLearningRate) || initialLearningRate <= 0)
throw new ArithmeticException("Learning rate must be a positive constant, not " + initialLearningRate);
this.initialLearningRate = initialLearningRate;
}
/**
* Returns the rate at which input is incorporated at each iteration of the SOM
* @return the rate the SOM learns at
*/
public double getInitialLearningRate()
{
return initialLearningRate;
}
/**
* The rate the SOM learns decays over each iteration, and this defines the
* way in which the rate decays.
* @param learningDecay the decay for the learning rate
*/
public void setLearningDecay(DecayRate learningDecay)
{
if(learningDecay == null)
throw new NullPointerException("Can not set a decay rate to null");
this.learningDecay = learningDecay;
}
/**
* The rate the SOM learns decays over each iteration, and this defines the
* way in which the rate decays.
* @return the decay for the learning rate
*/
public DecayRate getLearningDecay()
{
return learningDecay;
}
/**
* The range of effect each data point has decays with each iteration, and
* this defines the way in which the rate decays.
*
* @param neighborDecay the decay for the neighbor range.
*/
public void setNeighborDecay(DecayRate neighborDecay)
{
if(neighborDecay == null)
throw new NullPointerException("Can not set a decay rate to null");
this.neighborDecay = neighborDecay;
}
/**
* The range of effect each data point has decays with each iteration, and
* this defines the way in which the rate decays.
*
* @return the decay for the neighbor range.
*/
public DecayRate getNeighborDecay()
{
return neighborDecay;
}
/**
*
* @param D the dimension of the data set
* @return the initial neighbor radius
*/
private double intitalizeWeights(int D)
{
//TODO random intialization is theoretical interesting, but technically slower. Faster intializations exist
for(int i = 0; i < somHeight; i++)
for(int j = 0; j < somWidth; j++)
weights[i][j] = DenseVector.random(D);
return max(somWidth, somHeight);
}
private void iterationStep(final ExecutorService execServ, final int i, final DataSet dataSet, final double nbrRange, final double nbrRangeSqrd, final Vec scratch, final double learnRate)
{
Vec input_i = dataSet.getDataPoint(i).getNumericalValues();
PairedReturn closestBMUPR = getBMU(input_i);
int xBest = closestBMUPR.getFirstItem();
int yBest = closestBMUPR.getSecondItem();
//The bounding square of values that need to be updated
int xStart = Math.max((int)(xBest - nbrRange)-1, 0);
int yStart = Math.max((int)(yBest - nbrRange)-1, 0);
int xEnd = Math.min((int)(xBest + nbrRange)+1, somWidth);
int yEnd = Math.min((int)(yBest + nbrRange)+1, somHeight);
for(int x = xStart; x < xEnd; x++)
{
Vec[] weights_x = weights[x];
for(int y = yStart; y < yEnd; y++)
{
int xLength = xBest - x;
int yLength = yBest - y;
int pointDistSqrd = xLength*xLength + yLength*yLength;
if(pointDistSqrd < nbrRangeSqrd)//point is in the circle range,
{
double distWeight = kf.k(sqrt(pointDistSqrd)/nbrRange);
Vec weights_xy = weights_x[y];
if(execServ == null)
updateWeight(input_i, scratch, weights_xy, distWeight*learnRate);
else
weightUpdates.get(x).get(y).add(dataSet.getDataPoint(i));
}
}
}
}
private List> setUpVectorCollection(boolean parallel)
{
List> vecList = new ArrayList>(somWidth*somHeight);
for(int i = 0; i < weights.length; i++)
for(int j = 0; j < weights[i].length; j++)
vecList.add(new VecPaired<>(weights[i][j], vecList.size()));
vcCollection.build(parallel, vecList, dm);
return vecList;
}
private void updateWeight(Vec input_i, Vec scratch, Vec weightVec, double scale)
{
input_i.copyTo(scratch);
scratch.mutableSubtract(weightVec);
weightVec.mutableAdd(scale, scratch);
}
/**
* Finds the Best Matching Unit
* @param numericalValues the vector to find hte BMU of
* @return the BMU of the given vector
*/
private PairedReturn getBMU(Vec numericalValues)
{
double bestDist = Double.MAX_VALUE;
int x = -1, y = -1;
for(int i = 0; i < weights.length; i++)
{
Vec[] weights_i = weights[i];
for(int j = 0; j < weights[i].length; j++)
{
double dist = dm.dist(weights_i[j], numericalValues);
if(dist < bestDist)
{
bestDist =dist;
x = i;
y = j;
}
}
}
return new PairedReturn<>(x, y);
}
private void trainSOM(final DataSet dataSet, boolean parallel) throws InterruptedException
{
ExecutorService execServ = ParallelUtils.getNewExecutor(parallel);
final int D = dataSet.getNumNumericalVars();
weights = new Vec[somHeight][somWidth];
double neighborRadius = intitalizeWeights(D);
Random rand = RandomUtil.getRandom();
Vec scratch = new DenseVector(D);
/**
* this array is used to access the data in a random order to improve convergence
*/
final int[] pointAccessOrder = new int[dataSet.getSampleSize()];
for(int i = 0; i < pointAccessOrder.length; i++)
pointAccessOrder[i] = i;
final ThreadLocal localScratch1;
final ThreadLocal localScratch2;
if(execServ != null)//Create parallel structures
{
weightUpdates = new ArrayList>>(somHeight);
for(int i = 0; i < somHeight; i++)
{
ArrayList> subList = new ArrayList>(somWidth);
weightUpdates.add(subList);
for(int j = 0; j < somWidth; j++)
{
subList.add(Collections.synchronizedList(new ArrayList()));
}
}
localScratch1 = new ThreadLocal()
{
@Override
protected Vec initialValue()
{
return new DenseVector(D);
}
};
localScratch2 = new ThreadLocal()
{
@Override
protected Vec initialValue()
{
return new DenseVector(D);
}
};
}
else
localScratch2 = localScratch1 = null;
for(int iter = 0; iter < maxIters; iter++)
{
final double nbrRange = neighborDecay.rate(iter, maxIters, neighborRadius);
final double nbrRangeSqrd = nbrRange*nbrRange;
final double learnRate = learningDecay.rate(iter, maxIters, initialLearningRate);
//Set up before data loop. Shuffle for better convergence if single threaded, create result queus for paralllel collection
if(execServ == null)
ArrayUtils.shuffle(pointAccessOrder, rand);
else//Prep parallel structures
{
for(int i = 0; i < somHeight; i++)
for(int j = 0; j < somWidth; j++)
weightUpdates.get(i).get(j).clear();
}
//Performe main loop over all data points
if(execServ == null)
for(int ir = 0; ir 0 ? 1 : 0) + pos + size;
final int start = pos;
pos = to;
execServ.submit(new Runnable() {
@Override
public void run()
{
for(int i = start; i < to; i++)
iterationStep(execServ, i, dataSet, nbrRange, nbrRangeSqrd, localScratch1.get(), learnRate);
cdl.countDown();
}
});
}
cdl.await();
}
//Collect results if we did parallel computation
if(execServ != null)//Apply changes
{
final CountDownLatch cdl = new CountDownLatch(somHeight*somWidth);
for(int i = 0; i < somHeight; i++)
for(int j = 0; j < somWidth; j++)
{
final List dataList = weightUpdates.get(i).get(j);
final int x = i, y = j;
execServ.submit(new Runnable() {
@Override
public void run()
{
Vec mean = localScratch1.get();
mean.zeroOut();
double denom = 0.0;
for(DataPoint dp : dataList)
{
denom += dp.getWeight();
mean.mutableAdd(dp.getWeight(), dp.getNumericalValues());
}
if(denom > 0)
mean.mutableDivide(denom);
updateWeight(mean, localScratch2.get(), weights[x][y], learnRate);
cdl.countDown();
}
});
}
cdl.await();
}
}
execServ.shutdownNow();
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(crWeightPairs == null)
throw new UntrainedModelException();
return crWeightPairs[vcCollection.search(data.getNumericalValues(), 1).get(0).getVector().getPair()];
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
try
{
trainSOM(dataSet, parallel);
List> vecList = setUpVectorCollection(parallel);
crWeightPairs = new CategoricalResults[vecList.size()];
for(int i = 0; i < crWeightPairs.length; i++)
crWeightPairs[i] = new CategoricalResults(dataSet.getClassSize());
for(int i = 0; i < dataSet.getSampleSize(); i++)
{
DataPoint dp = dataSet.getDataPoint(i);
//Single nearest neighbor is the BMU
VecPaired vpBMU = vcCollection.search(dp.getNumericalValues(), 1).get(0).getVector();
int index = vpBMU.getPair();
crWeightPairs[index].incProb(dataSet.getDataPointCategory(i), dp.getWeight());
}
for(int i = 0; i < crWeightPairs.length; i++)
crWeightPairs[i].normalize();
}
catch (InterruptedException ex)
{
Logger.getLogger(SOM.class.getName()).log(Level.SEVERE, null, ex);
}
}
@Override
public boolean supportsWeightedData()
{
return true;
}
@Override
public SOM clone()
{
SOM clone = new SOM(maxIters, kf, initialLearningRate, learningDecay, neighborDecay, dm.clone(), somHeight, somHeight, vcCollection.clone());
if(this.weights != null)
{
clone.weights = new Vec[this.weights.length][this.weights[0].length];
for(int i = 0; i < this.weights.length; i++)
for(int j = 0; j < this.weights[i].length; j++)
clone.weights[i][j] = this.weights[i][j].clone();
}
if(this.vcCollection != null)
clone.vcCollection = this.vcCollection.clone();
if(this.crWeightPairs != null)
{
clone.crWeightPairs = new CategoricalResults[this.crWeightPairs.length];
for(int i = 0; i < this.crWeightPairs.length; i++)
clone.crWeightPairs[i] = this.crWeightPairs[i].clone();
}
return clone;
}
}
Ads help maintain this website.