Semi-supervised DBSCAN
Semi-supervised Density-Based Spatial Clustering of Applications with Noise · Also known as: Constrained DBSCAN, SS-DBSCAN, DBSCAN with must-link/cannot-link constraints, seeded DBSCAN
Semi-supervised DBSCAN extends the canonical density-based clustering algorithm (Ester et al., 1996) by incorporating a small set of pairwise or label constraints — must-link pairs that must share a cluster, cannot-link pairs that must be separated, or a handful of known labels — to guide cluster formation while retaining DBSCAN's ability to discover arbitrary-shaped clusters and flag noise points.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use semi-supervised DBSCAN when you have predominantly unlabeled data with complex, non-convex cluster shapes, varying cluster densities, or significant noise, and you can supply even a small number of pairwise or label constraints — perhaps 1-5% of data pairs annotated by a domain expert. It is particularly valuable in spatial analysis, anomaly-aware clustering, and scientific discovery tasks where cluster shape is irregular and ground-truth structure is known only partially. Avoid it when constraints are unavailable (use plain DBSCAN instead), when clusters are roughly spherical and constraints are plentiful (constrained k-means is simpler), when the dataset is very high-dimensional (density estimates degrade in many dimensions), or when constraints conflict strongly with the data's density structure.
Strengths & limitations
- Discovers arbitrary-shaped and variable-density clusters that centroid-based methods like k-means miss.
- Does not require specifying the number of clusters in advance; k emerges from the data and constraints.
- Naturally handles noise and outliers by classifying low-density points as noise rather than forcing them into a cluster.
- Even a small constraint set (as few as 10-50 pairs) can substantially align the clustering with domain knowledge.
- Constraints can be gathered cheaply compared with fully labeling a dataset.
- Performance is sensitive to the choice of epsilon and MinPts, and semi-supervised guidance does not eliminate the need to tune these parameters.
- Conflicting constraints (must-link pairs in regions of very different density) can produce infeasible or degenerate solutions.
- Scalability is limited: neighborhood queries are quadratic unless accelerated with spatial indexing, making very large datasets expensive.
- Degrades in high-dimensional spaces where Euclidean distance becomes uninformative (the curse of dimensionality).
Frequently asked
How many constraints do I need?
Even a very small constraint set — as few as 10 to 50 pairs, or 1-5% of all possible pairs — typically yields meaningful improvement over unconstrained DBSCAN. The gain usually plateaus well before full supervision is reached.
What if my constraints conflict with the density structure?
Conflicting constraints can produce infeasible merges or force unnatural clusters. Check constraints for consistency before running, and consider relaxing hard constraints to soft (penalty-weighted) constraints if conflicts are frequent.
How do I choose epsilon and MinPts in the semi-supervised version?
Use the same heuristic as plain DBSCAN: plot k-NN distances (k = MinPts - 1) and look for an elbow. Constraints reduce sensitivity somewhat but do not replace parameter tuning.
When should I prefer constrained k-means over semi-supervised DBSCAN?
If clusters are roughly spherical, roughly equal in size, and you have many constraints, constrained k-means is simpler and faster. Choose semi-supervised DBSCAN when cluster shapes are irregular, densities vary, or noise is expected.
Can I use labeled points instead of pairwise constraints?
Yes. Labeled seed points can be converted into must-link constraints (all points of the same label must link) and cannot-link constraints (points of different labels must not link), then fed into the standard constrained DBSCAN framework.
Sources
- Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), pp. 226–231. AAAI Press. link ↗
- Zhu, X., & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers. ISBN: 978-1-59829-548-7
How to cite this page
ScholarGate. (2026, June 3). Semi-supervised Density-Based Spatial Clustering of Applications with Noise. ScholarGate. https://scholargate.app/en/machine-learning/semi-supervised-dbscan
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- HDBSCANMachine learning↔ compare
- K-meansMachine learning↔ compare
- Semi-supervised Gaussian Mixture ModelMachine learning↔ compare
- Semi-supervised K-meansMachine learning↔ compare