# DBSCAN and OPTICS

Density-based clustering that finds arbitrarily shaped clusters and labels sparse points as noise.

**Rests on:** Scatterplots and Relationships

*Machine Learning · Unsupervised Learning*


## Why learn this

You have already met k-means and hierarchical clustering. K-means forces clusters to be round and roughly equal in size; hierarchical clustering builds a tree but still needs you to decide where to cut it. DBSCAN and OPTICS are the tools you reach for when your data has clusters of any shape — a long curved street of shops, a ring of factories around a lake — and when some points simply do not belong to any cluster at all. They are used everywhere in applied machine learning: finding fraud rings that spread out irregularly, grouping similar customer behaviours that do not form neat blobs, and preprocessing data before you build a model. Learning this unlocks the skill of 'exploratory data analysis' — looking at a scatter plot of your data and finding structure in it without knowing in advance how many groups exist.


## The intuition

DBSCAN works like marking out friendship groups on a map of a city. Imagine every house in the city has a GPS coordinate, and you want to find neighbourhoods — clusters — of houses that are close together. The rule is simple: two houses are 'friends' if they are within some walking distance (call it 'epsilon'). But a house is not just friends with its immediate neighbours — it's friends with all the friends of its friends, and so on. So a cluster is all the houses you can reach by hopping from one house to another within epsilon distance, each hop taking you to a house that itself has at least a certain number of friends within epsilon. Houses that are part of a dense crowd — where each house has many neighbours — form the core of a cluster. Houses on the edge of the crowd, with some neighbours but not enough to be a core, are still part of the cluster because they are reachable from a core house. Houses that are all alone, with hardly any neighbours within epsilon, are labelled as noise — they don't belong to any cluster. This is the key difference from k-means: k-means forces every point into a cluster, but DBSCAN says 'this point is an outlier, it belongs to nothing'. The shape of the cluster is whatever the data naturally forms — a long thin line of houses along a river, a circle around a pond — because there is no requirement for a round shape.


## An analogy

Think of a national park ranger trying to map out wolf packs from GPS collar data. The ranger has a rule: a wolf is a 'neighbour' if it is within 10 kilometers of another wolf. But a pack is not just pairs of wolves within 10 km — it is the entire set of wolves you can reach by hopping from one wolf to another, where each wolf you hop from has at least 3 other wolves within 10 km (a 'core' wolf). Wolves on the edge of a pack, with fewer than 3 neighbours, are still part of the pack if they are within 10 km of a core wolf. A lone wolf, far away from any cluster of 3, is labelled as 'noise' — it doesn't belong to any pack. The ranger's map does not assume that packs are round or equal in size; a pack might be a long line of wolves following a river, or a sprawling group around a den, or a small tight group of 4 wolves and a separate one of 20. This is exactly what DBSCAN does with numbers. But the analogy breaks down in one place: the ranger knows what a 'pack' is, and can use her knowledge to set the two numbers — the distance (epsilon) and the minimum pack size (the minimum points needed). In DBSCAN, you have to choose these numbers yourself, and the result is very sensitive to them. If the ranger sets the distance too small (say 2 km), she will break every pack into tiny fragments; if too large (say 50 km), she will merge all packs into one blob. That sensitivity is the practical difficulty of DBSCAN, and OPTICS is a variant that softens it by not requiring you to fix the distance in advance — it shows you the structure at all distances at once.


## Definition

DBSCAN is a clustering algorithm that groups points that are closely packed together — points with many nearby neighbours — into clusters of arbitrary shape, and labels points that lie alone in low-density regions as noise, based on two parameters: epsilon (the maximum distance for two points to be considered neighbours) and the minimum number of neighbours a point must have to start a cluster.


## How it connects

You have already studied k-means and hierarchical clustering in your notes, and DBSCAN and OPTICS are presented in Simplified Machine Learning as the answer to k-means' assumption of spherical, equally-sized clusters. K-means works by placing k centroids and assigning points to the nearest centroid; it inherits that geometry — clusters are always roughly circular in a 2D plot. DBSCAN has no centroids; it works purely on distances between points, so a cluster can be a spiral, a C-shape, or a long thin line. Your notes on hierarchical clustering mention that you can cut the dendrogram at any level to choose the number of clusters afterwards; DBSCAN instead asks you to commit to a density threshold (epsilon) up front, but OPTICS produces a structure like a dendrogram's 'reachability plot' that lets you choose clusters at various densities afterwards, similar in spirit to cutting a dendrogram. Noise labelling is a feature absent from both k-means and hierarchical clustering — every point belongs to a cluster there, but DBSCAN explicitly says some points are noise.


## The mathematics

DBSCAN and OPTICS are methods for finding groups (clusters) in data. They do not assume the groups have a specific shape, like circles or ellipses. Instead, they rely on two simple ideas: distance between points, and how many neighbors a point has.

The first idea is distance. To decide if two points are close, we measure the straight-line distance between them. If a point has coordinates (x1, y1) and another has (x2, y2), the distance is found by taking the difference in x, squaring it, taking the difference in y, squaring it, adding those two squares together, and then taking the square root of that sum. This is the standard way to measure distance on a flat plane.

The second idea is density. DBSCAN uses two settings you choose:
1. epsilon (read 'epsilon'): A distance threshold. Any point within this distance of another point is considered a neighbor.
2. minPts (read 'min-points'): A count threshold. A point is called a 'core point' if it has at least minPts neighbors within the epsilon distance, including itself.

DBSCAN works by looking for connected groups of core points. It picks an unvisited point. If that point is a core point, it starts a new cluster. Then it looks at all the neighbors of that core point. If a neighbor is also a core point, it joins the same cluster, and we look at its neighbors too. This process continues, expanding the cluster like a ripple, until no more core points can be added. Points that are not part of any dense group (not reachable from a core point) are labeled as noise.

OPTICS is similar but handles varying densities better. Instead of using a fixed epsilon for everyone, OPTICS calculates a 'reachability distance' for each point. This distance tells you how far you would have to look around a point to find its nearest neighbor that is already part of a cluster. By sorting all points by this reachability distance, you get a plot. In this plot, low values (valleys) indicate dense clusters, and high values (peaks) indicate gaps between clusters.


## A worked example

We have six points on a flat map, with coordinates (x, y) in kilometres: A(1, 2), B(2, 3), C(3, 2), D(8, 8), E(9, 9), F(10, 8). We set epsilon = 2 km and minPts = 3 (so a point must have at least 3 neighbours within 2 km, including itself).

Step 1: Distance between A and B.
First, find the difference in x: 2 - 1 = 1. Square it: 1 * 1 = 1.
Next, find the difference in y: 3 - 2 = 1. Square it: 1 * 1 = 1.
Add the squares: 1 + 1 = 2.
Take the square root: sqrt(2) ≈ 1.41 km.
This distance is less than epsilon (2 km), so B is a neighbour of A.

Step 2: Distance between A and C.
Difference in x: 3 - 1 = 2. Square it: 4.
Difference in y: 2 - 2 = 0. Square it: 0.
Add the squares: 4 + 0 = 4.
Take the square root: sqrt(4) = 2.0 km.
This distance is exactly equal to epsilon, so C counts as a neighbour of A.

Step 3: Distance between B and C.
Difference in x: 3 - 2 = 1. Square it: 1.
Difference in y: 2 - 3 = -1. Square it: 1 (note that squaring a negative number gives a positive result).
Add the squares: 1 + 1 = 2.
Take the square root: sqrt(2) ≈ 1.41 km.
This is less than epsilon, so B and C are neighbours.

Step 4: Check if A is a core point.
A's neighbours within 2 km are B and C. Including A itself, the total count is 3 points (A, B, C).
The rule minPts is 3. Since 3 >= 3, A is a core point. It starts Cluster 1.

Step 5: Expand from A to its neighbours B and C.
Check B: Its neighbours within 2 km are A (distance 1.41) and C (distance 1.41). Including itself, the count is 3. So B is a core point. It joins Cluster 1.
Check C: Its neighbours within 2 km are A (distance 2.0) and B (distance 1.41). Including itself, the count is 3. So C is a core point. It joins Cluster 1.
Since B and C are core points, we check their neighbours too. But all their neighbours (A, B, C) are already in Cluster 1. Cluster 1 is complete: {A, B, C}.

Step 6: Move to the next unvisited point, D(8, 8).
Find neighbours of D within 2 km.
Distance D to E(9, 9): sqrt((9-8)^2 + (9-8)^2) = sqrt(1+1) = sqrt(2) ≈ 1.41 km. This is < 2.
Distance D to F(10, 8): sqrt((10-8)^2 + (8-8)^2) = sqrt(4+0) = 2.0 km. This is <= 2.
D's neighbours are E and F. Including itself, the count is 3. Since 3 >= 3, D is a core point. It starts Cluster 2.

Step 7: Expand from D to its neighbours E and F.
Check E(9, 9): Neighbours within 2 km are D (1.41) and F (distance sqrt((10-9)^2 + (8-9)^2) = sqrt(1+1) = 1.41). Count is 3. E is a core point. Joins Cluster 2.
Check F(10, 8): Neighbours within 2 km are D (2.0) and E (1.41). Count is 3. F is a core point. Joins Cluster 2.
Cluster 2 is complete: {D, E, F}.

Step 8: Check for connections between clusters.
We check if any point in Cluster 1 is within epsilon of any point in Cluster 2.
The closest points are C(3, 2) and D(8, 8).
Distance C to D: sqrt((8-3)^2 + (8-2)^2) = sqrt(5^2 + 6^2) = sqrt(25 + 36) = sqrt(61) ≈ 7.81 km.
This is much larger than epsilon (2 km). There is no connection.

Result: Two separate clusters found: Cluster 1 = {A, B, C} and Cluster 2 = {D, E, F}. No points were left out as noise in this example.


## From scratch, in Python

```python
# We'll implement a simple version of DBSCAN from scratch.
# No external libraries, just plain Python and a bit of math.

import math

# A point is a tuple of two numbers: (x, y)
# A list of points: each element is a tuple
points = [(1, 2), (2, 3), (3, 2), (8, 8), (9, 9), (10, 8)]

epsilon = 2.0
min_pts = 3

# Function to compute Euclidean distance between two tuples
def distance(p, q):
    return math.sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2)

# Function to find all neighbours of a point within epsilon
def find_neighbours(point_index, points, epsilon):
    neighbours = []
    for i in range(len(points)):
        if distance(points[point_index], points[i]) <= epsilon:
            neighbours.append(i)
    return neighbours

# Main DBSCAN algorithm
# We keep a label for each point: -1 = noise, 0 = unvisited, >0 = cluster id
labels = [0] * len(points)  # start all as unvisited
cluster_id = 0

for i in range(len(points)):
    if labels[i] != 0:
        continue  # already processed
    neighbours = find_neighbours(i, points, epsilon)
    if len(neighbours) < min_pts:
        labels[i] = -1  # mark as noise for now
    else:
        cluster_id += 1
        labels[i] = cluster_id
        # Expand the cluster
        queue = list(neighbours)
        for j in queue:
            if labels[j] == -1:
                labels[j] = cluster_id  # noise point becomes border point
            if labels[j] != 0:
                continue  # already assigned
            labels[j] = cluster_id
            j_neighbours = find_neighbours(j, points, epsilon)
            if len(j_neighbours) >= min_pts:
                for k in j_neighbours:
                    if labels[k] == 0 or labels[k] == -1:
                        if labels[k] == -1:
                            labels[k] = cluster_id
                        elif labels[k] == 0:
                            labels[k] = cluster_id
                            queue.append(k)

print(labels)  # [1, 1, 1, 2, 2, 2]
```


## The same thing, with a framework

```python
In real applications, you would use scikit-learn: `from sklearn.cluster import DBSCAN; clustering = DBSCAN(eps=2.0, min_samples=3).fit(points)`. The `fit` method does exactly what our from-scratch code does — it computes all pairwise distances (internally optimised with a tree structure) and applies the same expansion rules. The result is a labels array where -1 means noise. For OPTICS, scikit-learn has `OPTICS(min_samples=3).fit(points)` which produces a reachability plot without requiring epsilon.
```


## What the code does

We start with a list of points. A list in Python is an ordered collection that can be changed; here each point is a tuple — a list that cannot be changed once made — holding two numbers, the x and y coordinates. The `distance` function takes two tuples and computes the straight-line distance squared then square-rooted. The `find_neighbours` function goes through every point in the list and checks if it is within epsilon of the given point, collecting the indices of those that are. The main loop goes through each point: if it has been assigned a label already (cluster id or noise), it skips; otherwise it finds its neighbours. If there are fewer than min_pts neighbours, it labels the point as noise (-1). If there are enough, it starts a new cluster, assigns the cluster id, and then expands the cluster by looking at each neighbour: if that neighbour is noise, it gets absorbed (becomes a border point); if unvisited, it is added to the cluster and, if it has enough neighbours itself, its neighbours are also considered for addition. The `queue` list acts as a to-do list of points to process next.


## Common misconceptions

**DBSCAN requires you to know the number of clusters** — Like k-means, I have to tell DBSCAN how many clusters there are before I run it.

DBSCAN does not take a 'k' parameter; it discovers the number of clusters from the density of the data. You only set epsilon and minPts. In fact: You set a density threshold (epsilon and minPts), and the algorithm finds however many clusters the data supports — it can even find zero clusters if everything is noise.

**Noise means error** — If the model labels some points as noise, it means the model made a mistake or my data is bad.

Noise labelling is a deliberate feature. Not every point belongs to a cluster; outliers are real. In fact: Noise is a correct output for points in low-density regions. It is useful for anomaly detection.

**Clusters must be round** — All clustering algorithms produce round clusters; that is just how clustering works.

That is a property of k-means, not of clustering in general. DBSCAN has no shape assumption. In fact: DBSCAN can find clusters of any shape — long lines, rings, spirals — based purely on density connectedness.

**Epsilon is easy to guess** — I'll just pick a rough distance like 1.0, it will probably work fine.

Results are highly sensitive to epsilon. A small change can split or merge clusters completely. In fact: You need to look at a k-distance plot or run OPTICS to choose a meaningful epsilon — this is the practical difficulty.

**All points must be in a cluster** — Clusters must cover every point in the dataset; noise is just a failure to find a home.

DBSCAN explicitly allows points to be noise, and that is useful. In fact: Noise points are legitimate: they are outliers, or new unseen patterns, that do not belong to any dense group.


## In short

DBSCAN groups points that are close together (within epsilon) and densely connected (at least minPts neighbours), discovering arbitrarily shaped clusters and labelling sparse points as noise. It relies only on distance arithmetic — the Pythagorean theorem. Its main weakness is parameter sensitivity to epsilon; OPTICS removes that by showing cluster structure at all densities. Use DBSCAN when you have non-round clusters and outliers.


## Where this is used

DBSCAN and OPTICS are used across a wide range of AI systems, though less in the core of large language models (LLMs) than in the data preparation and analysis that supports them. Let me be honest: the transformer architecture underlying modern LLMs does not use DBSCAN internally — the attention mechanism is based on dot products and matrix multiplications, not density clustering. However, DBSCAN is heavily used in the surrounding machine learning ecosystem. In **retrieval-augmented generation (RAG)**, where a language model is given relevant chunks of documents to answer a question, DBSCAN is used to **cluster embeddings** — numerical vectors representing the meaning of text. You might have documents about 'dog care' and 'dog nutrition'; after embedding them, the vectors form two dense groups. DBSCAN can find those groups without you knowing in advance how many topics there are, and then you can pick a representative document from each cluster to insert into the model's context. You could use k-means, but k-means would force every document into a cluster even if it is an outlier; DBSCAN will label a one-off document about 'cat behaviour' as noise, so it does not pollute the retrieval. Developers using the `sentence-transformers` library to embed documents, then `sklearn.cluster.DBSCAN` to cluster those embeddings, and then using the cluster centres as prompt context — that is a real pipeline. In **small language models running on devices** (phones, laptops), DBSCAN is used during the data curation phase: you have millions of text snippets from a mobile keyboard's autocomplete, and you want to find the distinct 'styles' or 'topics' of typing to build a small model that predicts the next word. Clustering the embeddings with DBSCAN reveals natural groups (e.g., professional emails vs casual chats) and helps sample a representative subset for training. The noise points are discarded as typos or rare usages that would confuse the model. In **agentic systems** that plan and call tools, DBSCAN appears in the **memory management** of an agent. An agent that retrieves past experiences to decide its next action might store each past interaction as an embedding; clustering these embeddings with OPTICS lets the agent see groups of similar situations ('when I was asked to sort a list, I used the sort function') and form generalised plans. OPTICS is preferred over DBSCAN here because new experiences arrive continuously and you do not want to re-tune epsilon each time. In **everyday applied machine learning**, DBSCAN and OPTICS are staples for **anomaly detection** — finding fraud in credit card transactions (fraudulent transactions form sparse clusters, legitimate ones form dense clusters), network intrusion detection, and even in astronomy for finding star clusters. They are also used in **image segmentation**: clustering pixel features (colour, position) to group pixels into objects; DBSCAN can find arbitrarily shaped objects, unlike k-means which always produces blob-shaped segments. For building software with DBSCAN, a data scientist typically reaches for scikit-learn's `DBSCAN` or `OPTICS` implementations. What they write is short — a few lines to load data, scale features (DBSCAN is sensitive to feature scales because it uses Euclidean distance), and fit the model. What breaks when done badly: choosing the wrong epsilon. If epsilon is too large, all points merge into one cluster and noise disappears; if too small, every point becomes noise. This parameter sensitivity is the classic pitfall. OPTICS helps by giving you a reachability plot to choose epsilon after the fact, but that requires visualisation and human judgement.


---

Read this on the web: https://basavapurushottam.com/learn-ai/dbscan-and-optics
