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