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

java.lang.Object
  de.lmu.ifi.dbs.elki.data.Subspace<V>
      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:

Model, TextWriteable, Comparable<CLIQUESubspace<V>>

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

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<CLIQUESubspace<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>	leftNeighbor(CLIQUEUnit<V> unit, Integer 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) Returns a string representation of this subspace that contains the coverage, the dimensions and the dense units of this subspace.
void	writeToText(TextWriterStream out, String label) Serialize using above toString method

Methods inherited from class de.lmu.ifi.dbs.elki.data.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<CLIQUESubspace<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

leftNeighbor

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

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

join

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

Joins this subspace with the specified subspace. The join is only successful 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 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.

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

writeToText

public void writeToText(TextWriterStream out,
                        String label)

Serialize using above toString method

Specified by:

writeToText in interface TextWriteable

Parameters:

out - Output writer

label - Label