DBSCAN

In these videos, we see the DBSCAN unsupervised clustering algorithm in action.

We observe how different clusters emerge point by point, without a predefined number of clusters. Additionally, outliers (points that do not belong to any cluster) are marked in a separate color, demonstrating anomaly detection.

In the first case, the code randomly generates 300 points on a 100x100 two-dimensional plane (with a unit distance of 1) and clusters them using an Epsilon parameter (neighborhood radius) of 7.3 units and a minimum of 4 neighbors.

In the second case, the code randomly generates a sad face on a 500x500 two-dimensional plane (with a unit distance of 1) and clusters the points using an Epsilon parameter of 65 units and a minimum of 3 neighbors.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based clustering algorithm that groups data into clusters without requiring the number of clusters to be predefined. This algorithm is particularly effective in handling noise (outliers) and data that follows density patterns.

How DBSCAN Works
The DBSCAN algorithm uses the following key concepts:

Data Point Density: DBSCAN examines the neighborhood (adjacent data points) and uses two fundamental parameters:

Eps (ε): The radius within which a data point is considered a neighbor of another data point.
MinPts: The minimum number of points within the ε-radius for a point to qualify as a core point.

The three types of data points:

Core Points: Points with at least MinPts neighbors within the ε-radius.
Border Points: Points within the ε-radius of a core point but with fewer than MinPts neighbors.
Noise Points (Outliers): Points outside the ε-radius of all other points, not belonging to any cluster.

Clustering Process:

DBSCAN selects an arbitrary data point, and if it has more than MinPts neighbors within the epsilon radius, it starts forming a cluster.
Clusters are expanded by adding all neighboring points.
Data points that do not belong to any cluster are considered noise points (outliers).

Applications
Density-Based Clustering: DBSCAN is highly effective for irregularly shaped clusters (not just spherical) and data containing noise or outliers. No need to predetermine the number of clusters.

Key Application Areas:

Geographic Data Analysis: DBSCAN can be used for clustering spatial data, such as identifying cities, restaurants, or stores based on their location.

Anomaly Detection: Useful for identifying noise points or outliers in datasets, which can represent unusual events or erroneous data.

Image Processing: Applicable for grouping objects in images or identifying specific visual patterns.

Network Data Mining: In internet or transportation networks, DBSCAN is valuable for analyzing the density of routes, nodes, and the connections between them. For example, it can be used to identify densely connected pathways, critical intersections, or areas with significant activity within the network.

Advantages:

Finds clusters without predefined cluster numbers. Effectively handles noise and outliers. Detects clusters of various shapes (not limited to spherical ones).

Disadvantages:

Sensitive to parameter selection, especially Eps and MinPts.
Can be slow with large, dense datasets.

Example

Suppose we are working with traffic data for a city and want to identify areas with high traffic density. Using DBSCAN, we can cluster the traffic data to pinpoint crowded, high-traffic areas (such as central intersections), while treating less-used roads or noisy data (e.g., faulty GPS coordinates) as outliers.

Overall, DBSCAN is a powerful tool for density-based clustering, especially in cases where the number of clusters is unknown and the data contains noise points or outliers.

import numpy as np

# Távolság számítása két pont között (euklideszi távolság)

def euclidean_distance(point1, point2):

return np.sqrt(np.sum((point1 - point2) ** 2))

# Szomszédok keresése (Eps távolságon belüli pontok)

def region_query(data, point_idx, eps):

neighbors = []

for i in range(len(data)):

if euclidean_distance(data[point_idx], data[i]) <= eps:

neighbors.append(i)

return neighbors

# Klaszter kibővítése

def expand_cluster(data, labels, point_idx, neighbors, cluster_id, eps, min_pts, visited):

labels[point_idx] = cluster_id

i = 0

while i < len(neighbors): neighbor_idx = neighbors[i] if not visited[neighbor_idx]: visited[neighbor_idx] = True new_neighbors = region_query(data, neighbor_idx, eps) if len(new_neighbors) >= min_pts:

neighbors.extend(new_neighbors)

if labels[neighbor_idx] == -1:

labels[neighbor_idx] = cluster_id

i += 1

return labels

# DBSCAN algoritmus

def dbscan(data, eps, min_pts):

labels = np.full(len(data), -1)

visited = np.full(len(data), False)

cluster_id = 0

for i in range(len(data)):

if visited[i]:

continue

visited[i] = True

neighbors = region_query(data, i, eps)

if len(neighbors) < min_pts:

labels[i] = -1 # Zajpont

else:

cluster_id += 1

labels = expand_cluster(data, labels, i, neighbors, cluster_id, eps, min_pts, visited)

return labels

# Pontok generálása

np.random.seed(42)

data = np.random.rand(300, 2) * 100 # 300 pont két dimenzióban, 0 és 100 között

# Paraméterek beállítása

eps = 7.3 # Sugár

min_pts = 4 # Minimális szomszédok száma

# DBSCAN alkalmazása az adatkészletre

labels = dbscan(data, eps, min_pts)