Research On Algorithms For Detecting Conditional Outliers Based On Spatial Topological Relations

Outlier detection is one of the important research topics in data mining. Outlier detection is aimed at discovering the unexpected, interesting, and useful knowledge. In the spatial database, there are spatial relationships between objects. Therefore spatial outlier detection is different from traditional outlier detection. In this paper, we do research on spatial outlier detection.At present, the outlier detection research mainly focuses on high-dimensional outlier detection, constraint-based outlier detection and explanations of reasons of outliers. The so-called "condition" refers to a problem or a premise which is a specific part deduced from the structure of the data set. Conditional outliers may be no longer outliers when they are out of the current conditions. Therefore, in this paper, algorithms for detecting conditional outliers based on spatial topological relationships are deeply studied, and some innovative contributions are achieved as follows:(1) Algorithm DCOP_IR is proposed for detecting conditional outlier polygons based on inclusion relations.In this algorithm, inclusion relations and non-spatial attributes are used as similarity measurement criteria, and a density-based outlier detecting algorithm is firstly used for detecting spatial outliers for the whole databases, secondly used for detecting spatial outliers which satisfy some certain conditions. The points which are not the whole database outliers but the outliers under certain condition are called spatial conditional outliers. The experimental results show that DCOP IR is effective and efficient.(2) Algorithms DCOP_SA and DCOP_SA*are proposed for detecting conditional outlier points by the constraint of space adjacent relations. In these algorithms, adjacent relations between the points are used as a condition, they are used to divide neighborhoods, the non-spatial attributes of the points are used as comparative attributes to detect spatial local outliers. Then detecting outliers without considering adjacent relations of the points, the points which are not the all database outliers but the local outliers are called spatial conditional outliers. Based on DCOP_SA, DCOP_SA*is improved which uses index mechanism to enhance the efficiency of spatial adjacent relation computations. The experimental results show that DCOP_SA and DCOP SA*are effective and DCOP SA*is more efficient than DCOP SA.