de.lmu.ifi.dbs.elki.algorithm.clustering
Class DeLiClu<NV extends NumberVector<NV,?>,D extends Distance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>
      de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<NV,D,ClusterOrderResult<D>>
          de.lmu.ifi.dbs.elki.algorithm.clustering.DeLiClu<NV,D>

Type Parameters:

NV - the type of NumberVector handled by this Algorithm

D - the type of Distance used

All Implemented Interfaces:

Algorithm, OPTICSTypeAlgorithm<D>, InspectionUtilFrequentlyScanned, Parameterizable

@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")
public class DeLiClu<NV extends NumberVector<NV,?>,D extends Distance<D>>
extends AbstractDistanceBasedAlgorithm<NV,D,ClusterOrderResult<D>>
implements OPTICSTypeAlgorithm<D>

DeLiClu provides the DeLiClu algorithm, 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.

Nested Class Summary

static class	DeLiClu.Parameterizer<NV extends NumberVector<NV,?>,D extends Distance<D>> Parameterization class.
class	DeLiClu.SpatialObjectPair Encapsulates an entry in the cluster order.

Field Summary

private UpdatableHeap<DeLiClu.SpatialObjectPair>	heap The priority queue for the algorithm.
private KNNJoin<NV,D,DeLiCluNode,DeLiCluEntry>	knnJoin Holds the knnJoin algorithm.
private static Logging	logger The logger for this class.
private int	minpts Holds the value of MINPTS_ID.
static OptionID	MINPTS_ID Parameter to specify the threshold for minimum number of points within a cluster, must be an integer greater than 0.

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

DISTANCE_FUNCTION_ID

Constructor Summary

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

Method Summary

private void	expandDirNodes(SpatialPrimitiveDistanceFunction<NV,D> distFunction, DeLiCluNode node1, DeLiCluNode node2) Expands the specified directory nodes.
private void	expandLeafNodes(SpatialPrimitiveDistanceFunction<NV,D> distFunction, DeLiCluNode node1, DeLiCluNode node2, DataStore<KNNList<D>> knns) Expands the specified leaf nodes.
private void	expandNodes(DeLiCluTree index, SpatialPrimitiveDistanceFunction<NV,D> distFunction, DeLiClu.SpatialObjectPair nodePair, DataStore<KNNList<D>> knns) Expands the spatial nodes of the specified pair.
D	getDistanceFactory() Get the distance factory.
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 DBID	getStartObject(Relation<NV> relation) Returns the id of the start object for the run method.
private void	reinsertExpanded(SpatialPrimitiveDistanceFunction<NV,D> distFunction, DeLiCluTree index, List<TreeIndexPathComponent<DeLiCluEntry>> path, DataStore<KNNList<D>> knns) Reinserts the objects of the already expanded nodes.
private void	reinsertExpanded(SpatialPrimitiveDistanceFunction<NV,D> distFunction, DeLiCluTree index, List<TreeIndexPathComponent<DeLiCluEntry>> path, int pos, SpatialDirectoryEntry parentEntry, DataStore<KNNList<D>> knns)
ClusterOrderResult<D>	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.OPTICSTypeAlgorithm

run

Field Detail

logger

private static final Logging logger

The logger for this class.

MINPTS_ID

public static final OptionID MINPTS_ID

Parameter to specify the threshold for minimum number of points within a cluster, must be an integer greater than 0.

heap

private UpdatableHeap<DeLiClu.SpatialObjectPair> heap

The priority queue for the algorithm.

knnJoin

private KNNJoin<NV extends NumberVector<NV,?>,D extends Distance<D>,DeLiCluNode,DeLiCluEntry> knnJoin

Holds the knnJoin algorithm.

minpts

private int minpts

Holds the value of MINPTS_ID.

Constructor Detail

DeLiClu

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

Constructor.

Parameters:

distanceFunction - Distance function

minpts - MinPts

Method Detail

run

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

getStartObject

private DBID getStartObject(Relation<NV> relation)

Returns the id of the start object for the run method.

Parameters:

relation - the database relation storing the objects

Returns:

the id of the start object for the run method

expandNodes

private void expandNodes(DeLiCluTree index,
                         SpatialPrimitiveDistanceFunction<NV,D> distFunction,
                         DeLiClu.SpatialObjectPair nodePair,
                         DataStore<KNNList<D>> 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,D> 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,D> distFunction,
                             DeLiCluNode node1,
                             DeLiCluNode node2,
                             DataStore<KNNList<D>> 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,D> distFunction,
                              DeLiCluTree index,
                              List<TreeIndexPathComponent<DeLiCluEntry>> path,
                              DataStore<KNNList<D>> 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,D> distFunction,
                              DeLiCluTree index,
                              List<TreeIndexPathComponent<DeLiCluEntry>> path,
                              int pos,
                              SpatialDirectoryEntry parentEntry,
                              DataStore<KNNList<D>> knns)

getMinPts

public int getMinPts()

Description copied from interface: OPTICSTypeAlgorithm

Get the minpts value used. Needed for OPTICS Xi etc.

Specified by:

getMinPts in interface OPTICSTypeAlgorithm<D extends Distance<D>>

Returns:

minpts value

getDistanceFactory

public D getDistanceFactory()

Description copied from interface: OPTICSTypeAlgorithm

Get the distance factory. Needed for type checking (i.e. is number distance)

Specified by:

getDistanceFactory in interface OPTICSTypeAlgorithm<D extends Distance<D>>

Returns:

distance factory

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<ClusterOrderResult<D extends Distance<D>>>

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<ClusterOrderResult<D extends Distance<D>>>

Returns:

the static logger