DBSCAN & Hierarchical Clustering

DBSCAN is a density-based clustering algorithm that needs no preset cluster count $K$ — only two parameters, ε and minPts. The ε-neighborhood is $N_\varepsilon(p) = \{ q \in D \mid \text{dist}(p, q) \le \varepsilon \}$; a core point satisfies $|N_\varepsilon(p)| \ge \text{minPts}$, a border point is non-core but inside some core point's ε-neighborhood, and noise points are neither.Density directly reachable: $p$ is a core point and $q \in N_\varepsilon(p)$; density reachable: a chain of core points $p_1, \ldots, p_m$ with consecutive direct reachability; density connected: some $o$ exists from which both $p$ and $q$ are density reachable. A cluster is a maximal set of density-connected points; noise is flagged explicitly. Complexity is $O(n \log n)$ with a KD-Tree or naive $O(n^2)$.Hierarchical clustering (AGNES) merges the closest clusters bottom-up using linkages — single (nearest-point distance, prone to chaining), complete (farthest-point distance, noise-robust), Ward (minimum variance increase, most common); naive complexity $O(n^3)$.

geo-spatial clustering, image segmentation, anomaly detection (noise points are outliers), and arbitrarily shaped clusters; interviews compare it with K-Means and ask about ε/minPts tuning.

K-Means needs K, assumes convex clusters, and forces noise into clusters; DBSCAN needs no K, finds arbitrary shapes, and separates noise automatically. The cost: ε is hard to set globally for uneven density (minPts ≈ 2×dimensions is a common heuristic) and neighborhood counting degrades in high dimensions (curse of dimensionality); hierarchical clustering keeps an $O(n^2)$ distance matrix, unfit for large data.

Define core, border, and noise points in DBSCAN; how do larger/smaller ε and minPts change the clustering?

Distinguish density-reachable from density-connected; why is reachability asymmetric while connectedness is symmetric?

Core differences between DBSCAN and K-Means; which data shapes suit each; why does DBSCAN fail on uneven density?

Single, complete, and Ward linkage criteria in hierarchical clustering; what is the chaining effect?

Time complexity of DBSCAN and index acceleration; why is ε hard to choose in high dimensions?