k-Means Clustering: A Centroid-Based Technique
K-means clustering is one of the easiest, simple and most popular unsupervised machine learning algorithms. The goal of K-means is simple: group similar data points together and recognize the underlying patterns. K-meanslooks for a fixed number (k) of clusters in a dataset, to accomplish this goal. A cluster refers to a collection of data points aggregated together exhibiting certain similarities. The target number k is a hyperparameter (i.e. You have to set its value by yourself before you the learning process begin), which refers to the number of centroids you need in the dataset. A centroid is the fictional or real location representing the center of the cluster. The centroid can be defined in various ways such as by the mean or medoid of the objects (or points) assigned to the cluster (we will deal with K medoid in upcoming articles).Every data point is assigned to each of the clusters through reducing the in-cluster sum of squares.
In other words, the K-means algorithm identifies k number of centroids, and then group every data point to the nearest cluster, while keeping the centroids as small as possible. The term ‘means’ of cluster in the K-means refers to average of the data in a cluster; that is, the centroid.
Suppose a data set, D, contains n data points in Euclidean space. Clustering (Partitioning) methods distribute the data points in D into k clusters, C1,… ,Ck, that is, Ci belongs to D. An objective function is used to assess the partitioning quality so that data points within a cluster are similar to one another.
A K means clustering technique uses the mean(i.e. centroid value) of a cluster, Ci , to represent that cluster. The difference between an data point p belongs to Ci and ci, the mean of the cluster, is measured by dist(p, ci), where dist(x,y) gives the Euclidean distance between the two points x and y. The quality of cluster Ci can be measured by the within cluster variation, which is the sum of squared error between all data points in Ci and the centroid ci, defined as,
|K means error
Where E is the sum of the squared error for all data points in the data set; p is the point in space representing a given data point ; and ci is the mean of cluster Ci (both p and ci are multidimensional).
In other words, for each data points in each cluster, the distance from the data point to its cluster center is squared, and the distances are summed. This objective function tries to make the resulting k clusters as compact and as separate as possible from other clusters.
How does the k-means algorithm work?
The k-means algorithm defines the centroid of a cluster as the mean value of the points among the cluster.
It works as follows,
First of all, it randomly selects k of the data point in D, each of which initially represents a cluster mean (i.e. centroid). Each of the remaining data points is assigned to the cluster to which it is the most similar, based on the Euclidean distance between the object and the cluster mean. The k-means algorithm then iteratively improves the within-cluster variation. For every cluster, it computes the new mean using the data points allocated to the cluster in the previous iteration. All the data points are then reallocated using the updated means as the new cluster means. The iterations goes on until the allocation is stable, that is, the clusters formed in the current round are the same as those formed in the previous round (i.e. the cluster mean obtained in this round is same as that of the obtained in the previous round). The k-means algorithm is summarized in figure below,
|K means Clustering
Algorithm of k-means Clustering:
The k-means algorithm is used for partitioning (clustering), where each cluster’s center is represented by the mean value of the data points in the cluster (group).
-k: the number of clusters,
-D: a data set containing n objects.
-A set of k clusters.
(1) randomly select k data points from D as the initial cluster centers;
(3) re/assign each data points to the cluster to which the object is the most similar (i.e. which is more near based upon the euclidean distance measure),based on the mean value of the objects in the cluster;
(4) update the cluster means, that is, calculate the new mean value of the data points for each cluster;
(5) go to loop until no change in cluster means;