---
title: "DBSCAN and density-based clustering"
subject: "Data Mining"
chapter: 5
key: "semester_7/data_mining:dbscan-density-clustering"
source: https://www.bctengineer.com/q/semester_7/data_mining/dbscan-density-clustering
site: BCT Engineering
---

# DBSCAN and density-based clustering

Data Mining · Chapter 5: Cluster Analysis

- Asked in: year not given
- Video: [#26 Density Based Clustering - DBSCAN Algorithm |DM|](https://www.youtube.com/watch?v=81-ATJW-EGI) — Trouble- Free
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/dbscan-density-clustering
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-5

## Question

Describe DBSCAN Clustering. What are the advantages of Density based clustering?

## Short answer

DBSCAN groups points into density-connected clusters using parameters eps and MinPts, identifying core, border, and noise points. It finds arbitrary-shaped clusters without specifying cluster count, handles noise explicitly, and runs in O(n log n) with spatial indexing, but is sensitive to parameter choices and struggles with varying densities.

## Answer

**DBSCAN (Density-Based Spatial Clustering of Applications with Noise)** (Ester et al., 1996) defines a cluster as a maximal set of **density-connected** points, i.e. a dense region separated from other clusters by regions of low density. It can find clusters of arbitrary shape and marks noise.

#### Parameters and terms
- **ε (eps)**: radius of the neighbourhood of a point.
- **MinPts**: minimum number of points in an ε-neighbourhood for the point to be dense.
- **Core point**: has at least MinPts points (including itself) within ε.
- **Border point**: fewer than MinPts in its ε-neighbourhood but lies inside the neighbourhood of a core point.
- **Noise (outlier)**: neither core nor border.
- **Directly density-reachable**: q is within ε of a core point p. **Density-reachable**: reachable by a chain of directly reachable points. **Density-connected**: both points are density-reachable from a common core point.

#### Algorithm
```text
1. Mark all points unvisited.
2. Pick an unvisited point p; mark it visited.
3. If p is a core point: create a new cluster C, add p, and add all
   points in its eps-neighbourhood to a candidate set N.
     For each point q in N:
        if q is unvisited: mark visited; if q is core, add its
        eps-neighbourhood to N
        if q is not in any cluster, add q to C
   else mark p as noise (it may later become a border point).
4. Repeat until all points are visited.
```

#### Advantages of density-based clustering
- Finds clusters of **arbitrary shape** (not only spherical).
- **Does not need the number of clusters** in advance.
- **Handles noise and outliers** explicitly.
- Needs only one scan of the data; with a spatial index the cost is O(n log n).
- The result is not dependent on the order of the points (except for border points).
- Disadvantages: sensitive to ε and MinPts; struggles with clusters of very different densities and with high-dimensional data.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a core point in DBSCAN?
   A. A point with at least MinPts points (including itself) within eps
   B. A point at the centre of the data set
   C. A point with no neighbours
   D. The first point visited
   Answer: A. A core point has at least MinPts points in its eps-neighbourhood. (Key point: Core point)

2. What distinguishes a border point from noise?
   A. Border points have more than MinPts neighbours
   B. A border point has fewer than MinPts neighbours but lies in the neighbourhood of a core point; noise is neither core nor border
   C. Noise lies inside a core point's neighbourhood
   D. They are the same
   Answer: B. Border points are reachable from a core point though not dense themselves; noise is neither. (Key point: Border vs noise)

3. Which is an advantage of density-based clustering?
   A. It requires k to be given in advance
   B. It finds only spherical clusters
   C. It finds arbitrary-shaped clusters and handles noise
   D. It is insensitive to eps and MinPts
   Answer: C. DBSCAN needs no k, finds arbitrary shapes and marks noise explicitly. (Key point: Advantages)

4. Which is a disadvantage of DBSCAN?
   A. Cannot handle noise
   B. Struggles with clusters of very different densities and is sensitive to eps and MinPts
   C. Needs the number of clusters
   D. Always O(n^3)
   Answer: B. One global eps/MinPts cannot suit clusters of widely varying density. (Key point: Weakness)

## Related in Data Mining

- [Cluster analysis; K-means on height/width](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Akmeans-height-width) — Data Mining, chapter 5

## Related in other subjects

- [Field methods for in-situ density](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Afield-density-methods) — Soil Mechanics, chapter 2, asked 2×