Abstract: The time complexity of the density-based outlier detecting algorithm (LOF algorithm) is not ideal,which effects its applications in large scale datasets and high dimensional datasets．Under such circumstances,a new density-based outlier detecting algorithm (NLOF algorithm) was introduced．The main idea of the NLOF algorithm is as follows:the known information is used as much as possible to optimize the neighborhood query operation of adjacent objects in the process of neighborhood searching of a data object．This method is adopted in neighborhood computing and searching in this paper．Firstly,clustering algorithm is taken as a preprocessing,and local outlier factors are calculated only for the data objects out of clusters．Secondly,the local outlier factors for the data objects out of clusters are calculated in the same way as calculating the local outlier factors in LOF algorithm．Leave-one partition information gain is introduced in the process of calculating the local outlier factor．The weight of attribute is determined by leave-one partition information gain．The weighted distance is used in calculating distances between objects．Extensive experimental results show the advantages of the proposed method．NLOF algorithm can improve the outlier detection accuracy,reduce the time complexity and realize the effective local outlier detection.

Key words: Data mining,Outlier detection,Information entropy,Clustering