Density-based Hierarchical

Density-based Hierarchical

1. Two Ideas Combined

• Density (DBSCAN): clusters = dense regions separated by sparse gaps. Finds arbitrary shapes, flags outliers, needs no $k$.
• Hierarchical: builds merge tree (dendrogram) — cut at any height for any $k$.

2. DBSCAN Rule

Point is core if ≥ $minPts$ neighbours within radius $ε$. Expand connected cores; non-reachable = noise.

pick unvisited p; if core: grow cluster via density-reachable chain
else mark noise (may later join another cluster)

Tune $ε$ by $k$-distance plot knee; $minPts ≈ 2×d$ heuristic.

3. Agglomerative Clustering

each point = cluster; repeat: merge nearest pair (single/complete/average linkage)
until one cluster; cut dendrogram for k

• Single linkage → chaining (moons OK, noise-sensitive).
• Complete / average → compact balls.

4. Limits

DBSCAN fails on varying density (one $ε$ fits all); hierarchical is $O(n²)$ — sample first for big $n$.

5. Exam Points

• Core / $ε$ / $minPts$ + trace — 5-7 marks, very frequent.
• Dendrogram + linkage types — 5 marks, frequent.
• Density vs $k$-means (shape, outliers) — 3 marks, frequent.