Research On Spatio-temporal Outlier Detection Algorithm

In comparison with fast advances of data collection technology, data mining technology has obviously fallen behind, especially in the field of spatio-temporal outlier detection. Currently, so-called"data explosion"coexists with the"knowledge deficiency". It is in urgent need to develop spatial data mining technology so as to discover and extract the spatial knowledge from myriad spatial data. As an important branch of spatial data mining, spatio-temporal outlier detection focuses on the approaches to picking out those objects from the available datasets, whose attributes are significantly distinguished from those of other objects in their spatio-temporal neighborhood. In general, these objects could easily be ignored, even canceled as data noise. Detecting spatio-temporal outlier could lead to the discovery of unexpected, interesting, and useful spatio-temporal patterns for further analysis. On the basis of theory of spatial data mining, this dissertation thoroughly studies spatial and spatio-temporal outlier detection issues, by introducing information entropy theory and LLE dimensionality reduction technology into the process of spatial and spatio-temporal outlier detection, which could be used to deal with the shortcoming of existing algorithm.The dissertation proposes a graph-based spatially weighted outlier detection algorithm. Most of the spatial outlier detection algorithms available are developed from traditional cluster methods or outlier detection methods, which use spatial attributes for determining the neighborhood relationship. The computation of the outlierness of a spatial object is solely based on the non-spatial attributes of this object and its neighbors. This traditional approach ignores the intrinsic link between the spatial and non-spatial attributes of spatial objects, which does not fully mine the potential role of spatial attributes in computation of the outlier of a spatial object. Based on this observation, graph-based spatially weighted outlier detection algorithm proposed in this paper, uses both the spatial and non-spatial attributes for evaluation of the differences in spatial objects. In the procedure of computing the outlier of spatial objects, different weights are assigned to different neighbors based on information entropy theory. And then spatial outlier could be detected by means of methods based on graph. The algorithm fully covers the role of spatial attributes in the process of determining differences in spatial objects. So it could be used to solve the problem, such as the separation of spatial and non-spatial attributes in the process of detecting spatial outlier.The paper also puts forward an improved LLE-based spatio-temporal outlier detection algorithm. In study of this relatively new method for spatio-temporal outlier detection, a lot of new issues have to be addressed, including the definition of spatio-temporal neighbor, efficiency of the algorithm, and limitations of traditional outlier detection methods. Firstly, the paper offers the improved LLE algorithm to transform high-dimensional spatio-temporal data to low-dimensional data which can greatly reduce the computation. Secondly, spatio-temporal anomaly coefficient is calculated and used to detect spatio-temporal outlier. This algorithm takes the role of different kinds of attributes of spatio-temporal objects into account, and causes no changes in the local topology of the data. Therefore, it could be used to solve the problems in detecting spatio-temporal outlier from high-dimensional dataset.Finally the paper designs and develops a prototype of the spatio-temporal outlier detection system. This prototypical system is designed for the need of studying and applying based on software engineering principles. The prototype has a relatively advanced framework, stronger extendibility and practical functions. Case studies show that the prototype system has realized the basic task of detecting spatial and spatio-temporal outliers from the true dataset, which proves the efficiency of the algorithm proposed in the dissertation.