de.lmu.ifi.dbs.elki.algorithm.clustering.correlation
Class ERiC<V extends RealVector<V,?>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<V,Clustering<CorrelationModel<V>>>
              de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.ERiC<V>

Type Parameters:

V - the type of Realvector handled by this Algorithm

All Implemented Interfaces:

Algorithm<V,Clustering<CorrelationModel<V>>>, ClusteringAlgorithm<Clustering<CorrelationModel<V>>,V>, Parameterizable

public class ERiC<V extends RealVector<V,?>>
extends AbstractAlgorithm<V,Clustering<CorrelationModel<V>>>
implements ClusteringAlgorithm<Clustering<CorrelationModel<V>>,V>

Performs correlation clustering on the data partitioned according to local correlation dimensionality and builds a hierarchy of correlation clusters that allows multiple inheritance from the clustering result.

Reference: E. Achtert, C. Böhm, H.-P. Kriegel, P. Kröger, and A. Zimek: On Exploring Complex Relationships of Correlation Clusters.
In Proc. 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), Banff, Canada, 2007.

Author:

Elke Achtert

Field Summary

private COPAC<V>	copacAlgorithm The COPAC clustering algorithm.
private Clustering<CorrelationModel<V>>	result Holds the result.

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

ERiC()
Performs the COPAC algorithm on the data and builds a hierarchy of correlation clusters that allows multiple inheritance from the clustering result.

Method Summary

private void	buildHierarchy(SortedMap<Integer,List<Cluster<CorrelationModel<V>>>> clusterMap)
private SortedMap<Integer,List<Cluster<CorrelationModel<V>>>>	extractCorrelationClusters(Database<V> database, int dimensionality) Extracts the correlation clusters and noise from the copac result and returns a mapping of correlation dimension to maps of clusters within this correlation dimension.
Description	getDescription() Returns a description of the algorithm.
Clustering<CorrelationModel<V>>	getResult() Returns the result of the algorithm.
private boolean	isParent(ERiCDistanceFunction<V,?> distanceFunction, Cluster<CorrelationModel<V>> parent, List<Cluster<CorrelationModel<V>>> children) Returns true, if the specified parent cluster is a parent of one child of the children clusters.
private ArrayList<String>	pcaParameters(int correlationDimension) Returns the parameters for the PCA for the specified correlation dimension.
protected Clustering<CorrelationModel<V>>	runInTime(Database<V> database) Performs the ERiC algorithm on the given database.
List<String>	setParameters(List<String> args) Calls the super method and passes remaining parameters to the copacAlgorithm.

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.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

Field Detail

copacAlgorithm

private COPAC<V extends RealVector<V,?>> copacAlgorithm

The COPAC clustering algorithm.

result

private Clustering<CorrelationModel<V extends RealVector<V,?>>> result

Holds the result.

Constructor Detail

ERiC

public ERiC()

Performs the COPAC algorithm on the data and builds a hierarchy of correlation clusters that allows multiple inheritance from the clustering result.

Method Detail

runInTime

protected Clustering<CorrelationModel<V>> runInTime(Database<V> database)
                                                                     throws IllegalStateException

Performs the ERiC algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<V extends RealVector<V,?>,Clustering<CorrelationModel<V extends RealVector<V,?>>>>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

getResult

public Clustering<CorrelationModel<V>> getResult()

Returns the result of the algorithm.

Specified by:

getResult in interface Algorithm<V extends RealVector<V,?>,Clustering<CorrelationModel<V extends RealVector<V,?>>>>

Specified by:

getResult in interface ClusteringAlgorithm<Clustering<CorrelationModel<V extends RealVector<V,?>>>,V extends RealVector<V,?>>

Returns:

the result of the algorithm

getDescription

public Description getDescription()

Returns a description of the algorithm.

Specified by:

getDescription in interface Algorithm<V extends RealVector<V,?>,Clustering<CorrelationModel<V extends RealVector<V,?>>>>

Returns:

a description of the algorithm

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException

Calls the super method and passes remaining parameters to the copacAlgorithm.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class AbstractAlgorithm<V extends RealVector<V,?>,Clustering<CorrelationModel<V extends RealVector<V,?>>>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

a list containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

extractCorrelationClusters

private SortedMap<Integer,List<Cluster<CorrelationModel<V>>>> extractCorrelationClusters(Database<V> database,
                                                                                         int dimensionality)

Extracts the correlation clusters and noise from the copac result and returns a mapping of correlation dimension to maps of clusters within this correlation dimension. Each cluster is defined by the basis vectors defining the subspace in which the cluster appears.

Parameters:

database - the database containing the objects

dimensionality - the dimensionality of the feature space

Returns:

a mapping of correlation dimension to maps of clusters

pcaParameters

private ArrayList<String> pcaParameters(int correlationDimension)

Returns the parameters for the PCA for the specified correlation dimension.

Parameters:

correlationDimension - the correlation dimension

Returns:

the parameters for the PCA for the specified correlation dimension

buildHierarchy

private void buildHierarchy(SortedMap<Integer,List<Cluster<CorrelationModel<V>>>> clusterMap)
                     throws IllegalStateException

Throws:

IllegalStateException

isParent

private boolean isParent(ERiCDistanceFunction<V,?> distanceFunction,
                         Cluster<CorrelationModel<V>> parent,
                         List<Cluster<CorrelationModel<V>>> children)

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

Parameters:

distanceFunction - the distance function for distance computation between the clusters

parent - the parent to be tested

children - the list of children to be tested

Returns:

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