k-means clustering

k-means clustering is a method of <a href="/facts/Vector_quantization/rKNehCok">vector quantization</a>, originally from <a href="/facts/Signal_processing/Npaja6zb">signal processing</a>, that aims to <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> n observations into k clusters in which each observation belongs to the <a href="/facts/Cluster_(statistics)/HUeDnWPt">cluster</a> with the nearest <a href="/facts/Mean/swcEd4Pg">mean</a> (cluster centers or cluster <a href="/facts/Centroid/H6dDbg0h">centroid</a>), serving as a prototype of the cluster. This results in a partitioning of the data space into <a href="/facts/Voronoi_cell/AhQY5LD8">Voronoi cells</a>. k-means clustering minimizes within-cluster variances (<a href="/facts/Squared_Euclidean_distance/9qDoQKQe">squared Euclidean distances</a>), but not regular Euclidean distances, which would be the more difficult <a href="/facts/Weber_problem/koaEg1fv">Weber problem</a>: the mean optimizes squared errors, whereas only the <a href="/facts/Geometric_median/aIQYJaHX">geometric median</a> minimizes Euclidean distances. For instance, better Euclidean solutions can be found using <a href="/facts/K-medians_clustering/09wScbjR">k-medians</a> and <a href="/facts/K-medoids/YFYaESyy">k-medoids</a>.
The problem is computationally difficult (<a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>); however, efficient <a href="/facts/Heuristic_algorithm/PM2qkoa2">heuristic algorithms</a> converge quickly to a <a href="/facts/Local_optimum/f40GlzAw">local optimum</a>. These are usually similar to the <a href="/facts/Expectation%E2%80%93maximization_algorithm/32P2bdBc">expectation–maximization algorithm</a> for <a href="/facts/Mixture_model/WWe6TJlg">mixtures</a> of <a href="/facts/Gaussian_distribution/UapjjPyQ">Gaussian distributions</a> 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 <a href="/facts/K-nearest_neighbor/Bs1UaAmE">k-nearest neighbor classifier</a>, a popular supervised <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> 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 <a href="/facts/Nearest_centroid_classifier/jpq0fFx0">nearest centroid classifier</a> or <a href="/facts/Rocchio_algorithm/a5fWdBxm">Rocchio algorithm</a>.

k-means clustering open-in-new

k-means clustering