K-means clustering

Standard algorithm (naive k-means)

The most common algorithm uses an iterative refinement technique. Due to its ubiquity, it is often called "the k-means algorithm"; it is also referred to as Lloyd's algorithm, particularly in the computer science community. It is sometimes also referred to as "naïve k-means", because there exist much faster alternatives.^[7]

Given an initial set of k means m₁⁽¹⁾, ..., m_k⁽¹⁾ (see below), the algorithm proceeds by alternating between two steps:^[8]

1. Assignment step: Assign each observation to the cluster with the nearest mean (centroid): that with the least squared Euclidean distance.^[9] (Mathematically, this means partitioning the observations according to the Voronoi diagram generated by the means.) $${\displaystyle S_{i}^{(t)}=\left\{x_{p}:\left\|x_{p}-m_{i}^{(t)}\right\|^{2}\leq \left\|x_{p}-m_{j}^{(t)}\right\|^{2}\ \forall j,1\leq j\leq k\right\},}$$ where each ${\displaystyle x_{p}}$ is assigned to exactly one ${\displaystyle S^{(t)}}$, even if it could be assigned to two or more of them.
2. Update step: Recalculate means (centroids) for observations assigned to each cluster. This is also called refitting. $${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$$

The objective function in k-means is the WCSS (within cluster sum of squares). After each iteration, the WCSS monotonically decreases, giving a nonnegative monotonically decreasing sequence. This guarantees that the k-means always converges, but not necessarily to the global optimum.

The algorithm has converged when the assignments no longer change or equivalently, when the WCSS has become stable. The algorithm is not guaranteed to find the optimal cluster assignment.^[10]

The algorithm is often presented as assigning objects to the nearest cluster by distance. Using a different distance function other than (squared) Euclidean distance may prevent the algorithm from converging. Various modifications of k-means such as spherical k-means and k-medoids have been proposed to allow using other distance measures.

Pseudocode

The below pseudocode outlines the implementation of the standard k-means clustering algorithm. Initialization of centroids, distance metric between points and centroids, and the calculation of new centroids are design choices and will vary with different implementations. In this example pseudocode, distance() returns the distance between the specified points.

function kmeans(k, points) is
    // Initialize centroids
    centroids ← list of k starting centroids
    converged ← false

    while converged == false do
        // Create empty clusters
        clusters ← list of k empty lists

        // Assign each point to the nearest centroid
        for i ← 0 to length(points) - 1 do
            point ← points[i]
            closestIndex ← 0
            minDistance ← distance(point, centroids[0])
            for j ← 1 to k - 1 do
                d ← distance(point, centroids[j])
                if d < minDistance THEN
                    minDistance ← d
                    closestIndex ← j
            clusters[closestIndex].append(point)

        // Recalculate centroids as the mean of each cluster
        newCentroids ← empty list
        for i ← 0 to k - 1 do
            newCentroid ← calculateCentroid(clusters[i])
            newCentroids.append(newCentroid)

        // Check for convergence
        if newCentroids == centroids THEN
            converged ← true
        else
            centroids ← newCentroids

    return clusters

Complexity

Finding the optimal solution to the k-means clustering problem for observations in d dimensions is:

• NP-hard in general Euclidean space (of d dimensions) even for two clusters,^[16][17]
• NP-hard for a general number of clusters k even in the plane,^[18]
• if k and d (the dimension) are fixed, the problem can be exactly solved in time ${\displaystyle O(n^{dk+1})}$, where n is the number of entities to be clustered.^[19]

Thus, a variety of heuristic algorithms such as Lloyd's algorithm given above are generally used.

The running time of Lloyd's algorithm (and most variants) is ${\displaystyle O(nkdi)}$,^[10][20] where:

• n is the number of d-dimensional vectors (to be clustered)
• k the number of clusters
• i the number of iterations needed until convergence.

On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. Lloyd's algorithm is therefore often considered to be of "linear" complexity in practice, although it is in the worst case superpolynomial when performed until convergence.^[21]

• In the worst-case, Lloyd's algorithm needs ${\displaystyle i=2^{\Omega ({\sqrt {n}})}}$ iterations, so that the worst-case complexity of Lloyd's algorithm is superpolynomial.^[21]
• Lloyd's k-means algorithm has polynomial smoothed running time. It is shown that^[15] for arbitrary set of n points in ${\displaystyle [0,1]^{d}}$, if each point is independently perturbed by a normal distribution with mean 0 and variance ${\displaystyle \sigma ^{2}}$, then the expected running time of k-means algorithm is bounded by ${\displaystyle O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})}$, which is a polynomial in n, k, d and ${\displaystyle 1/\sigma }$.
• Better bounds are proven for simple cases. For example, it is shown that the running time of k-means algorithm is bounded by ${\displaystyle O(dn^{4}M^{2})}$ for n points in an integer lattice ${\displaystyle \{1,\dots ,M\}^{d}}$.^[22]

Lloyd's algorithm is the standard approach for this problem. However, it spends a lot of processing time computing the distances between each of the k cluster centers and the n data points. Since points usually stay in the same clusters after a few iterations, much of this work is unnecessary, making the naïve implementation very inefficient. Some implementations use caching and the triangle inequality in order to create bounds and accelerate Lloyd's algorithm.^{[23][10][24][25][26][27]}

Optimal number of clusters

Finding the optimal number of clusters (k) for k-means clustering is a crucial step to ensure that the clustering results are meaningful and useful.^[28] Several techniques are available to determine a suitable number of clusters. Here are some of commonly used methods:

• Elbow method (clustering): This method involves plotting the explained variation as a function of the number of clusters, and picking the elbow of the curve as the number of clusters to use.^[29] However, the notion of an "elbow" is not well-defined and this is known to be unreliable.^[30]
• Silhouette (clustering): Silhouette analysis measures the quality of clustering and provides an insight into the separation distance between the resulting clusters.^[31] A higher silhouette score indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters.
• Gap statistic: The Gap Statistic compares the total within intra-cluster variation for different values of k with their expected values under null reference distribution of the data.^[32] The optimal k is the value that yields the largest gap statistic.
• Davies–Bouldin index: The Davies-Bouldin index is a measure of the how much separation there is between clusters.^[33] Lower values of the Davies-Bouldin index indicate a model with better separation.
• Calinski-Harabasz index: This Index evaluates clusters based on their compactness and separation. The index is calculated using the ratio of between-cluster variance to within-cluster variance, with higher values indicate better-defined clusters.^[34]
• Rand index: It calculates the proportion of agreement between the two clusters, considering both the pairs of elements that are correctly assigned to the same or different clusters.^[35] Higher values indicate greater similarity and better clustering quality. To provide a more accurate measure, the Adjusted Rand Index (ARI), introduced by Hubert and Arabie in 1985, corrects the Rand Index by adjusting for the expected similarity of all pairings due to chance.^[36]

Variations

• Jenks natural breaks optimization: k-means applied to univariate data
• k-medians clustering uses the median in each dimension instead of the mean, and this way minimizes ${\displaystyle L_{1}}$ norm (Taxicab geometry).
• k-medoids (also: Partitioning Around Medoids, PAM) uses the medoid instead of the mean, and this way minimizes the sum of distances for arbitrary distance functions.
• Fuzzy C-Means Clustering is a soft version of k-means, where each data point has a fuzzy degree of belonging to each cluster.
• Gaussian mixture models trained with expectation–maximization algorithm (EM algorithm) maintains probabilistic assignments to clusters, instead of deterministic assignments, and multivariate Gaussian distributions instead of means.
• k-means++ chooses initial centers in a way that gives a provable upper bound on the WCSS objective.
• The filtering algorithm uses k-d trees to speed up each k-means step.^[37]
• Some methods attempt to speed up each k-means step using the triangle inequality.^{[24][25][26][38][27]}
• Escape local optima by swapping points between clusters.^[10]
• The Spherical k-means clustering algorithm is suitable for textual data.^[39]
• Hierarchical variants such as Bisecting k-means,^[40] X-means clustering^[41] and G-means clustering^[42] repeatedly split clusters to build a hierarchy, and can also try to automatically determine the optimal number of clusters in a dataset.
• Internal cluster evaluation measures such as cluster silhouette can be helpful at determining the number of clusters.
• Minkowski weighted k-means automatically calculates cluster specific feature weights, supporting the intuitive idea that a feature may have different degrees of relevance at different features.^[43] These weights can also be used to re-scale a given data set, increasing the likelihood of a cluster validity index to be optimized at the expected number of clusters.^[44]
• Mini-batch k-means: k-means variation using "mini batch" samples for data sets that do not fit into memory.^[45]
• Otsu's method

Hartigan–Wong method

Hartigan and Wong's method^[10] provides a variation of k-means algorithm which progresses towards a local minimum of the minimum sum-of-squares problem with different solution updates. The method is a local search that iteratively attempts to relocate a sample into a different cluster as long as this process improves the objective function. When no sample can be relocated into a different cluster with an improvement of the objective, the method stops (in a local minimum). In a similar way as the classical k-means, the approach remains a heuristic since it does not necessarily guarantee that the final solution is globally optimum.

Let ${\displaystyle \varphi (S_{j})}$ be the individual cost of ${\displaystyle S_{j}}$ defined by ${\textstyle \sum _{x\in S_{j}}(x-\mu _{j})^{2}}$, with ${\displaystyle \mu _{j}}$ the center of the cluster.

Assignment step

Hartigan and Wong's method starts by partitioning the points into random clusters ${\displaystyle \{S_{j}\}_{j\in \{1,\cdots k\}}}$.

Update step

Next it determines the ${\displaystyle n,m\in \{1,\ldots ,k\}}$ and ${\displaystyle x\in S_{n}}$ for which the following function reaches a maximum $${\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).}$$ For the ${\displaystyle x,n,m}$ that reach this maximum, ${\displaystyle x}$ moves from the cluster ${\displaystyle S_{n}}$ to the cluster ${\displaystyle S_{m}}$.

Termination

The algorithm terminates once ${\displaystyle \Delta (m,n,x)}$ is less than zero for all ${\displaystyle x,n,m}$.

Different move acceptance strategies can be used. In a first-improvement strategy, any improving relocation can be applied, whereas in a best-improvement strategy, all possible relocations are iteratively tested and only the best is applied at each iteration. The former approach favors speed, whether the latter approach generally favors solution quality at the expense of additional computational time. The function ${\displaystyle \Delta }$ used to calculate the result of a relocation can also be efficiently evaluated by using equality^[46]

$${\displaystyle \Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.}$$

Global optimization and meta-heuristics

The classical k-means algorithm and its variations are known to only converge to local minima of the minimum-sum-of-squares clustering problem defined as $${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.}$$ Many studies have attempted to improve the convergence behavior of the algorithm and maximize the chances of attaining the global optimum (or at least, local minima of better quality). Initialization and restart techniques discussed in the previous sections are one alternative to find better solutions. More recently, global optimization algorithms based on branch-and-bound and semidefinite programming have produced ‘’provenly optimal’’ solutions for datasets with up to 4,177 entities and 20,531 features.^[47] As expected, due to the NP-hardness of the subjacent optimization problem, the computational time of optimal algorithms for k-means quickly increases beyond this size. Optimal solutions for small- and medium-scale still remain valuable as a benchmark tool, to evaluate the quality of other heuristics. To find high-quality local minima within a controlled computational time but without optimality guarantees, other works have explored metaheuristics and other global optimization techniques, e.g., based on incremental approaches and convex optimization,^[48] random swaps^[49] (i.e., iterated local search), variable neighborhood search^[50] and genetic algorithms.^[51][52] It is indeed known that finding better local minima of the minimum sum-of-squares clustering problem can make the difference between failure and success to recover cluster structures in feature spaces of high dimension.^[52]

Biology

In biological applications, the limitations of standard k-means clustering are often addressed by adapting the distance measures used and objective functions to better reflect the structure of experimental data. Rather than relying on Euclidean distance and variance-based measures of cluster scatter, alternative similarity metrics such as the Jaccard index are sometimes used when analyzing genomic datasets with k-means. In these contexts, clustering may be performed directly on distance matrices, and medoids (representative data points that have the smallest average distance to every other point within a cluster) may be selected as cluster centers instead of arithmetic means. This allows clustering methods to capture patterns of shared genomic features or co-occurrence that are not well represented in a traditional Euclidean analysis.^[55]

Clustering is widely used in biological data analysis to identify patterns in high-dimensional datasets such as gene expression profiles and genomic interaction matrices. Techniques such as k-means clustering partition observations into groups based on similarity, allowing researchers to detect structure in complex datasets. In gene expression studies, clustering is commonly used to group genes with similar expression profiles, often revealing co-regulated genes and underlying biological interactions.^[56]

In addition to gene expression analysis, clustering approaches are applied to chromatin interaction data to identify regions of coordinated activity. Similarity measures such as the Jaccard index can be used to quantify shared features between observations, and clustering of the resulting distance matrices can reveal structural organization within the genome. These patterns are commonly visualized using heatmaps, where clustered regions correspond to domains of interaction or co-segregation, providing insight into the regulatory organization of the genome.^[55] In such analyses, clustering of similarity or co-detection matrices can reveal groups of genomic windows that exhibit coordinated behavior across experimental conditions.^[55]

Clustering methods provide a practical method for uncovering biologically meaningful structure from complex datasets. By grouping observations with similar patterns of genomic detection, expression, or interaction, these techniques can reveal functional relationships, spatial organization within the nucleus, and regulatory behavior. In many applications, the resulting clusters correspond to distinct biological states or structural domains, further illustrating the broad applicability of k-means clustering.^[56]

Vector quantization

Vector quantization, a technique commonly used in signal processing and computer graphics, involves reducing the color palette of an image to a fixed number of colors, known as k. One popular method for achieving vector quantization is through k-means clustering. In this process, k-means is applied to the color space of an image to partition it into k clusters, with each cluster representing a distinct color in the image. This technique is particularly useful in image segmentation tasks, where it helps identify and group similar colors together.

Example: In the field of computer graphics, k-means clustering is often employed for color quantization in image compression. By reducing the number of colors used to represent an image, file sizes can be significantly reduced without significant loss of visual quality. For instance, consider an image with millions of colors. By applying k-means clustering with k set to a smaller number, the image can be represented using a more limited color palette, resulting in a compressed version that consumes less storage space and bandwidth. Other uses of vector quantization include non-random sampling, as k-means can easily be used to choose k different but prototypical objects from a large data set for further analysis.

Cluster analysis

Cluster analysis, a fundamental task in data mining and machine learning, involves grouping a set of data points into clusters based on their similarity. k-means clustering is a popular algorithm used for partitioning data into k clusters, where each cluster is represented by its centroid.

However, the pure k-means algorithm is not very flexible, and as such is of limited use (except for when vector quantization as above is actually the desired use case). In particular, the parameter k is known to be hard to choose (as discussed above) when not given by external constraints. Another limitation is that it cannot be used with arbitrary distance functions or on non-numerical data. For these use cases, many other algorithms are superior.

Example: In marketing, k-means clustering is frequently employed for market segmentation, where customers with similar characteristics or behaviors are grouped together. For instance, a retail company may use k-means clustering to segment its customer base into distinct groups based on factors such as purchasing behavior, demographics, and geographic location. These customer segments can then be targeted with tailored marketing strategies and product offerings to maximize sales and customer satisfaction.

Feature learning

k-means clustering has been used as a feature learning (or dictionary learning) step, in either (semi-)supervised learning or unsupervised learning.^[57] The basic approach is first to train a k-means clustering representation, using the input training data (which need not be labelled). Then, to project any input datum into the new feature space, an "encoding" function, such as the thresholded matrix-product of the datum with the centroid locations, computes the distance from the datum to each centroid, or simply an indicator function for the nearest centroid,^[57][58] or some smooth transformation of the distance.^[59] Alternatively, transforming the sample-cluster distance through a Gaussian RBF, obtains the hidden layer of a radial basis function network.^[60]

This use of k-means has been successfully combined with simple, linear classifiers for semi-supervised learning in NLP (specifically for named-entity recognition)^[61] and in computer vision. On an object recognition task, it was found to exhibit comparable performance with more sophisticated feature learning approaches such as autoencoders and restricted Boltzmann machines.^[59] However, it generally requires more data, for equivalent performance, because each data point only contributes to one "feature".^[57]

Example: In natural language processing (NLP), k-means clustering has been integrated with simple linear classifiers for semi-supervised learning tasks such as named-entity recognition (NER). By first clustering unlabeled text data using k-means, meaningful features can be extracted to improve the performance of NER models. For instance, k-means clustering can be applied to identify clusters of words or phrases that frequently co-occur in the input text, which can then be used as features for training the NER model. This approach has been shown to achieve comparable performance with more complex feature learning techniques such as autoencoders and restricted Boltzmann machines, albeit with a greater requirement for labeled data.

Big Data Parallelization

Standard Lloyd’s algorithm is inherently sequential. It has an effective time complexity of O(nkdi), which becomes a bottleneck as the number of data points (n) or dimensions (d) increases. This can be inefficient when used with massive, multidimensional data sets like social networks. Various parallelization strategies have been developed to distribute the workload across multi-core processors, GPUs, and distributed clusters.

• Shared Memory Model (OpenMP): This approach divides the work between CPU threads for the reassignment step of the process. These threads independently calculate distances to centroids. Partial sums and counts from each thread are aggregated to compute the new centroids for the next iteration. ^[62]

• GPU Parallelization (OpenACC): Unlike the OpenMP implementation, the OpenACC program’s parallel directive is called at each necessary step instead of at the very beginning. This exploits the SIMT (Single Instruction, Multiple Threads) architecture of GPUs to perform thousands of distance calculations simultaneously.^[62]

We see that in both parallel versions; efficiency is greatly increased for large datasets. This speedup is significant in the OpenACC implementation, due to the massively parallel nature of GPU architectures.

Astronomy

Modern astronomical surveys like APOGEE and the Gaia catalog collect spectroscopic and photometric data for millions of stars, making manual classification impractical at scale. K-means clustering has been applied to this data to automatically identify distinct stellar populations based on properties like luminosity, temperature, color, and chemical abundance.^[63]

One major application is identifying stellar populations through chemical tagging. Stars that form together in the same cluster share similar chemical compositions, so clustering algorithms applied to abundance data can recover these groupings even after the stars have spread throughout the galaxy. Studies using k-means on APOGEE infrared spectra measured abundances of up to 13 elements and successfully distinguished known star clusters from surrounding field stars.^[63] This has also revealed populations with unusual abundance patterns that would be difficult to catch through manual inspection.

K-means has also been combined with dimensionality reduction techniques to classify large numbers of unlabeled survey objects by separating stars, galaxies, and quasars based on their observed light properties. Labels from confirmed examples are then propagated to nearby cluster members. This approach has achieved accuracy comparable to fully supervised methods while requiring far fewer labeled examples, which makes it well suited for the scale of modern sky surveys.^[64]

K-means++ and Scalable Initialization

Proper initialization is very important when it comes to finding global optimum in a clustering algorithm. Random initialization is often used for k means clustering, but this can result in poor cluster quality.^[65] This is why the k-means++ initialization algorithm was developed.^[65] The algorithm attempts to find initial centers that are as close to possible to the global optimum, reducing computing time and producing more accurate clusters.^[65]

The k-means++ algorithm works by spreading out the initial cluster centers. It selects the first center uniformly at random from the dataset. Each subsequent center is chosen stochastically, with the probability of a point being selected proportional to its contribution to the overall error.^[65] This method achieves an O(log k) approximation of the optimum solution.^[65]

The primary drawback of standard k-means++ is its inherent sequential nature. To find k initial centers, the algorithm must make k separate passes over the data, as the selection of each new center depends on the previous choices.^[66] This becomes prohibitively slow when clustering massive datasets into a large number of clusters.^[66]

To overcome these limitations, researchers developed k-means||, a parallel version of k-means++.^[66] Instead of sampling a single point per pass, k-means|| uses an oversampling factor ℓ = Ω (k) to sample multiple points in each round.^[66] The algorithm drastically reduces the number of passes required, obtaining a nearly optimal set of centers with a time complexity of O(log n).^[66] In practice, as few as five rounds are needed to reach a high-quality solution. After several rounds, the algorithm typically has O(log n) intermediate centers.^[66] These are then assigned weights based on how many points are close to them and re-clustered, often using standard k-means++, to reduce the final set to exact k centers.^[66]

Recent developments

Recent advancements in the application of k-means clustering have explored the integration of k-means clustering with deep learning methods, such as convolutional neural networks (CNNs) and recurrent neural networks (RNNs), to enhance the performance of various tasks in computer vision, natural language processing, and other domains.

Gaussian mixture model

The slow "standard algorithm" for k-means clustering, and its associated expectation–maximization algorithm, is a special case of a Gaussian mixture model, specifically, the limiting case when fixing all covariances to be diagonal, equal and have infinitesimal small variance.^[67]: 850 Instead of small variances, a hard cluster assignment can also be used to show another equivalence of k-means clustering to a special case of "hard" Gaussian mixture modelling.^{[68]: 354, 11.4.2.5} This does not mean that it is efficient to use Gaussian mixture modelling to compute k-means, but just that there is a theoretical relationship, and that Gaussian mixture modelling can be interpreted as a generalization of k-means; on the contrary, it has been suggested to use k-means clustering to find starting points for Gaussian mixture modelling on difficult data.^[67]: 849

k-SVD

Another generalization of the k-means algorithm is the k-SVD algorithm, which estimates data points as a sparse linear combination of "codebook vectors". k-means corresponds to the special case of using a single codebook vector, with a weight of 1.^[69]

Principal component analysis

The relaxed solution of k-means clustering, specified by the cluster indicators, is given by principal component analysis (PCA).^[70][71] The intuition is that k-means describe spherically shaped (ball-like) clusters. If the data has 2 clusters, the line connecting the two centroids is the best 1-dimensional projection direction, which is also the first PCA direction. Cutting the line at the center of mass separates the clusters (this is the continuous relaxation of the discrete cluster indicator). If the data have three clusters, the 2-dimensional plane spanned by three cluster centroids is the best 2-D projection. This plane is also defined by the first two PCA dimensions. Well-separated clusters are effectively modelled by ball-shaped clusters and thus discovered by k-means. Non-ball-shaped clusters are hard to separate when they are close. For example, two half-moon shaped clusters intertwined in space do not separate well when projected onto PCA subspace. k-means should not be expected to do well on this data.^[72] It is straightforward to produce counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.^[73]

Mean shift clustering

Basic mean shift clustering algorithms maintain a set of data points the same size as the input data set. Initially, this set is copied from the input set. All points are then iteratively moved towards the mean of the points surrounding them. By contrast, k-means restricts the set of clusters to k clusters, usually much less than the number of points in the input data set, using the mean of all points in the prior cluster that are closer to that point than any other for the centroid (e.g. within the Voronoi partition of each updating point). A mean shift algorithm that is similar then to k-means, called likelihood mean shift, replaces the set of points undergoing replacement by the mean of all points in the input set that are within a given distance of the changing set.^[74] An advantage of mean shift clustering over k-means is the detection of an arbitrary number of clusters in the data set, as there is not a parameter determining the number of clusters. Mean shift can be much slower than k-means, and still requires selection of a bandwidth parameter.

Independent component analysis

Under sparsity assumptions and when input data is pre-processed with the whitening transformation, k-means produces the solution to the linear independent component analysis (ICA) task. This aids in explaining the successful application of k-means to feature learning.^[75]

Bilateral filtering

k-means implicitly assumes that the ordering of the input data set does not matter. The bilateral filter is similar to k-means and mean shift in that it maintains a set of data points that are iteratively replaced by means. However, the bilateral filter restricts the calculation of the (kernel weighted) mean to include only points that are close in the ordering of the input data.^[74] This makes it applicable to problems such as image denoising, where the spatial arrangement of pixels in an image is of critical importance.

Free Software/Open Source

The following implementations are available under Free/Open Source Software licenses, with publicly available source code.

• Accord.NET contains C# implementations for k-means, k-means++ and k-modes.
• ALGLIB contains parallelized C++ and C# implementations for k-means and k-means++.
• AOSP contains a Java implementation for k-means.
• CrimeStat implements two spatial k-means algorithms, one of which allows the user to define the starting locations.
• ELKI contains k-means (with Lloyd and MacQueen iteration, along with different initializations such as k-means++ initialization) and various more advanced clustering algorithms.
• Smile contains k-means and various more other algorithms and results visualization (for java, kotlin and scala).
• Julia contains a k-means implementation in the JuliaStats Clustering package.
• KNIME contains nodes for k-means and k-medoids.
• Mahout contains a MapReduce based k-means.
• mlpack contains a C++ implementation of k-means.
• Octave contains k-means.
• OpenCV contains a k-means implementation.
• Orange includes a component for k-means clustering with automatic selection of k and cluster silhouette scoring.
• PSPP contains k-means, The QUICK CLUSTER command performs k-means clustering on the dataset.
• R contains three k-means variations.
• SciPy and scikit-learn contain multiple k-means implementations.
• Spark MLlib implements a distributed k-means algorithm.
• Torch contains an unsup package that provides k-means clustering.
• Weka contains k-means and x-means.

Proprietary

The following implementations are available under proprietary license terms, and may not have publicly available source code.