de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan

Class LSDBC<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,Clustering<Model>>

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.LSDBC<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<Model>>, DistanceBasedAlgorithm<O>

@Title(value="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(value=100)
public class LSDBC<O extends NumberVector>
extends AbstractDistanceBasedAlgorithm<O,Clustering<Model>>
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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LSDBC.Parameterizer<O extends NumberVector> Parameterization class

Field Summary

Fields

Modifier and Type	Field and Description
protected double	alpha Alpha parameter.
protected int	k kNN parameter.
private static Logging	LOG Class logger.
protected static int	NOISE Constants used internally.
protected static int	UNPROCESSED Constants used internally.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
LSDBC(DistanceFunction<? super O> distanceFunction, int k, double alpha) Constructor.

Method Summary

Modifier and Type	Method and Description
protected int	expandCluster(int clusterid, WritableIntegerDataStore clusterids, KNNQuery<O> knnq, DBIDs neighbors, double maxkdist, FiniteProgress progress) Set-based expand cluster implementation.
private void	fillDensities(KNNQuery<O> knnq, DBIDs ids, WritableDoubleDataStore dens) Collect all densities into an array for sorting.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private boolean	isLocalMaximum(double kdist, DBIDs neighbors, WritableDoubleDataStore kdists) Test if a point is a local density maximum.
Clustering<Model>	run(Database database, Relation<O> relation) Run the LSDBC algorithm

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

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

Class logger.

k

protected int k

kNN parameter.

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(DistanceFunction<? super O> distanceFunction,
             int k,
             double alpha)

Constructor.

Parameters:

distanceFunction - Distance function to use

k - Neighborhood size parameter

alpha - Alpha parameter

Method Detail

run

public Clustering<Model> run(Database database,
                             Relation<O> relation)

Run the LSDBC algorithm

Parameters:

database - Database to process

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,
                            KNNQuery<O> 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(KNNQuery<O> knnq,
                           DBIDs ids,
                           WritableDoubleDataStore dens)

Collect all densities into an array for sorting.

Parameters:

knnq - kNN query

ids - DBIDs to process

dens - Density storage

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