Research On Minimal Negative Co-Location Patterns And Effective Mining Algorithms

With the continuous improvement of the accuracy of the Global Positioning System(GPS),location services have penetrated into all aspects of life,the data with spatial location information has also increased dramatically.In order to analyze and extract valuable information from these massive and complex data to support decision-making,spatial data mining arises at the historic moment.Spatial data mining is an important branch of data mining.It is a comprehensive use of technical methods to automatically mine previously unknown but potentially valuable knowledge from data with spatial location information,to reveal internal relations,essential rules,and development trends behind the spatial data.The spatial co-location patterns refer to a subset of a set of spatial features,the instances of which are frequently associated in space.Traditional co-location pattern mining algorithms can only mine prevalent positive patterns,and there are many valuable strong negative correlation patterns in the space,such as negative co-location patterns.The mining of such patterns also has great significance in some applications,and its support for decision-making cannot be underestimated.Due to the essential difference between the negative co-location patterns and the positive co-location patterns,the mining algorithm for prevalent positive patterns cannot be simply applied to the prevalent negative co-location pattern mining.As a result,the research of prevalent negative co-location pattern mining presents certain difficulties.There are three major problems in the existing negative co-location pattern mining algorithms.First,the mining result set is huge and difficult for users to research the patterns that they are interested in.Second,the efficiency of pruning is not ideal.As a result,it requires relatively long calculation time.Third,the mining results are lack of visual display.To solve the above problems,this thesis first explores the "upward inclusion" property of the negative co-location patterns,and puts forward the concept of the minimal negative co-location pattern;secondly,it proves that the minimal negative co-location pattern is an effective and compact representation of all prevalent negative co-location patterns,and all prevalent negative co-location patterns can be fully deduced,so as to solve the first problem.At the same time,three pruning strategies are proposed to improve the efficiency of negative co-location pattern mining,thus solving the second problem.A large number of experiments have been carried out on real and simulated data sets to verify the correctness and efficiency of the proposed algorithms in this thesis.At the same time,it is verified that the minimal negative co-location patterns usually has a high compression rate.Moreover,this thesis develops a prototype system for mining minimal negative co-location patterns,which can display and retrieve the mining results,and can draw the complete spatial data distribution of the minimal negative co-location pattern and the spatial data distribution of the specified area,so as to increase the interaction of users,thus solving the third problem.