de.lmu.ifi.dbs.elki.math.dimensionsimilarity

Class MCEDimensionSimilarity

java.lang.Object

de.lmu.ifi.dbs.elki.math.dimensionsimilarity.MCEDimensionSimilarity

All Implemented Interfaces:

DimensionSimilarity<NumberVector<?>>, Parameterizable

@Reference(authors="D. Guo",
           title="Coordinating computational and visual approaches for interactive feature selection and multivariate clustering",
           booktitle="Information Visualization, 2(4)",
           url="http://dx.doi.org/10.1057/palgrave.ivs.9500053")
public class MCEDimensionSimilarity
extends Object
implements DimensionSimilarity<NumberVector<?>>

Compute dimension similarity by using a nested means discretization. Reference:

D. Guo
Coordinating computational and visual approaches for interactive feature selection and multivariate clustering
Information Visualization, 2(4), 2003.

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
static MCEDimensionSimilarity	STATIC Static instance.
static int	TARGET Desired size: 35 observations.

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	MCEDimensionSimilarity() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private ArrayList<ArrayList<DBIDs>>	buildPartitions(Relation<? extends NumberVector<?>> relation, DBIDs ids, int depth, DimensionSimilarityMatrix matrix) Calculates "index structures" for every attribute, i.e. sorts a ModifiableArray of every DBID in the database for every dimension and stores them in a list.
void	computeDimensionSimilarites(Database database, Relation<? extends NumberVector<?>> relation, DBIDs subset, DimensionSimilarityMatrix matrix) Compute the dimension similarity matrix
private void	divide(DBIDArrayIter it, double[] data, ArrayList<DBIDs> idx, int start, int end, int depth, Mean mean) Recursive call to further subdivide the array.
private double	getMCEntropy(int[][] mat, int[] psizesx, int[] psizesy, int size, int gridsize, double loggrid) Compute the MCE entropy value.
private void	intersectionMatrix(int[][] res, ArrayList<? extends DBIDs> partsx, ArrayList<? extends DBIDs> partsy, int gridsize) Intersect the two 1d grid decompositions, to obtain a 2d matrix.

Methods inherited from class java.lang.Object

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

Field Detail

STATIC

public static final MCEDimensionSimilarity STATIC

Static instance.

TARGET

public static final int TARGET

Desired size: 35 observations. While this could trivially be made parameterizable, it is a reasonable rule of thumb and not expected to have a major effect.

See Also:

Constant Field Values

Constructor Detail

MCEDimensionSimilarity

protected MCEDimensionSimilarity()

Constructor. Use static instance instead!

Method Detail

computeDimensionSimilarites

public void computeDimensionSimilarites(Database database,
                               Relation<? extends NumberVector<?>> relation,
                               DBIDs subset,
                               DimensionSimilarityMatrix matrix)

Description copied from interface: DimensionSimilarity

Compute the dimension similarity matrix

Specified by:

computeDimensionSimilarites in interface DimensionSimilarity<NumberVector<?>>

Parameters:

database - Database context

relation - Relation

subset - DBID subset (for sampling / selection)

matrix - Matrix to fill

intersectionMatrix

private void intersectionMatrix(int[][] res,
                      ArrayList<? extends DBIDs> partsx,
                      ArrayList<? extends DBIDs> partsy,
                      int gridsize)

Intersect the two 1d grid decompositions, to obtain a 2d matrix.

Parameters:

res - Output matrix to fill

partsx - Partitions in first component

partsy - Partitions in second component.

gridsize - Size of partition decomposition

getMCEntropy

private double getMCEntropy(int[][] mat,
                  int[] psizesx,
                  int[] psizesy,
                  int size,
                  int gridsize,
                  double loggrid)

Compute the MCE entropy value.

Parameters:

mat - Partition size matrix

psizesx - Partition sizes on X

psizesy - Partition sizes on Y

size - Data set size

gridsize - Size of grids

loggrid - Logarithm of grid sizes, for normalization

Returns:

MCE score.

buildPartitions

private ArrayList<ArrayList<DBIDs>> buildPartitions(Relation<? extends NumberVector<?>> relation,
                                          DBIDs ids,
                                          int depth,
                                          DimensionSimilarityMatrix matrix)

Calculates "index structures" for every attribute, i.e. sorts a ModifiableArray of every DBID in the database for every dimension and stores them in a list.

Parameters:

relation - Relation to index

ids - IDs to use

matrix - Matrix for dimension information

Returns:

List of sorted objects

divide

private void divide(DBIDArrayIter it,
          double[] data,
          ArrayList<DBIDs> idx,
          int start,
          int end,
          int depth,
          Mean mean)

Recursive call to further subdivide the array.

Parameters:

it - Iterator (will be reset!)

data - 1D data, sorted

idx - Output index

start - Interval start

end - Interval end

depth - Depth

mean - Mean working variable (will be reset!)