From Adjacent Natural Neighbors Typical Clustering Method Comparison

Spatial clustering is an extremely important research direction which uses mathematical modeling to extract the models of spatial characteristics as prerequisite, utilizes specified similarity measure to calculate how much degree of close among spatial entities, and then interprets and evaluates the aggregation of distribution of spatial entities in spatial data mining and knowledge discovery field. The direct clustering of the geometric shape of spatial target is the symbol which distinguishes the difference between spatial clustering and traditional clustering. However, the variety of spatial entities shapes and the randomicity of theirs' locations make the similarity gets hard to define and calculate between geometric features, thus, it brings the limiting to the application of spatial clustering analysis. At present, the majority of commercial spatial database management systems are supporting the clustering analysis algorithms what utilize some kinds of distance as similarity measure, such as Euclidean distance, Manhattan distance, Mahalanobis distance, etc. In this case, clustering methods do not only lack the accurate expressions of complex shapes like points, lines and polygons, but also make difficult to calculate the degree of neighboring among features. Therefore, it leads these algorithms can not discover clusters of arbitrary shape by self-adaption. Moreover, especially for the processes of clustering which includes obstacle constraints, it can not be implemented by the traditional clustering algorithm because of basing on distance adjacency.Combining with experiment, from analyzing the lacks of above paragraphs, we could know that the prime reason comes from the limit of distance measure. It mainly performs in two aspects:(1) basic theory aspect, there are obviously gap between distance adjacency calculating models and the spatial recognition of human beings, the ideal distance definition can not easy to describe the real spatial complex distribution. (2) practical application aspect, distance adjacency calculating models ignored the external environment of practical application, and also lacks abilities to realize and deal with spatial obstacles, so that they reduce the accuracy and explanatory properties, restrict practical application.Based on Voronoi diagram, the natural adjacency spatial relationship was defined. It can effectively overcomes the lack of distance adjacency, and supplies an effectively approach for spatial data clustering. In this paper, our target is the implementation of two-dimensional spatial geometric data clustering. At first, we use distance adjacency measure, implement spatial zonal distributed data spots clustering based on improved TART2 neural network. Afterwards, considering about the complex spatial geometric properties and spatial data are separated by obstacles, we import natural adjacency measure, by dint of Voronoi polygons directly adjacent expression and optimal area threshold calculation, and then propose a clustering algorithm of spatial clustering base on natural adjacency (SCBNA). At last, integrating by practical applications, we make a comparison between distance adjacency and natural adjacency. At the same time, for effectively extracting Voronoi adjacency relationship, this paper proposes varying velocity Voronoi diagram composed algorithm based on raster data and full features Voronoi diagram generate method based on vector data. Besides, it analyzes the complexity and convergence of algorithm. Paper's contents and conclusions are divided into the following three points: (1) Classical ART2 neural network utilizes vector phase information as similarity measure to implement clustering. It has many characteristics such as good flexibility, relatively simple structure and strong recognition capability. However, it affects in two-dimension spatial data, not only includes pattern drift and vector model of information missing, but also its network cannot adaptively divide the spaces by different granularity, therefore it hard to adapt spatial data clustering with irregular shape distribution. In this paper, we propose a Tree-ART2 network model, it can keep the old patterns memories with spatial constraints Euclidean distance by long time memory (LTM) pattern, and then pull in the tree structure optimization, so it reduces the pattern mixing phenomenon happen and subjective requirements of vigilance parameter configuration. Comparison experiment results show that Tree-ART2 (TART2) network model is more adaptable to spatial data clustering by zonal distribution, and contains high plasticity and adaptability, is a typical distance neighboring clustering method.(2) Considering the real situation, obstacles(rivers, lakes, parks, railways and so on) split the continuity of spaces, so that it could not accurately express complex geometrical shapes of spatial obstacles by clustering methods with distance adjacency, in addition, it is hard to correctly define the spatial adjacency relationship of discrete entity. This paper introduces the Natural adjacency calculating method, determine adjacency relationship by recognition whether the two disjoined spatial objects share Voronoi boundary or not, and proposes a new clustering method with obstacle called spatial clustering base on natural adjacency (SCBNA). Through constructing full features Voronoi diagram, it accurately expresses the relative position between spatial entities by using natural adjacency measure, divide cluster into corresponding ownership regions by optimizing analysis area threshold, the algorithm could find arbitrary shapes of density gradient, accurate recognize the obstacle constraints spatial cluster targets without custom any parameters, it finally improved the accuracy and adaptability of clustering.(3) Inspecting the growing process of generator as a starting point, replacing weight constant to weight function, and describing growth velocity as time derivative pattern of weight distance, a new Voronoi diagram that called varying velocity Voronoi diagram (VVVD) was proposed. Its core concept is concerning the elevation variation of DEM, setting expansion the operation in morphological as fundament, establishing weight function with elevation variation, and convergency the expansion process which is depended on time consuming. In the field of expression of influence region and calculations of the Voronoi neighboring relationship, VVVD has greater practical applied value and significance.