Scalable Density-based Clustering with Random Projections
<|reference_start|>Scalable Density-based Clustering with Random Projections: We present sDBSCAN, a scalable density-based clustering algorithm in high dimensions with cosine distance. Utilizing the neighborhood-preserving property of random projections, sDBSCAN can quickly identify core points and their neighborhoods, the primary hurdle of density-based clustering. Theoretically, sDBSCAN outputs a clustering structure similar to DBSCAN under mild conditions with high probability. To further facilitate sDBSCAN, we present sOPTICS, a scalable OPTICS for interactive exploration of the intrinsic clustering structure. We also extend sDBSCAN and sOPTICS to L2, L1, $\chi^2$, and Jensen-Shannon distances via random kernel features. Empirically, sDBSCAN is significantly faster and provides higher accuracy than many other clustering algorithms on real-world million-point data sets. On these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-learn's counterparts demand several hours or cannot run due to memory constraints.<|reference_end|>
@article{xu2024scalable,
    title={Scalable Density-based Clustering with Random Projections},
    author={Haochuan Xu, Ninh Pham},
    journal={arXiv preprint arXiv:2402.15679},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.15679},
    primaryClass={cs.LG cs.CV}
}