package jsat.distributions.multivariate;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.distributions.empirical.KernelDensityEstimator;
import jsat.distributions.empirical.kernelfunc.EpanechnikovKF;
import jsat.distributions.empirical.kernelfunc.KernelFunction;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.*;
import jsat.linear.vectorcollection.*;
import jsat.math.OnLineStatistics;
import jsat.parameters.*;
import jsat.utils.concurrent.ParallelUtils;
/**
* MetricKDE is a generalization of the {@link KernelDensityEstimator} to the multivariate case.
* A {@link KernelFunction} is used to weight the contribution of each data point, and a
* {@link DistanceMetric } is used to effectively alter the shape of the kernel. The MetricKDE uses
* one bandwidth parameter, which can be estimated using a nearest neighbor approach, or tuned by hand.
* The bandwidth of the MetricKDE can not be estimated en the same way as the univariate case.
*
* @author Edward Raff
*/
public class MetricKDE extends MultivariateKDE implements Parameterized
{
private static final long serialVersionUID = -2084039950938740815L;
private KernelFunction kf;
private double bandwidth;
private DistanceMetric distanceMetric;
private VectorCollection> vc;
private int defaultK;
private double defaultStndDev;
private static final VectorCollection> defaultVC = new DefaultVectorCollection<>();
/**
* When estimating the bandwidth, the distances of the k'th nearest
* neighbors are used to perform the estimate. The default value of
* this k is {@value #DEFAULT_K}
*/
public static final int DEFAULT_K = 3;
/**
* When estimating the bandwidth, the distances of the k'th nearest
* neighbors are used to perform the estimate. The default number of
* standard deviations from the mean to add to the bandwidth estimate
* is {@value #DEFAULT_STND_DEV}
*/
public static final double DEFAULT_STND_DEV = 2.0;
/**
* When estimating the bandwidth, the distances of the k'th nearest
* neighbors are used to perform the estimate. The weight of each neighbor
* is controlled by the kernel function.
*/
public static final KernelFunction DEFAULT_KF = EpanechnikovKF.getInstance();
/**
* Creates a new KDE object that still needs a data set to model the distribution of
*/
public MetricKDE()
{
this(DEFAULT_KF, new EuclideanDistance(), defaultVC);
}
/**
* Creates a new KDE object that still needs a data set to model the distribution of
*
* @param distanceMetric the distance metric to use
*/
public MetricKDE(DistanceMetric distanceMetric)
{
this(DEFAULT_KF, distanceMetric, defaultVC);
}
/**
* Creates a new KDE object that still needs a data set to model the distribution of
* @param distanceMetric the distance metric to use
* @param vc a vector collection to generate vector collection from
*/
public MetricKDE(DistanceMetric distanceMetric, VectorCollection> vc)
{
this(DEFAULT_KF, distanceMetric, vc);
}
public MetricKDE(KernelFunction kf, DistanceMetric distanceMetric)
{
this(kf, distanceMetric, new DefaultVectorCollection>());
}
/**
* Creates a new KDE object that still needs a data set to model the distribution of
* @param kf the kernel function to use
* @param distanceMetric the distance metric to use
* @param vc a factory to generate vector collection from
*/
public MetricKDE(KernelFunction kf, DistanceMetric distanceMetric, VectorCollection> vc)
{
this(kf, distanceMetric, vc, DEFAULT_K, DEFAULT_STND_DEV);
}
/**
* Creates a new KDE object that still needs a data set to model the distribution of
* @param kf the kernel function to use
* @param distanceMetric the distance metric to use
* @param vc a factory to generate vector collection from
* @param defaultK the default neighbor to use when estimating the bandwidth
* @param defaultStndDev the default multiple of standard deviations to add when estimating the bandwidth
*/
public MetricKDE(KernelFunction kf, DistanceMetric distanceMetric, VectorCollection> vc, int defaultK, double defaultStndDev)
{
setKernelFunction(kf);
this.distanceMetric = distanceMetric;
this.vc = vc;
setDefaultK(defaultK);
setDefaultStndDev(defaultStndDev);
}
/**
* Sets the bandwidth used to estimate the density of the underlying distribution. Too small a bandwidth
* results in high variance, while too large causes high bias.
*
* @param bandwidth the bandwidth to use for estimation
* @throws ArithmeticException if the bandwidth given is not a positive number
*/
public void setBandwith(double bandwidth)
{
if(bandwidth <= 0 || Double.isNaN(bandwidth) || Double.isInfinite(bandwidth))
throw new ArithmeticException("Invalid bandwith given, bandwith must be a positive number, not " + bandwidth);
this.bandwidth = bandwidth;
}
/**
* Returns the current bandwidth used
* @return the current bandwidth
*/
public double getBandwith()
{
return bandwidth;
}
/**
* When estimating the bandwidth, the mean of the k'th nearest neighbors to each data point
* is used. This value controls the default value of k used when it is not specified.
*
* @param defaultK
*/
public void setDefaultK(int defaultK)
{
if(defaultK <= 0)
throw new ArithmeticException("At least one neighbor must be taken into acount, " + defaultK + " is invalid");
this.defaultK = defaultK;
}
/**
* Returns the default value of the k'th nearest neighbor to use when not specified.
* @return the default neighbor used to estimate the bandwidth when not specified
*/
public int getDefaultK()
{
return defaultK;
}
/**
* When estimating the bandwidth, the mean of the neighbor distances is used, and a multiple of
* the standard deviations is added. This controls the multiplier value used when the bandwidth is not specified.
* Zero and negative multipliers are allowed, but a negative multiplier may result in the fitting failing.
*
* @param defaultStndDev the multiple of the standard deviation to add the to bandwidth estimate
*/
public void setDefaultStndDev(double defaultStndDev)
{
if(Double.isInfinite(defaultStndDev) || Double.isNaN(defaultStndDev) || defaultStndDev <= 0)
throw new ArithmeticException("The number of standard deviations to remove must bea postive number, not " + defaultStndDev);
this.defaultStndDev = defaultStndDev;
}
/**
* Returns the multiple of the standard deviations that is added to the bandwidth estimate
* @return the multiple of the standard deviations that is added to the bandwidth estimate
*/
public double getDefaultStndDev()
{
return defaultStndDev;
}
/**
* Returns the distance metric that is used for density estimation
* @return the metric used
*/
public DistanceMetric getDistanceMetric()
{
return distanceMetric;
}
/**
* Sets the distance metric that is used for density estimation
* @param distanceMetric the metric to use
*/
public void setDistanceMetric(DistanceMetric distanceMetric)
{
this.distanceMetric = distanceMetric;
}
@Override
public MetricKDE clone()
{
MetricKDE clone = new MetricKDE(kf, distanceMetric.clone(), vc.clone(), defaultK, defaultStndDev);
clone.bandwidth = this.bandwidth;
if(this.vc != null)
clone.vc = this.vc.clone();
return clone;
}
@Override
public List extends VecPaired, Double>> getNearby(Vec x)
{
if(vc == null)
throw new UntrainedModelException("Model has not yet been created");
List extends VecPaired, Double>> nearBy = getNearbyRaw(x);
//Normalize from their distances to their weights by kernel function
for(VecPaired, Double> result : nearBy)
result.setPair(kf.k(result.getPair()));
return nearBy;
}
@Override
public List extends VecPaired, Double>> getNearbyRaw(Vec x)
{
if(vc == null)
throw new UntrainedModelException("Model has not yet been created");
List extends VecPaired, Double>> nearBy = vc.search(x, bandwidth*kf.cutOff());
for(VecPaired, Double> result : nearBy)
result.setPair(result.getPair()/bandwidth);
return nearBy;
}
@Override
public double pdf(Vec x)
{
List extends VecPaired, Double>> nearBy = getNearby(x);
if(nearBy.isEmpty())
return 0;
double PDF = 0;
for(VecPaired, Double> result : nearBy)
PDF+= result.getPair();
return PDF / (vc.size() * Math.pow(bandwidth, nearBy.get(0).length()));
}
@Override
public boolean setUsingData(List dataSet, boolean parallel)
{
ExecutorService ex = ParallelUtils.getNewExecutor(parallel);
boolean toRet = setUsingData(dataSet, ex);
ex.shutdownNow();
return toRet;
}
/**
* Sets the KDE to model the density of the given data set with the specified bandwidth
* @param dataSet the data set to model the density of
* @param bandwith the bandwidth
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, double bandwith)
{
return setUsingData(dataSet, bandwith, null);
}
/**
* Sets the KDE to model the density of the given data set with the specified bandwidth
* @param dataSet the data set to model the density of
* @param bandwith the bandwidth
* @param threadpool the source of threads for parallel construction
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, double bandwith, ExecutorService threadpool)
{
setBandwith(bandwith);
List> indexVectorPair = new ArrayList<>(dataSet.size());
for(int i = 0; i < dataSet.size(); i++)
indexVectorPair.add(new VecPaired<>(dataSet.get(i), i));
TrainableDistanceMetric.trainIfNeeded(distanceMetric, dataSet, threadpool);
vc.build(threadpool != null, indexVectorPair, distanceMetric);
return true;
}
/**
* Sets the KDE to model the density of the given data set by estimating the bandwidth by using
* the k nearest neighbors of each data point.
* @param dataSet the data set to model the density of
* @param k the number of neighbors to use to estimate the bandwidth
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, int k)
{
return setUsingData(dataSet, k, defaultStndDev);
}
/**
* Sets the KDE to model the density of the given data set by estimating the bandwidth by using
* the k nearest neighbors of each data point.
* @param dataSet the data set to model the density of
* @param k the number of neighbors to use to estimate the bandwidth
* @param threadpool the source of threads for computation
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, int k, ExecutorService threadpool)
{
return setUsingData(dataSet, k, defaultStndDev, threadpool);
}
/**
* Sets the KDE to model the density of the given data set by estimating the bandwidth
* by using the k nearest neighbors of each data data point.
* The bandwidth estimate is calculate as the mean of the distances of the k'th nearest
* neighbor plus stndDevs standard deviations added to the mean.
*
* @param dataSet the data set to model the density of
* @param k the number of neighbors to use to estimate the bandwidth
* @param stndDevs the multiple of the standard deviation to add to the mean of the distances
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, int k, double stndDevs)
{
return setUsingData(dataSet, k, stndDevs, null);
}
/**
* Sets the KDE to model the density of the given data set by estimating the bandwidth
* by using the k nearest neighbors of each data data point.
* The bandwidth estimate is calculate as the mean of the distances of the k'th nearest
* neighbor plus stndDevs standard deviations added to the mean.
*
* @param dataSet the data set to model the density of
* @param k the number of neighbors to use to estimate the bandwidth
* @param stndDevs the multiple of the standard deviation to add to the mean of the distances
* @param threadpool the source of threads to use for computation
* @return true if the model was fit, false if it could not be fit.
*/
public boolean setUsingData(List dataSet, int k, double stndDevs, ExecutorService threadpool)
{
List> indexVectorPair = new ArrayList<>(dataSet.size());
for(int i = 0; i < dataSet.size(); i++)
indexVectorPair.add(new VecPaired<>(dataSet.get(i), i));
TrainableDistanceMetric.trainIfNeeded(distanceMetric, dataSet, threadpool);
vc.build(indexVectorPair, distanceMetric);
//Take the average of the k'th neighbor distance to use as the bandwith
OnLineStatistics stats;
if(threadpool == null)//k+1 b/c the first nearest neighbor will be itself
stats = VectorCollectionUtils.getKthNeighborStats(vc, dataSet, k + 1);
else
stats = VectorCollectionUtils.getKthNeighborStats(vc, dataSet, k + 1, threadpool);
setBandwith(stats.getMean() + stats.getStandardDeviation() * stndDevs);
return true;
}
public boolean setUsingData(List dataSet, ExecutorService threadpool)
{
return setUsingData(dataSet, defaultK, threadpool);
}
/**
* Sampling not yet supported
* @param count
* @param rand
* @return will not return
* @throws UnsupportedOperationException not yet implemented
*/
@Override
public List sample(int count, Random rand)
{
//TODO implement sampling
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public KernelFunction getKernelFunction()
{
return kf;
}
public void setKernelFunction(KernelFunction kf)
{
this.kf = kf;
}
@Override
public void scaleBandwidth(double scale)
{
bandwidth *= scale;
}
}
Ads help maintain this website.