{"course":{"slug":"machine-learning-foundations","title":"Machine Learning, Foundations","url":"https://addaly.com/learn/machine-learning-foundations","level":"intermediate","track":"start"},"lesson":{"slug":"density-and-hierarchy","title":"DBSCAN and hierarchical clustering: when shape and structure matter","url":"https://addaly.com/learn/machine-learning-foundations/density-and-hierarchy","position":65,"of":92,"minutes":8,"answer":"DBSCAN defines clusters as dense regions, so it finds arbitrary shapes, decides the cluster count itself and labels outliers as noise, at the cost of assuming one density threshold suits the whole dataset.","keyIdea":"DBSCAN defines clusters as dense regions, so it finds arbitrary shapes, decides the cluster count itself and labels outliers as noise, at the cost of assuming one density threshold suits the whole dataset, which HDBSCAN removes."},"body":{"format":"markdown","text":"## DBSCAN: clusters as dense regions\n\nk-means asks which centre a point is nearest. DBSCAN asks a different question: is this point in a crowded neighbourhood?\n\nTwo parameters define the answer. `eps` is a radius. `min_samples` is how many points must be within that radius for a point to count as a **core point**. Core points that are within `eps` of each other join into one cluster. Points near a cluster but not themselves core are **border points**, and points in neither category are labelled **noise**, with cluster id -1.\n\n```python\nfrom sklearn.cluster import DBSCAN\nlabels = DBSCAN(eps=0.5, min_samples=5).fit_predict(X_scaled)\n(labels == -1).sum()      # how many were called noise\n```\n\nThree consequences follow directly, and they are exactly the things k-means could not do.\n\n**Clusters can be any shape.** Two interleaved crescents, a ring around a blob, a long winding band: DBSCAN follows density, so shape is irrelevant. k-means cannot find any of them.\n\n**You do not specify the number of clusters.** It emerges from the density structure.\n\n**Outliers are labelled as outliers** rather than being forced into a group. For many purposes this alone justifies the method.\n\n## Where DBSCAN struggles\n\n**Varying density.** One `eps` for the whole dataset means a value that separates a dense region will merge everything in a sparse one, and a value tuned for the sparse region will fragment the dense one. This is the main practical limitation.\n\n**HDBSCAN** solves it by building a hierarchy across all density levels and extracting the most stable clusters from it. It has one intuitive parameter (the minimum cluster size) and it is generally the better default now. It is a separate free package and it is worth installing.\n\n**Choosing eps.** The standard method: compute each point's distance to its `min_samples`-th nearest neighbour, sort those distances, and plot them. The curve has a knee, and `eps` at the knee is a good starting value. This is a more reliable elbow than the k-means one because the quantity being plotted is directly meaningful.\n\n**High dimensions.** Density is a volume-based notion, and volume behaves badly in high dimensions for the reasons in the k-NN lesson. Reduce dimensions first.\n\n## Hierarchical clustering: the whole tree\n\nInstead of one partition, build a nested sequence. Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest, recording the order. The result is a dendrogram: a tree you can cut at any height to get any number of clusters.\n\n```python\nfrom scipy.cluster.hierarchy import linkage, dendrogram, fcluster\nZ = linkage(X_scaled, method=\"ward\")\nlabels = fcluster(Z, t=5, criterion=\"maxclust\")\n```\n\nThe **linkage** choice defines what \"closest\" means between two clusters, and it changes the results substantially:\n\n- **Ward** minimises the increase in within-cluster variance. Produces compact, similar-sized clusters. The usual default.\n- **Complete** uses the maximum distance between members. Compact clusters, sensitive to outliers.\n- **Average** uses the mean distance. A middle option.\n- **Single** uses the minimum distance. Can follow chains of points, which finds elongated shapes and also produces the chaining effect where two distinct clusters merge because of one bridging point.\n\nThe dendrogram itself is often the real output. Being able to see that two segments merge at a low height (they are similar) while a third joins only at the top (it is different) tells you more than any flat partition, and it is the reason hierarchical clustering survives in fields like biology where the nesting is the object of interest.\n\nIts cost is quadratic in memory and roughly cubic in time, so it is impractical above about 20,000 rows without approximation.\n\n## Choosing between the three\n\n- Roughly spherical groups, large data, need speed: **k-means**.\n- Arbitrary shapes, unknown cluster count, outliers you want identified: **HDBSCAN**.\n- Small data, and you want to see the nesting: **hierarchical with a dendrogram**.\n- You want soft assignments and elliptical clusters: **Gaussian mixture**.\n\nAnd run at least two of them. If k-means and HDBSCAN broadly agree, the structure is probably real. If they disagree completely, that disagreement is the most informative result you have, and it usually means the groups are not well separated in the space you built."},"check":{"question":"A dataset has two dense city clusters and one sparse rural spread. DBSCAN with a single eps either merges the cities or shatters the rural region into noise. What is the underlying limitation?","options":[{"text":"DBSCAN requires standardised features, and the geographic coordinates were left unscaled.","correct":false,"tempting":"Scaling matters for any distance method, but scaling coordinates uniformly would not resolve a genuine difference in density between regions."},{"text":"min_samples is too high for the rural region, and lowering it would fix both cases.","correct":false,"tempting":"Lowering min_samples helps the sparse region but simultaneously makes the dense regions merge more readily, so the trade-off remains."},{"text":"DBSCAN cannot find non-convex clusters, which is what a dispersed rural region is.","correct":false,"tempting":"Finding non-convex shapes is precisely DBSCAN's strength; the difficulty here is density variation, not shape."},{"text":"A single eps sets one density threshold for the whole dataset, and no single value can suit regions whose densities differ by an order of magnitude, which is what HDBSCAN's hierarchy across density levels addresses.","correct":true}]},"prev":{"slug":"how-many-clusters","title":"Choosing k, and why the elbow rarely helps","url":"https://addaly.com/learn/machine-learning-foundations/how-many-clusters"},"next":{"slug":"principal-components","title":"PCA: fewer columns, and what you gave up","url":"https://addaly.com/learn/machine-learning-foundations/principal-components"},"authorship":"Founder and series editor: Dr Mustafa Mun. Written by AI models to a written standard. Exam keys checked blind by a second model: 3,665 of 3,666 agreed. Academic review invited.","review":{"status":"Draft, open for academic review"},"cite":"Addaly (2026) 'DBSCAN and hierarchical clustering: when shape and structure matter', in Machine Learning, Foundations. Edited by M. Mun. Addaly. Available at: https://addaly.com/learn/machine-learning-foundations/density-and-hierarchy (Accessed: 13 October 2026).","licence":{"name":"CC BY-NC-SA 4.0","url":"https://creativecommons.org/licenses/by-nc-sa/4.0/"},"reader":{"schema":1,"title":"DBSCAN and hierarchical clustering: when shape and structure matter","courseTitle":"Machine Learning, Foundations","module":{"index":7,"slug":"learning-without-labels","title":"Learning without labels, and learning a representation"},"answer":null,"keyIdea":"DBSCAN defines clusters as dense regions, so it finds arbitrary shapes, decides the cluster count itself and labels outliers as noise, at the cost of assuming one density threshold suits the whole dataset, which HDBSCAN removes.","hero":{"kind":"plate","image":null,"alt":null,"caption":null},"blocks":[{"t":"h2","id":"dbscan-clusters-as-dense-regions","runs":[{"text":"DBSCAN: clusters as dense regions"}]},{"t":"p","runs":[{"text":"k-means asks which centre a point is nearest. DBSCAN asks a different question: is this point in a crowded neighbourhood?"}]},{"t":"p","runs":[{"text":"Two parameters define the answer. "},{"text":"eps","code":true},{"text":" is a radius. "},{"text":"min_samples","code":true},{"text":" is how many points must be within that radius for a point to count as a "},{"text":"core point","b":true},{"text":". Core points that are within "},{"text":"eps","code":true},{"text":" of each other join into one cluster. Points near a cluster but not themselves core are "},{"text":"border points","b":true},{"text":", and points in neither category are labelled "},{"text":"noise","b":true},{"text":", with cluster id -1."}]},{"t":"code","lang":"python","label":"Python","text":"from sklearn.cluster import DBSCAN\nlabels = DBSCAN(eps=0.5, min_samples=5).fit_predict(X_scaled)\n(labels == -1).sum()      # how many were called noise"},{"t":"p","runs":[{"text":"Three consequences follow directly, and they are exactly the things k-means could not do."}]},{"t":"p","runs":[{"text":"Clusters can be any shape.","b":true},{"text":" Two interleaved crescents, a ring around a blob, a long winding band: DBSCAN follows density, so shape is irrelevant. k-means cannot find any of them."}]},{"t":"p","runs":[{"text":"You do not specify the number of clusters.","b":true},{"text":" It emerges from the density structure."}]},{"t":"p","runs":[{"text":"Outliers are labelled as outliers","b":true},{"text":" rather than being forced into a group. For many purposes this alone justifies the method."}]},{"t":"h2","id":"where-dbscan-struggles","runs":[{"text":"Where DBSCAN struggles"}]},{"t":"p","runs":[{"text":"Varying density.","b":true},{"text":" One "},{"text":"eps","code":true},{"text":" for the whole dataset means a value that separates a dense region will merge everything in a sparse one, and a value tuned for the sparse region will fragment the dense one. This is the main practical limitation."}]},{"t":"p","runs":[{"text":"HDBSCAN","b":true},{"text":" solves it by building a hierarchy across all density levels and extracting the most stable clusters from it. It has one intuitive parameter (the minimum cluster size) and it is generally the better default now. It is a separate free package and it is worth installing."}]},{"t":"p","runs":[{"text":"Choosing eps.","b":true},{"text":" The standard method: compute each point’s distance to its "},{"text":"min_samples","code":true},{"text":"-th nearest neighbour, sort those distances, and plot them. The curve has a knee, and "},{"text":"eps","code":true},{"text":" at the knee is a good starting value. This is a more reliable elbow than the k-means one because the quantity being plotted is directly meaningful."}]},{"t":"p","runs":[{"text":"High dimensions.","b":true},{"text":" Density is a volume-based notion, and volume behaves badly in high dimensions for the reasons in the k-NN lesson. Reduce dimensions first."}]},{"t":"h2","id":"hierarchical-clustering-the-whole-tree","runs":[{"text":"Hierarchical clustering: the whole tree"}]},{"t":"p","runs":[{"text":"Instead of one partition, build a nested sequence. Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest, recording the order. The result is a dendrogram: a tree you can cut at any height to get any number of clusters."}]},{"t":"code","lang":"python","label":"Python","text":"from scipy.cluster.hierarchy import linkage, dendrogram, fcluster\nZ = linkage(X_scaled, method=\"ward\")\nlabels = fcluster(Z, t=5, criterion=\"maxclust\")"},{"t":"p","runs":[{"text":"The "},{"text":"linkage","b":true},{"text":" choice defines what “closest” means between two clusters, and it changes the results substantially:"}]},{"t":"ul","items":[[{"text":"Ward","b":true},{"text":" minimises the increase in within-cluster variance. Produces compact, similar-sized clusters. The usual default."}],[{"text":"Complete","b":true},{"text":" uses the maximum distance between members. Compact clusters, sensitive to outliers."}],[{"text":"Average","b":true},{"text":" uses the mean distance. A middle option."}],[{"text":"Single","b":true},{"text":" uses the minimum distance. Can follow chains of points, which finds elongated shapes and also produces the chaining effect where two distinct clusters merge because of one bridging point."}]]},{"t":"p","runs":[{"text":"The dendrogram itself is often the real output. Being able to see that two segments merge at a low height (they are similar) while a third joins only at the top (it is different) tells you more than any flat partition, and it is the reason hierarchical clustering survives in fields like biology where the nesting is the object of interest."}]},{"t":"p","runs":[{"text":"Its cost is quadratic in memory and roughly cubic in time, so it is impractical above about 20,000 rows without approximation."}]},{"t":"h2","id":"choosing-between-the-three","runs":[{"text":"Choosing between the three"}]},{"t":"ul","items":[[{"text":"Roughly spherical groups, large data, need speed: "},{"text":"k-means","b":true},{"text":"."}],[{"text":"Arbitrary shapes, unknown cluster count, outliers you want identified: "},{"text":"HDBSCAN","b":true},{"text":"."}],[{"text":"Small data, and you want to see the nesting: "},{"text":"hierarchical with a dendrogram","b":true},{"text":"."}],[{"text":"You want soft assignments and elliptical clusters: "},{"text":"Gaussian mixture","b":true},{"text":"."}]]},{"t":"p","runs":[{"text":"And run at least two of them. If k-means and HDBSCAN broadly agree, the structure is probably real. If they disagree completely, that disagreement is the most informative result you have, and it usually means the groups are not well separated in the space you built."}]}],"check":{"question":[{"text":"A dataset has two dense city clusters and one sparse rural spread. DBSCAN with a single eps either merges the cities or shatters the rural region into noise. What is the underlying limitation?"}],"options":[{"text":[{"text":"DBSCAN requires standardised features, and the geographic coordinates were left unscaled."}],"correct":false,"tempting":[{"text":"Scaling matters for any distance method, but scaling coordinates uniformly would not resolve a genuine difference in density between regions."}]},{"text":[{"text":"min_samples is too high for the rural region, and lowering it would fix both cases."}],"correct":false,"tempting":[{"text":"Lowering min_samples helps the sparse region but simultaneously makes the dense regions merge more readily, so the trade-off remains."}]},{"text":[{"text":"DBSCAN cannot find non-convex clusters, which is what a dispersed rural region is."}],"correct":false,"tempting":[{"text":"Finding non-convex shapes is precisely DBSCAN’s strength; the difficulty here is density variation, not shape."}]},{"text":[{"text":"A single eps sets one density threshold for the whole dataset, and no single value can suit regions whose densities differ by an order of magnitude, which is what HDBSCAN’s hierarchy across density levels addresses."}],"correct":true,"tempting":null}],"order":[0,3,2,1],"why":null},"prev":{"slug":"how-many-clusters","title":"Choosing k, and why the elbow rarely helps","minutes":8},"next":{"slug":"principal-components","title":"PCA: fewer columns, and what you gave up","minutes":9}}}