Class SLINK<O>

  • Type Parameters:
    O - the type of DatabaseObject the algorithm is applied on
    All Implemented Interfaces:
    Algorithm, HierarchicalClusteringAlgorithm
    Direct Known Subclasses:
    CLINK

    @Title("SLINK: Single Link Clustering")
    @Description("Hierarchical clustering algorithm based on single-link connectivity.")
    @Reference(authors="R. Sibson",
               title="SLINK: An optimally efficient algorithm for the single-link cluster method",
               booktitle="The Computer Journal 16 (1)",
               url="https://doi.org/10.1093/comjnl/16.1.30",
               bibkey="DBLP:journals/cj/Sibson73")
    @Alias({"single-link","single-linkage"})
    @Priority(200)
    public class SLINK<O>
    extends java.lang.Object
    implements HierarchicalClusteringAlgorithm
    Implementation of the efficient Single-Link Algorithm SLINK of R. Sibson.

    For ELKI 0.8.0, this was rewritten to no longer use the original "pointer" output format, but instead generate an easier to use merge history now.

    This is probably the fastest exact single-link algorithm currently in use.

    Reference:

    R. Sibson
    SLINK: An optimally efficient algorithm for the single-link cluster method
    In: The Computer Journal 16 (1)

    Since:
    0.6.0
    Author:
    Elke Achtert, Erich Schubert
    • Field Detail

      • LOG

        private static final Logging LOG
        The logger for this class.
      • distance

        protected Distance<? super O> distance
        Distance function used.
    • Constructor Detail

      • SLINK

        public SLINK​(Distance<? super O> distance)
        Constructor.
        Parameters:
        distance - Distance function
    • 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 ClusterMergeHistory run​(Relation<O> relation)
        Performs the SLINK algorithm on the given database.
        Parameters:
        relation - Data relation to use
      • step2

        private void step2​(DBIDRef id,
                           DBIDArrayIter it,
                           int n,
                           DistanceQuery<? super O> distQuery,
                           WritableDoubleDataStore m)
        Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
        Parameters:
        id - the id of the object to be inserted into the pointer representation
        it - Array iterator
        n - Last object
        distQuery - Distance query
        m - Data store
      • step2primitive

        private void step2primitive​(DBIDRef id,
                                    DBIDArrayIter it,
                                    int n,
                                    Relation<? extends O> relation,
                                    PrimitiveDistance<? super O> distance,
                                    WritableDoubleDataStore m)
        Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
        Parameters:
        id - the id of the object to be inserted into the pointer representation
        it - Array iterator
        n - Last object
        m - Data store
        relation - Data relation
        distance - Distance function to use
      • slinkstep4

        private void slinkstep4​(DBIDRef id,
                                DBIDArrayIter it,
                                int n,
                                WritableDBIDDataStore pi,
                                WritableDoubleDataStore lambda)
        Fourth step: Actualize the clusters if necessary
        Parameters:
        id - the id of the current object
        it - array iterator
        n - Last object to process at this run
        pi - Pi data store
        lambda - Lambda data store
      • getLogger

        protected Logging getLogger()
        Get the (static) class logger.