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

Class NaiveMeanShiftClustering<V extends NumberVector<?>,D extends NumberDistance<D,?>>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<V,D,Clustering<MeanModel<V>>>

de.lmu.ifi.dbs.elki.algorithm.clustering.NaiveMeanShiftClustering<V,D>

Type Parameters:

V - Vector type

D - Distance type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MeanModel<V>>>, InspectionUtilFrequentlyScanned, Parameterizable

@Reference(authors="Y. Cheng",
           title="Mean shift, mode seeking, and clustering",
           booktitle="IEEE Transactions on Pattern Analysis and Machine Intelligence 17-8",
           url="http://dx.doi.org/10.1109/34.400568")
public class NaiveMeanShiftClustering<V extends NumberVector<?>,D extends NumberDistance<D,?>>
extends AbstractDistanceBasedAlgorithm<V,D,Clustering<MeanModel<V>>>
implements ClusteringAlgorithm<Clustering<MeanModel<V>>>

Mean-shift based clustering algorithm. Naive implementation: there does not seem to be "the" mean-shift clustering algorithm, but it is a general concept. For the naive implementation, mean-shift is applied to all objects until they converge to other. This implementation is quite naive, and various optimizations can be made. It also is not really parameter-free: the kernel needs to be specified, including a radius/bandwidth. By using range queries, the algorithm does benefit from index structures! TODO: add methods to automatically choose the bandwidth?

Reference:
Y. Cheng
Mean shift, mode seeking, and clustering
IEEE Transactions on Pattern Analysis and Machine Intelligence 17-8

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NaiveMeanShiftClustering.Parameterizer<V extends NumberVector<?>,D extends NumberDistance<D,?>> Parameterizer.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) KernelDensityFunction	kernel Density estimation kernel.
private static Logging	LOG Class logger.
(package private) static int	MAXITER Maximum number of iterations.
(package private) D	range Range of the kernel.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
NaiveMeanShiftClustering(DistanceFunction<? super V,D> distanceFunction, KernelDensityFunction kernel, D range) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
Clustering<MeanModel<V>>	run(Database database, Relation<V> relation) Run the mean-shift clustering algorithm.

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

getDistanceFunction

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

Class logger.

kernel

KernelDensityFunction kernel

Density estimation kernel.

range

D extends NumberDistance<D,?> range

Range of the kernel.

MAXITER

static final int MAXITER

Maximum number of iterations.

See Also:

Constant Field Values

Constructor Detail

NaiveMeanShiftClustering

public NaiveMeanShiftClustering(DistanceFunction<? super V,D> distanceFunction,
                        KernelDensityFunction kernel,
                        D range)

Constructor.

Parameters:

distanceFunction - Distance function

kernel - Kernel function

range - Kernel radius

Method Detail

run

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

Run the mean-shift clustering algorithm.

Parameters:

database - Database

relation - Data relation

Returns:

Clustering result

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<MeanModel<V extends NumberVector<?>>>>

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<MeanModel<V extends NumberVector<?>>>>

Returns:

the static logger