de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction

Class HDBSCANHierarchyExtraction

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.HDBSCANHierarchyExtraction

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<DendrogramModel>>

@Reference(authors="R. J. G. B. Campello, D. Moulavi, and J. Sander",
           title="Density-Based Clustering Based on Hierarchical Density Estimates",
           booktitle="Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD",
           url="http://dx.doi.org/10.1007/978-3-642-37456-2_14")
public class HDBSCANHierarchyExtraction
extends Object
implements ClusteringAlgorithm<Clustering<DendrogramModel>>

Extraction of simplified cluster hierarchies, as proposed in HDBSCAN. In contrast to the authors top-down approach, we use a bottom-up approach based on the more efficient pointer representation introduced in SLINK. In particular, it can also be used to extract a hierarchy from a hierarchical agglomerative clustering. Reference:

R. J. G. B. Campello, D. Moulavi, and J. Sander
Density-Based Clustering Based on Hierarchical Density Estimates
Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD

Note: some of the code is rather complex because we delay the creation of one-element clusters to reduce garbage collection overhead.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HDBSCANHierarchyExtraction.Parameterizer Parameterization class.
protected static class	HDBSCANHierarchyExtraction.TempCluster Temporary cluster.

Field Summary

Fields

Modifier and Type	Field and Description
private HierarchicalClusteringAlgorithm	algorithm Clustering algorithm to run to obtain the hierarchy.
private boolean	hierarchical Return a hierarchical result.
private static Logging	LOG Class logger.
private int	minClSize Minimum cluster size.

Constructor Summary

Constructors

Constructor and Description
HDBSCANHierarchyExtraction(HierarchicalClusteringAlgorithm algorithm, int minClSize, boolean hierarchical) Constructor.

Method Summary

Modifier and Type	Method and Description
private Clustering<DendrogramModel>	extractClusters(DBIDs ids, DBIDDataStore pi, DoubleDataStore lambda, DoubleDataStore coredist) Extract all clusters from the pi-lambda-representation.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
private boolean	isSpurious(HDBSCANHierarchyExtraction.TempCluster clus, boolean isCore) Spurious, also for non-materialized clusters.
Clustering<DendrogramModel>	run(Database database) Runs the algorithm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Class logger.

minClSize

private int minClSize

Minimum cluster size.

algorithm

private HierarchicalClusteringAlgorithm algorithm

Clustering algorithm to run to obtain the hierarchy.

hierarchical

private boolean hierarchical

Return a hierarchical result.

Constructor Detail

HDBSCANHierarchyExtraction

public HDBSCANHierarchyExtraction(HierarchicalClusteringAlgorithm algorithm,
                                  int minClSize,
                                  boolean hierarchical)

Constructor.

Parameters:

algorithm - Algorithm to run

minClSize - Minimum cluster size

hierarchical - Produce a hierarchical result

Method Detail

run

public Clustering<DendrogramModel> run(Database database)

Description copied from interface: Algorithm

Runs the algorithm.

Specified by:

run in interface Algorithm

Specified by:

run in interface ClusteringAlgorithm<Clustering<DendrogramModel>>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

extractClusters

private Clustering<DendrogramModel> extractClusters(DBIDs ids,
                                                    DBIDDataStore pi,
                                                    DoubleDataStore lambda,
                                                    DoubleDataStore coredist)

Extract all clusters from the pi-lambda-representation.

Parameters:

ids - Object ids to process

pi - Pi store

lambda - Lambda store

coredist - Core distances

Returns:

Hierarchical clustering

isSpurious

private boolean isSpurious(HDBSCANHierarchyExtraction.TempCluster clus,
                           boolean isCore)

Spurious, also for non-materialized clusters.

Parameters:

clus - Cluster, may be null for 1-element clusters.

isCore - Core property

Returns:

true if spurious.

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction