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>>

@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.

Author:

Arthur Zimek

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 int	epsilon Epsilon radius threshold.
private static Logging	LOG The logger for this class.
private int	minpts Minimum number of clusters for connectedness.
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, int epsilon, int minpts) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	expandCluster(SimilarityQuery<O> snnInstance, DBIDRef startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog) DBSCAN-function expandCluster adapted to SNN criterion.
protected ArrayModifiableDBIDs	findSNNNeighbors(SimilarityQuery<O> snnInstance, DBIDRef 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

LOG

private static final Logging LOG

The logger for this class.

epsilon

private int epsilon

Epsilon radius threshold.

minpts

private int minpts

Minimum number of clusters for connectedness.

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,
             int 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> snnInstance,
                                    DBIDRef 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> snnInstance,
                 DBIDRef 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