Building
DBSCAN Algorithm
from Scratch in Python
Without relying on high-level libraries
1 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
Table of Contents
1. Introduction to DBSCAN
2. Fundamental Concepts of DBSCAN
3. The Structure of a DBSCAN
4. Implementation DBSCAN from Scratch in Python
a. Import Necessary Libraries
b. Define the Distance Function
c. Identify Core Points
d. DBSCAN Algorithm
e. Expand Cluster
f. Visualize the Results
g. Test the Implementation
5. Conclusion
2 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
1. Introduction to DBSCAN Algorithm
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a powerful clustering algorithm used in machine
learning and data mining. Unlike other clustering algorithms like K-means, DBSCAN does not require the number of
clusters to be specified beforehand and can discover clusters of arbitrary shape. In this article, we will explain the
fundamental concepts of DBSCAN and provide a step-by-step guide to implementing it from scratch in Python
2. Fundamental Concepts of DBSCAN
DBSCAN relies on two key parameters:
1. Epsilon (ε): The maximum distance between two samples for them to be considered as part of the same
neighborhood.
2. MinPts: The minimum number of samples in a neighborhood to define a cluster.
Based on these parameters, DBSCAN classifies points into three categories:
• Core Point: A point with at least MinPts neighbors within ε.
• Border Point: A point that is not a core point but is in the neighborhood of a core point.
• Noise Point: A point that is neither a core point nor a border point.
3 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
3. The Structure of a DBSCAN Algorithm
This Structure includes the steps and sub-steps with appropriate labels and connections. Each step corresponds to a
function or a key part of the process described in the provided implementation.
4 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
4. Implementation in Python
Let's implement a simple DBSCAN Algorithm in Python.
Step 1: Import Necessary Libraries
We will start by importing the necessary libraries. Since we are implementing DBSCAN from scratch, we will
only use basic libraries like numpy.
import numpy as np
import [Link] as plt
from collections import deque
Step 2: Define the Distance Function
We will use the Euclidean distance to measure the distance between points.
Distance Function: euclidean_distance computes the Euclidean distance between two points
def euclidean_distance(point1, point2):
return [Link]([Link]((point1 - point2) ** 2))
Step 3: Identify Core Points
Next, we need a function to find the neighbors of a point within ε distance.
Get Neighbors: get_neighbors finds all points within ε distance of a given point.
def get_neighbors(point, data, epsilon):
neighbors = []
for i in range(len(data)):
if euclidean_distance(point, data[i]) < epsilon:
[Link](i)
return neighbors
Step 4: DBSCAN Algorithm
We will now implement the main DBSCAN algorithm. This function will initialize clusters and classify points.
DBSCAN Main Function: dbscan initializes the clustering process, iterates over each point, and calls expand_cluster
for core points.
def dbscan(data, epsilon, min_points):
labels = [-1] * len(data) # Initialize labels as -1 (unclassified)
cluster_id = 0
for i in range(len(data)):
if labels[i] != -1:
continue
neighbors = get_neighbors(data[i], data, epsilon)
if len(neighbors) < min_points:
labels[i] = -1 # Mark as noise
else:
cluster_id += 1
labels = expand_cluster(data, labels, i, neighbors, cluster_id, epsilon, min_points)
return labels
5 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
Step 5: Expand Cluster
This function will recursively expand the cluster by visiting each neighbor of the core point.
Expand Cluster: expand_cluster recursively assigns all reachable points to the same cluster.
def expand_cluster(data, labels, point_index, neighbors, cluster_id, epsilon, min_points):
labels[point_index] = cluster_id
queue = deque(neighbors)
while queue:
neighbor_index = [Link]()
if labels[neighbor_index] == -1:
labels[neighbor_index] = cluster_id
if labels[neighbor_index] != -1:
continue
labels[neighbor_index] = cluster_id
new_neighbors = get_neighbors(data[neighbor_index], data, epsilon)
if len(new_neighbors) >= min_points:
[Link](new_neighbors)
return labels
Step 6: Visualize the Results
Let's add a function to visualize the clusters.
Plot Clusters: plot_clusters visualizes the resulting clusters using different colors for each cluster and black for noise
def plot_clusters(data, labels):
unique_labels = set(labels)
colors = [[Link](each) for each in [Link](0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
if k == -1:
col = [0, 0, 0, 1] # Black used for noise.
class_member_mask = (labels == k)
xy = data[class_member_mask]
[Link](xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=6)
[Link]('DBSCAN Clustering')
[Link]()
6 ANSHUMAN JHA
Building DBSCAN Algorithm from Scratch in Python
Step 7: Test the Implementation
Finally, let's test our implementation with a sample dataset.
# Generate sample data
from [Link] import make_moons
data, _ = make_moons(n_samples=300, noise=0.1)
# Run DBSCAN
epsilon = 0.2
min_points = 5
labels = dbscan(data, epsilon, min_points)
# Plot the results
plot_clusters(data, labels)
5. Conclusion
In this article, we have built a DBSCAN algorithm from scratch in Python. We explained the fundamental
concepts, implemented each step with detailed explanations, and tested our implementation on a sample dataset.
DBSCAN is a robust clustering algorithm, especially useful for discovering clusters of arbitrary shape and
handling noise effectively. By understanding and implementing it from scratch, we gain deeper insights into its
workings and can customize it for specific applications.
Constructive comments and feedback are welcomed
7 ANSHUMAN JHA