MS-DS Master of Data science Unsupervised Learning Techniques 3 — Questions and Answers
Question 1: What is the computational complexity of a single iteration of k-means on n data points with k clusters and d dimensions?
- O(n²d)
- O(nkd) (Correct answer)
- O(k²d)
- O(n log n · d)
Correct answer: O(nkd)
Each of the n points must compute distances to each of the k cluster centroids in d dimensions, giving O(nkd) per iteration.
Question 2: Which method is used by UMAP to preserve both local and global structure, distinguishing it from t-SNE?
- UMAP uses a Gaussian kernel; t-SNE uses a Student-t kernel in low dimensions
- UMAP constructs a fuzzy topological representation and optimizes its cross-entropy with a low-dimensional analog (Correct answer)
- UMAP applies PCA as a preprocessing step that t-SNE does not use
- UMAP uses spectral clustering for initialization while t-SNE uses random initialization only
Correct answer: UMAP constructs a fuzzy topological representation and optimizes its cross-entropy with a low-dimensional analog
UMAP is grounded in Riemannian geometry and algebraic topology, building a fuzzy simplicial complex and minimizing its cross-entropy with a low-dimensional representation, preserving more global structure than t-SNE.
Question 3: What is the 'elbow method' used to determine in unsupervised learning?
- The optimal epsilon and minPts for DBSCAN
- The appropriate number of clusters k in k-means by plotting inertia vs. k (Correct answer)
- The number of principal components to retain in PCA
- The convergence threshold for the EM algorithm
Correct answer: The appropriate number of clusters k in k-means by plotting inertia vs. k
The elbow method plots within-cluster sum of squares (inertia) against k; the 'elbow' point where improvement diminishes suggests the optimal k.
Question 4: A researcher applies hierarchical agglomerative clustering with single linkage to data with two elongated, touching clusters. What artifact is likely to occur?
- The algorithm will fail to converge
- Chaining: the two clusters will merge prematurely into one elongated cluster (Correct answer)
- The algorithm will identify too many small clusters
- The dendrogram will be uninterpretable due to equidistant merges
Correct answer: Chaining: the two clusters will merge prematurely into one elongated cluster
Single linkage uses the minimum pairwise distance between clusters, making it susceptible to chaining where a bridge of close points merges two distinct elongated clusters early.
Question 5: In a Variational Autoencoder (VAE), what is the purpose of the reparameterization trick?
- To normalize the latent space to have zero mean and unit variance
- To allow gradients to flow through the stochastic sampling step during backpropagation (Correct answer)
- To enforce disentanglement of latent variables
- To reduce the dimensionality of the encoder output
Correct answer: To allow gradients to flow through the stochastic sampling step during backpropagation
The reparameterization trick expresses z = μ + σ·ε (ε ~ N(0,I)), making the random node deterministic w.r.t. ε and allowing gradient flow through μ and σ.
Question 6: Which metric is specifically designed to evaluate clustering quality when ground-truth labels are available?
- Silhouette coefficient
- Davies-Bouldin index
- Adjusted Rand Index (ARI) (Correct answer)
- Calinski-Harabasz index
Correct answer: Adjusted Rand Index (ARI)
The Adjusted Rand Index measures the similarity between predicted cluster assignments and ground-truth labels, adjusted for chance agreement.
Question 7: What distinguishes a self-organizing map (SOM) from k-means clustering?
- SOM requires specifying the number of clusters; k-means does not
- SOM preserves topological relationships of data on a low-dimensional grid; k-means does not (Correct answer)
- SOM can only handle two-dimensional data; k-means is general
- SOM performs hard assignment; k-means performs soft assignment
Correct answer: SOM preserves topological relationships of data on a low-dimensional grid; k-means does not
SOMs arrange neurons on a 2D grid and update neighboring neurons during training, preserving the topological structure of the input space in the output map.
MS-DS Master of Data science Unsupervised Learning Techniques 3
What is the computational complexity of a single iteration of k-means on n data points with k clusters and d dimensions?