How does the k-means algorithm work ? Write k-means algorithm for partitioning.

K-Means Algorithm :-

• First, it randomly selects k of the objects in D, each of which initially represents a cluster mean or center.

• For each of the remaining objects, an object 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 each cluster, it computes the new mean using the objects assigned to the cluster in the previous iteration.

• All the objects are then reassigned using the updated means as the new cluster centers.

• The iterations continue until the assignment is stable, that is, the clusters formed in the current round are the same as those formed in the previous round.

Algorithm :-

Input :
k : the number of clusters,
D : a data set containing n objects.
Output : A set of k clusters.

Method :-

• Arbitrarily choose k objects from D as the initial cluster centers;

• repeat

• (re)assign each object to the cluster to which the object is the most similar, based on the mean value of the objects in the cluster;

• update the cluster means, that is, calculate the mean value of the objects for each cluster;

• until no change;