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

Class DeLiClu<NV extends NumberVector>

java.lang.Object

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

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

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

Type Parameters:

NV - the type of NumberVector handled by this Algorithm

All Implemented Interfaces:

Algorithm, OPTICSTypeAlgorithm, DistanceBasedAlgorithm<NV>

@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="E. Achtert, C. B\u00f6hm, P. Kr\u00f6ger",
           title="DeLiClu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking",
           booktitle="Proc. 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2006), Singapore, 2006",
           url="http://dx.doi.org/10.1007/11731139_16")
@Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.DeLiClu")
public class DeLiClu<NV extends NumberVector>
extends AbstractDistanceBasedAlgorithm<NV,ClusterOrder>
implements OPTICSTypeAlgorithm

DeliClu: Density-Based Hierarchical Clustering, a hierarchical algorithm to find density-connected sets in a database.

Reference:
E. Achtert, C. Böhm, P. Kröger: DeLiClu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking.
In Proc. 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2006), Singapore, 2006.

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DeLiClu.Parameterizer<NV extends NumberVector> Parameterization class.
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.
private KNNJoin<NV,DeLiCluNode,DeLiCluEntry>	knnJoin Holds the knnJoin algorithm.
private static Logging	LOG The logger for this class.
private int	minpts Density threshold in number of objects.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
DeLiClu(DistanceFunction<? super NV> distanceFunction, int minpts) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	expandDirNodes(SpatialPrimitiveDistanceFunction<NV> distFunction, DeLiCluNode node1, DeLiCluNode node2) Expands the specified directory nodes.
private void	expandLeafNodes(SpatialPrimitiveDistanceFunction<NV> distFunction, DeLiCluNode node1, DeLiCluNode node2, DataStore<KNNList> knns) Expands the specified leaf nodes.
private void	expandNodes(DeLiCluTree index, SpatialPrimitiveDistanceFunction<NV> 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<NV> distFunction, DeLiCluTree index, IndexTreePath<DeLiCluEntry> path, DataStore<KNNList> knns) Reinserts the objects of the already expanded nodes.
private void	reinsertExpanded(SpatialPrimitiveDistanceFunction<NV> distFunction, DeLiCluTree index, List<IndexTreePath<DeLiCluEntry>> path, int pos, DeLiCluEntry parentEntry, DataStore<KNNList> knns)
ClusterOrder	run(Database database, Relation<NV> relation)

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

getDistanceFunction

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

makeParameterDistanceFunction, 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.

knnJoin

private KNNJoin<NV extends NumberVector,DeLiCluNode,DeLiCluEntry> knnJoin

Holds the knnJoin algorithm.

minpts

private int minpts

Density threshold in number of objects.

Constructor Detail

DeLiClu

public DeLiClu(DistanceFunction<? super NV> distanceFunction,
       int minpts)

Constructor.

Parameters:

distanceFunction - Distance function

minpts - MinPts

Method Detail

run

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

expandNodes

private void expandNodes(DeLiCluTree index,
               SpatialPrimitiveDistanceFunction<NV> 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<NV> 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<NV> 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<NV> 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<NV> distFunction,
                    DeLiCluTree index,
                    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