de.lmu.ifi.dbs.elki.algorithm.clustering
Class SNNClustering<O extends DatabaseObject,D extends Distance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O>
              de.lmu.ifi.dbs.elki.algorithm.clustering.SNNClustering<O,D>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

D - the type of Distance used for the preprocessing of the shared nearest neighbors neighborhood lists

All Implemented Interfaces:

Algorithm<O>, Clustering<O>, Loggable, Parameterizable

public class SNNClustering<O extends DatabaseObject,D extends Distance<D>>
extends AbstractAlgorithm<O>
implements Clustering<O>

Shared nearest neighbor clustering.

This class implements the algorithm proposed in L. Ertöz, M. Steinbach, V. Kumar: Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data. In: Proc. of SIAM Data Mining (SDM), 2003.

Author:

Arthur Zimek

Field Summary

private IntegerDistance	epsilon Holds the Epsilon value.
static OptionID	EPSILON_ID OptionID for EPSILON_PARAM
private IntParameter	EPSILON_PARAM Parameter to specify the minimum SNN density, must be an integer greater than 0.
private int	minpts Holds the minimum points value.
static OptionID	MINPTS_ID OptionID for MINPTS_PARAM
private IntParameter	MINPTS_PARAM Parameter to specify the threshold for minimum number of points in the epsilon-SNN-neighborhood of a point, must be an integer greater than 0.
protected Set<Integer>	noise Holds a set of noise.
protected Set<Integer>	processedIDs Holds a set of processed ids.
protected ClustersPlusNoise<O>	result Provides the result of the algorithm.
protected List<List<Integer>>	resultList Holds a list of clusters found.
private SharedNearestNeighborSimilarityFunction<O,D>	similarityFunction The similarity function for the shared nearest neighbor similarity.

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

SNNClustering()
Sets epsilon and minimum points to the optionhandler additionally to the parameters provided by super-classes.

Method Summary

String	description() Returns a description of the class and the required parameters.
protected void	expandCluster(Database<O> database, Integer startObjectID, Progress progress) DBSCAN-function expandCluster adapted to SNN criterion.
protected List<Integer>	findSNNNeighbors(Database<O> database, Integer queryObject)
List<AttributeSettings>	getAttributeSettings() Returns the settings of all options assigned to the option handler.
Description	getDescription() Returns a description of the algorithm.
IntegerDistance	getEpsilon()
ClustersPlusNoise<O>	getResult() Returns the result of the algorithm.
protected void	runInTime(Database<O> database) Performs the SNN clustering algorithm on the given database.
String[]	setParameters(String[] args) Sets the parameters epsilon and minpts additionally to the parameters set by the super-class' method.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.Algorithm

run, setTime, setVerbose

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription

Field Detail

EPSILON_ID

public static final OptionID EPSILON_ID

OptionID for EPSILON_PARAM

MINPTS_ID

public static final OptionID MINPTS_ID

OptionID for MINPTS_PARAM

EPSILON_PARAM

private final IntParameter EPSILON_PARAM

Parameter to specify the minimum SNN density, must be an integer greater than 0.

Key: -snn.epsilon

MINPTS_PARAM

private final IntParameter MINPTS_PARAM

Parameter to specify the threshold for minimum number of points in the epsilon-SNN-neighborhood of a point, must be an integer greater than 0.

Key: -snn.minpts

epsilon

private IntegerDistance epsilon

Holds the Epsilon value.

minpts

private int minpts

Holds the minimum points value.

resultList

protected List<List<Integer>> resultList

Holds a list of clusters found.

result

protected ClustersPlusNoise<O extends DatabaseObject> result

Provides the result of the algorithm.

noise

protected Set<Integer> noise

Holds a set of noise.

processedIDs

protected Set<Integer> processedIDs

Holds a set of processed ids.

similarityFunction

private SharedNearestNeighborSimilarityFunction<O extends DatabaseObject,D extends Distance<D>> similarityFunction

The similarity function for the shared nearest neighbor similarity.

Constructor Detail

SNNClustering

public SNNClustering()

Sets epsilon and minimum points to the optionhandler additionally to the parameters provided by super-classes.

Method Detail

runInTime

protected void runInTime(Database<O> database)

Performs the SNN clustering algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject>

Parameters:

database - the database to run the algorithm on

See Also:

AbstractAlgorithm.runInTime(de.lmu.ifi.dbs.elki.database.Database)

findSNNNeighbors

protected List<Integer> findSNNNeighbors(Database<O> database,
                                         Integer queryObject)

expandCluster

protected void expandCluster(Database<O> database,
                             Integer startObjectID,
                             Progress progress)

DBSCAN-function expandCluster adapted to SNN criterion.

Border-Objects become members of the first possible cluster.

Parameters:

database - the database on which the algorithm is run

startObjectID - potential seed of a new potential cluster

progress - the progress object to report about the progress of clustering

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Specified by:

getDescription in interface Algorithm<O extends DatabaseObject>

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Sets the parameters epsilon and minpts additionally to the parameters set by the super-class' method. Both epsilon and minpts are required parameters.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractAlgorithm<O extends DatabaseObject>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

getResult

public ClustersPlusNoise<O> getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Specified by:

getResult in interface Algorithm<O extends DatabaseObject>

Specified by:

getResult in interface Clustering<O extends DatabaseObject>

Returns:

the result of the algorithm

See Also:

Algorithm.getResult()

getEpsilon

public IntegerDistance getEpsilon()

description

public String description()

Description copied from interface: Parameterizable

Returns a description of the class and the required parameters.

This description should be suitable for a usage description as for a standalone application.

Specified by:

description in interface Parameterizable

Overrides:

description in class AbstractAlgorithm<O extends DatabaseObject>

Returns:

String a description of the class and the required parameters

See Also:

Parameterizable.description()

getAttributeSettings

public List<AttributeSettings> getAttributeSettings()

Description copied from class: AbstractParameterizable

Returns the settings of all options assigned to the option handler.

Specified by:

getAttributeSettings in interface Parameterizable

Overrides:

getAttributeSettings in class AbstractParameterizable

Returns:

the setting of the attributes of the parameterizable

See Also:

Parameterizable.getAttributeSettings()