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

Class UKMeans

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<KMeansModel>>

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.UKMeans

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<KMeansModel>>

@Reference(authors="M. Chau, R. Cheng, B. Kao, J. Ng",
           title="Uncertain data mining: An example in clustering location data",
           booktitle="Proc. 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2006)",
           url="http://dx.doi.org/10.1007/11731139_24")
public class UKMeans
extends AbstractAlgorithm<Clustering<KMeansModel>>
implements ClusteringAlgorithm<Clustering<KMeansModel>>

Uncertain K-Means clustering, using the average deviation from the center. Note: this method is, essentially, superficial. It was shown to be equivalent to doing regular K-means on the object centroids instead (see CKMeans for the reference and an implementation). This is only for completeness. Reference:

M. Chau, R. Cheng, B. Kao, J. Ng
Uncertain data mining: An example in clustering location data
Proc. of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2006)

Author:

Klaus Arthur Schmidt

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
protected int	k Number of cluster centers to initialize.
protected static String	KEY Key for statistics logging.
protected static Logging	LOG CLass logger.
protected int	maxiter Maximum number of iterations
protected RandomFactory	rnd Our Random factory

Constructor Summary

Constructors

Constructor and Description
UKMeans(int k, int maxiter, RandomFactory rnd) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	assignToNearestCluster(Relation<DiscreteUncertainObject> relation, List<Vector> means, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, double[] varsum) Returns a list of clusters.
protected double	getExpectedRepDistance(Vector rep, DiscreteUncertainObject uo) Get expected distance between a Vector and an uncertain object
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	logVarstat(DoubleStatistic varstat, double[] varsum) Log statistics on the variance sum.
protected List<Vector>	means(List<? extends ModifiableDBIDs> clusters, List<? extends NumberVector> means, Relation<DiscreteUncertainObject> database) Returns the mean vectors of the given clusters in the given database.
Clustering<?>	run(Database database, Relation<DiscreteUncertainObject> relation) Run the clustering.
protected boolean	updateAssignment(DBIDIter iditer, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, int newA) Update the cluster assignment.

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

protected static final Logging LOG

CLass logger.

KEY

protected static final String KEY

Key for statistics logging.

k

protected int k

Number of cluster centers to initialize.

maxiter

protected int maxiter

Maximum number of iterations

rnd

protected RandomFactory rnd

Our Random factory

Constructor Detail

UKMeans

public UKMeans(int k,
       int maxiter,
       RandomFactory rnd)

Constructor.

Parameters:

k - Number of clusters

maxiter - Maximum number of iterations

rnd - Random initialization

Method Detail

run

public Clustering<?> run(Database database,
                Relation<DiscreteUncertainObject> relation)

Run the clustering.

Parameters:

database - the Database

relation - the Relation

Returns:

Clustering result

assignToNearestCluster

protected boolean assignToNearestCluster(Relation<DiscreteUncertainObject> relation,
                             List<Vector> means,
                             List<? extends ModifiableDBIDs> clusters,
                             WritableIntegerDataStore assignment,
                             double[] varsum)

Returns a list of clusters. The k^th cluster contains the ids of those FeatureVectors, that are nearest to the k^th mean.

Parameters:

relation - the database to cluster

means - a list of k means

clusters - cluster assignment

assignment - Current cluster assignment

varsum - Variance sum output

Returns:

true when the object was reassigned

updateAssignment

protected boolean updateAssignment(DBIDIter iditer,
                       List<? extends ModifiableDBIDs> clusters,
                       WritableIntegerDataStore assignment,
                       int newA)

Update the cluster assignment.

Parameters:

iditer - Object id

clusters - Cluster list

assignment - Assignment storage

newA - New assignment.

Returns:

true if the assignment has changed.

getExpectedRepDistance

protected double getExpectedRepDistance(Vector rep,
                            DiscreteUncertainObject uo)

Get expected distance between a Vector and an uncertain object

Parameters:

rep - A vector, e.g. a cluster representative

uo - A discrete uncertain object

Returns:

The distance

means

protected List<Vector> means(List<? extends ModifiableDBIDs> clusters,
                 List<? extends NumberVector> means,
                 Relation<DiscreteUncertainObject> database)

Returns the mean vectors of the given clusters in the given database.

Parameters:

clusters - the clusters to compute the means

means - the recent means

database - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

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<KMeansModel>>

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<KMeansModel>>

Returns:

the static logger

logVarstat

protected void logVarstat(DoubleStatistic varstat,
              double[] varsum)

Log statistics on the variance sum.

Parameters:

varstat - Statistics log instance

varsum - Variance sum per cluster