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

Class SNNClustering<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<Model>>

de.lmu.ifi.dbs.elki.algorithm.clustering.SNNClustering<O>

Type Parameters:

O - the type of Object the algorithm is applied on

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<Model>>, InspectionUtilFrequentlyScanned, Parameterizable

@Title(value="SNN: Shared Nearest Neighbor Clustering")
@Description(value="Algorithm to find shared-nearest-neighbors-density-connected sets in a database based on the parameters \'minPts\' and \'epsilon\' (specifying a volume). These two parameters determine a density threshold for clustering.")
@Reference(authors="L. Ert\u00f6z, M. Steinbach, V. Kumar",
           title="Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data",
           booktitle="Proc. of SIAM Data Mining (SDM), 2003",
           url="http://www.siam.org/meetings/sdm03/proceedings/sdm03_05.pdf")
public class SNNClustering<O>
extends AbstractAlgorithm<Clustering<Model>>
implements ClusteringAlgorithm<Clustering<Model>>

Shared nearest neighbor clustering.

Reference: 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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SNNClustering.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private IntegerDistance	epsilon Holds the value of EPSILON_ID.
static OptionID	EPSILON_ID Parameter to specify the minimum SNN density, must be an integer greater than 0.
private static Logging	logger The logger for this class.
private int	minpts Holds the value of MINPTS_ID.
static OptionID	MINPTS_ID 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 ModifiableDBIDs	noise Holds a set of noise.
protected ModifiableDBIDs	processedIDs Holds a set of processed ids.
protected List<ModifiableDBIDs>	resultList Holds a list of clusters found.
private SharedNearestNeighborSimilarityFunction<O>	similarityFunction The similarity function for the shared nearest neighbor similarity.

Constructor Summary

Constructors

Constructor and Description
SNNClustering(SharedNearestNeighborSimilarityFunction<O> similarityFunction, IntegerDistance epsilon, int minpts) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	expandCluster(SimilarityQuery<O,IntegerDistance> snnInstance, DBID startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog) DBSCAN-function expandCluster adapted to SNN criterion.
protected ArrayModifiableDBIDs	findSNNNeighbors(SimilarityQuery<O,IntegerDistance> snnInstance, DBID queryObject) Returns the shared nearest neighbors of the specified query object in the given database.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
Clustering<Model>	run(Database database, Relation<O> relation) Perform SNN clustering

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

makeParameterDistanceFunction, run

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.clustering.ClusteringAlgorithm

run

Field Detail

logger

private static final Logging logger

The logger for this class.

EPSILON_ID

public static final OptionID EPSILON_ID

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

epsilon

private IntegerDistance epsilon

Holds the value of EPSILON_ID.

MINPTS_ID

public static final OptionID MINPTS_ID

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.

minpts

private int minpts

Holds the value of MINPTS_ID.

resultList

protected List<ModifiableDBIDs> resultList

Holds a list of clusters found.

noise

protected ModifiableDBIDs noise

Holds a set of noise.

processedIDs

protected ModifiableDBIDs processedIDs

Holds a set of processed ids.

similarityFunction

private SharedNearestNeighborSimilarityFunction<O> similarityFunction

The similarity function for the shared nearest neighbor similarity.

Constructor Detail

SNNClustering

public SNNClustering(SharedNearestNeighborSimilarityFunction<O> similarityFunction,
             IntegerDistance epsilon,
             int minpts)

Constructor.

Parameters:

similarityFunction - Similarity function

epsilon - Epsilon

minpts - Minpts

Method Detail

run

public Clustering<Model> run(Database database,
                    Relation<O> relation)

Perform SNN clustering

Parameters:

database - Database

relation - Relation

Returns:

Result

findSNNNeighbors

protected ArrayModifiableDBIDs findSNNNeighbors(SimilarityQuery<O,IntegerDistance> snnInstance,
                                    DBID queryObject)

Returns the shared nearest neighbors of the specified query object in the given database.

Parameters:

snnInstance - shared nearest neighbors

queryObject - the query object

Returns:

the shared nearest neighbors of the specified query object in the given database

expandCluster

protected void expandCluster(SimilarityQuery<O,IntegerDistance> snnInstance,
                 DBID startObjectID,
                 FiniteProgress objprog,
                 IndefiniteProgress clusprog)

DBSCAN-function expandCluster adapted to SNN criterion.

Border-Objects become members of the first possible cluster.

Parameters:

snnInstance - shared nearest neighbors

startObjectID - potential seed of a new potential cluster

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

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Clustering<Model>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<Model>>

Returns:

the static logger