de.lmu.ifi.dbs.elki.algorithm.clustering

Class GriDBSCAN.Instance<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.clustering.GriDBSCAN.Instance<V>

Type Parameters:

V - Vector type

Enclosing class:

GriDBSCAN<V extends NumberVector>

protected static class GriDBSCAN.Instance<V extends NumberVector>
extends java.lang.Object

Instance, for a single run.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
private Border[]	borders Border identifier objects (shared to conserve memory).
protected int[]	cells Number of cells per dimension.
private WritableDataStore<Assignment>	clusterids Cluster assignments.
private Core[]	cores Core identifier objects (shared to conserve memory).
protected int	dim Dimensionality.
protected DistanceFunction<? super V>	distanceFunction Distance function used.
protected double[][]	domain Value domain.
protected double	epsilon Holds the epsilon radius threshold.
(package private) it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap<ModifiableDBIDs>	grid Data grid partitioning.
protected double	gridwidth Width of the grid cells.
protected int	minpts Holds the minimum cluster size.
protected static int	NOISE Noise IDs.
protected double[]	offset Grid offset.
private boolean	overflown Indicates that the number of grid cells has overflown.
private WritableIntegerDataStore	temporary Temporary assignments of a single run.
protected static int	UNPROCESSED Unprocessed IDs.

Constructor Summary

Constructors

Constructor and Description
Instance(DistanceFunction<? super V> distanceFunction, double epsilon, int minpts, double gridwidth) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	buildGrid(Relation<V> relation, int numcells, double[] offset) Build the data grid.
protected int	checkGridCellSizes(int size, long numcell) Perform some sanity checks on the grid cells.
private long	computeGridBaseOffsets() Compute the grid base offset.
protected int	expandCluster(DBIDRef seed, int clusterid, WritableIntegerDataStore clusterids, ModifiableDoubleDBIDList neighbors, ArrayModifiableDBIDs activeSet, RangeQuery<V> rq, FiniteProgress pprog) Set-based expand cluster implementation.
private void	insertIntoGrid(DBIDRef id, V obj, int d, int v) Insert a single object into the grid; potentially into multiple cells (at most 2^d) via recursion.
protected void	mergeClusterInformation(ModifiableDBIDs cellids, WritableIntegerDataStore temporary, WritableDataStore<Assignment> clusterids) Merge cluster information.
protected int	processCorePoint(DBIDRef seed, DoubleDBIDList newneighbors, int clusterid, WritableIntegerDataStore clusterids, ArrayModifiableDBIDs activeSet) Process a single core point.
Clustering<Model>	run(Relation<V> relation) Performs the DBSCAN algorithm on the given database.
private void	updateCoreBorderObjects(int clusterid) Update the shared arrays for core points (to conserve memory)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

UNPROCESSED

protected static final int UNPROCESSED

Unprocessed IDs.

See Also:

Constant Field Values

NOISE

protected static final int NOISE

Noise IDs.

See Also:

Constant Field Values

distanceFunction

protected DistanceFunction<? super V extends NumberVector> distanceFunction

Distance function used.

epsilon

protected double epsilon

Holds the epsilon radius threshold.

minpts

protected int minpts

Holds the minimum cluster size.

gridwidth

protected double gridwidth

Width of the grid cells. Must be at least 2 epsilon!

domain

protected double[][] domain

Value domain.

dim

protected int dim

Dimensionality.

offset

protected double[] offset

Grid offset.

cells

protected int[] cells

Number of cells per dimension.

grid

it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap<ModifiableDBIDs> grid

Data grid partitioning.

cores

private Core[] cores

Core identifier objects (shared to conserve memory).

borders

private Border[] borders

Border identifier objects (shared to conserve memory).

clusterids

private WritableDataStore<Assignment> clusterids

Cluster assignments.

temporary

private WritableIntegerDataStore temporary

Temporary assignments of a single run.

overflown

private boolean overflown

Indicates that the number of grid cells has overflown.

Constructor Detail

Instance

public Instance(DistanceFunction<? super V> distanceFunction,
                double epsilon,
                int minpts,
                double gridwidth)

Constructor.

Parameters:

distanceFunction - Distance function

epsilon - Epsilon

minpts - MinPts

gridwidth - Grid width

Method Detail

run

public Clustering<Model> run(Relation<V> relation)

Performs the DBSCAN algorithm on the given database.

Parameters:

relation - Relation to process

updateCoreBorderObjects

private void updateCoreBorderObjects(int clusterid)

Update the shared arrays for core points (to conserve memory)

Parameters:

clusterid - Number of clusters

computeGridBaseOffsets

private long computeGridBaseOffsets()

Compute the grid base offset.

Returns:

Total number of grid cells

buildGrid

protected void buildGrid(Relation<V> relation,
                         int numcells,
                         double[] offset)

Build the data grid.

Parameters:

relation - Data relation

numcells - Total number of cells

offset - Offset

insertIntoGrid

private void insertIntoGrid(DBIDRef id,
                            V obj,
                            int d,
                            int v)

Insert a single object into the grid; potentially into multiple cells (at most 2^d) via recursion.

Parameters:

id - Object ID

obj - Object

d - Current dimension

v - Current cell value

checkGridCellSizes

protected int checkGridCellSizes(int size,
                                 long numcell)

Perform some sanity checks on the grid cells.

Parameters:

numcell - Number of cells

size - Relation size

Returns:

Number of cells with minPts points

expandCluster

protected int expandCluster(DBIDRef seed,
                            int clusterid,
                            WritableIntegerDataStore clusterids,
                            ModifiableDoubleDBIDList neighbors,
                            ArrayModifiableDBIDs activeSet,
                            RangeQuery<V> rq,
                            FiniteProgress pprog)

Set-based expand cluster implementation.

Parameters:

clusterid - ID of the current cluster.

clusterids - Current object to cluster mapping.

neighbors - Neighbors acquired by initial getNeighbors call.

activeSet - Set to manage active candidates.

rq - Range query

pprog - Object progress

Returns:

cluster size

processCorePoint

protected int processCorePoint(DBIDRef seed,
                               DoubleDBIDList newneighbors,
                               int clusterid,
                               WritableIntegerDataStore clusterids,
                               ArrayModifiableDBIDs activeSet)

Process a single core point.

Parameters:

seed - Point to process

newneighbors - New neighbors

clusterid - Cluster to add to

clusterids - Cluster assignment storage.

activeSet - Active set of cluster seeds

Returns:

Number of new points added to cluster

mergeClusterInformation

protected void mergeClusterInformation(ModifiableDBIDs cellids,
                                       WritableIntegerDataStore temporary,
                                       WritableDataStore<Assignment> clusterids)

Merge cluster information.

Parameters:

cellids - IDs in current cell

temporary - Temporary assignments

clusterids - Merged cluster assignment