Author: Monis Khan

Following are the difference between K-Means and Hierarchical Clustering Algorithm (HCA)

1. K-Means is that it needs us to pre-enter the number of clusters (K) but Hierarchical clustering has no such requirements. The algorithm on itself deduces the optimum number of cluster and displays it form of dendrogram.
2. Performance of K-Means on spherical data is better than that of HCA
3. Hierarchical clustering is a purely agglomerative approach and goes on to build one giant cluster. K-Means algorithm in all its iterations has same number of clusters.
4. K-Means need circular data, while Hierarchical clustering has no such requirement.
5. K-Means uses median or mean to compute centroid for representing cluster while HCA has various linkage method that may or may not employ the centroid.
6. With introduction of mini batches K-Means can work with very large datasets but HCA lacks in this regard.
7. Hierarchical methods are  suited for cases which require arrangement of the clusters  into a natural hierarchy. In K-means all clusters are on same level i.e. similar WCSS or cohesiveness.
8. HCA can produce reproducible results while older versions of K-Means can’t
9. K-Means simply divides data into mutually exclusive subsets while HCA arranges it into a tree format.

Following are the methods of linkage used by Hierarchical clustering algorithm:

1. Single Linkage: It is a distance based criteria and measures minimum pairwise distance.
2. Complete Linkage: It is a distance based criteria and measures maximum pairwise distance.
3. Centroid Linkage: It is a distance based criteria and measures distance between centroids.
4. Ward’s Linkage: It is a cluster similarity based criteria and measures distance between centroids.

Dendrograms depict the distance between clusters. The y-axis of a dendrogram depicts dissimilarity between two clusters. They are used to find the optimum number of clusters for a Hierarchical clustering algorithm.

Following are the two approaches used by clustering algorithms:

1. Agglomerative: The algorithms starts with assuming each individual point as a cluster and proceeds with adding the nearest point to the existing cluster. Thus similarity is used as a measure for creating new cluster. If not stopped, as per business requirement, the algorithm would go on to create one giant cluster with all the data points. This is also called bottoms up approach.
2. Divisive: The algorithm starts with e one giant cluster with all the data points and proceeds to remove dissimilar points into separate clusters. Thus dissimilarity is used as a measure for creating new cluster. If not stopped, as per business requirement, the algorithm would go on to create individual cluster for all data points. This is also called top down approach.

Following are the challenges faced by K-Means Clustering:

1. k-Means doesn’t perform well if the clusters have varying sizes, different densities, or non-spherical shapes.
2. Has to be run for a certain amount of iteration or it would produce a suboptimal result.
3. Computationally expensive as distance is to be calculated from each centroid to all data points.
4. Can’t handle high dimensional data
5. Number of clusters need to be specified
6. Since initial centroids are arbitrarily chosen, the result is not exactly replicable.
7. Shows out of memory error for large datasets

Following are the steps taken by K-Means algorithm in its learning process:

1. User specifies the value of K using the elbow curve.
2. For the first iteration, K number of points are arbitrarily chosen. Let’s call them centroids for the time being, in below steps you’ll get the reason for this nomenclature. In case of K-Means++, it is taken care that these points are farthest from each other. In further iterations the centroids calculated in step 4 are used.
3. Distance of all the points from these K points is calculated and the point which is nearest to given centroid is assigned to that centroid. Thus first set of K clusters are formed.
4. Centroid for each cluster is calculated. [That’s why we were calling the arbitrarily chosen points as centroids]
5. Go back to step 2 and repeat the process till the time centroids don’t move at all or the maximum number of iterations is reached. Beyond a certain number of iteration the movement in centroid, hence decrease in WCSS, is negligible.