Interview Question

"Compare K-Means, DBSCAN, and hierarchical clustering. What are the strengths and weaknesses of each? How do you choose the number of clusters and evaluate clustering quality?"

Difficulty: Medium | Frequently asked at Google, LinkedIn, Amazon

Theoretical Foundation

K-Means Clustering

Algorithm:

1. Initialize $K$ centroids randomly
2. Assign each point to nearest centroid
3. Update centroids as mean of assigned points
4. Repeat until convergence

Objective:

Properties:

• Assumes spherical clusters
• Sensitive to initialization (use K-Means++)
• $O(nKd)$ per iteration
• Converges to local minimum

DBSCAN (Density-Based Spatial Clustering)

Key Concepts:

• Core point: Has at least $\minPts$ neighbors within $\epsilon$
• Border point: Within $\epsilon$ of a core point but not a core point itself
• Noise point: Neither core nor border

Algorithm:

1. Find all core points
2. Expand clusters from core points
3. Border points join nearest core point cluster
4. Noise points remain unclustered

Properties:

• Finds arbitrary-shaped clusters
• Handles outliers naturally
• No need to specify $K$
• Sensitive to $\epsilon$ and $\minPts$

Hierarchical Clustering

Agglomerative (Bottom-Up):

1. Start with each point as its own cluster
2. Merge closest pair of clusters
3. Repeat until $K$ clusters remain

Divisive (Top-Down):

1. Start with all points in one cluster
2. Split clusters recursively
3. Stop when $K$ clusters remain

Linkage Methods:

• Single: Minimum distance between clusters
• Complete: Maximum distance between clusters
• Average: Average distance between clusters
• Ward: Minimize within-cluster variance

Clustering Comparison

Choosing the Number of Clusters

Elbow Method

Plot within-cluster sum of squares (WCSS) vs $K$. Look for the "elbow" where improvement slows.

Silhouette Score

where $a(i)$ is average distance to same cluster, $b(i)$ is average distance to nearest other cluster.

Gap Statistic

Compares WCSS to expected WCSS under null reference distribution.

Evaluation Metrics

Silhouette Coefficient

Range: $[-1, 1]$. Higher is better.

Adjusted Rand Index (ARI)

Corrected for chance. Range: $[-1, 1]$. 1 = perfect.

Normalized Mutual Information (NMI)

Measures agreement between cluster assignments. Range: $[0, 1]$.

Code Implementation

Real-World Applications

Google: Search Clustering

• Query Clustering: Grouping similar search queries
• Document Clustering: Organizing web pages by topic
• User Segmentation: Clustering users by behavior

LinkedIn: People You May Know

• Social Network Clustering: Identifying communities
• Skill Clustering: Grouping professionals by expertise
• Company Clustering: Categorizing businesses

Common Follow-Up Questions

Q1: How do you handle the scalability of K-Means? Use Mini-Batch K-Means, which processes small random batches. Also consider distributed implementations with MapReduce or Spark.

Q2: When would you choose DBSCAN over K-Means? When clusters have arbitrary shapes, when you expect noise/outliers, or when you don't know the number of clusters.

Q3: How do you evaluate clustering without ground truth? Use intrinsic metrics: silhouette score, Davies-Bouldin index, Calinski-Harabasz index.

Q4: What is the curse of dimensionality for clustering? In high dimensions, distance metrics become less meaningful. Use dimensionality reduction before clustering.

Related Topics

• Dimensionality Reduction for Clustering
• Anomaly Detection Methods
• Recommendation Systems
• Customer Segmentation