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

Class CASH<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.CASH<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<Model>>

@Title(value="CASH: Robust clustering in arbitrarily oriented subspaces")
@Description(value="Subspace clustering algorithm based on the Hough transform.")
@Reference(authors="E. Achtert, C. B\u00f6hm, J. David, P. Kr\u00f6ger, A. Zimek",
           title="Robust clustering in arbitraily oriented subspaces",
           booktitle="Proc. 8th SIAM Int. Conf. on Data Mining (SDM\'08), Atlanta, GA, 2008",
           url="http://www.siam.org/proceedings/datamining/2008/dm08_69_AchtertBoehmDavidKroegerZimek.pdf")
public class CASH<V extends NumberVector>
extends AbstractAlgorithm<Clustering<Model>>
implements ClusteringAlgorithm<Clustering<Model>>

The CASH algorithm is a subspace clustering algorithm based on the Hough transform. Reference:

E. Achtert, C. Böhm, J. David, P. Kröger, A. Zimek:
Robust clustering in arbitrarily oriented subspaces.
In Proc. 8th SIAM Int. Conf. on Data Mining (SDM'08), Atlanta, GA, 2008

Since:

0.2

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CASH.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	adjust Apply adjustment heuristic for interval choosing.
private Relation<ParameterizationFunction>	fulldatabase The entire relation.
protected double	jitter Maximum jitter for distance values.
private static Logging	LOG The logger for this class.
protected int	maxLevel Maximum level for splitting the hypercube.
protected int	minDim Minimum dimensionality of the subspaces to be found
protected int	minPts Threshold for minimum number of points in a cluster
private int	noiseDim Holds the dimensionality for noise.
private ModifiableDBIDs	processedIDs Holds a set of processed ids.

Constructor Summary

Constructors

Constructor and Description
CASH(int minPts, int maxLevel, int minDim, double jitter, boolean adjust) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private MaterializedRelation<ParameterizationFunction>	buildDB(int dim, Matrix basis, DBIDs ids, Relation<ParameterizationFunction> relation) Builds a dim-1 dimensional database where the objects are projected into the specified subspace.
private Database	buildDerivatorDB(Relation<ParameterizationFunction> relation, CASHInterval interval) Builds a database for the derivator consisting of the ids in the specified interval.
private Database	buildDerivatorDB(Relation<ParameterizationFunction> relation, DBIDs ids) Builds a database for the derivator consisting of the ids in the specified interval.
private Matrix	determineBasis(double[] alpha) Determines a basis defining a subspace described by the specified alpha values.
private double[]	determineMinMaxDistance(Relation<ParameterizationFunction> relation, int dimensionality) Determines the minimum and maximum function value of all parameterization functions stored in the specified database.
private CASHInterval	determineNextIntervalAtMaxLevel(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap) Determines the next ''best'' interval at maximum level, i.e. the next interval containing the most unprocessed objects.
private static int	dimensionality(Relation<ParameterizationFunction> relation) Get the dimensionality of a vector field.
private CASHInterval	doDetermineNextIntervalAtMaxLevel(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap) Recursive helper method to determine the next ''best'' interval at maximum level, i.e. the next interval containing the most unprocessed objects
private Clustering<Model>	doRun(Relation<ParameterizationFunction> relation, FiniteProgress progress) Runs the CASH algorithm on the specified database, this method is recursively called until only noise is left.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private void	initHeap(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap, Relation<ParameterizationFunction> relation, int dim, DBIDs ids) Initializes the heap with the root intervals.
private Relation<ParameterizationFunction>	preprocess(Database db, Relation<V> vrel) Preprocess the dataset, precomputing the parameterization functions.
private ParameterizationFunction	project(Matrix basis, ParameterizationFunction f) Projects the specified parameterization function into the subspace described by the given basis.
Clustering<Model>	run(Database database, Relation<V> vrel) Run CASH on the relation.
private Matrix	runDerivator(Relation<ParameterizationFunction> relation, int dim, CASHInterval interval, ModifiableDBIDs ids) Runs the derivator on the specified interval and assigns all points having a distance less then the standard deviation of the derivator model to the model to this model.
private LinearEquationSystem	runDerivator(Relation<ParameterizationFunction> relation, int dimensionality, DBIDs ids) Runs the derivator on the specified interval and assigns all points having a distance less then the standard deviation of the derivator model to the model to this model.
private double	sinusProduct(int start, int end, double[] alpha) Computes the product of all sinus values of the specified angles from start to end index.

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.

minPts

protected int minPts

Threshold for minimum number of points in a cluster

maxLevel

protected int maxLevel

Maximum level for splitting the hypercube.

minDim

protected int minDim

Minimum dimensionality of the subspaces to be found

jitter

protected double jitter

Maximum jitter for distance values.

adjust

protected boolean adjust

Apply adjustment heuristic for interval choosing.

noiseDim

private int noiseDim

Holds the dimensionality for noise.

processedIDs

private ModifiableDBIDs processedIDs

Holds a set of processed ids.

fulldatabase

private Relation<ParameterizationFunction> fulldatabase

The entire relation.

Constructor Detail

CASH

public CASH(int minPts,
    int maxLevel,
    int minDim,
    double jitter,
    boolean adjust)

Constructor.

Parameters:

minPts - MinPts parameter

maxLevel - Maximum level

minDim - Minimum dimensionality

jitter - Jitter

adjust - Adjust

Method Detail

run

public Clustering<Model> run(Database database,
                    Relation<V> vrel)

Run CASH on the relation.

Parameters:

database - Database

vrel - Relation

Returns:

Clustering result

preprocess

private Relation<ParameterizationFunction> preprocess(Database db,
                                            Relation<V> vrel)

Preprocess the dataset, precomputing the parameterization functions.

Parameters:

db - Database

vrel - Vector relation

Returns:

Preprocessed relation

doRun

private Clustering<Model> doRun(Relation<ParameterizationFunction> relation,
                      FiniteProgress progress)

Runs the CASH algorithm on the specified database, this method is recursively called until only noise is left.

Parameters:

relation - the Relation to run the CASH algorithm on

progress - the progress object for verbose messages

Returns:

a mapping of subspace dimensionalities to clusters

dimensionality

private static int dimensionality(Relation<ParameterizationFunction> relation)

Get the dimensionality of a vector field.

Parameters:

relation - Relation

Returns:

Dimensionality

initHeap

private void initHeap(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap,
            Relation<ParameterizationFunction> relation,
            int dim,
            DBIDs ids)

Initializes the heap with the root intervals.

Parameters:

heap - the heap to be initialized

relation - the database storing the parameterization functions

dim - the dimensionality of the database

ids - the ids of the database

buildDB

private MaterializedRelation<ParameterizationFunction> buildDB(int dim,
                                                     Matrix basis,
                                                     DBIDs ids,
                                                     Relation<ParameterizationFunction> relation)

Builds a dim-1 dimensional database where the objects are projected into the specified subspace.

Parameters:

dim - the dimensionality of the database

basis - the basis defining the subspace

ids - the ids for the new database

relation - the database storing the parameterization functions

Returns:

a dim-1 dimensional database where the objects are projected into the specified subspace

project

private ParameterizationFunction project(Matrix basis,
                               ParameterizationFunction f)

Projects the specified parameterization function into the subspace described by the given basis.

Parameters:

basis - the basis defining he subspace

f - the parameterization function to be projected

Returns:

the projected parameterization function

determineBasis

private Matrix determineBasis(double[] alpha)

Determines a basis defining a subspace described by the specified alpha values.

Parameters:

alpha - the alpha values

Returns:

a basis defining a subspace described by the specified alpha values

sinusProduct

private double sinusProduct(int start,
                  int end,
                  double[] alpha)

Computes the product of all sinus values of the specified angles from start to end index.

Parameters:

start - the index to start

end - the index to end

alpha - the array of angles

Returns:

the product of all sinus values of the specified angles from start to end index

determineNextIntervalAtMaxLevel

private CASHInterval determineNextIntervalAtMaxLevel(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap)

Determines the next ''best'' interval at maximum level, i.e. the next interval containing the most unprocessed objects.

Parameters:

heap - the heap storing the intervals

Returns:

the next ''best'' interval at maximum level

doDetermineNextIntervalAtMaxLevel

private CASHInterval doDetermineNextIntervalAtMaxLevel(ObjectHeap<IntegerPriorityObject<CASHInterval>> heap)

Recursive helper method to determine the next ''best'' interval at maximum level, i.e. the next interval containing the most unprocessed objects

Parameters:

heap - the heap storing the intervals

Returns:

the next ''best'' interval at maximum level

determineMinMaxDistance

private double[] determineMinMaxDistance(Relation<ParameterizationFunction> relation,
                               int dimensionality)

Determines the minimum and maximum function value of all parameterization functions stored in the specified database.

Parameters:

relation - the database containing the parameterization functions.

dimensionality - the dimensionality of the database

Returns:

an array containing the minimum and maximum function value of all parameterization functions stored in the specified database

runDerivator

private Matrix runDerivator(Relation<ParameterizationFunction> relation,
                  int dim,
                  CASHInterval interval,
                  ModifiableDBIDs ids)

Runs the derivator on the specified interval and assigns all points having a distance less then the standard deviation of the derivator model to the model to this model.

Parameters:

relation - the database containing the parameterization functions

interval - the interval to build the model

dim - the dimensionality of the database

ids - an empty set to assign the ids

Returns:

a basis of the found subspace

buildDerivatorDB

private Database buildDerivatorDB(Relation<ParameterizationFunction> relation,
                        CASHInterval interval)

Builds a database for the derivator consisting of the ids in the specified interval.

Parameters:

relation - the database storing the parameterization functions

interval - the interval to build the database from

Returns:

a database for the derivator consisting of the ids in the specified interval

runDerivator

private LinearEquationSystem runDerivator(Relation<ParameterizationFunction> relation,
                                int dimensionality,
                                DBIDs ids)

Runs the derivator on the specified interval and assigns all points having a distance less then the standard deviation of the derivator model to the model to this model.

Parameters:

relation - the database containing the parameterization functions

ids - the ids to build the model

dimensionality - the dimensionality of the subspace

Returns:

a basis of the found subspace

buildDerivatorDB

private Database buildDerivatorDB(Relation<ParameterizationFunction> relation,
                        DBIDs ids)

Builds a database for the derivator consisting of the ids in the specified interval.

Parameters:

relation - the database storing the parameterization functions

ids - the ids to build the database from

Returns:

a database for the derivator consisting of the ids in the specified interval

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

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

Returns:

the static logger