de.lmu.ifi.dbs.elki.algorithm.clustering
Class KMeans<D extends Distance<D>,V extends RealVector<V,?>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<V,D>
                  de.lmu.ifi.dbs.elki.algorithm.clustering.KMeans<D,V>

Type Parameters:

D - a type of Distance as returned by the used distance function

V - a type of RealVector as a suitable datatype for this algorithm

All Implemented Interfaces:

Algorithm<V>, Clustering<V>, Loggable, Parameterizable

public class KMeans<D extends Distance<D>,V extends RealVector<V,?>>
extends DistanceBasedAlgorithm<V,D>
implements Clustering<V>

Provides the k-means algorithm.

Author:

Arthur Zimek

Field Summary

private int	k Keeps k - the number of clusters to find.
private IntParameter	K_PARAM Parameter to specify the number of clusters to find, must be an integer greater than 0.
private Clusters<V>	result Keeps the result.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

optionHandler

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

KMeans()
Provides the k-means algorithm.

Method Summary

Description	getDescription() Returns a description of the algorithm.
Clusters<V>	getResult() Returns the result of the algorithm.
protected List<V>	means(List<List<Integer>> clusters, List<V> means, Database<V> database) Returns the mean vectors of the given clusters in the given database.
protected void	runInTime(Database<V> database) Performs the k-means algorithm on the given database.
String[]	setParameters(String[] args) Sets parameter k.
protected List<List<Integer>>	sort(List<V> means, Database<V> database) Returns a list of clusters.

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

getAttributeSettings, getDistanceFunction

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

description, isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

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.Algorithm

run, setTime, setVerbose

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, description, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription

Field Detail

K_PARAM

private final IntParameter K_PARAM

Parameter to specify the number of clusters to find, must be an integer greater than 0.

Key: -kmeans.k

k

private int k

Keeps k - the number of clusters to find.

result

private Clusters<V extends RealVector<V,?>> result

Keeps the result.

Constructor Detail

KMeans

public KMeans()

Provides the k-means algorithm.

Method Detail

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Specified by:

getDescription in interface Algorithm<V extends RealVector<V,?>>

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

getResult

public Clusters<V> getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Specified by:

getResult in interface Algorithm<V extends RealVector<V,?>>

Specified by:

getResult in interface Clustering<V extends RealVector<V,?>>

Returns:

the result of the algorithm

See Also:

Clustering.getResult()

runInTime

protected void runInTime(Database<V> database)
                  throws IllegalStateException

Performs the k-means algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<V extends RealVector<V,?>>

Parameters:

database - the database to run the algorithm on

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

See Also:

Algorithm.run(de.lmu.ifi.dbs.elki.database.Database)

means

protected List<V> means(List<List<Integer>> clusters,
                        List<V> means,
                        Database<V> 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

sort

protected List<List<Integer>> sort(List<V> means,
                                   Database<V> database)

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

Parameters:

means - a list of k means

database - the database to cluster

Returns:

list of k clusters

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Sets parameter k.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class DistanceBasedAlgorithm<V extends RealVector<V,?>,D extends Distance<D>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])