''k''-means clustering is a method of
vector quantization
Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by di ...
, originally from
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...
, that aims to
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
''n'' observations into ''k'' clusters in which each observation belongs to the
cluster
may refer to:
Science and technology Astronomy
* Cluster (spacecraft), constellation of four European Space Agency spacecraft
* Asteroid cluster, a small asteroid family
* Cluster II (spacecraft), a European Space Agency mission to study t ...
with the nearest
mean
There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value (magnitude and sign) of a given data set.
For a data set, the ''arithme ...
(cluster centers or cluster
centroid
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ob ...
), serving as a prototype of the cluster. This results in a partitioning of the data space into
Voronoi cell
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed t ...
s. ''k''-means clustering minimizes within-cluster variances (
squared Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two Point (geometry), points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theo ...
s), but not regular Euclidean distances, which would be the more difficult
Weber problem
In geometry, the Weber problem, named after Alfred Weber, is one of the most famous problems in location theory. It requires finding a point in the plane that minimizes the sum of the transportation costs from this point to ''n'' destination point ...
: the mean optimizes squared errors, whereas only the
geometric median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances ...
minimizes Euclidean distances. For instance, better Euclidean solutions can be found using
k-medians
In statistics, ''k''-medians clusteringP. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridg ...
and
k-medoids
The -medoids problem is a clustering problem similar to -means. The name was coined by Leonard Kaufman and Peter J. Rousseeuw with their PAM algorithm. Both the -means and -medoids algorithms are partitional (breaking the dataset up into group ...
.
The problem is computationally difficult (
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
); however, efficient
heuristic algorithm
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ...
s converge quickly to a
local optimum
In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which i ...
. These are usually similar to the
expectation-maximization algorithm for
mixtures
In chemistry, a mixture is a material made up of two or more different chemical substances which are not chemically bonded. A mixture is the physical combination of two or more substances in which the identities are retained and are mixed in the ...
of
Gaussian distributions via an iterative refinement approach employed by both ''k-means'' and ''Gaussian mixture modeling''. They both use cluster centers to model the data; however, ''k''-means clustering tends to find clusters of comparable spatial extent, while the Gaussian mixture model allows clusters to have different shapes.
The unsupervised k-means algorithm has a loose relationship to the
''k''-nearest neighbor classifier, a popular supervised
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
technique for classification that is often confused with ''k''-means due to the name. Applying the 1-nearest neighbor classifier to the cluster centers obtained by ''k''-means classifies new data into the existing clusters. This is known as
nearest centroid classifier
In machine learning, a nearest centroid classifier or nearest prototype classifier is a classification model that assigns to observations the label of the class of training samples whose mean (centroid) is closest to the observation. When applied ...
or
Rocchio algorithm The Rocchio algorithm is based on a method of relevance feedback found in information retrieval systems which stemmed from the SMART Information Retrieval System developed between 1960 and 1964. Like many other retrieval systems, the Rocchio algori ...
.
Description
Given a set of observations (x
1, x
2, ..., x
''n''), where each observation is a ''d''-dimensional real vector, ''k''-means clustering aims to partition the ''n'' observations into ''k'' (≤ ''n'') sets S = so as to minimize the within-cluster sum of squares (WCSS) (i.e.
variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers ...
). Formally, the objective is to find:
where ''μ
i'' is the mean of points in ''S
i''. This is equivalent to minimizing the pairwise squared deviations of points in the same cluster:
The equivalence can be deduced from identity
. Since the total variance is constant, this is equivalent to maximizing the sum of squared deviations between points in ''different'' clusters (between-cluster sum of squares, BCSS),.
This deterministic relationship is also related to the
law of total variance In probability theory, the law of total variance or variance decomposition formula or conditional variance formulas or law of iterated variances also known as Eve's law, states that if X and Y are random variables on the same probability space, and ...
in probability theory.
History
The term "''k''-means" was first used by James MacQueen in 1967,
though the idea goes back to
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Unive ...
in 1956. The standard algorithm was first proposed by Stuart Lloyd of
Bell Labs
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial research and scientific development company owned by mult ...
in 1957 as a technique for
pulse-code modulation
Pulse-code modulation (PCM) is a method used to digitally represent sampled analog signals. It is the standard form of digital audio in computers, compact discs, digital telephony and other digital audio applications. In a PCM stream, the ...
, although it was not published as a journal article until 1982.
[ Published in journal much later: ] In 1965, Edward W. Forgy published essentially the same method, which is why it is sometimes referred to as the Lloyd–Forgy algorithm.
Algorithms
Standard algorithm (naive k-means)
![K-means_convergence](https://upload.wikimedia.org/wikipedia/commons/e/ea/K-means_convergence.gif)
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 In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of t ...
, particularly in the computer science community. It is sometimes also referred to as "naïve ''k''-means", because there exist much faster alternatives.
Given an initial set of ''k'' means ''m''
1(1),...,''m
k''
(1) (see below), the algorithm proceeds by alternating between two steps:
: Assignment step: Assign each observation to the cluster with the nearest mean: that with the least squared
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
. (Mathematically, this means partitioning the observations according to the
Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
generated by the means.)
::
:: where each
is assigned to exactly one
, even if it could be assigned to two or more of them.
: Update step: Recalculate means (
centroids
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any o ...
) for observations assigned to each cluster.
::
The algorithm has converged when the assignments no longer change. The algorithm is not guaranteed to find the optimum.
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.
Initialization methods
Commonly used initialization methods are Forgy and Random Partition.
The Forgy method randomly chooses ''k'' observations from the dataset and uses these as the initial means. The Random Partition method first randomly assigns a cluster to each observation and then proceeds to the update step, thus computing the initial mean to be the centroid of the cluster's randomly assigned points. The Forgy method tends to spread the initial means out, while Random Partition places all of them close to the center of the data set. According to Hamerly et al.,
the Random Partition method is generally preferable for algorithms such as the ''k''-harmonic means and fuzzy ''k''-means. For expectation maximization and standard ''k''-means algorithms, the Forgy method of initialization is preferable. A comprehensive study by Celebi et al., however, found that popular initialization methods such as Forgy, Random Partition, and Maximin often perform poorly, whereas Bradley and Fayyad's approach performs "consistently" in "the best group" and
''k''-means++ performs "generally well".
File:K Means Example Step 1.svg, 1. ''k'' initial "means" (in this case ''k''=3) are randomly generated within the data domain (shown in color).
File:K Means Example Step 2.svg, 2. ''k'' clusters are created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
generated by the means.
File:K Means Example Step 3.svg, 3. The centroid
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ob ...
of each of the ''k'' clusters becomes the new mean.
File:K Means Example Step 4.svg, 4. Steps 2 and 3 are repeated until convergence has been reached.
The algorithm does not guarantee convergence to the global optimum. The result may depend on the initial clusters. As the algorithm is usually fast, it is common to run it multiple times with different starting conditions. However, worst-case performance can be slow: in particular certain point sets, even in two dimensions, converge in exponential time, that is . These point sets do not seem to arise in practice: this is corroborated by the fact that the
smoothed running time of ''k''-means is polynomial.
The "assignment" step is referred to as the "expectation step", while the "update step" is a maximization step, making this algorithm a variant of the ''generalized''
expectation-maximization algorithm.
Complexity
Finding the optimal solution to the ''k''-means clustering problem for observations in ''d'' dimensions is:
*
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
in general
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
(of ''d'' dimensions) even for two clusters,
*
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
for a general number of clusters ''k'' even in the plane,
* if ''k'' and ''d'' (the dimension) are fixed, the problem can be exactly solved in time
, where ''n'' is the number of entities to be clustered.
Thus, a variety of
heuristic algorithm
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ...
s such as Lloyd's algorithm given above are generally used.
The running time of Lloyd's algorithm (and most variants) is
,
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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
superpolynomial when performed until convergence.
* In the worst-case, Lloyd's algorithm needs
iterations, so that the worst-case complexity of Lloyd's algorithm is
superpolynomial
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
.
* Lloyd's ''k''-means algorithm has polynomial smoothed running time. It is shown that
for arbitrary set of ''n'' points in
, if each point is independently perturbed by a normal distribution with mean and variance
, then the expected running time of -means algorithm is bounded by
, which is a polynomial in , , and
.
* Better bounds are proven for simple cases. For example, it is shown that the running time of ''k''-means algorithm is bounded by
for points in an
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid ...
.
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.
Variations
*
Jenks natural breaks optimization
The Jenks optimization method, also called the Jenks natural breaks classification method, is a data clustering method designed to determine the best arrangement of values into different classes. This is done by seeking to minimize each class's ave ...
: ''k''-means applied to univariate data
*
''k''-medians clustering uses the median in each dimension instead of the mean, and this way minimizes
norm (
Taxicab geometry
A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...
).
*
''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
Fuzzy clustering (also referred to as soft clustering or soft ''k''-means) is a form of clustering in which each data point can belong to more than one cluster.
Clustering or cluster analysis involves assigning data points to clusters such that ...
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
kd-tree
In computer science, a ''k''-d tree (short for ''k-dimensional tree'') is a space-partitioning data structure for organizing points in a ''k''-dimensional space. ''k''-d trees are a useful data structure for several applications, such as search ...
s to speed up each ''k''-means step.
* Some methods attempt to speed up each ''k''-means step using the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, but ...
.
* Escape local optima by swapping points between clusters.
* The Spherical ''k''-means clustering algorithm is suitable for textual data.
* Hierarchical variants such as Bisecting ''k''-means,
X-means clustering Determining the number of clusters in a data set, a quantity often labelled ''k'' as in the ''k''-means algorithm, is a frequent problem in data clustering, and is a distinct issue from the process of actually solving the clustering problem.
For a ...
and G-means clustering
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. 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.
* Mini-batch ''k''-means: ''k''-means variation using "mini batch" samples for data sets that do not fit into memory.
*
Otsu's method
In computer vision and image processing, Otsu's method, named after , is used to perform automatic image thresholding. In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes, foreground a ...
Hartigan–Wong method
Hartigan and Wong's method
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
be the individual cost of
defined by
, with
the center of the cluster.
Assignment step: Hartigan and Wong's method starts by partitioning the points into random clusters
.
Update step: Next it determines the
and
for which the following function reaches a maximum
:
For the
that reach this maximum,
moves from the cluster
to the cluster
.
Termination: The algorithm terminates once
is less than zero for all
.
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
used to calculate the result of a relocation can also be efficiently evaluated by using equality
:
Global optimization and metaheuristics
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
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
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate soluti ...
and
semidefinite programming Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive ...
have produced ‘’provenly optimal’’ solutions for datasets with up to 4,177 entities and 20,531 features. As expected, due to the
NP-hardness
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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
In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimiza ...
and other
global optimization
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the max ...
techniques, e.g., based on incremental approaches and convex optimization,
random swaps
(i.e.,
iterated local search
Iterated Local Search (ILS) is a term in applied mathematics and computer science
defining a modification of local search or hill climbing methods for solving discrete optimization problems.
Local search methods can get stuck in a local minimum, ...
),
variable neighborhood search Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997,
is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems.
It explores distant neighborhoods of the current incumbent sol ...
and
genetic algorithms
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
.
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.
Discussion
![K-means_convergence_to_a_local_minimum](https://upload.wikimedia.org/wikipedia/commons/7/7c/K-means_convergence_to_a_local_minimum.png)
Three key features of ''k''-means that make it efficient are often regarded as its biggest drawbacks:
*
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
is used as a
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
and
variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers ...
is used as a measure of cluster scatter.
* The number of clusters ''k'' is an input parameter: an inappropriate choice of ''k'' may yield poor results. That is why, when performing ''k''-means, it is important to run diagnostic checks for
determining the number of clusters in the data set.
* Convergence to a local minimum may produce counterintuitive ("wrong") results (see example in Fig.).
A key limitation of ''k''-means is its cluster model. The concept is based on spherical clusters that are separable so that the mean converges towards the cluster center. The clusters are expected to be of similar size, so that the assignment to the nearest cluster center is the correct assignment. When for example applying ''k''-means with a value of
onto the well-known
Iris flower data set
The ''Iris'' flower data set or Fisher's ''Iris'' data set is a multivariate data set used and made famous by the British statistician and biologist Ronald Fisher in his 1936 paper ''The use of multiple measurements in taxonomic problems'' as an ...
, the result often fails to separate the three
Iris
Iris most often refers to:
*Iris (anatomy), part of the eye
*Iris (mythology), a Greek goddess
* ''Iris'' (plant), a genus of flowering plants
* Iris (color), an ambiguous color term
Iris or IRIS may also refer to:
Arts and media
Fictional ent ...
species contained in the data set. With
, the two visible clusters (one containing two species) will be discovered, whereas with
one of the two clusters will be split into two even parts. In fact,
is more appropriate for this data set, despite the data set's containing 3 ''classes''. As with any other clustering algorithm, the ''k''-means result makes assumptions that the data satisfy certain criteria. It works well on some data sets, and fails on others.
The result of ''k''-means can be seen as the
Voronoi cells of the cluster means. Since data is split halfway between cluster means, this can lead to suboptimal splits as can be seen in the "mouse" example. The Gaussian models used by the
expectation-maximization algorithm (arguably a generalization of ''k''-means) are more flexible by having both variances and covariances. The EM result is thus able to accommodate clusters of variable size much better than ''k''-means as well as correlated clusters (not in this example). In counterpart, EM requires the optimization of a larger number of free parameters and poses some methodological issues due to vanishing clusters or badly-conditioned covariance matrices. ''K''-means is closely related to nonparametric
Bayesian modeling.
Applications
''k''-means clustering is rather easy to apply to even large data sets, particularly when using heuristics such as
Lloyd's algorithm In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of t ...
. It has been successfully used in
market segmentation
In marketing, market segmentation is the process of dividing a broad consumer or business market, normally consisting of existing and potential customers, into sub-groups of consumers (known as ''segments'') based on some type of shared characte ...
,
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
, and
astronomy
Astronomy () is a natural science that studies astronomical object, celestial objects and phenomena. It uses mathematics, physics, and chemistry in order to explain their origin and chronology of the Universe, evolution. Objects of interest ...
among many other domains. It often is used as a preprocessing step for other algorithms, for example to find a starting configuration.
Vector quantization
![Rosa_Gold_Glow_2_small_noblue_color_space](https://upload.wikimedia.org/wikipedia/commons/3/3d/Rosa_Gold_Glow_2_small_noblue_color_space.png)
''k''-means originates from signal processing, and still finds use in this domain. For example, in
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
,
color quantization
In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as v ...
is the task of reducing the
color palette of an image to a fixed number of colors ''k''. The ''k''-means algorithm can easily be used for this task and produces competitive results. A use case for this approach is
image segmentation
In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects ( sets of pixels). The goal of segmentation is to simpl ...
. Other uses of vector quantization include
non-random sampling
In statistics, sampling bias is a bias in which a sample is collected in such a way that some members of the intended population have a lower or higher sampling probability than others. It results in a biased sample of a population (or non-human ...
, as ''k''-means can easily be used to choose ''k'' different but prototypical objects from a large data set for further analysis.
Cluster analysis
In cluster analysis, the ''k''-means algorithm can be used to partition the input data set into ''k'' partitions (clusters).
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.
Feature learning
''k''-means clustering has been used as a
feature learning
In machine learning, feature learning or representation learning is a set of techniques that allows a system to automatically discover the representations needed for feature detection or classification from raw data. This replaces manual feature ...
(or
dictionary learning
Sparse coding is a representation learning method which aims at finding a sparse representation of the input data (also known as sparse coding) in the form of a linear combination of basic elements as well as those basic elements themselves. These ...
) step, in either (
semi-
Numeral or number prefixes are prefixes derived from numerals or occasionally other numbers. In English and many other languages, they are used to coin numerous series of words. For example:
* unicycle, bicycle, tricycle (1-cycle, 2-cycle, 3-cyc ...
)
supervised learning
Supervised learning (SL) is a machine learning paradigm for problems where the available data consists of labelled examples, meaning that each data point contains features (covariates) and an associated label. The goal of supervised learning alg ...
or
unsupervised learning
Unsupervised learning is a type of algorithm that learns patterns from untagged data. The hope is that through mimicry, which is an important mode of learning in people, the machine is forced to build a concise representation of its world and t ...
.
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,
or some smooth transformation of the distance.
Alternatively, transforming the sample-cluster distance through a
Gaussian RBF, obtains the hidden layer of a
radial basis function network
In the field of mathematical modeling, a radial basis function network is an artificial neural network that uses radial basis functions as activation functions. The output of the network is a linear combination of radial basis functions of the inp ...
.
This use of ''k''-means has been successfully combined with simple,
linear classifier
In the field of machine learning, the goal of statistical classification is to use an object's characteristics to identify which class (or group) it belongs to. A linear classifier achieves this by making a classification decision based on the val ...
s for semi-supervised learning in
NLP (specifically for
named entity recognition
Named-entity recognition (NER) (also known as (named) entity identification, entity chunking, and entity extraction) is a subtask of information extraction that seeks to locate and classify named entities mentioned in unstructured text into pre ...
) and in
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
. On an object recognition task, it was found to exhibit comparable performance with more sophisticated feature learning approaches such as
autoencoder
An autoencoder is a type of artificial neural network used to learn efficient codings of unlabeled data ( unsupervised learning). The encoding is validated and refined by attempting to regenerate the input from the encoding. The autoencoder lea ...
s and
restricted Boltzmann machine
A restricted Boltzmann machine (RBM) is a generative stochastic artificial neural network that can learn a probability distribution over its set of inputs.
RBMs were initially invented under the name Harmonium by Paul Smolensky in 1986,
and rose ...
s.
However, it generally requires more data, for equivalent performance, because each data point only contributes to one "feature".
Relation to other algorithms
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.
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. 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.
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.
Principal component analysis
The relaxed solution of -means clustering, specified by the cluster indicators, is given by principal component analysis (PCA). 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. It is straightforward to produce counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.
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. Then this set is iteratively replaced by the mean of those points in the set that are within a given distance of that point. By contrast, ''k''-means restricts this updated set to ''k'' points usually much less than the number of points in the input data set, and replaces each point in this set by the mean of all points in the ''input set'' that are closer to that point than any other (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.
One of the advantages of mean shift over ''k''-means is that the number of clusters is not pre-specified, because mean shift is likely to find only a few clusters if only a small number exist. However, mean shift can be much slower than ''k''-means, and still requires selection of a bandwidth parameter. Mean shift has soft variants.
Independent component analysis
Under sparsity assumptions and when input data is pre-processed with the
whitening transformation A whitening transformation or sphering transformation is a linear transformation that transforms a vector of random variables with a known covariance matrix into a set of new variables whose covariance is the identity matrix, meaning that they ar ...
, ''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
In machine learning, feature learning or representation learning is a set of techniques that allows a system to automatically discover the representations needed for feature detection or classification from raw data. This replaces manual feature ...
.
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.
This makes it applicable to problems such as image denoising, where the spatial arrangement of pixels in an image is of critical importance.
Similar problems
The set of squared error minimizing cluster functions also includes the
''k''-medoids algorithm, an approach which forces the center point of each cluster to be one of the actual points, i.e., it uses
medoids Medoids are representative objects of a data set or a cluster within a data set whose sum of dissimilarities to all the objects in the cluster is minimal. Medoids are similar in concept to means or centroids, but medoids are always restricted to be ...
in place of
centroids
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any o ...
.
Software implementations
Different implementations of the algorithm exhibit performance differences, with the fastest on a test data set finishing in 10 seconds, the slowest taking 25,988 seconds (~7 hours).
The differences can be attributed to implementation quality, language and compiler differences, different termination criteria and precision levels, and the use of indexes for acceleration.
Free Software/Open Source
The following implementations are available under
Free/Open Source Software licenses, with publicly available source code.
*
Accord.NET
Accord.NET is a framework for scientific computing in .NET. The source code of the project is available under the terms of the Gnu Lesser Public License, version 2.1.
The framework comprises a set of libraries that are available in source code a ...
contains C# implementations for ''k''-means, ''k''-means++ and ''k''-modes.
*
ALGLIB
ALGLIB is a cross-platform open source numerical analysis and data processing library. It can be used from several programming languages (C++, C#, VB.NET, Python, Delphi).
ALGLIB started in 1999 and has a long history of steady development with r ...
contains parallelized C++ and C# implementations for ''k''-means and ''k''-means++.
*
AOSP contains a Java implementation for ''k''-means.
*
CrimeStat
CrimeStat is a crime mapping software program. CrimeStat is Windows-based program that conducts spatial and statistical analysis and is designed to interface with a geographic information system (GIS). The program is developed by Ned Levine & Assoc ...
implements two spatial ''k''-means algorithms, one of which allows the user to define the starting locations.
*
ELKI
ELKI (for ''Environment for DeveLoping KDD-Applications Supported by Index-Structures'') is a data mining (KDD, knowledge discovery in databases) software framework developed for use in research and teaching. It was originally at the database s ...
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
Julia is usually a feminine given name. It is a Latinate feminine form of the name Julio and Julius. (For further details on etymology, see the Wiktionary entry "Julius".) The given name ''Julia'' had been in use throughout Late Antiquity (e.g ...
contains a ''k''-means implementation in the JuliaStats Clustering package.
*
KNIME
KNIME (), the Konstanz Information Miner, is a free and open-source data analytics, reporting and integration platform. KNIME integrates various components for machine learning and data mining through its modular data pipelining "Building Blocks ...
contains nodes for ''k''-means and ''k''-medoids.
*
Mahout
A mahout is an elephant rider, trainer, or keeper. Mahouts were used since antiquity for both civilian and military use. Traditionally, mahouts came from ethnic groups with generations of elephant keeping experience, with a mahout retaining h ...
contains a
MapReduce
MapReduce is a programming model and an associated implementation for processing and generating big data sets with a parallel, distributed algorithm on a cluster.
A MapReduce program is composed of a ''map'' procedure, which performs filtering ...
based ''k''-means.
*
mlpack
mlpack is a machine learning software library for C++, built on top of the Armadillo library and thensmallennumerical optimization library. mlpack has an emphasis on scalability, speed, and ease-of-use. Its aim is to make machine learning possib ...
contains a C++ implementation of ''k''-means.
*
Octave
In music, an octave ( la, octavus: eighth) or perfect octave (sometimes called the diapason) is the interval between one musical pitch and another with double its frequency. The octave relationship is a natural phenomenon that has been refer ...
contains ''k''-means.
*
OpenCV
OpenCV (''Open Source Computer Vision Library'') is a library of programming functions mainly aimed at real-time computer vision. Originally developed by Intel, it was later supported by Willow Garage then Itseez (which was later acquired by In ...
contains a ''k''-means implementation.
*
Orange
Orange most often refers to:
*Orange (fruit), the fruit of the tree species '' Citrus'' × ''sinensis''
** Orange blossom, its fragrant flower
*Orange (colour), from the color of an orange, occurs between red and yellow in the visible spectrum
* ...
includes a component for ''k''-means clustering with automatic selection of ''k'' and cluster silhouette scoring.
*
PSPP
PSPP is a free software application for analysis of sampled data, intended as a free alternative for IBM SPSS Statistics. It has a graphical user interface and conventional command-line interface. It is written in C and uses GNU Scientific Lib ...
contains ''k''-means, The QUICK CLUSTER command performs ''k''-means clustering on the dataset.
*
R contains three ''k''-means variations.
*
SciPy
SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing.
SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signal ...
and
scikit-learn
scikit-learn (formerly scikits.learn and also known as sklearn) is a free software machine learning library for the Python programming language.
It features various classification, regression and clustering algorithms including support-vector ...
contain multiple ''k''-means implementations.
*
Spark
Spark commonly refers to:
* Spark (fire), a small glowing particle or ember
* Electric spark, a form of electrical discharge
Spark may also refer to:
Places
* Spark Point, a rocky point in the South Shetland Islands
People
* Spark (surname)
* ...
MLlib implements a distributed ''k''-means algorithm.
*
Torch
A torch is a stick with combustible material at one end, which is ignited and used as a light source. Torches have been used throughout history, and are still used in processions, symbolic and religious events, and in juggling entertainment. In ...
contains an ''unsup'' package that provides ''k''-means clustering.
*
Weka
The weka, also known as the Māori hen or woodhen (''Gallirallus australis'') is a flightless bird species of the rail family. It is endemic to New Zealand. It is the only extant member of the genus ''Gallirallus''. Four subspecies are recognize ...
contains ''k''-means and ''x''-means.
Proprietary
The following implementations are available under