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

Class PointerHierarchyRepresentationResult

java.lang.Object

de.lmu.ifi.dbs.elki.result.AbstractHierarchicalResult

de.lmu.ifi.dbs.elki.result.BasicResult

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

All Implemented Interfaces:

HierarchicalResult, Result

Direct Known Subclasses:

PointerDensityHierarchyRepresentationResult, PointerPrototypeHierarchyRepresentationResult

public class PointerHierarchyRepresentationResult
extends BasicResult

The pointer representation of a hierarchical clustering. Each object is represented by a parent object and the distance at which it joins the parent objects cluster. This is a rather compact and bottom-up representation of clusters, the classes CutDendrogramByNumberOfClusters and CutDendrogramByHeight. can be used to extract partitions from this graph.

This class can also compute dendrogram positions, but using a faster algorithm than the one proposed by Sibson 1971, using only O(n log n) time due to sorting, but using an additional temporary array.

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	PointerHierarchyRepresentationResult.Sorter Class for generating / optimizing the merge order.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) DBIDs	ids The DBIDs in this result.
(package private) boolean	isSquared Flag for squared distances.
(package private) IntegerDataStore	mergeOrder Merge order, useful for non-monotonous hierarchies.
(package private) DBIDDataStore	parent The parent DBID relation.
(package private) DoubleDataStore	parentDistance Distance to the parent object.
(package private) IntegerDataStore	positions Position storage, computed on demand.

Constructor Summary

Constructors

Constructor and Description
PointerHierarchyRepresentationResult(DBIDs ids, DBIDDataStore parent, DoubleDataStore parentDistance, boolean isSquared) Constructor.
PointerHierarchyRepresentationResult(DBIDs ids, DBIDDataStore parent, DoubleDataStore parentDistance, boolean isSquared, IntegerDataStore mergeOrder) Constructor.

Method Summary

Modifier and Type	Method and Description
private WritableDoubleDataStore	computeMaxHeight() Compute the maximum height of nodes.
private WritableIntegerDataStore	computeSubtreeSizes(DBIDs order) Compute the size of all subtrees.
DBIDs	getDBIDs() Get the clustered DBIDs.
DoubleDataStore	getParentDistanceStore() Get the distance to the parent.
DBIDDataStore	getParentStore() Get the parent DBID relation.
IntegerDataStore	getPositions() Get / compute the positions.
boolean	isSquared() Get the flag for squared distances.
ArrayDBIDs	topologicalSort() Topological sort the object IDs.

Methods inherited from class de.lmu.ifi.dbs.elki.result.BasicResult

getLongName, getShortName

Methods inherited from class de.lmu.ifi.dbs.elki.result.AbstractHierarchicalResult

addChildResult, getHierarchy, setHierarchy

Methods inherited from class java.lang.Object

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

Field Detail

ids

DBIDs ids

The DBIDs in this result.

parent

DBIDDataStore parent

The parent DBID relation.

parentDistance

DoubleDataStore parentDistance

Distance to the parent object.

positions

IntegerDataStore positions

Position storage, computed on demand.

mergeOrder

IntegerDataStore mergeOrder

Merge order, useful for non-monotonous hierarchies.

isSquared

boolean isSquared

Flag for squared distances.

Constructor Detail

PointerHierarchyRepresentationResult

public PointerHierarchyRepresentationResult(DBIDs ids,
                                            DBIDDataStore parent,
                                            DoubleDataStore parentDistance,
                                            boolean isSquared)

Constructor.

Parameters:

ids - IDs processed.

parent - Parent pointer.

parentDistance - Distance to parent.

isSquared - Flag to indicate squared distances

PointerHierarchyRepresentationResult

public PointerHierarchyRepresentationResult(DBIDs ids,
                                            DBIDDataStore parent,
                                            DoubleDataStore parentDistance,
                                            boolean isSquared,
                                            IntegerDataStore mergeOrder)

Constructor.

Parameters:

ids - IDs processed.

parent - Parent pointer.

parentDistance - Distance to parent.

isSquared - Flag to indicate squared distances

mergeOrder - Order in which to execute merges

Method Detail

getDBIDs

public DBIDs getDBIDs()

Get the clustered DBIDs.

Returns:

DBIDs

getParentStore

public DBIDDataStore getParentStore()

Get the parent DBID relation.

Returns:

Parent relation.

getParentDistanceStore

public DoubleDataStore getParentDistanceStore()

Get the distance to the parent.

Returns:

Parent distance.

getPositions

public IntegerDataStore getPositions()

Get / compute the positions.

Returns:

Dendrogram positions

isSquared

public boolean isSquared()

Get the flag for squared distances.

Returns:

true if squared distances are used.

computeSubtreeSizes

private WritableIntegerDataStore computeSubtreeSizes(DBIDs order)

Compute the size of all subtrees.

Parameters:

order - Object order

Returns:

Subtree sizes

computeMaxHeight

private WritableDoubleDataStore computeMaxHeight()

Compute the maximum height of nodes. This is necessary, because some linkages may sometimes yield anomalies, where d(a+b,c) < min(d(a,c), d(b,c)).

Returns:

Maximum height.

topologicalSort

public ArrayDBIDs topologicalSort()

Topological sort the object IDs. Even when we have this predefined merge order, it may be sub-optimal. Such cases arise for example when using NNChain with single-link, as it does not guarantee to discover merges in ascending order. Therefore, we employ the following logic: We process merges in merge order, and note the maximum height of the subtree. We then order points by this maximum height, then by their merge order.

Returns:

Sorted object ids.