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

Class NaiveMeanShiftClustering<V extends NumberVector>

java.lang.Object

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

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

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

Type Parameters:

V - Vector type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MeanModel>>, DistanceBasedAlgorithm<V>

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

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

Since:

0.5.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NaiveMeanShiftClustering.Parameterizer<V extends NumberVector> Parameterizer.

Field Summary

Fields

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

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

ALGORITHM_ID

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

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

Method Summary

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

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.

bandwidth

double bandwidth

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> distanceFunction,
                                KernelDensityFunction kernel,
                                double range)

Constructor.

Parameters:

distanceFunction - Distance function

kernel - Kernel function

range - Kernel radius

Method Detail

run

public Clustering<MeanModel> 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>>

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

Returns:

the static logger