Package elki.clustering

Class SNNClustering<O>

  • Type Parameters:
    O - the type of Object the algorithm is applied on
    All Implemented Interfaces:
    Algorithm, ClusteringAlgorithm<Clustering<Model>>
    @Title("SNN: Shared Nearest Neighbor Clustering")
@Description("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\'03)",
           url="https://doi.org/10.1137/1.9781611972733.5",
           bibkey="DBLP:conf/sdm/ErtozSK03")
public class SNNClustering<O>
extends java.lang.Object
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
    Proc. of SIAM Data Mining (SDM'03)

    Since:
    0.1
    Author:
    Arthur Zimek

    • 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 java.util.List<ModifiableDBIDs> resultList
        Holds a list of clusters found.

      • processedIDs

        protected ModifiableDBIDs processedIDs
        Holds a set of processed ids.

    • Constructor Detail

      • SNNClustering

        public SNNClustering​(SharedNearestNeighborSimilarity<O> similarityFunction,
                     int epsilon,
                     int minpts)
        Constructor.
        Parameters:
        similarityFunction - Similarity function
        epsilon - Epsilon
        minpts - Minpts

    • Method Detail

      • getInputTypeRestriction

        public TypeInformation[] getInputTypeRestriction()
        Description copied from interface: Algorithm
        Get the input type restriction used for negotiating the data query.
        Specified by:
        getInputTypeRestriction in interface Algorithm
        Returns:
        Type restriction

      • run

        public Clustering<Model> run​(Relation<O> relation)
        Perform SNN clustering
        Parameters:
        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