DBSCAN Algorithm And Its Application In Urban Gridding Management

Urban Gridding Management is a new pattern of urban management. Known form the old pattern, it is positive. With the new pattern, a supporting IT system has been developed which called Urban Gridding Management Information System. After several years operation, the system has accumulated mass data. Among these data, there are a great many spatial data. We can find out high-incidence areas of problems in urban management by using spatial clustering.In the paper, we design and realize a spatial clustering tool based on ArcGIS according to the data features of Urban Gridding Management Information System and the purpose of spatial clustering. The core algorithm of the tool is DBSCAN algorithm which is density-based. We considered tow facts associated with the realization of the algorithm: (1) Memory Overhead: DBSCAN algorithm will calculate the distances of one spatial point with the rest ones in data set. So we focused on the differences between upper triangular matrix and n-order matrix when storing distances between spatial points. We find out that using upper triangular matrix is overall superior than using n-order matrix after testing, so we ues upper triangular matrix to store distances of points. (2) Quick Sort: When proceeding spatial clustering with different MinPts and Eps, sort should be done on the distances of one spatial point with the rest ones in data set. This can save time for follow-up judgement. In the paper, we discussed which sort algorithm shouid be adopted and we select a quick sort algorithm based on three records in the data sequence, and we change to ues direct selection sort to finish the sorting procedure when recursive is near ending. According to the basic idea of DBSCAN, we designed and realized this algorithm. In the papar, we described the proceses in detail on how the algorithm proceeding, and also provided the core codes. In addition, the tool can acquire data conveniently and show result of spatial clustering by using ArcGIS Engine.In the end, we apply this tool to spatial clustering analysis of the point data in Urban Gridding Management Information System of shanghai pudong new area. As the managed objects are divided into managed components and events, we used two data sources. One is the point data that each point represents a stall-keeper on the road without license occurred in Meiyuan Xincun sub-district of Pudong New Area. Another one is the point data that each point represents a ash-bin in Jinyang Xincun sub-district of Pudong New Area. In the analysis of the former, we used different MinPts and Eps for clustering and chose one pare of them which provided a reasonable clustering result as the parameters for the follow-up clustering analysises. We finded out high-incidence areas of stall-keeper on the road without license of Meiyuan Xincun sub-district in four quarters of 2007. We discussed the results and finded out the defects in urban managements. In the analysis of the latter, we determined MinPts and Eps according to the setting standards of the ash-bin. We checked the status of the ash-bin's setting in Jinyang Xincun sub-district by using this tool. Through the practical application of DBSCAN algorithm, we validated the features of the algorithm, analysed and summarized the laws of spatial clustering results.