<commit_before>/** @file kmeans.c
 ** @brief K-means - Declaration
 ** @author <NAME>, <NAME>
 **/

/*
Copyright (C) 2007-12 <NAME> and <NAME>.
Copyright (C) 2013 <NAME> and <NAME>.
All rights reserved.

This file is part of the VLFeat library and is made available under
the terms of the BSD license (see the COPYING file).
*/

/**
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@page kmeans K-means clustering
@author <NAME>
@author <NAME>
@tableofcontents
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

@ref kmeans.h implements a number of algorithm for **K-means
quantization**: Lloyd @cite{lloyd82least}, an accelerated version by
Elkan @cite{elkan03using}, and a large scale algorithm based on
Approximate Nearest Neighbors (ANN). All algorithms support @c float
or @c double data and can use the $l^1$ or the $l^2$ distance for
clustering. Furthermore, all algorithms can take advantage of multiple
CPU cores.

Please see @subpage kmeans-fundamentals for a technical description of
K-means and of the algorithms implemented here.

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@section kmeans-starting Getting started
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

The goal of K-means is to partition a dataset into $K$
&ldquo;compact&rdquo; clusters. The following example demonstrates
using @ref kmeans.h in the C programming language to partition @c
numData @c float vectors into compute @c numCenters clusters using
Lloyd's algorithm:

@code
#include <vl/kmeans.h>
double energy ;
double * centers ;

// Use float data and the L2 distance for clustering
KMeans * kmeans = vl_kmeans_new (VLDistanceL2, VL_TYPE_FLOAT) ;

// Use Lloyd algorithm
vl_kmeans_set_algorithm (kmeans, VlKMeansLloyd) ;

// Initialize the cluster centers by randomly sampling the data
vl_kmeans_seed_centers_with_rand_data (kmeans, data, dimension, numData, numCenters) ;

// Run at most 100 iterations of cluster refinement using Lloyd algorithm
vl_kmeans_set_max_num_iterations (kmeans, 100) ;
vl_kmeans_refine_centers (kmeans, data, numData) ;

// Obtain the energy of the solution
energy = vl_kmeans_get_energy(kmeans) ;

// Obtain the cluster centers
centers = vl_kmeans_get_centers(kmeans) ;
@endcode

Once the centers have been obtained, new data points can be assigned
to clusters by using the ::vl_kmeans_quantize function:

@code
vl_uint32 * assignments = vl_malloc(sizeof(vl_uint32) * numData) ;
float * distances = vl_malloc(sizeof(float) * numData) ;
vl_kmeans_quantize(kmeans, assignments, distances, data, numData) ;
@endcode

Alternatively, one can directly assign new pointers to the closest
centers, without bothering with a ::VlKMeans object.

There are several considerations that may impact the performance of
KMeans. First, since K-means is usually based local optimization
algorithm, the **initialization method** is important. The following
initialization methods are supported:

Method         | Function                                | Description
---------------|-----------------------------------------|------------------------------
Random samples | ::vl_kmeans_seed_centers_with_rand_data | Random data points
K-means++      | ::vl_kmeans_seed_centers_plus_plus      | Random selection biased towards diversity
Custom         | ::vl_kmeans_set_centers                 | Choose centers (useful to run quantization oly)

See @ref kmeans-init for further details. The initialization methods
use a randomized selection of the data points; the random number
generator seed is controlled by ::vl_rand_seed.

The second important choice is the **optimization algorithm**. The
following optimization algorithms are supported:

Algorithm   | Symbol           | See               | Description
------------|------------------|-------------------|----------------------------------------
Lloyd       | ::VlKMeansLloyd  | @ref kmeans-lloyd | Alternate EM-style optimization
Elka
n       | ::VlKMeansElkan  | @ref kmeans-elkan | A speedup using triangular inequalities
ANN         | ::VlKMeansANN    | @ref kmeans-ann   | A speedup using approximated nearest neighbors

See the relative sections for further details. These algorithm are
iterative, and stop when either a **maximum number of iterations**
(::vl_kmeans_set_max_num_iterations) is reached, or when the energy
changes sufficiently slowly in one iteration (::vl_kmeans).


Parallel computation...

*/

/**
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@page kmeans-fundamentals K-means fundamentals
@tableofcontents
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

Given $n$ points $\bx_1,\dots,\bx_n \in \real^d$, the goal of K-means
is find $K$ `centers` $\bc_1,\dots,\bc_m \in \real^d$ and
`assignments` $q_1,\dots,q_n \in \{1,\dots,K\}$ of the points to the
centers such that the sum of distances

\[
 E(\bc_1,\dots,\bc_k,q_1,\dots,q_n)
 = \sum_{i=1}^n \|\bx_i - \bc_{q_i} \|_p^p
\]

is minimized. $K$-means is obtained for the case $p=2$ ($l^2$ norm),
because in this case the optimal centers are the means of the input
vectors assigned to them. Here the generalization $p=1$ ($l^1$ norm)
will also be considered.

Up to normalization, the K-means objective $E$ is also the average
reconstruction error if the original points are approximated with the<commit_msg>kmeans: doc: minor fix<commit_after>/** @file kmeans.c
 ** @brief K-means - Declaration
 ** @author <NAME>, <NAME>
 **/

/*
Copyright (C) 2007-12 <NAME> and <NAME>.
Copyright (C) 2013 <NAME> and <NAME>.
All rights reserved.

This file is part of the VLFeat library and is made available under
the terms of the BSD license (see the COPYING file).
*/

/**
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@page kmeans K-means clustering
@author <NAME>
@author <NAME>
@tableofcontents
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

@ref kmeans.h implements a number of algorithm for **K-means
quantization**: Lloyd @cite{lloyd82least}, an accelerated version by
Elkan @cite{elkan03using}, and a large scale algorithm based on
Approximate Nearest Neighbors (ANN). All algorithms support @c float
or @c double data and can use the $l^1$ or the $l^2$ distance for
clustering. Furthermore, all algorithms can take advantage of multiple
CPU cores.

Please see @subpage kmeans-fundamentals for a technical description of
K-means and of the algorithms implemented here.

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@section kmeans-starting Getting started
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

The goal of K-means is to partition a dataset into $K$
&ldquo;compact&rdquo; clusters. The following example demonstrates
using @ref kmeans.h in the C programming language to partition @c
numData @c float vectors into compute @c numCenters clusters using
Lloyd's algorithm:

@code
#include <vl/kmeans.h>
double energy ;
double * centers ;

// Use float data and the L2 distance for clustering
KMeans * kmeans = vl_kmeans_new (VLDistanceL2, VL_TYPE_FLOAT) ;

// Use Lloyd algorithm
vl_kmeans_set_algorithm (kmeans, VlKMeansLloyd) ;

// Initialize the cluster centers by randomly sampling the data
vl_kmeans_seed_centers_with_rand_data (kmeans, data, dimension, numData, numCenters) ;

// Run at most 100 iterations of cluster refinement using Lloyd algorithm
vl_kmeans_set_max_num_iterations (kmeans, 100) ;
vl_kmeans_refine_centers (kmeans, data, numData) ;

// Obtain the energy of the solution
energy = vl_kmeans_get_energy(kmeans) ;

// Obtain the cluster centers
centers = vl_kmeans_get_centers(kmeans) ;
@endcode

Once the centers have been obtained, new data points can be assigned
to clusters by using the ::vl_kmeans_quantize function:

@code
vl_uint32 * assignments = vl_malloc(sizeof(vl_uint32) * numData) ;
float * distances = vl_malloc(sizeof(float) * numData) ;
vl_kmeans_quantize(kmeans, assignments, distances, data, numData) ;
@endcode

Alternatively, one can directly assign new pointers to the closest
centers, without bothering with a ::VlKMeans object.

There are several considerations that may impact the performance of
KMeans. First, since K-means is usually based local optimization
algorithm, the **initialization method** is important. The following
initialization methods are supported:

Method         | Function                                | Description
---------------|-----------------------------------------|-----------------------------------------------
Random samples | ::vl_kmeans_seed_centers_with_rand_data | Random data points
K-means++      | ::vl_kmeans_seed_centers_plus_plus      | Random selection biased towards diversity
Custom         | ::vl_kmeans_set_centers                 | Choose centers (useful to run quantization only)

See @ref kmeans-init for further details. The initialization methods
use a randomized selection of the data points; the random number
generator seed is controlled by ::vl_rand_seed.

The second important choice is the **optimization algorithm**. The
following optimization algorithms are supported:

Algorithm   | Symbol           | See               | Description
------------|------------------|-------------------|-----------------------------------------------
Lloyd       | ::VlKMeansLloyd  | @ref kmeans-lloyd | Alternate EM-style optimization
Elkan       | ::VlKMeansElkan  | @ref kmeans-elkan | A speedup using triangular inequalities
ANN         | ::VlKMeansANN    | @ref kmeans-ann   | A speedup using approximated nearest neighbors

See the relative sections for further details. These algorithm are
iterative, and stop when either a **maximum number of iterations**
(::vl_kmeans_set_max_num_iterations) is reached, or when the energy
changes sufficiently slowly in one iteration (::vl_kmeans).

Parallel computation...
*/

/**
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->
@page kmeans-fundamentals K-means fundamentals
@tableofcontents
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->

Given $n$ points $\bx_1,\dots,\bx_n \in \real^d$, the goal of K-means
is find $K$ `centers` $\bc_1,\dots,\bc_m \in \real^d$ and
`assignments` $q_1,\dots,q_n \in \{1,\dots,K\}$ of the points to the
centers such that the sum of distances

\[
 E(\bc_1,\dots,\bc_k,q_1,\dots,q_n)
 = \sum_{i=1}^n \|\bx_i - \bc_{q_i} \|_p^p
\]

is minimized. $K$-means is obtained for the case $p=2$ ($l^2$ norm),
because in this case the optimal centers are the means of the input
vectors assigned to them. Here the generalization $p=1$ ($l^1$ norm)
will also be considered.

Up to normalization, the K-means objective $E$ is also the average
reconstruction error if the original points are approximated with the
{'fraction_non_alphanumeric': 0.18373968665986837, 'fraction_numerical': 0.007230926114767776, 'mean_word_length': 3.8053452115812916, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1716335', 'n_tokens_mistral': 3187, 'n_tokens_neox': 2924, 'n_words': 1135}