Title: IMPROVED VDBSCAN WITH GLOBAL OPTIMUM K

Year of Publication: Jul - 2013
Page Numbers: 225-228
Authors: Wei Wang, Shuang Zhou, Bingfei Ren, Suoju He
Conference Name: The Third International Conference on Digital Information and Communication Technology and its Applications (DICTAP2013)
- Czech Republic

Abstract:


Density-based clustering methods are an important part of clustering techniques. VDBSCAN is a well-known density-based one. VDBSCAN is robust against noise and it can recognize arbitrary shapes of clusters. Besides, it works effectively when dealing with varied density datasets. The main drawback of VDBSCAN is that it still asks for a user-specified parameter K. An inappropriate choice of K can seriously degrade the accuracy of results. So we propose a totally parameter-free algorithm, OVDBSCAN, to automatically find the global optimum K, and it uses derivative to help select the global optimum K. The basic idea of OVDBSCAN is to regard k-dist as a dependent variable of K and define Δdk as the derivative of k-dist, then it chooses the largest K on condition that Δdk doesn’t exceed the threshold we set. For OVDBSCAN, the determination of K is based on the distances among objects within a dataset, thus the generated K reflects the property of this dataset. We carry out an experiment on a two dimensional dataset to exemplify how OVDBSCAN works, and the result demonstrates that OVDBSCAN can derive the optimum K.