package jsat.clustering;
import java.util.*;
import jsat.DataSet;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.*;
import jsat.linear.vectorcollection.*;
import jsat.parameters.*;
import jsat.utils.*;
/**
* A parallel implementation of Locally Scaled Density Based Clustering.
*
* See paper:
* Biçici, E.,
*&Yuret, D. (2007). Locally scaled density based clustering.
* In B. Beliczynski, A. Dzielinski, M. Iwanowski,&B. Ribeiro (Eds.),
* Adaptive and Natural Computing Algorithms (pp. 739–748).
* Warsaw, Poland: Springer-Verlag.
* @author Edward Raff
*/
public class LSDBC extends ClustererBase implements Parameterized
{
private static final long serialVersionUID = 6626217924334267681L;
/**
* {@value #DEFAULT_NEIGHBORS} is the default number of neighbors used when
* performing clustering
*
* @see #setNeighbors(int)
*/
public static final int DEFAULT_NEIGHBORS = 15;
/**
* {@value #DEFAULT_ALPHA} is the default scale value used when performing clustering.
* @see #setAlpha(double)
*/
public static final double DEFAULT_ALPHA = 4;
private static final int UNCLASSIFIED = -1;
private DistanceMetric dm;
private VectorCollection> vc = new DefaultVectorCollection<>();
/**
* The weight parameter for forming new clusters
*/
private double alpha;
/**
* The number of neighbors to use
*/
private int k;
/**
* Creates a new LSDBC clustering object using the given distance metric
* @param dm the distance metric to use
* @param alpha the scale factor to use when forming clusters
* @param neighbors the number of neighbors to consider when determining clusters
*/
public LSDBC(DistanceMetric dm, double alpha, int neighbors)
{
setDistanceMetric(dm);
setAlpha(alpha);
setNeighbors(neighbors);
}
/**
* Creates a new LSDBC clustering object using the given distance metric
* @param dm the distance metric to use
* @param alpha the scale factor to use when forming clusters
*/
public LSDBC(DistanceMetric dm, double alpha)
{
this(dm, alpha, DEFAULT_NEIGHBORS);
}
/**
* Creates a new LSDBC clustering object using the given distance metric
* @param dm the distance metric to use
*/
public LSDBC(DistanceMetric dm)
{
this(dm, DEFAULT_ALPHA);
}
/**
* Creates a new LSDBC clustering object using the {@link EuclideanDistance}
* and default parameter values.
*/
public LSDBC()
{
this(new EuclideanDistance());
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public LSDBC(LSDBC toCopy)
{
this.alpha = toCopy.alpha;
this.dm = toCopy.dm.clone();
this.k = toCopy.k;
this.vc = toCopy.vc.clone();
}
/**
* Sets the vector collection factory used for acceleration of neighbor searches.
* @param vc the vector collection to use
*/
public void setVectorCollectionFactory(VectorCollection> vc)
{
this.vc = vc;
}
/**
* Sets the distance metric used when performing clustering.
* @param dm the distance metric to use.
*/
public void setDistanceMetric(DistanceMetric dm)
{
if(dm != null)
this.dm = dm;
}
/**
* Returns the distance metric used when performing clustering.
* @return the distance metric used
*/
@SuppressWarnings("unused")
private DistanceMetric getDistanceMetric()
{
return dm;
}
/**
* Sets the number of neighbors that will be considered when clustering
* data points
* @param neighbors the number of neighbors the algorithm will use
*/
public void setNeighbors(int neighbors)
{
if(neighbors <= 0)
throw new ArithmeticException("Can not use a non positive number of neighbors");
this.k = neighbors;
}
/**
* Returns the number of neighbors that will be considered when clustering
* data points
* @return the number of neighbors the algorithm will use
*/
public int getNeighbors()
{
return k;
}
/**
* Sets the scale value that will control how many points are added to a
* cluster. Smaller values will create more, smaller clusters - and more
* points will be labeled as noise. Larger values causes larger and fewer
* clusters.
*
* @param alpha the scale value to use
*/
public void setAlpha(double alpha)
{
if(alpha <= 0 || Double.isNaN(alpha) || Double.isInfinite(alpha))
throw new ArithmeticException("Can not use the non positive scale value " + alpha );
this.alpha = alpha;
}
/**
* Returns the scale value that will control how many points are added to a
* cluster. Smaller values will create more, smaller clusters - and more
* points will be labeled as noise. Larger values causes larger and fewer
* clusters.
*
* @return the scale value to use
*/
public double getAlpha()
{
return alpha;
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
if(designations == null)
designations = new int[dataSet.getSampleSize()];
//Compute all k-NN
List, Double>>> knnVecList;
//Set up
List> vecs = new ArrayList<>(dataSet.getSampleSize());
for (int i = 0; i < dataSet.getSampleSize(); i++)
vecs.add(new VecPaired<>(dataSet.getDataPoint(i).getNumericalValues(), i));
TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel);
vc.build(parallel, vecs, dm);
knnVecList = VectorCollectionUtils.allNearestNeighbors(vc, vecs, k+1, parallel);
//Sort
IndexTable indexTable = new IndexTable(knnVecList, new Comparator()
{
@Override
public int compare(Object o1, Object o2)
{
List, Double>> l1 =
(List, Double>>) o1;
List, Double>> l2 =
(List, Double>>) o2;
return Double.compare(getEps(l1), getEps(l2));
}
});
//Assign clusters, does very little computation. No need to parallelize expandCluster
Arrays.fill(designations, UNCLASSIFIED);
int clusterID = 0;
for(int i = 0; i < indexTable.length(); i++)
{
int p = indexTable.index(i);
if(designations[p] == UNCLASSIFIED && localMax(p, knnVecList))
expandCluster(p, clusterID++, knnVecList, designations);
}
return designations;
}
/**
* Performs the main clustering loop of expandCluster.
* @param neighbors the list of neighbors
* @param i the index of neighbors to consider
* @param designations the array of cluster designations
* @param clusterID the current clusterID to assign
* @param seeds the stack to hold all seeds in
*/
private void addSeed(List extends VecPaired, Double>> neighbors, int i, int[] designations, int clusterID, Stack seeds)
{
int index = neighbors.get(i).getVector().getPair();
if (designations[index] != UNCLASSIFIED)
return;
designations[index] = clusterID;
seeds.add(index);
}
/**
* Convenience method. Gets the eps value for the given set of neighbors
* @param neighbors the set of neighbors, with index 0 being the point itself
* @return the eps of the kth neighbor
*/
private double getEps(List extends VecPaired, Double>> neighbors)
{
return neighbors.get(k).getPair();
}
/**
* Returns true if the given point is a local maxima, meaning it is more dense then the density of all its neighbors
* @param p the index of the data point in question
* @param knnVecList the neighbor list
* @return true if it is a local max, false otherwise.
*/
private boolean localMax(int p, List, Double>>> knnVecList)
{
List extends VecPaired, Double>> neighbors = knnVecList.get(p);
double myEps = getEps(neighbors);
for(int i = 1; i < neighbors.size(); i++)
{
int neighborP = neighbors.get(i).getVector().getPair();
if(getEps(knnVecList.get(neighborP)) < myEps)
return false;
}
return true;
}
/**
* Does the cluster assignment
* @param p the current index of a data point to assign to a cluster
* @param clusterID the current cluster ID to assign
* @param knnVecList the in order list of every index and its nearest neighbors
* @param designations the array to store cluster designations in
*/
private void expandCluster(int p, int clusterID, List, Double>>> knnVecList, int[] designations)
{
designations[p] = clusterID;
double pointEps;
int n;
Stack seeds = new Stack<>();
{
List extends VecPaired, Double>> neighbors = knnVecList.get(p);
for (int i = 1; i < neighbors.size(); i++)
addSeed(neighbors, i, designations, clusterID, seeds);
pointEps = getEps(neighbors);
n = neighbors.get(k).length();
}
final double scale = Math.pow(2, alpha / n);
while (!seeds.isEmpty())
{
int currentP = seeds.pop();
List extends VecPaired, Double>> neighbors = knnVecList.get(currentP);
double currentPEps = getEps(neighbors);
if (currentPEps <= scale * pointEps)
{
for (int i = 1; i < neighbors.size(); i++)
addSeed(neighbors, i, designations, clusterID, seeds);
}
}
}
@Override
public LSDBC clone()
{
return new LSDBC();
}
}
Ads help maintain this website.