10.3 Density-based Clustering

Density-based clustering groups data points in high-density areas, separating them from low-density regions. This approach, exemplified by DBSCAN, finds clusters of any shape without specifying the number beforehand, making it robust to outliers.

The method defines density by points within a radius, classifying them as core, border, or noise. It expands clusters by connecting density-reachable points, offering advantages over other clustering techniques like K-means for non-spherical clusters and large datasets.

Understanding Density-Based Clustering

Concept of density-based clustering

• Groups data points in areas of high density separates regions of low density (noise or outliers)
• Discovers clusters of arbitrary shape robust to outliers no need to specify number of clusters beforehand
• Density defined by number of points within specified radius (neighborhood)
• Core points have minimum number of neighbors within radius
• Border points within radius of core point but fewer neighbors
• Noise points neither core nor border

Application of DBSCAN algorithm

• Select arbitrary unvisited point retrieve epsilon neighborhood
• Form cluster if enough points within epsilon expand by adding density-reachable points
• Move to next unvisited point after cluster expansion
• Start with core point and expand until no more density-connected points found
• Points not assigned to any cluster considered noise/outliers
• Uses spatial indexing structures for efficiency (R-trees, k-d trees)
• Handles large datasets through optimized implementations (OPTICS, HDBSCAN)

Parameters for density-based clustering

• Epsilon (ε) defines neighborhood radius affects cluster size and number
• Minimum points sets dense region threshold influences noise tolerance
• k-distance graph estimates epsilon domain knowledge sets minimum points
• Evaluate cluster stability across parameter ranges
• Small ε creates many small clusters or noise points
• Large ε merges distinct clusters
• High minimum points increases noise decreases clusters
• Low minimum points allows noise to form clusters

Density-based vs other clustering approaches

• DBSCAN finds arbitrary shapes K-means produces spherical clusters
• DBSCAN doesn't need predefined cluster number K-means requires it
• DBSCAN single pass algorithm hierarchical clustering creates multiple levels
• DBSCAN better for large datasets hierarchical computationally intensive
• Discovers arbitrary shapes robust to outliers no cluster number specification
• Struggles with varying densities sensitive to parameters challenging in high dimensions
• DBSCAN time complexity $O(n \log n)$ with spatial indexing K-means $O(knT)$ ($k$ clusters $T$ iterations)
• DBSCAN memory efficient hierarchical clustering requires distance matrix storage