DBSVEC: Density-Based Clustering Using Support Vector Expansion

By Zhen Wang, Rui Zhang, Jianzhong Qi, Bo Yuan. 2019

16 citations recorded by the source corpus.

DBSCAN is a popular clustering algorithm that can discover clusters of arbitrary shapes with broad applications. However, DBSCAN is computationally expensive, as it performs range queries for all the points to determine their neighbors and grow the clusters. To address this problem, we propose a novel approximate density-based clustering algorithm named DBSVEC. DBSVEC introduces support vectors into density-based clustering, which allows performing range queries only on a small subset of points called the core support vectors. This technique significantly improves the efficiency while retaining high-quality cluster results. We evaluate the performance of DBSVEC via extensive experiments on real and synthetic datasets. The results show that DBSVEC is up to three orders of magnitude faster than DBSCAN. Compared with the state-of-the-art approximate density-based clustering methods, DBSVEC is up to two orders of magnitude faster, and the clustering results of DBSVEC are more similar to those of DBSCAN.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Dacheng Tao
2. Liu Liu
3. Zhen Wang
4. Yiqun Duan
5. Mingming Gong
6. Junjie Zhu
7. Bingjun Luo
8. Xibin Zhao

In Computer Vision and Pattern Recognition

1. Dacheng Tao
2. Yue Gao
3. Liu Liu
4. Mingming Gong
5. Zhen Wang
6. Junjie Zhu
7. Bingjun Luo
8. Xibin Zhao

In Signal Processing

1. Dacheng Tao
2. Yiqun Duan
3. Liu Liu
4. Shihui Ying
5. Mingming Gong
6. Yue Gao
7. Zhen Wang

Citations in the corpus

• Continual Learning through Retrieval and Imagination (2022, methodology): “Here, we employ a pair-based metric learning loss, Multi-Similarity (MS) loss (Wang et al. 2019a), as our loss function ℓ : where S i,k denotes the similarity of a pair { x i , x k } ; P i and N i are the positive and negative sets for the anchor x i ; N b is the number of training samples in a…”
• IExpressNet: Facial Expression Recognition with Incremental Classes (2020, background): “With the popularization of mobile devices and social networks [79], more and more people prefer to record their daily activities [66], share their feelings, and express their opinions through images and videos, which generates a massive quantity of multimedia data [21, 39, 72].”
• A Relational Intervention Approach for Unsupervised Dynamics Generalization in Model-Based Reinforcement Learning (2022, methodology): “During the training procedure, the trajectory segments are randomly sampled from the same trajectory to break the temporal correlations of the training data, which was also adopted by (Seo et al., 2020; Wang et al., 2020b; 2019).”