A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method

doi:10.1016/j.patcog.2016.03.008

2016-10-01

219

PRE

A. Rama Mohan Reddy

DOI：10.1016/j.patcog.2016.03.008

原文链接

原文求助

摘要

En 中文

Density based clustering methods are proposed for clustering spatial databases with noise. Density Based Spatial Clustering of Applications with Noise (DBSCAN) can discover clusters of arbitrary shape and also handles outliers effectively. DBSCAN obtains clusters by finding the number of points within the specified distance from a given point. It involves computing distances from given point to all other points in the dataset. The conventional index based methods construct a hierarchical structure over the dataset to speed-up the neighbor search operations. The hierarchical index-structures fail to scale for datasets of dimensionality above 20. In this paper, we propose a novel graph-based index structure method Groups that accelerates the neighbor search operations and also scalable for high dimensional datasets. Experimental results show that the proposed method improves the speed of DBSCAN by a factor of about 1.5-2.2 on benchmark datasets. The performance of DBSCAN degrades considerably with noise due to unnecessary distance computations introduced by noise points while the proposed method is robust to noise by pruning out noise points early and eliminating the unnecessary distance computations. The cluster results produced by our method are exactly similar to that of DBSCAN but executed at a much faster pace. (C) 2016 Elsevier Ltd. All rights reserved.

Keyword:

Unsupervised learning

Density based clustering

DBSCAN

Neighborhood graph

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Pattern Recognition

IF:

7.6

论文数:

1.3W

被引数:

4.5W

机构

sri venkateswara university

学者数:

1.3K

论文数: 1.2K

被引数: 2

引用论文

Density, Surface Tension, and Viscosity of Liquid Pb–Sb Alloys

Journal of Chemical & Engineering Data

IF0

2018-04-18

PREAI

Tomasz Gancarz; Wladyslaw Gasior

IF0

PREAI

Bleaching, coral mortality and subsequent survivorship on a West Australian fringing reef

Coral Reefs

IF0

2012-10-21

PREAI

M. Depczynski; J. P. Gilmour; T. Ridgway; H. Barnes; A. J. Heyward; T. H. Holmes; J. A. Y. Moore; B. T. Radford; D. P. Thomson; P. Tinkler; S. K. Wilson

Object Depth Profile and Reflectivity Restoration From Sparse Single-Photon Data Acquired in Underwater Environments

IEEE Transactions on Computational Imaging

IF0

2017-09-01