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

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D>
                  de.lmu.ifi.dbs.elki.algorithm.clustering.DeLiClu<O,D>

Type Parameters:

O - the type of NumberVector handled by this Algorithm

D - the type of Distance used

All Implemented Interfaces:

Algorithm<O>, Loggable, Parameterizable

public class DeLiClu<O extends NumberVector<O,?>,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D>

DeLiClu provides the DeLiClu algorithm, a hierachical algorithm to find density-connected sets in a database.

Reference:
E. Achtert, C. Boehm, P. Kroeger: 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

class

DeLiClu.SpatialObjectPair Encapsulates an entry in the cluster order.

Field Summary

private ClusterOrder<O,D>	clusterOrder Provides the result of the algorithm.
private Heap<D,DeLiClu.SpatialObjectPair>	heap The priority queue for the algorithm.
private KNNJoin<O,D,DeLiCluNode,DeLiCluEntry>	knnJoin Holds the knnJoin algorithm.
static OptionID	MINPTS_ID OptionID for MINPTS_PARAM
private IntParameter	MINPTS_PARAM Parameter to specify the threshold for minimum number of points within a cluster, must be an integer greater than 0.
private int	numNodes The number of nodes of the DeLiCluTree.

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

DeLiClu()
Provides the DeLiClu algorithm, adding parameter MINPTS_PARAM to the option handler additionally to parameters of super class.

Method Summary

private void	expandDirNodes(SpatialDistanceFunction<O,D> distFunction, DeLiCluNode node1, DeLiCluNode node2) Expands the specified directory nodes.
private void	expandLeafNodes(SpatialDistanceFunction<O,D> distFunction, DeLiCluNode node1, DeLiCluNode node2, KNNJoinResult<O,D> knns) Expands the specified directory nodes.
private void	expandNodes(DeLiCluTree<O> index, SpatialDistanceFunction<O,D> distFunction, DeLiClu.SpatialObjectPair nodePair, KNNJoinResult<O,D> knns) Expands the spatial nodes of the specified pair.
List<AttributeSettings>	getAttributeSettings() Calls DistanceBasedAlgorithm.getAttributeSettings() and adds to the returned attribute settings the attribute settings of the knnJoin.
Description	getDescription() Returns a description of the algorithm.
Result<O>	getResult() Returns the result of the algorithm.
private Integer	getStartObject(SpatialIndexDatabase<O,DeLiCluNode,DeLiCluEntry> database) Returns the id of the start object for the run method.
private void	reinsertExpanded(SpatialDistanceFunction<O,D> distFunction, DeLiCluTree<O> index, List<TreeIndexPathComponent<DeLiCluEntry>> path, int pos, SpatialEntry parentEntry, KNNJoinResult<O,D> knns)
private void	reinsertExpanded(SpatialDistanceFunction<O,D> distFunction, DeLiCluTree<O> index, List<TreeIndexPathComponent<DeLiCluEntry>> path, KNNJoinResult<O,D> knns) Reinserts the objects of the already expanded nodes.
protected void	runInTime(Database<O> database) The run method encapsulated in measure of runtime.
String[]	setParameters(String[] args) Calls DistanceBasedAlgorithm#setParameters(args).
private void	updateHeap(D reachability, DeLiClu.SpatialObjectPair pair) Adds the specified entry with the specified key tp the heap.

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

getDistanceFunction

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

description, isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

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.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription

Field Detail

MINPTS_ID

public static final OptionID MINPTS_ID

OptionID for MINPTS_PARAM

MINPTS_PARAM

private final IntParameter MINPTS_PARAM

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

Key: -deliclu.minpts

clusterOrder

private ClusterOrder<O extends NumberVector<O,?>,D extends Distance<D>> clusterOrder

Provides the result of the algorithm.

heap

private Heap<D extends Distance<D>,DeLiClu.SpatialObjectPair> heap

The priority queue for the algorithm.

knnJoin

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

Holds the knnJoin algorithm.

numNodes

private int numNodes

The number of nodes of the DeLiCluTree.

Constructor Detail

DeLiClu

public DeLiClu()

Provides the DeLiClu algorithm, adding parameter MINPTS_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected void runInTime(Database<O> database)
                  throws IllegalStateException

Description copied from class: AbstractAlgorithm

The run method encapsulated in measure of runtime. An extending class needs not to take care of runtime itself.

Specified by:

runInTime in class AbstractAlgorithm<O extends NumberVector<O,?>>

Parameters:

database - the database to run the algorithm on

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

See Also:

Algorithm.run(de.lmu.ifi.dbs.elki.database.Database)

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Calls DistanceBasedAlgorithm#setParameters(args). The remaining parameters and the value of parameter MINPTS_PARAM are passed to the knnJoin.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class DistanceBasedAlgorithm<O extends NumberVector<O,?>,D extends Distance<D>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

getAttributeSettings

public List<AttributeSettings> getAttributeSettings()

Calls DistanceBasedAlgorithm.getAttributeSettings() and adds to the returned attribute settings the attribute settings of the knnJoin.

Specified by:

getAttributeSettings in interface Parameterizable

Overrides:

getAttributeSettings in class DistanceBasedAlgorithm<O extends NumberVector<O,?>,D extends Distance<D>>

Returns:

the setting of the attributes of the parameterizable

See Also:

Parameterizable.getAttributeSettings()

getResult

public Result<O> getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Returns:

the result of the algorithm

See Also:

Algorithm.getResult()

getStartObject

private Integer getStartObject(SpatialIndexDatabase<O,DeLiCluNode,DeLiCluEntry> database)

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

Parameters:

database - the database storing the objects

Returns:

the id of the start object for the run method

updateHeap

private void updateHeap(D reachability,
                        DeLiClu.SpatialObjectPair pair)

Adds the specified entry with the specified key tp the heap. If the entry's object is already in the heap, it will only be updated.

Parameters:

reachability - the reachability of the entry's object

pair - the entry to be added

expandNodes

private void expandNodes(DeLiCluTree<O> index,
                         SpatialDistanceFunction<O,D> distFunction,
                         DeLiClu.SpatialObjectPair nodePair,
                         KNNJoinResult<O,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(SpatialDistanceFunction<O,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(SpatialDistanceFunction<O,D> distFunction,
                             DeLiCluNode node1,
                             DeLiCluNode node2,
                             KNNJoinResult<O,D> knns)

Expands the specified directory 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(SpatialDistanceFunction<O,D> distFunction,
                              DeLiCluTree<O> index,
                              List<TreeIndexPathComponent<DeLiCluEntry>> path,
                              KNNJoinResult<O,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(SpatialDistanceFunction<O,D> distFunction,
                              DeLiCluTree<O> index,
                              List<TreeIndexPathComponent<DeLiCluEntry>> path,
                              int pos,
                              SpatialEntry parentEntry,
                              KNNJoinResult<O,D> knns)