K-Means Clustering Algorithm

K-Means Clustering Algorithm

• K-means clustering is an exclusive clustering algorithm where each object is assigned to precisely one of a set of clusters.
• The value of k (number of clusters) is generally a small integer, such as 2, 3, 4, or 5, but may be larger.

Steps of the K-Means Algorithm

• Choose a value of k (number of clusters).
• Select k objects in an arbitrary fashion, using these as the initial set of k centroids.
• Assign each of the objects to the cluster with the nearest centroid.
• Recalculate the centroids of the k clusters.
• Repeat steps 3 and 4 until the centroids no longer move.

Example of K-Means Clustering

• The algorithm is illustrated using a dataset of 16 objects with two attributes x and y.
• The initial centroids are chosen arbitrarily, and the objects are assigned to the closest centroid.
• The centroids are recalculated, and the process is repeated until convergence.

Limitations of the K-Means Algorithm

• The initial selection of centroids can significantly affect the result.
• There is no principled way to know what the value of k ought to be.
• The algorithm may not necessarily find the best set of clusters, corresponding to minimising the value of the objective function.

Choosing the Best Value of k

• The value of k can be chosen pragmatically by experimenting with different values and choosing the set of clusters with the smallest value of the objective function.
• The value of the objective function decreases as k increases, but it may level off or decrease slowly after a certain point.
• A small number of clusters is generally preferred.

k-Means Clustering Algorithm

• k-Means clustering is an exclusive clustering algorithm, where each object is assigned to precisely one of a set of clusters.
• The algorithm starts by deciding on the number of clusters (k) to be formed from the data, which is usually a small integer (2, 3, 4, or 5).
• The quality of the clusters is measured using the sum of the squares of the distances of each point from the centroid of the cluster to which it is assigned.

Initial Clustering

• The algorithm starts by selecting k initial points (centroids) which are treated as the centroids of k potential clusters.
• These points are selected arbitrarily, but it is recommended to choose points that are fairly far apart.
• Each object is then assigned to the cluster with the nearest centroid.

Iterative Process

• The centroids of the clusters are recalculated using the x and y values of the objects currently assigned to each cluster.
• The objects are then reassigned to the cluster with the nearest centroid.
• Steps 3 and 4 are repeated until the centroids no longer move.

Example

• The algorithm is illustrated using a dataset of 16 objects with two attributes (x and y).
• The initial centroids are chosen arbitrarily, and the objects are assigned to the cluster with the nearest centroid.
• The centroids are recalculated and the objects are reassigned to the cluster with the nearest centroid.

Finding the Best Set of Clusters

• The k-means algorithm does not necessarily find the best set of clusters, and the initial selection of centroids can significantly affect the result.
• To overcome this, the algorithm can be run several times with different initial centroids, and the set of clusters with the smallest value of the objective function is chosen.
• The value of k is often chosen pragmatically by experimenting with different values of k and choosing the set of clusters with the smallest value of the objective function.

Choosing the Value of k

• The value of k can be chosen by experimenting with different values and observing the value of the objective function.
• The results suggest that the best value of k is probably 3, as the value of the function drops sharply after k = 3.
• The goal is to find a fairly small number of clusters, as a large number of clusters will result in each object forming its own cluster, which is not useful.