Class LSDBC<O extends NumberVector>

  • Type Parameters:
    O - Object type
    All Implemented Interfaces:
    Algorithm, ClusteringAlgorithm<Clustering<Model>>

    @Title("LSDBC: Locally Scaled Density Based Clustering")
    @Reference(authors="E. Bi\u00e7ici, D. Yuret",
               title="Locally Scaled Density Based Clustering",
               booktitle="Adaptive and Natural Computing Algorithms",
               url="https://doi.org/10.1007/978-3-540-71618-1_82",
               bibkey="DBLP:conf/icannga/BiciciY07")
    @Priority(100)
    public class LSDBC<O extends NumberVector>
    extends java.lang.Object
    implements ClusteringAlgorithm<Clustering<Model>>
    Locally Scaled Density Based Clustering.

    This is a variant of DBSCAN which starts with the most dense point first, then expands clusters until density has dropped below a threshold.

    Reference:

    E. Biçici, D. Yuret
    Locally Scaled Density Based Clustering
    Adaptive and Natural Computing Algorithms

    Since:
    0.7.0
    Author:
    Erich Schubert
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger.
      • kplus

        protected int kplus
        Number of neighbors (+ query point)
      • alpha

        protected double alpha
        Alpha parameter.
      • UNPROCESSED

        protected static int UNPROCESSED
        Constants used internally.
      • NOISE

        protected static int NOISE
        Constants used internally.
    • Constructor Detail

      • LSDBC

        public LSDBC​(Distance<? super O> distance,
                     int k,
                     double alpha)
        Constructor.
        Parameters:
        distance - Distance function to use
        k - Neighborhood size parameter
        alpha - Alpha parameter
    • 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)
        Run the LSDBC algorithm
        Parameters:
        relation - Data relation
        Returns:
        Clustering result
      • isLocalMaximum

        private boolean isLocalMaximum​(double kdist,
                                       DBIDs neighbors,
                                       WritableDoubleDataStore kdists)
        Test if a point is a local density maximum.
        Parameters:
        kdist - k-distance of current
        neighbors - Neighbor points
        kdists - kNN distances
        Returns:
        true when the point is a local maximum
      • expandCluster

        protected int expandCluster​(int clusterid,
                                    WritableIntegerDataStore clusterids,
                                    KNNSearcher<DBIDRef> knnq,
                                    DBIDs neighbors,
                                    double maxkdist,
                                    FiniteProgress progress)
        Set-based expand cluster implementation.
        Parameters:
        clusterid - ID of the current cluster.
        clusterids - Current object to cluster mapping.
        knnq - kNNQuery
        neighbors - Neighbors acquired by initial getNeighbors call.
        maxkdist - Maximum k-distance
        progress - Progress logging
        Returns:
        cluster size
      • fillDensities

        private void fillDensities​(KNNSearcher<DBIDRef> knnq,
                                   DBIDs ids,
                                   WritableDoubleDataStore dens)
        Collect all densities into an array for sorting.
        Parameters:
        knnq - kNN query
        ids - DBIDs to process
        dens - Density storage