IMPROVED VDBSCAN WITH GLOBAL OPTIMUM K
Wei Wang, Bingfei Ren Shuang Zhou · Digital Information and Communication Technology and Its Applications · 2013
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.