xbe.at

Data visualisation

Visual Demonstration of DBSCAN Clustering

6 min read, 15 sections

Contents
  1. Introduction to DBSCAN Clustering
  2. Core Concepts of DBSCAN
  3. Source Code for Core Concepts of DBSCAN
  4. DBSCAN Algorithm Implementation
  5. Source Code for DBSCAN Algorithm Implementation
  6. Visualizing DBSCAN Results
  7. Source Code for Visualizing DBSCAN Results
  8. Advantages of DBSCAN over KMeans
  9. Source Code for Comparing DBSCAN and KMeans
  10. Real-Life Example: Geographic Data Clustering
  11. Source Code for Geographic Data Clustering
  12. Real-Life Example: Image Segmentation
  13. Source Code for Image Segmentation with DBSCAN
  14. Limitations and Considerations
  15. Additional Resources

Introduction to DBSCAN Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a powerful clustering algorithm that groups data points based on density. Unlike traditional clustering methods, DBSCAN can identify clusters of arbitrary shapes and handle noise effectively. This presentation will explore the core concepts, implementation, and advantages of DBSCAN over other clustering algorithms.

import numpy as np
import matplotlib.pyplot as plt

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

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

Core Concepts of DBSCAN

DBSCAN relies on two main parameters: epsilon (ε) and minPts. Epsilon defines the maximum distance between two points to be considered neighbors, while minPts is the minimum number of points required to form a dense region. The algorithm classifies points into three categories: core points, border points, and noise points.

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

def get_neighbors(data, point_idx, epsilon):
    return [idx for idx, point in enumerate(data) if euclidean_distance(data[point_idx], point) <= epsilon]

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

Source Code for Core Concepts of DBSCAN

def classify_points(data, epsilon, minPts):
    classifications = ['Noise'] * len(data)
    for idx in range(len(data)):
        neighbors = get_neighbors(data, idx, epsilon)
        if len(neighbors) >= minPts:
            classifications[idx] = 'Core'
        elif len(neighbors) > 0:
            classifications[idx] = 'Border'
    return classifications

# Example usage
classifications = classify_points(X, epsilon, minPts)
print(f"Core points: {classifications.count('Core')}")
print(f"Border points: {classifications.count('Border')}")
print(f"Noise points: {classifications.count('Noise')}")

DBSCAN Algorithm Implementation

The DBSCAN algorithm starts by selecting an arbitrary unvisited point and finding all its neighbors within the epsilon distance. If the number of neighbors is at least minPts, a new cluster is formed. The algorithm then recursively expands the cluster by adding neighboring core points and their neighbors.

Source Code for DBSCAN Algorithm Implementation

def dbscan(data, epsilon, minPts):
    labels = [0] * len(data)  # 0 represents unvisited points
    cluster_id = 0
    
    for point_idx in range(len(data)):
        if labels[point_idx] != 0:
            continue
        
        neighbors = get_neighbors(data, point_idx, epsilon)
        
        if len(neighbors) < minPts:
            labels[point_idx] = -1  # Mark as noise
        else:
            cluster_id += 1
            expand_cluster(data, labels, point_idx, neighbors, cluster_id, epsilon, minPts)
    
    return labels

def expand_cluster(data, labels, point_idx, neighbors, cluster_id, epsilon, minPts):
    labels[point_idx] = cluster_id
    
    i = 0
    while i < len(neighbors):
        neighbor_idx = neighbors[i]
        
        if labels[neighbor_idx] == -1:
            labels[neighbor_idx] = cluster_id
        elif labels[neighbor_idx] == 0:
            labels[neighbor_idx] = cluster_id
            new_neighbors = get_neighbors(data, neighbor_idx, epsilon)
            
            if len(new_neighbors) >= minPts:
                neighbors.extend(new_neighbors)
        
        i += 1

# Example usage
epsilon = 0.5
minPts = 5
cluster_labels = dbscan(X, epsilon, minPts)

Visualizing DBSCAN Results

After applying DBSCAN to our sample data, we can visualize the results to better understand how the algorithm identifies clusters and handles noise points. This visualization helps demonstrate the algorithm's ability to detect clusters of arbitrary shapes.

Source Code for Visualizing DBSCAN Results

def plot_dbscan_results(data, labels):
    unique_labels = set(labels)
    colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
    
    for label, color in zip(unique_labels, colors):
        if label == -1:
            color = 'black'
        
        class_member_mask = (labels == label)
        xy = data[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()

# Example usage
plot_dbscan_results(X, cluster_labels)

Advantages of DBSCAN over KMeans

DBSCAN offers several advantages over traditional clustering algorithms like KMeans:

  1. It can identify clusters of arbitrary shapes, not just spherical ones.
  2. It automatically detects and handles noise points.
  3. The number of clusters doesn't need to be specified beforehand.
  4. It can handle clusters of varying densities.

These advantages make DBSCAN particularly useful for complex datasets with non-uniform cluster shapes and densities.

Source Code for Comparing DBSCAN and KMeans

from sklearn.cluster import KMeans

# KMeans clustering
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Plot KMeans results
plt.figure(figsize=(12, 5))
plt.subplot(121)
plot_dbscan_results(X, cluster_labels)
plt.title("DBSCAN Clustering")

plt.subplot(122)
plot_dbscan_results(X, kmeans_labels)
plt.title("KMeans Clustering")

plt.tight_layout()
plt.show()

Real-Life Example: Geographic Data Clustering

DBSCAN is particularly useful for clustering geographic data, such as identifying urban areas or points of interest. Consider a dataset of GPS coordinates representing various locations in a city. DBSCAN can effectively group these points into clusters representing distinct neighborhoods or areas of activity.

Source Code for Geographic Data Clustering

import numpy as np
import matplotlib.pyplot as plt

# Generate sample GPS coordinates
np.random.seed(42)
gps_data = np.random.randn(500, 2) * 0.1
gps_data[:100] += [0.5, 0.5]  # Downtown area
gps_data[100:200] += [-0.5, 0.5]  # Residential area
gps_data[200:300] += [0, -0.5]  # Industrial area

# Apply DBSCAN
epsilon = 0.05
minPts = 10
gps_labels = dbscan(gps_data, epsilon, minPts)

# Visualize results
plt.figure(figsize=(10, 8))
plot_dbscan_results(gps_data, gps_labels)
plt.title("DBSCAN Clustering of GPS Coordinates")
plt.xlabel("Longitude")
plt.ylabel("Latitude")
plt.show()

Real-Life Example: Image Segmentation

Another practical application of DBSCAN is in image segmentation. By treating pixel intensities and positions as features, DBSCAN can group similar pixels together, effectively segmenting an image into distinct regions. This technique is useful in various fields, including medical imaging and computer vision.

Source Code for Image Segmentation with DBSCAN

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image

# Load and preprocess the image
image = Image.open("sample_image.jpg").convert("L")  # Convert to grayscale
image_array = np.array(image)
height, width = image_array.shape

# Create feature matrix (x, y, intensity)
features = np.column_stack([np.repeat(np.arange(height), width),
                            np.tile(np.arange(width), height),
                            image_array.flatten()])

# Apply DBSCAN
epsilon = 10
minPts = 50
segment_labels = dbscan(features, epsilon, minPts)

# Reshape labels to image dimensions
segmented_image = segment_labels.reshape(height, width)

# Visualize results
plt.figure(figsize=(12, 6))
plt.subplot(121)
plt.imshow(image, cmap='gray')
plt.title("Original Image")

plt.subplot(122)
plt.imshow(segmented_image, cmap='nipy_spectral')
plt.title("DBSCAN Segmentation")

plt.tight_layout()
plt.show()

Limitations and Considerations

While DBSCAN is powerful, it has some limitations:

  1. Sensitivity to parameter selection (epsilon and minPts).
  2. Difficulty in handling clusters with varying densities.
  3. Computational complexity of O(n^2) in the worst case.

To address these issues, variations like OPTICS and HDBSCAN have been developed, offering improved performance and adaptability to different datasets.

Additional Resources

For more information on DBSCAN and related clustering algorithms, consider the following 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). ArXiv: 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.07212

More in Data visualisation

  1. Visual Guide to Active Learning in Machine Learning10 min

    Active learning is a machine learning approach that interactively queries a user or other information source to label new data points. This method is...

  2. Time Series Visualization in Python From Raw Data to Insights8 min

    Time series visualization is a powerful tool for understanding and analyzing data that changes over time. It allows us to identify patterns, trends, and...

  3. Visual Guide to Bagging and Boosting in Machine Learning10 min

    Bagging, short for Bootstrap Aggregating, is a fundamental ensemble technique that creates multiple training subsets through random sampling with...

  4. The Psychology of Effective Data Visualization8 min

    Data visualization leverages our innate pattern recognition abilities to convey information more effectively than raw numbers. This presentation explores key...

  5. Visualizing Borel Sets in Python7 min

    Borel sets are fundamental in measure theory and probability. They form a σ-algebra generated by open sets in a topological space. Let's explore their...

  6. Stem-Leaf Plots in Python A Visual Representation of Data9 min

    A stem-leaf plot is a statistical method for organizing and displaying numerical data. It provides a visual representation of the distribution of data...