Chinese Journal of Computers   Full Text
Title	Study on Algorithms for Local Outlier Detection
Authors	XUE An-Rong JU Shi-Guang HE Wei-Hua CHEN Wei-He
Address	(School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang, Jiangsu 212013)
Year	2007
Issue	No.8(1455—1463)
Abstract &   Background	Abstract Outlier detection has attracted much attention recently. There are two kinds of outliers: global outliers and local outliers. In many scenarios, the detection of local outliers is more valuable than that of global outliers. To mine local outliers, it is more meaningful to assign to each object a degree of being an outlier. Some existing representative algorithms currently used for solving this problem are compared in detail, and their disadvantages are pointed out such as poor efficiency and the detection accuracy depending on the parameters given by the user. In general, the attributes of each data object can be categorized as the inherent attributes and the context attributes, the inherent attributes characterize the data object while the context attributes embody the relationship between this data object and the neighbor data objects. The context attributes is not intrinsic to the data object. In order to overcome those disadvantages mentioned above, this paper proposes to use the context attributes to determine the object neighborhood and use the inherent attributes to compute the outlier score. For spatial data, the attributes comprise the non-spatial dimensions and the spatial dimensions. The spatial attributes provide a location index to the data object. The neighborhood in the Euclidean space plays a very important role in the analysis of spatial data. The spatial attributes are used to determine spatial neighborhood and the non-spatial dimensions are used to compute the spatial outlier score. This paper also proposes a novel measure, spatial local outlier factor (SLOF), which captures the local behavior of datum in its spatial neighborhood. The experimental results show that proposed SLOF algorithm outperforms the other existing algorithms in detection accuracy, user dependency, scalability and efficiency. keywords outlier detection; local outlier factor; R*-tree; data mining; spatial outlier; trimmed mean background Outlier detection in large data sets is an active research field in data mining. All known outlier detection algorithms do not distinguish different kinds of attributes from each other. In these algorithms, all attributes of each data object are used as whole to formulation the neighborhood relationship, which is the common base for all existing outlier detection algorithms. In this paper, the authors argue that it is not propriety. In the research, the authors indicated that attributes of each data object fall into two categories: inherent attributes and context attributes. The context attributes are used in defining the neighborhood relationship. The inherent attributes are used in the computing of local outlier degree. The work is supported by the National Natural Science Foundation of China with the title "Research on the Novel Access Control Model of Location-based Service Based on the Spatial Location of Mobile Users"(No.60603041), the Natural Science Foundation of Jiangsu Education Council with the title "Research on Algorithm for Spatio-Temporal Outlier Detection"(No. 05KJB520017), the Natural Science Foundation of Jiangsu with the title "Study of the Spatial Extension of RBAC Model"(No. BK2006073). The result in this paper belongs to the part of abnormal user behavior detection. In the project "Research on the Novel Access Control Model of Location-based Service Based on the Spatial Location of Mobile Users", the proposed novel access control model(MULBAC) makes access control decisions based on the synthesized information from the result of outlier detection and the static access control policy. It is focused on proposing a new method for the abnormal user behavior detection, so as to provide new tools for the access control mechanism.