ISSN : 1796-203X
Volume : 3    Issue : 2    Date : February 2008

DDSC : A Density Differentiated Spatial Clustering Technique
B. Borah and D.K. Bhattacharyya
Page(s): 72-79
Full Text:
PDF (612 KB)

Finding clusters with widely differing sizes, shapes and densities in presence of noise and outliers
is a challenging job. The DBSCAN is a versatile clustering algorithm that can find clusters with
differing sizes and shapes in databases containing noise and outliers. But it cannot find clusters
based on difference in densities. We extend the DBSCAN algorithm so that it can also detect
clusters that differ in densities. Local densities within a cluster are reasonably homogeneous.
Adjacent regions are separated into different clusters if there is significant change in densities.
Thus the algorithm attempts to find density based natural clusters that may not be separated by any
sparse region. Computational complexity of the algorithm is O(n log n).

Index Terms
Variable density, natural clustering, spatial dataset, noises.