package jsat.clustering;
import java.util.*;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.DataPoint;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.utils.DoubleList;
import jsat.utils.random.RandomUtil;
/**
*
* @author Edward Raff
*/
public class CLARA extends PAM
{
private static final long serialVersionUID = 174392533688953706L;
/**
* The number of samples to take
*/
private int sampleSize;
/**
* The number of times to do sampling
*/
private int sampleCount;
private boolean autoSampleSize;
public CLARA(int sampleSize, int sampleCount, DistanceMetric dm, Random rand, SeedSelection seedSelection)
{
super(dm, rand, seedSelection);
this.sampleSize = sampleSize;
this.sampleCount = sampleCount;
this.autoSampleSize = false;
}
public CLARA(int sampleCount, DistanceMetric dm, Random rand, SeedSelection seedSelection)
{
super(dm, rand, seedSelection);
this.sampleSize = -1;
this.sampleCount = sampleCount;
this.autoSampleSize = true;
}
public CLARA(DistanceMetric dm, Random rand, SeedSelection seedSelection)
{
this(5, dm, rand, seedSelection);
}
public CLARA(DistanceMetric dm, Random rand)
{
this(dm, rand, SeedSelection.KPP);
}
public CLARA(DistanceMetric dm)
{
this(dm, RandomUtil.getRandom());
}
public CLARA()
{
this(new EuclideanDistance());
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public CLARA(CLARA toCopy)
{
super(toCopy);
this.sampleSize = toCopy.sampleSize;
this.sampleCount = toCopy.sampleCount;
this.autoSampleSize = toCopy.autoSampleSize;
}
/**
*
* @return the number of times {@link PAM} will be applied to a sample from the data set.
*/
public int getSampleCount()
{
return sampleCount;
}
/**
* Sets the number of times {@link PAM} will be applied to different samples from the data set.
*
* @param sampleCount the number of times to apply sampeling.
*/
public void setSampleCount(int sampleCount)
{
this.sampleCount = sampleCount;
}
/**
*
* @return the number of samples that will be taken to perform {@link PAM} on.
*/
public int getSampleSize()
{
return sampleSize;
}
/**
* Sets the number of samples CLARA should take from the data set to perform {@link PAM} on.
*
* @param sampleSize the number of samples to take
*/
public void setSampleSize(int sampleSize)
{
if(sampleSize >= 0)
{
autoSampleSize = false;
this.sampleSize = sampleSize;
}
else
autoSampleSize = true;
}
@Override
protected double cluster(DataSet data, boolean doInit, int[] medioids, int[] assignments, List cacheAccel, boolean parallel)
{
int k = medioids.length;
int[] bestMedoids = new int[medioids.length];
int[] bestAssignments = new int[assignments.length];
double bestMedoidsDist = Double.MAX_VALUE;
List X = data.getDataVectors();
if(sampleSize >= data.getSampleSize())//Then we might as well just do one round of PAM
{
return super.cluster(data, true, medioids, assignments, cacheAccel, parallel);
}
else if(doInit)
{
TrainableDistanceMetric.trainIfNeeded(dm, data);
cacheAccel = dm.getAccelerationCache(X);
}
int sampSize = autoSampleSize ? 40+2*k : sampleSize;
int[] sampleAssignments = new int[sampSize];
List sample = new ArrayList<>(sampSize);
/**
* We need the mapping to be able to go from the sample indicies back to their position in the full data set
* Key is the sample index [1, 2, 3, ..., sampSize]
* Value is the coresponding index in the full data set
*/
Map samplePoints = new LinkedHashMap<>();
DoubleList subCache = new DoubleList(sampSize);
for(int i = 0; i < sampleCount; i++)
{
//Take a sample and use PAM on it to get medoids
samplePoints.clear();
sample.clear();
subCache.clear();
while (samplePoints.size() < sampSize)
{
int indx = rand.nextInt(data.getSampleSize());
if (!samplePoints.containsValue(indx))
samplePoints.put(samplePoints.size(), indx);
}
for (Integer j : samplePoints.values())
{
sample.add(data.getDataPoint(j));
subCache.add(cacheAccel.get(j));
}
DataSet sampleSet = new SimpleDataSet(sample);
//Sampling done, now apply PAM
SeedSelectionMethods.selectIntialPoints(sampleSet, medioids, dm, subCache, rand, getSeedSelection());
super.cluster(sampleSet, false, medioids, sampleAssignments, subCache, parallel);
//Map the sample medoids back to the full data set
for(int j = 0; j < medioids.length; j++)
medioids[j] = samplePoints.get(medioids[j]);
//Now apply the sample medoids to the full data set
double sqrdDist = 0.0;
for(int j = 0; j < data.getSampleSize(); j++)
{
double smallestDist = Double.MAX_VALUE;
int assignment = -1;
for(int z = 0; z < k; z++)
{
double tmp = dm.dist(medioids[z], j, X, cacheAccel);
if(tmp < smallestDist)
{
assignment = z;
smallestDist = tmp;
}
}
assignments[j] = assignment;
sqrdDist += smallestDist*smallestDist;
}
if(sqrdDist < bestMedoidsDist)
{
bestMedoidsDist = sqrdDist;
System.arraycopy(medioids, 0, bestMedoids, 0, k);
System.arraycopy(assignments, 0, bestAssignments, 0, assignments.length);
}
}
System.arraycopy(bestMedoids, 0, medioids, 0, k);
System.arraycopy(bestAssignments, 0, assignments, 0, assignments.length);
return bestMedoidsDist;
}
@Override
public CLARA clone()
{
return new CLARA(this);
}
}
Ads help maintain this website.