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

Class CLIQUESubspace<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.data.Subspace

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

Type Parameters:

V - the type of NumberVector this subspace contains

public class CLIQUESubspace<V extends NumberVector>
extends Subspace

Represents a subspace of the original data space in the CLIQUE algorithm.

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CLIQUESubspace.CoverageComparator A partial comparator for CLIQUESubspaces based on their coverage.

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.data.Subspace

Subspace.DimensionComparator

Field Summary

Fields

Modifier and Type	Field and Description
private int	coverage The coverage of this subspace, which is the number of all feature vectors that fall inside the dense units of this subspace.
private List<CLIQUEUnit<V>>	denseUnits The dense units belonging to this subspace.

Constructor Summary

Constructors

Constructor and Description
CLIQUESubspace(int dimension) Creates a new one-dimensional subspace of the original data space.
CLIQUESubspace(long[] dimensions) Creates a new k-dimensional subspace of the original data space.

Method Summary

Methods

Modifier and Type	Method and Description
void	addDenseUnit(CLIQUEUnit<V> unit) Adds the specified dense unit to this subspace.
List<Pair<Subspace,ModifiableDBIDs>>	determineClusters() Determines all clusters in this subspace by performing a depth-first search algorithm to find connected dense units.
void	dfs(CLIQUEUnit<V> unit, ModifiableDBIDs cluster, CLIQUESubspace<V> model) Depth-first search algorithm to find connected dense units in this subspace that build a cluster.
int	getCoverage() Returns the coverage of this subspace, which is the number of all feature vectors that fall inside the dense units of this subspace.
List<CLIQUEUnit<V>>	getDenseUnits()
CLIQUESubspace<V>	join(CLIQUESubspace<V> other, double all, double tau) Joins this subspace and its dense units with the specified subspace and its dense units.
CLIQUEUnit<V>	leftNeighbor(CLIQUEUnit<V> unit, int dim) Returns the left neighbor of the given unit in the specified dimension.
CLIQUEUnit<V>	rightNeighbor(CLIQUEUnit<V> unit, Integer dim) Returns the right neighbor of the given unit in the specified dimension.
String	toString(String pre) Calls the super method and adds additionally the coverage, and the dense units of this subspace.

Methods inherited from class de.lmu.ifi.dbs.elki.data.Subspace

dimensionality, dimensonsToString, dimensonsToString, equals, getDimensions, hashCode, isSubspace, join, joinLastDimensions, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

denseUnits

private List<CLIQUEUnit<V extends NumberVector>> denseUnits

The dense units belonging to this subspace.

coverage

private int coverage

The coverage of this subspace, which is the number of all feature vectors that fall inside the dense units of this subspace.

Constructor Detail

CLIQUESubspace

public CLIQUESubspace(int dimension)

Creates a new one-dimensional subspace of the original data space.

Parameters:

dimension - the dimension building this subspace

CLIQUESubspace

public CLIQUESubspace(long[] dimensions)

Creates a new k-dimensional subspace of the original data space.

Parameters:

dimensions - the dimensions building this subspace

Method Detail

addDenseUnit

public void addDenseUnit(CLIQUEUnit<V> unit)

Adds the specified dense unit to this subspace.

Parameters:

unit - the unit to be added.

determineClusters

public List<Pair<Subspace,ModifiableDBIDs>> determineClusters()

Determines all clusters in this subspace by performing a depth-first search algorithm to find connected dense units.

Returns:

the clusters in this subspace and the corresponding cluster models

dfs

public void dfs(CLIQUEUnit<V> unit,
       ModifiableDBIDs cluster,
       CLIQUESubspace<V> model)

Depth-first search algorithm to find connected dense units in this subspace that build a cluster. It starts with a unit, assigns it to a cluster and finds all units it is connected to.

Parameters:

unit - the unit

cluster - the IDs of the feature vectors of the current cluster

model - the model of the cluster

leftNeighbor

public CLIQUEUnit<V> leftNeighbor(CLIQUEUnit<V> unit,
                         int dim)

Returns the left neighbor of the given unit in the specified dimension.

Parameters:

unit - the unit to determine the left neighbor for

dim - the dimension

Returns:

the left neighbor of the given unit in the specified dimension

rightNeighbor

public CLIQUEUnit<V> rightNeighbor(CLIQUEUnit<V> unit,
                          Integer dim)

Returns the right neighbor of the given unit in the specified dimension.

Parameters:

unit - the unit to determine the right neighbor for

dim - the dimension

Returns:

the right neighbor of the given unit in the specified dimension

getCoverage

public int getCoverage()

Returns the coverage of this subspace, which is the number of all feature vectors that fall inside the dense units of this subspace.

Returns:

the coverage of this subspace

getDenseUnits

public List<CLIQUEUnit<V>> getDenseUnits()

Returns:

the denseUnits

join

public CLIQUESubspace<V> join(CLIQUESubspace<V> other,
                     double all,
                     double tau)

Joins this subspace and its dense units with the specified subspace and its dense units. The join is only successful if both subspaces have the first k-1 dimensions in common (where k is the number of dimensions) and the last dimension of this subspace is less than the last dimension of the specified subspace.

Parameters:

other - the subspace to join

all - the overall number of feature vectors

tau - the density threshold for the selectivity of a unit

Returns:

the join of this subspace with the specified subspace if the join condition is fulfilled, null otherwise.

See Also:

Subspace.joinLastDimensions(de.lmu.ifi.dbs.elki.data.Subspace)

toString

public String toString(String pre)

Calls the super method and adds additionally the coverage, and the dense units of this subspace.

Overrides:

toString in class Subspace

Parameters:

pre - a string prefix for each row of this string representation

Returns:

a string representation of this subspace