Block-Diagonal Guided DBSCAN Clustering
Cluster analysis plays a crucial role in database mining, and one of the most widely used algorithms in this field is DBSCAN. However, DBSCAN has several limitations, such as difficulty in handling high-dimensional large-scale data, sensitivity to input parameters, and lack of robustness in producing clustering results. This paper introduces an improved version of DBSCAN that leverages the block-diagonal property of the similarity graph to guide the clustering procedure of DBSCAN. The key idea is to construct a graph that measures the similarity between high-dimensional large-scale data points and has the potential to be transformed into a block-diagonal form through an unknown permutation, followed by a cluster-ordering procedure to generate the desired permutation. The clustering structure can be easily determined by identifying the diagonal blocks in the permuted graph. We propose a gradient descent-based method to solve the proposed problem. Additionally, we develop a DBSCAN-based points traversal algorithm that identifies clusters with high densities in the graph and generates an augmented ordering of clusters. The block-diagonal structure of the graph is then achieved through permutation based on the traversal order, providing a flexible foundation for both automatic and interactive cluster analysis. We introduce a split-and-refine algorithm to automatically search for all diagonal blocks in the permuted graph with theoretically optimal guarantees under specific cases. We extensively evaluate our proposed approach on twelve challenging real-world benchmark clustering datasets and demonstrate its superior performance compared to the state-of-the-art clustering method on every dataset.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Subspace Clustering by Block Diagonal Representation
This paper studies the subspace clustering problem. Given some data points approximately drawn from a union of subspaces, the goal is to group these data points into their underlying subspaces. Many subspace clustering m…
ClusteringConvex Subspace Clustering by Adaptive Block Diagonal Representation
Subspace clustering is a class of extensively studied clustering methods where the spectral-type approaches are its important subclass. Its key first step is to desire learning a representation coefficient matrix with bl…
ClusteringAutomating DBSCAN via Deep Reinforcement Learning
DBSCAN is widely used in many scientific and engineering fields because of its simplicity and practicality. However, due to its high sensitivity parameters, the accuracy of the clustering result depends heavily on practi…
ClusteringComputational EfficiencyDeep Reinforcement Learningreinforcement-learning+3Convolutional Subspace Clustering Network with Block Diagonal Prior
Standard methods of subspace clustering are based on self-expressiveness in the original data space, which states that a data point in a subspace can be expressed as a linear combination of other points. However, the rea…
ClusteringRobust Subspace Segmentation with Block-diagonal Prior
The subspace segmentation problem is addressed in this paper by effectively constructing an exactly block-diagonal sample affinity matrix. The block-diagonal structure is heavily desired for accurate sample clustering bu…
ClusteringFace Clusteringgraph constructionMotion Segmentation+1