xbe.at

Machine learning / Classification and clustering

Building DBSCAN Clustering Algorithm from Scratch in Python

8 min read, 15 sections

Contents
  1. Introduction to DBSCAN
  2. Understanding DBSCAN Parameters
  3. Implementing Distance Calculation
  4. Identifying Core Points
  5. Expanding Clusters
  6. DBSCAN Algorithm Implementation
  7. Visualizing DBSCAN Results
  8. Handling Different Data Distributions
  9. Parameter Sensitivity
  10. Real-Life Example: Geographical Clustering
  11. Optimizing DBSCAN Performance
  12. Handling High-Dimensional Data
  13. Real-Life Example: Image Segmentation
  14. Challenges and Limitations
  15. Additional Resources

Introduction to DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular clustering algorithm used in data mining and machine learning. It groups together points that are closely packed together, marking points that lie alone in low-density regions as outliers. Let's explore how to build this algorithm from scratch in Python.

import numpy as np
import matplotlib.pyplot as plt

# Generate sample data
np.random.seed(42)
X = np.random.randn(100, 2) * 0.5
X = np.r_[X, X + [2, 2], X + [-2, 2]]

plt.scatter(X[:, 0], X[:, 1], alpha=0.7)
plt.title("Sample Data for DBSCAN")
plt.show()

Understanding DBSCAN Parameters

DBSCAN requires two main parameters: epsilon (eps) and minimum points (min_pts). Epsilon defines the neighborhood distance, while min_pts sets the minimum number of points required to form a dense region. These parameters significantly influence the clustering results.

def plot_circles(X, eps):
    for point in X:
        circle = plt.Circle(point, eps, fill=False, linestyle='--')
        plt.gca().add_artist(circle)

eps = 0.5
min_pts = 5

plt.figure(figsize=(10, 5))
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], alpha=0.7)
plot_circles(X[:5], eps)
plt.title(f"Epsilon Neighborhoods (eps={eps})")

plt.subplot(122)
plt.scatter(X[:, 0], X[:, 1], alpha=0.7)
plt.scatter(X[0], X[1], s=100, c='red')
plt.title(f"Core Point (min_pts={min_pts})")
plt.show()

Implementing Distance Calculation

The first step in DBSCAN is calculating distances between points. We'll use Euclidean distance for this example, but other distance metrics can be used depending on the application.

def euclidean_distance(point1, point2):
    return np.sqrt(np.sum((point1 - point2) ** 2))

def get_neighbors(X, point_idx, eps):
    distances = [euclidean_distance(X[point_idx], other_point) for other_point in X]
    return [i for i, dist in enumerate(distances) if dist <= eps]

# Example usage
point_idx = 0
neighbors = get_neighbors(X, point_idx, eps)
print(f"Number of neighbors for point {point_idx}: {len(neighbors)}")

Identifying Core Points

Core points are those with at least min_pts neighbors within the epsilon distance. These form the basis of clusters in DBSCAN.

def find_core_points(X, eps, min_pts):
    core_points = []
    for i in range(len(X)):
        if len(get_neighbors(X, i, eps)) >= min_pts:
            core_points.append(i)
    return core_points

core_points = find_core_points(X, eps, min_pts)
print(f"Number of core points: {len(core_points)}")

plt.scatter(X[:, 0], X[:, 1], alpha=0.7)
plt.scatter(X[core_points, 0], X[core_points, 1], c='red', s=50)
plt.title("Core Points Identified")
plt.show()

Expanding Clusters

Once core points are identified, we expand clusters by including their neighbors and the neighbors of those neighbors, recursively.

def expand_cluster(X, labels, point_idx, neighbors, cluster_id, eps, min_pts):
    labels[point_idx] = cluster_id
    i = 0
    while i < len(neighbors):
        neighbor = neighbors[i]
        if labels[neighbor] == -1:  # Noise becomes border point
            labels[neighbor] = cluster_id
        elif labels[neighbor] == 0:  # Unvisited
            labels[neighbor] = cluster_id
            new_neighbors = get_neighbors(X, neighbor, eps)
            if len(new_neighbors) >= min_pts:
                neighbors.extend(new_neighbors)
        i += 1
    return labels

# This function will be used in the main DBSCAN algorithm

DBSCAN Algorithm Implementation

Now, let's put everything together to implement the complete DBSCAN algorithm.

def dbscan(X, eps, min_pts):
    labels = [0] * len(X)  # 0: unvisited, -1: noise
    cluster_id = 0
    core_points = find_core_points(X, eps, min_pts)
    
    for point_idx in range(len(X)):
        if labels[point_idx] != 0:
            continue
        if point_idx in core_points:
            cluster_id += 1
            neighbors = get_neighbors(X, point_idx, eps)
            labels = expand_cluster(X, labels, point_idx, neighbors, cluster_id, eps, min_pts)
        else:
            labels[point_idx] = -1  # Noise
    
    return labels

# Run DBSCAN
labels = dbscan(X, eps, min_pts)

Visualizing DBSCAN Results

Let's visualize the clustering results to see how DBSCAN has performed on our sample data.

unique_labels = set(labels)
colors = plt.cm.rainbow(np.linspace(0, 1, len(unique_labels)))

plt.figure(figsize=(10, 7))
for label, color in zip(unique_labels, colors):
    if label == -1:
        color = 'gray'  # Use gray for noise points
    class_member_mask = (np.array(labels) == label)
    xy = X[class_member_mask]
    plt.scatter(xy[:, 0], xy[:, 1], c=[color], alpha=0.7, label=f'Cluster {label}')

plt.title("DBSCAN Clustering Results")
plt.legend()
plt.show()

Handling Different Data Distributions

DBSCAN performs well on data with varying densities and non-spherical shapes. Let's test it on a more complex dataset.

from sklearn.datasets import make_moons

# Generate a more complex dataset
X_moons, _ = make_moons(n_samples=200, noise=0.05, random_state=42)

# Run DBSCAN with adjusted parameters
eps_moons = 0.2
min_pts_moons = 5
labels_moons = dbscan(X_moons, eps_moons, min_pts_moons)

# Visualize results
plt.figure(figsize=(10, 7))
unique_labels = set(labels_moons)
colors = plt.cm.rainbow(np.linspace(0, 1, len(unique_labels)))

for label, color in zip(unique_labels, colors):
    if label == -1:
        color = 'gray'
    class_member_mask = (np.array(labels_moons) == label)
    xy = X_moons[class_member_mask]
    plt.scatter(xy[:, 0], xy[:, 1], c=[color], alpha=0.7, label=f'Cluster {label}')

plt.title("DBSCAN on Complex Dataset")
plt.legend()
plt.show()

Parameter Sensitivity

DBSCAN's performance is sensitive to its parameters. Let's explore how changing eps affects clustering results.

def plot_dbscan_results(X, eps, min_pts):
    labels = dbscan(X, eps, min_pts)
    unique_labels = set(labels)
    colors = plt.cm.rainbow(np.linspace(0, 1, len(unique_labels)))
    
    for label, color in zip(unique_labels, colors):
        if label == -1:
            color = 'gray'
        class_member_mask = (np.array(labels) == label)
        xy = X[class_member_mask]
        plt.scatter(xy[:, 0], xy[:, 1], c=[color], alpha=0.7)
    plt.title(f"DBSCAN: eps={eps}, min_pts={min_pts}")

plt.figure(figsize=(15, 5))
eps_values = [0.1, 0.3, 0.5]

for i, eps in enumerate(eps_values):
    plt.subplot(1, 3, i+1)
    plot_dbscan_results(X_moons, eps, min_pts_moons)

plt.tight_layout()
plt.show()

Real-Life Example: Geographical Clustering

DBSCAN is particularly useful for geographical data. Let's use it to cluster cities based on their coordinates.

# Sample city data (longitude, latitude)
cities = np.array([
    [-122.4194, 37.7749],  # San Francisco
    [-122.2711, 37.8044],  # Berkeley
    [-122.0839, 37.3861],  # San Jose
    [-118.2437, 34.0522],  # Los Angeles
    [-117.1611, 32.7157],  # San Diego
    [-74.0060, 40.7128],   # New York City
    [-73.9442, 40.6782],   # Brooklyn
    [-73.7845, 40.9115],   # White Plains
    [-87.6298, 41.8781],   # Chicago
    [-87.9065, 41.9742],   # O'Hare Airport
])

# Run DBSCAN
eps_cities = 1  # Approximately 111 km
min_pts_cities = 2
labels_cities = dbscan(cities, eps_cities, min_pts_cities)

# Visualize results
plt.figure(figsize=(12, 8))
scatter = plt.scatter(cities[:, 0], cities[:, 1], c=labels_cities, cmap='viridis')
plt.colorbar(scatter)
plt.title("City Clusters based on Geographical Proximity")
plt.xlabel("Longitude")
plt.ylabel("Latitude")
plt.show()

Optimizing DBSCAN Performance

For large datasets, we can optimize DBSCAN using spatial indexing structures like KD-trees for faster neighbor searches.

from scipy.spatial import cKDTree

def get_neighbors_kdtree(tree, point, eps):
    return tree.query_ball_point(point, eps)

def dbscan_optimized(X, eps, min_pts):
    tree = cKDTree(X)
    labels = [0] * len(X)
    cluster_id = 0
    
    for point_idx in range(len(X)):
        if labels[point_idx] != 0:
            continue
        neighbors = get_neighbors_kdtree(tree, X[point_idx], eps)
        if len(neighbors) < min_pts:
            labels[point_idx] = -1  # Noise
        else:
            cluster_id += 1
            labels = expand_cluster(X, labels, point_idx, neighbors, cluster_id, eps, min_pts)
    
    return labels

# Compare performance
import time

start_time = time.time()
labels_original = dbscan(X, eps, min_pts)
original_time = time.time() - start_time

start_time = time.time()
labels_optimized = dbscan_optimized(X, eps, min_pts)
optimized_time = time.time() - start_time

print(f"Original DBSCAN time: {original_time:.4f} seconds")
print(f"Optimized DBSCAN time: {optimized_time:.4f} seconds")
print(f"Speed improvement: {original_time / optimized_time:.2f}x")

Handling High-Dimensional Data

DBSCAN can struggle with high-dimensional data due to the curse of dimensionality. Let's explore a technique to address this: dimensionality reduction using PCA.

from sklearn.decomposition import PCA
from sklearn.datasets import make_blobs

# Generate high-dimensional data
X_high_dim, _ = make_blobs(n_samples=300, n_features=20, centers=3, random_state=42)

# Apply PCA
pca = PCA(n_components=2)
X_reduced = pca.fit_transform(X_high_dim)

# Run DBSCAN on reduced data
eps_reduced = 2
min_pts_reduced = 5
labels_reduced = dbscan(X_reduced, eps_reduced, min_pts_reduced)

# Visualize results
plt.figure(figsize=(10, 7))
scatter = plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=labels_reduced, cmap='viridis')
plt.colorbar(scatter)
plt.title("DBSCAN on PCA-reduced High-Dimensional Data")
plt.xlabel("First Principal Component")
plt.ylabel("Second Principal Component")
plt.show()

Real-Life Example: Image Segmentation

DBSCAN can be applied to image segmentation tasks. Let's use it to segment an image based on pixel intensities and positions.

from skimage import io
from skimage.color import rgb2gray

# Load and preprocess image
image = io.imread('https://raw.githubusercontent.com/scikit-image/scikit-image/master/skimage/data/astronaut.png')
gray_image = rgb2gray(image)

# Create feature matrix
h, w = gray_image.shape
X_image = np.column_stack([np.repeat(np.arange(h), w),
                           np.tile(np.arange(w), h),
                           gray_image.ravel()])

# Run DBSCAN
eps_image = 5
min_pts_image = 50
labels_image = dbscan(X_image, eps_image, min_pts_image)

# Visualize results
segmented_image = labels_image.reshape(gray_image.shape)

plt.figure(figsize=(12, 6))
plt.subplot(121)
plt.imshow(gray_image, cmap='gray')
plt.title("Original Grayscale Image")
plt.subplot(122)
plt.imshow(segmented_image, cmap='viridis')
plt.title("DBSCAN Segmented Image")
plt.show()

Challenges and Limitations

While DBSCAN is powerful, it has limitations. It struggles with varying densities and high-dimensional data. The choice of eps and min_pts can be challenging. For varying densities, consider OPTICS or HDBSCAN algorithms. For high dimensions, use dimensionality reduction techniques or adapt distance metrics.

# Varying density example
X_varied = np.vstack([
    np.random.randn(100, 2) * 0.3,
    np.random.randn(50, 2) * 0.1 + [1, 1]
])

plt.figure(figsize=(10, 5))
plt.subplot(121)
plt.scatter(X_varied[:, 0], X_varied[:, 1])
plt.title("Varying Density Data")

labels_varied = dbscan(X_varied, eps=0.1, min_pts=5)
plt.subplot(122)
plt.scatter(X_varied[:, 0], X_varied[:, 1], c=labels_varied, cmap='viridis')
plt.title("DBSCAN Result")
plt.show()

Additional Resources

For those interested in delving deeper into DBSCAN and related clustering algorithms, consider exploring these valuable resources:

  1. Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD (Vol. 96, No. 34, pp. 226-231). Available at: https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf
  2. Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), 1-21. ArXiv: https://arxiv.org/abs/1706.06778
  3. Campello, R. J., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. In Pacific-Asia conference on knowledge discovery and data mining (pp. 160-172). Springer, Berlin, Heidelberg. ArXiv: https://arxiv.org/abs/1507.07021

These papers provide in-depth explanations of DBSCAN's theoretical foundations, practical applications, and extensions to handle various data challenges. They offer valuable insights for both understanding and implementing density-based clustering algorithms.

More in Classification and clustering

  1. Classification Concepts and Decision Trees10 min

    Classification is a fundamental task in machine learning where we predict the category of an input based on its features. It's widely used in various fields...

  2. Building a Naive Bayes Classifier from Scratch in Python7 min

    Naive Bayes is a probabilistic machine learning algorithm based on Bayes' theorem. It's widely used for classification tasks, particularly in text...

  3. Classification Metrics for Machine Learning Models4 min

    Machine learning classification models require robust evaluation metrics to assess their performance accurately and ensure reliable predictions. These...

  4. Advantages of Support Vector Machines for Robust Classification10 min

    Support Vector Machines (SVM) establish optimal decision boundaries by maximizing the margin between classes, creating a robust separator that enhances...

  5. Classifying Complex Data for Machine Learning in Python9 min

    Machine learning classification involves assigning categories to input data. Complex data often requires sophisticated techniques to extract meaningful...

  6. Advantages of Random Forest Algorithm in Python12 min

    Random Forest is a powerful machine learning algorithm that leverages the strength of multiple decision trees to make predictions. It combines the output of...