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

Class DiSH<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<SubspaceModel>>

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.DiSH<V>

Type Parameters:

V - the type of NumberVector handled by this Algorithm

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<SubspaceModel>>, SubspaceClusteringAlgorithm<SubspaceModel>

@Title(value="DiSH: Detecting Subspace cluster Hierarchies")
 @Description(value="Algorithm to find hierarchical correlation clusters in subspaces.")
 @Reference(authors="E. Achtert, C. B\u00f6hm, H.-P. Kriegel, P. Kr\u00f6ger, I. M\u00fcller-Gorman, A. Zimek",
           title="Detection and Visualization of Subspace Cluster Hierarchies",
           booktitle="Proc. 12th International Conference on Database Systems for Advanced Applications (DASFAA), Bangkok, Thailand, 2007",
           url="http://dx.doi.org/10.1007/978-3-540-71703-4_15")
public class DiSH<V extends NumberVector>
extends AbstractAlgorithm<Clustering<SubspaceModel>>
implements SubspaceClusteringAlgorithm<SubspaceModel>

Algorithm for detecting subspace hierarchies. Reference:

E. Achtert, C. Böhm, H.-P. Kriegel, P. Kröger, I. Müller-Gorman, A. Zimek:
Detection and Visualization of Subspace Cluster Hierarchies.
In Proc. 12th International Conference on Database Systems for Advanced Applications (DASFAA), Bangkok, Thailand, 2007.

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DiSH.DiSHClusterOrder DiSH cluster order.
private class	DiSH.Instance OPTICS variant used by DiSH internally.
static class	DiSH.Parameterizer<V extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private DiSHPreferenceVectorIndex.Factory<V>	dishPreprocessor The DiSH preprocessor.
private double	epsilon Holds the value of DiSH.Parameterizer.EPSILON_ID.
private static Logging	LOG The logger for this class.
private int	mu OPTICS minPts parameter.

Constructor Summary

Constructors

Constructor and Description
DiSH(double epsilon, int mu, DiSHPreferenceVectorIndex.Factory<V> dishPreprocessor) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	buildHierarchy(Relation<V> database, Clustering<SubspaceModel> clustering, List<Cluster<SubspaceModel>> clusters, int dimensionality) Builds the cluster hierarchy.
private void	checkClusters(Relation<V> relation, gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap) Removes the clusters with size < minpts from the cluster map and adds them to their parents.
private Clustering<SubspaceModel>	computeClusters(Relation<V> database, DiSH.DiSHClusterOrder clusterOrder) Computes the hierarchical clusters according to the cluster order.
private gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>>	extractClusters(Relation<V> relation, DiSH.DiSHClusterOrder clusterOrder) Extracts the clusters from the cluster order.
private Pair<long[],ArrayModifiableDBIDs>	findParent(Relation<V> relation, Pair<long[],ArrayModifiableDBIDs> child, gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap) Returns the parent of the specified cluster
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private boolean	isParent(Relation<V> relation, Cluster<SubspaceModel> parent, Hierarchy.Iter<Cluster<SubspaceModel>> iter, int db_dim) Returns true, if the specified parent cluster is a parent of one child of the children clusters.
Clustering<SubspaceModel>	run(Database db, Relation<V> relation) Performs the DiSH algorithm on the given database.
private List<Cluster<SubspaceModel>>	sortClusters(Relation<V> relation, gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap) Returns a sorted list of the clusters w.r.t. the subspace dimensionality in descending order.
private int	subspaceDimensionality(NumberVector v1, NumberVector v2, long[] pv1, long[] pv2, long[] commonPreferenceVector) Compute the common subspace dimensionality of two vectors.
protected static double	weightedDistance(NumberVector v1, NumberVector v2, long[] weightVector) Computes the weighted distance between the two specified vectors according to the given preference vector.

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

makeParameterDistanceFunction, run

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.algorithm.clustering.ClusteringAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

epsilon

private double epsilon

Holds the value of DiSH.Parameterizer.EPSILON_ID.

dishPreprocessor

private DiSHPreferenceVectorIndex.Factory<V extends NumberVector> dishPreprocessor

The DiSH preprocessor.

mu

private int mu

OPTICS minPts parameter.

Constructor Detail

DiSH

public DiSH(double epsilon,
            int mu,
            DiSHPreferenceVectorIndex.Factory<V> dishPreprocessor)

Constructor.

Parameters:

epsilon - Epsilon value

mu - Mu parameter (minPts)

dishPreprocessor - DiSH preprocessor

Method Detail

run

public Clustering<SubspaceModel> run(Database db,
                                     Relation<V> relation)

Performs the DiSH algorithm on the given database.

Parameters:

relation - Relation to process

computeClusters

private Clustering<SubspaceModel> computeClusters(Relation<V> database,
                                                  DiSH.DiSHClusterOrder clusterOrder)

Computes the hierarchical clusters according to the cluster order.

Parameters:

database - the database holding the objects

clusterOrder - the cluster order

extractClusters

private gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> extractClusters(Relation<V> relation,
                                                                                             DiSH.DiSHClusterOrder clusterOrder)

Extracts the clusters from the cluster order.

Parameters:

relation - the database storing the objects

clusterOrder - the cluster order to extract the clusters from

Returns:

the extracted clusters

sortClusters

private List<Cluster<SubspaceModel>> sortClusters(Relation<V> relation,
                                                  gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap)

Returns a sorted list of the clusters w.r.t. the subspace dimensionality in descending order.

Parameters:

relation - the database storing the objects

clustersMap - the mapping of bits sets to clusters

Returns:

a sorted list of the clusters

checkClusters

private void checkClusters(Relation<V> relation,
                           gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap)

Removes the clusters with size < minpts from the cluster map and adds them to their parents.

Parameters:

relation - the relation storing the objects

clustersMap - the map containing the clusters

findParent

private Pair<long[],ArrayModifiableDBIDs> findParent(Relation<V> relation,
                                                     Pair<long[],ArrayModifiableDBIDs> child,
                                                     gnu.trove.map.hash.TCustomHashMap<long[],List<ArrayModifiableDBIDs>> clustersMap)

Returns the parent of the specified cluster

Parameters:

relation - the relation storing the objects

child - the child to search the parent for

clustersMap - the map containing the clusters

Returns:

the parent of the specified cluster

buildHierarchy

private void buildHierarchy(Relation<V> database,
                            Clustering<SubspaceModel> clustering,
                            List<Cluster<SubspaceModel>> clusters,
                            int dimensionality)

Builds the cluster hierarchy.

Parameters:

clustering - Clustering we process

clusters - the sorted list of clusters

dimensionality - the dimensionality of the data

database - the database containing the data objects

isParent

private boolean isParent(Relation<V> relation,
                         Cluster<SubspaceModel> parent,
                         Hierarchy.Iter<Cluster<SubspaceModel>> iter,
                         int db_dim)

Returns true, if the specified parent cluster is a parent of one child of the children clusters.

Parameters:

relation - the database containing the objects

parent - the parent to be tested

iter - the list of children to be tested

db_dim - Database dimensionality

Returns:

true, if the specified parent cluster is a parent of one child of the children clusters, false otherwise

subspaceDimensionality

private int subspaceDimensionality(NumberVector v1,
                                   NumberVector v2,
                                   long[] pv1,
                                   long[] pv2,
                                   long[] commonPreferenceVector)

Compute the common subspace dimensionality of two vectors.

Parameters:

v1 - First vector

v2 - Second vector

pv1 - First preference

pv2 - Second preference

commonPreferenceVector - Common preference

Returns:

Usually, v1.dim - commonPreference.cardinality, unless either pv1 and pv2 are a subset of the other.

weightedDistance

protected static double weightedDistance(NumberVector v1,
                                         NumberVector v2,
                                         long[] weightVector)

Computes the weighted distance between the two specified vectors according to the given preference vector.

Parameters:

v1 - the first vector

v2 - the second vector

weightVector - the preference vector

Returns:

the weighted distance between the two specified vectors according to the given preference vector

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Clustering<SubspaceModel>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<SubspaceModel>>

Returns:

the static logger