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

Class DeLiClu<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<V,ClusterOrder>

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.DeLiClu<V>

Type Parameters:

V - the type of NumberVector handled by this Algorithm

All Implemented Interfaces:

Algorithm, OPTICSTypeAlgorithm, DistanceBasedAlgorithm<V>

@Title(value="DeliClu: Density-Based Hierarchical Clustering")
 @Description(value="Hierachical algorithm to find density-connected sets in a database based on the parameter \'minpts\'.")
 @Reference(authors="Elke Achtert, Christian B\u00f6hm, Peer Kr\u00f6ger",
           title="DeLiClu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking",
           booktitle="Proc. 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2006)",
           url="https://doi.org/10.1007/11731139_16",
           bibkey="DBLP:conf/pakdd/AchtertBK06")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.DeLiClu")
public class DeLiClu<V extends NumberVector>
extends AbstractDistanceBasedAlgorithm<V,ClusterOrder>
implements OPTICSTypeAlgorithm

DeliClu: Density-Based Hierarchical Clustering

A hierarchical algorithm to find density-connected sets in a database, closely related to OPTICS but exploiting the structure of a R-tree for acceleration.

Reference:

Elke Achtert, Christian Böhm, Peer Kröger
DeLiClu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking
Proc. 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2006)

Since:

0.1

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DeLiClu.Parameterizer<V extends NumberVector> Parameterization class.
static class	DeLiClu.SpatialObjectPair Encapsulates an entry in the cluster order.

Field Summary

Fields

Modifier and Type	Field and Description
private UpdatableHeap<DeLiClu.SpatialObjectPair>	heap The priority queue for the algorithm.
protected DeLiCluTreeFactory<? super V>	indexer DeLiClu Index factory.
private static Logging	LOG The logger for this class.
private int	minpts Density threshold in number of objects.

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
DeLiClu(DeLiCluTreeFactory<? super V> indexer, DistanceFunction<? super V> distanceFunction, int minpts) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	expandDirNodes(SpatialPrimitiveDistanceFunction<V> distFunction, DeLiCluNode node1, DeLiCluNode node2) Expands the specified directory nodes.
private void	expandLeafNodes(SpatialPrimitiveDistanceFunction<V> distFunction, DeLiCluNode node1, DeLiCluNode node2, DataStore<KNNList> knns) Expands the specified leaf nodes.
private void	expandNodes(DeLiCluTree index, SpatialPrimitiveDistanceFunction<V> distFunction, DeLiClu.SpatialObjectPair nodePair, DataStore<KNNList> knns) Expands the spatial nodes of the specified pair.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
int	getMinPts() Get the minpts value used.
private void	reinsertExpanded(SpatialPrimitiveDistanceFunction<V> distFunction, DeLiCluTree index, IndexTreePath<DeLiCluEntry> path, DataStore<KNNList> knns) Reinserts the objects of the already expanded nodes.
private void	reinsertExpanded(SpatialPrimitiveDistanceFunction<V> distFunction, DeLiCluTree index, java.util.List<IndexTreePath<DeLiCluEntry>> path, int pos, DeLiCluEntry parentEntry, DataStore<KNNList> knns)
ClusterOrder	run(Database database, Relation<V> relation)

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.optics.OPTICSTypeAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

heap

private UpdatableHeap<DeLiClu.SpatialObjectPair> heap

The priority queue for the algorithm.

minpts

private int minpts

Density threshold in number of objects.

indexer

protected DeLiCluTreeFactory<? super V extends NumberVector> indexer

DeLiClu Index factory.

Constructor Detail

DeLiClu

public DeLiClu(DeLiCluTreeFactory<? super V> indexer,
               DistanceFunction<? super V> distanceFunction,
               int minpts)

Constructor.

Parameters:

distanceFunction - Distance function

minpts - MinPts

Method Detail

run

public ClusterOrder run(Database database,
                        Relation<V> relation)

expandNodes

private void expandNodes(DeLiCluTree index,
                         SpatialPrimitiveDistanceFunction<V> distFunction,
                         DeLiClu.SpatialObjectPair nodePair,
                         DataStore<KNNList> knns)

Expands the spatial nodes of the specified pair.

Parameters:

index - the index storing the objects

distFunction - the spatial distance function of this algorithm

nodePair - the pair of nodes to be expanded

knns - the knn list

expandDirNodes

private void expandDirNodes(SpatialPrimitiveDistanceFunction<V> distFunction,
                            DeLiCluNode node1,
                            DeLiCluNode node2)

Expands the specified directory nodes.

Parameters:

distFunction - the spatial distance function of this algorithm

node1 - the first node

node2 - the second node

expandLeafNodes

private void expandLeafNodes(SpatialPrimitiveDistanceFunction<V> distFunction,
                             DeLiCluNode node1,
                             DeLiCluNode node2,
                             DataStore<KNNList> knns)

Expands the specified leaf nodes.

Parameters:

distFunction - the spatial distance function of this algorithm

node1 - the first node

node2 - the second node

knns - the knn list

reinsertExpanded

private void reinsertExpanded(SpatialPrimitiveDistanceFunction<V> distFunction,
                              DeLiCluTree index,
                              IndexTreePath<DeLiCluEntry> path,
                              DataStore<KNNList> knns)

Reinserts the objects of the already expanded nodes.

Parameters:

distFunction - the spatial distance function of this algorithm

index - the index storing the objects

path - the path of the object inserted last

knns - the knn list

reinsertExpanded

private void reinsertExpanded(SpatialPrimitiveDistanceFunction<V> distFunction,
                              DeLiCluTree index,
                              java.util.List<IndexTreePath<DeLiCluEntry>> path,
                              int pos,
                              DeLiCluEntry parentEntry,
                              DataStore<KNNList> knns)

getMinPts

public int getMinPts()

Description copied from interface: OPTICSTypeAlgorithm

Get the minpts value used. Needed for OPTICS Xi.

Specified by:

getMinPts in interface OPTICSTypeAlgorithm

Returns:

minpts value

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<ClusterOrder>

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<ClusterOrder>

Returns:

the static logger