Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.clique
Class CLIQUESubspace<V extends RealVector<V,?>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.utilities.Subspace<V>
      extended by de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.clique.CLIQUESubspace<V>
Type Parameters:
V - the type of RealVector handled by this Algorithm
All Implemented Interfaces:
Comparable<CLIQUESubspace<V>>

public class CLIQUESubspace<V extends RealVector<V,?>>
extends Subspace<V>
implements Comparable<CLIQUESubspace<V>>

Represents a subspace of the original dataspace in the CLIQUE algorithm.

Author:
Elke Achtert

Field Summary
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
CLIQUESubspace(int dimension)
          Creates a new one-dimensional subspace of the original dataspace.
CLIQUESubspace(SortedSet<Integer> dimensions)
          Creates a new k-dimensional subspace of the original dataspace.
 
Method Summary
 void addDenseUnit(CLIQUEUnit<V> unit)
          Adds the specified dense unit to this subspace.
 int compareTo(CLIQUESubspace<V> other)
          Compares this subspace with the specified subspace for order.
 Map<CLIQUEModel<V>,Set<Integer>> determineClusters(Database<V> database)
          Determines all clusters in this subspace by performing a depth-first search algorithm to find connected dense units.
 void dfs(CLIQUEUnit<V> unit, Set<Integer> cluster)
          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.
 CLIQUESubspace<V> join(CLIQUESubspace<V> other, double all, double tau)
          Joins this subspace with the specified subspace.
 CLIQUEUnit<V> leftNeighbour(CLIQUEUnit unit, Integer dim)
          Returns the left neighbor of the given unit in the specified dimension.
 CLIQUEUnit<V> rightNeighbour(CLIQUEUnit unit, Integer dim)
          Returns the right neighbor of the given unit in the specified dimension.
 String toString(String pre)
          Returns a string representation of this subspace that contains the coverage, the dimensions and the dense units of this subspace.
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.Subspace
getDimensions, join, joinDimensions, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

denseUnits

private List<CLIQUEUnit<V extends RealVector<V,?>>> 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 dataspace.

Parameters:
dimension - the dimension building this subspace

CLIQUESubspace

public CLIQUESubspace(SortedSet<Integer> dimensions)
Creates a new k-dimensional subspace of the original dataspace.

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.

compareTo

public int compareTo(CLIQUESubspace<V> other)
Compares this subspace with the specified subspace for order. Returns a negative integer, zero, or a positive integer if the coverage of this subspace is less than, equal to, or greater than the coverage of the specified subspace.

Specified by:
compareTo in interface Comparable<CLIQUESubspace<V extends RealVector<V,?>>>
Parameters:
other - the subspace to be compared
Returns:
a negative integer, zero, or a positive integer if the coverage of this subspace is less than, equal to, or greater than the coverage of the specified subspace.

determineClusters

public Map<CLIQUEModel<V>,Set<Integer>> determineClusters(Database<V> database)
Determines all clusters in this subspace by performing a depth-first search algorithm to find connected dense units.

Parameters:
database - the database containing the feature vectors
Returns:
the clusters in this subspace and the corresponding cluster models

dfs

public void dfs(CLIQUEUnit<V> unit,
                Set<Integer> cluster)
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

leftNeighbour

public CLIQUEUnit<V> leftNeighbour(CLIQUEUnit unit,
                                   Integer 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

rightNeighbour

public CLIQUEUnit<V> rightNeighbour(CLIQUEUnit 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

join

public CLIQUESubspace<V> join(CLIQUESubspace<V> other,
                              double all,
                              double tau)
Joins this subspace with the specified subspace. The join is only sucessful if both subspaces have the first k-1 dimensions in common (where k is the number of dimensions).

Parameters:
other - the subspace to join
all - the overall number of featuer 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.

toString

public String toString(String pre)
Returns a string representation of this subspace that contains the coverage, the dimensions and the dense units of this subspace.

Overrides:
toString in class Subspace<V extends RealVector<V,?>>
Parameters:
pre - a string prefix
Returns:
a string representation of this subspace

Release 0.1 (2008-07-10_1838)