Class HDBSCANLinearMemory<O>
- java.lang.Object
-
- elki.clustering.hierarchical.AbstractHDBSCAN<O>
-
- elki.clustering.hierarchical.HDBSCANLinearMemory<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Algorithm
,HierarchicalClusteringAlgorithm
@Title("HDBSCAN: Hierarchical Density-Based Spatial Clustering of Applications with Noise") @Description("Density-Based Clustering Based on Hierarchical Density Estimates") @Reference(authors="R. J. G. B. Campello, D. Moulavi, J. Sander", title="Density-Based Clustering Based on Hierarchical Density Estimates", booktitle="Pacific-Asia Conf. Advances in Knowledge Discovery and Data Mining (PAKDD)", url="https://doi.org/10.1007/978-3-642-37456-2_14", bibkey="DBLP:conf/pakdd/CampelloMS13") public class HDBSCANLinearMemory<O> extends AbstractHDBSCAN<O> implements HierarchicalClusteringAlgorithm
Linear memory implementation of HDBSCAN clustering.By not building a distance matrix, we can reduce memory usage to linear memory only; but at the cost of roughly double the runtime (unless using indexes) as we first need to compute all kNN distances (for core sizes), then recompute distances when building the spanning tree.
This implementation follows the HDBSCAN publication more closely than
SLINKHDBSCANLinearMemory
, by computing the minimum spanning tree using Prim's algorithm (instead of SLINK; although the two are remarkably similar). In order to produce the preferred internal format of hierarchical clusterings (the compact pointer representation introduced inSLINK
) we have to perform a postprocessing conversion.This implementation does not include the cluster extraction discussed as Step 4, which is provided in a separate step. For this reason, we also do not include self-edges.
Reference:
R. J. G. B. Campello, D. Moulavi, J. Sander
Density-Based Clustering Based on Hierarchical Density Estimates
Pacific-Asia Conf. Advances in Knowledge Discovery and Data Mining (PAKDD)- Since:
- 0.7.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.clustering.hierarchical.AbstractHDBSCAN
AbstractHDBSCAN.HDBSCANAdapter, AbstractHDBSCAN.HeapMSTCollector
-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description private static Logging
LOG
Class logger.-
Fields inherited from class elki.clustering.hierarchical.AbstractHDBSCAN
distance, minPts
-
-
Constructor Summary
Constructors Constructor Description HDBSCANLinearMemory(Distance<? super O> distance, int minPts)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.protected Logging
getLogger()
Get the (STATIC) logger for this class.ClusterDensityMergeHistory
run(Relation<O> relation)
Run the algorithm-
Methods inherited from class elki.clustering.hierarchical.AbstractHDBSCAN
computeCoreDists, convertToMergeList
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.clustering.hierarchical.HierarchicalClusteringAlgorithm
autorun
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger.
-
-
Method Detail
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Overrides:
getInputTypeRestriction
in classAbstractHDBSCAN<O>
- Returns:
- Type restriction
-
run
public ClusterDensityMergeHistory run(Relation<O> relation)
Run the algorithm- Parameters:
relation
- Relation- Returns:
- Clustering hierarchy
-
getLogger
protected Logging getLogger()
Description copied from class:AbstractHDBSCAN
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classAbstractHDBSCAN<O>
- Returns:
- the static logger
-
-