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

Class PROCLUS<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.clustering.AbstractProjectedClustering<Clustering<SubspaceModel>,V>

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

Type Parameters:

V - the type of NumberVector handled by this Algorithm

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<SubspaceModel>>, SubspaceClusteringAlgorithm<SubspaceModel>

@Title(value="PROCLUS: PROjected CLUStering")
@Description(value="Algorithm to find subspace clusters in high dimensional spaces.")
@Reference(authors="C. C. Aggarwal, C. Procopiuc, J. L. Wolf, P. S. Yu, J. S. Park",
           title="Fast Algorithms for Projected Clustering",
           booktitle="Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD \'99)",
           url="http://dx.doi.org/10.1145/304181.304188")
public class PROCLUS<V extends NumberVector>
extends AbstractProjectedClustering<Clustering<SubspaceModel>,V>
implements SubspaceClusteringAlgorithm<SubspaceModel>

The PROCLUS algorithm, an algorithm to find subspace clusters in high dimensional spaces.

Reference:
C. C. Aggarwal, C. Procopiuc, J. L. Wolf, P. S. Yu, J. S. Park: Fast Algorithms for Projected Clustering.
In: Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD '99).

Author:

Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	PROCLUS.DoubleIntInt Simple triple.
static class	PROCLUS.Parameterizer<V extends NumberVector> Parameterization class.
private class	PROCLUS.PROCLUSCluster Encapsulates the attributes of a cluster.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.
private int	m_i Multiplier for the initial number of medoids.
private RandomFactory	rnd Random generator

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.AbstractProjectedClustering

k, k_i, l

Constructor Summary

Constructors

Constructor and Description
PROCLUS(int k, int k_i, int l, int m_i, RandomFactory rnd) Java constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private ArrayList<PROCLUS.PROCLUSCluster>	assignPoints(ArrayDBIDs m_current, long[][] dimensions, Relation<V> database) Assigns the objects to the clusters.
private double	avgDistance(Vector centroid, DBIDs objectIDs, Relation<V> database, int dimension) Computes the average distance of the objects to the centroid along the specified dimension.
private DBIDs	computeBadMedoids(ArrayDBIDs m_current, ArrayList<PROCLUS.PROCLUSCluster> clusters, int threshold) Computes the bad medoids, where the medoid of a cluster with less than the specified threshold of objects is bad.
private ArrayDBIDs	computeM_current(DBIDs m, DBIDs m_best, DBIDs m_bad, Random random) Computes the set of medoids in current iteration.
private double	evaluateClusters(ArrayList<PROCLUS.PROCLUSCluster> clusters, long[][] dimensions, Relation<V> database) Evaluates the quality of the clusters.
private List<PROCLUS.PROCLUSCluster>	finalAssignment(List<Pair<Vector,long[]>> dimensions, Relation<V> database) Refinement step to assign the objects to the final clusters.
private long[][]	findDimensions(ArrayDBIDs medoids, Relation<V> database, DistanceQuery<V> distFunc, RangeQuery<V> rangeQuery) Determines the set of correlated dimensions for each medoid in the specified medoid set.
private List<Pair<Vector,long[]>>	findDimensions(ArrayList<PROCLUS.PROCLUSCluster> clusters, Relation<V> database) Refinement step that determines the set of correlated dimensions for each cluster centroid.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
private DataStore<DoubleDBIDList>	getLocalities(DBIDs medoids, Relation<V> database, DistanceQuery<V> distFunc, RangeQuery<V> rangeQuery) Computes the localities of the specified medoids: for each medoid m the objects in the sphere centered at m with radius minDist are determined, where minDist is the minimum distance between medoid m and any other medoid m_i.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private ArrayDBIDs	greedy(DistanceQuery<V> distFunc, DBIDs sampleSet, int m, Random random) Returns a piercing set of k medoids from the specified sample set.
private ArrayDBIDs	initialSet(DBIDs sampleSet, int k, Random random) Returns a set of k elements from the specified sample set.
private double	manhattanSegmentalDistance(NumberVector o1, NumberVector o2, long[] dimensions) Returns the Manhattan segmental distance between o1 and o2 relative to the specified dimensions.
Clustering<SubspaceModel>	run(Database database, Relation<V> relation) Performs the PROCLUS algorithm on the given database.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.AbstractProjectedClustering

getDistanceFunction, getDistanceQuery

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

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

Field Detail

LOG

private static final Logging LOG

The logger for this class.

m_i

private int m_i

Multiplier for the initial number of medoids.

rnd

private RandomFactory rnd

Random generator

Constructor Detail

PROCLUS

public PROCLUS(int k,
       int k_i,
       int l,
       int m_i,
       RandomFactory rnd)

Java constructor.

Parameters:

k - k Parameter

k_i - k_i Parameter

l - l Parameter

m_i - m_i Parameter

rnd - Random generator

Method Detail

run

public Clustering<SubspaceModel> run(Database database,
                            Relation<V> relation)

Performs the PROCLUS algorithm on the given database.

Parameters:

database - Database to process

relation - Relation to process

greedy

private ArrayDBIDs greedy(DistanceQuery<V> distFunc,
                DBIDs sampleSet,
                int m,
                Random random)

Returns a piercing set of k medoids from the specified sample set.

Parameters:

distFunc - the distance function

sampleSet - the sample set

m - the number of medoids to be returned

random - random number generator

Returns:

a piercing set of m medoids from the specified sample set

initialSet

private ArrayDBIDs initialSet(DBIDs sampleSet,
                    int k,
                    Random random)

Returns a set of k elements from the specified sample set.

Parameters:

sampleSet - the sample set

k - the number of samples to be returned

random - random number generator

Returns:

a set of k elements from the specified sample set

computeM_current

private ArrayDBIDs computeM_current(DBIDs m,
                          DBIDs m_best,
                          DBIDs m_bad,
                          Random random)

Computes the set of medoids in current iteration.

Parameters:

m - the medoids

m_best - the best set of medoids found so far

m_bad - the bad medoids

random - random number generator

Returns:

m_current, the set of medoids in current iteration

getLocalities

private DataStore<DoubleDBIDList> getLocalities(DBIDs medoids,
                                      Relation<V> database,
                                      DistanceQuery<V> distFunc,
                                      RangeQuery<V> rangeQuery)

Computes the localities of the specified medoids: for each medoid m the objects in the sphere centered at m with radius minDist are determined, where minDist is the minimum distance between medoid m and any other medoid m_i.

Parameters:

medoids - the ids of the medoids

database - the database holding the objects

distFunc - the distance function

Returns:

a mapping of the medoid's id to its locality

findDimensions

private long[][] findDimensions(ArrayDBIDs medoids,
                      Relation<V> database,
                      DistanceQuery<V> distFunc,
                      RangeQuery<V> rangeQuery)

Determines the set of correlated dimensions for each medoid in the specified medoid set.

Parameters:

medoids - the set of medoids

database - the database containing the objects

distFunc - the distance function

Returns:

the set of correlated dimensions for each medoid in the specified medoid set

findDimensions

private List<Pair<Vector,long[]>> findDimensions(ArrayList<PROCLUS.PROCLUSCluster> clusters,
                                       Relation<V> database)

Refinement step that determines the set of correlated dimensions for each cluster centroid.

Parameters:

clusters - the list of clusters

database - the database containing the objects

Returns:

the set of correlated dimensions for each specified cluster centroid

assignPoints

private ArrayList<PROCLUS.PROCLUSCluster> assignPoints(ArrayDBIDs m_current,
                                             long[][] dimensions,
                                             Relation<V> database)

Assigns the objects to the clusters.

Parameters:

m_current - Current centers

dimensions - set of correlated dimensions for each medoid of the cluster

database - the database containing the objects

Returns:

the assignments of the object to the clusters

finalAssignment

private List<PROCLUS.PROCLUSCluster> finalAssignment(List<Pair<Vector,long[]>> dimensions,
                                           Relation<V> database)

Refinement step to assign the objects to the final clusters.

Parameters:

dimensions - pair containing the centroid and the set of correlated dimensions for the centroid

database - the database containing the objects

Returns:

the assignments of the object to the clusters

manhattanSegmentalDistance

private double manhattanSegmentalDistance(NumberVector o1,
                                NumberVector o2,
                                long[] dimensions)

Returns the Manhattan segmental distance between o1 and o2 relative to the specified dimensions.

Parameters:

o1 - the first object

o2 - the second object

dimensions - the dimensions to be considered

Returns:

the Manhattan segmental distance between o1 and o2 relative to the specified dimensions

evaluateClusters

private double evaluateClusters(ArrayList<PROCLUS.PROCLUSCluster> clusters,
                      long[][] dimensions,
                      Relation<V> database)

Evaluates the quality of the clusters.

Parameters:

clusters - the clusters to be evaluated

dimensions - the dimensions associated with each cluster

database - the database holding the objects

Returns:

a measure for the cluster quality

avgDistance

private double avgDistance(Vector centroid,
                 DBIDs objectIDs,
                 Relation<V> database,
                 int dimension)

Computes the average distance of the objects to the centroid along the specified dimension.

Parameters:

centroid - the centroid

objectIDs - the set of objects ids

database - the database holding the objects

dimension - the dimension for which the average distance is computed

Returns:

the average distance of the objects to the centroid along the specified dimension

computeBadMedoids

private DBIDs computeBadMedoids(ArrayDBIDs m_current,
                      ArrayList<PROCLUS.PROCLUSCluster> clusters,
                      int threshold)

Computes the bad medoids, where the medoid of a cluster with less than the specified threshold of objects is bad.

Parameters:

m_current - Current medoids

clusters - the clusters

threshold - the threshold

Returns:

the bad medoids

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Clustering<SubspaceModel>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<SubspaceModel>>

Returns:

the static logger