Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
              extended by de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,ClusterOrderResult<D>>
                  extended by 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,ClusterOrderResult<D>>, Parameterizable

public class DeLiClu<O extends NumberVector<O,?>,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D,ClusterOrderResult<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.

Author:
Elke Achtert

Nested Class Summary
 class DeLiClu.SpatialObjectPair
          Encapsulates an entry in the cluster order.
 
Field Summary
private  ClusterOrderResult<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.
protected  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, logger
 
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, AnnotationResult<KNNList<D>> knns)
          Expands the specified directory nodes.
private  void expandNodes(DeLiCluTree<O> index, SpatialDistanceFunction<O,D> distFunction, DeLiClu.SpatialObjectPair nodePair, AnnotationResult<KNNList<D>> knns)
          Expands the spatial nodes of the specified pair.
 Description getDescription()
          Returns a description of the algorithm.
 ClusterOrderResult<D> 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, AnnotationResult<KNNList<D>> knns)
          Reinserts the objects of the already expanded nodes.
private  void reinsertExpanded(SpatialDistanceFunction<O,D> distFunction, DeLiCluTree<O> index, List<TreeIndexPathComponent<DeLiCluEntry>> path, int pos, SpatialEntry parentEntry, AnnotationResult<KNNList<D>> knns)
           
protected  ClusterOrderResult<D> runInTime(Database<O> database)
          Performs the DeLiClu algorithm on the given database.
 List<String> setParameters(List<String> args)
          Calls the super method.
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
isTime, isVerbose, run, setTime, setVerbose
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, 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, collectOptions, getParameters, shortDescription
 

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

protected 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 ClusterOrderResult<D> runInTime(Database<O> database)
                                                       throws IllegalStateException
Performs the DeLiClu algorithm on the given database.

Specified by:
runInTime in class AbstractAlgorithm<O extends NumberVector<O,?>,ClusterOrderResult<D extends Distance<D>>>
Parameters:
database - the database to run the algorithm on
Returns:
the Result computed by this algorithm
Throws:
IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

getDescription

public Description getDescription()
Description copied from interface: Algorithm
Returns a description of the algorithm.

Returns:
a description of the algorithm

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException
Calls the super method. 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>,ClusterOrderResult<D extends Distance<D>>>
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

getResult

public ClusterOrderResult<D> getResult()
Description copied from interface: Algorithm
Returns the result of the algorithm.

Returns:
the result of the algorithm

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,
                         AnnotationResult<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(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,
                             AnnotationResult<KNNList<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,
                              AnnotationResult<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(SpatialDistanceFunction<O,D> distFunction,
                              DeLiCluTree<O> index,
                              List<TreeIndexPathComponent<DeLiCluEntry>> path,
                              int pos,
                              SpatialEntry parentEntry,
                              AnnotationResult<KNNList<D>> knns)

Release 0.2 (2009-07-06_1820)