20 k-Means Clustering Interview Questions (EXPLAINED) For ML Engineers

K-Means clustering intends to partition n objects into k clusters in which each object belongs to the cluster with the nearest mean. This method produces exactly k different clusters of the greatest possible distinction. The best number of clusters k leading to the greatest separation (distance) is not known as a priori and must be computed from the data. The objective of K-Means clustering is to minimize total intra-cluster variance, or, the squared error function:  

Algorithm:

1. Clusters the data into k groups where k is predefined.
2. Select k points at random as cluster centers.
3. Assign objects to their closest cluster center according to the Euclidean distance function.
4. Calculate the centroid or mean of all objects in each cluster.
5. Repeat steps 2, 3 and 4 until the same points are assigned to each cluster in consecutive rounds.

• k-means clustering is a method of vector quantization that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.
• k-means clustering minimizes within-cluster variances.
• Within-cluster-variance is simple to understand measure of compactness. So basically, the objective is to find the most compact partitioning of the data set into k partitions.

The common stopping conditions I have seen:

1. Convergence. No further changes, points stay in the same cluster.
2. The maximum number of iterations. When the maximum number of iterations has been reached, the algorithm will be stopped. This is done to limit the runtime of the algorithm.
3. Variance did not improve by at least x
4. Variance did not improve by at least x * initial variance

If you use MiniBatch k-means, it will not converge, so you need one of the other criteria. The usual one is the number of iterations.

• k-Means is a clustering algorithm that tries to partition a set of points into k sets such that the points in each cluster tend to be near each other. It is unsupervised because the points have no external classification.

• k-Nearest Neighbors is a classification (or regression) algorithm that, in order to determine the classification of a point, combines the classification of the k nearest points. It is supervised because it is trying to classify a point based on the known classification of other points.

Scalability

• k-means has an order of $O(n.k.d.i)$. The scalability of k-means is better than hierarchical clustering because k, i, and d are small, and also the memory consumption is linear.
• Hierarchical clustering has an order of $O(n^3d)$. The scalability of hierarchical clustering is worse, and its memory consumption is quadratic.

Flexibility

• k-means is extremely limited in applicability. It is limited to Euclidean distances, and it only works on numerical data.
• Hierarchical clustering does not even require distances (any measure can be used, including similarity function simply by preferring high values to low values). It can use any type of data including categorical, strings, time series, or mixed.

• k-means has trouble clustering data where clusters are of various sizes and densities.
• Outliers will cause the centroids to be dragged, or the outliers might get their own cluster instead of being ignored. Outliers should be clipped or removed before clustering.
• If the number of dimensions increase, a distance-based similarity measure converges to a constant value between any given examples. Dimensions should be reduced before clustering them.

• Entropy is used as an external validation measure by using the class labels of data as external information.
• Entropy is a measure of the purity of the cluster with respect to the given class label. Thus, if each cluster consists of objects with a single class label, the entropy value is 0. As the objects in a cluster become more diverse, the entropy value increases.
• The entropy of a cluster j is calculated by:
  $E_j = -\sum_i p_{ij}\log(p_{ij})$
  where $p_{ij}$ is the probability of assigning an object of class i to cluster j, and the sum is taken over all classes.
• Using entropy measure to validate the class labels tends to favor k-means which produce clusters in relatively uniform size. This effect is more significant in the situation that the data have highly imbalanced true clusters.
• So, using entropy measure for validating k-means clustering can lead to the results being misleading.

Calculate the Within-Cluster-Sum of Squared Errors (WSS) for different values of k, and choose the k for which WSS becomes first starts to diminish. In the plot of WSS-versus-k, this is visible as an elbow.

Some pre-processing steps to follow are:

• If the variables are of incomparable units, then the variables should be standardized.
• Even if the variables are of the same units but show quite different variances then it is a good idea to standardize them. Since k-means clustering produces more or less round clusters, it puts more weight on variables with smaller variance, so the clusters will tend to be separated along with variables with greater variance.
• k-means clustering results are sensitive to the order of objects in the dataset, so it is good to randomize the dataset and try clustering many different times.

• If the dataset is large, an alternative is using mini-batch k-Means.
• Mini batch k-means has the main advantage of reducing the computational cost of finding a partition. This cost is proportional to the size of the sample batch used and this difference is more evident when the number of clusters is larger.
• The main idea of mini-batch k-Means is to use small random batches of data of a fixed size, so they can be stored in memory. Each iteration a new random sample from the dataset is obtained and used to update the clusters and this is repeated until convergence.

• The objective of K-Means clustering is to minimize total intra-cluster variance, or, distance function. The objective function of k-means depends on the proximities of the data points to the cluster centroids. It is shown below:

$\min_{\{m_k\}, 1 \leq k \leq K} \sum_{k = 1} ^ K \sum_{x \in C_k} \pi_x dist(x, m_k)$

where $\pi_k$ is the weight of x, $n_k$ is the number of data objects assigned to cluster $C_k, m_k = \sum_{x \in C_k} \frac{\pi_x x}{n_k}$ is the centroid of cluster $C_k$. K is the number of clusters set by the user. The function dist computes the distance between object x and centroid $m_k, 1 \leq k \leq K$.

• While the selection of distance function is optional, the squared Euclidean distance, i.e. $|x - m|^2$ has been most widely used in both research and practice.

Classic k-Means

• In Classic k-Means, we seek to minimize the Euclidean distance between the cluster center and the members of the cluster.
• The intuition behind this is that the radial distance from the cluster-center to the element location should be similar for all elements of that cluster.

Spherical k-Means

• In Spherical k-Means, the idea is to set the center of each cluster such that it makes both uniform and minimal the angle between components.
• The intuition is like looking at stars - In spherical k-means, you aim to guarantee that the centers are on the sphere, so you could adjust the algorithm to use the cosine distance, and should additionally normalize the centroids of the final result.
• Cosine similarity measures the similarity between two vectors of an inner product space. It is measured by the cosine of the angle between two vectors and determines whether two vectors are pointing in roughly the same direction.

• k-Means minimizes within-cluster variance, which equals squared Euclidean distances. In general, the arithmetic mean does this. It does not optimize distances but squared deviations from the mean.

• k-Medians minimizes absolute deviations, which equals Manhattan distance. In general, the per-axis median should do this. It is a good estimator for the mean if you want to minimize the sum of absolute deviations (that is sum_i abs(x_i-y_i)), instead of the squared ones.

To decide between k-means and k-medians, take into consideration the following:

• If the distance is squared Euclidean distance, use k-means.
• If the distance is Taxicab metric, use k-medians.
• If there is any other distance, use k-medoids.

There is an exception which is:

• Maximizing cosine similarity is related to minimizing the squared Euclidean distance on the L2-normalized data. So, if the data is L2 normalized, and it is L2-normalized each iteration, then k-means can be used.

• Manhattan distance captures the distance between two points by aggregating the pairwise absolute difference between each variable.
• Euclidean distance captures the distance between two points by aggregating the squared difference in each variable.

• If two points are close on most variables but more discrepant on one of them, Euclidean distance will exaggerate that discrepancy, whereas Manhattan distance will shrug it off, being more influenced by the closeness of the other variables.
• Manhattan distance should give more robust results, whereas Euclidean distance is likely to be influenced by outliers.

• SAIL is an incremental algorithm.
• k-Means usually employs the batch-learning mode.

• SAIL is also different from the traditional incremental k-means; that is, to decide the assignment of each selected instance, SAIL does not compute the KL-divergence values between the instance and all the centroid vectors. Instead, it computes and updates the Shannon entropies of the centroids. This computation is supported by two incrementally-maintained summations for each cluster c: $p(c) = \sum_{x \in c} p(x)$ and $p(Y|c) = \sum_{x \in c} p(x) p(Y|x)$. This is also why this method is called Summation-based Incremental Learning (SAIL) algorithm.
• Incremental K-means clustering algorithm is applied to a dynamic database where the data may be frequently updated. This approach measures the new cluster centers by directly computing the new data from the means of the existing clusters instead of rerunning the K-means algorithm.

There are many different approaches to find the value of K. Some of the approaches are described below:

• Maximizing the Bayesian Information Criterion (BIC):
  $BIC(C|X)=L(X|C)-(p/2).\log n$
  where L(X|C) is the log-likelihood of the dataset X according to model C. p is the number of parameters in the model C, and n is the number of points in the dataset.
• Another method is to start with a large value of k and removing centroids (reducing k) until it no longer reduces the description length.
• Another method is to start with one cluster, and split the clusters until the points assigned to each cluster has a Gaussian distribution.