A spatial clustering method adaptive to local density change
G Li, Min Deng, Q Liu, Tao Cheng · UCL Discovery (University College London) · 2009
Most spatial clustering methods utilize fixed thresholds in the process of clustering which assume homogeneous(or even) distribution of the spatial points rather than inhomogeneous(or uneven) scattering.However,in many practical applications,spatial points usually distribute unevenly(in different density),which makes the fixed threshold methods inappropriate and the clustered results unreasonable.Thus,an Adaptive Density-change Based Spatial Cluster algorithm,ADBSC for short,is developed in this paper.To reduce the complexity of computation,a new measurement of spatial local density,named as maximum distance in k-spatial Nearest Neighborhood(k-NN for short),is proposed.And then,the concept of distance variation proportion is defined to measure the change of spatial local density.Moreover,a given threshold for the distance variation proportion is used to determine whether the maximum distances of all the adjacent points in k-NN are equal,that is to say,whether or not their spatial local density are equal.Furthermore,all the adjacent points whose local densities are equal compose a spatial cluster,so that the spatial clusters are implemented.In the meantime,the ADBSC algorithm is described in detail.Finally,a simulation test and a practical one are employed to illustrate the validity and the efficiency of the proposed algorithm(i.e.ADBSC).It is shown that on the one hand the ADBSC algorithm is capable to discover arbitrary shape clusters and is robust for noises,on the other hand that the ADBSC algorithm has more practicality than DBSCAN algorithm by a detailed comparison between them.