Package elki.clustering.kmeans

Class KDTreePruningKMeans<V extends NumberVector>

java.lang.Object

elki.clustering.kmeans.AbstractKMeans<V,KMeansModel>

elki.clustering.kmeans.KDTreePruningKMeans<V>

Type Parameters:

V - vector datatype

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<KMeansModel>>, KMeans<V,KMeansModel>

Direct Known Subclasses:

KDTreeFilteringKMeans

@Title("K-d-tree K-means with Pruning")
@Reference(authors="K. Alsabti, S. Ranka, V. Singh",title="An efficient k-means clustering algorithm",booktitle="Electrical Engineering and Computer Science, Technical Report 43",url="https://surface.syr.edu/eecs/43/",bibkey="tr/syracuse/AlsabtiRS97") @Reference(authors="K. Alsabti, S. Ranka, V. Singh",title="An Efficient Space-Partitioning Based Algorithm for the K-Means Clustering",booktitle="Pacific-Asia Conference on Knowledge Discovery and Data Mining",url="https://doi.org/10.1007/3-540-48912-6_47",bibkey="DBLP:conf/pakdd/AlsabtiRS99")
public class KDTreePruningKMeans<V extends NumberVector>
extends AbstractKMeans<V,KMeansModel>

Pruning K-means with k-d-tree acceleration.

This is an implementation of the earlier (1997) version of the k-d-tree based k-means, which uses minimum and maximum distances, rather than pruning with a hyperplane.

References:

K. Alsabti, S. Ranka, V. Singh
An efficient k-means clustering algorithm
Electrical Engineering and Computer Science, Technical Report 43

K. Alsabti, S. Ranka, V. Singh
An Efficient Space-Partitioning Based Algorithm for the K-Means Clustering
Pacific-Asia Conference on Knowledge Discovery and Data Mining

Since:

0.8.0

Author:

Cedrik Lüdicke (initial version), Erich Schubert (optimizations, rewrite)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	KDTreePruningKMeans.Instance	Inner instance, storing state for a single data set.
static class	KDTreePruningKMeans.KDNode	Node of the k-d-tree used internally.
static class	KDTreePruningKMeans.Par<V extends NumberVector>	Parameterization class.
static class	KDTreePruningKMeans.Split	Splitting strategies for constructing the k-d-tree.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
protected int	leafsize	Desired leaf size.
private static Logging	LOG	The logger for this class.
protected KDTreePruningKMeans.Split	split	Splitting strategy.

Fields inherited from class elki.clustering.kmeans.AbstractKMeans

distance, initializer, k, maxiter

Fields inherited from interface elki.clustering.kmeans.KMeans

DISTANCE_FUNCTION_ID, INIT_ID, K_ID, MAXITER_ID, SEED_ID, VARSTAT_ID

Constructor Summary

Constructors

Constructor	Description
KDTreePruningKMeans(NumberVectorDistance<? super V> distance, int k, int maxiter, KMeansInitialization initializer, KDTreePruningKMeans.Split split, int leafsize)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected Logging	getLogger()	Get the (STATIC) logger for this class.
Clustering<KMeansModel>	run(Relation<V> relation)	Run the clustering algorithm.

Methods inherited from class elki.clustering.kmeans.AbstractKMeans

getDistance, getInputTypeRestriction, incrementalUpdateMean, initialMeans, means, minusEquals, nearestMeans, plusEquals, plusMinusEquals, setDistance, setInitializer, setK

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.clustering.ClusteringAlgorithm

autorun

Field Detail

LOG

private static final Logging LOG

The logger for this class.

split

protected KDTreePruningKMeans.Split split

Splitting strategy.

leafsize

protected int leafsize

Desired leaf size.

Constructor Detail

KDTreePruningKMeans

public KDTreePruningKMeans(NumberVectorDistance<? super V> distance,
                           int k,
                           int maxiter,
                           KMeansInitialization initializer,
                           KDTreePruningKMeans.Split split,
                           int leafsize)

Constructor.

Parameters:

distance - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Initialization method

split - Splitting strategy

leafsize - Leaf size

Method Detail

run

public Clustering<KMeansModel> run(Relation<V> relation)

Description copied from interface: KMeans

Run the clustering algorithm.

Parameters:

relation - Relation to process.

Returns:

Clustering result

getLogger

protected Logging getLogger()

Description copied from class: AbstractKMeans

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractKMeans<V extends NumberVector,KMeansModel>

Returns:

the static logger