Abstract
OUTCLUST is a density-based clustering algorithm designed to handle datasets with varying densities and complex shapes. By identifying "exceptions"—points that significantly deviate from their local neighborhood density—the algorithm effectively partitions data into homogeneous clusters while remaining robust to noise and high-dimensional challenges.
Introduction
Traditional clustering algorithms often struggle with the complexities of real-world data. Partitioning methods like k-means are efficient but limited to finding spherical clusters and are sensitive to outliers. Conversely, density-based methods like DBSCAN can identify arbitrary shapes but often rely on a global density threshold. This creates a "Goldilocks" problem: a threshold high enough to distinguish dense clusters from noise may overlook sparser, yet legitimate, clusters.
OUTCLUST addresses these challenges by introducing a normalized notion of local density, allowing it to simultaneously uncover clusters of varying shapes and densities, even in the presence of significant high-dimensional noise.
The OUTCLUST Algorithm
The core innovation of OUTCLUST is the principle of "clustering by exceptions." Instead of directly searching for dense regions, it identifies points that are "least like" their neighbors.
The method follows a structured process:
- Local Density Estimation: For every point $p_i$, the algorithm calculates a distance-based value ($\delta_{p_i}$) using its $k$-nearest neighbors. This value is inversely related to density.
- Normalization ($\sigma$): A normalized density value $\sigma_{p_i}$ is computed by comparing a point's density to those of its neighbors. A value near 1 indicates uniform local density, while a high $\sigma$ identifies an outlier.
- Outlier Removal: Based on a frequency threshold $f$, the top $fN$ "exceptions" (highest $\sigma$ values) are temporarily set aside.
- Cluster Building: The remaining "inlier" points are merged into clusters if they are connected through regions where the normalized density exceeds that of the removed outliers.
- Refinement: Small clusters (fewer than $k$ points) are removed, and the previously set-aside outliers are assigned to their nearest neighboring cluster.
Experimental Evaluation
The algorithm was evaluated using 2D synthetic benchmarks (e.g., Chameleon, CURE, BIRCH) and ten real-world datasets from the UCI Machine Learning Repository (e.g., Iris, Satellite Image, Wisconsin Breast Cancer).
Key Results
- Superior Accuracy: Using Normalized Mutual Information (NMI), OUTCLUST outperformed Shared Nearest Neighbor (SNN), k-means, and linkage-based methods on 8 out of 10 real-world datasets.
- Noise Tolerance: On synthetic datasets, the algorithm successfully separated clusters connected by dense "bridges" and surrounded by random noise, scenarios where other algorithms typically fail.
- Efficiency: The algorithm's complexity is $O(kN \log N)$ for data with low intrinsic dimensionality, making it feasible for large datasets.
Discussion and Insights
OUTCLUST's effectiveness stems from its use of relative vs. global density. By normalizing density locally, it can distinguish sparse clusters adjacent to dense ones. Furthermore, it treats outliers as boundary markers, using them to define the limits of homogeneous groups rather than just ignoring them as noise.
Experimental "heat maps" of the parameter space ($k$ and $f$) demonstrate significant stability, suggesting that OUTCLUST is less sensitive to hyperparameter tuning than many competing tools. It also handles "bridges" between clusters effectively by identifying them as exceptions due to their lower local neighborhood density.
Conclusion
OUTCLUST offers a robust framework for clustering complex, high-dimensional data. While it demonstrates high accuracy and noise tolerance, future work could address the computational bottleneck of nearest-neighbor searches in very high dimensions and explore automated methods for parameter selection.
Summary updated