kmeans.h File Reference

K-means (K-means clustering) More...

#include "generic.h"
#include "random.h"
#include "mathop.h"
#include "kdtree.h"

Data Structures
struct	VlKMeans
	K-means quantizer. More...

Enumerations
enum	VlKMeansAlgorithm { VlKMeansLloyd, VlKMeansElkan, VlKMeansANN }
	K-means algorithms. More...
enum	VlKMeansInitialization { VlKMeansRandomSelection, VlKMeansPlusPlus }
	K-means initialization algorithms. More...

Functions
Create and destroy
VlKMeans *	vl_kmeans_new (vl_type dataType, VlVectorComparisonType distance)
	Create a new KMeans object.
VlKMeans *	vl_kmeans_new_copy (VlKMeans const *kmeans)
	Create a new KMeans object by copy.
void	vl_kmeans_delete (VlKMeans *self)
	Deletes a KMeans object.
Basic data processing
void	vl_kmeans_reset (VlKMeans *self)
	Reset state.
double	vl_kmeans_cluster (VlKMeans *self, void const *data, vl_size dimension, vl_size numData, vl_size numCenters)
	Cluster data.
void	vl_kmeans_quantize (VlKMeans *self, vl_uint32 *assignments, void *distances, void const *data, vl_size numData)
	Quantize data.
void	vl_kmeans_quantize_ANN (VlKMeans *self, vl_uint32 *assignments, void *distances, void const *data, vl_size numData, vl_size iteration)
Advanced data processing
void	vl_kmeans_set_centers (VlKMeans *self, void const *centers, vl_size dimension, vl_size numCenters)
	Set centers.
void	vl_kmeans_init_centers_with_rand_data (VlKMeans *self, void const *data, vl_size dimensions, vl_size numData, vl_size numCenters)
	init centers by randomly sampling data
void	vl_kmeans_init_centers_plus_plus (VlKMeans *self, void const *data, vl_size dimensions, vl_size numData, vl_size numCenters)
	Seed centers by the KMeans++ algorithm.
double	vl_kmeans_refine_centers (VlKMeans *self, void const *data, vl_size numData)
	Refine center locations.
Retrieve data and parameters
vl_type	vl_kmeans_get_data_type (VlKMeans const *self)
	Get data type.
VlVectorComparisonType	vl_kmeans_get_distance (VlKMeans const *self)
	Get data type.
VlKMeansAlgorithm	vl_kmeans_get_algorithm (VlKMeans const *self)
	Get K-means algorithm.
VlKMeansInitialization	vl_kmeans_get_initialization (VlKMeans const *self)
	Get K-means initialization algorithm.
vl_size	vl_kmeans_get_num_repetitions (VlKMeans const *self)
	Get maximum number of repetitions.
vl_size	vl_kmeans_get_dimension (VlKMeans const *self)
	Get data dimension.
vl_size	vl_kmeans_get_num_centers (VlKMeans const *self)
	Get the number of centers (K)
int	vl_kmeans_get_verbosity (VlKMeans const *self)
	Get verbosity level.
vl_size	vl_kmeans_get_max_num_iterations (VlKMeans const *self)
	Get maximum number of iterations.
vl_size	vl_kmeans_get_max_num_comparisons (VlKMeans const *self)
	Get maximum number of comparisons in ANN-KD-Tree.
vl_size	vl_kmeans_get_num_trees (VlKMeans const *self)
double	vl_kmeans_get_energy (VlKMeans const *self)
	Get the number energy of the current fit.
void const *	vl_kmeans_get_centers (VlKMeans const *self)
	Get centers.
Set parameters
void	vl_kmeans_set_algorithm (VlKMeans *self, VlKMeansAlgorithm algorithm)
	Set K-means algorithm.
void	vl_kmeans_set_initialization (VlKMeans *self, VlKMeansInitialization initialization)
	Set K-means initialization algorithm.
void	vl_kmeans_set_num_repetitions (VlKMeans *self, vl_size numRepetitions)
	Set maximum number of repetitions.
void	vl_kmeans_set_max_num_iterations (VlKMeans *self, vl_size maxNumIterations)
	Set maximum number of iterations.
void	vl_kmeans_set_verbosity (VlKMeans *self, int verbosity)
	Set verbosity level.
void	vl_kmeans_set_max_num_comparisons (VlKMeans *self, vl_size maxNumComparisons)
	Set maximum number of comparisons in ANN-KD-Tree.
void	vl_kmeans_set_num_trees (VlKMeans *self, vl_size numTrees)
	Get number of trees in ANN-KD-Tree.

---

Detailed Description

Author:

Andrea Vedaldi

David Novotny

---

Enumeration Type Documentation

enum VlKMeansAlgorithm

Enumerator:

VlKMeansLloyd	Lloyd algorithm
VlKMeansElkan	Elkan algorithm
VlKMeansANN	Approximate nearest neighbors

enum VlKMeansInitialization

Enumerator:

VlKMeansRandomSelection	Randomized selection
VlKMeansPlusPlus	Plus plus raondomized selection

---

Function Documentation

double vl_kmeans_cluster	(	VlKMeans *	self,
		void const *	data,
		vl_size	dimension,
		vl_size	numData,
		vl_size	numCenters
	)

Parameters:

self	KMeans object.
data	data to quantize.
dimension	data dimension.
numData	number of data points.
numCenters	number of clusters.

Returns:

K-means energy at the end of optimization.

The function initializes the centers by using the initialization algorithm set by vl_kmeans_set_initialization and refines them by the quantization algorithm set by vl_kmeans_set_algorithm. The process is repeated one or more times (see vl_kmeans_set_num_repetitions) and the resutl with smaller energy is retained.

void vl_kmeans_delete

(

VlKMeans *

self

)

Parameters:

self	KMeans object instance.

The function deletes the KMeans object instance created by vl_kmeans_new.

VlKMeansAlgorithm vl_kmeans_get_algorithm ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object.

Returns:

algorithm.

void const * vl_kmeans_get_centers ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

cluster centers.

vl_type vl_kmeans_get_data_type ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

data type.

vl_size vl_kmeans_get_dimension ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

data dimension.

VlVectorComparisonType vl_kmeans_get_distance ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

data type.

double vl_kmeans_get_energy ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

energy.

VlKMeansInitialization vl_kmeans_get_initialization ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object.

Returns:

algorithm.

vl_size vl_kmeans_get_max_num_comparisons ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

maximum number of comparisons.

vl_size vl_kmeans_get_max_num_iterations ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

maximum number of iterations.

vl_size vl_kmeans_get_num_centers ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

number of centers.

vl_size vl_kmeans_get_num_repetitions ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

current number of repretitions for quantization.

int vl_kmeans_get_verbosity ( VlKMeans const *  self )

inline

Parameters:

self	KMeans object instance.

Returns:

verbosity level.

void vl_kmeans_init_centers_plus_plus	(	VlKMeans *	self,
		void const *	data,
		vl_size	dimension,
		vl_size	numData,
		vl_size	numCenters
	)

Parameters:

self	KMeans object.
data	data to sample from.
dimension	data dimension.
numData	nmber of data points.
numCenters	number of centers.

void vl_kmeans_init_centers_with_rand_data	(	VlKMeans *	self,
		void const *	data,
		vl_size	dimension,
		vl_size	numData,
		vl_size	numCenters
	)

Parameters:

self	KMeans object.
data	data to sample from.
dimension	data dimension.
numData	nmber of data points.
numCenters	number of centers.

The function inits the KMeans centers by randomly sampling the data data.

VlKMeans* vl_kmeans_new	(	vl_type	dataType,
		VlVectorComparisonType	distance
	)

Parameters:

dataType	type of data (VL_TYPE_FLOAT or VL_TYPE_DOUBLE)
distance	distance.

Returns:

new KMeans object instance.

VlKMeans* vl_kmeans_new_copy

(

VlKMeans const *

kmeans

)

Parameters:

kmeans

KMeans object to copy.

Returns:

new copy.

void vl_kmeans_quantize	(	VlKMeans *	self,
		vl_uint32 *	assignments,
		void *	distances,
		void const *	data,
		vl_size	numData
	)

Parameters:

self	KMeans object.
assignments	data to closest center assignments (output).
distances	data to closest center distance (output).
data	data to quantize.
numData	number of data points to quantize.

double vl_kmeans_refine_centers	(	VlKMeans *	self,
		void const *	data,
		vl_size	numData
	)

Parameters:

self	KMeans object.
data	data to quantize.
numData	number of data points.

Returns:

K-means energy at the end of optimization.

The function calls the underlying K-means quantization algorithm (VlKMeansAlgorithm) to quantize the specified data data. The function assumes that the cluster centers have already been assigned by using one of the seeding functions, or by setting them.

void vl_kmeans_reset

(

VlKMeans *

self

)

The function reset the state of the KMeans object. It deletes any stored centers, releasing the corresponding memory. This cancels the effect of seeding or setting the centers, but does not change the other configuration parameters.

void vl_kmeans_set_algorithm ( VlKMeans *  self, VlKMeansAlgorithm  algorithm  )

inline

Parameters:

self	KMeans object.
algorithm	K-means algorithm.

void vl_kmeans_set_centers	(	VlKMeans *	self,
		void const *	centers,
		vl_size	dimension,
		vl_size	numCenters
	)

Parameters:

self	KMeans object.
centers	centers to copy.
dimension	data dimension.
numCenters	number of centers.

void vl_kmeans_set_initialization ( VlKMeans *  self, VlKMeansInitialization  initialization  )

inline

Parameters:

self	KMeans object.
initialization	initialization.

void vl_kmeans_set_max_num_comparisons ( VlKMeans *  self, vl_size  maxNumComparisons  )

inline

Parameters:

self	KMeans filter.
maxNumComparisons	maximum number of comparisons.

void vl_kmeans_set_max_num_iterations ( VlKMeans *  self, vl_size  maxNumIterations  )

inline

Parameters:

self	KMeans filter.
maxNumIterations	maximum number of iterations.

void vl_kmeans_set_num_repetitions ( VlKMeans *  self, vl_size  numRepetitions  )

inline

Parameters:

self	KMeans object instance.
numRepetitions	maximum number of repetitions. The number of repetitions cannot be smaller than 1.

void vl_kmeans_set_num_trees ( VlKMeans *  self, vl_size  numTrees  )

inline

Parameters:

self	KMeans object instance.

Returns:

number of trees.

void vl_kmeans_set_verbosity ( VlKMeans *  self, int  verbosity  )

inline

Parameters:

self	KMeans object instance.
verbosity	verbosity level.