Mastering DBSCAN: From Basics to Implementation

Greetings to aspiring data scientists! Today, we'll unlock the curious world of the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm. Standing out in the clustering landscape, DBSCAN is famous for its resilience to outliers and for eliminating the need for pre-set cluster numbers. This lesson will demystify DBSCAN through a Python-based implementation from scratch.

Let's start by peeling off the layers of DBSCAN. At its core, DBSCAN operates on concepts of density and noise. It identifies clusters as regions of high density separated by lower-density regions. Concurrently, it classifies low-density entities as noise, enhancing its robustness towards outliers. The secret recipe behind DBSCAN? A pair of parameters: Epsilon (Eps) and Minimum Points (MinPts), which guide the classification of points into categories of 'core', 'border', or 'outlier'.

With a foundational understanding, it's time to roll up our sleeves and implement DBSCAN from scratch.

We'll create a simple toy dataset using numpy arrays for the first hands-on task. This dataset represents a collection of points on a map that we'll be clustering.

data_points = np.array([
    [1.2, 1.9], [2.1, 2], [2, 3.5], [3.3, 3.9], [3.2, 5.1],
    [8.5, 7.9], [8.1, 7.8], [9.5, 6.5], [9.5, 7.2], [7.7, 8.6],
    [6.0, 6.0]
])

Next, we'll devise a function to calculate the Euclidean distance between the data points. The function uses numpy's linalg.norm to evaluate this distance, which reflects the shortest possible distance between two points.

def euclidean_distance(a, b):
    return np.linalg.norm(a - b, axis=-1)

This function evaluates the Euclidean distance $d(a, b)$ between points $a$ and $b$ using the formula:

$d(a, b) = \sqrt{{(a_1 - b_1)}^2 + {(a_2 - b_2)}^2 + \dots + {(a_n - b_n)}^2}$

where $a = (a_1, a_2, \dots, a_n)$ and $b = (b_1, b_2, \dots, b_n)$.

Armed with a dataset and the Euclidean distance function, we are prepared to implement DBSCAN.

We will use the following labels:

• 0 is noise or outlier data points, not belonging to any cluster.
• 1 is the data points in the first identified cluster.
• 2 is the data points in the second identified cluster.

Our function initially labels each point as an outlier. It then verifies if each point has at least MinPts within an Eps radius. If this condition is satisfied, the point qualifies as a core point. The code block below demonstrates these steps.

def dbscan(data, Eps, MinPt):
    point_label = [0] * len(data)
    # Initialize list to maintain count of surrounding points within radius Eps for each point. 
    point_count = []
    core = []
    noncore = []

    # Check for each point if it falls within the Eps radius of point at index i
    for i in range(len(data)):
        point_count.append([])
        for j in range(len(data)):
            if euclidean_distance(data[i], data[j]) <= Eps and i != j:
                point_count[i].append(j)
        
        # If a point has atleast MinPt points within its Eps radius (excluding itself), classify it as a core point, and vice versa
        if len(point_count[i]) >= MinPt:
            core.append(i)
        else:
            noncore.append(i)
    ...