|
|
|||||||||||||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object de.lmu.ifi.dbs.elki.logging.AbstractLoggable de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<ParameterizationFunction,Clustering<Model>> de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.CASH
@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
Provides the CASH algorithm, an 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
Field Summary | |
---|---|
private boolean |
adjust
Holds the value of ADJUST_FLAG . |
private Flag |
ADJUST_FLAG
Flag to indicate that an adjustment of the applied heuristic for choosing an interval is performed after an interval is selected. |
static OptionID |
ADJUST_ID
OptionID for ADJUST_FLAG |
private Database<ParameterizationFunction> |
database
The database holding the objects. |
private double |
jitter
Holds the value of JITTER_PARAM . |
static OptionID |
JITTER_ID
OptionID for JITTER_PARAM |
private DoubleParameter |
JITTER_PARAM
Parameter to specify the maximum jitter for distance values, must be a double greater than 0. |
private int |
maxLevel
Holds the value of MAXLEVEL_PARAM . |
static OptionID |
MAXLEVEL_ID
OptionID for MAXLEVEL_PARAM . |
private IntParameter |
MAXLEVEL_PARAM
Parameter to specify the maximum level for splitting the hypercube, must be an integer greater than 0. |
private int |
minDim
Holds the value of MINDIM_PARAM . |
static OptionID |
MINDIM_ID
OptionID for MINDIM_PARAM |
private IntParameter |
MINDIM_PARAM
Parameter to specify the minimum dimensionality of the subspaces to be found, must be an integer greater than 0. |
private int |
minPts
Holds the value of MINPTS_PARAM . |
static OptionID |
MINPTS_ID
OptionID for MINPTS_PARAM |
private IntParameter |
MINPTS_PARAM
Parameter to specify the threshold for minimum number of points in a cluster, must be an integer greater than 0. |
private int |
noiseDim
Holds the dimensionality for noise. |
private Set<Integer> |
processedIDs
Holds a set of processed ids. |
Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable |
---|
debug, logger |
Constructor Summary | |
---|---|
CASH(Parameterization config)
Constructor, adhering to Parameterizable |
Method Summary | |
---|---|
private Database<ParameterizationFunction> |
buildDB(int dim,
Matrix basis,
Set<Integer> ids,
Database<ParameterizationFunction> database)
Builds a dim-1 dimensional database where the objects are projected into the specified subspace. |
private Database<DoubleVector> |
buildDerivatorDB(Database<ParameterizationFunction> database,
CASHInterval interval)
Builds a database for the derivator consisting of the ids in the specified interval. |
private Database<DoubleVector> |
buildDerivatorDB(Database<ParameterizationFunction> database,
Set<Integer> 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(Database<ParameterizationFunction> database,
int dimensionality)
Determines the minimum and maximum function value of all parameterization functions stored in the specified database. |
private CASHInterval |
determineNextIntervalAtMaxLevel(DefaultHeap<Integer,CASHInterval> heap)
Determines the next ''best'' interval at maximum level, i.e. the next interval containing the most unprocessed objects. |
private CASHInterval |
doDetermineNextIntervalAtMaxLevel(DefaultHeap<Integer,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(Database<ParameterizationFunction> database,
FiniteProgress progress)
Runs the CASH algorithm on the specified database, this method is recursively called until only noise is left. |
private Set<Integer> |
getDatabaseIDs(Database<ParameterizationFunction> database)
Returns the set of ids belonging to the specified database. |
private void |
initHeap(DefaultHeap<Integer,CASHInterval> heap,
Database<ParameterizationFunction> database,
int dim,
Set<Integer> ids)
Initializes the heap with the root intervals. |
private ParameterizationFunction |
project(Matrix basis,
ParameterizationFunction f)
Projects the specified parameterization function into the subspace described by the given basis. |
private Matrix |
runDerivator(Database<ParameterizationFunction> database,
int dim,
CASHInterval interval,
Set<Integer> 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(Database<ParameterizationFunction> database,
int dimensionality,
Set<Integer> 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. |
protected Clustering<Model> |
runInTime(Database<ParameterizationFunction> database)
Performs the CASH algorithm on the given database. |
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 |
---|
isTime, isVerbose, run, setTime, setVerbose |
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable |
---|
debugFine, debugFiner, debugFinest, exception, progress, verbose, warning |
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 |
Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.Algorithm |
---|
setTime, setVerbose |
Field Detail |
---|
public static final OptionID MINPTS_ID
MINPTS_PARAM
private final IntParameter MINPTS_PARAM
Key: -cash.minpts
private int minPts
MINPTS_PARAM
.
public static final OptionID MAXLEVEL_ID
MAXLEVEL_PARAM
.
private final IntParameter MAXLEVEL_PARAM
Key: -cash.maxlevel
private int maxLevel
MAXLEVEL_PARAM
.
public static final OptionID MINDIM_ID
MINDIM_PARAM
private final IntParameter MINDIM_PARAM
Default value: 1
Key: -cash.mindim
private int minDim
MINDIM_PARAM
.
public static final OptionID JITTER_ID
JITTER_PARAM
private final DoubleParameter JITTER_PARAM
Key: -cash.jitter
private double jitter
JITTER_PARAM
.
public static final OptionID ADJUST_ID
ADJUST_FLAG
private final Flag ADJUST_FLAG
Key: -cash.adjust
private boolean adjust
ADJUST_FLAG
.
private int noiseDim
private Set<Integer> processedIDs
private Database<ParameterizationFunction> database
Constructor Detail |
---|
public CASH(Parameterization config)
Parameterizable
config
- ParameterizationMethod Detail |
---|
protected Clustering<Model> runInTime(Database<ParameterizationFunction> database) throws IllegalStateException
runInTime
in class AbstractAlgorithm<ParameterizationFunction,Clustering<Model>>
database
- the database to run the algorithm on
IllegalStateException
- if the algorithm has not been initialized
properly (e.g. the setParameters(String[]) method has been failed
to be called).private Clustering<Model> doRun(Database<ParameterizationFunction> database, FiniteProgress progress) throws UnableToComplyException, ParameterException, NonNumericFeaturesException
database
- the current database to run the CASH algorithm onprogress
- the progress object for verbose messages
UnableToComplyException
- if an error according to the database
occurs
ParameterException
- if the parameter setting is wrong
NonNumericFeaturesException
- if non numeric feature vectors are usedprivate void initHeap(DefaultHeap<Integer,CASHInterval> heap, Database<ParameterizationFunction> database, int dim, Set<Integer> ids)
heap
- the heap to be initializeddatabase
- the database storing the paramterization functionsdim
- the dimensionality of the databaseids
- the ids of the databaseprivate Database<ParameterizationFunction> buildDB(int dim, Matrix basis, Set<Integer> ids, Database<ParameterizationFunction> database) throws UnableToComplyException
dim
- the dimensionality of the databasebasis
- the basis defining the subspaceids
- the ids for the new databasedatabase
- the database storing the parameterization functions
UnableToComplyException
- if an error according to the database
occursprivate ParameterizationFunction project(Matrix basis, ParameterizationFunction f)
basis
- the basis defining he subspacef
- the parameterization function to be projected
private Matrix determineBasis(double[] alpha)
alpha
- the alpha values
private double sinusProduct(int start, int end, double[] alpha)
start
- the index to startend
- the index to endalpha
- the array of angles
private CASHInterval determineNextIntervalAtMaxLevel(DefaultHeap<Integer,CASHInterval> heap)
heap
- the heap storing the intervals
private CASHInterval doDetermineNextIntervalAtMaxLevel(DefaultHeap<Integer,CASHInterval> heap)
heap
- the heap storing the intervals
private Set<Integer> getDatabaseIDs(Database<ParameterizationFunction> database)
database
- the database containing the parameterization functions.
private double[] determineMinMaxDistance(Database<ParameterizationFunction> database, int dimensionality)
database
- the database containing the parameterization functions.dimensionality
- the dimensionality of the database
private Matrix runDerivator(Database<ParameterizationFunction> database, int dim, CASHInterval interval, Set<Integer> ids) throws UnableToComplyException, ParameterException
database
- the database containing the parameterization functionsinterval
- the interval to build the modeldim
- the dimensionality of the databaseids
- an empty set to assign the ids
UnableToComplyException
- if an error according to the database
occurs
ParameterException
- if the parameter setting is wrongprivate Database<DoubleVector> buildDerivatorDB(Database<ParameterizationFunction> database, CASHInterval interval) throws UnableToComplyException
database
- the database storing the parameterization functionsinterval
- the interval to build the database from
UnableToComplyException
- if an error according to the database
occursprivate LinearEquationSystem runDerivator(Database<ParameterizationFunction> database, int dimensionality, Set<Integer> ids)
database
- the database containing the parameterization functionsids
- the ids to build the modeldimensionality
- the dimensionality of the subspace
private Database<DoubleVector> buildDerivatorDB(Database<ParameterizationFunction> database, Set<Integer> ids) throws UnableToComplyException
database
- the database storing the parameterization functionsids
- the ids to build the database from
UnableToComplyException
- if initialization of the database is not
possible
|
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |