Automated clustering of multi-density spatial data is developed. The algorithm KDDClus serves as an enhancement to the wellknown DBSCAN. Averaging the distances of a pattern to all k of its nearest neighbours allows a smoothing out of noise while automatically detecting the \knees" from the k-distance plot. The use of the KD-tree data structure enables e±cient computation of the k-nearest neighbours (k-NN) of a pattern point, particularly for large data. Experimental results on synthetic data, involving nested multiple densities of di®erent shapes, demonstrates the superiority of KDDClus.
Often we come across spatial data consisting of a mixture of pattern
distributions involving di®erent densities, which may or may not be nested within each
other, in the presence of background noise. Clusters of di®erent densities can,
therefore, be modeled as belonging to point processes having di®erent
intensities. Clustering of such data is a challenging problem in data mining [
The density-based approach addresses this issue, while detecting clusters of
di®ering densities having arbitrary shape and size. It is non-parametric, and
requires no prior information regarding the number of clusters or their underlying
density. The algorithms detect the di®erence in densities among regions of
contiguous patterns in a spatial database, and accordingly assign them to di®erent
clusters. Noise and outliers are treated as low-density regions, and are removed
in terms of certain density criteria. The earliest research in this direction was
reported in Refs. [
Typically these algorithms require user-speci¯cation of certain parameters, related to density-level thresholds, to be provided as input. Often this becomes all the more di±cult when clusters in di®erent regions of the feature space have considerably di®erent densities or clusters with di®erent density levels are nested. In such cases the partitioning might not be proper with one single density threshold.
In this article we describe a new and simple algorithm KDDClus which
clusters multiple pattern distributions of di®erent densities in the presence of noise. It
is able to distinguish between di®erent density regions, which may or may not be
nested and are generally of non-convex shape. The algorithm automatically
estimates a number of thresholds to optimally identify the di®erent density regions,
without any prior knowledge about the data. While conventional density-based
clustering algorithms like DBSCAN typically resort to visual determination of a
single threshold to distinguish between two density regions, algorithm KDDClus
may be considered as an enhancement to it. The space-partitioning KD-tree data
structure [
Clustering patterns involving di®erent densities and noise, coexisting in the same spatial dataset, requires the determination of a number of thresholds. Automatic estimation of such parameters, particularly in varying densities of multiple point processes, is a di±cult task.
Algorithm DBSCAN requires proper estimation of two global parameters ² and M inP ts. This is highly data-dependent, and can be overestimated or underestimated by the visual and/or interactive procedure used. It may automatically lead to misplacement of patterns and even misidenti¯cation of clusters. Moreover, the algorithm does not consider the handling of a simultaneous presence of di®erent densities, originating from di®erent point processes in the data. Note that no single set of ² and M inP ts can properly cluster such a dataset. The complexity of searching the neighborhood is large in high-dimensions, thereby leading to the di±culty in determining a proper distance estimate.
We present here a new and simple way to automatically identify the number of point processes (or clusters of di®erent densities) including noise. The algorithm utilizes the KD-tree data structure for e±cient processing in high dimensions. It can simultaneously estimate the di®erent density parameters without any prior knowledge about the data. It is also not expensive.
We compute the average of the distances of a pattern to all k of its
nearest neighbors. This is unlike DBSCAN, where only the kth nearest neighbor
is considered during the distance computation. The use of the KD-tree data
structure [
A knee corresponds to a threshold where a sharp change of gradient occurs along the k-distance curve. This represents a change in density distribution amongst patterns. Any value less than this density-threshold ² estimate can e±ciently cluster patterns whose average k-NN distances is lower than that, implying patterns belonging to a certain density. Analogously all knees in the smoothed graph can collectively estimate a set of ²'s for identifying all the clusters having di®erent density distributions. The knee regions are detected in KDDClus by clustering the sorted k-NN distances. We determine the optimal number c0 of such segments, by using c-means while optimizing a clustering validity index.
Starting from the lowest value in the sorted k-NN distance graph, we sequentially execute DBSCAN for each of the c0 estimated ²'s considered in ascending order. The ¯rst estimate obviously corresponds to the most dense cluster. Tagging the patterns in the already detected clusters as \visited", we proceed towards larger values of k-distance while allowing DBSCAN to work on the stillunvisited patterns only. In this manner we are able to e®ectively determine all clusters in a multi-density framework, in a decreasing order of density, with noise being modelled as the sparsest region. 3
We have implemented the proposed KDDClus algorithm on a synthetic pattern set. There exist ¯ve clusters with three di®erent densities for dataset Decode in Fig. 1(a). The semi-circular region on the top-left, inner quadrilateral, and circular region on bottom-right of the ¯gure constitute the most dense clusters. The outer quadrilateral and triangular region form the medium-density clusters. The background is least dense and consists of noise.
We ¯nd from part (d) of the ¯gure that DBSCAN, with the lower threshold of ² = 0.3038, could correctly identify only (i) the smaller quadrilateral inscribed within the larger one, (ii) the circle, and (iii) the semi-circular region. These are indicated by di®erent shades of gray in the ¯gure. Using DBSCAN with the higher ²-value of 0.4226 resulted in the output map in part (e) of the ¯gure. In this case it is noticed that the smaller dense quadrilateral along with some surrounding points from the outer medium-density quadrilateral get merged into one cluster.
This adverse e®ect is eliminated with algorithm KDDClus, as observed from part (c) of the ¯gure. After correctly detecting the smaller quadrilateral, the circle and the semi-circular region with ² = 0.3038, the algorithm marks the 4 constituent patterns from the dataset as visited. In the next step DBSCAN needs to work only on the unvisited patterns with ² = 0.4226. Now it is able to correctly distinguish the larger quadrilateral and the triangle as the second lower-density level, within the background noise.
The algorithm KDDClus is an enhancement to DBSCAN, in terms of automatically estimating the various density-based parameters for optimal clustering. Unlike DBSCAN, where only the kth nearest neighbour is considered during the distance computation, here we calculate the average of the distances of a pattern to all k of its nearest neighbours. Such averaging allows a smoothing of the curve for subsequent easier automated detection of the \knees" amongst the background noise. The use of the KD-tree data structure enables e±cient computation of the k-nearest neighbours (k-NN) of a pattern point, particularly for large data. Comparative study has been made on three sets of synthetic data to establish the superiority of the proposed algorithm.