package jsat.clustering;
import java.util.*;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.linear.vectorcollection.VectorCollectionUtils;
import jsat.math.OnLineStatistics;
import jsat.utils.concurrent.ParallelUtils;
/**
* A density-based algorithm for discovering clusters in large spatial databases
* with noise (1996) by Martin Ester , Hans-peter Kriegel , Jörg S , Xiaowei Xu
*
* @author Edward Raff
*/
public class DBSCAN extends ClustererBase
{
private static final long serialVersionUID = 1627963360642560455L;
/**
* Used by {@link #cluster(DataSet, double, int, VectorCollection,int[]) }
* to mark that a data point as not yet been visited.
* Clusters that have been visited have a value >= 0, that indicates their cluster. Or have the value {@link #NOISE}
*/
private static final int UNCLASSIFIED = -1;
/**
* Used by {@link #expandCluster(int[], DataSet, int, int, double, int, VectorCollection) }
* to mark that a data point has been visited, but was considered noise.
*/
private static final int NOISE = -2;
/**
* Factory used to create a vector space of the inputs.
* The paired Integer is the vector's index in the original dataset
*/
private VectorCollection > vc;
private DistanceMetric dm;
private double stndDevs = 2.0;
public DBSCAN(DistanceMetric dm, VectorCollection> vc)
{
this.dm = dm;
this.vc = vc;
}
public DBSCAN()
{
this(new EuclideanDistance());
}
public DBSCAN(DistanceMetric dm)
{
this(dm ,new DefaultVectorCollection>());
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public DBSCAN(DBSCAN toCopy)
{
this.vc = toCopy.vc.clone();
this.dm = toCopy.dm.clone();
this.stndDevs = toCopy.stndDevs;
}
public List> cluster(DataSet dataSet, int minPts)
{
return createClusterListFromAssignmentArray(cluster(dataSet, minPts, (int[])null), dataSet);
}
public int[] cluster(DataSet dataSet, int minPts, int[] designations)
{
return cluster(dataSet, minPts, false, designations);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 3, parallel, designations);
}
@Override
public DBSCAN clone()
{
return new DBSCAN(this);
}
public List> cluster(DataSet dataSet, int minPts, boolean parallel)
{
return createClusterListFromAssignmentArray(cluster(dataSet, minPts, parallel, null), dataSet);
}
public int[] cluster(DataSet dataSet, int minPts, boolean parallel, int[] designations)
{
TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel);
vc.build(parallel, getVecIndexPairs(dataSet), dm);
List> neighbors = new ArrayList<>();
List> distances = new ArrayList<>();
vc.search(vc, minPts+1, neighbors, distances, parallel);
OnLineStatistics stats = ParallelUtils.run(parallel, dataSet.getSampleSize(), (start, end)->
{
OnLineStatistics s = new OnLineStatistics();
for(int i = start; i < end; i++)
s.add(distances.get(i).get(minPts));
return s;
}, (t, u)->t.apply(t, u));
double eps = stats.getMean() + stats.getStandardDeviation()*stndDevs;
return cluster(dataSet, eps, minPts, vc, parallel, designations);
}
private List> getVecIndexPairs(DataSet dataSet)
{
List> vecs = new ArrayList<>(dataSet.getSampleSize());
for(int i = 0; i < dataSet.getSampleSize(); i++)
vecs.add(new VecPaired<>(dataSet.getDataPoint(i).getNumericalValues(), i));
return vecs;
}
public List> cluster(DataSet dataSet, double eps, int minPts)
{
return createClusterListFromAssignmentArray(cluster(dataSet, eps, minPts, (int[]) null), dataSet);
}
public int[] cluster(DataSet dataSet, double eps, int minPts, int[] designations)
{
TrainableDistanceMetric.trainIfNeeded(dm, dataSet);
return cluster(dataSet, eps, minPts, vc, false, designations);
}
public List> cluster(DataSet dataSet, double eps, int minPts, boolean parallel)
{
return createClusterListFromAssignmentArray(cluster(dataSet, eps, minPts, parallel, null), dataSet);
}
public int[] cluster(DataSet dataSet, double eps, int minPts, boolean parallel, int[] designations)
{
TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel);
return cluster(dataSet, eps, minPts, vc, parallel, designations);
}
private int[] cluster(DataSet dataSet, double eps, int minPts, VectorCollection> vc, boolean parallel, int[] pointCats)
{
if (pointCats == null)
pointCats = new int[dataSet.getSampleSize()];
Arrays.fill(pointCats, UNCLASSIFIED);
vc.build(parallel, getVecIndexPairs(dataSet), dm);
List> neighbors = new ArrayList<>();
List> distances = new ArrayList<>();
vc.search(vc, 0, eps, neighbors, distances, parallel);
int curClusterID = 0;
for(int i = 0; i < pointCats.length; i++)
{
if(pointCats[i] == UNCLASSIFIED)
{
//All assignments are done by expandCluster
if(expandCluster(pointCats, dataSet, i, curClusterID, eps, minPts, neighbors))
curClusterID++;
}
}
return pointCats;
}
/**
*
* @param pointCats the array to store the cluster assignments in
* @param dataSet the data set
* @param point the current data point we are working on
* @param clId the current cluster we are working on
* @param eps the search radius
* @param minPts the minimum number of points to create a new cluster
* @param vc the collection to use to search with
* @return true if a cluster was expanded, false if the point was marked as noise
*/
private boolean expandCluster(int[] pointCats, DataSet dataSet, int point, int clId, double eps, int minPts, List> neighbors)
{
List seeds = neighbors.get(point);
if(seeds.size() < minPts)// no core point
{
pointCats[point] = NOISE;
return false;
}
//Else, all points in seeds are density-reachable from Point
List results;
pointCats[point] = clId;
Queue workQue = new ArrayDeque<>(seeds);
while(!workQue.isEmpty())
{
int currentP = workQue.poll();
results = neighbors.get(currentP);
if(results.size() >= minPts)
for(int resultPIndx : results)
{
if(pointCats[resultPIndx] < 0)// is UNCLASSIFIED or NOISE
{
if(pointCats[resultPIndx] == UNCLASSIFIED)
workQue.add(resultPIndx);
pointCats[resultPIndx] = clId;
}
}
}
return true;
}
}
Ads help maintain this website.