Skip to main content

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular density-based clustering algorithm that groups data points based on their density in feature space. It’s beneficial for datasets with clusters of varying shapes, sizes, and densities, and can identify noise or outliers.

Step 1: Initialize Parameters

Define two important parameters:

  • Epsilon (ε): The maximum distance between two points for them to be considered neighbors.
  • Minimum Points (minPts): The minimum number of points required in an ε-radius neighborhood for a point to be considered a core point.

Step 2: Label Each Point as Core, Border, or Noise

For each data point PP in the dataset:

  1. Find all points within the ε radius of PP (the ε-neighborhood of PP).
  2. Core Point: If PP has at least minPts points within its ε-neighborhood, it’s marked as a core point.
  3. Border Point: If PP has fewer than minPts points in its ε-neighborhood but is within the ε-neighborhood of a core point, it’s labeled a border point.
  4. Noise Point: If PP doesn’t satisfy either condition (not enough neighbors, not within a core point's neighborhood), it’s marked as noise.

Step 3: Form Clusters from Core Points

  1. Start with an unvisited core point: A new cluster begins if the point is a core point.
  2. Expand the cluster: Add all reachable points within ε of the core point to the cluster. Mark each added point as "visited."
  3. For each new point added to the cluster:
    • If it’s also a core point, repeat the expansion process by adding all its reachable neighbors within ε to the cluster.
    • If it’s a border point, add it to the cluster but don’t expand further from it (since it doesn’t have enough density to expand).

Step 4: Mark Noise Points

Any points not assigned to any cluster during the expansion process are labeled as noise or outliers.

Step 5: Repeat for All Unvisited Points

Continue with the remaining unvisited points:

  • If the next unvisited point is a core point, start a new cluster and expand it.
  • If it's a border point or noise, mark it accordingly without forming a new cluster.

Step 6: Output the Clusters

When all points are visited, DBSCAN completes, resulting in clusters of core and border points, and isolated points marked as noise.

Implementation

# Import necessary libraries
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

# Generate synthetic data (e.g., with two moon-shaped clusters)
X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

# Define DBSCAN parameters
epsilon = 0.2  # Radius for neighborhood
min_samples = 5  # Minimum number of points for a core point

# Apply DBSCAN clustering
dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
labels = dbscan.fit_predict(X)

# Plotting the clusters and noise
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))

# Plot each cluster with a different color, mark noise as black
for label, color in zip(unique_labels, colors):
    if label == -1:  # Noise points have a label of -1
        color = "black"  # Mark noise as black
    class_members = (labels == label)
    plt.plot(X[class_members, 0], X[class_members, 1], "o", markerfacecolor=color, markeredgecolor="k", markersize=6)

plt.title("DBSCAN Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()




Comments

Post a Comment

Popular posts from this blog

ML Lab Questions

1. Using matplotlib and seaborn to perform data visualization on the standard dataset a. Perform the preprocessing b. Print the no of rows and columns c. Plot box plot d. Heat map e. Scatter plot f. Bubble chart g. Area chart 2. Build a Linear Regression model using Gradient Descent methods in Python for a wine data set 3. Build a Linear Regression model using an ordinary least-squared model in Python for a wine data set  4. Implement quadratic Regression for the wine dataset 5. Implement Logistic Regression for the wine data set 6. Implement classification using SVM for Iris Dataset 7. Implement Decision-tree learning for the Tip Dataset 8. Implement Bagging using Random Forests  9.  Implement K-means Clustering    10.  Implement DBSCAN clustering  11.  Implement the Gaussian Mixture Model  12. Solve the curse of Dimensionality by implementing the PCA algorithm on a high-dimensional 13. Comparison of Classification algorithms  14. Compa...
Post a Comment
Read more

Gaussian Mixture Model

A Gaussian Mixture Model (GMM) is a probabilistic model used for clustering and density estimation. It assumes that data is generated from a mixture of several Gaussian distributions, each representing a cluster within the dataset. Unlike K-means, which assigns data points to the nearest cluster centroid deterministically, GMM considers each data point as belonging to each cluster with a certain probability, allowing for soft clustering. GMM is ideal when: Clusters have elliptical shapes or different spreads : GMM captures varying shapes and densities, unlike K-means, which assumes clusters are spherical. Soft clustering is preferred : If you want to know the probability of a data point belonging to each cluster (not a hard assignment). Data has overlapping clusters : GMM allows a point to belong partially to multiple clusters, which is helpful when clusters have significant overlap. Applications of GMM Image Segmentation : Used to segment images into regions, where each region can be...
Post a Comment
Read more